PaperlayerView exact revision on arXiv

Source-linked AI summary

Weisfeiler and Lehman Go Cellular: CW Networks

Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, Michael Bronstein

arXiv:2106.12575v3cs.LGstat.ML

TL;DR

GNNs are limited by WL-level expressivity, difficulty modeling higher-order structures, and the coupling between computational and input graphs. The paper introduces CW Networks, which lift graphs into regular cell complexes for hierarchical message passing and theoretically stronger expressivity. CWNs are strictly more powerful than WL, at least as powerful as 3-WL for some liftings, and achieve strong results on molecular benchmarks, with computational costs limiting general-graph use.

  • Problem

    GNNs have limited expressivity, struggle with long-range interactions, and lack a principled way to model higher-order structures because computation is tightly coupled to the input graph.

  • Method

    CW Networks lift graphs into regular cell complexes and perform hierarchical message passing using flexible higher-dimensional cells and cell adjacencies.

  • Results

    CWNs are strictly more powerful than WL, while some lifting schemes are not less powerful than 3-WL, and the models achieve state-of-the-art results on molecular graph datasets and related tasks.

  • Takeaways & Limitations

    Cell-complex lifting provides a theoretically grounded framework for more expressive graph architectures that model higher-order molecular structure through hierarchical message passing.

  • Takeaways & Limitations

    For general graphs, the number of rings or simple cycles can be exponential, and cell-complex models typically require dimension-specific weights that increase parameters compared with GNNs.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. These problems can be attributed to the strong coupling between the computational graph and the input graph structure. The recently proposed Message Passing Simplicial Networks naturally decouple these elements by performing message passing on the clique complex of the graph. Nevertheless, these models can be severely constrained by the rigid combinatorial structure of Simplicial Complexes (SCs). In this work, we extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph "lifting" transformations, each leading to a unique hierarchical message passing procedure. The resulting methods, which we collectively call CW Networks (CWNs), are strictly more powerful than the WL test and not less powerful than the 3-WL test. In particular, we demonstrate the effectiveness of one such scheme, based on rings, when applied to molecular graph problems. The proposed architecture benefits from provably larger expressivity than commonly used GNNs, principled modelling of higher-order signals and from compressing the distances between nodes. We demonstrate that our model achieves state-of-the-art results on a variety of molecular datasets.

1 Introduction

Standard GNN message passing is tied to the input graph, limiting expressivity, higher-order structure detection, and long-range interactions. CW Networks address these issues by lifting graphs into flexible cell complexes for hierarchical message passing.

  • GNN neighborhood aggregation is at most as powerful as the Weisfeiler-Lehman test for distinguishing non-isomorphic graphs.
  • These limitations prevent GNNs from reliably detecting higher-order meso-scale structures such as cliques and induced cycles.
  • CW Networks use regular cell complexes to decouple the computational graph from the input graph through higher-dimensional graph liftings.
  • CW Networks generalise Message Passing Simplicial Networks while avoiding the rigid combinatorial structure of simplicial complexes.
  • The proposed framework targets more expressive hierarchical message passing for graph-structured data, including molecular graphs.

2 Background

Regular cell complexes represent spaces through cells organized by boundaries and face-poset relations. They generalize graphs by attaching higher-dimensional cells, while simplicial complexes impose more rigid simplex-shaped cells; their adjacencies support message passing.

  • A regular cell complex partitions a topological space into cells, each homeomorphic to the interior of a closed ball with a closure satisfying regularity.
  • The face poset records cell containment, and for regular complexes this combinatorial structure encodes the topology.
  • Cell complexes are built hierarchically by attaching edges to vertices and gluing disk boundaries to graph cycles, with higher-dimensional analogues possible.
  • Simplicial complexes are cell complexes whose n-dimensional cells are n-simplices, restricting two-dimensional cells to triangle shapes.
  • The boundary relation identifies immediate lower-dimensional incidences, such as edges bounding faces, and induces the complex’s partial order.
  • Four local adjacency types—boundary, co-boundary, lower, and upper—form the building blocks of cell-complex message passing.

3 Cellular Weisfeiler Lehman

CWL extends Weisfeiler–Lehman colour refinement from graphs and simplicial complexes to regular cell complexes, enabling graph liftings that add flexible higher-dimensional structure. Its lifting-based variants can exceed WL, match or surpass SWL, and in some cases distinguish graphs that 3-WL cannot.

  • Cellular Weisfeiler–Lehman: CWL performs colour refinement on regular cell complexes using boundary, co-boundary, lower, and upper cell adjacencies.Each iteration updates cell colours from injectively hashed multisets of adjacent-cell colours until a stable colouring is reached.
  • Cellular Weisfeiler–Lehman: CWL without co-boundary and lower adjacencies has the same distinguishing power as CWL with all adjacencies.This generalises an analogous pruning result previously established for simplicial complexes.
  • Graph lifting: Skeleton-preserving liftings retain the graph’s vertices and edges while attaching cells of dimension at least two, and their CWL is at least as powerful as WL.The lifting preserves the input graph’s 1-skeleton, ensuring that added higher-dimensional structure does not replace the original graph structure.
  • Graph lifting: For every k ≥3, liftings based on cliques, induced cycles, or simple cycles yield CWL variants strictly more powerful than WL.These transformations attach cells to the corresponding graph substructures up to size k.
  • Expressive power: Some cycle- and clique-based CWL variants distinguish graph pairs that 3-WL cannot, while combined liftings can be strictly more powerful than SWL.The 3-WL separation holds for k-CL and k-IC at k ≥4, and k-C at k ≥8.

4 Molecular Message Passing with CW Networks

Molecular CWNs lift graphs by representing atoms, bonds, and induced-cycle rings as hierarchical cell-complex signals. This structure supports ring-mediated message passing, retains strong expressivity, and can shorten long-range communication paths while remaining nearly linear for bounded molecular complexes.

  • Molecular architecture: The molecular CWN lifting attaches 2-cells to induced cycles, representing atoms, bonds, and chemical rings.The model uses boundary and upper adjacencies between these cell types.
  • Molecular architecture: Messages flow from atoms to bonds and bonds to rings, and between bonded atoms or bonds sharing a ring.Pairwise messages include the intervening bond or ring features, allowing higher-order context to modulate updates.
  • Expressivity: With injective aggregators and sufficient layers, CWNs attain CWL-level expressivity, while CWL bounds their ability to distinguish cell complexes.For induced-cycle liftings with k ≥3, this gives molecular CWNs expressivity strictly beyond standard WL.
  • Long-range interactions: At most L layers are required for the hierarchical scheme to communicate information across an L-hop molecular dependency.The comparison is motivated by molecular properties involving atoms on opposite sides of a ring.
  • Complexity: For bounded cell dimension and boundary size, message passing is linear in complex size, and molecular lifting is almost linear when ring counts are bounded.The stated molecular example uses an average of three rings per MOLHIV molecule as a small constant bound.

5 Experiments

Experiments evaluate CIN, a CWN instantiated with GIN-style local aggregators, on synthetic expressivity tests and molecular or graph benchmarks. CIN distinguishes difficult graph pairs, solves ring-based long-range transfer with few steps, and reports strong or state-of-the-art results across several molecular datasets.

  • Experimental setup: CIN is evaluated with stacked CWN layers and GIN-style local aggregators across synthetic, TUDataset, ZINC, and Mol-HIV benchmarks.The experiments focus on graph classification, regression, and molecular prediction settings.
  • Synthetic benchmarks: On CSL, CIN identifies isomorphism classes that message-passing GNNs and RingGNN fail to distinguish.The benchmark contains 150 4-regular graphs from 10 isomorphism classes and is unsolvable by WL-based message passing approaches.
  • Synthetic benchmarks: On strongly regular graph families, CIN distinguishes all pairs at k = 6, achieving a 0.0% failure rate.CIN outperforms the MLP baseline for the same k values, while the pairs are not provably distinguishable by 3-WL.
  • Synthetic benchmarks: CIN solves RingTransfer with only 3 computational steps independently of ring size, whereas GIN performance degrades for k ≥24.RingTransfer requires transferring a source label to a target node on the opposite side of a chordless cycle.
  • Real-world graph benchmarks: On TUDatasets, CIN achieves second place on the remaining datasets and performs best on biological and chemical datasets where rings are relevant.The evaluation covers eight biology, chemistry, and social-network benchmarks.
  • Real-world graph benchmarks: CIN achieves state-of-the-art performance on both ZINC and ZINC-FULL, including under a 100k-parameter constraint on ZINC.It remains on par with the best unconstrained baseline under edge-feature ablation.

6 Related Work, Discussion and Conclusion

The paper positions CWNs as a flexible, theoretically characterized extension of higher-order graph models, with strong molecular-benchmark performance and computational and theoretical scope boundaries.

  • Related Work: CWNs subsume existing simplicial methods while providing a comprehensive characterization of cellular message-passing expressiveness.The paper contrasts its framework with prior cell-complex work that neither studies expressive power nor experimentally validates performance.
  • Related Work: Higher-order k-GNNs become impractical at k ≥3, whereas CWNs can explicitly represent common chemical rings such as five- or six-membered cycles.The cited comparison attributes this difference to the computational complexity of higher-dimensional tensor representations.
  • Limitations: Exponential numbers of simple cycles can make general-graph lifting computationally expensive, requiring smaller 2-cells such as efficiently found triangles.Dimension-specific weights also increase parameter counts, although reduced depth can compensate on some molecular benchmarks.
  • Limitations: The theoretical analysis is restricted to regular cell complexes, leaving non-regular complexes and their trade-offs for future work.The paper states that some results might extend to non-regular complexes obtained through lifting transformations not studied here.
  • Discussion: Molecular-benchmark evidence suggests potential relevance to pharmaceutical applications such as drug discovery, while evidence for social-network adoption remains insufficient.The paper reports no immediate direct negative societal impacts within its stated scope.
  • Conclusion: The proposed cell-complex message-passing procedure combines graph lifting with decoupled computational and input graphs and performs strongly on diverse molecular benchmarks.The conclusion describes the procedure as provably powerful and motivated by a colour-refinement algorithm for testing cell-complex isomorphism.

Funding and Acknowledgements

The paper acknowledges external research support, contributor assistance, and the absence of competing interests.

  • Funding: YW and GM acknowledge support from the ERC under the EU’s Horizon 2020 programme.The acknowledgement cites grant agreement no 757983.
  • Funding: MB is supported in part by an ERC Consolidator grant, and the authors declare no competing interests.The acknowledgement identifies grant no 724228 (LEMAN).
  • Acknowledgements: The authors thank several researchers for feedback and for clarifying aspects of Benchmarking GNNs and SR graph experiments.The acknowledgement also notes a numerical precision issue in early SR graph experiments.

A.1 Cellular WL Results

The cellular Weisfeiler–Lehman framework defines colour refinement on regular cell complexes and supports graph liftings that add higher-dimensional structure. The resulting CWL procedures can exceed WL and, for selected liftings, match or exceed stronger simplicial and 3-WL comparisons.

  • Cellular colourings assign palette colours to cells, and refinement compares colour multisets across cell complexes.
  • CWL can remove co-boundary and lower-adjacency information without changing its expressive power on non-isomorphic cell complexes.Theorem 7 establishes equivalence with the complete adjacency rule.
  • CWL identifies whether a cell is an n-simplex after at most n + 1 iterations, separating it from non-simplices.The proposition states that the colours differ for every t ≥ n + 1.
  • Ring-based lifting distinguishes strongly regular graph pairs that differ in induced 4-, 5-, 6-, and 8-cycles, while clique lifting separates a pair differing in 4-cliques.CWL(4-IC) distinguishes the ring example, and clique-complex lifting is not less powerful than 3-WL.
  • CWL’s greater expressive power may extend beyond counting the substructures used by a lifting, but this is presented as a conjectural interpretation supported by SR experiments.The authors report evidence from reduced failure rates rather than a proof of this broader claim.

A.2 CW Network Proof

The proof establishes that CW Networks inherit Cellular WL’s expressive guarantees under suitable lifting transformations. These guarantees include strict superiority to WL and comparison with MPSNs and 3-WL.

  • A.2 CW Network Proof: CWNs inherit Cellular WL properties when their aggregation is injective and the network has enough layers for colouring convergence.The proof relates CWN features to Cellular WL colourings through inductive arguments.
  • A.2 CW Network Proof: CWNs using skeleton-preserving lifting transformations are at least as powerful as the WL test.
  • A.2 CW Network Proof: CWNs using the lifting maps from Corollary 15 are strictly more powerful than the WL test.
  • A.2 CW Network Proof: CWNs using the lifting transformations from Theorem 16 are not less powerful than 3-WL.
  • A.2 CW Network Proof: CWNs are at least as powerful as MPSNs with clique-complex lifting and strictly more powerful when cells are attached to cliques and rings or cycles.Ring-based CWNs are strictly more powerful than triangle-based MPSNs because triangles are rings of size 3.

B Computational Analysis

The analysis describes the computational cost of cellular message passing and graph lifting, alongside equivariance properties for cell permutations and orientations. It also identifies future convolutional extensions based on normalised Hodge Laplacians and sheaves.

  • B Computational Analysis: For fixed complex dimension and boundary sizes, cellular message passing has linear complexity in the size of the cell complex.The analysis calls this optimal because reading the cell complex itself requires linear time.
  • B Computational Analysis: Cycle- and induced-cycle-based lifting can use specialised listing algorithms, with planar graphs admitting especially efficient triangle and 4-ring listing.
  • B Computational Analysis: The implemented lifting procedure uses graph-tool’s VF2-based subgraph isomorphism and is parallelised across independent dataset graphs.The authors report modest effective preprocessing time on molecular benchmarks.
  • B Computational Analysis: CWNs are cell-permutation equivariant because their adjacency matrices transform consistently under permutations of cells.
  • B Computational Analysis: Orientation equivariance requires additional layer constraints, while normalised Hodge-Laplacian and sheaf-based convolutional extensions are left for future work.

E Experimental details and additional results

The experimental architecture is implemented as a PyTorch and PyTorch Geometric model operating on ring-lifted two-dimensional cell complexes. CIN layers update cells across dimensions and use dimension-wise readouts for graph prediction.

  • E Experimental details and additional results: The implementation uses PyTorch, PyTorch Geometric, graph-tool, and Joblib, with lifting operations parallelised through Joblib.
  • E Experimental details and additional results: All experiments use ring-lifted 2-dimensional complexes containing nodes, edges, and induced cycles up to a selected size as 0-, 1-, and 2-cells.Original node features or learned node embeddings initialize 0-cells, while higher-dimensional cell features depend on the benchmark.
  • E Experimental details and additional results: Cellular message passing layers update representations of p-cells, and stacking L such layers defines the Cell Isomorphism Network architecture.
  • E Experimental details and additional results: CIN forms dimension-wise mean or sum readouts before combining cell representations into an overall complex representation for prediction.
  • E Experimental details and additional results: Training uses dense nonlinear layers with Batch Normalization and ReLU activations, followed by Adam optimisation.

E.4 Additional experimental details

The additional experiments cover graph isomorphism, signal replication, ring-size transfer, molecular, and social or biological graph benchmarks. Dataset-specific configurations vary in labels, features, model depth, and training procedures.

  • E.4 Additional experimental details: The CSL benchmark contains 150 4-regular graphs with 48 nodes spanning 10 isomorphism classes determined by the skip number.
  • E.4 Additional experimental details: The SR experiments use untrained double-precision models and classify complex embeddings as different when their L2 distance exceeds ϵ = 0.01.
  • E.4 Additional experimental details: RingTransfer uses 5,000 training graphs with five uniformly represented labels and a CIN with three message passing layers independently across ring sizes.
  • E.4 Additional experimental details: TUDatasets include molecular and protein tasks such as mutagenicity, carcinogenicity, enzyme recognition, and cancer-cell activity classification.
  • E.4 Additional experimental details: ZINC predicts penalised water-octanol partition coefficient logP, while Mol-HIV predicts a binary label for HIV-replication inhibition using scaffold-based data splits.

E.5 Ablation study on ZINC

The ZINC ablation evaluates how including rings affects CIN performance when edge features and matched hyperparameters are retained. Removing rings reduces overall performance, although the ring-free model remains stronger than other ring-agnostic baselines.

  • Removing 2-cells decreases the overall performance of both CIN No-Rings variants on ZINC.The variants neglect rings during message passing while retaining edge features and the original CIN hyperparameters.
  • CIN No-Rings is outperformed by GSN and HIMP, which incorporate cycle-counting information or Junction Tree message passing.
  • CIN No-Rings still outperforms all other ring-agnostic baselines.The authors attribute this strength to richer modelling of edge signals through updates involving incident nodes.
  • Table 9 reports the ZINC ablation with edge features and identifies benefits from integrating rings into message passing.
Loading 2106.12575v3…