Graph Neural Networks Inspired by Classical Iterative Algorithms
arXiv:2103.06064
Abstract
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.
arXiv commentaccepted as long oral for ICML 2021
References in corpus (21)
- Inductive Representation Learning on Large Graphs
- Molecular Graph Convolutions: Moving Beyond Fingerprints
- Graph Neural Networks: A Review of Methods and Applications
- Simplifying Graph Convolutional Networks
- Representation Learning on Graphs with Jumping Knowledge Networks
- Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
- Towards Deeper Graph Neural Networks
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Simple and Deep Graph Convolutional Networks
- Adversarial Attacks on Graph Neural Networks via Meta Learning
- DeeperGCN: All You Need to Train Deeper GCNs
- Deep Unfolding: Model-Based Inspiration of Novel Deep Architectures
- Geom-GCN: Geometric Graph Convolutional Networks
- Adversarial Examples on Graph Data: Deep Insights into Attack and Defense
- DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses
- Residual Correlation in Graph Neural Network Regression
- Implicit Graph Neural Networks
- Interpreting and Unifying Graph Neural Networks with An Optimization Framework
- Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions
- Revisiting Graph Convolutional Network on Semi-Supervised Node Classification from an Optimization Perspective