PaperlayerView exact revision on arXiv

Source-linked AI summary

FoSR: First-order spectral rewiring for addressing oversquashing in GNNs

Kedar Karhadkar, Pradeep Kr. Banerjee, Guido Montúfar

arXiv:2210.11790v2cs.LGstat.ML

TL;DR

GNNs can have difficulty capturing long-range interactions: rewiring to improve connectivity can also cause oversmoothing. The paper combines first-order spectral rewiring with a relational architecture that preserves the original graph structure. It reports improved performance on several graph-classification benchmarks and theoretical guarantees against oversmoothing.

  • Problem

    GNNs can struggle with long-range interactions because information may be oversquashed, while adding too many edges can cause oversmoothing.

    Source: §1 · pp. 1–2

  • Method

    FoSR iteratively adds edges based on first-order spectral-gap improvement, while relational rewiring distinguishes added edges from original ones to preserve the input topology.

    Source: §4 · pp. 6–7

  • Results

    FoSR typically achieves the best classification accuracy among rewiring methods with relational rewiring, and the proposed methods significantly improve GNN performance on several graph-classification benchmarks.

    Source: §5 · p. 9, §6 · p. 10

  • Takeaways & Limitations

    Relational rewiring preserves the original graph structure while adding connectivity and is shown to prevent oversmoothing with theoretical guarantees.

    Source: §6 · p. 9

Abstract

from arXiv · show

Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph topologies it leads to inefficient information propagation and a problem known as oversquashing. This has recently been linked with the curvature and spectral gap of the graph. On the other hand, adding edges to the message-passing graph can lead to increasingly similar node representations and a problem known as oversmoothing. We propose a computationally efficient algorithm that prevents oversquashing by systematically adding edges to the graph based on spectral expansion. We combine this with a relational architecture, which lets the GNN preserve the original graph structure and provably prevents oversmoothing. We find experimentally that our algorithm outperforms existing graph rewiring methods in several graph classification tasks.

1 INTRODUCTION

GNNs struggle to capture long-range interactions because shallow networks underreach, while deeper networks can oversquash information or oversmooth node features. The paper proposes relational rewiring and FoSR to improve connectivity while preserving original topology, and reports improved classification accuracy and faster spectral expansion.

1 INTRODUCTION

  • GNNs face underreaching with few layers, oversquashing when long-range information is compressed, and oversmoothing when repeated convolutions make node features indistinguishable.These problems arise in different layer-depth regimes and limit the capture of long-range interactions.Source: §1 · pp. 1–2

1.1 MAIN CONTRIBUTIONS

  • Relational rewiring labels added edges separately, preserving the input topology while using added connectivity; Theorem 3 shows this approach prevents oversmoothing.The framework applies to rewiring methods that sequentially add edges.Source: §1.1 · p. 2
  • FoSR adds the edge with the greatest first-order increase in spectral gap, targeting improved graph connectivity.The paper contrasts its approach with earlier rewiring methods based on curvature or spectral-gap measures, including SDRF and G-RLEF (Banerjee et al., 2022).Source: §1.1 · p. 2, §1.2 · p. 3
  • Experiments report faster spectral expansion and improved test accuracy against several baselines on graph-classification tasks; relational structure significantly boosts test accuracy.The introduction points to Table 1 for the classification results.Source: §1.1 · pp. 2–3

1.2 RELATED WORKS

2 PRELIMINARIES

The preliminaries introduce spectral graph quantities used to describe connectivity and define relational message passing. They also give examples of relational GNN layers and their non-relational special cases.

2.1 BACKGROUND ON SPECTRAL GRAPH THEORY

  • The normalized Laplacian is defined from the adjacency and degree matrices, and its second eigenvalue is the spectral gap, with a larger gap indicating good spectral expansion.The preliminaries also relate spectral gap to the Cheeger constant.Source: §2.1 · pp. 3–4

2.2 BACKGROUND ON RELATIONAL GNNS

  • A general R-GNN layer uses relation-specific message-passing functions and an update function; a classical GNN is recovered when there is only one relation.Source: §2.2 · p. 4
  • R-GCN, GCN, and GIN layers are presented as special cases of the general relational GNN formulation.For R-GCN, the relation-specific learned linear maps and self-loop relation are described in the preliminaries.Source: §2.2 · p. 4

3 RELATIONAL REWIRING OF GNNS

Relational rewiring retains the original graph while adding connectivity, giving an R-GCN separate edge relations to regulate smoothing. The paper proves that R-GCN layers can attain a range of smoothing rates and reports empirical evidence on Dirichlet energy.

3.1 RELATIONAL REWIRING

  • Original and added edges receive separate relation types, allowing the R-GCN to use added edges without sacrificing the original graph structure.The relations have separate weights, so the model can use original edges for structural features and rewired edges to transmit information.Source: §3.1 · p. 4
  • Separate relation weights give the model flexibility to counterbalance excessive added edges and regulate smoothing.In the stated worst case, the model can set most added-edge weights to zero and focus on the original graph.Source: §3.1 · p. 4

3.2 RATE OF SMOOTHING FOR R-GCN WITH REWIRING

  • Adding edges can make a vanilla GCN oversmooth, producing similar node representations when the input graph has a high spectral gap.The section uses Dirichlet energy to characterize smoothness of node features over a graph.Source: §3.2 · p. 5
  • For a graph G1 and its rewiring G2 = (V, E1 ∪ E2), an R-GCN layer with relations E1 and E2 can smooth G2 at any rate λ ∈ [0, λ2(L(G2))] by choosing Θ, Θ1, and Θ2.Source: §3.2 · p. 5
  • R-GNNs empirically achieve lower Dirichlet energy than GNNs.The paper reports this comparison in Appendix B.3.Source: §3.2 · p. 6

4 FOSR: FIRST ORDER SPECTRAL REWIRING

FoSR adds edges sequentially using a first-order approximation to spectral-gap improvement. It estimates the second eigenvector iteratively rather than computing a full eigendecomposition, and the paper reports faster spectral expansion than SDRF and G-RLEF.

  • FoSR has a faster rate of spectral expansion than SDRF and G-RLEF.The paper presents spectral expansion rate as a determinant of oversquashing.Source: §4 · p. 6
  • FoSR selects edges using a first-order approximation to spectral-gap improvement, avoiding an expensive spectral-gap computation for every possible edge.The direct search would require computing eigenvalues for O(n^2) different matrices.Source: §4 · pp. 6–7
  • At each iteration, FoSR approximates the second eigenvector with power iteration, adds an edge, and updates the approximation without a full eigendecomposition.The algorithm repeatedly alternates edge addition and power iteration.Source: §4 · p. 7
  • The initial power-iteration count r is typically 5–10, while the edge-addition count k is problem-specific and tuned during training.The paper says k can be chosen to increase the spectral gap sufficiently.Source: §4 · p. 8
  • FoSR costs O(kn^2) operations in general, with relaxations that reduce the total cost to O(km).Each power iteration costs O(m); the relaxed edge search can also take O(m) per added edge.Source: §4 · p. 8

5 EXPERIMENTS

The experiments compare graph-rewiring approaches on graph-classification benchmarks using matched GNN architectures for each dataset. Relational rewiring improves accuracy across methods, and FoSR typically performs best among rewiring methods when relations are used.

  • The benchmark covers six TUDataset graph-classification tasks identified as requiring long-range interactions.The datasets are REDDIT-BINARY, IMDB-BINARY, MUTAG, ENZYMES, PROTEINS, and COLLAB.Source: §5 · p. 8
  • Compared methods include DIGL, SDRF, and fully adjacent rewiring of either the last layer or every layer.SDRF is tested both in its original edge-addition-only form and with relational rewiring.Source: §5 · p. 8
  • For each dataset, the rewiring methods use the same GNN architecture, with method-specific rewiring hyperparameters tuned separately.The number of layers, hidden dimension, and dropout probability are held constant across methods for that dataset.Source: §5 · p. 8
  • Test accuracy is evaluated after selecting configurations using validation accuracy across 100 random train-validation splits of the development set.The test set comprises 10% of graphs and is used once for the selected configurations; test results report 95% confidence intervals.Source: §5 · pp. 8–9
  • FoSR typically achieves the best classification accuracy among rewiring methods with relational rewiring, and without relations it outperforms DIGL and SDRF on most datasets.The reported +FA results are sometimes competitive but depend strongly on architecture; +FA performs poorly for GCNs and R-GCNs.Source: §5 · p. 9, Table 1 · p. 9

6 CONCLUSIONS

The conclusion presents FoSR and relational rewiring as complementary approaches to oversquashing and oversmoothing, with improved performance on graph-classification benchmarks. The appendices explain graph bottlenecks through the Cheeger constant and its relation to spectral gap.

6 CONCLUSIONS

  • The proposed methods improve GNN performance on several graph-classification benchmarks, while future work could examine training dynamics and rewiring strategies that aid training.The conclusion describes FoSR as iterative first-order spectral-gap maximization and relational rewiring as addressing oversmoothing with theoretical guarantees.Source: §6 · pp. 9–10

A.1 QUANTIFYING STRUCTURAL BOTTLENECKS VIA THE CHEEGER CONSTANT

  • The Cheeger constant measures the minimum edge boundary between complementary node subsets relative to their volumes, serving as a measure of structural bottlenecks.A large Cheeger constant indicates that every part of the graph is connected to the rest by a large fraction of its edges.Source: §A.1 · p. 13
  • The dumbbell graph formed by two cliques joined by a bridge illustrates a low Cheeger constant, with value 1/(1 + n(n −1)).Source: §A.1 · p. 13

A.2 BOUNDING THE CHEEGER CONSTANT VIA THE SPECTRAL GAP

  • The spectral gap bounds the Cheeger constant away from zero exactly when the Cheeger constant is bounded away from zero, so the paper uses spectral gap as a computable bottleneck measure.The appendix states that a graph is connected exactly when λ2 > 0.Source: §A.2 · pp. 13–14

B SPECTRAL GAP AND OVERSQUASHING

This section links spectral-gap expansion to oversquashing and reports that FoSR expands the gap faster than curvature-based methods on NEIGHBORSMATCH and TUDataset graphs.

B SPECTRAL GAP AND OVERSQUASHING

B.1.1 THE NEIGHBORSMATCH PROBLEM (DETAILS ON FIGURE 1)

The appendix evaluates FoSR on a long-range NEIGHBORSMATCH task and TUDataset graphs, then compares its rewiring runtime with SDRF.

B.1.1 THE NEIGHBORSMATCH PROBLEM (DETAILS ON FIGURE 1)

  • The NEIGHBORSMATCH task requires matching a target node’s label to a node with the same blue-neighbor count, potentially across a long-range interaction.The setup uses a path of three size-10 cliques connected by two edges; the maximum target-to-candidate distance is 5.Source: §B.1.1 · pp. 14–15
  • On NEIGHBORSMATCH, FoSR has the fastest spectral expansion among FoSR, SDRF, and G-RLEF.For all three methods, normalized spectral gap and training accuracy increase monotonically until saturating at around 150 rewiring iterations.Source: §B.1.1 · p. 15

B.1.2 THE TUDATASET

B.2 COMPARISON OF THE COMPUTATION TIME FOR FOSR AND SDRF

B.3 TRADE-OFF BETWEEN OVERSQUASHING AND OVERSMOOTHING AS A FUNCTION OF REWIRING ITERATIONS

Relational GNNs reduce oversmoothing, but rewiring still involves a trade-off: too many added edges can lower performance.

B.3 TRADE-OFF BETWEEN OVERSQUASHING AND OVERSMOOTHING AS A FUNCTION OF REWIRING ITERATIONS

  • Relational rewiring yields higher Dirichlet energies, which the section identifies as evidence of reduced oversmoothing.Energy is averaged over dataset graphs after training across 100 runs.Source: §B.3 · p. 16
  • Even with relational GNNs, adding edges beyond an optimal number causes performance to decline.Source: §B.3 · p. 16
  • R-GCN performance peaks at around 25 rewiring iterations, as reflected in test accuracy and final-layer Dirichlet energy.Source: §B.3 · p. 16

B.4 DISCUSSION ON THE APPROXIMATION ERROR OF FOSR

FoSR’s spectral-gap approximations track actual changes on ENZYMES, and its spectral evolution on a dumbbell graph is nearly identical to exact greedy rewiring. The discussion also examines the iteration trade-off and derives the eigenvalue gradient used in the method’s theory.

B.4 DISCUSSION ON THE APPROXIMATION ERROR OF FOSR

  • On ENZYMES, actual spectral-gap changes are well-correlated with both FoSR approximations, which are also well-correlated with each other.The comparison records actual, first-order, and FoSR-approximated changes after one rewiring iteration.Source: §B.4 · p. 16, Figure 6 · p. 18
  • For TUDataset graphs, relational architectures tend to have higher final-layer Dirichlet energy after training, indicating less oversmoothing.The energy is averaged over graphs after training and summed over 100 runs.Source: Table 3 · p. 17
  • R-GCN performance peaks at around 25 rewiring iterations, reflected in both test accuracy and final-layer Dirichlet energy.This illustrates the trade-off between oversquashing and oversmoothing as rewiring iterations increase.Source: Figure 5 · p. 17
  • FoSR’s spectral evolution on a dumbbell graph is indistinguishable from greedy rewiring using exact eigenvalue computation.The graph consists of two cliques of size 50 connected by a path of length 3.Source: §B.4 · p. 17, Figure 7 · p. 18

C DETAILS ON SECTION 4

  • Theorem 4’s proof derives the eigenvalue gradient by perturbing a diagonalized matrix and applying the chain rule.The proof first establishes that the eigenvalue is continuously differentiable.Source: C DETAILS ON SECTION 4 · p. 19

D DETAILS ON THE EXPERIMENTS FROM SECTION 5

The experimental appendix provides implementation and hyperparameter details, along with scripts for rerunning the experiments.

D DETAILS ON THE EXPERIMENTS FROM SECTION 5

  • The authors make the proposed-method implementation and experiment rerun scripts publicly available.The appendix introduces details on hyperparameters, libraries, and compute infrastructure.Source: D DETAILS ON THE EXPERIMENTS FROM… · p. 20

D.1 HYPERPARAMETERS

  • The appendix includes a table of common hyperparameters and a table of rewiring iteration counts for FoSR and SDRF.Source: Table 4 · p. 20, Table 5 · p. 21
  • A separate table lists DIGL hyperparameters, including teleport probability α.Source: Table 6 · p. 21

D.2 COMPUTER INFRASTRUCTURE AND LIBRARIES

The experiments used Python-based graph-learning tools and were run on a local server with specified CPU and GPU hardware.

D.2 COMPUTER INFRASTRUCTURE AND LIBRARIES

  • Experiments were implemented in Python using PyTorch, NumPy, PyG, and Matplotlib.Source: §D.2 · p. 21
  • PyTorch, PyG, and NumPy are available under the BSD license, while Matplotlib is under the PSF license.Source: §D.2 · p. 21
  • The experiments ran on a local server with two 22-core Intel Xeon Gold 6152 processors and eight NVIDIA GeForce RTX 2080 Ti GPUs.Each GPU had 11 GB of GDDR6 memory.Source: §D.2 · p. 21
Loading 2210.11790v2…