PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking the Expressive Power of GNNs via Graph Biconnectivity

Bohang Zhang, Shengjie Luo, Liwei Wang, Di He

arXiv:2301.09505v3cs.LGstat.ML

TL;DR

The paper addresses the lack of principled expressivity measures for GNNs beyond WL by using graph biconnectivity. It introduces GD-WL and its Graphormer-GD implementation, showing provable coverage of biconnectivity problems and strong performance, while identifying scope limitations in weaker related frameworks.

  • Problem

    Principled metrics beyond the WL hierarchy remain lacking, despite extensive work on more expressive GNNs and concerns about their computational cost and necessity.

  • Method

    The paper introduces GD-WL, which encodes distance information into WL aggregation, and implements it as the parallelizable Graphormer-GD architecture.

  • Results

    Existing representative GNNs fail basic biconnectivity distinctions, whereas GD-WL is provably expressive for all biconnectivity metrics and Graphormer-GD achieves 100% accuracy on both synthetic tasks.

  • Takeaways & Limitations

    Graph biconnectivity provides a systematic lens for GNN expressivity, and distance-aware GD-WL offers an efficient, expressive alternative supported by synthetic and real-world experiments.

  • Takeaways & Limitations

    The weaker DS-WL variant cannot identify cut vertices with common node-based policies, although extensions adding final cross-graph aggregation may avoid this negative result.

Abstract

from arXiv · show

Designing expressive Graph Neural Networks (GNNs) is a central topic in learning graph-structured data. While numerous approaches have been proposed to improve GNNs in terms of the Weisfeiler-Lehman (WL) test, generally there is still a lack of deep understanding of what additional power they can systematically and provably gain. In this paper, we take a fundamentally different perspective to study the expressive power of GNNs beyond the WL test. Specifically, we introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. As biconnectivity can be easily calculated using simple algorithms that have linear computational costs, it is natural to expect that popular GNNs can learn it easily as well. However, after a thorough review of prior GNN architectures, we surprisingly find that most of them are not expressive for any of these metrics. The only exception is the ESAN framework, for which we give a theoretical justification of its power. We proceed to introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL), which is provably expressive for all biconnectivity metrics. Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves expressiveness and enjoys full parallelizability. A set of experiments on both synthetic and real datasets demonstrates that our approach can consistently outperform prior GNN architectures.

1 INTRODUCTION

The paper argues that existing GNN expressivity lacks principled metrics beyond WL and studies graph biconnectivity as such a lens. It proves limitations of representative architectures, develops GD-WL and Graphormer-GD, and reports strong theoretical and empirical performance.

  • Motivation: Existing expressive GNN work often relies on toy examples, while principled metrics beyond the WL hierarchy remain lacking.Higher-order WL approaches are costly, and the necessity of their expressiveness for real-world tasks is questioned.
  • Motivation: Graph biconnectivity captures intrinsic graph structure through cut vertices, cut edges, biconnected components, and block cut trees.It is theoretically relevant, practically connected to molecular and social networks, and computationally tractable.
  • Limitations of prior GNNs: Representative GNN architectures cannot even distinguish graphs with and without cut vertices or cut edges, and therefore fail harder node-, edge-, and graph-level biconnectivity tasks.The harder tasks include identifying all cut vertices or edges and distinguishing non-isomorphic block cut trees.
  • Prior expressive framework: DSS-WL with node marking can precisely identify both cut vertices and cut edges, whereas ego-network policies without marking and weaker DS-WL variants cannot identify cut vertices.This gives a theoretical justification for ESAN’s relevant expressive power while exposing the importance of the design choices.
  • Proposed framework: GD-WL incorporates distance information into WL aggregation; SPD-WL handles edge-biconnectivity, RD-WL handles vertex-biconnectivity, and together they solve all biconnectivity problems.The framework targets the distance-information weakness of classic 1-WL and is designed to be more efficient than DSS-WL.
  • Implementation and evaluation: Graphormer-GD preserves GD-WL expressiveness in a Transformer-like architecture and achieves perfect cut-vertex and cut-edge detection while outperforming prior GNNs on benchmark datasets.The architecture injects distances into multi-head attention and is fully parallelizable.

2 PRELIMINARY

The preliminary section defines graph connectivity, biconnectivity, color refinement, and the paper’s distinguishing tasks. It also states that standard algorithms compute biconnectivity structures in linear graph-size complexity.

  • Notation: The paper considers simple undirected graphs without repeated edges or self-loops, defining neighborhoods, degrees, paths, sets, multisets, and index notation.These notations support the later definitions of connectivity and biconnected components.
  • Connectivity: A graph is connected when every pair of nodes has a path between them, and its connected components partition the vertex set.The graph is connected exactly when it has one connected component.
  • Biconnectivity: A cut vertex is a node whose removal increases the number of connected components; vertex-biconnected graphs are connected graphs without cut vertices.Vertex-biconnected components are maximal induced vertex-biconnected sets, with analogous definitions for cut edges and edge-biconnected components.
  • Biconnectivity: Nodes share a vertex-biconnected component when two paths connect them without intersecting except at endpoints, and share an edge-biconnected component when two such paths share no edge.Nodes in different components must be linked through cut vertices or cut edges.
  • Block cut trees: Block cut-vertex trees represent a graph using its vertex-biconnected components together with its cut vertices and incidence edges.The definition introduces BCVTree(G) from the component set and cut-vertex set.
  • Algorithms: Depth-First Search computes cut vertices, cut edges, biconnected components, and block cut trees in Θ(|V| + |E|) time.This establishes linear computational complexity in graph size for the classical biconnectivity problems.
  • Color refinement and tasks: Color refinement algorithms assign isomorphism-invariant node colors, and the paper defines increasing tasks for distinguishing biconnectivity and identifying cut vertices or edges.The supplied setup states the graph-level comparison criterion through multisets of node colors.

3 INVESTIGATING KNOWN GNN ARCHITECTURES VIA BICONNECTIVITY

The analysis finds that several prominent GNN variants fail to distinguish graph biconnectivity, while DSS-WL with node marking can identify cut vertices and cut edges. Its advantage is linked to distance information and cross-subgraph aggregation.

  • Known GNN architectures: Most surveyed GNN variants are not expressive for any listed biconnectivity problem.The review covers MPNNs, GSN variants, lifting-based methods, GraphSNN, and subgraph GNNs.
  • Known GNN architectures: 1-WL cannot distinguish biconnectivity because counterexample graphs receive identical node-color representations.The counterexamples include graphs with cut vertices or edges and graphs without them.
  • Known GNN architectures: Arbitrary connected substructure counts do not make SC-WL expressive for vertex- or edge-biconnectivity.Theorem 3.1 gives counterexamples with O(n) vertices and edges when the largest chosen substructure has n vertices.
  • Known GNN architectures: Lifting-based SWL and CWL also cannot solve any listed biconnectivity problem.The negative result applies to methods built from higher-order structures such as cliques and cycles.
  • DSS-WL expressiveness: DSS-WL with node marking identifies cut vertices and cut edges from its color mapping.Matching node colors preserve cut-vertex status, and matching endpoint-color pairs preserve cut-edge status across graphs.
  • DSS-WL expressiveness: DSS-WL’s biconnectivity advantage depends on distance information and cross-subgraph aggregation.Node marking encodes distance information, whereas common DS-WL policies without cross-graph interaction cannot identify cut vertices.

4 GENERALIZED DISTANCE WEISFEILER-LEHMAN TEST

The paper introduces GD-WL, a distance-aware refinement framework designed to efficiently achieve provable expressiveness for graph biconnectivity. Its SPD and RD variants characterize edge- and vertex-biconnectivity, while matching these guarantees with lower complexity than DSS-WL.

  • Motivation: DSS-WL solves biconnectivity but requires Θ(n^2) space and Θ(nm) time per iteration, motivating more efficient refinement algorithms.These costs are n times those of 1-WL in the stated comparison.
  • GD-WL framework: GD-WL extends 1-WL by aggregating node information according to an arbitrary distance metric, addressing 1-WL’s lack of distance information.The framework is introduced as a simple distance-aware color refinement procedure.
  • SPD-WL: SPD-WL, obtained with shortest-path distance, is strictly more powerful than 1-WL and is fully expressive for all edge-biconnectivity problems.It additionally aggregates k-hop neighbors for every k > 1 and identifies cut-edge structure through BCETree representations.
  • RD-WL: RD-WL uses resistance distance to solve vertex-biconnectivity, including identification of cut vertices and reconstruction of the block cut-vertex tree.Resistance distance is defined through effective resistance in an electrical-network interpretation and can be efficiently calculated.
  • Expressiveness and efficiency: Combining shortest-path and resistance distances yields GD-WL, which is fully expressive for both vertex- and edge-biconnectivity.The framework requires Θ(n) space and Θ(n^2) time per iteration, below DSS-WL’s stated costs.
  • Limits and implementation: Graphormer-GD can preserve GD-WL’s expressiveness with suitable functions, sufficiently many heads, and sufficiently many layers, while 2-FWL remains an upper bound.Theoretically, 2-FWL is more powerful than both SPD-WL and RD-WL and is itself fully expressive for both biconnectivity types.
  • Distance-regular graphs: For distance-regular graphs, RD-WL is strictly more powerful than SPD-WL and matches 2-FWL, providing a worst-case justification for resistance distance.The paper presents this as a result showing an efficient WL algorithm can match 2-FWL on this graph class.

5 EXPERIMENTS

The experiments evaluate Graphormer-GD on synthetic biconnectivity tasks and ZINC, testing both theoretical expressiveness and practical generalization. Graphormer-GD achieves perfect synthetic accuracy and matches or surpasses competitive baselines on ZINC.

  • Real-world tasks: The experiments test whether biconnectivity-expressive GNNs improve real-world performance on ZINC-Subset and ZINC-Full.ZINC-Full contains 250K molecular graphs, while ZINC-Subset contains 12K selected graphs.
  • Synthetic tasks: Graphormer-GD achieves 100% accuracy on both cut-vertex and cut-edge detection tasks, whereas baseline GNNs cannot perfectly solve them.Using SPD suffices for cut-edge identification, while RD is additionally necessary for cut-vertex identification.
  • Real-world tasks: With approximately 500K parameters, Graphormer-GD is compared against publicly released expressive GNN baselines under a matched parameter budget.The ZINC evaluation reports test-set MAE and per-epoch training time on ZINC-Subset.
  • Real-world tasks: Graphormer-GD surpasses or matches all competitive baselines on both ZINC-Subset and ZINC-Full.Its performance is averaged over four experiments with different random seeds.
  • Real-world tasks: Subgraph GNNs consistently outperform classic MPNNs, while Graphormer-GD is simpler, more parallelizable, and achieves better performance than Subgraph GNNs.The paper suggests these properties support extension to practical scenarios such as drug discovery.
  • Other tasks: Additional node-level experiments are conducted on the Brazil-Airports and Europe-Airports datasets, with results reported in Appendix F.3.The supplied passage does not report their numerical outcomes.

6 CONCLUSION

The paper studies GNN expressiveness through graph biconnectivity, analyzes the limits of existing architectures, and proposes GD-WL and Graphormer-GD as expressive and efficient alternatives. Experiments support the effectiveness of the resulting architecture, while several theoretical questions remain open.

  • Contributions: The conclusion presents GD-WL as fully expressive for all biconnectivity metrics and Graphormer-GD as an expressive architecture with practical efficiency and parallelizability.Experiments on synthetic and real-world datasets demonstrate Graphormer-GD’s effectiveness.
  • Open problems: Open problems include whether equivariant GNNs can solve biconnectivity in o(n^2) time and how GD-WL relates to graph spectral information and expressiveness.The paper specifically conjectures that RD-WL may encode graph spectral information and exceed SPD-WL on general graphs.
  • Background: Higher-order GNNs improve expressiveness but incur severe computation and memory costs, motivating more efficient alternatives within or beyond message passing.Prior approaches include higher-order, substructure-based, subgraph, non-equivariant, and structure-aware GNNs.
  • Background: Classic 1-WL iteratively refines node colors using each node’s current color and neighborhood color multiset, but can fail to distinguish non-isomorphic graphs.The stable color multiset serves as a graph representation for the test.

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

SC-WL augments 1-WL with substructure counts, while DSS-WL aggregates information across symmetrically generated subgraphs. The section also introduces GD-WL’s distance-based refinement and summarizes expressivity results for these methods.

  • SC-WL: SC-WL counts selected connected substructures, such as cycles and cliques, around each vertex and concatenates orbit-specific counts into node features.The procedure first selects a set of small connected graphs, then counts induced copies containing each vertex.
  • SC-WL: SC-WL’s message-passing update incorporates these substructure counts, and the same expressive conclusion applies when counts are calculated for edges.The edge-feature extension is described as analogous to the vertex-feature procedure.
  • DSS-WL: DSS-WL generates a bag of graphs sharing vertices but differing in edge sets, then jointly aggregates node colors within and across those graphs.Its graph-generation policy determines both the generated edge sets and initial coloring.
  • DSS-WL: DSS-WL policies must be permutation-equivariant; common choices include node marking, node deletion, and ego-network policies.The node marking policy creates one graph per vertex with a specially colored marked node, while node deletion isolates the selected node.
  • DSS-WL: DSS-WL with the listed policies is strictly more powerful than classic 1-WL, and node marking is at least as powerful as node deletion.The original DS-WL output is graph-level, requiring adaptations for node-level tasks such as cut-vertex detection.
  • GD-WL: GD-WL generalizes color refinement by supplying a distance metric; choosing shortest-path distance yields SPD-WL, which is strictly more powerful than 1-WL.Its algorithm takes a graph, a distance metric dG, and an iteration count as input.
  • Analysis: DSS-WL, SPD-WL, and k-FWL satisfy a generalized WL-condition used to analyze their color-refinement behavior.The condition compares neighborhood color counts for vertices sharing a color, including across graphs where applicable.

C.2 COUNTEREXAMPLES

The counterexamples construct graph pairs that differ in cut vertices or cut edges but remain indistinguishable to several prior WL and GNN variants. These results show that the failures extend across substructure, cellular, overlap-subgraph, ego-network, and GNN-AK approaches.

  • Counterexample construction: The counterexample families contain graph pairs with identical node sets but different cycle and attachment structures, including graphs where only one graph has cut vertices or cut edges.Example C.9 uses n = 2km + 1 nodes, while Example C.10 uses n = 2m nodes with m ≥3.
  • Substructure and WL variants: For connected substructure sets H with nV < m, SC-WL cannot distinguish whether graphs have cut vertices or cut edges, with counterexamples of size O(nV).Because the counterexample cycles have length at least m, substructures smaller than m cannot exploit those cycles; the proof reduces the relevant connected substructures to trees.
  • Substructure and WL variants: Simplicial WL and the considered Cellular WL variants cannot distinguish cut vertices or cut edges, including counterexamples whose size is O(k).When the counterexample graphs lack suitable cliques or have cycles longer than k, these methods reduce to classic 1-WL.
  • Substructure and WL variants: Even with k scaling to graph size, Cellular WL with k-IC still fails to distinguish cut vertices on the Example C.9 graph pair.The relevant two-dimensional cells are cycles of equal length and receive the same Cellular WL color.
  • GNN and subgraph architectures: Overlap Subgraph WL, unmarked DSS-WL with ego-network policies, and GNN-AK cannot distinguish selected graph pairs involving cut vertices or cut edges.Overlap Subgraph WL reduces to 1-WL on triangle-free graphs, while the cited ego-network and GNN-AK results provide separate counterexamples.

C.3 PROOF OF THEOREM 3.2

The proof analyzes DSS-WL with node marking by relating matching color information to distances, connected components, and marked neighborhoods. It establishes that matching DSS-WL colors preserve whether corresponding nodes or edges are cut elements.

  • Node cut vertices: Theorem 3.2 states that equal DSS-WL colors under node marking preserve cut-vertex status across two graphs.The proof first reduces attention to the connected components containing the compared marked nodes, then uses distance and color-mapping properties.
  • Edge cut edges: Equal endpoint-color multisets preserve cut-edge status for corresponding edges in two graphs.This is the edge-level counterpart of the node result and is stated as a separate conclusion of Theorem 3.2.
  • Distance and color properties: DSS-WL node marking separates marked from unmarked nodes and encodes distance information through marked color mappings.The proof derives distance equality from the WL-condition and from how marked colors propagate through connected graphs.
  • Proof for node status: The proof proceeds by induction over distance layers and derives contradictions from paths that would avoid the purported cut vertex.The induction controls the color multisets at successive distances, while path arguments transfer connectivity constraints between graphs.
  • Proof for node status: For a cut vertex u, removing u partitions the graph into at least two connected components, and the proof tracks color classes across those components.The argument uses distance layers and equal-color constraints to show that a node sharing u’s color must also be a cut vertex.

C.4 PROOF OF THEOREM 4.1

The proof establishes that SPD-WL preserves cut-edge correspondence across graphs with matching color representations and determines their block cut-edge trees up to isomorphism. The argument uses color-graph structure, distance-based contradictions, and connected-component analysis.

  • Main result: SPD-WL matching edge-color multisets preserve whether corresponding edges are cut edges.For edges in G and H with identical endpoint-color multisets, one edge is a cut edge if and only if the other is.
  • Main result: Equal SPD-WL graph representations imply isomorphic block cut-edge trees.The block cut-edge tree is therefore determined by the multiset of SPD-WL node colors.
  • Proof strategy: The proof first handles connected graphs by analyzing a cut edge and the two components created when it is removed.It separates cases according to whether the cut edge’s endpoints have distinct or identical SPD-WL colors.
  • Proof strategy: The auxiliary color graph records endpoint-color pairs for graph edges and supports the contradiction arguments used to rule out non-corresponding cut-edge structures.Its edges are multisets because self-loops can occur.
  • Proof strategy: Distance-based arguments show that carefully chosen same-colored vertices would acquire incompatible distance multisets under SPD-WL.This contradiction is used to establish the needed structural properties around cut edges.
  • Proof strategy: The result extends from connected graphs by combining color-multiset matching, preservation of connectivity status, and the connected-case argument.The cited corollary applies the same reasoning to the disconnected case.

C.5 PROOF OF THEOREM 4.2

The proof of Theorem 4.2 shows that RD-WL preserves cut-vertex correspondence and determines the block cut-vertex tree from the graph representation. The argument reduces matching colors to matching graph representations and then analyzes connected graphs.

  • Main result: RD-WL matching node colors preserve whether corresponding vertices are cut vertices.A vertex w in G is a cut vertex exactly when any vertex x in H with the same RD-WL color is a cut vertex.
  • Main result: Equal RD-WL graph representations imply isomorphic block cut-vertex trees.Thus the representation determines the tree-level organization of cut vertices and biconnected components.
  • Proof strategy: The proof uses a resistance-distance lemma and follows the earlier SPD-WL analysis after reducing matching colors to equal graph representations.The two theorem bullets are proved separately for connected graphs, with disconnected cases handled through the representation properties.

C.5.1 PROOF OF THE FIRST PART

The first part of Theorem 4.2 derives cut-vertex preservation under RD-WL from resistance distance. A vertex is characterized by additive resistance distances across pairs separated by that vertex, and RD-WL transfers this structure between graphs.

  • Resistance-distance characterization: A vertex is a cut vertex exactly when some pair of other vertices has resistance distance that decomposes through it.For a cut vertex v separating u and w, resistance distance satisfies disR(u,w) = disR(u,v) + disR(v,w).
  • Resistance-distance characterization: Resistance distance equals commute-time distance divided by 2|E|, linking the proof’s resistance-distance criterion to random-walk hitting times.The commute-time identity is used as the technical basis for the resistance-distance analysis.
  • Proof strategy: If a vertex is not a cut vertex, hitting paths between any two other vertices include paths that avoid it, preventing the cut-vertex distance decomposition.The proof partitions hitting paths according to whether they pass through the candidate vertex.
  • Proof strategy: For a cut vertex, removing it partitions the remaining vertices into at least two connected components, and RD-WL distance relations constrain where same-colored vertices can occur.The proof uses these component partitions to show that matching RD-WL colors preserve cut-vertex status.
  • Conclusion: The resulting contradiction shows that vertices with matching RD-WL colors have the same cut-vertex status across the two graphs.The argument concludes by applying the resistance-distance characterization to the constructed vertex pairs.

C.5.2 PROOF OF THE SECOND PART

The second part shows that RD-WL determines the block cut-vertex tree from its graph representation. The proof matches component-color structures around corresponding cut vertices and recursively reconstructs the tree.

  • Component matching: After removing a cut vertex u, the resulting components are indexed as S_G,i(u), with their number m_G(u) exceeding one.This component structure is the basis for comparing corresponding cut vertices across graphs.
  • Component matching: The proof uses resistance-distance comparisons to distinguish components containing matching-colored vertices from components that do not.The two cases yield strict or equal resistance-distance relations depending on component correspondence.
  • Component matching: RD-WL matching colors preserve the number of components and the multisets of colors associated with corresponding components.Corollary C.51 states that matching-colored vertices have equal component counts and matching component-color structure.
  • Tree reconstruction: In a block cut-vertex tree, nodes represent cut vertices or biconnected components, with edges joining each cut vertex to the biconnected components containing it.This structural definition supplies the object reconstructed from the representation.
  • Tree reconstruction: Given representation R, all cut-vertex colors and each cut vertex’s component count can be recovered without knowing the specific graph.The component count equals the corresponding cut vertex’s degree in the block cut-vertex tree.
  • Tree reconstruction: The BCVTree is constructed recursively by identifying leaf cut-vertex nodes and then exposing new leaves until the full tree is recovered.Each step depends only on R and the color-based component structure.

C.6 PROOF OF THEOREM 4.5

The proof establishes that 2-FWL is at least as expressive as SPD-WL and RD-WL, yielding corresponding limits and comparisons for distance-based biconnectivity analysis.

  • 2-FWL preserves equality of node-pair colors only when corresponding structural relations, including equality and adjacency, agree.
  • Equal 2-FWL colors imply equal graph and resistance distances between the corresponding node pairs.
  • 2-FWL is more powerful than both SPD-WL and RD-WL under the induced vertex-partition ordering.
  • Any refinement that is at least as fine as another color mapping inherits its ability to distinguish cut vertices, cut edges, and block-cut-tree isomorphism types.
  • For distance-regular graphs, SPD-WL distinguishes graphs exactly by k-hop-neighbor arrays, whereas RD-WL and 2-FWL distinguish them exactly by intersection arrays.

C.7.1 PROOF OF THEOREM C.58

The theorem characterizes SPD-WL and RD-WL on distance-regular graphs and shows that RD-WL matches 2-FWL there while strictly exceeding SPD-WL.

  • For distance-regular graphs, equal k-hop-neighbor arrays are exactly the condition under which SPD-WL cannot distinguish the graphs.
  • Resistance distance between node pairs in a distance-regular graph depends only on their shortest-path distance.
  • Equal intersection arrays imply equal resistance-distance multisets, preventing RD-WL from distinguishing the graphs.
  • Different intersection arrays produce a differing resistance-distance multiset, allowing RD-WL to distinguish the graphs.
  • 2-FWL also cannot distinguish distance-regular graphs with identical intersection arrays, while differing arrays are distinguishable.

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

The paper reviews existing expressivity metrics, emphasizing their computational or practical limitations, and motivates biconnectivity as a theoretically basic and application-relevant alternative.

  • WL hierarchy: Higher-order WL tests provide expressivity but incur severe computational costs, with each 2-FWL iteration requiring Ω(n^3) time and Θ(n^2) space.
  • Structural metrics: Structural metrics such as substructure counting, cycle detection, and diameter computation may correspond to problems that are too hard for GNNs.
  • Biconnectivity: Biconnectivity is presented as a basic graph property with important theoretical and practical value, unlike metrics focused mainly on rarely occurring regular graphs.
  • Contributions: The paper formalizes GD-WL as a principled framework that includes SPD-WL as a special case and unifies prior distance-based approaches.
  • Contributions: A Transformer-based GNN is designed to be provably as expressive as GD-WL while supporting practical implementation and parallelizable computation.

E.3 TRANSFORMER-BASED IMPLEMENTATION

Graphormer-GD incorporates shortest-path and resistance distances into Transformer attention, and under suitable capacity it matches GD-WL expressiveness.

  • Architecture: Graphormer-GD uses Transformer self-attention and feed-forward blocks, with graph structure injected through distance-dependent attention.
  • Distance encoding: The model encodes shortest-path distance and resistance distance, using Gaussian-basis kernels for the potentially non-integer resistance values.
  • Expressivity guarantee: With sufficiently many heads and layers and suitable functions, Graphormer-GD is as powerful as GD-WL.
  • Expressivity simulation: GD-WL updates each node by aggregating colors of nodes grouped by their distance configurations.
  • Expressivity simulation: The implementation uses multi-head attention to obtain injective aggregates for nodes sharing each distance configuration, thereby simulating GD-WL.

F.2 REAL-WORLD TASKS

The paper evaluates Graphormer-GD on molecular solubility and airport-network tasks against diverse GNN baselines under controlled parameter budgets. It matches or outperforms baselines on real-world benchmarks while maintaining efficiency comparable to classic MPNNs through Transformer parallelizability.

  • ZINC experiments: ZINC contains 250K molecular graphs, with experiments conducted on both ZINC-Full and the 12K-graph ZINC-Subset for constrained-solubility prediction.The task targets a chemical property relevant to drug discovery.
  • ZINC experiments: Graphormer-GD is compared with MPNNs, higher-order GNNs, substructure-based GNNs, subgraph GNNs, and Graph Transformers under approximately 500K parameters.The comparison includes representative models from five architecture categories.
  • Node-level tasks: Graphormer-GD outperforms the baselines on both Brazil-Airports and Europe-Airports, although its variance is slightly larger because these datasets are small.The airport graphs represent commercial-flight networks between airports.
  • Efficiency: 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 paper attributes this efficiency to the high parallelizability of Transformer layers and reports greater efficiency than higher-order GNNs.
Loading 2301.09505v3…