Interpreting and Unifying Graph Neural Networks with An Optimization Framework

Abstract

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.

WWW2021, 12 pages

References in corpus (15)

• Inductive Representation Learning on Large Graphs
• Graph Neural Networks: A Review of Methods and Applications
• Simplifying Graph Convolutional 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
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• Revisiting Graph Neural Networks: All We Have is Low-Pass Filters
• Strategies for Pre-training Graph Neural Networks
• A Fair Comparison of Graph Neural Networks for Graph Classification
• Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data
• An Attention Enhanced Graph Convolutional LSTM Network for Skeleton-Based Action Recognition
• Graph Neural Networks for Social Recommendation
• Graph Neural Networks with Generated Parameters for Relation Extraction
• Learning to Hash with Graph Neural Networks for Recommender Systems

Cited by in corpus (8)

• Is Homophily a Necessity for Graph Neural Networks?
• BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation
• Beyond Graph Convolutional Network: An Interpretable Regularizer-centered Optimization Framework
• Graph Neural Networks Inspired by Classical Iterative Algorithms
• Highly Accurate Disease Diagnosis and Highly Reproducible Biomarker Identification with PathFormer
• Does your graph need a confidence boost? Convergent boosted smoothing on graphs with tabular node features
• Implicit vs Unfolded Graph Neural Networks
• Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clustering