Video summary

ICML 2024 Tutorial - Graph Learning: Principles, Challenges, and Open Directions

Main summary

Key takeaways

Educational

Main ideas, concepts, and lessons

1) What “graph learning” is and why it matters

  • Graphs are represented by nodes and edges (e.g., via an adjacency matrix).
  • Graph learning refers to machine learning on graph-structured data.
  • Typical task types:
    • Node-level (e.g., classification/regression)
    • Edge-level (e.g., link prediction)
    • Graph-level (predict a property of the whole graph)
  • Many real-world domains naturally form graphs: molecules, road networks, etc.

2) Why graphs are hard compared to sequences/images

  • Classic deep learning success:
    • CNNs for grid/pixel-like data (weight sharing, local neighborhoods)
    • Transformers for sequences (token ordering + positional encodings; attention)
  • Graphs have irregular topology:
    • Neighborhood size/structure varies widely across nodes (dense vs. sparse regions).
  • Key tension:
    • How to learn representations when neighborhood structure is non-uniform.

3) Early graph representation learning: node/graph embeddings and random walks

  • Node embeddings / graph kernels map nodes to a low-dimensional space so similar nodes have similar embeddings.
  • Approaches mentioned:
    • DeepWalk
    • node2vec (referred to with “notak”)
  • Core similarity idea:
    • Nodes are similar if they co-occur on random walks starting from them.
  • Random-walk driven optimization:
    • Sample random walks from nodes
    • Collect co-occurrence statistics
    • Train embeddings with an SGD-optimized loss
  • Differences highlighted:
    • DeepWalk: fixed-length biased random walks (bias described broadly)
    • node2vec: biased walks interpolating between local exploration and longer-range traversal
  • Example:
    • Karate graph node classification recovered from topology via embeddings.

4) Graph Neural Networks (GNNs) via message passing

GNNs address limitations of embedding-only methods:

  • Better integration of features
  • Better inductive/generalization (e.g., across different graphs, not only seen nodes)

Message passing framework (core methodology)

Inputs:

  • Initial node features (h_u^{(0)})
  • Node/edge attributes

For each layer/time step (t):

  1. Message function: compute (m_{uv}^{(t)}) from sender node representation, edge features, etc.
  2. Aggregation at node (u):
    • Aggregate messages from all neighbors of (u) using a permutation-invariant function (f_{\text{aggregate}}) (e.g., sum/mean/max, “Deep Sets” style).
  3. Update:
    • Combine aggregated neighborhood information with the node’s own representation to get (h_u^{(t+1)}).

Optional readout layer:

  • Graph-level: combine all node embeddings
  • Edge-level: combine embeddings of endpoints (u, v)

Architectural examples

  • GCN (Graph Convolutional Network):
    • Uses normalized adjacency multiplication with learnable weights; equivalent to degree-normalized neighborhood aggregation.
  • GraphSAGE:
    • Uses sampling (e.g., multi-hop neighborhoods) to control explosion and improve efficiency.
  • GAT (Graph Attention Networks):
    • Uses attention weights (\alpha_{uv}) (softmax-like) to weight neighbor contributions non-uniformly.

5) Tools/metrics from spectral graph theory (Adrian’s section)

Objects:

  • Degree matrix (D)
  • Adjacency/graph Laplacian and its normalized variant
  • Eigenvalues/eigenvectors to study graph signal behavior

Interpretation:

  • The graph Laplacian relates to minimizing variability of a signal over edges.

Key spectral concepts:

  • Laplacian eigenvectors:
    • First eigenvector relates to constant signals
    • Higher eigenvectors capture more oscillatory/sharp structure
  • Cheeger constant (also tied to M-Cut):
    • Measures the “bottleneck” (minimum edge cuts separating communities)
    • Connected to the spectral gap (second eigenvalue)
  • Effective resistance / commute time:
    • A global random-walk-based distance capturing long-range connectivity
    • Adding/removing edges can change effective resistance even when shortest paths don’t

6) Graph Transformers: different computation graph from input graph (Amia’s section)

Transformers are sequence-oriented; for graphs:

  • Graph Transformers use attention, but their computational graph is often different from the input graph.

Major differentiators:

  • In GNN message passing:
    • computation follows input edges
  • In many graph Transformers:
    • computations connect many/all node pairs, losing the original graph’s inductive bias

Challenges and solutions:

  • Inductive bias loss:
    • Mitigated via positional encodings for graphs
  • Positional encodings:
    • Often derived from Laplacian eigenvectors (spectral positional encodings) or learned variants
  • Graph Forer:
    • Adds centrality encoding and attention bias based on shortest path distance
  • Scaling/efficiency:
    • Full attention is typically quadratic in the number of nodes
    • Uses sparsification approaches
  • Example: XFormer (expander-based sparse computation):
    • Combines:
      • edges from the original graph (keeps inductive bias)
      • expander graphs for global connectivity with linear edges
      • virtual/global “sync” nodes connected to all nodes
    • Reported to improve long-range dependency performance on long-range benchmarks

7) Expressivity: what functions can GNNs represent?

Expressivity is analyzed via the Weisfeiler–Leman (WL) hierarchy and its relation to message passing GNN limits.

1-WL test

  • Iterative color refinement:
    • Start with initial node colors
    • Update colors based on multisets of neighbors’ colors
    • Equivalent to hashing neighbor structure
  • Converges:
    • Distinguishes some non-isomorphic graphs
    • But fails on certain pairs

Key limitation

  • Vanilla MPNNs are bounded in expressivity by the WL test:
    • They cannot distinguish graphs that WL cannot distinguish.

Higher-order WL

  • k-WL is more expressive by reasoning over tuples of nodes (k-tuples), at higher cost.

Going beyond WL limitations (three buckets)

  1. Add more features
    • Random features can already exceed 1-WL
    • Graph Substructure Networks (GSN): count node/edge appearances within structural substructures (“orbits”)
    • Affinity/resistive features:
      • effective resistance, hitting times, resistive embeddings
  2. Modulate message passing
    • Attention (GAT) reweights neighbors
    • Identity-aware / directional / anisotropic variants
  3. Alter the underlying graph / computation
    • Higher-order GNNs
    • Graph Transformer can be interpreted as changing computation connectivity

8) Generalizability: expressivity doesn’t always guarantee performance

  • More expressive models can overfit, but in practice:
    • improved test performance is often observed
  • Statistical learning theory lens:
    • VC dimension can bound test error using training error + a capacity term
    • Work discussed aims to characterize VC dimension for graph neural networks
  • Open/practical insight:
    • Why expressivity improves generalization even with similar training set sizes is not fully settled
    • Margin-based perspectives and learning-theory analyses are being developed

9) Practical challenges of MPNNs: diffusion-induced failure modes

Issues framed through diffusion/mixing on graphs:

  1. Under-reaching

    • Nodes only exchange information within roughly K layers
    • For long-range tasks (or heterophilic graphs), important interactions may require more hops than feasible

  2. Over-smoothing

    • As depth increases, representations converge toward similar values
    • In the limit, node features collapse (related to Laplacian/random-walk mixing)
    • This reduces accuracy

  3. Over-squashing

    • Multi-hop neighborhoods can grow exponentially, but information must be compressed into a fixed-size vector
    • Creates a bottleneck: signals become insensitive across distant regions
    • Related to effective resistance / Cheeger-like bottlenecks

Mitigation strategies (examples mentioned):

  • Normalization, skip connections
  • Graph sparsification/rewiring to adjust spectral properties (spectral gap, mixing)
  • Weight matrix/dynamics control, orthogonal or norm-reducing transformations
  • Residual/high-frequency dominant behavior emphasis
  • Virtual nodes as shortcut paths to reduce squashing/bottlenecks
  • Advanced architectures that adaptively learn message filters, depths, or rewiring rules

10) Measuring these phenomena (squashing emphasis)

  • Over-squashing can be studied with:
    • Sensitivity metrics measuring how features at one node/layer affect another
    • Example metric: Jacobian-based sensitivity and a symmetric variant
  • Bounding tools connect:
    • spectral gap / Cheeger constant
    • effective resistance
    • total effective resistance as a global measure related to pairwise interactions

11) Open questions (key themes)

  • Over-smoothing:
    • fragile in practice; sometimes mitigated if smoothing aligns with label-relevant directions (not too much / not too little)
  • Over-squashing:
    • improvements may depend on the metric used (shortest path may not change even if effective resistance/normalized quantities do)
  • Long-range dependency + heterophily:
    • existing metrics may not capture how far relevant features/labels spread
  • Broader direction:
    • consider probabilistic perspectives—graph structure usefulness for distributions over random variables (graph structure learning / deep generative graph models mentioned)

Methodologies / instruction-like content

A) Message Passing Neural Network (MPNN) step-by-step procedure

Given:

  • Node features (h_u^{(t)})
  • Edge features (optional)
  • Neighbor set (N(u))

Repeat for (t = 0 \ldots K-1):

  1. Compute messages for each neighbor (conceptually):
    • (m_{uv}^{(t)} = \text{Message}(h_u^{(t)}, h_v^{(t)}, e_{uv}))
  2. Aggregate messages at each node (u):
    • (\text{Agg}u^{(t)} = f : w \in N(u)}))}}({m_{vw}^{(t)
    • Require permutation invariance (sum/mean/max or DeepSets-like functions)
  3. Update node state:
    • (h_u^{(t+1)} = \text{Update}(h_u^{(t)}, \text{Agg}_u^{(t)}))

Readout (depends on task):

  • Node-level: output from (h_u^{(K)})
  • Edge-level: output from function((h_u^{(K)}, h_v^{(K)}))
  • Graph-level: output from pooling/combining ({h_u^{(K)}}_{u\in V})

B) Weisfeiler–Leman (WL) style color refinement (expressivity test)

  • Initialize:
    • assign all nodes the same color (or use structural initialization)
  • Iterate:
    • for each node (u), form the multiset of neighbor colors
    • update the node’s color by hashing/encoding that multiset
  • Compare graphs:
    • run in parallel on both graphs
    • if color multisets differ at any iteration ⇒ graphs are not isomorphic
    • if never differ ⇒ heuristic suggests isomorphism, but false positives exist

Speakers / sources featured (as named in subtitles)

Tutorial presenters

  • Amia (Google Research; research scientist) — first main presenter (speaker name partially mis-transcribed as “AA”)
  • Adrian (PhD student at Ellis alante; co-presenter; name partially mis-transcribed)

Panel discussion participants (on-stage and remote)

  • Brian Perzzi (Google Research)
  • Michael Bronstein (DeepMind; professor of artificial intelligence)
  • Christopher Morris (AEN University)
  • Michael GIN (remote; Intel Labs)

Other named researchers mentioned within the talk (not speakers in the panel)

  • Vaswani (referenced via Transformer work “vaswani Adel” / Vaswani et al.)
  • Background references include:
    • Alon (e.g., graph limits/bottlenecks)
    • Dani / “Franchesco djani” (continuous models/differential equations + graph networks)
    • Morris (also appears as panelist)
    • Spielman / van der (effective resistance attribution)
    • Alon, J. and C. (CTP): “Alon Java” and “Topol” (mis-transcribed; context about squashing bottlenecks/binary tree experiments)

Subtitles are auto-generated and contain transcription errors; some proper names may be misspelled or partially omitted.

Original video