PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Expressive Power of Geometric Graph Neural Networks

Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, Pietro Liò

arXiv:2301.09308v3cs.LGmath.GRstat.ML

TL;DR

Standard GNNs and WL do not directly apply to geometric graphs whose attributes transform with physical symmetries. The paper proposes GWL to analyze geometric GNN discrimination; it shows that invariant and equivariant designs differ in reach and connects discrimination to universal approximation.

  • Problem

    Standard GNNs and the WL framework do not directly handle geometric graphs whose attributes transform under spatial symmetries.

    Source: §1 · p. 1

  • Method

    The paper proposes GWL, a geometric WL test that characterizes geometric GNN expressivity through discrimination of geometric graphs.

    Source: §1 · p. 2, §7 · p. 9

  • Results

    Invariant layers cannot distinguish graphs with identical one-hop neighborhoods, whereas equivariant layers distinguish a larger class by propagating geometric information beyond local neighborhoods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GWL offers a more granular view of geometric GNN expressivity than binary universality and connects discrimination ability to universal approximation.

    Source: §1 · p. 2

    Invariant GNNs cannot decide several global or non-local geometric properties, including bounding-shape measures, distance from the centroid or centre of mass, and dihedral angles.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

The expressive power of Graph Neural Networks (GNNs) has been studied extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However, standard GNNs and the WL framework are inapplicable for geometric graphs embedded in Euclidean space, such as biomolecules, materials, and other physical systems. In this work, we propose a geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the underlying physical symmetries: permutations, rotation, reflection, and translation. We use GWL to characterise the expressive power of geometric GNNs that are invariant or equivariant to physical symmetries in terms of distinguishing geometric graphs. GWL unpacks how key design choices influence geometric GNN expressivity: (1) Invariant layers have limited expressivity as they cannot distinguish one-hop identical geometric graphs; (2) Equivariant layers distinguish a larger class of graphs by propagating geometric information beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable maximally powerful geometric GNNs; and (4) GWL's discrimination-based perspective is equivalent to universal approximation. Synthetic experiments supplementing our results are available at \url{https://github.com/chaitjo/geometric-gnn-dojo}

1. Introduction

Geometric graphs combine relational structure with spatial attributes whose physical meaning depends on respecting spatial symmetries, a setting standard GNNs and the WL framework do not directly handle. The paper introduces GWL to characterize geometric GNN expressivity and relate design choices to graph discrimination.

1. Introduction

  • Geometric graphs represent systems such as molecules using node attributes and spatial coordinates that transform under rotations, reflections, and translations.Ordinary GNNs that ignore these symmetries are ill-suited because geometric attributes would lose their physical meaning and transformation behavior.Source: §1 · p. 1
  • GWL provides a geometric counterpart to WL for characterizing geometric GNN expressivity and serves as an upper bound on their distinguishing power.It addresses the mismatch between standard graph tools and geometric graphs.Source: §1 · p. 2
  • Invariant GNNs cannot distinguish graphs with identical one-hop neighborhoods, while stacked equivariant layers can propagate geometric information beyond local neighborhoods.The paper also identifies scalarisation body order and tensor order as design axes for expressivity.Source: Figure 1 · p. 1, §1 · p. 2
  • The paper connects GWL discrimination to universal approximation and uses synthetic experiments to illustrate practical implications for expressive model design.The experiments include geometric oversquashing with increased depth and counterexamples motivating higher-order spherical tensors.Source: §1 · p. 2

2. Background

The background defines attributed and geometric graphs, their relevant symmetries, and the distinction between invariant and equivariant geometric GNN layers. It also motivates graph discrimination as a way to reason about geometric representations.

2. Background

  • An attributed graph consists of nodes, edges encoded by an adjacency matrix, and scalar node features; a geometric graph adds coordinates and optionally vector features.The geometric attributes transform under node permutations, orthogonal transformations, and translations.Source: §2 · pp. 2–3
  • WL iteratively hashes node features and neighborhood colors, but its graph-isomorphism framework does not directly account for geometric symmetries.A stable color partition that differs between graphs establishes non-isomorphism; otherwise WL is inconclusive.Source: §2 · p. 2
  • Geometric graph isomorphism allows geometric attributes to match up to global rotations or reflections and translations, in addition to an edge-preserving attributed-graph bijection.Distinguishing local geometries is motivated by representing distinct molecular environments with distinct representations.Source: §2 · p. 3
  • Equivariant geometric GNN layers propagate scalar and geometric features, whereas invariant layers propagate only local invariant scalars such as distances and angles.Both use permutation-equivariant message passing, and final scalar features can be mapped to graph-level predictions by a permutation-invariant readout.Source: §2 · p. 3

3. The Geometric Weisfeiler-Leman Test

GWL extends WL by aggregating geometric neighborhoods while preserving their transformation behavior, then assigning colors invariant to global symmetries. The framework upper-bounds equivariant GNN expressivity and characterizes conditions under which such networks match it.

3. The Geometric Weisfeiler-Leman Test

  • The GWL analysis assumes finite geometric graphs drawn from a countable dataset, with injectivity required over the dataset's countable set of G-orbits.Source: §3 · p. 3
  • The construction requires colors to be invariant to global group actions while auxiliary geometric information is updated equivariantly and injectively.This preserves neighborhood geometry, including relative pose or orientation, rather than retaining only invariant colors.Source: §3 · pp. 3–4
  • GWL aggregates geometric information from progressively larger t-hop neighborhoods and assigns colors through a G-invariant, orbit-injective map.It terminates when the color partition stabilizes and distinguishes two graphs when their color multisets differ at an iteration.Source: §3 · p. 4
  • IGWL(k) restricts local invariant descriptors to tuples of at most k nodes, so increasing body order can distinguish configurations missed by lower-order scalarisation.Pairwise distances provide 2-body information and distances plus angles provide 3-body information; some local geometries require higher-order invariants.Source: §3 · pp. 4–5

3.1. Characterising the expressivity of geometric GNNs

  • Any geometric graph pair distinguishable by a G-equivariant GNN is also distinguishable by GWL, and suitable injective aggregation, update, and readout functions let the GNN match GWL.The conditions require an injective G-equivariant multiset aggregation, orbit-injective invariant scalar updates, injective equivariant vector updates, and an injective multiset readout.Source: §3.1 · p. 5

4. Understanding the Design Space of Geometric GNNs via GWL

The section uses GWL to analyze how depth, equivariant versus invariant message passing, and scalarisation body order shape geometric GNN expressivity. Its results identify both architectural limits and conditions under which distinctions become possible.

4.1. Role of depth: propagating geometric information

  • GWL distinguishes k-hop distinct geometric graphs with isomorphic underlying attributed graphs in k iterations, while up to k iterations cannot distinguish k-hop identical graphs.For graphs built from point clouds using radial cutoffs, it distinguishes graphs with non-isomorphic underlying attributed graphs within the maximum graph diameter.Source: §4.1 · p. 5

4.2. Limitations of invariant message passing: failure to capture global geometry

  • GWL is strictly more powerful than IGWL: invariant message passing cannot distinguish 1-hop identical graphs or compute several global geometric properties.The cited examples include bounding-box or sphere perimeter, surface area and volume, centroid distance, and dihedral angles.Source: §4.2 · pp. 5–6, §4.1 · p. 5
  • For fully connected geometric graphs, IGWL has the same expressive power as GWL.The section also identifies precomputed non-local features and all-to-all message passing as ways to address limitations of local invariant message passing.Source: §4.2 · p. 6

4.3. Role of scalarisation body order: identifying neighbourhood G-orbits

  • I-HASH(m) is G-orbit injective when m equals the largest local-neighbourhood size in the dataset, and IGWL(k) is at least as powerful as IGWL(k−1), strictly so for k ≤ 5.The section notes that constructing injective I-HASH(k) may require intractably high k.Source: §4.3 · p. 6
  • When all edges have equal length, IGWL(2) distinguishes two geometric graphs if and only if WL distinguishes their attributed graphs.Distance-based invariant models also inherit WL failure cases, including distinguishing two equilateral triangles from a regular hexagon.Source: §4.3 · p. 6

5. Synthetic Experiments on Expressivity

Synthetic experiments probe depth-related propagation limits and the role of tensor order in distinguishing rotationally symmetric structures. The results point to oversquashing with deeper equivariant message passing and orientation limits when tensor order is below symmetry fold.

5. Synthetic Experiments on Expressivity

  • The experiments use k-chain graphs to probe depth and rotationally symmetric structures to test orientation discrimination and the utility of higher-order tensors.The accompanying codebase is described as a pedagogical resource for geometric GNN architectures.Source: §5 · pp. 6–7

5.1. Experiment in Table 1: Depth, non-local geometric properties, and oversquashing

  • G-equivariant GNNs can need more layers than GWL predicts for k-chains, while IGWL and invariant GNNs cannot distinguish k-chains for k ≥ 2 and G = O(3).The text presents this as preliminary evidence of oversquashing with geometric information propagated across layers in fixed-dimensional feature spaces.Source: §5 · p. 7, Table 1 · p. 7, §5.1 · p. 7

5.2. Experiment in Table 2: Higher order tensors and rotationally symmetric structures

  • Order L spherical-tensor layers cannot identify orientations when a structure’s rotational symmetry is higher than L-fold; the issue is especially prevalent with Cartesian vectors.The experiment trains single-layer equivariant GNNs to distinguish two rotated versions of each L-fold symmetric structure.Source: Table 2 · p. 8, §5.2 · p. 8

6. Discrimination and Universality

The section connects geometric-graph discrimination to universal approximation, first for countable features and then for continuous settings. It also derives lower bounds on the number of invariant aggregators needed to distinguish point clouds.

Countable Features

  • For countable Y, universal approximation implies pairwise YG discrimination; when Y is finite, pairwise discrimination implies universal approximation by C+2.The section motivates discrimination because a model that cannot distinguish two non-isomorphic geometric graphs is not universal.Source: §6 · p. 9

Continuous Features

  • For continuous features, universal approximation implies pairwise YG discrimination, and the converse holds with the additional assumption X = Y.The converse uses C+2 to approximate continuous functions over Y.Source: §6 · p. 9
  • For point clouds in R3, at least q = 3(n − 1) aggregators are required for orbit-injective functions under the stated setting.The section interprets this lower bound as an argument for why greater representational width can help distinguish neighbourhoods.Source: §6 · p. 9
  • Any Sn-invariant injective function from Rn×d to Rq requires q ≥ nd.This result concerns the zero-dimensional subgroup Sn × {eSO(d)} ≃ Sn.Source: §6 · p. 9

7. Conclusion

The paper proposes GWL to characterize geometric GNN expressive power, studies how design choices affect expressivity, and connects discrimination to universal approximation. It also identifies a practical challenge: GWL assumes perfect neighbourhood aggregation and colouring.

7. Conclusion

  • GWL provides a framework for characterizing geometric GNN expressivity and studying the effects of architectural choices.The work also reports synthetic experiments on practical challenges and connects discrimination to universal approximation.Source: §7 · p. 9
  • Building provably powerful practical models is challenging because GWL relies on perfect neighbourhood aggregation and colouring functions.The paper identifies developing maximally powerful practical geometric GNNs as future work.Source: §7 · p. 9

A. Discussion

The discussion positions GWL as a way to analyze discrimination beyond local point-cloud completeness and identifies limits to its coverage and completeness. The background contrasts invariant scalar message passing with equivariant vector and tensor representations.

A. Discussion

  • GWL extends analyses of local atom-centred neighbourhoods to geometric graph isomorphism beyond those neighbourhoods.The discussion contrasts its discrimination-based analysis with prior completeness work on point clouds around atoms.Source: A. Discussion · p. 12
  • GWL is complete for graphs built with radial cutoffs, but pathological cases may remain when graph topology is independent of coordinates.When coordinates and vector features are all zero, GWL coincides with 1-WL and inherits its failure cases.Source: A. Discussion · p. 12
  • GWL does not directly cover non-local architectures such as GemNet-Q or models using canonical reference frames, which the discussion leaves for future work.Canonical frames can scalarise equivariant features into invariant ones when such frames are readily defined, for example in protein backbones.Source: A. Discussion · p. 12

B. Additional Background on Geometric Graph Neural Networks

  • The background distinguishes invariant models, which propagate local scalar features, from equivariant models, which propagate geometric quantities such as vectors or tensors.The discussion also notes that proving complete geometric GNNs for all possible geometric graphs remains open under the completeness notions it describes.Source: A. Discussion · p. 12, B. Additional Background on Geometric… · p. 13

B.1. G-invariant GNNs

  • Invariant layers use distances or distances and angles, while their updated scalar features remain invariant to geometric transformations and translations.SchNet and CGCNN use relative distances; DimeNet and GemNet-T also use angles.Source: §B.1 · p. 13

B.2. G-equivariant GNNs using Cartesian vectors

  • Cartesian-vector equivariant layers update scalar and vector features; PaiNN conditions learned message filters on relative distance, and vector norms implicitly build 3-body invariants.Updated scalar features are invariant, while vector features are equivariant to G and invariant to translations.Source: §B.2 · pp. 13–14

B.3. G-equivariant GNNs using spherical tensors

  • Spherical-tensor models update features from scalar and vector orders through arbitrary higher orders, using tensor products and spherical harmonics of relative displacements.Learned radial basis functions provide distance-dependent weights, and Clebsch-Gordan coefficients ensure equivariance; restricting orders recovers scalar- or vector-style updates.Source: §B.3 · pp. 14–15
  • MACE obtains high body-order features by repeatedly taking self-tensor products of aggregated neighbourhood features, avoiding explicit symmetrisation or generation of all k-tuples.The discussion compares this computation to expanding a power of a sum, which implicitly includes the cross terms.Source: §B.3 · p. 15

C. Details on Synthetic Experiments

The synthetic experiments use several invariant and equivariant architectures to test geometric GNN expressivity. Their tasks probe non-local propagation, neighbourhood orientation, and the limits of k-body scalarisation.

C. Details on Synthetic Experiments

  • The evaluated models include SchNet, DimeNet, SphereNet, E-GNN, GVP-GNN, TFN, and MACE across invariant, Cartesian-vector, and spherical-tensor classes.The implementations are drawn from PyTorch Geometric, the respective authors, or e3nn, with MACE also reimplemented using its EquivariantProductBasisBlock in a TFN layer.Source: C. Details on Synthetic Experiments · p. 15
  • The experiments test k-chain discrimination, rotationally symmetric structures, and counterexamples to k-body scalarisation.These tasks respectively probe non-local geometric propagation and oversquashing, neighbourhood orientation, and the need for higher body order.Source: C. Details on Synthetic Experiments · p. 15
  • Models use 128 scalar channels or 64 scalar/vector/tensor channels, TFN and MACE default to order L = 2, and results average 10 random seeds.Training runs for 100 epochs with Adam, starting at learning rate 1e-4 and reducing it by 0.9 after a 25-epoch performance plateau.Source: C. Details on Synthetic Experiments · p. 15
  • Table 3 evaluates single-layer models on counterexamples to k-body scalarisation, where a geometric GNN layer of body order k cannot distinguish the corresponding structure.The table covers 2-, 3-, and 4-body counterexamples, including examples from Pozdnyakov et al. (2020).Source: Table 3 · p. 16

D.1. Role of depth (Section 4.1)

The results relate GWL's distinguishing power to hop depth and contrast it with invariant GWL's one-hop limit. Under radial-cutoff graph construction, GWL can also distinguish non-isomorphic underlying attributed graphs.

D.1. Role of depth (Section 4.1)

  • GWL distinguishes k-hop-distinct geometric graphs with isomorphic underlying attributed graphs in k iterations.The result follows because k iterations identify the G-orbit of each k-hop subgraph.Source: §D.1 · p. 16
  • Up to k iterations, GWL cannot distinguish k-hop-identical geometric graphs whose underlying attributed graphs are isomorphic.The stated hop relations say k-hop-distinct graphs are also (k + 1)-hop distinct, while k-hop-identical graphs are also (k − 1)-hop identical.Source: §D.1 · p. 16
  • IGWL distinguishes 1-hop-distinct graphs in one iteration but cannot distinguish 1-hop-identical graphs with isomorphic underlying attributed graphs, regardless of iterations.IGWL identifies local neighbourhood orbits but does not propagate geometric information beyond one hop.Source: §D.1 · pp. 16–17
  • With radial-cutoff graph construction, GWL distinguishes graphs with non-isomorphic underlying attributed graphs in at most kMax iterations, the maximum of their graph diameters.The radial cutoff defines edges by whether the squared distance between coordinates is at most r.Source: §D.1 · p. 17

D.2. Limitations of invariant message passing (Section 4.2)

GWL is strictly more powerful than IGWL, while invariant message passing cannot distinguish geometric graphs that are identical at one hop but differ in several global or non-local properties. The scalarisation results show that increasing body order can increase IGWL’s power, with limits and special cases depending on graph structure.

D.2. Limitations of invariant message passing (Section 4.2)

  • GWL is strictly more powerful than IGWL because it distinguishes some k-hop-distinct geometric graphs with isomorphic underlying attributed graphs that IGWL cannot distinguish.The proof uses pairs with k > 1.Source: §D.2 · p. 17
  • Figure 6 exhibits graphs that invariant methods cannot distinguish despite differing in bounding-box measures, centroid distances, and dihedral angles.Their bounding-box perimeter, surface area, and volume are (32 units, 40 units2, 16 units3) versus (28 units, 24 units2, 8 units3); their centroid-distance multisets also differ.Source: Figure 6 · p. 18, §D.2 · p. 18
  • IGWL computation trees remain identical when all one-hop neighbourhoods are computationally identical, because invariant updates do not pass geometric orientation between levels.The computation-tree construction unrolls message passing, with information propagated from leaves to root.Source: §D.2 · pp. 18–19, Figure 7 · p. 18
  • For fully connected geometric graphs, IGWL and GWL have the same expressive power.The proposition states equality specifically for fully connected graphs.Source: §D.2 · p. 19

D.3. Role of scalarisation body order (Section 4.3)

  • I-HASH(m) is G-orbit injective when m is the maximum neighbourhood cardinality in the dataset.The proof relies on distinct neighbourhoods having distinct multisets of m-body scalars.Source: §D.3 · p. 19
  • IGWL(k) is at least as powerful as IGWL(k−1), and is strictly more powerful for k ≤ 5 in the stated cases.The cited examples establish strict increases at k = 3, 4, and 5 for O(3) or SO(3), with the k = 5 cases distinguished by group.Source: §D.3 · pp. 19–20
  • When all edges have equal length, IGWL(2) distinguishes two geometric graphs if and only if WL distinguishes their attributed graphs.Source: §D.3 · p. 20

E. Proofs for equivalence between GWL and Geometric GNNs (Section 3.1)

The proofs relate the distinguishing power of geometric GNNs to GWL and IGWL. Equivariant GNNs are bounded by GWL, and injectivity conditions give matching expressive power; analogous results hold for invariant GNNs and IGWL.

E. Proofs for equivalence between GWL and Geometric GNNs (Section 3.1)

F.1. Equivalence between universality and discrimination

This section relates pairwise discrimination of geometric isomorphism classes to universal approximation. The implications hold in both directions under the stated finite-set or continuous-function assumptions.

F.1. Equivalence between universality and discrimination

  • If C is universally approximating over Y, then it is pairwise YG discriminating.This is the forward implication of the equivalence.Source: §F.1 · p. 22
  • For finite Y, pairwise YG discrimination by C implies that C+2 is universally approximating over Y.Theorem 17 establishes the converse under the finite-set setting.Source: §F.1 · p. 23
  • For continuous G-invariant functions on Y, universal approximation by C implies pairwise YG discrimination.The result assumes a metric space, compact Y, and a continuous action of G on X.Source: §F.1 · p. 23
  • For compact Y, a pairwise YG-discriminating class of continuous invariant functions can locate every orbit, and C+2 is then universal approximating.The section connects discrimination to orbit localization as a step toward universality.Source: §F.1 · p. 24
  • When X=Y, pairwise YG discrimination implies that C+2 universally approximates continuous functions over Y.This gives the converse for the continuous setting under the additional X=Y assumption.Source: §F.1 · p. 25

F.2. Number of aggregators in continuous setting

The section derives lower bounds on the output dimension of continuous orbit-injective representations in the continuous setting. The bounds depend on the acting symmetry group and its assumptions.

F.2. Number of aggregators in continuous setting

  • d ≥ n − m for any G-orbit injective function under the stated manifold and free-action assumptions.Here X is a smooth n-dimensional manifold, G is a compact Lie group of dimension m, and a same-dimensional submanifold with free G-action is assumed.Source: §F.2 · p. 25
  • q ≥ nd − d(d − 1)/2 for continuous S_n × SO(d) orbit-space injective functions when n ≥ d − 1 > 0 or n = d = 1.Theorem 21 gives this lower bound under the stated dimensional conditions.Source: §F.2 · p. 25
  • q ≥ nd − d(d − 1)/2 for continuous S_n × O(d) orbit-space injective functions when n ≥ d > 0.Theorem 22 states the bound for the orthogonal-group action.Source: §F.2 · p. 26
  • q ≥ nd for any S_n-invariant injective function from R^(n×d) to R^q.This proposition concerns permutation invariance without the geometric group action in the orbit-space bounds.Source: §F.2 · p. 26
Loading 2301.09308v3…