Source-linked AI summary
SIGN: Scalable Inception Graph Neural Networks
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, Federico Monti
TL;DR
Large graph neural networks need scalable training because graph convolutions are expensive on web-scale graphs and existing methods often use sampling. SIGN avoids sampling by precomputing diverse multi-scale diffusion features, achieves competitive benchmark performance with fast training and inference, and reaches state-of-the-art results on ogbn-papers100M.
Problem
Scaling graph neural networks to web-scale graphs is difficult because graph diffusion creates computational and memory costs, leading many methods to rely on sampling.
Method
SIGN combines graph convolutional filters and linear diffusion operators of different types and sizes whose feature products can be precomputed, eliminating graph sampling during training and inference.
Results
SIGN is competitive with state-of-the-art architectures across large-scale benchmarks and achieves state-of-the-art results on ogbn-papers100M and ogbn-products among sampling-free methods.
Takeaways & Limitations
SIGN provides a scalable sampling-free architecture that retains sufficient expressive power for large-scale graph learning and flexibly incorporates diverse graph operators.
Takeaways & Limitations
Feature-dependent operators such as graph attention preclude efficient precomputation, although attention parameters can first be estimated on a small graph subset and then fixed.
Abstract
from arXiv · showhide
Graph representation learning has recently been applied to a broad spectrum of problems ranging from computer graphics and chemistry to high energy physics and social media. The popularity of graph neural networks has sparked interest, both in academia and in industry, in developing methods that scale to very large graphs such as Facebook or Twitter social networks. In most of these approaches, the computational cost is alleviated by a sampling strategy retaining a subset of node neighbors or subgraphs at training time. In this paper we propose a new, efficient and scalable graph deep learning architecture which sidesteps the need for graph sampling by using graph convolutional filters of different size that are amenable to efficient precomputation, allowing extremely fast training and inference. Our architecture allows using different local graph operators (e.g. motif-induced adjacency matrices or Personalized Page Rank diffusion matrix) to best suit the task at hand. We conduct extensive experimental evaluation on various open benchmarks and show that our approach is competitive with other state-of-the-art architectures, while requiring a fraction of the training and inference time. Moreover, we obtain state-of-the-art results on ogbn-papers100M, the largest public graph dataset, with over 110 million nodes and 1.5 billion edges.
1 Introduction
Graph deep learning has become prominent, but scaling graph neural networks to web-scale graphs remains difficult because graph convolutions couple node computations and expand rapidly with receptive field. SIGN addresses this challenge with precomputable multi-scale filters, achieving competitive large-scale performance without sampling.
- Graph neural networks extend convolution-like operations to graph-structured data and support relational-data applications.
- Web-scale graph learning is difficult because edge-based information diffusion makes node losses interdependent and larger receptive fields increase computational and memory costs.
- Graph sampling reduces training costs by retaining selected neighbors or subgraphs, but SIGN instead uses graph convolutional filters of different sizes that can be precomputed.
- SIGN achieves competitive results on several large-scale graph-learning datasets with one graph convolutional layer while providing faster training and inference.The paper reports even one order of magnitude speedup, especially for inference.
- SIGN obtains state-of-the-art results on ogbn-papers100M, a benchmark with over 110 million nodes and 1.5 billion edges.
2 Background and Related Work
Graph neural network methods range from spectral and polynomial filters to GCNs and deeper architectures, while large-graph training commonly relies on node-, layer-, or graph-wise sampling. These approaches trade computational feasibility against receptive field, memory use, and modeling flexibility.
- Basic notions: Graph representation learning constructs embeddings of graph structure and node data for transductive or inductive node-wise prediction.Transductive learning uses one graph for training and testing, whereas inductive learning uses different graphs.
- Convolution-like operators on graphs: Spectral methods generalize CNNs through graph-Laplacian eigenvectors but face high complexity, limited spatial localization, and other scalability constraints.
- Convolution-like operators on graphs: Polynomial spectral filters use O(r) parameters, avoid explicit eigendecomposition, and aggregate neighboring features across an r-hop receptive field with complexity O(|E|r) ≈ O(nr).
- Convolution-like operators on graphs: GCN combines node-wise transformations with graph diffusion, while stacking layers produces larger receptive fields but can make training difficult.
- Graph sampling: Web-scale graphs make storing diffusion matrices impractical, motivating sampling methods that approximate connectivity through partial neighborhoods, layers, or connected subgraphs.
3 Scalable Inception Graph Neural Networks
SIGN uses parallel graph filtering operators with precomputable feature transformations, reducing learning to an MLP-like computation whose forward and backward complexity is independent of graph structure. Its flexible operator choices provide multi-scale and domain-specific representations without node or subgraph sampling.
- Architecture: SIGN applies linear diffusion operators A1, . . . , Ar to node features for node-wise classification, then concatenates the resulting representations before prediction.The model is written as Z = σ([XΘ0, A1XΘ1, . . . , ArXΘr]) and Y = ξ(ZΩ).
- Scalability: A1X, . . . , ArX can be precomputed because they do not depend on learnable parameters, reducing model complexity to O(rLffNd2).Distributed infrastructures such as Apache Spark can accelerate this precomputation for large graphs.
- Scalability: SIGN's forward and backward pass complexity does not depend on graph structure, and the model avoids sampling nodes or subgraphs.The paper reports that this makes SIGN significantly faster than GraphSAGE, ClusterGCN, and GraphSAINT.
- Architecture: An inception-like configuration sets Ak = Bk, creating convolutional filters of different sizes controlled by r, with r = 0 corresponding to node-wise linear transformations.This parallels the Inception module in classic CNNs.
- Operator choice: Operator choice can reflect the task, graph structure, and features, including motif-induced operators, diffusion operators, and directed adjacency powers.The paper gives triangles or cliques, noisy-connectivity diffusion, and normalized directed adjacency matrices as examples.
- Expressivity: Parallel operators produce multi-scale node representations that capture diverse connectivity patterns, while SIGN can incorporate domain-specific operators for greater expressivity.The paper contrasts this with collapsed single-filter configurations such as S-GCN.
4 Experiments
SIGN is evaluated across inductive and transductive node-classification benchmarks, with experiments examining operator choices, accuracy, convergence, and runtime. The results show competitive or superior performance on most benchmarks, state-of-the-art performance on ogbn-papers100M, and substantially faster inference, while operator suitability and dataset distribution affect outcomes.
- Experimental setup: SIGN is evaluated on four inductive datasets, two transductive datasets, and Wikipedia links for scalability timing experiments.The inductive tasks include Reddit, Flickr, Yelp, and PPI; transductive tasks include ogbn-products and ogbn-papers100M.
- Experimental setup: SIGN uses powers of normalized adjacency, PPR diffusion, and triangle-induced adjacency operators, with PPR restart probabilities of α = 0.01 for inductive and α = 0.05 for transductive datasets.The configurations are denoted SIGN(p,s,t), where p, s, and t specify the maximum powers of the three operators.
- Inductive results: SIGN outperforms other methods on Reddit and Flickr, performs competitively on PPI, and performs worse on Yelp, where the authors hypothesize that more tailored operators are needed.SIGN significantly outperforms S-GCN across all inductive datasets, which the authors associate with the expressivity of using different operators.
- Transductive results: SIGN achieves state-of-the-art results on ogbn-papers100M, outperforming other sampling-free methods by at least 1.8% while processing only required labeled nodes after precomputation.Only approximately 1.35% of nodes are labeled, so sampling-based methods may process many nodes that do not contribute to loss or evaluation.
- Transductive results: SIGN outperforms sampling-free methods by at least 2.7% on ogbn-products but is surpassed by sampling methods, which may generalize better under the dataset’s distribution shift.The test nodes are sampled from a different distribution than the training and validation nodes.
- Runtime and ablations: All SIGN architectures are at least one order of magnitude faster in inference than other methods, while preprocessing is slightly longer and can be parallelized.The largest eight-operator model requires no more than 30 seconds to infer over 12M nodes; on ogbn-papers100M, SIGN(3,3,3) takes 1.99 ± 0.05 seconds for validation and 3.34 ± 0.04 seconds for test evaluation.
- Runtime and ablations: The best operator combination varies by benchmark: PPR helps transductive ogbn-products but offers little or negative benefit inductively, while triangle operators show promise on Flickr and PPI.The authors leave operators induced by more complex network motifs for future research.
5 Conclusion and Future Work
SIGN is a sampling-free GNN that scales to gigantic graphs through fast precomputation while retaining competitive expressive power. The conclusion highlights flexible operators, shallow architectures, and extensions to higher-order or temporal structures, while noting a limitation for feature-dependent operators.
- Conclusion: SIGN achieves competitive results across large-scale graph benchmarks, including state-of-the-art performance on ogbn-papers100M with ∼111M nodes and ∼1.6B edges.Its flexible incorporation of diverse, domain-specific operators helps address expressivity limitations of other sampling-free models.
- Conclusion: Fast training and inference combined with simplicity and expressiveness make SIGN suitable for scalable applications on web-scale graphs.
- Depth vs. width for Graph Neural Networks: Competitive and often state-of-the-art results can be obtained with one graph convolutional layer, favoring shallow architectures in the reported experiments.The paper proposes exploring wider collections of expressive local operators rather than simply stacking more layers.
- Extensions: Triangle-based operators show promise, with possible extensions to simplicial complexes, paths, motifs, and temporal motifs.
- Limitations: Feature-dependent diffusion operators such as graph attention preclude efficient precomputation, although fixed attention parameters can be used after a preliminary training stage.
A.1 Inductive datasets
Reddit, Flickr, Yelp, and PPI are inductive classification benchmarks covering multiclass and multilabel prediction tasks.
- Reddit and Flickr are multiclass classification problems.
- Reddit predicts online-post communities from user comments.
- Flickr categorizes online images using their descriptions and common properties.
- Yelp and PPI are multilabel tasks predicting business attributes from reviews and protein functions from human protein interactions.
A.2 Transductive dataset
The transductive benchmarks use large graph structures to infer node labels, with splits based on popularity for ogbn-products and publication time for ogbn-papers100M.
- ogbn-products is an Amazon product co-purchasing network with multiclass product-category prediction.
- ogbn-products assigns the top 10% of products by sales ranking to training, the next 2% to validation, and the remaining 88% to testing.
- ogbn-papers100M is a directed citation network of approximately 111 million academic papers.
- ogbn-papers100M uses the full citation network to infer subject areas for a smaller subset of ArXiv papers.
- Its time-based split uses papers through 2017 for training, 2018 for validation, and papers since 2019 for testing.
A.3 Wikipedia
Wikipedia links is a large directed article-link network converted to an undirected graph for timing experiments, with randomly generated 100-dimensional node features.
- Wikipedia links connects articles in the English version of Wikipedia through a large-scale directed network.
- The network is treated as undirected for timing experiments.
- Node features are randomly generated with dimensionality 100, matching ogbn-products.
B Model Selection and Hyperparameter Tuning
SIGN tuning varies architectural and optimization hyperparameters, selecting configurations differently for inductive and transductive experiments.
- Inductive configurations were selected by the best average validation loss across 5 runs.The searched parameters included weight decay, dropout, batch size, learning rate, and layer widths and counts.
- The transductive configuration was selected by minimum validation loss from a single run.
C Triangle-based Operators
Triangle-based operators strengthen neighborhood aggregation by emphasizing edges participating in shared closed triads. Their usefulness varies by dataset, with larger weight variation associated with greater observed improvement, while PPI retains original self-loops as an unresolved scope point.
- Triangle operator definition: Triangle operators connect nodes sharing a closed triad and weight edges according to their triangle participation.Weights are row-normalized to represent each neighbor’s relative importance.
- Triangle operator behavior: The operator preserves the original neighborhood while emphasizing neighbors more closely related through shared triangles.
- Dataset-dependent behavior: Flickr shows larger intra-neighborhood weight variation and relatively large performance improvement, whereas Reddit shows the smallest variation and relatively small improvement.On Flickr, aggregation concentrates on neighbors in more triangles; on Reddit, it approaches uniform averaging.
- Scope and caveat: For PPI, triangle-operator computation retained the dataset’s original self-loops, while their effect on expressiveness remains for future investigation.