PaperlayerView exact revision on arXiv

Source-linked AI summary

Elastic Graph Neural Networks

Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, Jiliang Tang

arXiv:2107.06996v1cs.LGcs.AIcs.NE

TL;DR

Existing GNNs largely use ℓ2-based smoothing with a shared global smoothness level, while smoothness can differ across graph regions. Elastic GNNs combine ℓ1 and ℓ2 smoothing through Elastic Message Passing; experiments report better adaptivity and robustness to graph attacks.

  • Problem

    Existing GNNs prominently use ℓ2-based smoothing with a shared global smoothness level, despite smoothness varying across graph regions and the limited investigation of ℓ1 smoothing in GNN design.

    Source: §1 · pp. 1–2

  • Method

    Elastic GNNs integrate an elastic graph signal estimator combining ℓ1 and ℓ2 smoothing with a predict-correct primal-dual message-passing scheme.

    Source: §1 · p. 2, §3.1 · p. 3, §3.2 · p. 4

  • Results

    Experiments report better adaptivity on real-world datasets and significant robustness to graph adversarial attacks, with ℓ1- and ℓ2-based smoothing suggested to be complementary.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The study concludes that integrating ℓ1 and ℓ2 graph smoothing gives Elastic GNNs better smoothness adaptivity.

    Source: §6 · p. 9

    The robustness study focuses on robustness introduced by ℓ1 smoothing rather than comparing defense strategies; existing defenses may be applied to Elastic GNNs.

    Source: §4.3 · p. 7

Abstract

from arXiv · show

While many existing graph neural networks (GNNs) have been proven to perform $\ell_2$-based graph smoothing that enforces smoothness globally, in this work we aim to further enhance the local smoothness adaptivity of GNNs via $\ell_1$-based graph smoothing. As a result, we introduce a family of GNNs (Elastic GNNs) based on $\ell_1$ and $\ell_2$-based graph smoothing. In particular, we propose a novel and general message passing scheme into GNNs. This message passing algorithm is not only friendly to back-propagation training but also achieves the desired smoothing properties with a theoretical convergence guarantee. Experiments on semi-supervised learning tasks demonstrate that the proposed Elastic GNNs obtain better adaptivity on benchmark datasets and are significantly robust to graph adversarial attacks. The implementation of Elastic GNNs is available at \url{https://github.com/lxiaorui/ElasticGNN}.

1. Introduction

Elastic GNNs combine ℓ1- and ℓ2-based graph smoothing to improve local smoothness adaptivity, addressing the uniform smoothness of existing ℓ2-based methods. Experiments report better adaptivity on real-world datasets and robustness to graph adversarial attacks.

1. Introduction

  • Existing ℓ2-based GNN smoothing enforces a shared smoothness level globally, although smoothness can vary across graph regions, motivating greater local adaptivity.Source: §1 · p. 1
  • Introducing ℓ1-based smoothing into GNNs requires an efficient scalable solver, operations compatible with back-propagation, and normalization for diverse node degrees.Source: §1 · p. 2
  • The paper introduces ℓ1-based graph smoothing into GNN design to enhance local smoothness adaptivity.Source: §1 · p. 2
  • Elastic Message Passing (EMP) is a general message-passing scheme integrated into deep neural networks to create the Elastic GNN family.Source: §1 · p. 2
  • Elastic GNNs show better adaptivity on real-world datasets and significant robustness to graph adversarial attacks; variant studies suggest ℓ1 and ℓ2 smoothing are complementary.The authors also describe the resulting models as more versatile.Source: §1 · p. 2

2. Preliminary

The preliminary section defines graph notation and reviews two foundations for the paper: interpreting popular GNNs as graph signal denoisers and graph trend filtering as adaptive, ℓ1-based smoothing.

2. Preliminary

  • A graph is represented by nodes, edges, node features, an adjacency matrix, a Laplacian, and an oriented incident matrix; the unnormalized Laplacian equals ∆⊤∆.Source: §2 · p. 2

2.1. GNNs as Graph Signal Denoising

  • Popular GNN message-passing schemes, including GCN and PPNP/APPNP, use ℓ2-based smoothing and can be interpreted through graph signal denoising.GCN is described through a gradient-descent step, while PPNP and APPNP are linked to an exact solution and a gradient-descent step.Source: §2.1 · p. 2

2.2. Graph Trend Filtering

  • Graph trend filtering uses graph difference operators and ℓ1 penalties to adapt to varying signal smoothness, tending to produce piecewise-polynomial signals.For k = 0, sparsity in edge differences supports piecewise-constant signals; GTF smoothers are not linear transformations of the input.Source: §2.2 · p. 3

3. Elastic Graph Neural Networks

The section develops Elastic GNNs by combining ℓ1- and ℓ2-based graph smoothing in an efficient message-passing scheme. It presents the estimator, its primal-dual solver, and its integration into neural networks.

3.1. Elastic Graph Signal Estimator

  • The estimator combines edgewise ℓ1 differences with quadratic Laplacian smoothing and input fidelity; λ1 and λ2 balance the two smoothers.The paper focuses on the 0-th order graph difference operator under a piecewise-constant graph prior.Source: §3.1 · p. 3
  • For ℓ1 smoothing, each column of the incident matrix is normalized by the square root of node degrees to improve numerical stability and handle diverse degrees.The ℓ2 smoother uses a normalized Laplacian.Source: §3.1 · p. 3
  • The ℓ21 estimator promotes row sparsity in normalized edge differences, encouraging similar sparsity patterns across feature dimensions.This coupling reflects the possibility that node-difference sparsity is shared among dimensions.Source: §3.1 · p. 4

3.2. Elastic Message Passing

  • EMP uses an efficient primal-dual, predict-correct algorithm to solve the coupled nonsmooth estimator, avoiding costly subproblem iterations and supporting back-propagation.Each iteration predicts the primal variable, updates the dual variable, then corrects the primal variable.Source: §3.2 · p. 4
  • The ℓ1 proximal operator treats feature dimensions independently, whereas the ℓ21 operator couples them through row-wise projection.Source: §3.2 · p. 5

3.3. Elastic GNNs

  • Elastic GNNs first predict from node features and then propagate predictions with EMP; λ1, λ2, and K are hyperparameters rather than learnable parameters.The two smoothing coefficients provide smoothness adaptivity according to graph-data smoothness.Source: §3.3 · p. 6

4. Experiment

Experiments evaluate Elastic GNNs on semi-supervised benchmarks, adversarially attacked graphs, and ablations of their adaptive smoothness and message passing. The reported results show gains over representative baselines and evidence of local smoothness adaptivity, sparse node differences, and EMP convergence.

4.1. Experimental Settings

  • Evaluation spans eight real-world graphs with 2-layer, 64-hidden-unit models; reported performance averages 10 runs with tuned hyperparameters.The datasets include citation, co-authorship, co-purchase, and blog graphs.Source: §4.1 · p. 6

4.2. Performance on Benchmark Datasets

  • 3.1%, 2.0%, and 1.8%: Elastic GNN improves over GCN on Cora, CiteSeer, and PubMed, and outperforms the reported baselines across all datasets.It also consistently exceeds APPNP, which the paper identifies as a special case with λ1 = 0.Source: §4.2 · p. 7, Table 1 · p. 8

4.3. Robustness Under Adversarial Attack

  • Under every tested perturbation rate, Elastic variants outperform GCN and GAT; this evaluation isolates smoothing-related robustness, not defense strategies.The attack experiments use four datasets and results are not directly comparable with Table 1 because the settings differ.Source: §4.3 · p. 7, Table 2 · p. 8

4.4. Ablation Study

  • Elastic GNN has a higher ratio of average node differences on wrong versus correct edges than the ℓ2-based APPNP, indicating stronger local smoothness adaptivity.The ratio is computed from last-layer node features and is reported for all evaluated datasets.Source: Table 3 · p. 8, §4.4 · p. 8
  • Elastic GNN has substantially more sparse adjacent node differences than APPNP across datasets, supporting the designed piecewise-constant prior.An edge difference is counted as sparse when its ℓ2 norm is below 0.1.Source: Table 4 · p. 8, §4.4 · p. 8
  • Accuracy improves with propagation steps, small K already performs well, and the objective decreases during forward EMP, supporting its convergence.The paper notes that small K can keep EMP computation cost low.Source: Figure 2 · p. 9, Figure 3 · p. 9, §4.4 · p. 9

5. Related Work

Related work views GNN message passing through spectral and spatial architectures and graph-signal filtering. The paper situates its contribution between established ℓ2 smoothing in GNNs and ℓ1-based graph methods whose use in GNN design had remained unclear.

5. Related Work

  • Prior work describes message passing as low-pass graph filtering (Nt & Maehara, 2019) and unifies many GNNs as graph signal denoising (Ma et al., 2020; Pan et al., 2020; Zhu et al., 2021; Chen et al., 2020).Source: §5 · p. 9
  • These denoising-based message-passing schemes perform ℓ2-based graph smoothing and are typically linear smoothers.Source: §5 · p. 9
  • ℓ1 graph methods appear in trend filtering, semi-supervised learning, clustering, and graph cuts, but whether they could inform GNN design was unclear.The paper presents its investigation as the first of its kind.Source: §5 · p. 9

6. Conclusion

The paper combines ℓ1- and ℓ2-based graph smoothing in Elastic GNNs through Elastic Message Passing, reporting benefits on benchmark datasets and adversarially attacked graphs.

  • Elastic Message Passing derives a general message passing scheme from an elastic graph signal estimator.Source: §6 · p. 9
  • Integrating the scheme with deep neural networks yields the Elastic GNN family.Source: §6 · p. 9
  • Experiments suggest ℓ1- and ℓ2-based smoothing are complementary and that Elastic GNNs have better smoothness adaptivity.The paper reports benefits on benchmark datasets and adversarially attacked graphs.Source: §6 · p. 9

A. Data Statistics

The appendix reports dataset statistics for benchmark datasets and for graphs used in adversarial-attack experiments.

A. Data Statistics

B. Convergence Guarantee

The section establishes convergence of EMP to the optimal solution of either elastic graph signal estimator under specified stepsize conditions. It also gives sufficient parameter settings for convergence.

B. Convergence Guarantee

  • EMP converges to the optimal solution of either elastic graph signal estimator when its stepsizes satisfy the theorem's conditions.The theorem covers Option I and Option II.Source: B. Convergence Guarantee · p. 12
  • The convergence argument applies to the estimator problems because their function components are convex and the graph difference operator is bounded.Source: B. Convergence Guarantee · p. 12
  • The section gives simpler sufficient stepsize bounds for EMP using operator-norm bounds on the graph operators.It states γ < 2/(1 + 2λ2) and β ≤ 2/(3γ) as sufficient settings.Source: B. Convergence Guarantee · pp. 12–13
Loading 2107.06996v1…