Post-Hoc Robustness Enhancement in Graph Neural Networks with Conditional Random Fields

Yassine Abbahaddou, Sofiane Ennadir, Johannes F. Lutzeyer, Fragkiskos D. Malliaros, Michalis VazirgiannisSubmission to ICLR 2025 · Withdrawn

TL;DR

Existing defenses against adversarial attacks on Graph Neural Networks (GNNs) typically require altering model architectures or retraining from scratch, often sacrificing performance on clean data. RobustCRF introduces a post-hoc, model-agnostic defense applied strictly during inference by framing prediction smoothing as inference in a Conditional Random Field (CRF). By balancing fidelity to initial predictions with local consistency across sampled graph neighborhoods, it improves robustness against both structural and feature attacks without needing retraining or architecture modifications.

What Problem Does This Paper Address?

GNNs are vulnerable to adversarial perturbations in both graph topology (e.g., adding or removing edges) and node features. While defenses exist, the vast majority intervene during training:

  • Architecture/Training-time constraints: Methods that modify message passing or require adversarial training cannot be deployed directly on off-the-shelf, pre-trained models and often hurt generalization on unattacked ("clean") graphs.
  • Limitations of existing post-hoc smoothing: Test-time approaches such as randomized smoothing can suffer from "shrinking decision regions" or force the classifier to output constant predictions over wide regions, leading to severe accuracy drops on clean data.

The authors set out to provide an architecture-agnostic, post-hoc defense that runs purely during test time, preserving clean accuracy while defending against both feature and structural adversarial attacks.

Methods

RobustCRF formulates robustness as a smoothness constraint on a graph-level manifold: adjacent graph inputs should yield similar outputs.

  1. Conditional Random Field (CRF) Formulation:
  2. Nodes in the CRF represent input graphs $[G, X]$, and edges connect inputs within a ball $B([G, X], r)$ defined by an optimal transport distance metric $d_{\alpha, \beta}$ covering structure and features.
  3. For a given input $a$, the target prediction $\tilde{Y}_a$ is constrained by two potentials:
  4. Node potential: $\phi_a(\tilde{Y}_a, Y_a) = \sigma \|\tilde{Y}_a - Y_a\|_2^2$, anchoring predictions to the original model output $Y_a$.
  5. Edge potential: $\phi_{ab}(\tilde{Y}_a, \tilde{Y}_b) = (1 - \sigma) g_{ab} \|\tilde{Y}_a - \tilde{Y}_b\|_2^2$, penalizing divergence between neighboring inputs according to their input similarity $g_{ab}$ (e.g., cosine similarity for features, prior distance for structure).
  6. Tuning $\sigma \in [0, 1]$ directly controls the trade-off between clean model confidence and smoothness.
  7. Mean-Field Variational Inference:
  8. Because exact marginalization over the CRF is intractable, the authors derive a Coordinate Ascent Inference (CAI) update rule using a fully factorized mean-field approximation. This yields closed-form, Gaussian-expectation updates at each iteration $k$.
  9. Stratified Sampling for Tractability:
  10. The authors prove that the combinatorial number of structural graph neighbors within Hamming radius $r$ grows exponentially (bounded below by binary entropy).
  11. To make inference practical, they approximate the CRF neighborhood using stratified sampling: first sampling a distance $d \le r$ from a binomial prior, then randomly flipping $d$ adjacency entries (or perturbing continuous features via bounded sampling). In practice, only a few samples ($L \approx 5$) and iterations ($K = 2$) are needed.

Datasets

The authors evaluated RobustCRF on standard benchmark node classification datasets spanning citation networks, co-authorship graphs, blogs, and non-homophilous graphs:

  • Cora, CoraML, CiteSeer, PubMed (citation networks)
  • CS (co-authorship network)
  • PolBlogs (political blog graph; structure-only)
  • Texas (non-homophilous benchmark)
  • ogbn-arxiv (large-scale open graph benchmark)

No new datasets were introduced; standard public splits and benchmark configurations were used.

Key Insights and Ideas

  • Generalizing Randomized Smoothing: When $\sigma = 0$, number of iterations $K = 1$, and all similarities $g_{ab} = 1$, RobustCRF reduces to standard randomized smoothing with a uniform distribution. Retaining non-zero $\sigma$ and edge similarity weighting is what prevents the catastrophic clean-accuracy drops typical of pure randomized smoothing.
  • Average vs. Worst-Case Robustness: Rather than chasing specific worst-case adversarial gradients, the CRF enforces average consistency over a localized neighborhood ball, yielding defenses that generalize well against unknown attack strategies.
  • Composability: Because it operates purely at inference, RobustCRF can be wrapped around already defended training-time models (such as GCORN, RGCN, or NoisyGCN) to provide additive robustness gains.

Key Results

  • Resilience to Feature Attacks (PGD & Random Noise):
  • On the heterophilous Texas dataset under PGD attacks, vanilla GCN achieves 52.97%, whereas applying RobustCRF raises performance to 62.16% while also boosting clean accuracy from 51.35% to 61.08%.
  • On PubMed under PGD, RobustCRF achieves 75.17% accuracy compared to 74.86% for vanilla GCN.
  • Resilience to Structural Attacks (Dice, 10% budget):
  • On PolBlogs, RobustCRF maintains 90.46% accuracy under attack (vs. 87.14% for standard GCN), while achieving top clean accuracy (95.40% vs. 95.16%).
  • On Cora, under the Dice attack, RobustCRF achieves 82.44% accuracy compared to 81.87% for GCN.
  • Boosting Other Baselines: Wrapping RobustCRF around NoisyGCN on Cora under random feature noise improved accuracy from 78.59% to 81.07%.

Limitations and Future Work

  • Inference Latency: Evaluating the CRF requires running the base model multiple times ($O(L^K)$ forward passes across samples $L$ and iterations $K$). Table 7 shows inference runtime on an RTX A6000 jumping from ~1.99s ($L=5, K=1$) to 224.86s ($L=20, K=2$).
  • Scalability to Massive Graphs: On large-scale graphs like ogbn-arxiv, sampling multiple perturbations and running multi-step inference per query becomes computationally demanding, and gains on ogbn-arxiv were relatively modest (50.10% vs. 50.24% under PGD).
  • Heuristic Potentials: The potential functions currently rely on simple $L_2$ distances and cosine/prior weights; the authors note that learning task-adaptive potential functions via regression could be a logical next step.

Summary updated

Abstract

Graph Neural Networks (GNNs), which are nowadays the benchmark approach in graph representation learning, have been shown to be vulnerable to adversarial attacks, raising concerns about their real-world applicability. While existing defense techniques primarily concentrate on the training phase of GNNs, involving adjustments to message passing architectures or pre-processing methods, there is a noticeable gap in methods focusing on increasing robustness during inference. In this context, this study introduces RobustCRF, a post-hoc approach aiming to enhance the robustness of GNNs at the inference stage. Our proposed method, founded on statistical relational learning using a Conditional Random Field, is model-agnostic and does not require prior knowledge about the underlying model architecture. We validate the efficacy of this approach across various models, leveraging benchmark node classification datasets.
BibTeX
@misc{abbahaddou2024post,
  author = {Yassine ABBAHADDOU and Sofiane ENNADIR and Johannes F. Lutzeyer and Fragkiskos D. Malliaros and Michalis Vazirgiannis},
  title = {{Post-Hoc Robustness Enhancement in Graph Neural Networks with Conditional Random Fields}},
  year = {2024},
  eprint = {2411.05399},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.05399},
}

Loading related content...

Figure