# Spectrally unstable nodes drive reliability failures in graph learning

arXiv: https://arxiv.org/abs/2412.14738 · HTML: https://mlsanity.com/paper/2412.14738/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 19 Dec 2024.

## Builds on (most cited first, 11 of 11)

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluation](https://mlsanity.com/paper/2102.03716/) (2021)
- [Elastic Net Hypergraph Learning for Image Clustering and Semi-supervised Classification](https://mlsanity.com/paper/1603.01096/) (2016)
- [Deep Hypergraph Structure Learning](https://mlsanity.com/paper/2208.12547/) (2022)
- [ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks](https://mlsanity.com/paper/2403.09171/) (2024)

## Abstract (arXiv)

Graph-learning algorithms can fail when graph structure is adversarially perturbed, intrinsically noisy or constructed from imperfect observations. Here we show that some nodes bear much greater responsibility than others for allowing adversarial perturbations and intrinsic noise to harm graph-learning algorithms. Building on graph-spectral distortion analysis, we identify these failure-driving nodes and introduce a reliability-aware intervention that isolates them from the main learning step. The target algorithm is applied to a stable induced subgraph, and predictions for isolated nodes are recovered through topology- or centroid-based propagation. Across graph neural networks under targeted and non-targeted structural attacks, spectral hypergraph clustering and multi-view spectral clustering, this principle improves reliability under both adversarial and intrinsic noise. These results suggest that node-level spectral instability provides a common mechanism for understanding and mitigating reliability failures in graph learning.