Source-linked AI summary
Residual Gated Graph ConvNets
Xavier Bresson, Thomas Laurent
TL;DR
The paper studies how recurrent and convolutional neural networks can represent graphs with arbitrary size, addressing learning on graph-structured data beyond regular domains. It proposes graph extensions and compares them experimentally on subgraph matching and graph clustering, finding advantages for deeper graph ConvNets and residuality.
Problem
Graph data are heterogeneous and irregular, so neural-network architectures designed for regular Euclidean grids or one-dimensional sequences do not directly address graph learning tasks.
Method
The paper reviews graph RNNs and ConvNets, proposes graph extensions of Tree-LSTM and ConvNets, and evaluates them on controlled subgraph-matching and graph-clustering experiments.
Results
Graph ConvNets improve with depth while graph RNN performance decreases at larger layer counts; the best learning model reaches 82% accuracy versus 45.37% for the variational method.
Takeaways & Limitations
Gated edges help models learn which graph connections matter, while residuality is essential for stacking deeper graph neural networks and provides a 10% performance gain.
Takeaways & Limitations
Some graph-RNN approaches rely on contractive mappings for convergence, and large iteration counts can be computationally expensive.
Abstract
from arXiv · showhide
Graph-structured data such as social networks, functional brain networks, gene regulatory networks, communications networks have brought the interest in generalizing deep learning techniques to graph domains. In this paper, we are interested to design neural networks for graphs with variable length in order to solve learning problems such as vertex classification, graph classification, graph regression, and graph generative tasks. Most existing works have focused on recurrent neural networks (RNNs) to learn meaningful representations of graphs, and more recently new convolutional neural networks (ConvNets) have been introduced. In this work, we want to compare rigorously these two fundamental families of architectures to solve graph learning tasks. We review existing graph RNN and ConvNet architectures, and propose natural extension of LSTM and ConvNet to graphs with arbitrary size. Then, we design a set of analytically controlled experiments on two basic graph problems, i.e. subgraph matching and graph clustering, to test the different architectures. Numerical results show that the proposed graph ConvNets are 3-17% more accurate and 1.5-4x faster than graph RNNs. Graph ConvNets are also 36% more accurate than variational (non-learning) techniques. Finally, the most effective graph ConvNet architecture uses gated edges and residuality. Residuality plays an essential role to learn multi-layer architectures as they provide a 10% gain of performance.
1 INTRODUCTION
The paper addresses neural-network design for variable-length graphs, where conventional deep-learning architectures built for regular domains do not directly apply. It reviews graph RNNs and ConvNets and proposes a rigorous comparison through controlled graph-learning experiments.
- Motivation: Regular-domain CNNs and RNNs require structured inputs such as Euclidean grids or sequences, whereas many important datasets lie on heterogeneous graphs.Examples include social, brain, gene-regulatory, and telecommunication networks.
- Related approaches: Graph learning methods for variable-length graphs have included recurrent formulations and newer convolutional architectures.Prior work includes graph RNNs, spectral graph ConvNets for fixed-length graphs, and several graph ConvNet variants.
- Paper scope: The paper studies RNNs and ConvNets for graphs of arbitrary length and reviews existing techniques before presenting new models and numerical experiments.The experiments target subgraph matching and graph clustering.
2 NEURAL NETWORKS FOR GRAPHS WITH ARBITRARY LENGTH
Graph RNNs and ConvNets construct vertex representations from graph neighborhoods, but differ in update mechanisms and computational requirements. The reviewed architectures include recurrent, tree-structured, vanilla convolutional, and edge-gated formulations.
- Graph RNNs: Graph RNNs compute each vertex feature from its data vector and an unordered set of neighboring vertex features, making representations permutation-invariant and graph-length independent.Their neighborhood transfer function is local and uses shared weights.
- Graph RNNs: Graph RNNs on arbitrary graphs may require fixed-point iterations because their computational graphs are not directed acyclic graphs.Convergence is guaranteed under a contractive mapping, which can be a strong assumption.
- Graph RNNs: Tree-LSTM recurrence cannot be directly applied to arbitrary graphs, while graph RNN formulations address arbitrary neighborhoods through iterative updates.Trees are a special case of graphs and do not contain the same general cyclic structure.
- Graph ConvNets: Graph ConvNets replace Euclidean neighborhoods with graph neighborhoods and compute a vertex representation from the center feature and an unordered set of neighboring features.This preserves locality and treats the center vertex as the distinguished location.
- Proposed and reviewed models: The paper proposes extending Tree-LSTM to arbitrary graphs and multiple layers, alongside graph ConvNet formulations including vanilla and edge-gated variants.The vanilla graph ConvNet uses a layer-level transfer function with ReLU activation.
- Graph ConvNets: Edge-gated graph ConvNets learn gates that regulate information flow from neighboring vertices, allowing irrelevant neighbors to be ignored for tasks such as community detection.The mechanism is presented as analogous in spirit to gating in Tree-LSTM models.
3 MODELS
The paper proposes Graph LSTM and gated graph ConvNet models for arbitrary-size graphs, then adds residual connections to gated ConvNets for multi-layer learning.
- Proposed Graph LSTM: Graph LSTM extends Tree-LSTM to arbitrary graphs and multiple layers, but requires iterative updates because general graphs lack a recurrent formula.The resulting representation at iteration T is passed to the next layer.
- Proposed Graph LSTM: Unlike earlier Graph LSTM variants, the proposed cell is iterated multiple times T, a difference associated with improved performance in the experiments.The paper contrasts this design with models whose cell is not iterated over multiple times.
- Proposed Gated Graph ConvNets: Gated graph ConvNets combine a vanilla graph ConvNet with edge gates that use neighboring vertices’ feature vectors.This provides the generic graph ConvNet formulation while retaining edge-gating behavior.
- Residual Gated Graph ConvNets: Residual gated graph ConvNets add the identity operator between successive gated convolutional layers.The paper describes this residual strategy as effective for multi-layer graph neural networks.
4 EXPERIMENTS
The experiments compare graph RNN and ConvNet architectures on subgraph matching and semi-supervised clustering, varying noise, depth, parameter budget, and recurrent iterations. ConvNets generally become more competitive or superior with depth, converge faster, and outperform the variational baseline under the reported setting.
- Experimental tasks: The study evaluates graph architectures on subgraph matching and semi-supervised clustering using stochastic block model graphs with variable length.Subgraph matching seeks localized patterns, while clustering identifies 10 communities from one labeled vertex per community.
- Experimental setup: All reported algorithm results average five trials and compare five architectures under controlled parameter and layer settings.The compared models include Gated Graph Neural Networks, CommNets, SyntacticNets, Graph LSTM, and Gated ConvNets; experiments also use multilayer and residual variants.
- Subgraph matching: With increasing depth, ConvNet architectures benefit from larger L, whereas RNN performance decreases at large depths and all ConvNets remain faster than RNNs.The multilayer experiment varies L = {1, 2, 4, 6, 10}; the proposed graph ConvNet performs slightly better than the other ConvNets.
- Subgraph matching: At larger parameter budgets, the proposed graph ConvNet performs best on subgraph matching while remaining faster than RNNs.The budget experiment varies B = {25K, 50K, 75K, 100K, 150K} with L = 6.
- Semi-supervised clustering: On semi-supervised clustering, ConvNets outperform RNNs as depth increases, with the proposed Gated ConvNet outperforming the other architectures and learning-based methods reaching 82% versus 45.37% for the variational model.For fixed L = 6, the graph ConvNets and Marcheggiani & Titov (2017) perform best across budgets; the variational comparison uses one label per class.
5 CONCLUSION
The study compares graph neural network architectures for variable-length graphs using controlled subgraph-matching and graph-clustering experiments. Graph ConvNets scale more reliably with depth, and residuality is essential for deep models, providing a 10% accuracy boost beyond six layers.
- The experiments evaluate graph neural network architectures on subgraph matching and graph clustering with variable-length graphs.
- Graph ConvNets gain accuracy monotonically with depth, whereas graph RNN performance decreases when networks become deep.
- Without residuality, existing graph neural networks cannot stack more than a few layers effectively.
- 10% accuracy boost occurs when more than 6 layers are stacked with residuality.
- Future work targets domain-specific problems in chemistry, physics, and neuroscience.