PaperlayerView exact revision on arXiv

Source-linked AI summary

On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems

Alessio Gravina, Moshe Eliasof, Claudio Gallicchio, Davide Bacciu, Carola-Bibiane Schönlieb

arXiv:2405.01009v2cs.LG

TL;DR

Oversquashing limits MPNNs’ ability to transmit information between distant nodes, making long-range interactions difficult to model. The paper introduces SWAN, a GNN with space and weight antisymmetry intended to provide global and local non-dissipativity. It reports synthetic score improvements of up to 117% and competitive real-world benchmark results.

  • Problem

    In MPNNs, information transmission declines exponentially as node distance grows, limiting the modeling of long-range interactions.

    Source: §1 · p. 1, §2.1 · p. 2

  • Method

    SWAN uses space and weight antisymmetric parameterization to obtain global and local non-dissipativity in a DE-GNN.

    Source: §1 · pp. 1–2

  • Results

    Experiments report synthetic score improvements of up to 117% and competitive real-world results compared with existing MPNNs, DE-GNNs, and graph transformers.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper presents global and local non-dissipativity as a general design principle for introducing this inductive bias into DE-GNNs.

    Source: §6 · p. 7

    The theoretical analyses assume that the Jacobian J(t) does not change significantly over time.

    Source: §2.3 · p. 2, §3.2 · p. 4

Abstract

from arXiv · show

A common problem in Message-Passing Neural Networks is oversquashing -- the limited ability to facilitate effective information flow between distant nodes. Oversquashing is attributed to the exponential decay in information transmission as node distances increase. This paper introduces a novel perspective to address oversquashing, leveraging dynamical systems properties of global and local non-dissipativity, that enable the maintenance of a constant information flow rate. We present SWAN, a uniquely parameterized GNN model with antisymmetry both in space and weight domains, as a means to obtain non-dissipativity. Our theoretical analysis asserts that by implementing these properties, SWAN offers an enhanced ability to transmit information over extended distances. Empirical evaluations on synthetic and real-world benchmarks that emphasize long-range interactions validate the theoretical understanding of SWAN, and its ability to mitigate oversquashing.

1 Introduction

The introduction frames oversquashing as a long-range information-transfer problem and proposes SWAN, which combines global and local non-dissipativity through space and weight antisymmetry. The paper reports synthetic score improvements of up to 117% and competitive results on real-world benchmarks.

1 Introduction

  • Oversquashing limits MPNNs because information transmission between nodes decreases exponentially with distance, hindering tasks that need long-range interactions.The introduction notes that such interactions are often necessary for real-world tasks.Source: §1 · p. 1
  • SWAN uses space and weight antisymmetry to achieve global and local non-dissipativity, which the paper connects to a constant information-flow rate.The introduction contrasts this with typical diffusion-based methods and presents the design as a theoretically grounded way to mitigate oversquashing.Source: §1 · p. 1
  • Figure 1 contrasts SWAN’s propagation to distant nodes with diffusion, which cannot achieve it, and local non-dissipativity, which has a limited effect.Source: Figure 1 · p. 2
  • SWAN experiments report score improvements of up to 117% on synthetic datasets and competitive results on real-world benchmarks against existing methods.The comparisons include MPNNs, other DE-GNNs, and graph transformers.Source: §1 · p. 2

2 Preliminaries

The preliminaries relate oversquashing to distance-dependent information loss, then introduce differential-equation GNNs and a dynamical-systems view of information preservation. They use sensitivity to initial conditions and Jacobian eigenvalues to distinguish instability, dissipation, and non-dissipation.

2 Preliminaries

  • The preliminaries organize the background around oversquashing, differential-equation GNNs, and mathematical tools for analyzing their properties.The section overview says these tools are used to analyze and understand SWAN.Source: §2 · p. 2

2.1 Oversquashing

  • Oversquashing arises as neighborhood aggregation across multiple hops grows exponentially while node feature channels remain finite, risking information loss and weaker long-range effectiveness.An MPNN needs at least k layers to receive information from k-hop nodes; otherwise it under-reaches.Source: §2.1 · p. 2

2.2 GNNs Inspired by Differential-Equations

  • DE-GNNs view GNNs as discretized ODEs, while ADGN uses antisymmetric learned weights for stable, locally non-dissipative propagation.The ODE uses a spatial aggregation function; common implementations combine graph diffusion with channel mixing.Source: §2.2 · p. 2

2.3 Mathematical Background

  • The analysis studies sensitivity of an ODE solution to its initial condition, assuming the Jacobian changes little over time.The paper states that this assumption is used in its theorems and discusses its justification and numerical verification in an appendix.Source: §2.3 · pp. 2–3
  • The real parts of the Jacobian eigenvalues distinguish instability, dissipativity, and non-dissipativity; zero real parts correspond to stable information preservation.Negative real parts make sensitivity to initial conditions vanish exponentially, preserving only local neighborhood information.Source: §2.3 · p. 3

3 SWAN: Space-Weight Antisymmetric GNN

SWAN combines space- and weight-domain antisymmetry to obtain local and graph-wise non-dissipativity. The analysis links these properties to constant information propagation across depth and a higher sensitivity bound relevant to oversquashing.

3 SWAN: Space-Weight Antisymmetric GNN

  • SWAN adds antisymmetry to the aggregation function in space and weights, with a parameterization that gives its node- and graph-wise Jacobians purely imaginary eigenvalues.The paper presents the general formulation as a design principle for introducing non-dissipativity in DE-GNNs.Source: §3 · p. 3

3.1 Node-wise Analysis of SWAN

  • At the node level, M2’s zero-real-part eigenvalues establish stability and non-dissipative propagation, supporting individual nodes’ long-term memory.M2 is a sum of two antisymmetric matrices.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Graph-wise Analysis of SWAN

  • SWAN is stable and globally and locally non-dissipative, maintaining constant information propagation over time unlike diffusion GNNs’ exponential decay.The paper attributes this to Jacobian eigenvalues with zero real part; the figure contrasts graph-wise and node-wise non-dissipative behavior with dissipation.Source: Figure 2 · p. 4, §3.2 · p. 4

3.3 The Benefit of Spatial Antisymmetry

  • The added antisymmetric spatial term Ψ increases the measured sensitivity upper bound; together with constant information flow, this has potential to theoretically mitigate oversquashing.The bound concerns the sensitivity of one connected node’s embedding after ℓ layers to another node’s input.Source: §3.3 · p. 5

4 Experiments

Experiments evaluate SWAN on information transfer, synthetic graph-property prediction, and real-world long-range benchmarks, then ablate its non-dissipative components. Across these settings, SWAN variants show strong performance, with SWAN-LEARN leading on graph-property tasks.

4 Experiments

  • The experiments compare SWAN with linear-complexity MPNNs, DE-GNNs, and oversquashing-oriented methods, and evaluate predefined-operator SWAN alongside learned-aggregation SWAN-LEARN.The predefined variant uses normalized adjacency operators; SWAN-LEARN learns aggregation terms.Source: §4 · p. 5

4.1 Graph Transfer

  • For transfer across line, ring, and crossed-ring graphs, SWAN and ADGN maintain low errors across distances, and SWAN consistently outperforms ADGN.Baseline methods struggle especially at distances of 10 hops or more.Source: §4.1 · p. 5, Figure 3 · p. 6

4.2 Graph Property Prediction

  • For graph-property prediction, SWAN consistently improves performance over MPNNs and DE-GNNs, while SWAN-LEARN yields the best results, with improvement of up to 117% over the runner-up model.Table 1 reports mean test-set log10(MSE) and standard deviation averaged over four random weight initializations.Source: §4.2 · p. 5, Table 1 · p. 6

4.3 Long-Range Graph Benchmark

  • SWAN outperforms standard MPNNs and DE-GNNs overall on long-range benchmarks, performs better than Transformers, and retains linear complexity O(|V| + |E|).The comparison covers three LRGB tasks; Transformer complexity is O(|V|^2).Source: Table 2 · p. 6, §4.3 · p. 6

4.4 Ablation Study

  • Global and local non-dissipative SWAN-LEARN achieves the highest performance across the synthetic and real-world tasks, while spatial antisymmetry improves performance over the weight-only variant.The weight-only variant is formed by setting β = 0; non-enforced variants also outperform it.Source: §4.4 · pp. 6–7, Table 3 · p. 7

5 Related Work

Related work frames SWAN against differential-equation GNNs and methods aimed at mitigating oversquashing. It distinguishes diffusion-based approaches from non-dissipative dynamics and notes the computational cost often associated with dense communication.

Graph Neural Networks based on Differential Equations

  • Many DE-GNNs use diffusion to control smoothing and address oversmoothing, while other designs mix diffusion with oscillatory processes or use antisymmetric, reaction-diffusion, and advection-reaction-diffusion dynamics.The paper characterizes most prior DE-GNNs as diffusion-based and limited in modeling long-range interactions, in contrast to SWAN’s constant information flow.Source: §5 · p. 7

Oversquashing in MPNNs

  • Oversquashing mitigation includes graph rewiring, all-to-all Transformer message passing, and non-local dynamics, but these approaches often increase computational complexity through dense propagation operators.The discussion also connects non-dissipative GNN dynamics to prior work on local non-dissipativity for long interactions.Source: §5 · p. 7

6 Summary

The paper concludes that SWAN uses space and weight antisymmetry to provide global and local non-dissipativity, and presents this as a design principle for DE-GNNs. The appendices describe its discretization, aggregation choices, stability adjustment, and applicability to general MPNNs.

6 Summary

  • SWAN combines graph-wise and node-wise non-dissipativity through space and weight antisymmetric parameterization, offering a design principle for introducing non-dissipativity into DE-GNNs.The paper concludes that its theoretical and experimental results emphasize the significance of both forms of non-dissipativity.Source: §6 · p. 7

A.1 Integration of SWAN

  • Forward Euler discretizes SWAN’s ODE into graph-neural layers, with a shared set of learnable matrices and aggregation matrices across layers.A positive γ is subtracted from the weight-matrix diagonal to stabilize the Euler discretization; as γ approaches zero, a smaller step size ϵ is needed.Source: §A.1 · p. 10, §A.3 · p. 10

A.2 Spatial Aggregation Terms

  • SWAN uses predefined normalized adjacency operators or learns aggregation terms from edge features using an MLP.The predefined option uses symmetric-normalized and random-walk adjacency matrices; the learned option builds edge weights on original graph connectivity.Source: §A.2 · p. 10

A.3 The role of γ and ϵ

  • The positive γ adjustment counteracts forward Euler instability for SWAN’s purely imaginary Jacobian eigenvalues, with smaller γ requiring a smaller step size ϵ.The passage states the stability condition in terms of |1 + ϵλ(J(t))| and the unit circle.Source: §A.3 · p. 10, §A.1 · p. 10

A.4 Applicability of SWAN to general MPNNs

  • SWAN is a special case of an MPNN, and its general formulation provides an antisymmetric parameterization that can incorporate non-dissipativity into other DE-GNNs.The paper describes implementing antisymmetric aggregation with A − A^⊤ and symmetrizing weights with Z + Z^⊤, including compatibility with GCN and GAT.Source: §A.4 · p. 11

B Proof of Theorem 3.2

The proof of Theorem 3.2 analyzes diffusion-based networks through their Jacobian eigenvalues and derives exponential decay in information propagation. The following proof proceeds by induction and states its assumptions and bounds.

B Proof of Theorem 3.2

  • For a diffusion-based network on a connected graph, the graph Laplacian yields non-positive Jacobian eigenvalues, allowing the proof to write J = −K.At least one eigenvalue is strictly negative under the stated connected-graph assumption.Source: B Proof of Theorem 3.2 · p. 11
  • The resulting diffusion-based information propagation rate decays exponentially over time.The proof states that the rate converges to 1 as time tends to infinity, below its early-time rate.Source: B Proof of Theorem 3.2 · p. 11

C Proof of Theorem 3.3

  • The proof of Theorem 3.3 uses induction for layers ℓ > 1, assumes antisymmetric W and symmetric Z parameterizations, and bounds terms using Lipschitz maps and maximal weight magnitude.It omits the straightforward base case and refers to Di Giovanni et al. (2023) for more details.Source: C Proof of Theorem 3.3 · p. 11

D.1 Graph Transfer Dataset

The appendices describe the graph-transfer, graph-property, and long-range benchmark datasets, then outline experimental details and SWAN variants. The datasets cover varied graph structures and long-range tasks, while SWAN variants differ in their non-dissipative properties.

D.1 Graph Transfer Dataset

  • Graph transfer evaluates label swapping at source–target distances of 3, 5, 10, and 50 on line, ring, and crossed-ring graphs.The 1,000/100/100 train/validation/test graphs use random node features; source and target labels are swapped while intermediate nodes remain unchanged.Source: §D.1 · p. 12, Figure 4 · p. 12

D.2 Graph Property Prediction

  • Graph-property prediction uses 7,040 graphs from ten graph distributions, with 25–35 nodes and targets for shortest paths, node eccentricity, and graph diameter.The split is 5,120 training, 640 validation, and 1,280 test graphs.Source: §D.2 · p. 12

D.3 Long Range Graph Benchmark

  • The long-range benchmark comprises Peptides-func, Peptides-struct, and PascalVOC-sp, covering peptide graph prediction and superpixel-node classification.The peptide datasets contain 15,535 graphs each; PascalVOC-sp contains 11,355 graphs.Source: §D.3 · p. 12

E Experimental Details

E.1 SWAN versions

  • SWAN and SWAN-LEARN use symmetric graph shift operators and antisymmetric weights for global and node-wise non-dissipativity; the -NE variants may permit moderate signal amplification or loss.For -NE variants, arbitrary weights place Jacobian eigenvalues within a radius bounded by the weight-matrix norm around the imaginary axis.Source: §E.1 · pp. 12–13

E.2 Graph Transfer Task

The experimental setup uses shared encoder and readout architectures, grid-search tuning, and task-specific training settings. SWAN is linear in nodes and edges per layer; on larger datasets, its runtimes are similar to GCN while its accuracy is higher.

E.2 Graph Transfer Task

  • Models combine an encoder, a graph convolution, and a readout, with the encoder and readout architectures held constant across models.Source: §E.2 · p. 13

E.3 Graph Property Prediction

  • Graph-property experiments use grid search, Adam, up to 1,500 epochs, and early stopping; results average four runs with different initializations.Source: §E.3 · p. 14

E.4 Long-Range Graph Benchmarks

  • Long-range benchmark tuning optimizes AP, MAE, or macro weighted F1 by task, uses AdamW for up to 300 epochs, and stays within a 500K-parameter budget.Results average three runs with different weight initializations.Source: §E.4 · p. 14

E.5 Hyperparameters

  • For graph transfer, the number of layers equals the source–target distance; Table 5 reports the hyperparameter grids for transfer, graph-property, and LRGB tasks.Source: §E.5 · p. 14, Table 5 · p. 14

F Complexity and Runtimes

G Additional Comparisons

Additional comparisons report gains from layer-dependent weights on graph-property tasks and characterize SWAN’s performance across long-range benchmarks. The reported comparisons also note the complexity trade-off against multi-hop methods.

Graph Property Prediction

  • Layer-dependent weights further improve SWAN and SWAN-LEARN, with the reported comparison showing them significantly outperforming all baselines.The table reports mean test-set log10(MSE) and standard deviation across graph-property tasks; lower values are better.Source: G Additional Comparisons · p. 15, Table 8 · p. 16

Long Range Graph Benchmark

  • On Peptide-struct, SWAN outperforms all compared methods; on Peptide-func it trails multi-hop methods such as DRew, while PascalVOC-sp results are competitive with multi-hop and transformer methods.Source: G Additional Comparisons · p. 16
  • The paper concludes that SWAN is effective for long-range interaction tasks while retaining linear complexity, unlike the higher-complexity multi-hop methods discussed.Source: G Additional Comparisons · p. 16

H Derivation of the Graph-wise Jacobian

The derivation identifies components of SWAN’s graph-wise Jacobian, including a Kronecker-product expression for one derivative term. The accompanying stability analysis reports small layer-to-layer Jacobian change for SWAN on Peptides-func compared with GCN.

H Derivation of the Graph-wise Jacobian

I The Stability of the Jacobian

  • On Peptides-func, SWAN’s Jacobian changes by 0.6% on average between layers, compared with 40% for GCN.The analysis assumes the underlying Jacobian does not change significantly over time, an assumption also used in prior approaches.Source: I The Stability of the Jacobian · p. 17

J Limitations and Broader Impact

SWAN is aimed at GNN problems requiring long-range interaction modeling, with possible applications elsewhere in GNNs. The authors note that higher-order GNNs or transformers may sometimes achieve higher downstream performance when computational complexity and theoretical understanding are not priorities.

J Limitations and Broader Impact

  • The paper emphasizes applications requiring long-range propagation or suffering from oversquashing, while noting possible use in other GNN areas.SWAN is specifically focused on problems requiring long interaction modeling.Source: J Limitations and Broader Impact · pp. 17–18
  • Higher-order GNNs or transformers may sometimes achieve higher downstream performance when complexity and theoretical understanding are not priorities.The authors frame SWAN around long-interaction problems and note that these alternatives may be viable for maximizing downstream performance.Source: J Limitations and Broader Impact · p. 18
Loading 2405.01009v2…