PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Oversquashing in GNNs through the Lens of Effective Resistance

Mitchell Black, Zhengchao Wan, Amir Nayyeri, Yusu Wang

arXiv:2302.06835v2cs.LG

TL;DR

Message-passing GNNs can struggle to transmit information between distant nodes when it is compressed through graph bottlenecks. The paper bounds oversquashing using effective resistance and rewires graphs to reduce total resistance; it reports improved GNN performance, while noting that broader benchmarks are needed to compare rewiring approaches.

  • Problem

    Oversquashing makes it difficult for message-passing GNNs to transmit distant-node information through graph bottlenecks.

    Source: §1 · p. 1

  • Method

    The paper relates information passing between nodes to effective resistance, uses total effective resistance as a global measure, and adds edges to reduce it.

    Source: §1 · p. 2

  • Results

    Rewiring based on total effective resistance improves GNN and relational-GNN performance on graph-classification tasks and outperforms SDRF while performing similarly to FoSR.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    The paper presents total effective resistance as a bound on total graph oversquashing and reports that lowering it improves GNN performance.

    Source: §6 · p. 8

    Broader graph benchmarks are needed to compare rewiring methods because adding edges both decreases total resistance and increases spectral gap.

    Source: §6 · p. 8

Abstract

from arXiv · show

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the effective resistance between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use total effective resistance as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

1. Introduction

Message-passing GNNs can lose long-range information at graph bottlenecks as their receptive neighborhoods grow. This paper connects oversquashing to effective resistance, uses total effective resistance to guide graph rewiring, and reports improved performance compared with existing methods.

1. Introduction

  • Oversquashing occurs when information from long-range interactions through graph bottlenecks has negligible impact as larger neighborhoods are aggregated.The information from potentially exponentially many nodes is compressed into fixed-sized node vectors.Source: §1 · p. 1
  • Effective resistance can bound oversquashing between nodes: lower resistance corresponds to less oversquashing when messages pass between them.The paper states that its bounds apply between any two nodes at any GNN layer, unlike the cited curvature analysis, which applies only within two hops.Source: §1 · p. 2
  • The paper uses total effective resistance as a global oversquashing measure and adds edges to minimize it.This extends its pairwise effective-resistance analysis into a graph-rewiring strategy.Source: §1 · p. 2
  • The rewiring method outperforms curvature-based SDRF and has similar performance to spectral-gap-based FoSR.Source: §1 · p. 2
  • Unlike approaches targeting high-resistance edges, this paper targets pairs with high resistance by reducing total resistance; that quantity reflects the Laplacian spectrum, including the spectral gap.Source: §1 · pp. 2–3

2. Background

This section introduces spectral-graph notation and describes graph neural networks as iterative neighborhood-aggregation models, including relational variants for rewired graphs.

2.1. Matrices and Spectra of Graphs.

  • A graph is represented by adjacency, degree, and Laplacian matrices, with normalized adjacency and Laplacian defined from the degree matrix.Source: §2.1 · p. 3
  • The normalized Laplacian eigenvalues lie in [0, 2], while normalized-adjacency eigenvalues satisfy μ_i = 1 − λ_i and lie in [−1, 1].The normalized adjacency matrix has eigenvalue 1 and has eigenvalue −1 exactly when the graph is bipartite.Source: §2.1 · p. 3

2.2. Graph Neural Networks

  • A GNN iteratively updates node features by aggregating features from neighboring nodes through learnable functions.The described class is a strict subset of the more general message-passing neural networks.Source: §2.2 · p. 3
  • Relational GNNs distinguish edge types and are used after rewiring to retain original-graph information while exploiting the new graph structure.Each neighbor set is specified by its incident edge type.Source: §2.2 · p. 3

3. Effective Resistance and Oversquashing

Effective resistance captures pairwise connectivity through paths and provides a way to relate graph structure to information flow in GNNs. The section develops pairwise and graph-wide bounds, then examines how spectral gap relates to oversquashing.

3. Effective Resistance and Oversquashing

  • More and shorter paths between two vertices imply lower effective resistance, which is associated with less oversquashing between them.The Jacobian analysis connects this relationship to how strongly one node's features can influence another's.Source: §3 · p. 4, §3.1 · p. 4

3.1. Effective Resistance and the Jacobian of GNNs.

  • For non-bipartite graphs, Theorem 3.3 bounds the Jacobian between a pair of node features using their effective resistance.The analysis applies to any vertex pair and any number of GNN layers, unlike the cited Balanced Forman curvature bound, which is limited to distance-2 pairs and two consecutive layers.Source: §3.1 · pp. 4–5
  • Total effective resistance, the sum of pairwise resistances, bounds the sum of Jacobians between all node pairs.This makes total resistance a graph-wide measure of message-passing influence.Source: §3.1 · p. 4

3.2. Effective Resistance and the Spectral Gap

  • The spectral-gap connection yields a looser bound than total resistance, and the section argues that oversquashing may depend on the entire Laplacian spectrum.The discussion contrasts prior spectral-gap motivation, which lacked direct theoretical evidence for bounding information passing, with the paper's effective-resistance bounds.Source: §3.2 · pp. 5–6

4. Minimizing Total Resistance by Rewiring

The section derives how adding an edge changes total resistance, then uses that result to greedily select edges that reduce it. It also notes why this single-edge strategy does not directly solve the multiple-edge selection problem.

4. Minimizing Total Resistance by Rewiring

  • The squared biharmonic distance is proportional to the negative partial derivative of total resistance with respect to an edge’s weight, linking it to global connectivity.This relation motivates using biharmonic distance to measure an edge’s effect on the graph.Source: §4 · p. 6
  • Theorem 4.1 calculates an added edge’s decrease in total resistance using its biharmonic distance and effective resistance.The formula gives the basis for ranking candidate edges by their contribution to reducing total resistance.Source: §4 · p. 6
  • GTR repeatedly adds the edge maximizing B^2_uv/(1 + R_uv), restricting additions to vertices already in the same connected component.The paper adds edges only; it does not remove or replace existing edges.Source: §4 · pp. 6–7
  • GTR can be implemented naively in O(n^3) time, while more sophisticated algorithms take O(m poly log n + n^2 poly log n).The paper uses “rewiring” here to mean adding edges, unlike some prior uses that replace edges.Source: §4 · pp. 6–7
  • The reduction from adding an edge is non-monotonic across nested graphs, so an edge’s contribution can grow as other edges are added.The paper gives an example where the two individually highest-ranked edges are not the pair that most reduces total resistance.Source: §4 · p. 7
  • Finding the k edges that most reduce total resistance is NP-hard, making a heuristic preferable to exact selection.The paper reports that the best known algorithm searches over all sets of k edges.Source: §4 · p. 7

5. Experiments

Across graph-classification experiments, GTR and FoSR generally outperform DIGL, SDRF, and no rewiring, with architecture-dependent comparisons between GTR and FoSR. The experiments also compare their effects on the spectrum and examine edge-count and hidden-dimension variations.

5.1. Spectral Gap vs. Total Resistance

  • On Cora’s largest connected component after 50 edge additions, FoSR raises the first few Laplacian eigenvalues more, while GTR raises larger eigenvalues more and reduces total resistance more.Figure 4 compares the 50 smallest eigenvalues and the spectral gap and total resistance.Source: §5.1 · pp. 7–8, Figure 4 · p. 7

5.2. Graph Classification

  • The graph-classification comparison includes Last FA, All FA, DIGL, SDRF, FoSR, and no rewiring, across GCN, R-GCN, GIN, and R-GIN convolutions.For GTR, the experiments tune the number of added edges and fix other hyperparameters.Source: §5.2 · p. 8
  • GTR and FoSR generally outperform DIGL, SDRF, or no rewiring; they perform similarly on GIN and R-GIN, while GTR often substantially outperforms FoSR on R-GCN.The authors report that both global strategies outperform local-curvature SDRF, especially for relational GNNs.Source: §5.2 · p. 8

5.3. Edge Ablation

  • No single edge count works across datasets, and performance does not necessarily rise as total resistance falls.The authors therefore recommend tuning the number of added edges during training.Source: §5.3 · p. 8

5.4. Hidden Dimension Ablation

  • Rewiring and increasing hidden dimension are complementary in the reported experiments: either or both increases GNN performance.The experiments vary both the number of added edges and hidden dimension.Source: §5.4 · p. 8

6. Concluding Remarks

The paper concludes that effective resistance bounds oversquashing and that lowering total resistance improves GNN performance. It also identifies limits in comparing resistance with the spectral gap and in choosing multiple shortcut edges.

6. Concluding Remarks

  • Total-resistance-based rewiring significantly improves GNN and R-GNN performance on graph classification tasks.The authors report that lowering total resistance improves GNN performance.Source: §6 · p. 8
  • The total-resistance bound on oversquashing is tighter than the spectral-gap bound, though their effects remain difficult to contrast.Adding edges necessarily decreases total resistance while increasing the spectral gap.Source: §6 · p. 8
  • Finding the optimal set of k edges is NP-hard, and whether the greedy strategy approximates that set remains unclear.The paper leaves efficient approximation algorithms and better heuristics for future work.Source: §6 · pp. 8–9

A.1. Proof of Lemma 3.1

  • Effective resistance between u and v can be characterized as the minimum squared 2-norm of any uv-flow.The proof of Lemma 3.1 applies a general matrix fact twice.Source: §A.1 · p. 12

A.2. Proof of Lemma 3.2

  • Lemma 3.2 assumes bounded Jacobians for its layer maps, and its proof proceeds by induction on layer depth.The proof splits the Jacobian of ϕ_r into argument blocks and bounds their norms.Source: §A.2 · pp. 12–13

A.3. Proof of Theorem 3.3

The proof of Theorem 3.3 combines an effective-resistance expression with a Jacobian bound. The proof of Theorem 4.1 uses the Laplacian representation of total resistance to derive its change when an edge is added.

A.3. Proof of Theorem 3.3

  • For non-bipartite graphs, the proof uses a spectral-series expression to rewrite effective resistance.The series representation is established using the spectral decomposition of the normalized adjacency matrix.Source: §A.3 · pp. 13–14
  • Theorem 3.3's proof combines an effective-resistance formula with the Jacobian bound from Lemma 3.2.The theorem's stated conditions include bounds on the layer-map Jacobians and a non-bipartite graph.Source: §A.3 · p. 14

A.4. Proof of Theorem 4.1

  • Adding an edge changes the Laplacian by a rank-one term, and the proof applies Woodbury’s formula to derive the total-resistance change.The argument expresses total resistance using a trace involving the Laplacian pseudoinverse.Source: §A.4 · pp. 15–16

B.1. Asymptotic Analysis

The naive GTR implementation has cubic preprocessing cost and quadratic per-edge updates. The appendix also describes faster estimation options and reports a timing comparison for computing 50 additional edges.

B.1. Asymptotic Analysis

  • O(n^3 + kn^2) is the naive GTR runtime when adding k edges.The initial all-pairs computations take O(n^3), while each edge selection and update takes O(n^2).Source: §B.1 · p. 16
  • Woodbury updates apply here because adding an edge to a connected graph changes the Laplacian in a way orthogonal to its kernel.The appendix cautions that Woodbury’s formula cannot generally update a matrix pseudoinverse.Source: §B.1 · p. 16
  • O(m poly log n + n^2 poly log n) time can estimate all-pairs effective resistance and biharmonic distance using Laplacian solvers and random projection.The appendix also describes computing the pseudoinverses using Laplacian solvers.Source: §B.1 · p. 17

B.2. Experimental Analysis

  • Table 2 reports the seconds needed by FoSR and GTR to compute 50 additional edges.The appendix says its fastest found GTR implementation used the naive algorithm with GPU pseudoinverse computation.Source: Table 2 · p. 17, §B.2 · p. 17

C. Counterexamples to the Optimality of GTR.

GTR selects the single edge that most reduces total resistance, but its greedy choices need not form the best multi-edge set. The examples also show that an edge’s resistance reduction can increase after another edge is added.

C. Counterexamples to the Optimality of GTR.

  • Theorem 4.1 guarantees GTR’s best single edge, but not the best set of k edges when k > 1.The 5-vertex path is given as a counterexample.Source: C. Counterexamples to the Optimality… · p. 17, Figure 5 · p. 17
  • Rtot ≈8.18 for GTR’s two-edge choice on the 5-vertex path, versus ≈7.67 for the pair that most decreases total resistance.GTR first adds the edge connecting the path’s first and last vertices.Source: Figure 5 · p. 17
  • On the 20-vertex path, the red edge reduces total resistance by ≈30.33 alone and ≈40.17 after the endpoint edge is added.This illustrates that an edge’s decrease in total resistance is not monotonic as the graph changes.Source: Figure 6 · p. 17, C. Counterexamples to the Optimality… · p. 17

D. Experimental Details

The experiments use randomized data splits and report averaged test accuracy; Figure 7 indicates that GTR appears to reduce total resistance more than FoSR.

D. Experimental Details

  • Test accuracy is averaged over 100 random splits with 95% confidence intervals, using random 80%/10%/10% train/validation/test splits.Hyperparameter search uses average accuracies over 10 randomly generated splits.Source: D. Experimental Details · pp. 17–18
  • Table 3 reports dataset-level edge counts for GTR and selected FoSR runs, while Table 4 lists shared graph-classification hyperparameters.FoSR counts are shown only when the edge-ablation run outperformed the run reported by Karhadkar et al. (2022).Source: Table 3 · p. 18, Table 4 · p. 18

E. Total Resistance vs. Number of Edges Added

F. Edge Ablation

The edge-ablation experiments show dataset-dependent accuracy responses: a few added edges often yield the largest gains, and adding more does not consistently help.

F. Edge Ablation

  • The edge-count comparison uses R-GIN and tests adding between 0 and 50 edges across graph-classification datasets.The experiments follow the procedure described in Appendix D.Source: F. Edge Ablation · p. 18
  • Accuracy responses vary by dataset, with no single tested edge count maximizing performance across datasets.Proteins and IMDB-Binary show an initial jump followed by little improvement, while Enzymes accuracy nearly only rises through the 50-edge limit.Source: F. Edge Ablation · p. 18
  • For almost all datasets, accuracy improves fastest after adding a few edges.A possible explanation offered is that total resistance decreases most rapidly with the first few added edges.Source: F. Edge Ablation · p. 18

G. Hidden Dimension Ablation

The hidden-dimension ablation compares rewiring and model width using R-GIN; both rewiring and increasing hidden dimension generally improve classification accuracy.

G. Hidden Dimension Ablation

Loading 2302.06835v2…