Rethinking the Expressive Power of GNNs via Graph Biconnectivity

• Existing MPNNs are bounded by 1-WL, while higher-order and enhanced architectures leave unclear what systematic, provable power they gain beyond the WL hierarchy.Higher-order methods incur severe computation and memory costs, and many alternatives rely mainly on toy distinguishing examples.Source: §1 · p. 1
• Graph biconnectivity offers intrinsic structural metrics with theoretical, practical, and linear-time computational significance, including cut vertices, cut edges, and biconnected components.These concepts relate to graph theory, molecular bond breakage, and social-network group connectivity, while classic algorithms solve them in graph-size complexity.Source: §1 · p. 2
• None of four representative GNN architecture classes can distinguish whether a graph has cut vertices or cut edges, so they also fail harder node-, edge-, and graph-level tasks.The harder tasks include identifying all cut vertices or edges and distinguishing graphs with non-isomorphic block cut trees.Source: §1 · p. 2
• For ESAN (Bevilacqua et al., 2022), DSS-WL with node marking precisely identifies both cut vertices and cut edges, whereas unmarked ego-networks and weaker DS-WL cannot identify cut vertices.This analysis also provides theoretical justification for DSS-WL and its extensions (Frasca et al., 2022).Source: §1 · p. 2
• GD-WL restores the missing distance information in 1-WL and is provably expressive for all biconnectivity problems; SPD-WL handles edge-biconnectivity, while RD-WL targets vertex-biconnectivity.SPD-WL still cannot identify cut vertices, motivating the resistance-distance variant.Source: §1 · pp. 2–3
• Graphormer-GD implements GD-WL with distance-injected multi-head attention, preserves its expressiveness, achieves perfect cut-vertex and cut-edge detection, and outperforms prior GNNs on benchmark datasets.Theoretical limits show SPD-WL and RD-WL are bounded by 2-FWL, while GD-WL matches 2-FWL on distance-regular graphs.Source: §1 · p. 3

Notations

• The paper studies simple undirected graphs using formal notation for vertices, edges, neighborhoods, degrees, paths, shortest-path distances, and induced subgraphs.These definitions fix the basic objects and notation used throughout the paper.Source: §2 · p. 3

Connectivity and biconnectivity

• Connectivity is characterized through connected components, while vertex- and edge-biconnectivity are defined using cut vertices, cut edges, and maximal biconnected components.A connected graph has one connected component; biconnected components cannot be enlarged while preserving the corresponding biconnectivity property.Source: §2 · pp. 3–4

Block-cut structures

• Pairs of nodes share a biconnected component when two paths connect them without sharing internal nodes or edges, and cut elements link components through block-cut trees.The vertex version uses internally disjoint paths, whereas the edge version uses edge-disjoint paths; paths across different components must pass through a cut element.Source: §2 · p. 4

Computational complexity

• All biconnectivity tasks—including finding cut vertices, cut edges, biconnected components, and block-cut trees—are solvable by depth-first search in Θ(|V| + |E|) time.This is the linear-time result attributed to Tarjan (1972).Source: §2 · p. 4

Isomorphism and problem setup

• Color refinement assigns isomorphism-invariant node colors whose multisets form graph representations, and the paper evaluates whether these representations distinguish biconnectivity properties and block-cut trees.The setup includes distinguishing vertex- or edge-biconnected graphs, identifying cut vertices or edges, and distinguishing non-isomorphic block-cut trees.Source: §2 · p. 4

3.1 COUNTEREXAMPLES

• Most investigated GNNs—including 1-WL/MPNNs, GSN, MPSN/CWN, GraphSNN, GNN-AK, and NGNN—are not expressive for any listed biconnectivity problem, whereas ESAN and variants handle both vertex- and edge-biconnectivity.The negative results cover arbitrary connected substructure sets for GSN and analogous variants, with counterexamples of O(n) vertices and edges; lifting-based SWL/CWL also fails.Source: §3 · p. 4, §3.1 · p. 5

3.2 PROVABLE EXPRESSIVENESS OF ESAN AND DSS-WL

• DSS-WL generates vertex-shared subgraphs and jointly aggregates within- and across-subgraph node colors, with policies including node deletion, node marking, and ego-networks.Its node-based graph generation associates each subgraph with a specific node; refinement continues until a stable vertex partition is reached.Source: §3.2 · p. 5
• DSS-WL with node marking preserves cut-vertex and cut-edge status across graphs with matching colors, proving ESAN’s expressiveness for both biconnectivity types.Theorem 3.2 states that equal DSS-WL colors imply equivalent cut-vertex status, and matching endpoint-color multisets imply equivalent cut-edge status.Source: §3.2 · p. 6
• DSS-WL’s crucial advantage is that its color mapping implicitly encodes distance information alongside biconnectivity information, which 1-WL lacks.Differences in nodes’ distance sets can produce different DSS-WL colors, supporting discrimination of edge- and vertex-biconnectivity.Source: §3.1 · p. 5, §3.2 · p. 6
• Node marking is stronger than fixed-radius ego-networks: πEGO(k) cannot distinguish cut vertices, while distance encoding lets GNN-AK+ avoid the analogous limitation.GNN-AK and GNN-AK-ctx remain unable to solve vertex-biconnectivity, whereas GNN-AK+ adds distance encoding and is more expressive than node marking.Source: §3.2 · p. 6
• Cross-subgraph aggregation is essential: DS-WL with common node-based policies cannot identify cut vertices, unlike DSS-WL’s interacting subgraph representations.A later DS-WL extension with final cross-graph aggregation may evade this negative result, but its expressiveness remains a future theoretical question.Source: §3.2 · p. 6

Computational cost

• GD-WL requires Θ(n) space and Θ(n^2) time per iteration, improving strictly over DSS-WL and matching 1-WL’s space complexity.Distance preprocessing is one-time, bounded by O(nm) for SPD and O(n^3) for RD, and is reported negligible relative to the GNN architecture.Source: §4 · pp. 6–8

SPD-WL for edge-biconnectivity

• SPD-WL, obtained from GD-WL using shortest-path distance, is strictly more powerful than 1-WL and fully expressive for edge-biconnectivity.It identifies cut edges and block cut-edge trees under the stated color-matching conditions.Source: §4 · p. 7

RD-WL for vertex-biconnectivity

• RD-WL uses effective resistance distance and is fully expressive for vertex-biconnectivity, identifying cut vertices and block cut-vertex trees.Unlike SPD-WL, RD-WL resolves vertex-biconnectivity problems that shortest-path distance alone cannot distinguish.Source: §4 · pp. 7–8

GD-WL framework

• GD-WL is fully expressive for both vertex-biconnectivity and edge-biconnectivity when combining shortest-path and resistance distances.This follows by combining SPD-WL’s edge-biconnectivity result with RD-WL’s vertex-biconnectivity result.Source: §4 · pp. 7–8

Practical implementation

• Graphormer-GD implements GD-WL with distance-informed multi-head attention and matches GD-WL expressivity using suitable functions, sufficient heads, and layers.It is never more powerful than GD-WL in distinguishing non-isomorphic graphs.Source: §4 · p. 8

Expressivity bounds and worst-case analysis

• The 2-FWL algorithm is more powerful than both SPD-WL and RD-WL, yet RD-WL matches 2-FWL on distance-regular graphs while strictly surpassing SPD-WL.Consequently, 2-FWL is fully expressive for both biconnectivity types, and RD-WL matches its distance-regular-graph power more efficiently.Source: §4 · pp. 8–9

5 EXPERIMENTS

• Graphormer-GD achieves 100% accuracy on both cut vertex and cut edge detection, whereas baseline GNNs cannot perfectly solve these synthetic tasks.SPD suffices for cut-edge identification, but RD is additionally necessary for cut-vertex identification, consistent with Theorems 4.1, 4.2 and 4.4.Source: Table 2 · p. 9, §5 · p. 9

Real-world tasks.

• On ZINC-Subset and ZINC-Full, Graphormer-GD surpasses or matches all competitive baselines on the test set under an approximately 500K-parameter budget.The reported score is averaged over four seeds, and Table 3 also reports ZINC-Subset per-epoch training time and model parameters.Source: Real-world tasks · pp. 9–10
• Graphormer-GD’s empirical performance aligns with biconnectivity expressivity: Subgraph GNNs outperform classic MPNNs, while Graphormer-GD is simpler, more parallelizable, and achieves better performance than Subgraph GNNs.The study also evaluates node-level tasks on Brazil-Airports and Europe-Airports, with results deferred to Appendix F.3.Source: Real-world tasks · p. 10

6 CONCLUSION

• GD-WL is fully expressive for all biconnectivity metrics, and Graphormer-GD is provably powerful, efficient, parallelizable, and effective on synthetic and real-world datasets.These contributions provide theoretical and practical advances over the expressive-power limitations identified for existing GNNs.Source: §6 · p. 10
• Open problems include subquadratic equivariant solutions, deeper understanding of GD-WL, more expressive distance encodings, and higher-order connectivity such as tri-connectivity.The paper specifically conjectures that RD-WL encodes graph spectral information and is strictly more powerful than SPD-WL on general graphs.Source: §6 · p. 10

A RECENT ADVANCES IN EXPRESSIVE GNNS

• Expressive GNN research includes higher-order, substructure-based, subgraph, non-equivariant, local-structure, distance-encoding, spectral, and higher-order-subgraph approaches.Higher-order methods improve expressiveness through k-tuple features but incur substantial computational cost, while localized variants trade some expressiveness for efficiency.Source: A RECENT ADVANCES IN EXPRESSIVE GNNS · p. 18
• Subgraph GNNs preserve equivariance by symmetrically generating subgraphs and aggregating their outputs, with ESAN providing per-layer aggregation and stronger expressiveness.Related policies include node deletion, edge deletion, node marking, and ego-networks; later work bounds one extension by 3-WL.Source: A RECENT ADVANCES IN EXPRESSIVE GNNS · p. 18

B THE WEISFEILER-LEHMAN ALGORITHMS AND RECENTLY PROPOSED VARIANTS

• The appendix introduces 1-WL, k-FWL, SC-WL, OS-WL, DSS-WL, and GD-WL as the principal Weisfeiler-Lehman algorithms and variants studied.The algorithms use an injective hash over colors, multisets, tuples, and related objects.Source: B THE WEISFEILER-LEHMAN ALGORITHMS AND… · p. 19

B.1 1-WL TEST

• 1-WL repeatedly hashes each vertex’s current color together with its neighborhood color multiset, producing a stable partition and node or graph representations.It can certify non-isomorphism when graph color multisets differ, but fails on some non-isomorphic graphs with identical representations.Source: §B.1 · p. 19, §5 · p. 19

B.2 k-FWL TEST

• k-FWL colors ordered k-tuples using induced-subgraph structure and iteratively aggregates colors of tuples differing in one coordinate.Its tuple partition stabilizes after finitely many iterations, analogously to 1-WL.Source: §B.2 · p. 20, §6 · p. 20

6 Return: χT

• k-FWL is strictly more powerful than 1-WL, and (k + 1)-FWL is strictly more powerful than k-FWL for every k ≥2.Diagonal tuple colors also yield vertex representations whose partitions refine those induced by lower-order WL tests.Source: §6 · p. 20

B.3 WL WITH SUBSTRUCTURE COUNTING (SC-WL)

• SC-WL augments 1-WL with counts of selected small connected subgraphs, including cycles and cliques, measured per vertex and automorphism orbit before message passing.The resulting orbit- and structure-specific counts are concatenated into vertex features and incorporated into the update rule; edge features can be treated analogously.Source: §B.3 · p. 21

B.4 EQUIVARIANT SUBGRAPH AGGREGATION WL (DSS-WL)

• DSS-WL jointly refines colors across a permutation-equivariant bag of graphs sharing vertices but differing in edges, with node-marking, node-deletion, and ego-network policies as examples.Its policies must preserve symmetry under vertex permutations, and the resulting DSS-WL algorithm is strictly more powerful than classic 1-WL; node marking is at least as powerful as node deletion.Source: §B.4 · p. 21, §8 · p. 22

8 Return: χT

• DSS-WL’s graph policies include node marking, which isolates a distinguished node through its initial color, and node deletion, which removes all incident edges to isolate it.The ego-network policy instead retains edges among nodes within k hops of the distinguished vertex and isolates other nodes; a marked ego variant is also possible.Source: §B.4 · p. 21, §8 · p. 22

B.5 GENERALIZED DISTANCE WL (GD-WL)

• GD-WL generalizes distance-based color refinement by taking a graph and distance metric as input, with SPD-WL as the special case d_G = dis_G, which is strictly more powerful than 1-WL.The algorithm initializes every vertex with a common color and iteratively returns a vertex color mapping.Source: §B.5 · p. 22

C PROOF OF THEOREMS

• The paper’s proof section restates theorems and supplies missing proofs for the proposed color-refinement results.These proofs use the WL-condition as a common framework for comparing color mappings produced on one or two graphs.Source: C PROOF OF THEOREMS · p. 23, §C.1 · p. 23

C.1 PROPERTIES OF COLOR REFINEMENT ALGORITHMS

• DSS-WL, SPD-WL, and k-FWL satisfy the WL-condition, which requires equal-colored vertices to have matching counts of neighbors in every color class.For DSS-WL, the property follows from both within-subgraph aggregation and aggregation across the generated graph bag; SPD-WL and k-FWL satisfy it as well.Source: §C.1 · p. 23
• The WL-condition guarantees that any colored path in one graph can be matched by a path of the same length and corresponding colors from any equally colored starting vertex in another graph.This path-preservation lemma is then used to derive statements about shortest-path distances from equally colored vertices to color classes.Source: §C.1 · p. 24

Counterexample families

• Examples C.9 and C.10 give graph pairs with differing cut-vertex and cut-edge structures: in C.9, G1 lacks cut vertices while G2 has one, and in C.10 structures differ.In Example C.9, when k = 1, G2 has three cut vertices and two cut edges. In Example C.10, G1 has neither cut vertices nor cut edges, whereas G2 has two cut vertices and one cut edge.Source: §C.2 · p. 25

SC-WL

• SC-WL with any fixed connected substructure set cannot distinguish cut vertices or cut edges, even though counterexamples have O(nV) vertices and edges.The proof reduces relevant substructures to trees smaller than the cycle lengths and constructs bijections preserving rooted induced-subgraph orbits; classic 1-WL colors also coincide.Source: §C.2 · pp. 25–26

Simplicial and Cellular WL

• SWL and CWL with k-CL, k-IC, or k-C cannot distinguish cut vertices or cut edges; for k-IC, failure persists even when k scales with graph size.For k-IC or k-C, counterexamples of size O(k) suffice when m > k, while Example C.9 still defeats CWL with IC for k ≥ 2 because corresponding 2-cells receive identical colors.Source: §C.2 · p. 26

Overlap Subgraph WL

• Overlap Subgraph WL cannot detect cut vertices or cut edges for any subgraph mapping, because triangle-free counterexamples reduce its overlap subgraphs to single edges and hence to 1-WL.Example C.9 applies for m > 1 and Example C.10 for m > 3; Example C.9 with m = 1 also remains a counterexample.Source: §C.2 · p. 26

DSS-WL

• DSS-WL with an unmarked ego-network policy cannot distinguish Example C.9 with m = 1, since both radius policies yield identical stable color mappings.At radius 2, all ego graphs equal the original graph; at radius 1, non-special ego graphs are isomorphic and the resulting partition stabilizes identically.Source: §C.2 · p. 27

GNN-AK

• GNN-AK cannot distinguish whether a graph has cut vertices because centroid encoding is added after, rather than before, the WL procedure.This makes GNN-AK weaker than the corresponding DSS-WL construction on the two counterexample graphs.Source: §C.2 · p. 27

DS-WL and NGNN

• DS-WL with node marking/deletion and associated-subgraph node colors cannot distinguish cut vertices, and NGNN with shortest-path distance encoding likewise fails.For Example C.9 with m = 1, DS-WL assigns the special node n the same color in both graphs; the paper reports an analogous failure for NGNN.Source: §C.2 · p. 27

C.3 PROOF OF THEOREM 3.2

• Matching DSS-WL node colors imply that corresponding nodes are cut vertices simultaneously, and matching endpoint-color multisets imply that corresponding edges are cut edges simultaneously.These are the two claims stated in Theorem C.17.Source: §C.3 · p. 27
• DSS-WL color agreement preserves the connected component containing each matched node, allowing the proof to restrict attention to connected induced components.Lemma C.18 establishes component-local color agreement, and cut-vertex status is unchanged when restricting to the relevant component.Source: §C.3 · p. 28
• For connected graphs, the proof derives that matched DSS-WL colors preserve distances between marked nodes and corresponding nodes.Lemma C.19 supplies distance preservation and related properties of the DSS-WL color mappings.Source: §C.3 · p. 28

C.3.1 PROOF FOR THE FIRST PART OF THEOREM 3.2

• The first-part proof uses induction over hop distance to show that marked-node color multisets at every distance match across graphs.Lemma C.20 establishes the distance-layer multiset invariant, which supports the subsequent cut-vertex argument.Source: §C.3.1 · p. 29
• For a cut vertex, removing it partitions the graph into components, and DSS-WL color and path correspondences yield contradictions if a same-colored counterpart were not also a cut vertex.The argument handles both the case where a color class spans components and the case where it is concentrated in one component.Source: §C.3.1 · pp. 29–30
• The reverse direction transfers the same component-separation and path-correspondence argument from G to H, completing the cut-vertex equivalence.The proof uses matched color-class sizes and WL-condition path lifting to derive contradictions in H.Source: §C.3.1 · pp. 30–31

C.3.2 PROOF FOR THE SECOND PART OF THEOREM 3.2

• The second-part proof shows that equal DSS-WL colors induce identical multisets of distance-color pairs, making the DSS-WL vertex partition finer than the SPD-WL partition and enabling Theorem 4.1.Corollary C.24 provides the multiset equality, while Proposition C.56 completes the invocation of Theorem 4.1.Source: §C.3.2 · p. 31

C.4 PROOF OF THEOREM 4.1

• Theorem C.25 shows that matching SPD-WL color pairs preserve whether corresponding edges are cut edges, while identical graph representations imply isomorphic block cut-edge trees.The proof treats connected graphs with equal representations first, then extends the result to disconnected graphs and unequal representations in Appendix C.4.3.Source: §C.4 · p. 32

C.4.1 THE CASE OF χG(u)̸ = χG(v) FOR CONNECTED GRAPHS

• For connected graphs with χG(u) ≠ χG(v), the proof defines a color graph and uses SPD-WL distance constraints to show that the corresponding color-pair edge is a cut edge, forcing matching graph edges to be cut edges.The argument partitions the graph by removing the edge, derives structural constraints on color classes and paths, and obtains contradictions from SPD-WL distance information when the edge is assumed non-cut.Source: §C.4.1 · pp. 32, 34, 35
• For connected graphs with χG(u) ≠ χG(v), distance equalities and color-path constraints force a cut edge, with alternative configurations yielding contradictions.The argument uses two same-colored nodes at prescribed distances and shows that otherwise distance differences or path structure contradict the assumed coloring correspondence.Source: §C.4.1 · pp. 36–37

C.4.2 THE CASE OF χG(u) = χG(v) FOR CONNECTED GRAPHS

• For χG(u) = χG(v), the proof constructs an auxiliary graph whose cross-part edge is unique and a cut edge, then derives matching distance and neighborhood-multiset relations.The mapping fG is surjective; the auxiliary graph supports distance correspondences, and the resulting relations show that the corresponding edge {u, v} is also a cut edge in H.Source: §C.4.2 · pp. 37–39

C.4.3 THE GENERAL CASE

• Matching SPD-WL-colored edges preserve cut-edge status, including in disconnected graphs by restricting to corresponding largest connected components.The connected case follows from the preceding proofs; for disconnected graphs, induced largest components have matching sizes and color multisets, allowing the same argument.Source: §C.4.3 · p. 40
• The general proof establishes that equal stable GD-WL color multisets imply isomorphic block cut-edge trees, extending the connected argument to disconnected graphs.Each cut edge corresponds to a tree edge and each biconnected component to a tree node; the disconnected extension uses the same component-wise technique.Source: §C.4.3 · p. 40
• The proof reduces BCETree reconstruction to determining the multiset of vertex colors in one component of a cut edge from R and its endpoint edge color.Once this multiset is known, leaf edges and their connections can be identified recursively until the full BCETree is constructed.Source: §C.4.3 · p. 41
• For cut-edge colors cu and cv, the construction uses the well-defined distance-based quantity D(c1, c2), which is independent of the selected vertex.The definition applies to arbitrary cut edges with the same endpoint colors, allowing the resulting multiset to depend only on those colors and R.Source: §C.4.3 · p. 41
• The multiset T(cu, cv) exactly equals the colors of nodes lying on the u-side of the cut edge, completing the general-case proof.Its characterization uses the condition disG(u, w) + 1 = disG(v, w) and the color restriction χG(w) ∈ CV.Source: §C.4.3 · p. 41

Theorem 4.2

• RD-WL assigns the same color to nodes only when they agree on whether they are cut vertices.For w ∈ V in G and x ∈ V in H, χG(w) = χH(x) implies that w is a cut vertex of G if and only if x is a cut vertex of H.Source: §C.5 · p. 41
• Identical RD-WL graph representations guarantee that the block cut-vertex trees of G and H are isomorphic.The condition {{χG(w) : w ∈ V}} = {{χH(w) : w ∈ V}} implies BCVTree(G) ≃ BCVTree(H).Source: §C.5 · p. 41

Proof Sketch

• The proof uses Lemma C.43 for general distances, restricts attention to connected graphs, and handles the two theorem claims in separate appendices.The first claim is proved in Appendix C.5.1 and the second in Appendix C.5.2, assuming connected graphs with identical graph representations.Source: §C.5 · p. 41

C.5.1 PROOF OF THE FIRST PART

• Resistance Distance identifies cut vertices: v is a cut vertex exactly when some distinct u,w satisfy the corresponding resistance-distance equality through v.This is Lemma C.45, proved by relating Resistance Distance to Commute Time Distance and average random-walk hitting times.Source: §C.5.1 · pp. 41–42
• When v is a cut vertex, paths between nodes in different components after removing v pass through v, making the relevant hitting-time equalities hold exactly.The proof uses this path decomposition to obtain equalities in both directions of the commute time.Source: §C.5.1 · p. 42
• The cut-vertex characterization yields distinct RD-WL colors for nodes occupying incompatible component positions around a cut vertex.The argument explicitly concludes that u and u_i cannot have the same RD-WL color, and later derives a corresponding cut-vertex conclusion for u′.Source: §C.5.1 · pp. 42–43
• Applying the same argument to color-preserving node correspondences transfers cut-vertex status between the compared graphs and proves the first bullet of Theorem 4.2.The proof considers corresponding color classes, derives a resistance-distance relation, and concludes that the matched node is a cut vertex.Source: §C.5.1 · p. 43

C.5.2 PROOF OF THE SECOND PART

• The proof represents components avoiding a cut vertex’s color using an index set whose size is either mG(u)−1 or mG(u), enabling the two-case correspondence argument.This classification is the starting point for matching component color multisets and completing Corollary C.51.Source: §C.5.2 · p. 43
• For corresponding cut vertices, component membership controls relative distances: matched components preserve distances, while mismatched components yield a strict distance inequality.These relations prevent incompatible component-color configurations and establish the correspondence used by Corollary C.49.Source: §C.5.2 · pp. 43–44
• Vertices with the same RD-WL color have equal numbers of connected components after removal, and their corresponding component color multisets match.Corollary C.51 derives this from Lemma C.48 and Corollary C.49, including the cases where components contain or do not contain vertices of the removed vertex’s color.Source: §C.5.2 · pp. 44–45
• Equal RD-WL color multisets imply BCVTree(G) ≃ BCVTree(H), because cut vertices, biconnected components, and their incidences can be reconstructed solely from the representation.The construction recursively identifies leaf cut-vertex nodes and removes them until the full block cut-vertex tree is determined.Source: §C.5.2 · pp. 45–46

C.6 PROOF OF THEOREM 4.5

• 2-FWL-equivalent node pairs have equal graph distances and resistance distances, via preserved path counts and hitting-path degree sequences.The argument proceeds through an induction showing equality of path counts and hitting-path degree tuples at every iteration.Source: §C.6 · pp. 47–48
• The 2-FWL vertex partition is finer than both SPD-WL and RD-WL, so 2-FWL is more powerful than each algorithm.The proof derives equal distance- and vertex-color multisets from equal 2-FWL colors, then applies the partition comparison.Source: §C.6 · p. 48
• Any refinement that is at least as fine as another color refinement inherits its ability to distinguish cut vertices, cut edges, and BCVTree(G)/BCETree(G) isomorphism types.This proposition transfers distinguishability guarantees from a coarser vertex partition to a finer one.Source: §C.6 · p. 48

C.7 PROOF OF THEOREM 4.7

• For connected distance-regular graphs, SPD-WL distinguishes graphs exactly when their k-hop-neighbor arrays κ(G) differ.Thus equal κ(G) places the graphs in the same SPD-WL equivalence class.Source: §C.7 · p. 49
• For connected distance-regular graphs, RD-WL and 2-FWL distinguish graphs exactly when their intersection arrays ι(G) differ.Both algorithms therefore have the same distinguishing criterion on this graph class.Source: §C.7 · p. 49
• Because equal intersection arrays imply equal k-hop-neighbor arrays, RD-WL is strictly more powerful than SPD-WL but equally powerful to 2-FWL on non-isomorphic distance-regular graphs.The strictness follows from the characterization of the two algorithms’ equivalence classes.Source: §C.7 · p. 49
• The Dodecahedron and Desargues graph share κ(G)=(3, 6, 6, 3, 1) but have different intersection arrays, whereas the 4x4 rook’s and Shrikhande graphs share {6, 3; 1, 2}.Consequently, SPD-WL fails on the first pair while RD-WL succeeds, and both RD-WL and 2-FWL fail on the second pair.Source: §C.7 · p. 49

C.7.1 PROOF OF THEOREM C.58

• SPD-WL distinguishes graphs with different k-hop-neighbor arrays and cannot distinguish graphs with identical k-hop-neighbor arrays.After the first iteration, node colors encode the sizes of all distance-neighborhoods; identical arrays preserve matching colors through every iteration.Source: §C.7.1 · pp. 49–50
• In a connected distance-regular graph, resistance distance between two nodes depends only on their shortest-path distance and is recursively determined by the intersection array.The proof represents the resistance-distance matrix through the Laplacian pseudoinverse and verifies the required matrix identity by separating equal, nonmaximal, and maximal graph distances.Source: §C.7.1 · pp. 50–51
• Equal intersection arrays imply equal resistance-distance multisets and therefore identical RD-WL colors at every iteration.Theorem C.61 supplies the resistance-distance values and multiplicities needed to preserve the color mapping across iterations.Source: §C.7.1 · p. 51
• Different intersection arrays yield a first index where either a resistance distance or its multiplicity differs, allowing RD-WL to distinguish the graphs immediately.The argument compares the multisets of resistance distances repeated according to the k-hop-neighbor array.Source: §C.7.1 · p. 51
• RD-WL cannot distinguish distance-regular graphs with the same intersection array, but distinguishes graphs whose intersection arrays differ.The proof uses the strict ordering of recursively defined resistance distances and their multiplicities to show that differing intersection arrays produce different first-iteration color multisets.Source: §C.7.1 · p. 51
• 2-FWL distinguishes graphs with different intersection arrays, while identical intersection arrays prevent distinction because equal graph distances induce equal two-step distance-pair multisets.The equal-distance invariant is proved inductively using Lemma C.60 and the 2-FWL update rule.Source: §C.7.1 · pp. 51–52

D.1 KNOWN METRICS FOR MEASURING THE EXPRESSIVE POWER OF GNNS

• Biconnectivity is a basic, practically meaningful property computable in linear graph size, unlike higher-order WL and many structural metrics whose efficient computation is difficult.2-FWL requires Ω(n^3) time and Θ(n^2) space, while prior structural tasks require super-linear complexity and often costly precomputation.Source: §D.1 · p. 52

D.2 GNNS WITH DISTANCE ENCODING

• GD-WL provides a principled framework that includes SPD-WL as a special case and theoretically generalizes prior distance-based approaches.Prior work used distance encodings, subgraph GNNs, Transformers, or k-hop aggregation, but formal analyses were often restricted to regular graphs.Source: §D.2 · p. 53
• The paper systematically analyzes SPD-WL on general graphs and identifies its fundamental advantage in distinguishing edge-biconnectivity.The resulting Transformer-based GNN is provably as expressive as GD-WL and is intended for empirical implementation on real-world tasks.Source: §D.2 · p. 53

E IMPLEMENTATION OF GENERALIZED DISTANCE WEISFEILER-LEHMAN

• The GD-WL implementation section presents the architecture together with a detailed analysis of its computational complexity for graphs with n vertices and m edges.The section assumes an input graph G = (V, E) with n vertices and m edges.Source: E IMPLEMENTATION OF GENERALIZED… · p. 53

E.1 PREPROCESSING SHORTEST PATH DISTANCE

• Shortest-path distances require Θ(n^3) time with Floyd–Warshall, or Θ(nm) time using breadth-first search on sparse graphs.The sparse-graph setting is described as m = o(n^2).Source: §E.1 · p. 53

E.2 PREPROCESSING RESISTANCE DISTANCE

• Resistance distance equals commute-time distance and is a valid graph metric; it never exceeds shortest-path distance while providing finer-grained rational values.For fixed n, resistance distance has finitely many possible values, lies in the same range as shortest-path distance, and is not restricted to integers.Source: §E.2 · p. 54
• Resistance distance can be computed in O(n^3) time, while achieving an m-dependent sparse-graph complexity remains conjectural and is left as an open problem.The paper suggests that Sherman–Morrison–Woodbury-style updates might yield O(nm) time, but does not establish this bound.Source: §E.2 · p. 55

E.3 TRANSFORMER-BASED IMPLEMENTATION

• Graphormer-GD modifies Graphormer self-attention to encode graph distances, enabling Transformer blocks to capture structural information absent from standard attention.The model uses Transformer self-attention followed by feed-forward layers with normalization and skip connections.Source: §E.3 · p. 56
• The implementation combines shortest-path and resistance-distance encodings, using learnable distance scalars for shortest paths and Gaussian Basis kernels with an MLP for resistance distances.Disconnected node pairs receive a special learnable shortest-path scalar, and node degrees are incorporated through degree embeddings.Source: §E.3 · p. 56
• With proper distance functions and sufficiently many attention heads and layers, Graphormer-GD is as powerful as GD-WL, while never exceeding GD-WL’s expressiveness.The result holds under the theorem’s stated choice of functions and capacity assumptions.Source: §E.3 · p. 56
• Graphormer-GD simulates GD-WL by assigning attention heads to distance configurations and injectively aggregating node representations within each configuration.Multi-head concatenation preserves the tuple of distance-conditioned multisets, and sufficient layers reproduce GD-WL updates.Source: §E.3 · p. 57

F.1 SYNTHETIC TASKS

• Synthetic evaluation uses three families of hard graphs, including regular graphs with cut vertices and cut edges, with graph-level accuracy requiring every target vertex or edge to be identified exactly.Graphs contain at most 120 nodes; results average accuracy over five random seeds.Source: §F.1 · p. 57
• The synthetic comparisons include GCN, GAT, GIN, Graph Substructure Network, and Graphormer, spanning models with different known expressive-power levels.The classic MPNNs are characterized as at most 1-WL powerful, while Graph Substructure Network and Graphormer provide stronger comparison points.Source: §F.1 · p. 58
• Experiments train a 6-layer Graphormer-GD with 768-dimensional hidden and feed-forward layers, 128 Gaussian Basis kernels, and 64 attention heads for 100k steps.Training uses AdamW, a peak learning rate of 9e-5, 6k warm-up steps, linear decay, batch size 32, and one NVIDIA Tesla V100 GPU.Source: §F.1 · p. 58

F.2 REAL-WORLD TASKS

• Graphormer-GD is evaluated on ZINC-Full and ZINC-Subset for constrained molecular solubility prediction, using 250K molecular graphs in the full dataset.The ZINC-Subset contains 12K selected graphs, and comparisons use approximately 500K parameters across MPNNs, higher-order, substructure-based, subgraph, and Transformer GNNs.Source: §F.2 · p. 58

F.3 MORE TASKS

• The airport experiments compare Graphormer-GD with GCN, GraphSAGE, GIN, Struc2vec, and distance-encoding GNNs.Graphormer-GD uses hidden and feed-forward dimensions of 80, 128 Gaussian Basis kernels, and 8 attention heads, with the number of layers selected from [3, 6].Source: §F.3 · p. 59
• Graphormer-GD outperforms the selected baselines on both Brazil-Airports and Europe-Airports node-classification datasets, despite slightly larger variance on the small graphs.Results average accuracy over 20 random seeds; Table 5 reports the comparisons across the two datasets.Source: §F.3 · p. 59, Table 5 · p. 60

F.4 EFFICIENCY EVALUATION

• Efficiency is profiled on ZINC-Subset using matched batch size 128 and a 16GB NVIDIA Tesla V100 GPU, with publicly available baseline implementations.Graphormer-GD uses 12 layers, hidden dimension 80, and 8 attention heads; Table 6 reports time per training epoch and model parameters.Source: §F.4 · pp. 59–60, Table 6 · p. 60
• Graphormer-GD has per-epoch efficiency in the same order of magnitude as classic MPNNs despite Θ(n^2) rather than Θ(n + m) computation complexity.The result is attributed to the high parallelizability of Transformer layers and is reported with time per training epoch and parameter counts in Table 6.Source: §F.4 · p. 60, Table 6 · p. 60
• Graphormer-GD is much more efficient than higher-order GNNs and almost as efficient as the original Graphormer.The added Resistance Distance encoding requires negligible additional time compared with the full architecture.Source: §F.4 · p. 60