# HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 49 references that are in the map.
- First posted on arXiv 26 Mar 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [Graph Neural Networks Inspired by Classical Iterative Algorithms](https://mlsanity.com/paper/2103.06064/) (2021)
- [Revisiting Over-smoothing in Deep GCNs](https://mlsanity.com/paper/2003.13663/) (2020)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://mlsanity.com/paper/2110.14363/) (2021)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Revisiting Graph Convolutional Network on Semi-Supervised Node Classification from an Optimization Perspective](https://mlsanity.com/paper/2009.11469/) (2020)
- [LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation](https://mlsanity.com/paper/2302.01503/) (2023)
- [Implicit vs Unfolded Graph Neural Networks](https://mlsanity.com/paper/2111.06592/) (2021)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://mlsanity.com/paper/2007.10254/) (2020)
- [Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2206.11081/) (2022)
- [An Efficient Parallel Solver for SDD Linear Systems](https://mlsanity.com/paper/1311.3286/) (2013)
- [A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time](https://mlsanity.com/paper/1301.6628/) (2013)

## Abstract (arXiv)

As a variant of Graph Neural Networks (GNNs), Unfolded GNNs offer enhanced interpretability and flexibility over traditional designs. Nevertheless, they still suffer from scalability challenges when it comes to the training cost. Although many methods have been proposed to address the scalability issues, they mostly focus on per-iteration efficiency, without worst-case convergence guarantees. Moreover, those methods typically add components to or modify the original model, thus possibly breaking the interpretability of Unfolded GNNs. In this paper, we propose HERTA: a High-Efficiency and Rigorous Training Algorithm for Unfolded GNNs that accelerates the whole training process, achieving a nearly-linear time worst-case training guarantee. Crucially, HERTA converges to the optimum of the original model, thus preserving the interpretability of Unfolded GNNs. Additionally, as a byproduct of HERTA, we propose a new spectral sparsification method applicable to normalized and regularized graph Laplacians that ensures tighter bounds for our algorithm than existing spectral sparsifiers do. Experiments on real-world datasets verify the superiority of HERTA as well as its adaptability to various loss functions and optimizers.