PaperlayerView exact revision on arXiv

Source-linked AI summary

Reliable Graph Neural Networks via Robust Aggregation

Simon Geisler, Daniel Zügner, Stephan Günnemann

arXiv:2010.15651v1cs.LGstat.ML

TL;DR

Graph-structure attacks can inject outlier neighbors that arbitrarily distort conventional GNN aggregation, while existing defenses do not reliably address such attacks. The paper introduces fully differentiable Soft Medoid aggregation with a 0.5 breakdown point and reports substantially improved certified and empirical robustness, including strong gains for low-degree nodes.

  • Problem

    Structure attacks remain difficult to defend because injected edges act as additional aggregation inputs and conventional GNN aggregators can be arbitrarily distorted by a single outlier.

  • Method

    The paper replaces standard GNN aggregation with Soft Medoid, a fully differentiable Medoid generalization whose temperature interpolates between Medoid and mean behavior.

  • Results

    Soft Medoid has asymptotic breakdown point 0.5 and outperforms baseline and competing defenses against structural perturbations, with up to 700% relative gains for low-degree edges.

  • Takeaways & Limitations

    Robust aggregation provides bounded aggregation error when adversarial inputs are a minority and improves GNN robustness without attack-specific assumptions.

  • Takeaways & Limitations

    The analytical finite upper bound on maxbias is not derived, and some robust estimators are computationally impractical or insufficiently differentiable for neural message passing.

Abstract

from arXiv · show

Perturbations targeting the graph structure have proven to be extremely effective in reducing the performance of Graph Neural Networks (GNNs), and traditional defenses such as adversarial training do not seem to be able to improve robustness. This work is motivated by the observation that adversarially injected edges effectively can be viewed as additional samples to a node's neighborhood aggregation function, which results in distorted aggregations accumulating over the layers. Conventional GNN aggregation functions, such as a sum or mean, can be distorted arbitrarily by a single outlier. We propose a robust aggregation function motivated by the field of robust statistics. Our approach exhibits the largest possible breakdown point of 0.5, which means that the bias of the aggregation is bounded as long as the fraction of adversarial edges of a node is less than 50\%. Our novel aggregation function, Soft Medoid, is a fully differentiable generalization of the Medoid and therefore lends itself well for end-to-end deep learning. Equipping a GNN with our aggregation improves the robustness with respect to structure perturbations on Cora ML by a factor of 3 (and 5.5 on Citeseer) and by a factor of 8 for low-degree nodes.

1 Introduction

Structure attacks exploit non-robust neighborhood aggregation in GNNs, while attack-specific defenses remain inadequate. The paper proposes Soft Medoid aggregation, which bounds distortion below a 50% adversarial-input fraction and substantially improves robustness.

  • 1 Introduction: Structure-attack defenses remain unresolved, and heuristic or attack-specific defenses can be bypassed or fail to generalize.The proposed model therefore avoids attack-specific assumptions.
  • 1 Introduction: Adversarially inserted edges act as additional neighborhood samples, so non-robust aggregations can distort message passing and accumulate errors across layers.A single outlier can arbitrarily distort standard sum or mean aggregation.
  • 1 Introduction: Soft Medoid is differentiable and has a breakdown point of 0.5, so minority-controlled aggregation inputs cannot be distorted arbitrarily.Its bounded-error guarantee applies regardless of attack characteristics when the adversary controls fewer than half the inputs.
  • 1 Introduction: Soft Medoid aggregation improves robustness to structural perturbations by up to 550% relative and improves low-degree-node robustness by a factor of 8.The method also outperforms previous state-of-the-art defenses.

2 Robust aggregation functions for graph neural networks

The paper motivates replacing conventional GNN aggregation with robust location estimation because neighborhood outliers can arbitrarily shift message-passing embeddings. It introduces differentiable Soft Medoid aggregation as a practical approximation that interpolates between Medoid and mean behavior.

  • 2 Robust aggregation functions for graph neural networks: Standard weighted means, maxima, and sums are vulnerable because a single perturbed neighborhood embedding can arbitrarily deviate the resulting node embedding.The paper hypothesizes that this aggregation non-robustness contributes to GNN non-robustness.
  • 2 Robust aggregation functions for graph neural networks: Only about 25% adversarial outliers can move a conventional neighborhood aggregation outside the clean data convex hull, whereas Soft Medoid is much less affected.This motivates using robust aggregation directly in message passing.
  • 2 Robust aggregation functions for graph neural networks: Existing robust estimators are often too expensive, difficult to vectorize, or not continuously differentiable for repeated neural message passing.The authors specifically found M(R)CD, soft-sorting median, and some high-dimensional estimators impractical or ineffective.
  • 2 Robust aggregation functions for graph neural networks: Soft Medoid replaces Medoid arg min with a softmax-weighted average, assigning larger weights to central points and smaller weights to remote points.The temperature T controls the approximation: T →0 recovers Medoid, while T →∞ recovers the sample mean.
  • 2 Robust aggregation functions for graph neural networks: Soft Medoid outputs lie in the convex hull of the input points and preserve orthogonal equivariance under rotations and translations.These properties support its use as a multivariate aggregation function.

3 Robustness analysis

The robustness analysis shows that Soft Medoid retains Medoid-level asymptotic robustness for every temperature. Below its breakdown point, its bias remains finite, although the exact analytical upper bound is not derived.

  • 3 Robustness analysis: The breakdown analysis formalizes when the estimator can be arbitrarily displaced and contrasts Soft Medoid with the sample mean, whose asymptotic breakdown point is 0.A single perturbed sample can arbitrarily deviate the sample mean.
  • 3 Robustness analysis: Soft Medoid has finite-sample breakdown point 1/n⌊(n+1)/2⌋ and asymptotic breakdown point 0.5 for every temperature T.This matches the best possible breakdown point for the analyzed estimator class.
  • 3 Robustness analysis: For perturbation fractions below the breakdown point, Soft Medoid has a finite maxbias curve and therefore bounded deviation from the clean estimate.The guarantee transfers to robustness of each GNN layer’s embedding space.
  • 3 Robustness analysis: Empirically, high temperatures can reduce bias for distant perturbations but may increase bias for small perturbations at high contamination levels.When perturbations are close to the data, the bias cannot be very high.

4 Instantiating the Soft Medoid for graph neural networks

The paper adapts Soft Medoid to weighted GNN message passing by incorporating adjacency weights into the estimator and normalization. A truncated implementation reduces computational cost for high-degree nodes while retaining comparable training-time practicality.

  • 4 Instantiating the Soft Medoid for graph neural networks: The Weighted Soft Medoid replaces the standard GNN aggregation and uses neighbor embeddings as inputs with adjacency entries as weights.The weights provide input-dependent reweighting of the message-passing matrix.
  • 4 Instantiating the Soft Medoid for graph neural networks: The weighted formulation interpolates between weighted Medoid and weighted mean behavior, while normalization preserves the scale of standard GNN aggregation.The factor c ensures proper normalization.
  • 4 Instantiating the Soft Medoid for graph neural networks: For positive weights, arbitrary perturbation is prevented when total adversarial weight is smaller than total clean weight.This extends the unweighted robustness theorem to message-passing weights.
  • 4 Instantiating the Soft Medoid for graph neural networks: Restricting computation to the k highest-weight neighbors yields O(nk^2) time and space complexity and total worst-case O(n) complexity when k ≪ n.The truncation addresses high-degree nodes and enables a fully vectorized implementation.

5 Experimental evaluation

The evaluation measures empirical and certifiable robustness under structural perturbations across standard datasets, attacks, architectures, and certification radii. Soft Medoid GDC generally outperforms competing defenses, especially for edge additions and low-degree nodes, while robustness gains involve accuracy and attribute-robustness trade-offs.

  • Temperature analysis: The temperature analysis found maximum robustness around T = 0.2, while lower temperatures increased robustness at an accuracy cost and high temperatures approached the sample mean.The evaluation used a Soft Medoid GDC model and examined accumulated certifications alongside base-classifier accuracy.
  • Empirical robustness: Empirical attack accuracy remained high for Soft Medoid under strong adjacency perturbations and exceeded all baselines by a significant margin on Cora ML.The evaluation used Dice, FGSM-like, and PGD L0 attacks; Nettack, Metattack, and Citeseer results are reported separately.
  • Certified robustness: More than 200% relative improvement in accumulated certifications against adversarial edge additions was achieved on Cora ML, while Citeseer performance improved by a factor of 5.5.Soft Medoid GDC also outperformed hard Medoid and dimension-wise Median, with slightly lower accuracy than the best less-robust model.
  • Attack comparison: With equal perturbation budgets, injecting a few outlier edges was more powerful than deleting the same number of good edges.Vanilla GCN already performed decently under edge deletion, making edge addition the more challenging structural attack.
  • Certified robustness: Soft Medoid GDC outperformed all tested defenses across certification radii, with the largest margin for attacks that solely add edges.Certification ratio compares correct predictions robust to specified addition and deletion radii, and higher values are better.

6 Related work

Prior work includes attack-specific defenses, certification methods, and randomized smoothing, while Soft Medoid targets robustness rather than expressive power.

  • Certification methods provide robustness guarantees but typically restrict architectures or perturbations.
  • Soft Medoid’s objective is robust aggregation, contrasting with Xu et al.’s focus on maximizing GNN expressive power.

7 Conclusion

The paper proposes Soft Medoid as a differentiable robust aggregation function and reports substantial gains against structural perturbations, especially for low-degree nodes.

  • Up to 450% relative robustness gains over baselines and other defenses are reported for structural perturbations, reaching 700% for low-degree edges.
  • Soft Medoid is a fully differentiable Medoid generalization with a best-possible breakdown point of 0.5 and bounded internal aggregation bias.

Broader Impact

The broader-impact discussion connects robust GNNs to applications where reduced manipulation could support new AI use cases, while the accompanying material develops robustness analysis and evaluation context.

  • Broader Impact: Robust GNNs could benefit applications including computer vision, knowledge graphs, recommender systems, and physics engines.
  • Proof analysis: The appendix begins by defining decomposable perturbations and formalizing replaced-point assumptions before deriving the estimator bounds.
  • Proof analysis: The analysis permits adversarial replacement, perturbation, or addition of samples and uses orthogonal equivariance to preserve breakdown-point behavior under rotations and translations.
  • Proof analysis: Worst-case influence analysis compares variance and cross-distance terms between perturbed and clean samples, with point-mass perturbations representing the relevant extreme case.
  • Proof analysis: The proofs use standard addition and division limit laws, including element-wise limits for vector-valued functions.

A.2 Proof of Lemma 1

The appendix proves that Soft Medoid remains bounded when fewer than half the samples are perturbed and extends the argument to weighted inputs and experimental certification context.

  • A.2 Proof of Lemma 1: At the asymptotic threshold of 0.5 contamination, the estimator has a finite worst-case bound, establishing the breakdown guarantee.
  • A.2 Proof of Lemma 1: The proof models the worst case with m perturbed points concentrated at a point mass on one axis and analyzes the resulting limits.
  • A.2 Proof of Lemma 1: When perturbed points move toward infinity, their Soft Medoid weights approach zero, preventing the location estimate from diverging while clean points remain finite.
  • Weighted Soft Medoid: The weighted result follows by converting rational weights into duplicated samples and applying the unweighted Soft Medoid argument when clean examples remain more numerous.
  • Weighted Soft Medoid: Normalization does not change the breakdown point because zero weights on infinitely distant perturbed samples remain zero after normalization.
  • Experimental context: The experimental context uses citation graphs with publication nodes, citation edges, bag-of-words features, and semi-supervised publication-category prediction.

B.3 Empirical robustness

The Soft Medoid GDC is evaluated against structure-attack defenses using evasion, targeted, and global attacks. It performs strongly across these empirical settings, including Citeseer results and comparisons summarized in the reported tables.

  • Evaluation setup: The experiments evaluate evasion attacks with a surrogate GCN, training models on the clean graph and applying perturbed adjacency matrices only during prediction.This setup gives every model the same changed edges and avoids measuring architecture-specific gradient obfuscation.
  • Evaluation scope: The empirical comparisons cover Citeseer accuracy, targeted-attack margins and failure rates, and global-attack accuracy on Cora ML and Citeseer.The reported tables define the targeted-attack metrics and the perturbed-accuracy setting for global attacks.
  • Empirical attack evaluation: Soft Medoid GDC performs decently across a wide range of evasion, Nettack, and Metattack attacks, with SVD GCN matching it only on Nettack.The Citeseer evasion results show significant superiority under strong perturbations, while Nettack results identify SVD GCN as the sole comparable defense.

B.4 Certified robustness

Certified-robustness experiments span Cora ML, Citeseer, and PubMed, where Soft Medoid GDC is reported as the most robust model in each structure-robustness benchmark. PubMed comparisons include only selected baselines because of runtime constraints.

  • Certified robustness: Soft Medoid GDC significantly improves structural robustness on Cora ML, Citeseer, and PubMed, with one model the most robust in every structure-robustness benchmark.Table 6 reports three-sigma errors of the mean and compares accumulated certifications and accuracy across architectures.
  • Experimental scope: PubMed results omit most competing defenses because of runtime constraints, retaining selected baselines including RGCN.RGCN is identified as the only other cited defense reporting results on a larger dataset such as PubMed.

B.5 Structural vs. attribute robustness

The paper reports a trade-off between structural and attribute robustness, while a T = 10 Soft Medoid configuration improves attribute certifications. Structural certification is especially strong for low-degree nodes and edge-addition attacks.

  • Robustness trade-off: Increased robustness against structure attacks is accompanied by decreased robustness against attribute attacks across the compared approaches.The paper illustrates this trade-off by noting that GAT outperforms APPNP on attribute attacks but lags behind it on structure attacks.
  • Attribute robustness: About 15% to 30% higher accumulated certifications against attribute attacks are achieved by the Soft Medoid configuration using alternative normalization and T = 10.This configuration has the highest attribute robustness among the tested architectures and is not a GCN special case.
  • Degree-dependent certification: Around 50% of low-degree nodes are certifiable with Soft Medoid GDC, whereas competing approaches certify basically 0% when degree ≤2 before self-loops.This contrast is reported for accumulated certifications over node degrees, especially when edges are added.
  • Structural certification: Soft Medoid GDC outperforms other architectures in certification ratios, with the largest margin in the case of solely adding edges.Figure 8 compares combined deletion/addition noise with deletion-only and addition-only settings on Cora ML.
Loading 2010.15651v1…