PaperlayerView exact revision on arXiv

Source-linked AI summary

Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks

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

arXiv:2103.03212v2cs.LGcs.SI

TL;DR

Graph-based message passing is limited in representing higher-order interactions and in distinguishing some non-isomorphic graphs. The paper introduces SWL and MPSNs on simplicial complexes, showing stronger expressivity than WL, parity with or superiority to 3-WL in stated comparisons, and higher linear-region complexity than GNNs and SCNNs. These results support simplicial message passing as a higher-order alternative, subject to stated theoretical assumptions and scope boundaries.

  • Problem

    Message-passing GNNs are limited by WL-level expressivity, including difficulty detecting graph structures such as triangles and cliques, while graphs do not capture multi-level interactions.

  • Method

    The paper introduces SWL for simplicial-complex isomorphism testing and MPSNs that perform message passing across simplicial complexes, including clique-complex lifting for graphs.

  • Results

    SWL and MPSNs are strictly more powerful than WL, are not less powerful than 3-WL, and MPSNs have higher linear-region complexity than GNNs and SCNNs.

  • Takeaways & Limitations

    Simplicial message passing provides a theoretically stronger framework for higher-order relational modelling and graph distinction than conventional WL-based message passing.

  • Takeaways & Limitations

    The pruned adjacency result is theoretical and does not imply that excluded adjacencies are useless in practice; some linear-region bounds assume invertible aggregation functions.

Abstract

from arXiv · show

The pairwise interaction paradigm of graph machine learning has predominantly governed the modelling of relational systems. However, graphs alone cannot capture the multi-level interactions present in many complex systems and the expressive power of such schemes was proven to be limited. To overcome these limitations, we propose Message Passing Simplicial Networks (MPSNs), a class of models that perform message passing on simplicial complexes (SCs). To theoretically analyse the expressivity of our model we introduce a Simplicial Weisfeiler-Lehman (SWL) colouring procedure for distinguishing non-isomorphic SCs. We relate the power of SWL to the problem of distinguishing non-isomorphic graphs and show that SWL and MPSNs are strictly more powerful than the WL test and not less powerful than the 3-WL test. We deepen the analysis by comparing our model with traditional graph neural networks (GNNs) with ReLU activations in terms of the number of linear regions of the functions they can represent. We empirically support our theoretical claims by showing that MPSNs can distinguish challenging strongly regular graphs for which GNNs fail and, when equipped with orientation equivariant layers, they can improve classification accuracy in oriented SCs compared to a GNN baseline.

1. Introduction

The paper argues that graph message passing is limited for higher-order interactions and introduces simplicial-complex models to address this limitation. It develops SWL and MPSNs, establishing stronger expressivity and greater functional complexity than conventional graph approaches.

  • Motivation: Message-passing GNNs match the WL test when their local aggregators are injective, limiting their ability to detect structures such as triangles and cliques.This motivates architectures that represent higher-order interactions explicitly.
  • Motivation: Simplicial complexes are proposed as a middle ground between graphs and more general hypergraphs for modelling local higher-order interactions.They also connect to algebraic and differential topology and geometry.
  • Contributions: The paper introduces SWL for distinguishing non-isomorphic simplicial complexes and MPSNs as a message-passing architecture motivated by that test.MPSNs extend graph neural networks and spectral simplicial convolutions.
  • Contributions: SWL and MPSNs are strictly more powerful than conventional WL and are not less powerful than the 3-WL test.The comparison concerns distinguishing non-isomorphic structures.
  • Contributions: MPSNs have higher functional complexity than GNNs and SCNNs under bounds on representable linear regions.The paper also provides optimal bounds for SCNNs.

2. Background

The background defines simplicial complexes, their simplices, boundary relations, and orientations. It also introduces signed boundary matrices and the Hodge Laplacian used for oriented simplicial signals.

  • Simplicial complexes: A simplicial complex is a nonempty collection of subsets closed under taking subsets and containing every singleton vertex subset.This closure property ensures that every face of a simplex is included.
  • Simplicial complexes: A k-simplex has k + 1 vertices; vertices, edges, and triangles are 0-, 1-, and 2-dimensional simplices, respectively.The dimension tracks one less than the simplex cardinality.
  • Incidence relations: The boundary incidence relation σ ≺ τ holds when σ is a direct subset of τ with no intermediate simplex.It identifies which simplices lie on another simplex’s boundary.
  • Orientations: An orientation equips each simplex with an ordering of its vertices, although the chosen orientation is mathematically arbitrary.Equivalent vertex permutations can represent the same directional movement.
  • Operators: Signed boundary matrices encode whether a lower-dimensional simplex appears with positive or negative orientation in a higher-dimensional simplex.The unsigned matrix records incidence without orientation signs, while L0 is the graph Laplacian.

3. Simplicial WL Test

SWL extends WL colour refinement from graphs to simplicial complexes by aggregating colours across several adjacency types. Clique-complex lifting lets it distinguish graph pairs that WL or even 3-WL cannot distinguish.

  • SWL procedure: SWL assigns colours to simplices and repeatedly hashes multisets of colours from their adjacent simplices until a stable colouring is reached.Different colour histograms at any level indicate non-isomorphism.
  • Adjacencies: SWL considers boundary, co-boundary, lower, and upper adjacencies between simplices.These generalize familiar graph incidences and neighbourhoods to multiple dimensions.
  • Expressivity and complexity: A pruned SWL adjacency choice preserves the general test’s expressive power while giving linear complexity in the total number of simplices.The paper notes that other adjacency combinations may also preserve expressive power.
  • Clique complexes: Clique-complex lifting maps every graph clique to a simplex, enabling SWL to distinguish graph pairs that WL cannot distinguish.The transformation is injective over non-isomorphic graphs.
  • Clique complexes: SWL distinguishes the Rook’s and Shrikhande graphs in SR(16,6,2,2), whereas the 3-WL test fails.Their clique complexes differ because only the Rook’s graph contains 4-cliques.

4. Message Passing Simplicial Networks

MPSNs implement simplicial message passing across multiple adjacency types and match SWL expressivity with sufficient layers and injective aggregation. The architecture supports symmetry handling, extends spectral convolutions, and has favourable complexity under restricted adjacencies.

  • Architecture: MPSNs update each simplex by combining messages from the four simplicial adjacency types with its previous representation.The global readout aggregates feature multisets across all simplex dimensions.
  • Expressivity: With sufficient layers and injective neighbourhood aggregators, MPSNs are as powerful as SWL.MPSNs are also at most as powerful as SWL, establishing equality under these conditions.
  • Expressivity: Clique-complex lifting yields an MPSN that is more powerful than WL for distinguishing non-isomorphic graphs.Boundary and upper adjacencies suffice for this result.
  • Spectral connections: MPSNs generalise certain spectral convolution operators defined over simplicial complexes.The connection is derived from higher-order simplicial Hodge-Laplacian constructions.
  • Equivariance: MPSN layers are simplex-permutation equivariant and can be made orientation equivariant using relative orientation signs and odd message, aggregation, and update functions.An invariant readout can be used after stacking equivariant layers.
  • Complexity: Using only boundary and upper adjacencies gives linear complexity in complex size, whereas lower adjacencies can produce quadratic worst-case complexity.Clique listing can exploit graph sparsity and is strictly better than the Ω(n^k) cost of all k-GNNs in the stated analysis.

5. Simplicial Networks by Linear Regions

The section compares ReLU GNN, SCNN, and MPSN layers through the number of representable linear regions. MPSNs permit cross-dimensional simplex interactions and achieve greater functional complexity than the compared architectures under the stated settings.

  • Expressivity measure: The analysis uses linear-region counts to compare the expressive power of graph, simplicial convolutional, and message passing simplicial networks.The focus is on linear message functions with sum aggregation followed by ReLU.
  • GNNs: A ReLU GNN layer has an optimal upper bound on its number of linear regions when its linear aggregation function is invertible.This applies to several commonly used graph convolutions, subject to the invertibility condition.
  • SCNNs: An SCNN layer has an optimal upper bound whose product structure reflects the absence of interactions between features on different simplex dimensions.The GNN bound is recovered as the special case p = 0.
  • MPSNs: MPSNs allow features on simplices of different dimensions to interact through message passing and ReLU updates.Their layer uses adjacency matrices for same-, lower-, and higher-dimensional simplex interactions.
  • Comparison: The MPSN lower bound surpasses the SCNN upper bound, while Figure 4 shows linear-region counts increasing from GNN to SCNN to MPSN.The illustrated case uses a triangular complex with S0 = S1 = 3, S2 = 1 and output dimension m = 3.
  • Populated higher features: When only vertex features are available, populating higher-order features as linear functions of vertex features can yield RMPSN ≥ RSCNN.The paper presents this as a strategy for exploiting simplicial-complex structure while increasing functional complexity.

6. Experiments

Experiments evaluate simplicial message passing on strongly regular graphs, real-world graph classification benchmarks, and oriented edge-flow trajectories. Across these settings, higher-order triangle information and orientation-equivariant processing improve discrimination or generalization relative to graph-based baselines.

  • Strongly Regular Graphs: SIN distinguishes the majority of strongly regular graph pairs across all families by accessing clique information unavailable to standard GNNs.It also outperforms the MLP-sum baseline on certain families.
  • Edge-Flow Classification: The synthetic trajectory benchmark contains two classes associated with paths through different corners of a complex with two holes.The classes approximately correspond to orthogonal directions in the harmonic-function space associated with the holes.
  • Edge-Flow Classification: The real-world benchmark uses 160 training and 40 test ocean-drifter trajectories around Madagascar, with clockwise and counter-clockwise flows around an island-shaped hole.Test trajectories use random orientations to challenge non-invariant models.
  • Edge-Flow Classification: Triangle-aware and orientation-equivariant models generalize better on trajectory classification than models lacking these properties.The GNN performs worse because it cannot extract the harmonic component, while the ReLU model fits fixed-orientation training data but fails on randomly oriented test flows.
  • Real-World Graph Classification: The graph-classification evaluation lifts input graphs to 2-complexes by representing triangles as 2-simplices and compares SIN with graph kernels and GNNs.Performance is reported using best mean test accuracy from 10-fold crossvalidation.

7. Discussion and Conclusion

The discussion positions MPSNs as a higher-order, locally operating alternative to standard GNNs, extending simplicial expressivity beyond pairwise interactions. The conclusion reports theoretical gains, symmetry properties, linear-region analysis, and empirical validation across several tasks.

  • 7. Discussion and Conclusion: MPSNs retain local operations while performing message passing on simplices rather than only at the node level.This distinguishes them from related higher-order graph models whose message passing remains node-based.
  • 7. Discussion and Conclusion: Clique complexes are one graph-lifting choice, while other transformations could emphasize task-relevant motifs or target cubical and cell complexes.The discussion therefore presents the framework as extensible beyond clique-based simplicial representations.
  • 7. Discussion and Conclusion: The paper concludes that SWL and MPSNs are more expressive than WL when graphs are lifted through clique complexes.It also reports simplex permutation equivariance, possible orientation equivariance, and superior linear-region expressivity relative to GNNs and SCNNs.
  • 7. Discussion and Conclusion: Empirical validation covers challenging non-isomorphic strongly regular graphs, real-world graph classification, edge-flow classification, and two-dimensional linear-region slices.These experiments are presented as confirmation of the theoretical results.

A. Proofs of SWL Theory Results

The proofs establish refinement relationships among simplicial colourings and show that SWL matches or exceeds established graph-isomorphism tests, with strict gains on suitable clique complexes.

  • Definitions: A simplicial colouring assigns colours to simplices, while refinement means equal colours under the finer colouring imply equal colours under the coarser one.Equivalent colourings refine each other.
  • Refinement arguments: If one colouring distinguishes two complexes by their colour multisets, any colouring refining it also distinguishes them.This transfers distinguishing power from a coarser colouring to a finer one.
  • SWL update rules: SWL with HASH is as powerful as SWL with the generalised update rule, because the restricted rule can recover the additional co-boundary information by induction.The proof establishes mutual refinement between the two update procedures.
  • Comparison with WL: SWL is at least as powerful as WL because higher-dimensional simplex information refines vertex colouring, while graph instances retain the WL setting at vertex level.The argument applies to simplicial complexes and graphs, since graphs are simplicial complexes.
  • Strict separation: WL fails to distinguish a graph pair whose clique complexes SWL separates because one complex contains two triangles and the other contains none.The higher-level simplex histograms provide the strict separation.
  • Strongly regular graphs: No pair of strongly regular graphs in SR(n,d,λ,µ) is distinguished by 2-FWL, whereas SWL distinguishes the Rook’s 4x4 and Shrikhande graphs in SR(16,6,2,2).The 2-FWL proof relies on colourings remaining constant within its initial partitions.

B. Proofs of Linear Regions Results

The linear-region analysis represents ReLU layers through central hyperplane arrangements and derives region-counting bounds for GNN and SCNN architectures.

  • Hyperplane arrangements: A ReLU partitions its input space into two linear regions, and a layer of ReLUs induces a hyperplane arrangement whose regions are the function’s affine pieces.The arrangement consists of the hyperplanes separating individual ReLU regions.
  • Region bounds: For M central hyperplanes in R^N in general position, the arrangement attains the maximum possible number of regions among central arrangements.The result is used as an upper bound for piecewise-linear network layers.
  • Constrained arrangements: The main difficulty is that constrained arrangements need not be in general position; the analysed layers impose block Kronecker-product structure on their normal vectors.This structure motivates architecture-specific region bounds.
  • GNN bounds: GNN layer arrangements decompose as direct sums across input-feature columns, so their total region count is the product of the counts for the component arrangements.Each component arrangement has normals spanning a subspace of dimension at most d.
  • SCNN bounds: SCNN region counts are obtained similarly by decomposing arrangements across simplices within each dimension and then multiplying across dimensions.The construction treats each n-dimensional simplex and combines dimensions through direct sums.

B.3. MPSNs

The MPSN analysis compares its induced hyperplane arrangements with SCNN arrangements and shows that higher-dimensional interactions can increase representational complexity, including when higher features are populated from vertices.

  • MPSN representation: The entire MPSN layer can be written as a piecewise-linear map ψ(WH), enabling its linear-region count to be analysed through the matrix W.The representation concatenates the layer expressions over all simplex dimensions.
  • Region comparison: Rank comparisons between MPSN and SCNN row submatrices provide lower bounds on MPSN region counts relative to SCNN.The argument applies a rank-based monotonicity proposition for central arrangements.
  • MPSN bounds: Theorem 19 combines an architecture-specific upper bound with the general central-arrangement upper bound and a rank-based lower bound for MPSNs.The bounds depend on feature dimensions, simplex counts, output dimension, and interaction matrices.
  • Matrix structure: MPSN’s matrix W is lower block triangular, reflecting interactions among boundary, same-dimensional, and co-boundary simplices.This structure is contrasted with the block-diagonal matrix of SCNNs.
  • Populated higher-features: Populating higher-dimensional input features as linear functions of vertex features can increase MPSN complexity when only vertex features are initially available.This setting is analysed against a corresponding SCNN layer.
  • Populated higher-features: For the populated setting, RMPSN ≥ RSCNN, with strict inequality for certain complexes and feature dimensions; Figure 7 illustrates more MPSN regions than GNN/SCNN.The comparison concerns output vertex features under the stated feature and layer parameters.

C. Relationship to Convolutions

The paper relates simplicial message passing to Hodge-Laplacian convolutions and formalizes permutation and orientation equivariance. MPSNs use upper and lower simplex interactions, while prior convolutional schemes can be recovered as restricted message-passing cases.

  • Hodge-Laplacian structure: Hodge-Laplacian convolutions are built from boundary operators whose products encode upper and lower simplex adjacencies.The relation BpBp+1 = 0 expresses that a simplex boundary has no boundary.
  • Hodge-Laplacian structure: SNN convolutional filters are R-degree polynomials of the Hodge p-Laplacian, with small R providing spatial localization.The convolution acts on p-cochains, which assign real-valued signals to p-simplices.
  • Message-passing interpretation: MPSN message passing separates upper and lower adjacencies and can aggregate extended upper- and lower-neighborhoods.The extended neighborhoods include p-simplices reachable within distance R through upper or lower adjacency.
  • Relations to prior convolutions: The convolutional schemes of Ebli et al. and Bunch et al. can be rewritten within the MPSN framework, although Bunch et al. models cross-dimensional interactions.The Bunch et al. derivation is given for edges, with vertex and triangle cases as special cases.
  • Equivariance: The framework is permutation equivariant under simultaneous permutation of simplex features and boundary matrices.Permutation invariance is separately defined for functions whose outputs do not change under these permutations.
  • Equivariance: When the activation is odd, the described MPSN layer is orientation equivariant because messages incorporate relative simplex orientations.The layer uses sum aggregation and combines incoming messages with linearly transformed features before applying the activation.

E. Cubical Complexes

The paper discusses extending simplicial message passing and Weisfeiler–Lehman testing to cubical complexes. It identifies cubical complexes as a future direction while noting cases where graph-based tests miss topological distinctions.

  • Extension to cubical complexes: The proposed message-passing approach can extend to cubical complexes, and the authors plan this extension as future work.Cubical complexes are presented as a theoretically similar type of cell complex used in applications.
  • Extension to cubical complexes: Message passing and a Weisfeiler–Lehman test could be directly implemented for cubical complexes.The paper notes that cubical complexes may suit certain datasets better than simplicial complexes.
  • Topological distinctions: Two non-isomorphic cubical complexes can have isomorphic underlying graphs, so graph structure alone may miss their distinction.The paper also states that the clique complexes of those underlying graphs are isomorphic.
  • Topological distinctions: The paper notes that SWL based on clique complexes also fails to distinguish the non-isomorphic molecular graphs shown in Figure 9.This motivates considering tests that account more directly for topological information, such as homeomorphism tests.
  • Future applications: Digital images are identified as a natural future application where cubical complexes may provide computational speed-ups over simplicial complexes.The proposed next step is to evaluate such datasets more naturally modeled by cubical complexes.

F. Additional Experimental Details

The experiments cover strongly regular graphs, trajectory tasks, and standard graph-classification benchmarks using matched architectures and specified orientation treatments. The implementation includes orientation-equivariant and non-equivariant MPSN variants alongside GNN baselines.

  • Experimental setup: Strongly regular graph experiments embed clique complexes with an untrained 5-layer MPSN into 16-dimensional representations.Graphs are treated as non-isomorphic when their embedded Euclidean distance exceeds the threshold ε = 0.01.
  • Strongly regular graphs: The strongly regular graph comparison includes a GIN baseline whose inability to distinguish any pair was empirically verified.This is theoretically consistent with GIN’s expressive power being upper-bounded by 1-WL.
  • Orientation handling: Training complexes use a fixed arbitrary orientation, whereas each test trajectory receives a random orientation through ±1 diagonal transformations.This setup evaluates behavior under orientation changes between training and testing.
  • Orientation handling: MPSN Id and MPSN Tanh are orientation equivariant, while MPSN ReLU is not.The distinction follows from the layer being orientation equivariant when its activation is odd.
  • Trajectory prediction: Trajectory experiments use four layers with hidden size 64, batch size 64, and initial learning rate 0.001.Training lasts 100 epochs on the synthetic dataset and 250 epochs on the ocean drifter dataset.
  • Graph classification: The graph-classification experiments lift each graph to a clique 2-complex and initialize higher-dimensional simplices with means of constituent node features.The SIN model combines node- and triangle-level embeddings for final class predictions.

F.4. Implementation & Availability

The authors implemented the experiments in PyTorch and PyTorch Geometric, using Gudhi’s simplex-tree data structure for clique complexes. They provide an official repository supporting oriented simplicial complexes and higher-order batching.

  • Software: The experiments use PyTorch and PyTorch Geometric to implement the simplicial message-passing scheme.
  • Data structures: Clique-lifting procedures use Gudhi’s simplex-tree data structure.For graphs with 10^6 nodes, simplex trees are reported to generate clique complexes at fixed dimension in cost linear in the number of complex simplices.
  • Availability: The official code repository supports simplicial-complex datasets, oriented complexes, higher-order batching, and clique complexes.
Loading 2103.03212v2…