# Graph Neural Networks Inspired by Classical Iterative Algorithms

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 69 references that are in the map.
- First posted on arXiv 10 Mar 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (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)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Molecular Graph Convolutions: Moving Beyond Fingerprints](https://mlsanity.com/paper/1603.00856/) (2016)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Attention-based Graph Neural Network for Semi-supervised Learning](https://mlsanity.com/paper/1803.03735/) (2018)
- [Implicit Graph Neural Networks](https://mlsanity.com/paper/2009.06211/) (2020)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures](https://mlsanity.com/paper/1409.2574/) (2014)

## Built on by (most cited first, 30 of 60)

- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion](https://mlsanity.com/paper/2301.09474/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Bag of Tricks for Node Classification with Graph Neural Networks](https://mlsanity.com/paper/2103.13355/) (2021)
- [ContraNorm: A Contrastive Learning Perspective on Oversmoothing and Beyond](https://mlsanity.com/paper/2303.06562/) (2023)
- [Optimization-Induced Graph Implicit Nonlinear Diffusion](https://mlsanity.com/paper/2206.14418/) (2022)
- [PC-Conv: Unifying Homophily and Heterophily with Two-fold Filtering](https://mlsanity.com/paper/2312.14438/) (2023)
- [Transformers from an Optimization Perspective](https://mlsanity.com/paper/2205.13891/) (2022)
- [EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks](https://mlsanity.com/paper/2205.13892/) (2022)
- [Alternating Differentiation for Optimization Layers](https://mlsanity.com/paper/2210.01802/) (2022)
- [From Hypergraph Energy Functions to Hypergraph Neural Networks](https://mlsanity.com/paper/2306.09623/) (2023)
- [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)
- [TouchUp-G: Improving Feature Representation through Graph-Centric Finetuning](https://mlsanity.com/paper/2309.13885/) (2023)
- [Why Propagate Alone? Parallel Use of Labels and Features on Graphs](https://mlsanity.com/paper/2110.07190/) (2021)
- [Does your graph need a confidence boost? Convergent boosted smoothing on graphs with tabular node features](https://mlsanity.com/paper/2110.13413/) (2021)
- [Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2206.11081/) (2022)
- [MGNN: Graph Neural Networks Inspired by Distance Geometry Problem](https://mlsanity.com/paper/2201.12994/) (2022)
- [Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials](https://mlsanity.com/paper/2305.19872/) (2023)
- [Robust Graph Neural Networks via Unbiased Aggregation](https://mlsanity.com/paper/2311.14934/) (2023)
- [Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors](https://mlsanity.com/paper/2406.04090/) (2024)
- [A Piece-wise Polynomial Filtering Approach for Graph Neural Networks](https://mlsanity.com/paper/2112.03499/) (2021)
- [Spatial Heterophily Aware Graph Neural Networks](https://mlsanity.com/paper/2306.12139/) (2023)
- [Training-Free Message Passing for Learning on Hypergraphs](https://mlsanity.com/paper/2402.05569/) (2024)
- [Unveiling the Hidden Structure of Self-Attention via Kernel Principal Component Analysis](https://mlsanity.com/paper/2406.13762/) (2024)
- [From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited](https://mlsanity.com/paper/2309.13599/) (2023)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)

## Abstract (arXiv)

Despite the recent success of graph neural networks (GNN), common architectures often exhibit significant limitations, including sensitivity to oversmoothing, long-range dependencies, and spurious edges, e.g., as can occur as a result of graph heterophily or adversarial attacks. To at least partially address these issues within a simple transparent framework, we consider a new family of GNN layers designed to mimic and integrate the update rules of two classical iterative algorithms, namely, proximal gradient descent and iterative reweighted least squares (IRLS). The former defines an extensible base GNN architecture that is immune to oversmoothing while nonetheless capturing long-range dependencies by allowing arbitrary propagation steps. In contrast, the latter produces a novel attention mechanism that is explicitly anchored to an underlying end-to-end energy function, contributing stability with respect to edge uncertainty. When combined we obtain an extremely simple yet robust model that we evaluate across disparate scenarios including standardized benchmarks, adversarially-perturbated graphs, graphs with heterophily, and graphs involving long-range dependencies. In doing so, we compare against SOTA GNN approaches that have been explicitly designed for the respective task, achieving competitive or superior node classification accuracy. Our code is available at https://github.com/FFTYYY/TWIRLS.