PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness of Graph Neural Networks at Scale

Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, Stephan Günnemann

arXiv:2110.14038v4cs.LGstat.ML

TL;DR

Existing GNN robustness studies largely use small graphs, limiting understanding of adversarial behavior at scale. The paper introduces sparsity-aware attacks, improved global-attack losses, and Soft Median, showing practical robustness evaluation on graphs up to 111 million nodes and substantial defense gains.

  • Problem

    Prior GNN robustness studies rely on relatively small graphs, while attacks and defenses face unsuitable losses, quadratic representations, and limited scalability.

  • Method

    The paper combines surrogate losses for global attacks, sparsity-aware first-order optimization attacks, and a differentiable robust aggregation function called Soft Median.

  • Results

    The methods scale to graphs of up to 111 million nodes; surrogate losses can double attack strength, and in some settings Soft Median reduces attack success from around 90 % to 1 %.

  • Takeaways & Limitations

    The work enables empirical assessment of GNN robustness for massive-scale applications and provides scalable attacks and defenses for that assessment.

  • Takeaways & Limitations

    The attacks require an approximately differentiable victim model, and Soft Median’s best possible breakdown point does not prove adversarial robustness.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are increasingly important given their popularity and the diversity of applications. Yet, existing studies of their vulnerability to adversarial attacks rely on relatively small graphs. We address this gap and study how to attack and defend GNNs at scale. We propose two sparsity-aware first-order optimization attacks that maintain an efficient representation despite optimizing over a number of parameters which is quadratic in the number of nodes. We show that common surrogate losses are not well-suited for global attacks on GNNs. Our alternatives can double the attack strength. Moreover, to improve GNNs' reliability we design a robust aggregation function, Soft Median, resulting in an effective defense at all scales. We evaluate our attacks and defense with standard GNNs on graphs more than 100 times larger compared to previous work. We even scale one order of magnitude further by extending our techniques to a scalable GNN.

1 Introduction

The paper addresses the limited scalability of prior GNN robustness studies by developing attacks and defenses for much larger graphs. It identifies three barriers—weak global-attack losses, quadratic attack representations, and unscalable robust GNNs—and proposes solutions that support graphs up to 111 million nodes.

  • Motivation: Previous robustness studies use tiny graphs despite GNN deployment in Internet-scale applications, making scalable evaluation necessary.PubMed already requires around 20 GB for a dense-adjacency attack.
  • Scope: The paper studies structure-based white-box evasion attacks for node classification, distinguishing local attacks on one node from global attacks using a shared budget.The methods can also be used for poisoning attacks.
  • Challenges: The authors identify three scalability challenges: unsuitable global-attack losses, quadratic attack optimization, and robust GNNs that are typically unscalable.These challenges motivate the paper’s surrogate losses, sparse attacks, and Soft Median defense.
  • Contributions: Novel surrogate losses can improve global attack strength by 100%, while two first-order strategies avoid the dense adjacency matrix’s quadratic memory burden.For attacks on the scalable GNN PPRGo, the authors obtain an algorithm with constant complexity in the number of nodes.
  • Contributions: Soft Median is a computationally efficient, differentiable robust aggregation function that achieves similar robustness to prior work with a significantly lower memory footprint.This lower memory footprint enables defense at scale.

2 Surrogate Losses for Global Attacks

Global GNN attacks must allocate a shared budget across many nodes, but common losses can spend that budget on nodes already misclassified or on confident nodes. The paper derives loss properties that prioritize correctly classified nodes near the decision boundary and proposes tanh margin as a suitable surrogate.

  • Cross Entropy limitation: When ∆/n →0, Cross Entropy can increase without reducing accuracy because it favors low-confidence nodes that are already misclassified.These nodes have negative classification margin ψ < 0.
  • Global attack objective: Global attacks must preserve a shared budget while finding edges that maximally reduce overall accuracy by targeting fragile nodes.This differs from attacking a single image or node with an independent budget.
  • Desired loss properties: A suitable global-attack surrogate should ignore misclassified nodes and favor correctly classified nodes close to the decision boundary.These requirements are formalized as properties (I) and (II).
  • Optimization guarantee: Under simplifying independence assumptions, a surrogate satisfying both properties yields the global optimum for greedy node selection until the budget is exhausted.The result applies to the stated 0/1-loss optimization problem.
  • Existing losses: Cross Entropy violates property (I), while Carlini-Wagner violates property (II) and can spend its entire budget on confident nodes without flipping any.The two losses therefore lack the required combination of stopping after misclassification and focusing near the boundary.
  • Proposed surrogates: The tanh margin enforces confidently misclassified nodes and is reported as effective in contrast to Cross Entropy’s budget allocation.For a greedy gradient-based attack, Masked Cross Entropy gains more than 200% in strength, although applying it to PGD yields hardly any improvement over CE.

3 Scalable Attacks

The paper develops scalable graph-structure attacks that avoid dense adjacency representations while retaining first-order optimization. PR-BCD and GR-BCD reduce attack overhead, and the methods extend to scalable GNNs.

  • Scalability challenge: Previous gradient-based attacks optimize dense adjacency matrices with quadratic space complexity Θ(n^2), limiting robustness studies on larger graphs.The paper frames this as a central scalability bottleneck for graph-structure attacks.
  • PR-BCD: PR-BCD keeps only a promising block of the perturbation search space, reducing attack space complexity to Θ(b) on top of the GNN.The method resamples less promising coordinates while optimizing a randomly sampled block.
  • Scalability challenge: Sparse block optimization can provide linear practical overhead when the budget ∆ is a fraction of the number of edges and b > ∆.The implementation uses sparse operations and scales with the number of represented coordinates.
  • GR-BCD: GR-BCD greedily flips the entries with the largest gradient in each block until the perturbation budget is met.It is more scalable than PR-BCD because it does not require b > ∆.
  • Limitations: The attacks are approximate and provide no guarantee on how closely they solve the discrete optimization problem, yielding only an upper bound on adversarial accuracy.Their gradient-based approximation also requires the victim model to be approximately differentiable.
  • Scalable GNNs: The approach extends to scalable GNNs such as PPRGo, where local attacks use differentiable updates to support much larger graphs.The PPR update is obtained through a closed-form rank-one update using the Sherman–Morrison formula.

4 Scalable Defense

The paper introduces Soft Median, a differentiable robust aggregation function designed to make GNN defenses scalable. It preserves strong theoretical and empirical robustness while reducing the computational and memory burden of prior robust aggregation.

  • Soft Median: Soft Median is a computationally efficient, differentiable robust aggregation function based on differentiable sorting and designed for defense at scale.It is reported to have lower computational complexity and memory footprint than Soft Medoid.
  • Scalability: Combined with PPRGo, Soft Median enables a defense on massive graphs with over 111M nodes.The paper presents this as the first defense scaled to that graph size.
  • Soft Median: Soft Median assigns lower influence to instances far from the dimension-wise median, filtering them through distance-based weights.Its temperature controls the weighting behavior, ranging from a median-like selection toward the sample mean.
  • Theoretical robustness: Soft Median has the best possible finite-sample breakdown point, approaching 0.5 as the sample size grows.The finite-sample value is 1/n⌊(n+1)/2⌋.
  • Empirical robustness: 20% lower error was observed for Soft Median than for the weighted-sum aggregation of a GCN in latent-space perturbation experiments.The comparison concerns the L2 distance after the first message-passing operation.
  • Limitations: The breakdown point does not prove adversarial robustness, so attacks and certification techniques remain necessary for application-specific validation.The defense also has higher cost than naïve summation despite matching its asymptotic complexity.

5 Empirical Evaluation

Experiments evaluate scalable attacks and defenses across graphs ranging from small benchmarks to 111.1 million nodes. The proposed attacks remain effective at scale, while Soft Median defenses substantially improve robustness.

  • Experimental setup: Approximately 2,500 runs evaluate attacks and defenses across six graphs, including Products and Papers 100M.The dataset suite ranges from 2.8 k to 111.1 M nodes.
  • Surrogate losses: MCE with greedy FGSM reduces accuracy twice as much as CE, while tanh margin is preferred for PGD and PR-BCD.For larger budgets, elu margin is also reported as a strong choice.
  • Attacks: PR-BCD attacks are as strong as dense equivalents while using a more scalable representation, and they outperform SGA in the reported comparisons.The comparison includes both Vanilla GCN and Vanilla SGC settings.
  • Global robustness: On Products, perturbing roughly 2% of edges lowers accuracy below 60%, matching the performance of an MLP.This result supports the conclusion that GNNs on large graphs can be highly vulnerable to global attacks.
  • Defenses: For ε = 0.1, Vanilla GCN loses 20 percentage points in accuracy, whereas Soft Median PPRGo loses 5 percentage points.Soft Median defenses are consistently among the strongest models tested across scales.
  • Large-scale defenses: On Papers 100M, Soft Median PPRGo reduces attacker success from around 90% to 30% at Δ_i = 0.25, and from 90% to 1% on Products at Δ_i = 0.5.The defense remains robust on the largest evaluated graphs.

6 Conclusion

The paper develops scalable attacks and a Soft Median defense for studying adversarial robustness in GNNs at massive scale. Its methods reach graphs with up to 111 million nodes, and the defense can reduce attack success substantially in some settings.

  • Conclusion: The study addresses limitations in surrogate losses, quadratic attack parameterization, and the scalability of robust GNNs.These are identified as the three major challenges hindering robustness research at scale.
  • Conclusion: The proposed first-order attacks optimize over a quadratic number of possible edges while retaining a scalable representation.This targets the computational burden of dense adjacency-based optimization.
  • Conclusion: The methods scale to graphs of up to 111 million nodes, and in some settings the defense reduces attack success from around 90% to 1%.The paper frames this scale as enabling robustness assessment for massive GNN applications.
  • Surrogate-loss dynamics: The loss study finds that cross-entropy can increase while accuracy remains constant or recovers during an attack.The mismatch is especially visible for small budgets and can also occur for multi-layer GCNs on undirected graphs.
  • Surrogate-loss dynamics: Zero gradients in CW and MCE after misclassification can cause attacked nodes to become correctly classified again, producing instability.The resulting accuracy oscillations are particularly visible for CW attacks.

B.2 What Nodes Are Being Attacked?

Across datasets and attack configurations, surrogate-loss behavior is consistent: CE tends to target low-margin nodes, while the strongest loss depends on attack type and budget. The analysis is largely model agnostic, and the proposed attacks use sparse first-order optimization with discrete budget-feasible outputs.

  • Node selection: CE mostly attacks nodes with a negative margin across the evaluated dataset and budget variations.The distributions are reported for Cora ML, Citeseer, Pubmed, and arXiv, with directed and undirected settings distinguished.
  • Surrogate losses: For sufficiently small budgets, MCE is strongest for greedy FGSM, while tanh margin outperforms other losses for PGD and PR-BCD.With larger budgets, elu margin can become particularly strong, although such budgets are often unrealistic.
  • Budget effects: For arXiv, elu margin becomes slightly stronger than tanh margin above ǫ > 0.075 because only 29% of nodes are attacked while the budget uses all edges.This yields an effectively four-times larger budget per attacked node than on Cora ML, Citeseer, or Pubmed.
  • Model transfer: The loss analysis and choices are model agnostic across architectures, apart from a few exceptions in transfer attacks on Cora ML and Citeseer.These comparisons are reported in Tables B.2 and B.3.
  • Attack procedure: The attack objective relaxes binary edge flips to weighted perturbations, then samples a binary adjacency perturbation satisfying the edge budget.The perturbation probabilities are projected after gradient updates, and the final solution is obtained through constrained Bernoulli sampling or top-∆ selection.
  • Attack procedure: GR-BCD is more scalable than PR-BCD because it does not require b > ∆, but its learning dynamics are much slower because flipped edges are rarely flipped back.The experiments use equal block sizes for comparability despite this difference.

C.3 Derivation and Complexity of Personalized Page Rank Update

The local PPRGo attack updates only the relevant adjacency row and exploits top-k-sparsified PPR scores. This reduces the update and attack complexity to O(bk) for suitable k ≪ n, while retaining a differentiable procedure for perturbed PPR scores.

  • Local attack construction: The local PPRGo attack restricts perturbations to incoming edges and updates PPR scores after perturbing the graph structure.It uses a differentiable update procedure because PPRGo relies on PPR scores rather than recursive message passing.
  • PPR update: Sherman-Morrison avoids a full rank-one matrix update by altering one normalized adjacency row and obtaining gradients for at most b potentially non-zero perturbations.A dense rank-one update would require O(n^2) space and O(n^3) computation.
  • Sparsification: Top-k-sparsified PPR makes the relevant vector-matrix product operate on reduced shapes determined by b non-zero entries and r non-zero columns.This removes the need to process the dense PPR matrix for the local update.
  • Complexity: For k ≪ n, the expected number of relevant non-zero columns is E[r] = O(bk), and the local attack complexity is O(bk).The stronger relation E[r] = Θ(bk) is also stated, while observed values of r are slightly lower in practice.

D.1 Proof of Theorem 1

The proof establishes that Soft Median resists arbitrarily large point-mass perturbations until at least half of the inputs are perturbed. The argument extends to weighted inputs under the paper’s stated representation assumptions.

  • Theorem: Soft Median has finite-sample breakdown point 1/n⌊(n+1)/2⌋, approaching 0.5 as n tends to infinity.The theorem applies to finite-coordinate inputs and temperatures T ∈ [0, ∞).
  • Proof: When fewer than half the inputs are perturbed, each dimension-wise median remains within the range of the clean points.Therefore the perturbed median stays within the smallest possible hypercube around the original clean data.
  • Proof: An unbounded Soft Median displacement can occur only when the perturbed fraction satisfies m/n ≥ 0.5.This conclusion follows for all temperatures in the theorem’s stated range.
  • Weighted extension: The proof also applies to weighted inputs by converting a weighted problem into an equivalent unweighted representation when the greatest common divisor of the weights can be determined.The discussion notes finite computer precision as a reason for not providing an elaborate proof for arbitrary real-valued weights.

D.3 Empirical Error

The empirical evaluation studies Soft Median under point-mass perturbations and compares its error with prior aggregation results. The perturbation varies along one axis as the outlier fraction increases.

  • Empirical error: Soft Median exhibits lower error under perturbed inputs, reproducing and complementing the prior finding in Figure 2 of [18].The error is measured as ∥t(X) − t(˜X)∥2.
  • Experimental setup: The experiment uses 50 samples from a centered bivariate normal distribution with tSoftMedian(X) = 0.The adversary applies a point-mass perturbation on the first axis while increasing the outlier fraction ǫ.

D.4 Improving Provable Robustness

Soft Median improves provable robustness under randomized smoothing while retaining a lower-memory design, but local attack complexity can still grow with the receptive field and graph connectivity.

  • Improving Provable Robustness: Soft Median can increase provable adversarial robustness under randomized smoothing, despite lacking an adversarial robustness guarantee itself.The accumulated certificates are obtained with the same randomized-smoothing setup used for comparison.
  • Complexity Overview: Theoretical complexity comparisons cover global and local attacks, models, and defenses using n nodes, m edges, and k top-k sparsification.The overview assumes feature and hidden-neuron dimensions are negligible relative to graph size.
  • Local Attack Costs: Local attack space complexity is driven by receptive-field edge deletions and candidate insertions toward nodes of the second most likely class.Finding insertion gradients may require checking O(n) nodes, while recursive message passing can expand the receptive field substantially.
  • Local Attack Costs: For power-law graphs, local gradient computation can require considering O(m) edges in the worst case.High-degree neighbors can make the attacked node’s receptive field span a large fraction of the graph.
  • Evaluation Scope: The appendix extends the evaluation with experiment setup, time and memory costs, and additional global and local attack experiments.The local PR-BCD attack is adaptive, whereas the global attacks transfer from a Vanilla GCN and may face nondifferentiable defenses.

F.1 Setup

The setup evaluates attacks and defenses from small benchmark graphs through 111-million-node Papers100M, using sparse implementations and memory-saving techniques to make large-scale experiments feasible.

  • Datasets: The evaluation uses Cora ML, Citeseer, PubMed, arXiv, Products, and Papers 100M, extending global attacks beyond prior large-scale experiments.The local attack reaches Papers 100M with 111 million nodes, outscaling previous local attacks by a factor of 500.
  • Attacks: Global attacks include PR-BCD, GR-BCD, PGD, greedy FGSM, and DICE, while local PR-BCD is compared with Nettack.DICE is a randomized black-box attack; Nettack greedily exploits a linearized GCN surrogate.
  • Defenses: The defense comparison includes Soft Median architectures, SVD GCN, RGCN, and Jaccard GCN, with GDC/PPR preprocessing used alongside Soft Median.The baselines filter perturbations through low-rank approximation, Gaussian aggregation, or attribute dissimilarity.
  • Memory Management: Checkpointing obtains gradients with sublinear memory cost by exploiting operations that depend mainly on neighborhood size.This addresses the extra memory required for gradients during sparse GNN attacks.
  • Configuration: Experiments generally use three random seeds, early stopping, sparse GDC/PPR preprocessing, and attack-specific block sizes and epoch budgets.The largest dataset, Papers100M, is an exception to the three-seed protocol.
  • Time and Memory: Global PR-BCD requires about 4 GB on arXiv compared with about 1 TB for global PGD, while remaining effective.The appendix reports low memory footprints for both global and local PR-BCD across the evaluated settings.
  • Reporting Caveat: Reported appendix runtime and memory figures include preprocessing and postprocessing, making them slightly more pessimistic than the main-text numbers.The authors identify this as an inconsistency to address in a future version.

F.3 Global Attacks

Global attack experiments compare transfer and adaptive settings across budgets and architectures, showing strong Soft Median defenses but also revealing limitations of transfer-based robustness assessments and PPR scalability.

  • Adaptive Global Attack: Soft Median GDC outperforms the baselines by a large margin over all budgets ǫ > 0.01 under adaptive global attacks.The comparison includes Vanilla GCN and Vanilla GDC as an ablation.
  • Adaptive Global Attack: Adaptive attacks can change the relative strength of greedy methods, so transfer attacks may give a false impression of robustness.For Vanilla GDC and Soft Median GDC, the earlier parity between greedy attacks and PGD or PR-BCD does not hold.
  • Attack Strength: On Cora ML, GR-BCD reaches 60% adversarial accuracy at ǫ = 1, whereas PR-BCD falls below 60% between ǫ = 0.25 and 0.5.The comparison uses an MLP achieving around 60% accuracy as a reference.
  • Scalability Limitation: PPR-based Soft Median defenses are constrained by matrix-inverse computation with runtime O(n3) and space O(n2).The limitation arises because an efficient differentiable PPR implementation is unavailable and sparse-matrix inverses are generally not sparse.
  • Evaluation Metrics: The attack success rate is less sensitive to clean-margin distributions than margin comparisons, but it is less fine-grained.PR-BCD is stronger in most reported cases, while lower values indicate better defense performance.
  • Temperature: Soft Median PPRGo has a temperature trade-off: lowering temperature can improve robustness at slightly lower clean accuracy, but very low temperatures reduce both.Robustness is also weaker at very large temperatures, with maximum robustness at an intermediate range.
  • Local Attack Results: Soft Median PPRGo resists local attacks better than the baselines on Cora ML, Citeseer, Products, and Papers 100M.The extended figure compares local PR-BCD with Nettack and includes the two large directed datasets, Products and Papers 100M.

F.5 Relationship of Graph Size and GNNs Robustness

The experiments report larger relative adversarial-accuracy drops on larger graphs, while noting that dataset characteristics complicate direct size-only comparisons.

  • Interpretation: The authors report that larger graphs appear more fragile, but caution that dataset properties such as test-set size and feature type also differ.The reported relationship persists across architectures beyond GCN, while local attacks make the trend more pronounced.
Loading 2110.14038v4…