PaperlayerView exact revision on arXiv

Source-linked AI summary

Anti-Symmetric DGN: a stable architecture for Deep Graph Networks

Alessio Gravina, Davide Bacciu, Claudio Gallicchio

arXiv:2210.09789v3cs.LG

TL;DR

Deep Graph Networks may require many layers to capture distant node interactions, yet preserving long-range dependencies remains a challenge. A-DGN uses a stable, non-dissipative graph ODE formulation, and the authors report competitive benchmark performance, particularly when long-range dependencies matter, even with dozens of layers.

  • Problem

    Deep Graph Networks may need many layers to capture distant interactions, while lossy dynamics can cause long-range dependencies to be forgotten.

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

  • Method

    A-DGN formulates graph networks as stable, non-dissipative ODEs using anti-symmetric weight matrices, then derives layers through forward Euler discretization.

    Source: §5 · pp. 8–9

  • Results

    A-DGN largely outperforms standard DGNs when long-range dependencies matter and is generally competitive across several graph benchmarks, with dozens of layers and no noticeable performance drop.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The formulation can reinterpret and extend classical DGNs as stable, non-dissipative graph ODEs.

    Source: §5 · p. 9

    The paper leaves the effects on over-smoothing and extensions to alternative discretizations and dynamical graphs for future study.

    Source: §5 · p. 9

Abstract

from arXiv · show

Deep Graph Networks (DGNs) currently dominate the research landscape of learning from graphs, due to their efficiency and ability to implement an adaptive message-passing scheme between the nodes. However, DGNs are typically limited in their ability to propagate and preserve long-term dependencies between nodes, i.e., they suffer from the over-squashing phenomena. This reduces their effectiveness, since predictive problems may require to capture interactions at different, and possibly large, radii in order to be effectively solved. In this work, we present Anti-Symmetric Deep Graph Networks (A-DGNs), a framework for stable and non-dissipative DGN design, conceived through the lens of ordinary differential equations. We give theoretical proof that our method is stable and non-dissipative, leading to two key results: long-range information between nodes is preserved, and no gradient vanishing or explosion occurs in training. We empirically validate the proposed approach on several graph benchmarks, showing that A-DGN yields to improved performance and enables to learn effectively even when dozens of layers are used.

1 INTRODUCTION

Deep Graph Networks learn node representations through message passing, but tasks requiring distant interactions may call for many layers, where over-squashing can impair long-range information. The paper introduces A-DGN, an ODE-based design intended to preserve long-range dependencies and support deep networks.

1 INTRODUCTION

  • DGNs may need many layers to capture task-relevant interactions between distant nodes, but increasing depth can cause over-squashing that prevents learning long-range information.Message passing aggregates neighboring node states into fixed-length encodings.Source: §1 · pp. 1–2
  • A-DGN formulates deep graph networks through ordinary differential equations and uses anti-symmetric weight matrices to obtain stable, non-dissipative graph dynamics.Its layer update follows from forward Euler discretization of the graph ODE.Source: §1 · p. 2
  • The authors theoretically show that the proposed dynamics preserve long-term dependencies and prevent gradient explosion or vanishing during training.These properties follow from the stability and non-dissipation conditions imposed on the graph ODE.Source: §1 · p. 2
  • Across several datasets, A-DGN can outperform classical DGNs even with dozens of layers.The introduction describes extensive experiments but does not give benchmark-specific values here.Source: §1 · p. 2

2 ANTI-SYMMETRIC DEEP GRAPH NETWORK

A-DGN treats node processing as a graph ODE and derives a layerwise network by discretizing it. Anti-symmetric weights and a suitable aggregation function yield stable, non-dissipative dynamics intended to preserve long-range information without vanishing or exploding gradients.

2 ANTI-SYMMETRIC DEEP GRAPH NETWORK

  • The framework treats node states as a continuous graph process, with initial node features as inputs and the ODE solution as node embeddings for downstream tasks.Each forward Euler step corresponds to a DGN layer, with L = T/ϵ steps approximating the states at successive times.Source: §2 · pp. 2–3
  • Stability alone can still yield lossy dynamics that forget long-range dependencies, so A-DGN seeks stable dynamics whose Jacobian eigenvalues remain near the imaginary axis.Under the stated assumption that the Jacobian changes little over time, forward and backward propagation are stable and non-dissipative, avoiding expected gradient vanishing or explosion.Source: §2 · p. 4
  • An anti-symmetric weight matrix makes the graph ODE stable and non-dissipative when the neighborhood aggregation is independent of the current node state.When aggregation includes the current node state, the resulting Jacobian eigenvalues remain bounded in a small neighborhood around the imaginary axis.Source: §2 · p. 4
  • Forward Euler discretization, with an added diffusion term to preserve stability, produces the A-DGN layer update.The node state at layer ℓ represents the discretized state at time t = ϵℓ.Source: §2 · pp. 4–5
  • A-DGN uses shared weights across layers in its stated formulation, while also allowing layer-dependent weights and task-appropriate node-and-edge aggregation functions.Its general aggregation formulation can cast standard DGNs in stable, non-dissipative versions.Source: §2 · p. 5

3 RELATED WORK

The related-work discussion situates A-DGN among message-passing networks and continuous graph models. It presents A-DGN as a framework that adds stability and non-dissipation to graph-network formulations, distinguishing its focus on preserving long-range dependencies.

3 RELATED WORK

  • Many graph networks vary their message and update functions, but the cited methods focus on aggregation schemes rather than stability and non-dissipative behavior.The discussion associates deeper use of these methods with limited layers before over-squashing.Source: §3 · pp. 5–6
  • The stability properties discussed for time-varying weights require the Jacobian eigenvalue condition and sufficiently slow changes over time.This is a condition on the dynamical analysis, not a claim that arbitrary time-varying weights retain the same properties.Source: §3 · p. 5
  • The paper presents A-DGN as a way to reinterpret and extend standard graph networks through stable, non-dissipative graph ODEs that preserve long-range dependencies.The related-work discussion describes earlier message-passing approaches as unconstrained discretized instances of this framework.Source: §3 · pp. 5–6
  • A-DGN extends graph neural ODE work by adding stability and non-dissipation, while contrasting with approaches targeting oversmoothing or using PDEs and second-order ODEs.The paper characterizes its own graph ODE as first-order and non-dissipative.Source: §3 · p. 6

4 EXPERIMENTS

Experiments assess long-range information on graph-property tasks and compare A-DGN with established models on graph benchmarks. A-DGN strongly outperforms baselines on graph-property prediction, while node-classification results and depth trends are more qualified.

4 EXPERIMENTS

  • The evaluation covers shortest paths, node eccentricity, graph diameter, and node classification, comparing A-DGN variants with established DGN and neural ODE baselines.The graph-property tasks use randomly generated graphs with 25 to 35 nodes; node classification uses five datasets and repeated random splits.Source: §4.1 · p. 7, §4.2 · pp. 7–8

4.1 GRAPH PROPERTY PREDICTION

  • With GCN-based aggregation, A-DGN achieves an error score averaging 0.80 points better than the selected baselines.The authors also report that A-DGN outperforms all DGNs in this experiment.Source: §4.1 · p. 7, Table 1 · p. 8
  • A-DGN with simple aggregation performs 200% to 300% better than the best baseline in each graph-property task.The reported evaluation metric is log10(MSE), for which lower is better.Source: §4.1 · p. 7, Table 1 · p. 8

4.2 GRAPH BENCHMARKS

  • On node-classification benchmarks, A-DGN outperforms selected baselines except on PubMed and Amazon Computers, where GCNII is slightly better.GCN-based aggregation scores higher than simple aggregation in this setting.Source: §4.2 · pp. 7–8
  • On Coauthor CS, GraphSAGE, GAT, GCN, and GIN lose 24.5% to 78.2% of accuracy as layers increase, while A-DGN maintains or improves accuracy.The authors report that including more than 5-hop neighborhoods is fundamental to improve state-of-the-art performances.Source: §4.2 · p. 8

5 CONCLUSION

A-DGN uses anti-symmetric weights to formulate a stable, non-dissipative graph ODE whose forward Euler discretization yields its layer. The authors report long-range information preservation, stable gradients, and competitive performance across graph benchmarks, while identifying further directions for study.

5 CONCLUSION

  • A-DGN is built from a graph ODE constrained by anti-symmetric weights; its layer is the forward Euler discretization of the corresponding Cauchy problem.The framework is proposed as a way to reinterpret and extend classical DGNs as stable, non-dissipative ODEs.Source: §5 · pp. 8–9
  • The authors theoretically prove that the differential equation is stable and non-dissipative, so gradient explosion and vanishing do not occur during training.The conclusion associates these properties with preserving long-range dependencies between nodes.Source: §5 · pp. 8–9
  • A-DGN is reported to be competitive on several graph benchmarks and to explore dozens of layers without noticeable performance drop.The authors report larger gains over standard DGNs when capturing long-range dependencies matters.Source: §5 · p. 9
  • The authors identify over-smoothing, alternative ODE discretizations, dynamical graph structures, and Reservoir Computing as future research directions.They describe the approach as a possible starting point for mitigating over-smoothing, not as an established result.Source: §5 · p. 9

A STABILITY AND DISSIPATIVITY DEFINITIONS

  • A stable solution keeps nearby initial conditions' solutions close, whereas a dissipative system eventually maps initial conditions from a bounded set into a bounded set.These are the paper's definitions of stability and dissipativity.Source: A STABILITY AND DISSIPATIVITY… · p. 13

B PROOF OF PROPOSITION 1

The proof analyzes how the ODE solution responds to changes in its initial condition. Under a nearly time-constant Jacobian, its eigenvalues determine whether perturbations grow, decay, or remain preserved, with the last case also keeping the longest gradient chain stable.

B PROOF OF PROPOSITION 1

  • Assuming the Jacobian changes little over time, the solution's sensitivity to its initial condition can be solved analytically using autonomous differential-equation results.The proof first differentiates the ODE with respect to its initial condition.Source: B PROOF OF PROPOSITION 1 · p. 13
  • Positive real parts of Jacobian eigenvalues imply exponentially growing representation differences, while negative real parts imply exponential sensitivity decay and a dissipative system.The passage notes that these effects become more evident as the largest absolute eigenvalue real part increases.Source: B PROOF OF PROPOSITION 1 · p. 13
  • When all Jacobian eigenvalues have zero real part, input-graph information is propagated with constant sensitivity, and the longest gradient chain remains constant during backpropagation.Under this condition, the system is stable and non-dissipative, with no gradient vanishing or explosion.Source: B PROOF OF PROPOSITION 1 · p. 13

C PROOF OF PROPOSITION 2

For an aggregation function independent of the node's own state, the proof factors the Jacobian into a diagonal and an anti-symmetric matrix. An eigenpair argument then shows that the Jacobian's eigenvalues are purely imaginary.

C PROOF OF PROPOSITION 2

  • When aggregation is independent of the node's own state, the Jacobian can be expressed using an invertible diagonal matrix and an anti-symmetric matrix.The passage frames the Jacobian in this factorized form for the proof.Source: C PROOF OF PROPOSITION 2 · p. 13
  • For an eigenpair of the factorized matrix, the proof relates v∗Bv to λ(v∗A−1v); the latter scalar is real while the former is imaginary.Here ∗ denotes conjugate transpose, and B is real and anti-symmetric.Source: C PROOF OF PROPOSITION 2 · p. 14
  • The eigenvalue λ must therefore be purely imaginary, so all eigenvalues of the Jacobian are purely imaginary under the stated aggregation condition.The conclusion follows from the eigenpair argument for the factorized Jacobian.Source: C PROOF OF PROPOSITION 2 · pp. 13–14

D BOUNDED EIGENVALUES OF J(t)

When aggregation depends on the node's own state, its derivative contributes an additional term to the Jacobian. The proof bounds the resulting eigenvalues near the imaginary axis, limiting the system to at most moderate signal amplification or loss.

D BOUNDED EIGENVALUES OF J(t)

  • For aggregation that depends on the node's own state, the Jacobian includes the derivative of the aggregation function with respect to that state.For the cited aggregation example, this derivative is C = V/ d̂_u; under Proposition 2's assumption, C is zero.Source: D BOUNDED EIGENVALUES OF J(t) · p. 14
  • The eigenvalues of the generalized Jacobian lie within radius r = ∥AC∥ ≤ ∥C∥ of the imaginary axis, since the eigenvalues of AB are imaginary.For the cited aggregation function, the passage gives r ≤ ∥V∥/ d̂_u.Source: D BOUNDED EIGENVALUES OF J(t) · p. 14
  • This bound does not guarantee imaginary eigenvalues, but it limits graph-system dynamics to at most moderate signal amplification or loss.The passage presents this as a practical restriction on the eigenvalues' position around the imaginary axis.Source: D BOUNDED EIGENVALUES OF J(t) · p. 14

E DATASETS DESCRIPTION AND STATISTICS

The datasets cover graph-property prediction, citation and co-purchase networks, and co-authorship graphs. Dataset statistics are ordered by graph density, defined as the ratio of edges to possible edges.

E DATASETS DESCRIPTION AND STATISTICS

F EXPLORED HYPER-PARAMETER SPACE

The explored hyper-parameter spaces are presented as grids for model selection in the graph property prediction task and graph benchmark. The parameters ϵ and γ apply only to A-DGN.

F EXPLORED HYPER-PARAMETER SPACE

G COMPLETE RESULTS

The complete graph-property prediction results are reported across A-DGN versions and configurations. The appendix also reports per-epoch timing; all evaluated models use 20 layers and embedding dimension 30.

G COMPLETE RESULTS

  • Every model in the evaluation uses 20 layers and embedding dimension 30.Source: G COMPLETE RESULTS · p. 15
  • Table 6 reports mean test-set log10(MSE) and standard deviations across A-DGN configurations, averaged over four random weight initializations.The table distinguishes weight-sharing (ws) and layer-dependent-weight (ldw) configurations.Source: G COMPLETE RESULTS · p. 15, Table 6 · p. 16
  • Table 7 reports average per-epoch time in seconds and standard deviations across four random weight initializations.Each timing uses 20 layers and embedding dimension 30.Source: G COMPLETE RESULTS · p. 15, Table 7 · p. 16

H.1 GRAPH HETEROPHILIC BENCHMARKS

On heterophilic node-classification benchmarks, A-DGN is comparable to state-of-the-art methods on four of six datasets and maintains or improves performance as depth increases. On Tree-NeighborsMatch, it generally outperforms baselines under normalized accuracy, with a stated exception at radius 5.

H.1 GRAPH HETEROPHILIC BENCHMARKS

  • The benchmark uses six node-classification datasets, weight-sharing A-DGN, and grid-search hyperparameter tuning to optimize accuracy.Source: §H.1 · p. 16, Table 8 · p. 17
  • A-DGN generally maintains or improves performance as layers increase and performs outstandingly with 64 layers on highly heterophilic graphs.Figure 3 plots test accuracy against layer count across Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin, averaged over 10 splits.Source: §H.1 · p. 17, Figure 3 · p. 18
  • A-DGN achieves results comparable to state-of-the-art methods on four of six heterophilic datasets and ranks third overall, or fourth in its GCN variant.It outperforms most DGNs designed to mitigate over-smoothing, although A-DGN is not designed to address over-smoothing.Source: §H.1 · pp. 16–17, Table 9 · p. 17

H.2 TREE-NEIGHBORSMATCH

  • The Tree-NeighborsMatch experiment uses weight sharing and simple aggregation, with the same setting as Alon & Yahav (2021).Source: §H.2 · pp. 17–18, Table 10 · p. 18
  • On Tree-NeighborsMatch, A-DGN generally beats baselines in normalized train accuracy, except at radius 5; its original accuracy is on par with or better than GAT, GCN, and GIN despite fewer trainable parameters.The normalization is accuracy in percentage points divided by the total number of trainable hidden units; A-DGN uses weight sharing while baselines have up to eight trainable layers.Source: §H.2 · p. 18, Table 11 · p. 19
Loading 2210.09789v3…