PaperlayerView exact revision on arXiv

Source-linked AI summary

How Powerful are Graph Neural Networks?

Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka

arXiv:1810.00826v3cs.LGcs.CVstat.ML

TL;DR

The paper asks how expressive GNNs are and how their aggregation schemes limit graph-structure recognition. It develops a theoretical framework based on multiset aggregation and the Weisfeiler-Lehman test, introduces GIN, and finds that GIN matches WL-level expressiveness while achieving strong benchmark performance.

  • Problem

    GNNs achieve strong empirical results, but their representational properties and limitations are not well understood theoretically.

  • Method

    The paper analyzes GNN aggregation as multiset functions, relates expressiveness to the Weisfeiler-Lehman test, and develops the Graph Isomorphism Network.

  • Results

    GIN is as powerful as the Weisfeiler-Lehman test, while popular variants such as GCN and GraphSAGE cannot distinguish certain graph structures; GIN also achieves state-of-the-art benchmark performance.

  • Takeaways & Limitations

    Injective aggregation and readout provide WL-level GNN expressiveness, and the resulting GIN architecture performs strongly on graph classification benchmarks.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieves state-of-the-art performance.

1 INTRODUCTION

The paper addresses limited theoretical understanding of GNN expressiveness by relating neighborhood aggregation to the Weisfeiler-Lehman test. It characterizes GNN variants, identifies their limitations, introduces GIN, and validates the theory empirically.

  • Motivation: GNN research has achieved strong empirical performance, but the theoretical properties and limitations of its architectures remain insufficiently understood.
  • Framework: The framework analyzes GNN expressiveness through multiset aggregation, where more discriminative aggregation functions yield greater representational power.
  • Main results: GNNs are at most as powerful as the Weisfeiler-Lehman test when distinguishing graph structures.
  • Main results: Injective neighbor aggregation and graph readout functions make a GNN as powerful as the Weisfeiler-Lehman test.
  • Main results: Popular variants such as GCN and GraphSAGE cannot distinguish some graph structures because their aggregation schemes are less expressive.
  • Empirical validation: GIN achieves high representational power experimentally, outperforming less powerful variants and attaining state-of-the-art performance on many graph classification benchmarks.

2 PRELIMINARIES

GNNs iteratively aggregate neighbor representations to encode node and graph structure, while the WL test provides a related procedure for distinguishing graph structures. Different aggregation and readout choices determine what information these models can capture.

  • Graph learning tasks: Node classification predicts node labels from final node representations, whereas graph classification predicts graph labels from aggregated graph representations.
  • Graph Neural Networks: GNNs update node representations through neighborhood aggregation, with k iterations capturing structural information within a node’s k-hop neighborhood.
  • Aggregation schemes: Aggregation and combination functions are central architectural choices, including max-pooling in GraphSAGE and mean pooling in GCN.
  • Graph-level representation: Graph-level readout functions aggregate final node features into a permutation-invariant representation for graph classification.
  • Weisfeiler-Lehman test: The WL test repeatedly aggregates neighborhood labels and hashes them into new labels, declaring graphs non-isomorphic when labels differ.
  • Weisfeiler-Lehman test: WL subtree features count rooted subtree structures represented by node labels at successive iterations.

3 THEORETICAL FRAMEWORK: OVERVIEW

The framework studies GNN expressiveness by treating neighboring feature vectors as multisets and asking when different neighborhoods receive different embeddings. This connects recursive neighborhood representation to the structures captured by the model.

  • Multisets: Neighboring feature vectors form multisets because identical feature vectors may occur at multiple neighboring nodes.
  • Multisets: A multiset consists of an underlying set of distinct elements together with the multiplicity of each element.
  • Expressiveness analysis: The framework evaluates GNN power by determining whether different neighborhoods map to distinct embeddings.
  • Expressiveness analysis: Maximally powerful GNNs preserve distinctions between different recursively defined subtree structures and their node features.
  • Expressiveness analysis: Popular GNN variants use inherently non-injective aggregation schemes, making them less powerful while still able to capture other graph properties.

4 BUILDING POWERFUL GRAPH NEURAL NETWORKS

The paper characterizes when GNNs can match the Weisfeiler-Lehman test and develops GIN, a simple architecture with maximum discriminative power among GNNs.

  • 4 BUILDING POWERFUL GRAPH NEURAL NETWORKS: Injective neighbor aggregation and graph-level readout make a GNN as powerful as the Weisfeiler-Lehman test.The result is stated for sufficiently many layers and countable input feature sets.
  • 4 BUILDING POWERFUL GRAPH NEURAL NETWORKS: GNNs satisfying the theorem’s criteria can embed subtrees in a low-dimensional space while preserving their discriminative distinctions.This extends beyond the one-hot feature representations used by the WL test to capture similarity between subtrees.
  • 4 BUILDING POWERFUL GRAPH NEURAL NETWORKS: Graph Isomorphism Network (GIN) provably satisfies the conditions required for maximum discriminative power among GNNs.GIN is constructed using injective multiset functions based on sum aggregation and neural networks.
  • 4 BUILDING POWERFUL GRAPH NEURAL NETWORKS: GIN is one simple example among many GNNs that can achieve maximum discriminative power.The paper does not claim GIN is the only architecture with this property.
  • 4 BUILDING POWERFUL GRAPH NEURAL NETWORKS: GIN generalizes the WL test and WL subtree kernel when graph readout sums node features from corresponding iterations.The model can use representations from all depths to incorporate structural information at multiple scales.

5 LESS POWERFUL BUT STILL INTERESTING GNNS

The paper explains why common GNN variants are less expressive: non-injective aggregators and shallow perceptrons can collapse distinct graph structures, although their retained information may suit some tasks.

  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: GCN and GraphSAGE use aggregation choices that can confuse surprisingly simple graphs and are less powerful than the WL test.The analysis characterizes which graph information these variants can and cannot capture.
  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: One-layer perceptrons can degenerate toward summing neighborhood features and are not universal approximators of multiset functions.The paper attributes the limitation partly to their linear behavior and, in the analyzed setting, the lack of a bias term.
  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: With identical node features, mean and max aggregation can produce the same representation everywhere and fail to capture structural information.Sum distinguishes different degrees through different multiples of the transformed feature.
  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: Mean aggregation preserves element proportions but not exact multiplicities, so scaled copies of a multiset receive the same embedding.Mean can match sum when node features are diverse and rarely repeat, or when degree information supplies the missing counts.
  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: Max aggregation ignores multiplicities and captures only the underlying set, preserving neither exact structure nor element distribution.It may nevertheless suit tasks that identify representative elements or a structural skeleton rather than exact graph structure.
  • 5 LESS POWERFUL BUT STILL INTERESTING GNNS: The framework does not cover non-standard aggregation schemes such as attention-based weighted averages and LSTM pooling.The authors state that the framework is general enough to analyze aggregation-based GNNs and leave these schemes for future work.

6 OTHER RELATED WORK

The paper contrasts its general framework for GNN expressive power with prior architecture-specific analyses. It presents GIN as theoretically motivated, simple, and powerful.

  • Earlier theoretical studies focused on individual GNN architectures and did not readily generalize across multiple architectures.
  • The paper instead provides a general framework for analyzing and characterizing the expressive power of a broad class of GNNs.
  • GIN combines theoretical motivation with a simple architecture designed to provide strong expressive power.

7 EXPERIMENTS

Experiments evaluate GIN and less powerful GNN variants across nine graph-classification benchmarks, emphasizing representational power through training fit and generalization through test accuracy. GINs fit training data best and achieve state-of-the-art or comparable performance across all datasets.

  • Evaluation: Training accuracy is used to compare representational power, whereas test accuracy measures generalization ability.
  • Datasets and models: The study evaluates GINs and less powerful variants on 9 graph-classification benchmarks spanning bioinformatics and social-network datasets.Social-network experiments emphasize learning graph structure rather than relying on informative node features.
  • Training set performance: GIN-ϵ and GIN-0 almost perfectly fit all training sets, while mean/max-pooling and 1-layer-perceptron variants severely underfit many datasets.Fixing ϵ to 0 yields no training-fit loss relative to learning ϵ.
  • Training set performance: MLP-based variants generally achieve higher training accuracy than 1-layer-perceptron variants, and sum aggregation fits better than mean or max pooling.
  • Training set performance: GNN training accuracies never exceed those of the WL subtree kernel, consistent with the WL test providing an upper bound on aggregation-based GNN representational capacity.On IMDB-BINARY, no model perfectly fits the training set, and GNNs reach at most the WL kernel’s accuracy.
  • Test set performance: GINs, especially GIN-0, outperform or match less powerful GNN variants on all 9 datasets and achieve state-of-the-art performance.Mean-aggregation models perform especially poorly on the unlabeled Reddit graphs, while GIN-0 slightly but consistently exceeds GIN-ϵ in test accuracy.

8 CONCLUSION

The paper establishes theoretical foundations for GNN expressive power and proves tight representational bounds. It also designs a provably maximally powerful neighborhood-aggregation GNN while identifying broader directions beyond this framework.

  • The paper develops theoretical foundations for reasoning about GNN expressive power and proves tight bounds for popular GNN variants.
  • It designs a GNN that is provably maximally powerful within the neighborhood-aggregation framework.
  • Future work includes architectures beyond neighborhood aggregation and improved understanding of GNN generalization and optimization.

A PROOF FOR LEMMA 2

The proof shows that a neighborhood-aggregation GNN cannot distinguish two graphs that the WL test cannot distinguish. This follows by inductively matching WL labels with GNN node features and using permutation-invariant readout.

  • If the WL test gives two graphs identical node-label collections, their GNNs also produce identical collections of node features.
  • Identical neighborhood multisets produce identical GNN updates because the same aggregation and combination functions receive the same inputs.
  • The proof inductively establishes that corresponding WL node labels imply corresponding GNN node features at every iteration.
  • Permutation-invariant graph readout then yields A(G1) = A(G2), contradicting any claimed GNN distinction between the graphs.

B PROOF FOR THEOREM 3

The proof shows that an injective GNN aggregation process preserves the Weisfeiler–Lehman test’s ability to distinguish non-isomorphic graphs. It establishes this correspondence inductively across iterations and concludes that graph embeddings differ when WL separates the graphs.

  • Inductive correspondence: An injective graph-level readout reduces the proof to showing that neighborhood aggregation produces different node-feature multisets for graphs separated by WL.The argument considers graphs that WL decides are non-isomorphic after iteration K.
  • Inductive correspondence: At each subsequent iteration, the proof constructs an injective correspondence between WL labels and GNN representations by composing injective functions.The composition argument preserves injectivity across iterations.
  • Inductive correspondence: The base case holds because WL and GNN use the same initial node features, allowing the correspondence function to be the identity.This establishes the induction at k = 0.
  • Conclusion: Because the final node embeddings differ for the two graphs, injectivity of the graph-level readout yields different graph representations.Thus, the GNN distinguishes the graph pair whenever the WL test does.

C PROOF FOR LEMMA 4

The proof establishes countability of bounded-size multisets and uses injective encodings to support the construction of universal multiset functions. It then shows how these encodings distinguish multisets and node-neighborhood pairs.

  • Countability construction: Countability of N × N extends by induction to finite Cartesian products of countable sets, providing the foundational counting result.This result is used to show that bounded-size multiset encodings have countable range.
  • Countability construction: Every bounded-size multiset can be injectively encoded as a fixed-length tuple of ordered elements padded with a dummy element e.The bound on multiset size supplies a common tuple length, and padding preserves injectivity.
  • Injective multiset functions: A countable element-to-integer mapping assigns each multiset element a unique coordinate, enabling an injective one-hot-style sum representation.The construction uses f(x) = N − Z(x) and bounded cardinality to make multiset sums unique.
  • Injective multiset functions: For a node and its neighbor multiset, h(c, X) = (1 + ϵ) · f(c) + Σx∈X f(x) is injective when ϵ is irrational.The irrational coefficient separates the central element from the rational multiset-sum contribution.
  • Max-based construction: The max aggregator can distinguish multisets sharing an underlying set by using one-hot embeddings, making the maximum unique for each such multiset.The construction assigns each element a distinct one-hot coordinate.

I DETAILS OF DATASETS

The experiments use social-network and bioinformatics graph-classification datasets. The social datasets represent movie, online discussion, or collaboration networks, while the bioinformatics datasets represent chemical compounds and protein structures.

  • Social networks datasets: IMDB-BINARY and IMDB-MULTI contain actor or actress ego-networks, with graph labels determined by the movie genre.Nodes represent actors or actresses, and edges connect pairs appearing in the same movie.
  • Social networks datasets: REDDIT-BINARY and REDDIT-MULTI5K are balanced graph datasets derived from online discussion networks.The supplied description identifies these datasets as social-network benchmarks.
  • Bioinformatics datasets: PROTEINS represents secondary-structure elements connected by sequence or three-dimensional proximity, with labels for helix, sheet, or turn.Its three discrete labels correspond to protein secondary-structure types.
  • Bioinformatics datasets: PTC contains 344 chemical compounds with 19 discrete labels reporting carcinogenicity for male and female rats.The dataset provides compound-level carcinogenicity classifications.
Loading 1810.00826v3…