PaperlayerView exact revision on arXiv

Source-linked AI summary

Continuous Graph Neural Networks

Louis-Pascal A. C. Xhonneux, Meng Qu, Jian Tang

arXiv:1912.00967v3cs.LGstat.ML

TL;DR

Deep GNNs face over-smoothing and limited long-range information propagation. The paper proposes continuous graph neural networks based on diffusion-inspired ODEs, showing stability over time, robustness to over-smoothing, and improved node-classification performance over competitive baselines, while noting homophily and graph-scope limitations.

  • Problem

    Deeper GNNs can suffer over-smoothing, while understanding the signals learned from graph structure remains an important open issue.

  • Method

    CGNN defines node-representation evolution with diffusion-inspired ODEs, including independent feature-channel dynamics and dynamics with channel interactions.

  • Results

    CGNN is robust to integration time, theoretically avoids information loss as time goes to infinity, and outperforms many state-of-the-art methods on node classification.

  • Takeaways & Limitations

    Stability over time allows CGNN to use effectively unlimited depth and learn global dependencies by propagating information from all adjacency-matrix powers.

  • Takeaways & Limitations

    The approach assumes homophily and does not yet learn more complex nonlinear relationships such as those found in molecules or knowledge graphs.

Abstract

from arXiv · show

This paper builds on the connection between graph neural networks and traditional dynamical systems. We propose continuous graph neural networks (CGNN), which generalise existing graph neural networks with discrete dynamics in that they can be viewed as a specific discretisation scheme. The key idea is how to characterise the continuous dynamics of node representations, i.e. the derivatives of node representations, w.r.t. time. Inspired by existing diffusion-based methods on graphs (e.g. PageRank and epidemic models on social networks), we define the derivatives as a combination of the current node representations, the representations of neighbors, and the initial values of the nodes. We propose and analyse two possible dynamics on graphs---including each dimension of node representations (a.k.a. the feature channel) change independently or interact with each other---both with theoretical justification. The proposed continuous graph neural networks are robust to over-smoothing and hence allow us to build deeper networks, which in turn are able to capture the long-range dependencies between nodes. Experimental results on the task of node classification demonstrate the effectiveness of our proposed approach over competitive baselines.

1. Introduction

The introduction motivates continuous graph neural networks as a way to understand and deepen GNNs while avoiding over-smoothing. CGNN uses ODE-based propagation inspired by diffusion methods, with restart information supporting stability and long-range dependencies.

  • Motivation: GNNs update node representations through repeated neighbor aggregation, but deeper networks can suffer inferior performance.Typical tasks often use two or three layers.
  • Motivation: Over-smoothing makes nearby node representations increasingly similar and can cause all node representations to converge, worsening performance.The introduction identifies alleviating this effect as an important goal for deeper GNNs.
  • Proposed perspective: CGNN defines continuous node-representation dynamics with ODEs and analyzes the propagation using continuous dynamical-system tools.The propagation scheme is inspired by diffusion-based methods on graphs.
  • Proposed perspective: The model uses a restart distribution that retains initial-node information, helping avoid over-smoothing and supporting meaningful stationary representations.The restart distribution is motivated by PageRank and prevents forgetting information from low powers of the adjacency matrix.
  • Contributions: The paper proposes two continuous ODEs of increasing capacity, with feature channels evolving independently in one and interacting in the other.These dynamics are presented as principal contributions of the paper.
  • Contributions: As t →∞, the learned representation approaches a stable fixed point that captures graph structure and original node features, enabling arbitrarily deep networks and long-range dependencies.The paper states that stability permits an infinite number of effective layers.
  • Contributions: The model is memory efficient, robust to the choice of t, and outperforms many existing state-of-the-art methods on node classification.The comparison is reported against competitive baselines.

2. Preliminaries

The preliminaries represent graphs with adjacency matrices and node features, then formulate the learning target as node representations governed by continuous ODEs. Degree normalization and regularization provide a stable graph-structure matrix.

  • Graph representation: A graph is defined by vertices and edges, and its adjacency matrix provides an alternative characterization under a chosen node ordering.The adjacency matrix is indexed by pairs of vertices.
  • Graph representation: The normalized adjacency matrix uses the degree matrix to account for potentially different node degrees.The paper introduces degree-based normalization before regularizing the graph matrix.
  • Graph representation: The regularized graph matrix has eigenvalues in [0, α], where α ∈(0, 1), avoiding the negative eigenvalues associated with the normalized adjacency matrix.The regularization follows the approach used by Kipf and Welling.
  • Learning objective: Given graph matrix A and node-feature matrix X, the objective is to learn a node-representation matrix H.The representation dimension is d, and each row corresponds to one node.
  • Scope: The paper restricts its graph setting to simple graphs.This scope condition appears as a footnote in the preliminaries.
  • Continuous dynamics: A continuous ODE specifies the evolution of a state x, with a parametrized function f defining its hidden dynamics.The paper notes that such ODEs can serve as neural-network building blocks through backpropagation.

3. Related Work

Related work treats GNNs as discrete propagation systems and explores deeper architectures, continuous dynamics, and theoretical analyses. CGNN differs by using a diffusion-motivated continuous message-passing layer with theoretical justification and depth-independent representation size.

  • Continuous graph models: Neural ODEs model continuous hidden dynamics for unstructured data, whereas CGNN extends continuous dynamics to graph-structured data.The distinction is that graph inputs contain dependencies among nodes.
  • GNN foundations: Standard GNNs use discrete propagation layers that update node representations from neighboring messages and learn finite polynomial filters of graph structure.This places CGNN in the broader literature on graph-based representation learning.
  • Deep GNNs: Residual connections and layer concatenation have been proposed to address deep-GNN limitations, but concatenation grows the representation size and does not scale to very deep networks.These approaches are alternatives to continuous formulations.
  • CGNN distinction: Unlike related ODE-based approaches, CGNN provides theoretical justification for its ODE and keeps representation size independent of depth.The paper contrasts this with approaches that use discrete deep networks to parameterize the derivative.
  • Theoretical analyses: Prior theory argues that graph topology requires learning graph moments, while deeper GCNs can lose expressivity or information exponentially.Layer concatenation has been proposed to recover multiple graph moments but increases representation size.
  • Concurrent work: Concurrent work uses ODE formulations, but CGNN motivates its ODEs from diffusion methods and theoretically connects them to over-smoothing and long-range dependencies.CGNN uses a continuous message-passing layer rather than directly parameterizing the derivative with a discrete two- or three-layer GNN.

4. Model

CGNN encodes node features, evolves them through graph-aware continuous dynamics, and decodes the resulting representations for node classification. Two ODE designs support independent or interacting feature channels while incorporating initial features and long-range propagation.

  • Architecture: The model encodes node features without graph structure, evolves representations with an ODE, then decodes them with a neural layer and softmax classifier.The ODE operates between the encoder and decoder in the overall architecture.
  • Independent feature channels: Each propagation step aggregates neighbor information through AHn while adding H0, preserving original node features during graph propagation.H0 is the encoder output E(X), so the update combines propagated information with the initial representation.
  • Continuous propagation: CGNN extends discrete propagation to continuous time by treating the discrete process as a Riemann-sum discretisation of an ODE.The continuous variable t replaces the discrete propagation step n.
  • Independent feature channels: The first CGNN ODE uses H(0)=E and combines neighbor influence, natural recovery, and initial features as AH(t), −H(t), and E.The epidemic-model analogy motivates the three terms in the first-order ODE.
  • Long-range propagation: As t approaches infinity, the exponential term vanishes and H(t) becomes a stable fixed point representing all orders of propagated information.This gives the model an effectively infinite number of propagation layers for modelling global or long-range node dependencies.
  • Interacting feature channels: The second ODE adds a feature-channel weight matrix W, allowing different representation dimensions to interact during propagation and increasing model capacity.Its analytical solution is stable because the relevant eigenvalues lie below zero, causing exponential terms to approach zero as t increases.

5. Discussion

CGNN uses continuous diffusion-inspired dynamics to avoid over-smoothing, model global dependencies, and retain initial node information. Its variants also support channel interactions and node-specific diffusion control.

  • Robustness with time to over-smoothing: CGNN is robust to over-smoothing as integration time grows and theoretically does not suffer information loss at infinite time.This contrasts with deeper discrete GCNs, whose representations can lose information exponentially on dense graphs.
  • Global dependencies: CGNN’s stability with time enables learning global dependencies by propagating information from all powers of the adjacency matrix.The method therefore captures long-range relationships between nodes without requiring a finite stack of discrete layers.
  • Diffusion constant: The diffusion parameter α controls the rate at which higher-order adjacency powers vanish, with each node learning its own diffusion rate.Node-specific α values allow diffusion weights to vary independently across nodes.
  • Entangling channels during graph propagation: The weighted ODE variant continuously entangles information across feature channels, and the weight matrix’s eigenvalues affect the learned representation.This extends the independent-channel dynamics with a higher-capacity interaction mechanism.
  • Role of the restart distribution H0: The restart distribution H0 preserves original node features while information propagates, preventing dependence on a precisely chosen ending time.Without H0, the ending time determines which adjacency power is learned and makes performance sensitive to that choice.

6. Experiment

The experiments evaluate CGNN and related variants on semi-supervised node classification benchmarks, comparing them with discrete and continuous GNN baselines. Results show stronger performance than many baselines, robustness at larger times, and constant memory usage for CGNN.

  • Comparison with existing methods: CGNN outperforms standard GCN and GAT in most node-classification cases and also surpasses GODE on Cora and Pubmed.The authors attribute this to ODEs designed from prior knowledge of graph information propagation.
  • Comparison of CGNN and its variants: CGNN achieves better results than CGNN discrete on all datasets, while CGNN and CGNN with weight produce close results.The close weighted- and unweighted-channel results may reflect the relative ease of the evaluated datasets; the authors leave harder-graph verification for future work.
  • Performance with respect to time steps: GCN and GAT perform best at 2 or 3 layers before degrading, whereas CGNN is most effective at t > 10 and remains more stable.These results indicate that CGNN is robust to over-smoothing and can model longer-term node dependencies.
  • Performance with respect to time steps: Removing the initial-value term produces much worse results, while CGNN also outperforms the directly discrete propagation variant.Both comparisons support the importance of the restart term and continuous dynamics for node representation learning.
  • Memory Efficiency: CGNN has constant, relatively small memory cost through the adjoint method, while GCN, GAT, and CGNN discrete scale linearly with discrete layers.This supports modeling long-term node dependencies with lower memory growth than discrete propagation.

7. Conclusion

The paper introduces CGNNs by defining continuous node-representation evolution with ODEs, including independent and interacting feature-channel dynamics. It reports theoretical and empirical effectiveness, while assuming connected nodes are similar and leaving more complex nonlinear relationships for future work.

  • 7. Conclusion: CGNNs generalise discrete graph neural networks by defining the evolution of node representations with ordinary differential equations.
  • 7. Conclusion: The proposed ODEs consider feature channels that either change independently or interact with each other.
  • 7. Conclusion: The paper reports theoretical and empirical evidence for CGNN effectiveness over many existing methods.
  • 7. Conclusion: The approach assumes connected nodes are similar and leaves learning more complex nonlinear relationships for future work.

A. Proof of Proposition 1 and 2

The proof develops the first propositions by interpreting discrete dynamics as a Riemann sum and taking a continuous-time limit. Because the resulting expression is intractable for non-integer time, the derivation proceeds through a second-order ODE and integration.

  • A. Proof of Proposition 1 and 2: The derivation begins by expressing the discrete formulation as a Riemann sum and taking n →∞ to obtain an integral.
  • A. Proof of Proposition 1 and 2: The direct computation of A_t+1 is intractable for non-integer t, so the proof uses a second-order ODE before integrating again.
  • A. Proof of Proposition 1 and 2: The proof determines the integration constant using the initial condition and arrives at the final ODE.
  • A. Proof of Proposition 1 and 2: The second proposition is solved using an Ansatz and the integrating factor exp(−(A −I)t).

B. Proof of Proposition 3 and 4

The proof of Propositions 3 and 4 establishes analytical solutions by using eigenvalue decompositions and evaluating the resulting integrals element-wise. It also invokes a Sylvester ODE formulation to obtain the required result.

  • B. Proof of Proposition 3 and 4: The analytical solution is derived under eigenvalue decompositions of the relevant matrices.
  • B. Proof of Proposition 3 and 4: The transformed matrix is represented using eE = P −1EQ during the derivation.
  • B. Proof of Proposition 3 and 4: The proof identifies the ODE in Eq. (32) as a Sylvester ODE and uses its analytical solution.
  • B. Proof of Proposition 3 and 4: The remaining integrals are evaluated element-wise to establish the stated lemma and proposition results.

B.1. Derivation of the ODE

This derivation rewrites the discrete dynamics in continuous form by interpreting them as a Riemann integral. Differentiation, a second derivative, integration, and the initial condition produce the corresponding ODE and its constant.

  • B.1. Derivation of the ODE: The discrete dynamics are rewritten in continuous form by interpreting the equation as a Riemann integral.
  • B.1. Derivation of the ODE: Differentiating H(t) with respect to t yields the corresponding ODE.
  • B.1. Derivation of the ODE: The derivation considers the second derivative of H(t) to obtain a more convenient ODE form.
  • B.1. Derivation of the ODE: Integrating the second-derivative equation gives an expression for the first derivative containing a constant c.
  • B.1. Derivation of the ODE: The initial value H(0) is used to determine the ODE's initial condition and integration constant.
  • B.1. Derivation of the ODE: The resulting reformulation is presented as the final ODE, with Proposition 4 following from Lemma 1.

C. Hyperparameters & training details

The experiments specify dataset-dependent hyperparameters, training stabilisation choices, and evaluation setups for runtime and depth comparisons. The reported implementation includes an augmentation whose stated effect on final performance was limited.

  • Hyperparameters: Cora, Citeseer, and Pubmed use hidden dimension 16, encoder dropout 0.5, and weight decay 5 × 10−4, while NELL uses hidden dimension 64, dropout 0.1, and weight decay 1 × 10−5.For NELL, dropout is applied in both encoder and decoder.
  • Hyperparameters: The hyperparameter tables use rmsprop for Cora and Citeseer, and adam for Pubmed and NELL.The Cora and Citeseer captions identify rmsprop, while the Pubmed and NELL tables identify adam.
  • Training settings: The CGNN variants are reported with dataset-specific learning rates, integration times, α, γ, and β settings, with weighted CGNN using β = 0.5 where specified.The algorithm table lists separate settings for CGNN discrete, CGNN, and CGNN with weights.
  • Training stabilisation: Training used Dupont et al.’s augmentation to stabilise optimization, but the passage states that it had little or no effect on final performance.The augmentation adds latent dimensions, allowing the ODE trajectory a potentially simpler path.
  • Evaluation setup: Runtime comparisons measure total time over 400 epochs on Cora, using Table 4 hyperparameters and a single CPU-GPU machine.The comparison includes the proposed algorithms and GCN under the specified hardware configuration.
  • Evaluation setup: Depth comparisons evaluate GCN with residual links at 2, 4, 8, and 16 layers on Cora, Citeseer, and PubMed under fixed and random data splits.The results are reported in Table 9.
Loading 1912.00967v3…