PaperlayerView exact revision on arXiv

Source-linked AI summary

Decoupling the Depth and Scope of Graph Neural Networks

Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, Ren Chen

arXiv:2201.07858v1cs.LGcs.AI

TL;DR

GNNs struggle to scale because increasing depth couples computation to expanding neighborhoods and can cause oversmoothing. The paper decouples these dimensions by extracting a localized subgraph before applying an independently deep GNN, achieving accuracy gains with orders-of-magnitude lower computation and hardware cost across broad benchmarks.

  • Problem

    GNN scalability is limited because greater depth expands receptive fields exponentially while oversmoothing degrades expressivity.

  • Method

    The method extracts a target-specific subgraph as the scope and applies a GNN whose depth is independently chosen from that scope.

  • Results

    Across seven benchmarks, graph-learning tasks, and multiple architectures, decoupling significantly improves accuracy while reducing computation and hardware costs by orders of magnitude.

  • Takeaways & Limitations

    Localized scopes can support deeper message passing that improves expressivity and scalability without propagating across the full graph.

  • Takeaways & Limitations

    The practical shallow-neighborhood implementation can lose accuracy when applications depend critically on long-range relationships.

Abstract

from arXiv · show

State-of-the-art Graph Neural Networks (GNNs) have limited scalability with respect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge: 1. degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose a design principle to decouple the depth and scope of GNNs -- to generate representation of a target entity (i.e., a node or an edge), we first extract a localized subgraph as the bounded-size scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of a small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into "white noise". Theoretically, decoupling improves the GNN expressive power from the perspectives of graph signal processing (GCN), function approximation (GraphSAGE) and topological learning (GIN). Empirically, on seven graphs (with up to 110M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.

1 Introduction

GNN depth is coupled to receptive-field scope, creating oversmoothing and neighbor-explosion problems that limit scalability. The paper proposes extracting localized subgraphs and applying independently chosen-depth GNNs to improve accuracy and efficiency.

  • GNNs face an open scalability problem as both graph and model sizes grow.
  • Oversmoothing collapses different nodes’ embeddings into a fixed, low-dimensional subspace.
  • Neighbor explosion makes multi-hop receptive fields grow exponentially, increasing computation cost.
  • Under the global view, GNN depth determines full L-hop scope, whereas the local view fixes scope to a target-specific neighborhood.On ogbn-products, a 4-layer coupled GNN may propagate from about 0.6M neighbors, many of which may be barely relevant.
  • Decoupling extracts a small subgraph first, then applies a flexibly deep GNN whose depth and scope are independently tuned.The design uses extra message passing within the extracted scope to improve representation while avoiding global propagation.
  • Across seven benchmarks and two graph-learning tasks, SHADOW-GNNs improve accuracy while reducing computation and hardware costs by orders of magnitude.The largest cited benchmark contains 111M nodes.

2 Preliminaries

The preliminaries define graph notation, GNN layer variables, subgraph depth, and the distinction between model depth and subgraph depth. They also state that the framework extends beyond node classification to link prediction.

  • The graph is represented by nodes V, edges E, node features X, adjacency matrix A, and degree matrix D.
  • The notation distinguishes normalized adjacency matrices and subgraph-specific quantities such as G[u], X[v], and A[v].
  • For an L-layer GNN, H^(ℓ) denotes layer-ℓ features, d^(ℓ) the channel count, σ the activation, and W^(ℓ) the learnable weight.
  • A subgraph’s depth is the maximum shortest-path distance from its target node to any included node.
  • The paper’s depth–scope comparison refers to model depth rather than subgraph depth, and the design also generalizes to link prediction.

3 Decoupling the Depth and Scope of GNNs

SHADOW-GNN decouples GNN depth from scope by extracting a target-centered subgraph before applying a flexible-depth GNN. Theoretical analyses show gains in expressivity through local signal preservation, function approximation, and topological discrimination, while the practical design supports pooling and ensemble extensions.

  • Decoupling the Depth and Scope of GNNs: SHADOW-GNN extracts a connected subgraph G[v] around target v, then applies an L′-layer GNN while ignoring nodes and edges outside that subgraph.The extractor and GNN depth are independently tunable, unlike a normal GNN whose full L-hop neighborhood determines its scope.
  • Decoupling the Depth and Scope of GNNs: A normal GNN couples depth with scope, so increasing layers expands the receptive field and can propagate information from increasingly distant nodes.Under the normal setup, an L-layer GNN operates on the full graph and aggregates neighbors up to L hops away.
  • Graph Signal Processing Perspective: SHADOW-GCN preserves local feature and structural information because fixed subgraphs exclude faraway nodes regardless of propagation depth.By contrast, normal GCN propagation on a connected graph converges toward representations retaining little target information beyond degree.
  • Graph Signal Processing Perspective: SHADOW-GCN avoids normal-GCN oversmoothing: distinct extracted neighborhoods can yield different aggregations even for nodes with the same degree.The analysis contrasts normal GCN aggregation, which can collapse same-degree nodes, with SHADOW-GCN representations that preserve feature information.
  • Function Approximation Perspective: SHADOW-SAGE can express every function GraphSAGE can and some functions GraphSAGE cannot, including functions whose approximation error decays exponentially with depth.The construction uses extraction to prevent extra message passing from incorporating nodes outside the target neighborhood.
  • Topological Learning Perspective: SHADOW-GIN becomes more discriminative than 1-WL because localized subgraphs can break symmetries that remain indistinguishable in regular graphs.The same correspondence implies SHADOW-GIN is more discriminative than normal GIN.
  • Practical Design: Decoupling connects node- and link-level prediction with graph-level learning by enabling subgraph pooling and READOUT operations for target-entity tasks.The paper identifies pooling and ensemble extensions as ways to use embeddings produced by deep message passing.
  • Practical Design: Shallow subgraphs are a practical guideline rather than a universal requirement because applications with critical long-range dependencies may incur accuracy loss.The general decoupling principle may still help in such settings, but the paper leaves their study for future work.

4 Related Work

Related work addresses deep-GNN expressivity through architectural modifications, efficiency through sampling, and neighborhood redesign through graph reconstruction. These approaches differ from SHADOW-GNN because they do not generally decouple depth and scope.

  • Deep GNNs: Deep-GNN methods use residual connections, skip connections, or multi-hop propagation to improve performance as model depth increases.Examples include AS-GCN, DeepGCN, JK-net, MixHop, Snowball, DAGNN, and GCNII.
  • Sampling-based Methods: Sampling methods improve training efficiency by sampling neighbors per layer or subgraphs as minibatches.The cited methods include FastGCN, VR-GCN, AS-GCN, LADIES, MVS-GNN, Cluster-GCN, and GraphSAINT.
  • Re-defining the Neighborhood: Graph-reconstruction methods redefine neighborhoods or graph operators, but they still keep GNN depth and scope tightly coupled.The paper contrasts this coupling with SHADOW-GNN’s separate scope extraction and message-passing depth.

5 Experiments

Experiments evaluate SHADOW-GNN across seven graphs, six backbone architectures, node and link prediction, accuracy, neighborhood composition, oversmoothing, and inference cost. Results show that localized scopes support deeper models with improved accuracy and substantially lower computation.

  • Setup: SHADOW-GNN is evaluated on seven graphs ranging from 9K to 110M nodes, covering node classification and link prediction.The setup includes six node-classification datasets and ogbl-collab for link prediction.
  • Setup: SHADOW-GNN is constructed with six backbones: GCN, GraphSAGE, GAT, JK-Net, GIN, and SGC.Normal GNN baselines use full-batch or GraphSAINT minibatch training, whereas SHADOW-GNN uses minibatches for both training and inference.
  • Neighborhood composition: SHADOW-GNN scopes concentrate most neighbors within two hops, with almost none four or more hops away, making the effective scope much smaller than normal GNN neighborhoods.Normal GNN neighborhoods grow rapidly with depth, while SHADOW-GNN uses a small localized subgraph.
  • Accuracy: SHADOW-GNNs with scope sizes no more than 200 generally achieve significantly higher accuracy than normal GNNs at matched depths.The comparison indicates that shallow neighborhoods can contain sufficient information without changing the backbone architecture.
  • Accuracy: Increasing SHADOW-GNN depth from 3 to 5 often improves accuracy, and pooling sometimes provides an additional gain.Both deeper message passing and subgraph pooling are reported as effective architecture-tuning strategies.
  • Extraction and cost: PPR EXTRACT generally yields higher accuracy than 2-hop EXTRACT, while SHADOW-GNN inference cost is orders of magnitude lower than normal GNNs and grows linearly with depth.A 5-layer SHADOW-GNN remains much cheaper than a 3-layer normal GNN; GraphSAINT improves efficiency only during training.
  • Scaling: On ogbn-papers100M, the localized scope barely increases despite the full graph being at least two orders of magnitude larger than the Table 1 graphs.This experiment tests scaling to one of the largest public datasets.
  • Link prediction: SHADOW-SAGE outperforms the rank-1 model by a significant margin on ogbl-collab under the leaderboard comparison setting.The link-prediction evaluation excludes validation edges from training updates.

6 Conclusion

The paper concludes that decoupling GNN depth from scope improves expressivity and computation scalability across architectures, graphs, and learning tasks. Its theoretical analysis covers GCN, GraphSAGE, and GIN perspectives.

  • 6 Conclusion: The design principle decouples GNN depth and scope, improving expressivity and computation scalability across models.The paper presents theoretical analysis and design components including subgraph extraction functions and architecture extensions.
  • 6 Conclusion: The proof analyzes normalized subgraph adjacency using eigen-decomposition and the corresponding eigenvectors.The subgraph adjacency is described as a real symmetric matrix with eigenvalues bounded below −1 and largest eigenvalue 1.
  • 6 Conclusion: SHADOW-GCN’s aggregation distinguishes at least ⌈|V| / n⌉ possible aggregation patterns.The bound follows from at most n−1 other nodes sharing a target node’s neighborhood.
  • 6 Conclusion: When EXTRACT gives every node a distinct neighborhood, SHADOW-GCN produces distinct aggregations for all nodes.The cited corollary states that all nodes then have different aggregations.

A.2 Proof on SHADOW-SAGE Expressivity

The SHADOW-SAGE proof interprets normalized subgraph aggregation as a Markov-chain process. Its output approximates a target function, with error decreasing exponentially as depth increases.

  • A.2 Proof on SHADOW-SAGE Expressivity: The localized subgraph prevents certain long-range influences from reaching the target under the limited message passing available to normal GraphSAGE.The proof’s example includes an external node and an edge between 2-hop neighbors whose influence cannot reach the target in two passings.
  • A.2 Proof on SHADOW-SAGE Expressivity: SHADOW-SAGE’s normalized adjacency is a transition matrix whose limiting distribution supplies the coefficients of the target function τ.The proof uses Markov-chain convergence and mixing time to characterize approximation.
  • A.2 Proof on SHADOW-SAGE Expressivity: SHADOW-SAGE approximates τ when its depth is sufficiently large.The model output is stated to approach τ for large L′.
  • A.2 Proof on SHADOW-SAGE Expressivity: The approximation error decays exponentially with SHADOW-SAGE depth L′.The depth needed for a target error can be related to Markov-chain mixing time and the transition matrix’s absolute spectral gap.

A.3 Proof on SHADOW-GIN Expressivity

The SHADOW-GIN proof shows that decoupling preserves at least 1-WL-level discrimination and can exceed 1-WL on selected regular graphs. Local subgraphs can expose structural differences hidden by the full graph.

  • A.3 Proof on SHADOW-GIN Expressivity: A SHADOW-GNN following the stated update rule is at least as discriminative as the 1-dimensional Weisfeiler-Lehman test.An adequately deep GNN on the extracted subgraph can reproduce the output of the corresponding shallower model.
  • A.3 Proof on SHADOW-GIN Expressivity: SHADOW-GNN can distinguish nodes that 1-WL cannot when their extracted subgraphs are non-isomorphic and non-regular.The proof constructs this situation inside a connected 3-regular graph with identical node features.
  • A.3 Proof on SHADOW-GIN Expressivity: The SHADOW version of 1-WL separates selected nodes after two iterations in the constructed example.The corresponding local subgraphs differ topologically even though the full graph is regular.
  • A.3 Proof on SHADOW-GIN Expressivity: A 2-regular graph with two connected components provides another case where decoupling GIN distinguishes nodes that otherwise cannot be differentiated.The cited example identifies the graph as another 2-regular construction.
  • A.3 Proof on SHADOW-GIN Expressivity: Overall, applying decoupling makes the resulting GNN more discriminative than 1-WL.This combines the at-least-1-WL result with the constructed separating examples.

B Inference Complexity Calculation

The inference-cost analysis compares arithmetic operations for GCN, GraphSAGE, and GAT under minibatch inference. Normal GNN neighborhoods can grow exponentially with depth, whereas SHADOW-GNN cost grows linearly when the extracted subgraph is bounded.

  • B Inference Complexity Calculation: The reported inference complexity is intended to reflect practical minibatch deployment rather than only full-batch benchmark computation.The analysis assumes large graphs, relatively few target nodes, and embedding generation for a small target subset.
  • B Inference Complexity Calculation: On the same graph, GCN is less expensive than GraphSAGE, which is generally less expensive than GAT.The comparison is attributed to the different input and output node counts and attention computation.
  • B Inference Complexity Calculation: Normal GNN inference cost can grow exponentially with depth because full multi-hop neighborhoods cause neighbor explosion.The input-node and edge counts may increase exponentially with layer depth under the full-neighborhood architecture.
  • B Inference Complexity Calculation: SHADOW-GNN inference cost grows linearly with depth when its extracted subgraph has fixed n nodes and m edges.For SHADOW-GNN, n(ℓ) = n and m(ℓ) = m at every layer.
  • B Inference Complexity Calculation: Many benchmark graphs may not represent the realistic setting because their smaller size enables full-batch inference.The paper notes that ogbn-arxiv is downscaled 657× from ogbn-papers100M.
  • B Inference Complexity Calculation: Full-batch inference requires the full adjacency matrix and node features to fit in GPU memory.The paper gives 48GB as the requirement for 3-layer full-batch training on ogbn-products and states that full-batch computation is infeasible in practice.

C Designing Subgraph Extraction Algorithms

SHADOW-GNN treats subgraph extraction as an independently designed component for selecting bounded neighborhoods around target nodes. The paper describes heuristic, model-based, and learning-based extraction approaches, then applies a flexible GNN and readout pipeline to each extracted subgraph.

  • Heuristic based: Heuristic extraction can use hop limits, neighbor budgets, graph metrics, or PPR scores to select the subgraph around a target node.L-HOP EXTRACT traverses up to L hops with budget b, while PPR EXTRACT selects nodes with large approximate PPR scores.
  • Heuristic based: PPR EXTRACT computes an approximate PPR vector, retains high-score neighbors, and forms their induced subgraph.The computation visits only a local region because most PPR values are close to zero.
  • Alternative approaches: Model-based extraction reverses an assumed graph-generation process, whereas learning-based extraction incorporates extraction into GNN training.Learning extraction is challenging because subgraph selection is combinatorial and may require approximation or relaxation.
  • Design principle: EXTRACT and GNN depth are independently tunable, allowing localized subgraphs to support deeper message-passing models.The extraction function and layer propagation are separate stages in the inference algorithm.
  • Inference pipeline: The framework propagates node features through each extracted subgraph, then applies READOUT pooling and optional ensemble operations to produce embeddings.A subsequent MLP can combine the pooled subgraph summary with the target-node vector.
  • Scope: Detailed designs and evaluations for model-based and learning-based extraction are left for future work.The experiments described here focus on implemented extraction approaches rather than completing those alternatives.

D.1 Architecture for Subgraph Pooling

SHADOW-GNN supports multiple subgraph pooling operations for converting node-level subgraph embeddings into fixed representations. Sort pooling selects the most prominent rows before an MLP produces a single vector.

  • Pooling options: READOUT supports sum, max, mean, sort, and other pooling operations over the subgraph embedding matrix.The framework integrates these operations as subgraph-level readouts.
  • Sort pooling: Sort pooling orders the final feature column, selects the top s rows, and feeds the resulting s-row submatrix to an MLP.The MLP outputs one vector from the selected submatrix.
  • Ensemble: The framework also supports attention over outputs from different model branches before producing the final embedding.The ensemble uses a learnable vector and softmax-normalized weights.
  • Implementation: The paper notes that experiment tracking and visualization used Weight & Biases.This is an implementation detail rather than a pooling operation.

E.1 Additional Dataset Details

The appendix documents datasets, hardware, training configurations, and hyperparameter choices used to evaluate SHADOW-GNN. It also describes resource adaptability and implementation settings across the benchmark experiments.

  • Datasets: Yelp uses F1-micro because nodes may have multiple labels, while the other node-classification datasets use accuracy.For Reddit and Flickr, F1-micro equals accuracy because each node has one label.
  • Datasets: Only around 1% of ogbn-papers100M nodes have ground-truth labels, and splits are made among those labeled nodes.The passage specifies the labeled-node constraint for training, validation, and test sets.
  • Hardware: SHADOW-GNN was tested from low-end desktops to high-end servers, with batch size adapting training and inference to available hardware.The appendix lists three machines spanning different CPU, RAM, and GPU configurations.
  • Hardware: GPU memory is controlled by batch size, whereas larger graphs still require more RAM for their raw features.The raw data files for ogbn-papers100M already occupy 70GB.
  • Training configuration: Experiments use Adam, grid-search activation, dropout, DropEdge, and batch-size settings, with EXTRACT hyperparameters tuned separately.PPR EXTRACT uses either a fixed sampling budget or score thresholding with an upper-bound subgraph size.
  • EXTRACT configuration: PPR settings include budgets p in {150, 175, 200} or thresholds θ in {0.01, 0.05}, with upper bounds p of 200 or 500.The thresholding configuration retains an upper bound to avoid hardware inefficiency from very large neighborhoods.
  • Reproducibility: The appendix provides configurations for reproducing results in Tables 1–3 and specifies SGC settings shared across datasets.SGC and SHADOW-SGC use learning rate 0.001 and dropout 0.1.

F.1 Understanding the Low Memory Overhead of SHADOW-GNN

SHADOW-GNN reduces memory and computation demands by operating on minibatches of bounded subgraphs rather than full-graph propagated features. Its batch size and subgraph budget provide practical controls over hardware use, inference latency, and accuracy.

  • Memory overhead: SHADOW-GNN generally consumes much less memory than other GNN-based methods.The paper explains this through minibatched computation and avoidance of full-graph preprocessing.
  • Memory overhead: Minibatched SHADOW-GNN requires less GPU memory than normal full-graph GNNs, whose sampling alternatives can reduce accuracy or scalability.The comparison concerns both training and inference memory use.
  • Memory overhead: SIGN requires 682GB of RAM for the (3, 3, 3) ogbn-papers100M architecture, excluding temporary variables and other training buffers.The estimate follows from storing preprocessed features over the full graph.
  • Memory overhead: SGC requires at least 137GB of RAM on ogbn-papers100M from temporary features and the full adjacency matrix.The calculation is 2 · 56 + 25 = 137GB.
  • Hardware scaling: A 5-layer SHADOW-GAT can train ogbn-papers100M on a low-end server with 4GB of GPU memory and 128GB of RAM.Increasing batch size can improve GPU utilization on more powerful machines.
  • Architecture results: Pooling improves 5-layer SHADOW-SAGE accuracy on both evaluated graphs, although the best pooling function depends on graph characteristics.The paper leaves detailed analysis of pooling effects for future work.
  • Execution cost: PPR sampling is lighter than GNN computation in most evaluated cases, and its per-node sampling time does not grow with full graph size.The evaluation uses CPU parallelism for extraction and GPU execution for the GNN.
  • Accuracy–latency tradeoff: Reducing the PPR subgraph size from 200 to 50 cuts inference latency by 2× to 4× with less than 1% accuracy drop.This adjustment can be made without retraining, allowing latency-constrained deployment choices.
Loading 2201.07858v1…