Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 3 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 3 also cleared it.

Message-passing GNNs and the 1-WL ceiling — Examples

1 · Prerequisites

Message-passing GNNs and the 1-WL ceiling

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

A six-cycle and two disjoint triangles are regular but one-WL-indistinguishable

Example

Let $G$ have vertices $0, 1, 2, 3, 4, 5$ , edges ${{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0}}$ , and the same initial label $⋆$ at every vertex. Let $H$ have vertices $a_{0}, a_{1}, a_{2}, b_{0}, b_{1}, b_{2}$ , edges ${{a_{0}, a_{1}}, {a_{1}, a_{2}}, {a_{2}, a_{0}}, {b_{0}, b_{1}}, {b_{1}, b_{2}}, {b_{2}, b_{0}}}$ , and the same initial label $⋆$ at every vertex. Both graphs are 2-regular. Every pair of vertices in $G$ can be joined by a finite edge path, whereas no edge path joins a vertex among $a_{0}, a_{1}, a_{2}$ to a vertex among $b_{0}, b_{1}, b_{2}$ in $H$ . The graphs are nonisomorphic, yet one-dimensional Weisfeiler–Leman color refinement gives the same graph color multiset at every finite round.

Example references

finite graphs and neighborhoods

label-preserving graph isomorphisms

finite multisets

one-dimensional color refinement

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §2 and §4

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.4.1

Morris et al., “Weisfeiler and Leman Go Neural,” §3

Diagram

The left component draws the six vertices and six cyclic edges of $G$ . The right component draws the two separate three-vertex cycles of $H$ ; no edge joins those cycles. The vertex names are shown, and every vertex has label $⋆$ . The verification below uses the listed edge sets and does not rely on the drawing.

diagram failed to render:
\begin{tikzpicture}[scale=0.9]
\node[draw,circle,inner sep=2pt] (v0) at (0,1.4) {$0$};
\node[draw,circle,inner sep=2pt] (v1) at (1.2,2.1) {$1$};
\node[draw,circle,inner sep=2pt] (v2) at (2.4,1.4) {$2$};
\node[draw,circle,inner sep=2pt] (v3) at (2.4,0) {$3$};
\node[draw,circle,inner sep=2pt] (v4) at (1.2,-0.7) {$4$};
\node[draw,circle,inner sep=2pt] (v5) at (0,0) {$5$};
\draw (v0)--(v1)--(v2)--(v3)--(v4)--(v5)--(v0);
\node at (1.2,-1.35) {$G$};
\begin{scope}[xshift=5.5cm]
\node[draw,circle,inner sep=2pt] (a0) at (0,1.1) {$a_0$};
\node[draw,circle,inner sep=2pt] (a1) at (1,1.1) {$a_1$};
\node[draw,circle,inner sep=2pt] (a2) at (0.5,2) {$a_2$};
\draw (a0)--(a1)--(a2)--(a0);
\node[draw,circle,inner sep=2pt] (b0) at (2.5,1.1) {$b_0$};
\node[draw,circle,inner sep=2pt] (b1) at (3.5,1.1) {$b_1$};
\node[draw,circle,inner sep=2pt] (b2) at (3,2) {$b_2$};
\draw (b0)--(b1)--(b2)--(b0);
\node at (1.75,0.25) {$H$};
\end{scope}
\end{tikzpicture}

Facts & Assumptions

Given: The two graphs and their uniform initial labels in the Example. Verify regularity, nonisomorphism, and one-WL indistinguishability.

[F1]

Finite simple undirected graphs with vertex labels: A vertex neighborhood consists exactly of vertices joined to it by an edge.

[F2]

Label-preserving graph isomorphisms: A graph isomorphism is a bijection preserving adjacency in both directions.

[F3]

Finite-round one-dimensional Weisfeiler–Leman color refinement: The next color is the ordered pair of the current color and the multiset of current neighbor colors.

[F4]

Finite multisets as finitely supported multiplicity functions: A finite multiset records every element with its multiplicity.

Verification

1.1givenF1algebra

In $G$ , vertex $i$ has the two distinct neighbors $i - 1$ and $i + 1$ modulo $6$ . In $H$ , each vertex has the other two vertices of its own triangle as neighbors. Thus every vertex in each graph has degree $2$ .

1.2givenF3F4inductionalgebra

At round $0$ , all vertices of both graphs have color $⋆$ . If every vertex in both graphs has a common color $c_{t}$ at round $t$ , then each vertex has the neighbor-color multiset with exactly two copies of $c_{t}$ . The update [F3] therefore assigns the same ordered-pair color to every vertex in both graphs at round $t + 1$ . By induction, each graph has six copies of the same color at every round, so their color multisets agree and 1-WL never distinguishes them.

2.1givenF2algebra∎

Suppose an isomorphism $φ : G \to H$ existed. Choose one vertex from each of the two triangles of $H$ and take their preimages under the surjection $φ$ . In $G$ a finite sequence of cyclically consecutive vertices joins those preimages. Applying $φ$ to that sequence gives an edge path in $H$ by [F2], but $H$ has no edge between its triangles and hence no such path. This contradiction proves nonisomorphism.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

Mean and max aggregation can lose multiset multiplicity

Example

Let $d \geq 1$ and $x \in R^{d}$ . For a nonempty finite multiset $S$ of vectors, define its mean as $∣ S ∣^{- 1} \sum_{y \in S} y$ and its coordinatewise maximum to have $j$ -th coordinate $\max_{y \in S} y_{j}$ . The distinct multisets $S_{1} = {⁣ {x} ⁣}$ and $S_{2} = {⁣ {x, x} ⁣}$ have the same mean $x$ and the same coordinatewise maximum $x$ . Thus both mean aggregation and coordinatewise max aggregation can identify different multisets when multiplicities differ.

Example references

finite multisets and multiplicities

neighbor aggregation as a function on multisets

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §5.2 and Appendices G–H

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.4

Facts & Assumptions

Given: $d \geq 1$ , a vector $x \in R^{d}$ , and the two finite multisets in the Example. Verify their inequality and aggregator outputs.

[F1]

Finite multisets as finitely supported multiplicity functions: Multiset equality requires equality of each element's multiplicity, and size is total multiplicity.

Verification

1.1givenF1algebra

The multiplicity of $x$ is $1$ in $S_{1}$ and $2$ in $S_{2}$ , so $S_{1} \neq S_{2}$ by [F1].

2.1givenstep 1.1algebra∎

The sums are $x$ and $2 x$ , with sizes $1$ and $2$ , so both means equal $x$ . In each coordinate, the maximum of one copy of $x_{j}$ and the maximum of two equal copies of $x_{j}$ are both $x_{j}$ . Thus both aggregators return the same value on the distinct multisets.

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passjudge pass (gpt-6-luna)Open item page →

An irrational GIN self-weight separates two bounded color neighborhoods

Example

Let the countable feature set be $X = {r, b}$ with code $ϕ (r) = 1$ , $ϕ (b) = 2$ , the base- $2$ code $ϕ (x) = 2^{ν (x)}$ for $ν (r) = 0, ν (b) = 1$ . Set the GIN self-weight parameter to $ε = \sqrt{2}$ . On a center feature $c$ and a one-neighbor multiset $S$ , the scalar preactivation is $J_{ε} (c, S) = (1 + ε) ϕ (c) + \sum_{x \in S} ϕ (x)$ . For the distinct center/neighbor pairs $(r, {⁣ {b} ⁣})$ and $(b, {⁣ {r} ⁣})$ , the preactivations are $3 + \sqrt{2}$ and $3 + 2 \sqrt{2}$ , respectively, so this GIN sum code separates the pair under the size bound $∣ S ∣ \leq 1$ .

Example references

finite multisets and their sizes

the GIN sum preactivation

the countable bounded-multiset encoding theorem

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §4.1 and Corollary 6

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.4

Facts & Assumptions

Given: The two feature values, code, and center/neighbor pairs in the Example. Verify the irrationality condition and the two preactivation values.

[F1]

Finite multisets as finitely supported multiplicity functions: A multiset records each feature with its number of occurrences.

[F2]

Graph Isomorphism Network update rule: A GIN preactivation is $(1 + ε) h_{v} + \sum_{u \in N (v)} h_{u}$ before the layer MLP.

[F3]

Countable bounded multisets admit injective sum encodings: For countable features and bounded neighbor-multiset size, an irrational self-weight makes the coded center/multiset sum injective.

Verification

1.1givenalgebracontradiction

The number $\sqrt{2}$ is irrational: if $\sqrt{2} = p / q$ for coprime positive integers $p, q$ , then $p^{2} = 2 q^{2}$ makes $p$ even, say $p = 2 s$ , and substitution gives $q^{2} = 2 s^{2}$ , so $q$ is even as well, contradicting coprimality.

2.1givenF1F2step 1.1algebra

By [F2], $J_{\sqrt{2}} (r, {⁣ {b} ⁣}) = (1 + \sqrt{2}) \cdot 1 + 2 = 3 + \sqrt{2}$ , while $J_{\sqrt{2}} (b, {⁣ {r} ⁣}) = (1 + \sqrt{2}) \cdot 2 + 1 = 3 + 2 \sqrt{2}$ . Their difference is $\sqrt{2} \neq 0$ , so the distinct pairs have distinct preactivations.

3.1givenF1F3step 1.1step 2.1algebra∎

The feature set has two elements and both neighbor multisets have size one. Thus the example meets the countability and bound hypotheses of [F3], with irrational $ε$ established in step 1.1; the computed separation is a concrete instance of that injective coding condition.

Message-passing GNNs and the 1-WL ceiling — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

A six-cycle and two disjoint triangles are regular but one-WL-indistinguishable

Example

Example references

Diagram

Facts & Assumptions

Verification

Mean and max aggregation can lose multiset multiplicity

Example

Example references

Facts & Assumptions

Verification

An irrational GIN self-weight separates two bounded color neighborhoods

Example

Example references

Facts & Assumptions

Verification

Sources