# GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 30 Jan 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Spatially-Aware Graph Neural Networks for Relational Behavior Forecasting from Sensor Data](https://mlsanity.com/paper/1910.08233/) (2019)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Towards Robust Graph Neural Networks for Noisy Graphs with Sparse Labels](https://mlsanity.com/paper/2201.00232/) (2022)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [Large Scale Graph Learning from Smooth Signals](https://mlsanity.com/paper/1710.05654/) (2017)
- [Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields](https://mlsanity.com/paper/1404.6640/) (2014)
- [SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluation](https://mlsanity.com/paper/2102.03716/) (2021)
- [Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation](https://mlsanity.com/paper/1306.3212/) (2013)
- [SGL: Spectral Graph Learning from Measurements](https://mlsanity.com/paper/2104.07867/) (2021)

## Built on by (most cited first, 14 of 14)

- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Adversarial Robustness in Graph Neural Networks: A Hamiltonian Approach](https://mlsanity.com/paper/2310.06396/) (2023)
- [GrOVe: Ownership Verification of Graph Neural Networks using Embeddings](https://mlsanity.com/paper/2304.08566/) (2023)
- [Robust Graph Neural Networks via Unbiased Aggregation](https://mlsanity.com/paper/2311.14934/) (2023)
- [SORSA: Singular Values and Orthonormal Regularized Singular Vectors Adaptation of Large Language Models](https://mlsanity.com/paper/2409.00055/) (2024)
- [SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds](https://mlsanity.com/paper/2402.08653/) (2024)
- [ASGNN: Graph Neural Networks with Adaptive Structure](https://mlsanity.com/paper/2210.01002/) (2022)
- [Resilient Graph Neural Networks: A Coupled Dynamical Systems Approach](https://mlsanity.com/paper/2311.06942/) (2023)
- [Towards Robust Graph Structural Learning Beyond Homophily via Preserving Neighbor Similarity](https://mlsanity.com/paper/2401.09754/) (2024)
- [Adversarial Training for Graph Neural Networks via Graph Subspace Energy Optimization](https://mlsanity.com/paper/2412.18886/) (2024)
- [Robust Learning on Noisy Graphs via Latent Space Constraints with External Knowledge](https://mlsanity.com/paper/2507.05540/) (2025)
- [COPYCOP: Ownership Verification for Graph Neural Networks](https://mlsanity.com/paper/2605.05360/) (2026)
- [Adversarial Graph Neural Network Benchmarks: Towards Practical and Fair Evaluation](https://mlsanity.com/paper/2605.05534/) (2026)
- [FedLSG: LLM-Enhanced Semantic Calibration for Federated Graph Backdoor Defense](https://mlsanity.com/paper/2607.19674/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have been increasingly deployed in various applications that involve learning on non-Euclidean data. However, recent studies show that GNNs are vulnerable to graph adversarial attacks. Although there are several defense methods to improve GNN robustness by eliminating adversarial components, they may also impair the underlying clean graph structure that contributes to GNN training. In addition, few of those defense models can scale to large graphs due to their high computational complexity and memory usage. In this paper, we propose GARNET, a scalable spectral method to boost the adversarial robustness of GNN models. GARNET first leverages weighted spectral embedding to construct a base graph, which is not only resistant to adversarial attacks but also contains critical (clean) graph structure for GNN training. Next, GARNET further refines the base graph by pruning additional uncritical edges based on probabilistic graphical model. GARNET has been evaluated on various datasets, including a large graph with millions of nodes. Our extensive experiment results show that GARNET achieves adversarial accuracy improvement and runtime speedup over state-of-the-art GNN (defense) models by up to 13.27% and 14.7x, respectively.