Source-linked AI summary
Fast and Deep Graph Neural Networks
Claudio Gallicchio, Alessio Micheli
TL;DR
Deep graph neural networks face a computational-cost challenge, while multilayer reservoir approaches for general graphs remain unexplored. FDGNN uses stable fixed-point graph embeddings in a deep architecture with untrained recurrent units, and outperforms the best literature results on most evaluated benchmarks.
Problem
Deep architectures and structured graph data raise computational costs, while multilayer reservoir approaches for general graphs remain unexplored.
Source: §1 · p. 2Method
FDGNN represents graphs with stable fixed-point embeddings in a deep architecture, using sparse, small recurrent units whose weights remain untrained.
Source: §1 · p. 2Results
FDGNN outperforms the best literature results on 7 of 9 graph-classification benchmarks, with the highest graph-neural-network accuracy on NCI1 or near the highest result on COLLAB in the other cases.
Source: §3.1 · pp. 5–6Takeaways & Limitations
The results indicate that stable layered GNN architectures can produce useful graph-classification representations even before recurrent connections are trained.
Source: §3.1 · p. 6The graph embedding requires global asymptotic stability for every input and every pair of initial states.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
We address the efficiency issue for the construction of a deep graph neural network (GNN). The approach exploits the idea of representing each input graph as a fixed point of a dynamical system (implemented through a recurrent neural network), and leverages a deep architectural organization of the recurrent units. Efficiency is gained by many aspects, including the use of small and very sparse networks, where the weights of the recurrent units are left untrained under the stability condition introduced in this work. This can be viewed as a way to study the intrinsic power of the architecture of a deep GNN, and also to provide insights for the set-up of more complex fully-trained models. Through experimental results, we show that even without training of the recurrent connections, the architecture of small deep GNN is surprisingly able to achieve or improve the state-of-the-art performance on a significant set of tasks in the field of graphs classification.
1 Introduction
Deep GNNs can represent increasingly structured data, but their computational cost motivates efficient multilayer graph models. FDGNN uses stable fixed-point graph embeddings with untrained recurrent units, and evaluates the approach against recent graph-classification methods.
1 Introduction
- Graphs let machine-learning systems model both vector patterns and relationships, preserving the structured nature of the data.The introduction names molecular data and social and biological networks as examples.Source: §1 · p. 1
- Earlier graph neural approaches addressed cycles through contractive state dynamics or architectural layers, approaches later reflected in spatial graph convolutions.The introduction contrasts iterative state computation with layer-by-layer propagation of graph context.Source: §1 · p. 1
- Learning on structured data and deep architectures increases computational cost, motivating deep and efficient approaches for graphs.The introduction notes that multilayer reservoir computing for general graphs remains unexplored.Source: §1 · p. 2
- Neural processing of structured data has progressed from sequences and trees to general graphs, alongside a shift from shallow to deep architectures.Earlier recursive neural approaches handled tree-structured data and were extended to directed acyclic graphs (Sperduti and Starita 1997; Frasconi, Gori, and Sperduti 1998; Micheli, Sona, and Sperduti 2004).Source: §1 · pp. 1–2
- FDGNN combines stable dynamical graph embeddings, deep architectural organization, and randomized recurrent units that are not trained.The graph embedding uses the dynamical system's fixed point; the approach also uses sparse connections and relatively few units.Source: §1 · p. 2
- The paper evaluates FDGNN on established graph-classification benchmarks to compare it with recent state-of-the-art approaches.The introduction identifies graph classification as the task and frames the experiments as a comparison with recent methods.Source: §1 · p. 2
2 Proposed Method
FDGNN builds graph representations by stacking recurrent GNN layers that converge to fixed points, while leaving hidden-layer weights untrained after stable initialization. It uses sparse connections and a simple trained readout to combine the final vertex embeddings.
2 Proposed Method
- Hidden-layer weights remain untrained after initialization, and each neuron has only a constant number C of input and recurrent connections.The hidden-layer connectivity pattern need not match the input graph’s topology; the embedding process preserves the input graph topology.Source: §2 · p. 3
- Each layer iterates its state transition to a fixed point, using vertex labels as first-layer input and the preceding layer’s embeddings as input thereafter.Iteration stops when successive states are within threshold ϵ or the maximum number of iterations ν is reached.Source: §2 · p. 3
- The readout combines the final-layer embeddings of all vertices, applies a randomized projection, and trains only the output weights.Output weights are trained in closed form using Tikhonov regularization.Source: §2 · pp. 3–4
2.1 Stability Conditions for Graph Embedding
- Graph Embedding Stability (GES) requires embeddings for the same input to converge to a unique fixed point regardless of initial states.A sufficient condition is ∥W_H∥k < 1; under the stated admissible-input assumption, a necessary condition is ρ(W_H)k < 1.Source: §2.1 · p. 4
- FDGNN initializes recurrent weights under the necessary stability condition, since the sufficient contractive condition may be too restrictive in practice.The effective spectral radius is set below 1; input weights are sampled within layer-specific ranges, with scaling values treated as hyperparameters.Source: §2.1 · p. 4
2.2 Computational Cost
- O(L ν (C + k + N) H) is the full embedding cost, scaling linearly with layers, iterations, connection sparsity, maximum degree, and graph size.Embedding cost is the same during training and testing because internal weights are not trained; the paper compares its efficiency with the Weisfeiler-Lehman graph kernel.Source: §2.2 · p. 4
- The simple readout can be trained efficiently by direct methods, unlike alternatives that may require gradient descent through multiple layers or support vector machines.The passage compares readout training costs, not classification performance.Source: §2.2 · p. 4
3 Experiments
Across nine graph-classification benchmarks, FDGNN outperformed the best literature results on seven, using untrained graph embeddings. The experiments also report advantages from depth and low training times.
3 Experiments
- The nine benchmarks cover cheminformatics and social networks; social-network graphs use a fixed one-dimensional input label of 1 for every vertex.Cheminformatics vertex labels encode atom types, while social-network vertices have no attached labels.Source: §3 · pp. 4–5
- Networks used H=50 except on NCI1 and COLLAB, where H=500; each hidden neuron had one incoming input and one recurrent connection, with 100 configurations and 20 network guesses explored.The experiments used random search for embedding hyperparameters and averaged errors across the network guesses.Source: §3 · p. 5
- Performance was measured by accuracy with stratified 10-fold cross-validation and nested 10-fold model selection within each training fold.The reported outer-fold test accuracies are averaged over the folds.Source: §3 · p. 5, §3.1 · p. 5
3.1 Results
- Table 1 indicates FDGNN outperforms the best literature results on 7 out of 9 benchmarks, achieving state-of-the-art performance and showing, in many cases, clear improvement over neural-network, graph-kernel, and hybrid models.Table 1 also reports single-hidden-layer FDGNN (L = 1) results alongside literature comparisons.Source: §3.1 · pp. 5–6, Table 1 · p. 6
- Stable layered graph embeddings were reported as useful for classification even without training the recurrent connections.The paper presents this as an indication of the intrinsic representational value of layered GNN architectures.Source: §3.1 · p. 6
- Deeper FDGNN settings generally performed better than single-hidden-layer settings, except on PTC and PROTEINS; selected configurations averaged about 3 layers and reached 5.Table 2 reports selected configuration depth averaged over the outer 10 folds.Source: §3.1 · p. 6, Table 2 · p. 7
- FDGNN's low runtimes were attributed to sparse, small hidden layers, untrained internal weights, and a stabilization process described as computationally inexpensive.The experiments used up to 1001 trainable weights; reported runtimes were measured in single-core mode without GPU acceleration.Source: Table 3 · p. 7, §3.1 · p. 7
- On MUTAG, FDGNN trained more than 300 times faster than GNN, almost 900 times faster than GIN, and about 2 times faster than WL.These comparisons use training times; the paper reports FDGNN test accuracy of 0.948 under similar conditions, while GIN's cited 0.835–0.9 range is validation accuracy.Source: Table 4 · p. 7, §3.1 · p. 7
4 Conclusions
FDGNN combines deep graph-neural architectures with randomized recurrent units to construct graph embeddings efficiently. Its stable but untrained embedding layers support progressively more effective graph representations, with accuracy competitive against many state-of-the-art graph CNNs and kernel methods.
4 Conclusions
- FDGNN combines deep GNN architecture for structured graph processing with the efficiency of randomized neural-network methods.The model leaves recurrent graph-embedding layers untrained but stable.Source: §4 · p. 7
- Its deep architecture builds progressively more effective representations of input graphs through untrained, stable embedding layers.The randomized implementation enables the untrained recurrent layers.Source: §4 · p. 7
- FDGNN’s empirical accuracy is competitive with many state-of-the-art graph CNN models and kernel methods.The conclusion describes this performance alongside the model’s simple setup and fast computation.Source: §4 · p. 7
Supplementary Material
The supplementary material includes theorem proofs and additional dataset information. It gives convergence and stability conditions for recurrent layers and points to a table summarizing the experimental datasets.
Supplementary Material
- If ∥WH∥k < 1, the recurrent-state difference converges to zero for the layer dynamics.The proof considers any input and initial states for the layer.Source: Supplementary Material · p. 9
- For a k-regular graph with zero vertex labels, ρ(WH)k < 1 is necessary for generalized exponential stability.The proof derives this condition from the linearized system’s effective spectral radius.Source: Supplementary Material · p. 9
- Table 5 summarizes statistics for the datasets considered in the experiments.The supplementary material identifies additional dataset information as part of its contents.Source: Supplementary Material · p. 9, Table 5 · p. 9