Source-linked AI summary
The expressive power of kth-order invariant graph networks
Floris Geerts
TL;DR
The open question is whether kth-order invariant graph networks can distinguish graphs that k-WL cannot, despite k-IGNs already simulating k-WL. The paper uses the k-WL–Ck connection to extend the k=2 bound to arbitrary k, showing that the two formalisms have equal graph-distinguishing power.
Problem
Although k-IGNs can simulate k-WL, it remained open whether they could distinguish graphs that k-WL cannot.
Source: §1 · p. 2Method
The paper extends the k=2 argument to arbitrary k, using the connection between k-WL and the logic Ck.
Source: §1 · p. 2Results
For arbitrary k, k-IGNs are bounded by k-WL, so they have equal power to distinguish graphs.
Source: §1 · p. 2, §4 · p. 16Takeaways & Limitations
A k-IGN layer corresponds to k −1 k-WL iterations, potentially distinguishing graphs faster at the cost of more intensive updates over all k-tuples.
Source: §1 · p. 2, §4 · p. 17
Abstract
from arXiv · showhide
The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
1 Introduction
The introduction asks whether kth-order invariant graph networks can distinguish graphs beyond k-WL, despite their ability to simulate k-WL. It establishes that their distinguishing power is bounded by k-WL for arbitrary k.
1 Introduction
- MPNNs are bounded by 2-WL, while degree awareness can let them distinguish graphs one iteration earlier than 2-WL.MPNNs update vertex features using neighboring vertices; variants also use port numbering, random initial features, or static vertex identifiers.Source: §1 · pp. 1–2
- k-WL’s increasing expressive power makes it a basis for more expressive GNNs, including distinguishing graph patterns such as cycles and cliques.For example, 3-WL can distinguish graphs by their numbers of cycles of length up to 7 and triangles.Source: §1 · p. 2
- k-IGNs already simulate k-WL, but their updates use all k-tuples rather than only neighboring tuples, leaving open whether they are more expressive.Their equivariant layers can treat tuples differently according to equality and inequality patterns relative to the tuple being updated.Source: §1 · p. 2
- For undirected graphs, Chen et al. (2020) showed that 2-IGN expressive power is bounded by 2-WL, with a one-to-one correspondence between 2-IGN layers and 2-WL iterations.The passage identifies k-FWL as more efficient to implement; k-PPGNs simulate k-FWL (and thus (k + 1)-WL) using kth-order tensors with tensor multiplication.Source: §1 · pp. 2–3
- For arbitrary k, k-IGNs are bounded by k-WL in graph-distinguishing power; one k-IGN layer corresponds to k −1 k-WL iterations.This generalizes the k=2 result; the faster correspondence comes with a more intensive update involving all k-tuples.Source: §1 · p. 2
2 Background
The background establishes the notation and formal tools used to compare k-WL with k-IGNs: tuple colorings, counting logic, and permutation-equivariant tensor networks.
2 Background
- Graphs are treated as coloured graphs, and the section fixes notation for vertex tuples, colours, and tensor entries.The vertex set is identified with [n], and each coloured graph assigns a colour to every vertex.Source: §2 · p. 3
2.1 Weisfeiler-Leman
- k-WL iteratively colors k-tuples; its initial tuple colors encode vertex colors and which coordinates are equal.The update uses colors of neighboring tuples and an injective hash of the resulting input.Source: §2.1 · p. 3
2.2 Counting logics
- Ck uses k variables, equality, color and edge predicates, Boolean operations, and counting quantifiers; two graphs agree in k-WL exactly when they satisfy the same Ck sentences.The equivalence holds also when both comparisons are restricted by quantifier rank.Source: §2.2 · p. 4
2.3 Invariant graph neural networks
- Equivariant linear layers commute with vertex permutations and are constant on tuple pairs sharing the same equality pattern.Equality patterns can be represented as partitions of the 2k tuple positions.Source: §2.3 · pp. 4–5
- A k-IGN maps an initial tensor encoding of a graph through equivariant layers, pointwise activations, an invariant layer, and an MLP to an invariant output.The initial tensor encodes the initial k-WL colors, and graph indistinguishability is defined by equality of the resulting outputs.Source: §2.3 · p. 5
3 The expressive power of k-IGNs
This section shows that k-IGNs cannot distinguish any pair of graphs that k-WL cannot, complementing the known ability of k-IGNs to simulate k-WL. Its proof establishes a key lemma by comparing colour counts in relaxed tuple sets, treating patterns with and without used constant classes.
3 The expressive power of k-IGNs
- For any k ≥ 2, if G ≡k-WL H, then G ≡F H for every k-IGN F, extending the result to directed graphs.The proof matches one equivariant layer to k − 1 rounds of k-WL, reflecting that k-IGNs aggregate information from all k-tuples while k-WL propagates through neighbouring tuples.Source: §3 · pp. 6–7
3.1 Proof of Lemma 3
- The proof of Lemma 3 uses induction in steps of k − 1 WL rounds and a key lemma connecting colour multisets grouped by equality pattern to equivariant-layer updates.The key lemma uses the connection between k-WL and counting logics, a proof strategy that generalizes beyond the case analysis used by Chen et al. (2020) for k = 2.Source: §3.1 · p. 8
3.2 Proof of Lemma 4
- Lemma 4 shows that matching tuple features after d layers makes the invariant readout agree, because invariant layers can be decomposed according to equality patterns.The proof then concludes G ≡F H.Source: §3.2 · p. 10
3.3 Proof of the key lemma
- The key lemma is proved by contradiction: a failed equality-pattern colour-multiset match would yield a Ck formula of quantifier rank at most t distinguishing the tuples, with special patterns handled using G ≡t′-WL H.The proof classifies equality-pattern classes as constant or variable, and constant classes as used or unused, to describe the tuple constraints.Source: §3.3 · p. 10
- Dropping condition (d) defines relaxed tuple sets, which allow the original sets to be rewritten using relaxed sets for modified equality patterns.The proof first motivates omitting condition (d), then states that the example’s rewriting holds in general.Source: §3.3 · pp. 11–12
- A permutation can make an equality pattern good while preserving its relaxed tuple sets, enabling the proof to handle patterns in the required form.Goodness requires that, in each used constant class, the smallest-index variable position belongs to that class.Source: §3.3 · p. 14
- For good equality patterns with at least one used constant class, the proof establishes equality of the k-WL colour counts in the relaxed tuple sets.A C_k formula of quantifier rank at most t would distinguish the tuples if the counts differed, contradicting their agreement on such formulas.Source: §3.3 · pp. 15–16
- When µ has no used constant classes, membership depends only on variable-class equality conditions and can be replaced by membership in an equality pattern τ.The passage notes that there is no relationship between the tuples v and v′ in this case.Source: §3.3 · p. 16
- The proof uses the stated k-WL equivalence to infer equality (11), concluding the Key Lemma.Source: §3.3 · p. 16
4 Conclusion
The conclusion establishes that k-IGNs and k-WL are equally expressive for distinguishing graphs. It also relates a k-IGN layer to k −1 k-WL iterations and suggests variants based on allowed equality patterns.
4 Conclusion
- k-IGNs and k-WL are equally expressive in distinguishing graphs.Source: §4 · p. 16
- A single k-IGN layer corresponds to k −1 iterations of k-WL.Source: §4 · p. 17
- Restricting allowed equality patterns may yield less computationally intensive k-IGN variants, with k-WL and k-IGN as special cases.Source: §4 · p. 17