# Interpreting and Unifying Graph Neural Networks with An Optimization Framework

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

## Key facts

- Cited by 131 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 50 references that are in the map.
- First posted on arXiv 28 Jan 2021.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [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)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [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)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [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)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)

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

- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited](https://mlsanity.com/paper/2202.03580/) (2022)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (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)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [ContraNorm: A Contrastive Learning Perspective on Oversmoothing and Beyond](https://mlsanity.com/paper/2303.06562/) (2023)
- [FMP: Toward Fair Graph Message Passing against Topology Bias](https://mlsanity.com/paper/2202.04187/) (2022)
- [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)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [A Survey on Spectral Graph Neural Networks](https://mlsanity.com/paper/2302.05631/) (2023)
- [RAW-GNN: RAndom Walk Aggregation based Graph Neural Network](https://mlsanity.com/paper/2206.13953/) (2022)
- [Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs](https://mlsanity.com/paper/2306.07608/) (2023)
- [A New Perspective on the Effects of Spectrum in Graph Neural Networks](https://mlsanity.com/paper/2112.07160/) (2021)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [Graph Condensation: A Survey](https://mlsanity.com/paper/2401.11720/) (2024)
- [Partitioning Message Passing for Graph Fraud Detection](https://mlsanity.com/paper/2412.00020/) (2024)
- [Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks](https://mlsanity.com/paper/2107.10234/) (2021)
- [From Hypergraph Energy Functions to Hypergraph Neural Networks](https://mlsanity.com/paper/2306.09623/) (2023)
- [Graph Data Condensation via Self-expressive Graph Structure Reconstruction](https://mlsanity.com/paper/2403.07294/) (2024)
- [Node-oriented Spectral Filtering for Graph Neural Networks](https://mlsanity.com/paper/2212.03654/) (2022)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have received considerable attention on graph-structured data learning for a wide variety of tasks. The well-designed propagation mechanism which has been demonstrated effective is the most fundamental part of GNNs. Although most of GNNs basically follow a message passing manner, litter effort has been made to discover and analyze their essential relations. In this paper, we establish a surprising connection between different propagation mechanisms with a unified optimization problem, showing that despite the proliferation of various GNNs, in fact, their proposed propagation mechanisms are the optimal solution optimizing a feature fitting function over a wide class of graph kernels with a graph regularization term. Our proposed unified optimization framework, summarizing the commonalities between several of the most representative GNNs, not only provides a macroscopic view on surveying the relations between different GNNs, but also further opens up new opportunities for flexibly designing new GNNs. With the proposed framework, we discover that existing works usually utilize naive graph convolutional kernels for feature fitting function, and we further develop two novel objective functions considering adjustable graph kernels showing low-pass or high-pass filtering capabilities respectively. Moreover, we provide the convergence proofs and expressive power comparisons for the proposed models. Extensive experiments on benchmark datasets clearly show that the proposed GNNs not only outperform the state-of-the-art methods but also have good ability to alleviate over-smoothing, and further verify the feasibility for designing GNNs with our unified optimization framework.