Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency

AI summary

Overview

• Research area: Graph machine learning, specifically higher-order graph neural networks (HOGNNs) and the Weisfeiler-Leman (WL) expressivity hierarchy. The paper sits at the intersection of graph-theoretic structural analysis (connected and biconnected components, block-cut trees) and efficient GNN architecture design.
• Technical level: Intermediate to Advanced. The core insight is intuitive, but the paper assumes familiarity with the 1-WL/2-FWL hierarchy, message passing over node tuples, and graph connectivity concepts such as cut nodes and biconnected components.
• Scope: This paper proposes "Co-Sparsify," a framework that removes provably expressivity-redundant 2-node and 3-node computations from 2-FWL GNNs, proves that the result remains exactly as expressive as the 2-FWL test, and demonstrates efficiency gains on synthetic substructure counting and real-world molecular benchmarks.

What This Paper Is About

Higher-order GNNs based on the 2-FWL test are far more expressive than standard message-passing GNNs because they model interactions among pairs and triples of nodes, but this costs roughly O(n³) memory and computation per layer. Existing efficiency methods (subgraph sampling, set-based reduction, localized aggregation) buy speed by approximating or restricting the computation, which reduces expressive power. This paper asks whether computations can instead be removed exactly — keeping every interaction that contributes discriminative power and dropping only those that provably contribute nothing.

Key Contributions

1. A structural characterization of where higher-order interactions matter. The authors identify that in 2-FWL GNNs, 3-node interactions are expressively useful only within biconnected components, and 2-node interactions matter only within connected components. Outside these regions, higher-order computation adds no discriminative power.

2. The Co-Sparsify message-passing scheme. A connectivity-aware sparsification method that restricts 3-node interactions to triples inside the same biconnected block and 2-node message passing to pairs inside the same connected component. It uses no sampling, approximation, or heuristic pruning — sparsification follows exact graph topology.

3. An expressivity-preservation proof. The authors prove (Theorem 4, with supporting Lemmas 1–3) that Co-Sparsified 2-FWL GNNs are as powerful as the 2-FWL test at detecting substructures and distinguishing non-isomorphic graphs, under injective aggregation and consistent initialization. The paper describes this as the first sparsification method for HOGNNs with a guaranteed expressivity preservation result.

4. Empirical validation of the framework. Applied to PPGN (yielding CoSp-PPGN), the method matches or exceeds the original model on synthetic substructure counting tasks and reports state-of-the-art performance on ZINC and QM9, while reducing runtime and memory.

Main Findings

• Preserved expressivity with less computation: Co-Sparsify keeps the same update rules as standard 2-FWL GNNs but restricts the neighbor set. Standard 2-FWL GNNs update O(n²) 2-tuples using O(n³) 3-tuple interactions; Co-Sparsify reduces this to O(Σᵢ nᵢ²) pairs (summed over connected components of size nᵢ) and O(Σⱼ n_{bⱼ}³) triples (summed over biconnected components of size n_{bⱼ}). On graphs with sparse or fragmented higher-order connectivity, such as molecules, the paper reports this yields sub-quadratic or sub-cubic complexity in practice.

• Negligible preprocessing cost: Connectivity is computed via breadth-first search and block-cut tree decomposition, running in O(n + m) time. The measured overhead is roughly 1 ms per graph on average.

• Substructure counting: On the synthetic counting dataset of 5,000 randomly generated graphs (0.3/0.2/0.5 train/validation/test split), CoSp-PPGN reports the lowest normalized test MAE on several targets, including 4-Path (0.0029), Tailed Triangle (0.0016), 6-Cycles (0.0056) and Tri.-Rec. (0.0049), while comparing against NGNN, GIN-AK+, I²-GNN, N²-GNN and PPGN. The paper states CoSp-PPGN matches or surpasses PPGN across all substructure counting tasks.

• QM9: CoSp-PPGN+RRWP achieves top-two performance on 10 out of 12 molecular property targets, which the authors present as empirical validation that sparsification preserves PPGN's full 2-FWL expressivity.

• ZINC: On ZINC-Subset (12K graphs), CoSp-PPGN+RRWP reaches 0.050 ± 0.001 MAE versus 0.055 ± 0.002 for PPGN+RRWP; on ZINC-Full (250K graphs), 0.018 ± 0.002 versus 0.020 ± 0.002. Both models have 478K parameters. The paper describes these as state-of-the-art results.

• TUD classification benchmarks: CoSp-PPGN reports the best accuracy among the compared methods on all four datasets shown, with results averaged over 10 runs: FRANK. 77.65 ± 1.35 (versus UnionGNNs 68.02 ± 1.47 and 3WL-GNN 58.68 ± 1.93), NCI1 82.87 ± 1.87 (versus 82.24 ± 1.24 and 78.39 ± 1.54), NCI109 82.91 ± 1.22 (versus 82.34 ± 1.93 and 77.97 ± 2.22), and ENZYMES 74.50 ± 6.45 (versus 68.17 ± 5.70 and 54.17 ± 6.25). Note the paper states in the text that "Table 6" reports these results, while the corresponding table is captioned Table 5.

• Efficiency gains on PPGN: Runtime is reduced by 13–60% — from 9.3 s to 7.9 s per epoch on ZINC-subset, 456.9 s to 403.6 s on ZINC-Full, and 97.1 s to 60.7 s on QM9. Memory consumption decreases by 12–52% — from 3.7 GB to 3.0 GB on ZINC-subset, 17.4 GB to 15.6 GB on ZINC-Full, and 6.4 GB to 4.2 GB on QM9.

• A generalization bottleneck, not an expressivity one: On long-range tasks such as Peptides-struct, standard CoSp-PPGN underperforms despite high expressivity. A localized variant restricting updates and aggregation to pairs within shortest-path distance ≤ 4 reaches a state-of-the-art average MAE of 0.245, outperforming Graph Transformers. Peak performance occurs with one message-passing layer and degrades with depth, which the authors attribute to over-squashing rather than to any loss of expressive power.

Methodology in Plain English

The starting point is observing what a 2-FWL GNN actually computes. It updates the representation of every node pair (u, v) by aggregating messages from coupled pairs ((u, t), (t, v)) over all intermediate nodes t. When u, t and v are all distinct, this is a 3-node interaction — the mechanism that lets the model detect structures like two internally disjoint paths. When u = t or t = v, the interaction collapses to a 2-node one.

The authors' argument is that a 3-node interaction only adds information when u, t and v sit inside the same biconnected component — a maximal subgraph where every pair of nodes lies on a cycle. By Menger's theorem, biconnectedness guarantees at least two internally disjoint paths between any two nodes, and distinguishing that situation requires looking at triples. Everywhere else, the interaction decomposes: if all u-to-v paths must pass through a cut node, the connection is just the concatenation of shorter pairwise paths that 2-FWL already updates; if u and v are in different connected components, there is no path at all and the structural context (component size, component count) is handled by ordinary readout functions.

So the implementation is a restricted neighbor set. The graph is first decomposed into connected components and biconnected blocks using Tarjan's block-cut tree algorithm in O(n + m) time. Pair representations are then updated only over triples inside the same biconnected block, plus a small set of 2-node interactions that propagate information between self-pairs (nodes) and off-diagonal pairs, and between pairs and nodes. Disconnected pairs receive no update at all. Readouts are defined at the node level (aggregating incoming pairs within a component), the component level (separate readouts over self-pairs and off-diagonal pairs), and the graph level (aggregating component representations).

The expressivity proof proceeds by induction over message-passing layers: any query subgraph lying inside a biconnected component is detected exactly as in full 2-FWL, any subgraph spanning multiple blocks decomposes into pairwise segments that are already fully encoded, and disconnected queries are handled by unchanged readout operations.

Why This Matters

Impact on research. The result reframes the expressivity-efficiency trade-off in higher-order GNNs. Most prior efficient HOGNN work (ESAN, KCSetGNN, 1-2-3-GNN, and others) accepts some loss of expressive power in exchange for tractable computation. This paper argues that a large class of the computation in 2-FWL GNNs is simply unnecessary — redundant given graph topology — so efficiency can come from structural insight rather than approximation. If the framework generalizes, it suggests a design principle for scalable GNNs generally: align computation with structural criticality. It also supplies the first expressivity-preservation guarantee for HOGNN sparsification, which makes the approach auditable in a way approximation-based methods are not.

Real-world applications (the paper evaluates on molecular graph benchmarks, which is where these apply):

• Molecular property prediction in computational chemistry and early-stage drug discovery, where models must regress quantum-chemical targets such as HOMO/LUMO energies, ZPVE, and internal energy from graph structure (QM9).
• Large-scale molecular screening, where the penalty-constrained graph-level regression on ZINC-Full (249,456 graphs) is representative of virtual-library-scale workloads.
• Molecular and chemical graph classification, such as the TUD benchmarks (NCI1, NCI109, ENZYMES, FRANK.) used for activity and property prediction.
• Peptide and biomolecular property prediction, though the paper reports that standard CoSp-PPGN underperforms here and only a distance-restricted localized variant reaches state-of-the-art results (0.245 average MAE).

Industry relevance. The efficiency numbers are the practical story: PPGN's O(η²) per-graph memory due to padding, where η is the largest graph in a batch, limits its deployment on large or irregular graphs. A method that cuts memory by 12–52% and runtime by 13–60% while keeping the same parameter count (478K for the reported PPGN variants) and the same accuracy makes higher-order GNNs more viable in resource-constrained or throughput-sensitive settings. The O(n + m), roughly 1 ms-per-graph preprocessing step also means the method can be adopted without a costly offline pipeline.

Future Directions

• Balancing expressivity and generalization. The authors identify this as the key open problem. Under 2-FWL-level expressivity, CoSp-PPGN peaks at one message-passing layer and degrades with depth, and the paper attributes this to over-squashing from combinatorial message aggregation rather than to insufficient expressive power. Understanding and fixing that is the natural next step.

• Adaptive receptive fields. The paper states plans to explore adaptive receptive fields, motivated by the finding that a localized variant (shortest-path distance ≤ 4) beats the unrestricted model on Peptides-struct.

• Scaling the framework to higher orders. HOGNNs beyond 2-FWL face prohibitive computational complexity. The authors aim to extend the sparsification principle to make those models more scalable, though it is not yet shown whether the biconnected/connected-component argument has an analogue at higher arities.

• Broadening the evaluation. The paper focuses on datasets where expressive power is the primary bottleneck, which it notes is common practice for HOGNNs, and does not report results on datasets where PPGN cannot be applied at all. Whether Co-Sparsify's gains translate to those settings, and which datasets fall into that category, is listed in the appendix but not summarized in the main text.

Target Audience

Researchers and practitioners working on graph neural networks, particularly those interested in GNN expressivity, the WL hierarchy, and higher-order message passing. It is also relevant to graph-theory-inclined readers interested in how connectivity decompositions (connected components, block-cut trees, cut nodes) can be used as architectural priors rather than just analysis tools. Practitioners applying GNNs to molecular property prediction will find the QM9, ZINC, and TUD results directly useful, and efficiency-focused engineers will find the runtime and memory figures actionable. Readers without background in the 2-FWL test or graph connectivity will need to consult the preliminaries section and cited background work first.

Authors’ abstract

Higher-order Graph Neural Networks (HOGNNs) based on the 2-FWL test achieve superior expressivity by modeling 2- and 3-node interactions, but at $\mathcal{O}(n^3)$ computational cost. However, this computational burden is typically mitigated by existing efficiency methods at the cost of reduced expressivity. We propose \textbf{Co-Sparsify}, a connectivity-aware sparsification framework that eliminates \emph{provably redundant} computations while preserving full 2-FWL expressive power. Our key insight is that 3-node interactions are expressively necessary only within \emph{biconnected components} -- maximal subgraphs where every pair of nodes lies on a cycle. Outside these components, structural relationships can be fully captured via 2-node message passing or global readout, rendering higher-order modeling unnecessary. Co-Sparsify restricts 2-node message passing to connected components and 3-node interactions to biconnected ones, removing computation without approximation or sampling. We prove that Co-Sparsified GNNs are as expressive as the 2-FWL test. Empirically, on PPGN, Co-Sparsify matches or exceeds accuracy on synthetic substructure counting tasks and achieves state-of-the-art performance on real-world benchmarks (ZINC, QM9). This study demonstrates that high expressivity and scalability are not mutually exclusive: principled, topology-guided sparsification enables powerful, efficient GNNs with theoretical guarantees.