PaperlayerView exact revision on arXiv

Source-linked AI summary

From Local Structures to Size Generalization in Graph Neural Networks

Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, Haggai Maron

arXiv:2010.08853v3cs.LGcs.NEstat.ML

TL;DR

GNNs can process different graph sizes, but it is unclear when they generalize from small to large graphs, especially when local structure changes with size. The paper formalizes this shift with d-patterns, proves that bad global minima can exist, studies convergence empirically, and proposes adaptation strategies, including a self-supervised task that improves large-graph classification accuracy.

  • Problem

    The paper asks when GNNs trained on small graphs generalize to larger graphs, a problem made practically important by costly or difficult large-graph labeling.

  • Method

    The paper characterizes size generalization using d-patterns, proves bad global minima can arise under d-pattern discrepancy, and evaluates self-supervised and semi-supervised approaches.

  • Results

    The paper finds that local-structure discrepancy leads to non-generalizing solutions, while the new self-supervised task increases large-graph classification accuracy by 4% on average on real datasets.

  • Takeaways & Limitations

    Size generalization can be improved by learning d-pattern representations from both small and large graphs or by using limited labeled examples from the target domain.

  • Takeaways & Limitations

    The approach assumes categorical node features and bidirectional edges without features, and some tasks still do not show improved generalization.

Abstract

from arXiv · show

Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.

1. Introduction

The paper studies when GNNs generalize from small to large graphs, focusing on distributions whose local structures change with graph size. It identifies local-structure discrepancy as a source of difficult size generalization and proposes approaches to improve it.

  • Size generalization matters because graph sizes vary widely across molecular biology, social networks, and other domains.Large-graph labels can be expensive to obtain or difficult for humans to assign accurately.
  • The paper focuses on graph distributions where the distribution of local structures depends on graph size, including preferential attachment graphs.This dependency is reported in social, biological, and internet-related networks.
  • d-pattern discrepancy between training and test graphs can create global minima that fit small graphs but fail on large graphs.d-patterns represent local structures visible to GNNs within d-step neighborhoods.
  • As d-pattern discrepancy grows, GNN generalization to new graph sizes deteriorates in controlled synthetic experiments.
  • A self-supervised task on d-patterns increased large-graph classification accuracy by 4% on average on real datasets.The setup trains on labeled small graphs while applying the new task to large graphs.
  • The paper combines theoretical and empirical results to identify difficult distributions and suggests approaches for improving size generalization.The proposed ideas are intended to extend to graph-learning settings with train-test local-structure discrepancies.

2. Preliminaries

The preliminaries define the message-passing GNN setting and explain how graph size can alter local structure in common graph distributions. Examples include Erdős–Rényi and preferential attachment graphs.

  • The paper uses message-passing GNNs whose node representations are updated from features and neighboring-node information across layers.The cited architecture is described as maximally expressive among message-passing neural networks.
  • For graph prediction, node representations are aggregated by an additional readout layer, possibly followed by a fully connected network.
  • In G(n, p) graphs, fixing p while increasing n changes the mean degree and therefore the local structure.
  • In preferential attachment graphs, increasing graph size raises the maximum degree and changes local structure.New nodes connect preferentially to higher-degree nodes.

3. Overview

The overview frames size generalization through d-patterns, which capture GNN-visible local structure, and connects their discrepancy to both theoretical failure modes and empirical convergence. It then presents domain-adaptation, self-supervised, and semi-supervised routes for improvement.

  • A simple edge-counting task can be solved by a 1-layer GNN, yet training on non-diverse data reaches a non-generalizing solution with probability 1 over initialization.
  • d-patterns: d-patterns encode a node’s local structure and its d-step neighbors as captured by a GNN.For featureless graphs, a 1-pattern represents degree, while a 2-pattern includes neighboring degrees.
  • Theoretical result: When test graphs contain d-patterns absent from training graphs, there exist global minima that succeed on training data but fail on test data.This result applies to graph tasks solvable by a GNN.
  • Empirical result: In controlled experiments, GNNs tend to converge to small-graph solutions that fail on large graphs when large-graph d-patterns are absent from small graphs.This occurs even when another global minimum solves the task across all graph sizes and is also observed in real datasets.
  • Improving generalization: The paper proposes domain adaptation, a d-pattern self-supervised task, and limited target-domain labels as ways to improve size generalization.Both proposed learning setups are evaluated on synthetic and real data.

4. GNNs and local graph patterns

The paper introduces d-patterns to represent the local information available to a d-layer GNN and shows that these patterns characterize its node-level outputs. A constructive theorem further shows that GNN outputs can be assigned independently across finite d-patterns.

  • GNN expressivity: The d-pattern representation is motivated by the Weisfeiler–Lehman test, which has the same representational power as GNNs.The construction describes local structures as seen through message-passing iterations.
  • Defining d-patterns: d-patterns encode a node’s feature and the recursively counted patterns of its neighbors within d steps.For uniform node features, 1-patterns represent degree, while 2-patterns count neighboring degrees.
  • GNN expressivity: A d-layer GNN must produce the same output for nodes with the same d-pattern.Thus, d-patterns capture the information that message passing can distinguish at a node.
  • Representation limits: Different neighborhoods can share a d-pattern, so d-patterns contain only part of a node’s full d-neighborhood information.This limits what the representation can distinguish even when it exactly characterizes d-layer GNN outputs.
  • Constructive expressivity: A GNN with d + 2 layers can assign prescribed outputs to every pattern in a finite set of d-patterns.The construction uses ReLU activations and width bounded by max((N + 1)^d · |C|, 2).
  • Constructive expressivity: The construction improves on prior work by specifying outputs for each d-pattern with more efficient width dependence on the number of patterns.Its width dependence is 2^|P| instead of |P|^2.

5. ”Bad” global minima exist

The paper proves that discrepancies in d-pattern distributions can create GNN solutions that fit training graphs but fail on graphs from another distribution. This applies especially when large test graphs contain d-patterns absent from small training graphs.

  • Scope: The theory covers both graph-level prediction and node-level prediction tasks.Examples include graph edge counting and node regression.
  • Graph-level tasks: If test graphs contain d-patterns absent from training graphs, a GNN can solve the training task while failing arbitrarily badly on every test graph.For graph regression, the constructed network has depth at most d + 3 and can have arbitrarily large test error.
  • Mechanism: The mechanism is that GNN weights can assign different outputs to d-patterns unseen during training, changing predictions on the test distribution.A global readout transfers node-level output differences to graph-level predictions.
  • Node-level tasks: For node prediction, a discrepancy between d-pattern distributions implies a solution with low loss on one distribution and loss Δ(ϵ) on the other.The discrepancy is measured by pattern sets that have small probability under the training distribution and large probability under the test distribution.
  • Example: For Erdős–Rényi training graphs G(n, p) and test graphs G(2n, p), the average degree changes from np to 2np, creating different local structures.This provides a concrete small-to-large size-generalization setting for the theoretical result.

6. A controlled empirical study

Controlled experiments show that GNN size generalization tracks the discrepancy between local d-pattern distributions in training and test graphs. Generalization worsens when the discrepancy grows and improves when graph sizes or expected degrees are aligned.

  • Main findings: Large d-pattern discrepancies are associated with failed generalization, while smaller discrepancies are associated with improved generalization.These two trends are observed across the controlled synthetic experiments.
  • Varying test size: With constant p = 0.3, increasing test graph size from a training range of n ∈ [40, 50] degrades size generalization.The d-pattern distribution diverges from the training distribution, and the problem persists for graphs up to 500 nodes.
  • Degree normalization: Keeping expected degree np constant while varying graph size yields significantly better generalization to large graphs.Adjusting p preserves a more similar d-pattern distribution between training and test graphs.
  • Training-size range: As the maximum training size approaches the fixed test size n = 150, d-pattern discrepancy decreases and generalization improves.This experiment varies training sizes n ∈ [40, x] with x up to 150.
  • Matching local structure: When testing n = 100 graphs across p values, test loss is minimized at p = 0.15, where expected node degree and d-pattern distribution most closely match training.Training uses n ∈ [40, 50] and p = 0.3.
  • Network depth: Size generalization becomes more difficult with deeper networks because higher-order patterns create more severe distribution discrepancies.The paper notes that 2-patterns divide nodes into substantially more pattern classes than 1-patterns.
  • Robustness: The findings remain consistent across max clique, edge count, and node regression tasks, PA and point-cloud graphs, and GIN architectures.Additional experiments also examine tanh and sigmoid activations and large-to-small generalization.

7. Towards improving size generalization

The paper formulates size generalization as domain adaptation from small-graph source data to large-graph target data, targeting unseen d-patterns. A pattern-tree SSL task and limited target labels improve performance across several experimental settings.

  • Domain adaptation: The authors treat small graphs as a source domain and large graphs as a target domain whose unseen d-patterns require adaptation.The target data may be unlabeled or may include a small number of labeled examples.
  • Pattern-tree pretext task: The proposed SSL task learns node representations that encode local d-patterns appearing in both source and target graphs.The pretext task predicts a descriptor formed from feature histograms across layers of a pattern tree.
  • Datasets: The real-data evaluation uses seven molecular-biology and social-network datasets, with severe d-pattern discrepancies for social networks and milder discrepancies for biological datasets.The reported total-variation distances are approximately 1 for social datasets and range from 0.15 to 0.48 for biological datasets.
  • Experiments: The pattern-tree method with pretraining raises average test accuracy from 63% to 67% compared with the second-best method across seven binary classification tasks.It achieves the highest accuracy in most tasks.
  • Experiments: Pretraining with the d-pattern task outperforms other baselines in 5 of 7 datasets and improves average accuracy by 4% across all datasets.On datasets with high local-pattern discrepancy, the improvement over vanilla training averages 5.4%.
  • Experiments: Without SSL, larger size gaps hurt more, whereas SSL improves over vanilla training for larger gaps.The experiments compare training on the 30% smallest graphs with testing on the 5% largest graphs against a smaller 10% gap.
  • Experiments: In the semi-supervised setup, pretraining performs better with 0, 1, and 5 labeled target examples and comparably with 10 labeled examples.Accuracy increases monotonically with the number of labeled examples for both methods.

8. Related work

Related work covers size generalization, theoretical GNN generalization, and graph self-supervised learning. The paper differs by focusing its SSL task on local node structure rather than whole-graph representations.

  • Size generalization: Prior studies report successful size generalization or improved generalization from step-by-step algorithmic training, but the underlying reasons and practical applicability remain limited.The cited algorithmic procedures cannot be easily applied to general graph-learning settings.
  • Related generalization settings: Other work studies GNN expressivity on set-structured inputs and generalization in abstract reasoning tasks.These studies address related reasoning and representation questions rather than the paper’s specific size-generalization characterization.
  • GNN generalization: Existing GNN generalization-bound studies address particular GNN classes but do not discuss size generalization, while benchmarks assess logical generalization abilities.The paper positions its question separately from these bounds and benchmarks.
  • Self-supervised learning: Graph self-supervised learning includes graph autoencoders, global-property prediction, node masking, and contrastive learning.These approaches span unsupervised representation learning and pretext tasks on graphs.
  • Self-supervised learning: Unlike contrastive approaches that incorporate the entire graph, this paper’s SSL task represents each node’s local structure through its d-pattern.The distinction follows the paper’s theoretical observation about local-pattern shifts.

9. Conclusion and Discussion

The paper concludes that d-pattern distributions help explain failures of GNN size generalization and that the proposed approaches improve generalization on multiple tasks. Their scope is limited by feature and edge assumptions, and some tasks remain unimproved.

  • Conclusion: For important graph distributions, GNNs do not naturally generalize to larger graphs even on simple tasks.The paper connects this failure to the distribution of local d-patterns.
  • Conclusion: The paper defines d-patterns, characterizes how size-generalization failure depends on them, and proposes two approaches that improve generalization across multiple tasks.The conclusion frames these contributions as steps toward understanding size generalization.
  • Discussion: Some tasks still do not show improved generalization with the proposed approaches.The conclusion explicitly preserves this boundary despite improvements on multiple tasks.
  • Limitations: The approach assumes categorical node features and bidirectional edges without edge features.The authors identify extending beyond these assumptions as future work.

Supplementary Material: From Local Structures to Size Generalization in

The theoretical analysis shows that even an easy task solvable by a single-layer GNN can have many training solutions, while only a small subset generalizes across graph sizes. The construction formalizes local structures through d-patterns and shows how GNNs can represent and memorize them.

  • Single-layer size generalization: The edge-count task is solvable for any graph size by counting each node’s neighbors and summing them, yielding 2|E|.A one-layer GNN can compute neighbor counts, and additive readout aggregates these counts.
  • Single-layer size generalization: The training objective has an affine solution space, but only solutions with w1 + b = 0 and w2 = 1/2 generalize to every graph size and edge count.Other solutions depend on the training graph size n.
  • Single-layer size generalization: With fixed n/m, gradient descent from standard initialization converges with probability 1 to a non-generalizing global solution.The selected solution is the global solution closest to the initialization point.
  • Single-layer size generalization: Simple regularization does not generally recover the generalizing solution because it is not usually the least-norm solution under either L1 or L2 norms.It is least L1 norm only when 2m > n.
  • d-pattern constructions: d-patterns encode a node’s value and its d-step neighborhood as seen by a GNN, while the proofs construct networks that map finite pattern sets to prescribed labels.The construction uses WL-equivalent local structure and ReLU networks with bounded width to represent pattern-dependent outputs.

C. Proofs from Sec. 5

The proofs establish that GNNs can behave differently on graph distributions with distinct local-pattern supports, and experiments show that this mismatch produces poor size generalization across tasks, architectures, and graph distributions.

  • Proofs from Sec. 5: A constructed GNN preserves outputs on source patterns but changes outputs on patterns appearing only in the second distribution, causing incorrect predictions there.The construction augments node representations with an indicator for patterns outside the source support.
  • Empirical size generalization: The experiments show that increasing graph size can significantly increase test loss even when validation loss is effectively zero.This result persists when training on graphs of size 40–50 and testing up to size 500 with p = 0.3.
  • Max-clique size: On max-clique, changing depth reduces loss by at most 25% under similar pattern distributions but can increase loss by more than 5.5× under a pattern-distribution shift.The effect appears in both first-order GNN and GIN architectures.
  • Preferential attachment: For preferential-attachment edge counting, depth-2 and depth-3 GNNs increasingly fail as test graphs grow from 50 to 500 nodes, despite an all-size solution existing.Training uses n uniformly sampled from [10, 50] and m = 4; testing varies n with m = 4.
  • Reverse size generalization: Large-to-small generalization is also difficult, but performance improves when training and test graph sizes are closer.The experiments use G(n, p) graphs with p = 0.3 and test sizes 50 and 75.

E. SSL task on d-pattern tree

The SSL approach uses d-pattern trees to expose local-structure information to GNNs, with pretraining or multitask training procedures incorporating this auxiliary task. Pattern trees encode the information a GNN can produce for a node.

  • d-pattern trees: A d-pattern tree represents the local structure around a node recursively, with node features attached to the corresponding tree nodes.The construction is based on the d-pattern introduced earlier in the paper.
  • d-pattern trees: Pattern trees encode all information a GNN can produce for a given node, and correspond one-to-one with d-patterns of the same depth.Representing the target distribution’s pattern trees therefore represents its d-patterns.
  • SSL task: The SSL regression task asks each node to count nodes by layer and feature within its d-pattern tree.This descriptor loses some connectivity information but retains layer-structure information.
  • Training procedures: Pretraining first trains the GNN and SSL head, then freezes the GNN while training a main-task head on labeled data.This separates representation learning from main-task learning.
  • Training procedures: Multitask training jointly optimizes a shared GNN with separate SSL and main-task heads, weighting the SSL loss by α = 1/2 in the experiments.Few-shot target examples can additionally contribute a weighted main-task loss in both procedures.

G.1. Synthetic datasets

Synthetic experiments evaluate size generalization from graphs with 40–50 nodes to graphs with 100 nodes and test d-pattern SSL, pretraining, and multitask settings. The results show that SSL can improve transfer, but gains depend on the task and setup.

  • Training used G(n, p) graphs with n uniformly sampled from [40, 50] and p = 0.3, while target graphs had n = 100 and p = 0.3.
  • Adding the d-patterns SSL task significantly improved the teacher-student task, although it did not completely solve size generalization.
  • For the 3-layer teacher-student experiment, pattern-tree SSL with pretraining improved over vanilla training for every tested p except p = 0.15.
  • Max clique: On max-clique prediction, pretraining with SSL reduced average squared loss from 2325 without SSL to 1327, whereas multitask training performed worse than vanilla training.
  • The ogbg-molpcba evaluation produced inconclusive results, with a slight edge toward vanilla training after omitting unsupported node and edge features.
Loading 2010.08853v3…