Implicit Graph Neural Networks

By Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, Laurent El Ghaoui. 2020

181 citations recorded by the source corpus.

Graph Neural Networks (GNNs) are widely used deep learning models that learn meaningful representations from graph-structured data. Due to the finite nature of the underlying recurrent structure, current GNN methods may struggle to capture long-range dependencies in underlying graphs. To overcome this difficulty, we propose a graph learning framework, called Implicit Graph Neural Networks (IGNN), where predictions are based on the solution of a fixed-point equilibrium equation involving implicitly defined "state" vectors. We use the Perron-Frobenius theory to derive sufficient conditions that ensure well-posedness of the framework. Leveraging implicit differentiation, we derive a tractable projected gradient descent method to train the framework. Experiments on a comprehensive range of tasks show that IGNNs consistently capture long-range dependencies and outperform the state-of-the-art GNN models.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Benjamin Paul Chamberlain
2. Cees G. M. Snoek
3. Gertjan J. Burghouts
4. David W. Zhang
5. Emanuele Rossi
6. James Rowbottom
7. Simon Lacoste-Julien
8. Zenan Li

In Computer Vision and Pattern Recognition

1. Junchi Yan
2. Cees G. M. Snoek
3. Dacheng Tao
4. Luc Van Gool
5. Xiaogang Wang
6. Qi Tian
7. Simon Lacoste-Julien
8. Jitendra Malik

In Graph Learning

1. Benjamin Paul Chamberlain
2. Simon Lacoste-Julien
3. Zenan Li
4. Michael M. Bronstein
5. Wentao Zhao
6. Emanuele Rossi
7. David Paul Wipf
8. Junchi Yan

Citations in the corpus

• Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, methodology): “Beyond the sets and multisets considered in this work, implicit differentiation has been applied to other non-Euclidean domains, such as hyperbolic space (Lou et al., 2020) and graphs (Gu et al., 2020).”
• GRAND: Graph Neural Diffusion (2021, methodology): “Continuous GNNs were also explored by Gu et al. (2020) who, similarly to (Scarselli et al., 2009), addressed the solutions of fixed point equations.”
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, background): “OGB-Proteins is a multi-task dataset with 112 output dimensions, while Amazon2M is extracted from the Amazon Co-Purchasing network that entails long-range dependence [13].”
• Long Range Graph Benchmark (2022, unknown): “Finally, a Chains dataset [23] was created for testing long-range dependency that was adopted to develop enhanced models such as higher order Transformers [31], among others [64, 39].”