Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity
Authors: Yam Eitan
Yoav Gelberg
Guy Bar-Shalom
Fabrizio Frasca
Michael M. Bronstein
Haggai Maron
Venue: ICLR 2025 Oral (2025)
Keywords: Topological Deep Learning
Message Passing
Higher Order Message Passing
Expressivity
Graph Neural Networks
GNNs
Topology
Homology
Symmetry
Primary area: learning on graphs and other geometries & topologies

Abstract: Topological deep learning (TDL) is a rapidly growing field that seeks to leverage topological structure in data and facilitate learning from data supported on topological objects, ranging from molecules to 3D shapes. Most TDL architectures can be unified under the framework of higher-order message-passing (HOMP), which generalizes graph message-passing to higher-order domains. In the first part of the paper, we explore HOMP's expressive power from a topological perspective, demonstrating the framework's inability to capture fundamental topological and metric invariants such as diameter, orientability, planarity, and homology. In addition, we demonstrate HOMP's limitations in fully leveraging lifting and pooling methods on graphs. To the best of our knowledge, this is the first work to study the expressivity of TDL from a topological perspective. In the second part of the paper, we develop two new classes of architectures -- multi-cellular networks (MCN) and scalable MCN (SMCN) -- which draw inspiration from expressive GNNs. MCN can reach full expressivity, but scaling it to large data objects can be computationally expansive. Designed as a more scalable alternative, SMCN still mitigates many of HOMP's expressivity limitations. Finally, we design new benchmarks for evaluating models based on their ability to learn topological properties of complexes. We then evaluate SMCN on these benchmarks as well as on real-world graph datasets, demonstrating improvements over both HOMP baselines and expressive graph methods, highlighting the value of expressively leveraging topological information.

Published as a conference paper at ICLR 2025
TOPOLOGICAL BLINDSPOTS: AND EXTENDING TOPOLOGICAL DEEP LEARNING THROUGH THE LENS OF EXPRESSIVITY
UNDERSTANDING
Yam Eitan 1
Yoav Gelberg 22
Guy Bar-Shalom²
Fabrizio Frasca'
Michael 2ronstein 2.3
Haggai Maron
Technion Israel Institute of Technology
University of Oxford
3 AITHYRA
NNVIDIA Research
ABSTRACT
Topological deep learning (TDL) is rapidly growing field that seeks to leverage topological structure in data and facilitate learning from data supported on topo- logical objects, ranging from molecules 3D shapes. Most TDL architectures can be unified under the framework of higher-order message-passing (HOMP), which generalizes graph message-passing part of the paper, we explore HOMP's expressive power from a topological perspective, demonstrating the framework's inability capture fundamental topological and metric invariants such as diameter. orientability, planarity. and homology. In addition, we demonstrate HOMP's limitations in fully leveraging lifting and pooling methods on graphs. To the best of our knowledge, this is the first work to study the expressivity of TDL. from a topological perspective. In the second part of the paper, we develop two new classes of architectures multi-celuular networks (MCN) and scalable MCN (SMCN) which draw inspi- ration from expressive GNNs. MCN can reach full expressivity, but scaling large data objects can be computationally expansive. Designed as a more scalable alternative, SMCN still mitigates many of HOMP's expressivity limitations. Finally, we create new benchmarks for evaluating models based on their ability learn topological properties of complexes. We then evaluate SMCN these benchmarks and on real-world graph datasets, demonstrating improvements over both HOMP baselines and expressive graph methods, highlighting the value of expressively leveraging topologiaa information. Code and data are available at htttp:://itthu/ compy//b.occoooo/v/.e///// rSMNMCN
higher-order domains. In the first
INTRODUCTION
Topological Deep Learning (TDL) is an emerging field focused on learning from data supported on topological objects. Higher-order ressage-passing (HOMP) (Haji) et al. [022a b) has emerged as a key framework in TDL, unifying architectures designed for various topological data types. Originally introduced for simplicial complexes (Bodnar al. 2021b), HOMP has been successively adapted for cellular complexes (Bodnar et al. 2 Hajij et al. 2020), and more recently, for combinatorial complexes (Hajij et al. 2022a b). Each adaptation is a direct generalization of its predecessor. The HOMP framework extends traditional message-passe passing neural networks (MPNNs) (Gilmer et al. 2017). widely used in graph learning, to higher-order topological domains.
Despite their widespread adoption in various graph learning applications, MPNNs are known to struggle with expressivity limitations, often failing to distinguish even simple non-isomorphic graphs (Morris et al. 2019: Xu et al.) 20188. This realization has led substantial body of work
dedicated to developing more expressive graph architectures (Morris et al. (2233)
|2033|Maron Maron et al. 2019
Morris al. 2019: Bevilacqua et al.] 202T Abboud al. 2020; Bouritsas et al.] (022). Given the similarity between HOMP and MPNNs, a natural question arises: What are the limitations of higher-order message-passinn architectures in distinguishing topological objects? This question, highlighted in a recent position paper (Papamarkou et al.) 2024), is the main focus of this paper.
Equal contribution.

---

Published as a conference paper at ICLR 2025
(a) Diameter
(b) Oriemaailltyyplanaritty
(c) Homology
Figure 1: Pairs of CUOMP-indistinguise
complexes differing fundamental metric/topological properties that. In Figure [[a] tori with different diameters (top 20, bottom 22); in Figure [(b] Möbius strip and a cylinder differing in both orientability and planarity; in Figure I(c)
a torus and
a pair of disconnected tori which have different homology groups.
We address this question from a topological perspective. First, we introduce a topological criterion designed to identify cases in which a pair of complexes is indistinguishable by HOMP. We then use this criterion to prove HOMP's inability to differentiate between complexes based on several fundamental topological and metric invariants, including diameter, orientability, planarity, and homology groups. These limitations are particularly noteworthy, as TDL's main goal is to leverage topological structure in data. In fact, several methods directly inject information closely related to some of the above properties into pre-existing framewroks (Horn et al., [021 Chen et al. [021] Rieck [023] Zhang al. (023c).. Additionally, since many topological data objects are constructed by lifting graph data, we examine HOMP's limitations in expressively leveraging lifting and pooling
methods to distinguish graphs.
In the second part of the paper, we introduce new class of TDL architectures called multi-cellular networks (MCN) designed to address HOMP's expressivity limitations. MCN draws inspiration
from higher-order graph architectures (Maron et al. 2019 Morris al. 2019 Keriven & Peyré
2019 Azizian & Lelarge 2020), which successfully resolve expressivity limitations in MPNNs.
MCN utilizes the equivariant linear layers introduced in Maron al.) (2018) and integrates them into the HOMP pipeline, resulting in architectures reminiscent of Invariant Graph Networks (IGNs) introduced the same paper. We prove that MCN can reach full expressivity in distinguishing non-isomorphic complexes. Recognizing the scalability challenges of both IGNs and MCN, we propose an alternative called scalable MCN (SMCN). SMCN models apply expressive graph layers often used practical alternatives to IGNs complex. We prove that SMCN still mitigates many of HOMP's expressivity limitations.
graph structures defined the cells of the
We empirically evaluate SMCN on several weal-world (lifted) graph benchmarks and find perfor- mance gains over both standard HOMP baselines and expressive GNNs, highlighting the value of expressively leveraging topological information. Additionally, we design three benchmarks to assess TDL architectures' ability to capture topological and metric information. The first, called the Torus Dataset, a BREC-like (Wang & Zhang 2024) dataset consisting of pairs of cellular complexes com- prising one more disjoint tori. Models are tasked with separating each pair in statistically signif- icant way. The two other benchmarks evaluate models based on their ability to predict topological properties of complexes obtained by lifting molecular graphs from ZINC (Sterling & Irwin 2015).
Our contributions. Summarizing, the key contributions of this paper are as follows: (1) We provide a comprehensive analysis of HOMP's expressive power, evaluating its ability to capture topologi- cal and metric invariant and leverage lifting and pooling methods. (2) We introduce multi-cellular networks (MCN), a novel class of TDL. models, inspired by IGNs, which can provably reach full expressivity. (3) We develop SMCN, scalable version of MCN that addresses HOMP's expressiv- ity limitations while maintaining computational efficiency. (4) We construct three benchmarks for assessing the topological expressivity of TDL architectures. (5) We empirically evaluate the per- formance of SMCN, demonstrating improvements over both standard TDL methods and expressive graph models, highlighting the benefits of expressively leveraging topological information.
2 PREVIOUS WORK
Topological Deep Learning. TDL architectures enable learning from data supported topological objects, traditionally focusing on four domains: hypergraphs, simplicial complexes, cellular com- plexes, and combinatorial complexes. The prominent framework for the latter three is higher-order
2

---

Published as a conference paper at ICLR 2025
message-passingg (HOMP). Originally introduced for simplicial complexes (Bodnar et al. 202 and later extended to cellular (Bodnar et al. 2021a Hajuj et al. 2020) and combinatorial complexes (Hajij et al., 2022a b), HOMP architectures ac achieve strong experimental results and have been shown to enhance the expressive power of MPNNs. Another approach in TDL research incorporates pre- computed topological information into existing models like MPNNs (Hom et al. 202T] Chen al.) 2021 |ieck| 2023) and HOMP (Verma et al. 2024, Buffelli et al., 2024). These methods enhance the expressive power of the base models and show strong experimental results, highlighting the value of integrating topological features. Most prior work is focused on the expressivity of TDL models with respect to graphs, the ability of HOMP to capture topological and metric invariants of complexes without relying on pre-computation remains unexplored.
Expressive power of GNNs. The expressivity of GNNs typically evaluated in terms of their sep- aration power, i.e. their ability to assign distinct values to non-isomorphic graphs. Seminal works by Morris et al. 2019) and Xu et al. (018)) demonstrate that the expressive power of MPNNs is equiv- alent to that of the I-WL test (Weisfeiler & Leman 1968). These findings inspired the development of more expressive GNNs, with expressive power surpassing that of the 1-WL test, albeit often requiring greater computational resources. MMrris et al. (2019) and Maron et al. (2018) propose architectures that are as expressive as the k-WL test with O(n*) runtime and memory complex- ity. Various other expressive GNNs have been introduced in the literature, utilizing techniques such as random features (Abboud et al.) 2020), substructure counts (Bouritsas et al.] (2022), equivariant polynomials (Maron et al. 2019]0191 Puny et al. (023), processing sets of subgraphs (Bevilacqua al.) 2021 Frasca et al.) 2022 Zhang et al. 2023b; Zhang & Li 2021 Cotta et al. (022) and more. We use these frameworks, specifically the architectures proposed Maron et al. (2019) and Zhang al. 2023b): BBar-Shalom et al. (2024) to construct efficient and expressive models for combinatorial complexes. BBambergerr(222)
offers a perspective on MPNN expressivity through the lens of graph coverings. We extend their work to combinatorial complexes and use it to analyze the topological expressivity of HOMP, For comprehensive review of expressive graph architectures, refer to the following surveys: Jegelka 2022). Morris et al. (2023); Zhang et al. (202aa).
PRELIMINARIES
Notation. We denote [m] (1, n1.....n.. The size of set S is denoted by |S]. + and X denote aggregation functions, where ① is permutation invariant. Bold lowercase letters denote tuples of integers e.g. k = (ko....,ke) ke). e, denotes the tuple with one at the i-th position and zeros elsewhere.
Combinatorial complexes. Combinatorial complexes (CCs) are a class of higher-order objects that can flexibly represent many types of hierarchical data. Most topological data domains, including simplicial complexes, cellular complexes, and hypergraphs, can be considered subclasses of combi- natorial complexes. Therefore, throughout the paper, all data objects are represented as CCs.
Definition 3.1 (Combinatorial complex). A combinatorial complex (CC) is a 3-tuple (S, rk) comprising a node set S, a cell set X C P(S) 0. and a rank function rk X + Ezo such that Vs S. (5} E X, rk((s)) = 0, and Vx, y X x y + rk(x) S rk(y).
The set of r-rank cells (r-cells) is called the r-skeleton and is denoted by X, rk rr), its size is denoted by n, := |K* the dimension of CC is e = max rk(z). We often simplify the notation and use X' to denote the entire CC. For definitions of simplicial and cellular complexes, we refer the reader to Bodnar et al. (2021a) and Bodnar et al. (2021b).
Neighborhood functions. Neighborhood functions are a key component in HOMP, facilitating dynamic aggregation of information across cells. Formally, a neighborhood function can be any function N X' - P(X), but the most common neighborhood functions are
(1) The (r1,
and co-adjacency, defined by
s.t. N. C 2}. coA (x) = tu Xr, 3> Nr, s.t. 2 C x,
Aniro (x) = {u Xr, 3z E Xr,
for E Xr, and Ar. (x) = Ao .2 (x) = @ for x & Xr.
(2) The (r1, (h,rr2)-pper and lower incidence, defined by Br,rz (x) = (v Xrz x Ev), B (T) (v E Ex,, [C
(2)
3

---

Published as a conference paper at ICLR 2025
for X and Br (2) Br. =0 for & Xx1-
We call the neighborhood functions defined above natural neighborhood functions, a collection denote by N nat- See Appendix A.2 for an illustration. Given enumeration of the cells, neighborhood function can be represented in matrix form. For example, given a graph G = (V.8) V) and X1 = E, the matrix
viewed as a one dimensional CC through S V, X = {fv) forms of the neighborhood functions 1 and B are the graph adjacency and incidence matrices respectively.
Cochain spaces. Data defined over an E-dimensional CC can be viewed as a collection of functions (h, X, Rd
) v Each of these functions is called cochain cell feature map. The vector space of all cochains over cells of rank is denoted by C* (X, (d)r or C The feature associated with a cell Xr is denoted by (z), (hr) or simply h..
Higher-order message-passingg Higher-order message passing (HOMP) (Hajij et al. 2022b) is general computational framework for processing in- formation supported on higher-order domains by exchanging messages across cells. Let / = ... N be a collection of neighborhood functions; given an initial cochain h()) h, HOMP recursively defined via the fol- lowing update rule
out
An,1
Ag,0
Bo,
(h (l()) )
h ((+1))
MLP(() s,rk(w))
i= (EN
C
C2
where h is the feature associated with cell æ E X at layer and / is non- linear activation. In the rest of the paper, we assume N C wmtt- Similarly
Figure 2: HOMP
Tensor diagram.
to MPNNs, the HOMP framework encompasses many TDL architectures, including architectures
for simplicial complexes Bodnar et al.] (20215), cellular complexes Hajij et al. (2020); Bodnar et al. (021a): Giusti et al. (2023). and combinatorial complexes Hajij et al. (2022a
Tensor diagrams. Hajij et al. (2022a) introduce tensor diagrams, a DAG notation scheme for nav- igating the rich space of possible HOMP architectures. Tensor diagrams allow for selective aggre- gation over different neighborhood functions for different cochain spaces in different layers of the network. The nodes of tensor diagram represent cochain spaces, and the edges represent neigh- borhood functions. The signal flows from each level of the diagram to the next via the update rule specified in Equation 3] where aggregation is performed only over neighborhood functions associ- ated with the incoming edges"] See Figure 2 for an illustration of tensor diagram and Hajij et al. (2022b) for an in-depth overview.
4 EXPRESSIVITY LIMITATIONS OF HIGHER-ORDER MESSAGE-PASSING
The expressivity of graph models is often evaluated in terms of their ability to assign different values to non-isomorphic graphs. Similarly, study HOMP's 's ability to distinguish non non-isomorphic CC
4.1 A TOPOLOGICAL CRITERION FOR HOMP-INDISTINCUISIAIII
The main tool we use throughout this section is topological HOMP JoMMP-inditinguushabblii criterion based of the notion of covering spaces, extending the main result of Bamberger (2022) from graph coverings to combinatorial complex coverings.
Definition 4.1 (CC covering). X is said cover X' if there exists a surjective rank-preserving map P: X X which is local isomorphism with respect to natural neighborhood functions (i.e. p bijectively maps the set A(x') to (p(x)) for all x' X and M EV nat).
Examples of CC coverings are depicted Figures 3 10 and 11 Explicit constructions of covering CCs can be found in Appendix B The following theorem shows that complexes sharing cover
GGnnraally, dr, # drg. e.g. atoms (0-cells) and bonds (1-cells) might have different number of features. for neighhorhond functions M, that not associated with an incoming edge. Equation 3 in its full generality corresponds to fully-connected tensor diagram.
"This is equivalent setting MLP(2)
XX' and X" are isomorphic if there exists bijective mapping & X + X' which is both rank- mee-preser and paaeuusionppeservviii
Appendix [ for formal definition.
4

---

Published as a conference paper at ICLR 2025
indistinguishable by HOMP models. See Appendix B for proof of Theorem 4.2 and further discussion.
Theorem 4.2 (Hiiiindisiingiisbbilittt criterion). Let X and X' be CCs such that (26]= [g If there exists a CC X that covers each of the connected components of both X and X', then for every HOMP model M, M(X)) = M(X").
4.2 TOPOLOGICAL AND METRIC LIMITATIONS
Although CCs are combinatorial objects, they give rise to various met- ric and topologiaal spaces. The shortest path distance with respect to any neighborhood function defines a metric on the cells of the CC. In addition, if the complex is cellular or simplicial, it can be canonically associated with topological space. The topological/metric properties of these spaces are invariants the underlying CC. We prove HOMP's inability to distinguish between complexes based on the following com- mon invariants: (1) the diameter, which measures how "spread out" the complex is; (2) orientability, which captures whether a consistent "side" or direction can be defined across the entire space; (3) planarity, which captures whether the complex be embedded in IR2;; (4) the homology groups, which encode the structure of "d-dimensional holes"
Figure 3: Cyl,,2p covers both Cyhn.p and Möb,.p.
Theorem 4.3 (Topological blindspots). For any invariant I E {diameter, orientability, planarity, homology) } there exists pair of HOMP iaii---ndistinguishbba CCs that differ in I.
Figure depicts pairs of HOMP SiMMPiindstinguishablee CCs which differ in each the above invariants. In addition, Appendix B provides detailed discussion regarding each invariant, as well as a complete proof of Theorem 4.3 To demonstrate the techniques used in the proof, we include short proof sketch for the case of orientability and planarity.
digpictssppcts
Figure Cylinders are planar.
Proof sketch. Let Cyle.p and Möba.p be Cylinder and a Möbius strip with height h and cycle length p. The cylinder is orientable and planar, while the Möbius strip is neither (see Figure 4 for an illustration). As illustrated in Figure Cyl,,2p covers both Cyl,.p and Möb Intuitively, 2 covers Cyl by "wrapping" around it twice, and Möb by "wrapping" and "twisting" around (formal construction of both covering maps appears in Appendix B). Since both CCs are connected and have the same number of O-cells, Theorem 4.2 shows they are HOMP hia--idistinguishabl..
4.3 LIFTING AND POOLING
One benefit of combinatorial complexes is their flexibility in incorporating lifting and pooling meth- ods to construct CCs from graphs. Common graph lifting methods, such as the ones in Bodnar al. 2021aab) add meaningful substructures (that standard message-passing cannot detect) as higher- order cells. This results in models that are strictly more expressive than MPNNs. Graph pooling methods, like spectral pooling Ma et al. (2019), Mapper Singh et al. (2007); Hajij et al. (2018) Dey al. (2016), and DiffPool DiffPool Ying et al. (2018), coarsen input graphs enable more efficient learning.
common feature of many lifting and pooling methods is their ability to generate CCs with a small number of high-order cells that differ in fundamental topological and metric invariants. The sparsity of these cells allows for efficient computation of these invariants, resulting an efficient way to distinguish the original graphs. However, the following proposition, formally stated and proved in Appendix B.3 suggests that HOMP may still struggle to differentiate between the resulting CCs.
Proposition 4.4. There exist pairs of CCs generated by standard lifting and pooling methods on graphs (See Figures TOTI in Appendix B.3) that HOMP fails to distinguish, even though they differ in basic topological/mericc properties. These properties can be efficiently computed due to the sparsity of higher-order cells.
'F.g. circle has single 1-dimensional hole, a sphere has a single 2-dimensional hole, etc.
'n its broadest sense, the term "lifting" includes both substructure lifting and pooling methods. However, as these concepts are often discussed separately in the literature, we distinguish between them, referring to substructure lifting "lifting" and pooling-based lifting as "pooling".
5

---

Published as a conference paper at ICLR 2025
ogpt
app
agan
ogir
НОMP
MCN
SMCN
Node labels
Edge labels
HOMP
SMCN
MCN
HOMP
SMCN
MCN
Aryon Ar I B / B, Neighborhood function induced update
"SCL" label
"equiv" label
eo0
Co
22
Co
SCL layer
Equivariant linear layer
Figure 5: Example tensor diagrams for HOMP, MCN, and SMCN. HOMP only uses nodes labeled with standard cochain spaces. MCN adds nodes labeled with multi-cellular cochain spaces and edges labeled with "equiv" updates. SMCN introduces edges labeled with "SCL". Note that the highest order nodes (green and orange) which can only appear in the MCN diagram are replaced in the SMCN diagram through "SCL." updates of lower order nodes (pink and light blue).
5 MULTI-CELLULAN NETWORKS
In graph learning, expressivity limitations similar to those shown in Section been mitigated by architectures that process features defined over tuples of nodes, and in particular by IGNs (Maron
al. 2018 2019 Keriven & Peyré 2019 Azizian & Lelarge 2020). 'Tese models are built by stacking equivariant linear layers between high-order tensor spaces defined over the nodes of the graph, interleaved with pointwise non- non-linearities. We use similar approach, introducing multi- cellular cochain spaces (as analogue to IGN tensor spaces) and incorporating their induced equiv- ariant linear updates into the HOMP framework. For an overview of IGNs, see Appendix(A.. [A.]]
Multi-cellular cochain spaces. Given an Ê-dimensional CC X' and (E + 1)-tuple & N++1
the - Rd.. The vector space of multi-cellular cochains, denoted by (* R24) or Ck is called a multi-cellular cochain space. Multi-cellular cochain spaces are a natural generalization of standard cochain spaces, providing a way represent other types of CC data. E.g. (1) C ~ Ci: (2) Br, can be represented multi-cellular cochain E C +Cra; ter; (3) (co)Arrss can be represented as a multi-cellular cochain E C (see appendix for details). Moreover, multi-cellular cochain spaces recover many linear spaces studied in several previous works. For example, Cker matches the features space of k-IGN layer operating on r-cells, and Ce,, terz corresponds to the input space of the exchangeable matrix layers introduced in Hartford et al.) (2018).
k-order multi-cellular cochain is function h4 Xthu x
Symmetry group. Given enumerations of the sets No = {-. a J. X = {zf. multi-cellula, cochain h (*2, can be identified with tensor A defined by
of
(22 (Au)áa.....es = h (fo) (1o)
(4)
(Ge)
for multi-indices indices i E mo is E fl.... "l.....ne]$ fe. Therefore, C can be identified with the tensor space R xxx
be xd The group = Sno x .... x Sn, acts on h E c by
(a h)(2 ...., x²) ((oo....... .I) h)(2" ()("...,, x') h(oo x0 of x²).
(5) In
where if xr" (x) ...., ,.,)) E Xh-- is tuple of cells, x. (x" ( simple terms, the group G acts on h by reordering the cells each rank independently. Therefore, ensure independence of cell ordering, we aim construct G-invariant architectures.
(1)

---

Published as a conference paper at ICLR 2025
Equivariant updates. Since the space C* can be identified with R.n x..xnn xn xd we utilize the
basis of equivariant linear layers IR" x--xx xd + R" x...xn "e xd' constructed in Maron et al. 20188). to describe the space of equivariant linear maps C+ + Ck' Using this basis, denoted 17 (d.. (Here I(k. k', d, 3') is an index set defined in Appendix C we follow the con- struction of well- permutation-ing invariant architectures (Maron et al. [2018] Zahherr et al. 2017.
Hartford al. 2018 Bronstein et al. 2021), and define learnable equivariant layers
F(h) = 3
Σ
W. (, (Au))
(6)
(K d.d")
where (wy))eeTA. (ddd) are learnable parameters and / a non-linearity.
MCN. We incorporate equivariant layers the HOMP framework by adding node and edge labels to the tensor diagram scheme (as depicted in Figure 5 defining a new class of TDL architec-
tures we call multi-cellular networks (MCNs). At each layer of an MCN tensor diagram, if v is node labeled by C*, we compute a multi-cellular cochain (v) E C by h(")
X uépred(()) mu,r(ar) where pred(u) denotes the set of predecessor nodes in the diagram, and messages my,e C computed based on the label of the edge (u, v). If the edge is labeled with "equiv", the message is computed described in Equation [ For edges labeled by neighborhood functionn, the message follows the standard tensor diagram update rule. A formal definition of the MCN framework can be found in Appendix [ Using nodes labeled by higher-order multi-cellular cochain spaces and equiv- ariant updates improves expressivity. In fact, by using multi-cellular cochain spaces of high order, MCN can reach full expressivity, as proved in Appendix
Proposition 5.1 (MCN is fully expressive). If X and X' are non-isomorphic CCs, there exists an MCN model M such that M(X) A M(X").
SCALABLE MULTI-CELLULAR NETWORKS
Despite its strong expressive power, implementing MCN in full gener- ality is impractical as the computational complexity and the size of the basis [[k. k', d, d')l grow exponentially with & and k'. In this section, we design scalable MCN (SMCN), more efficient version of MCN that still mitigates many of HOMP's expressivity limitations. Below is an overview and motivation for the SMCN architecture. A formal construc- tion and computational runtime analysis can be found in Appendix D an implementation guide and empirical runtime evaluation are provided in Appendix G
coA2,11
First, we restrict SMCN multi-cellular cochain spaces Ck with o k S 3. Of these, the spaces whose updates incur the heaviest computational overhead are C3e, and C2e,, We replace the up- dates induced by these spaces with new updates inspired by expressive GNNs, providing a middle ground between expressive power and scal- ability. These GNNs are applied to graph structures, called augmented Hasse graphs, that capture relational information between cells.
X
HeaAs (X)
Figure 6: HeoAz1"
Definition 6.1 (Augmented Hasse graph). The augmented Hasse graph of X w.n.t. (co) defined by H(co)Am = (V,E), where V = Xr, and È = {(x,)) y (n.)),,
is
See Figure for an illustration of an augmented Hasse graph.
Replacing 22er terz with Cer1 ter2, Recall that C2er can be identified with ". x xd Under the action of Sn., x Sn.y. tensor H E "R xn, xd can be viewed bag of tensors (He RTr, xnr, xd "kjjne,) each of which considered up-to Sn,, permutations. These the exact objects processed by Subgraph GNNs (Bevilacqua et al. 2021 Frasca al. [022] Zhang al. 20236), which operate on a set of adjacency matrices corresponding to different subgraphs defined
(co))r,.r represents either adjacency adjacency neighhorhood function.
7

---

Published as a conference paper at ICLR 2025
( 2eX2
(H hEE
(
Subgraph GNN
Figure 7: Illustration an SCL update on Ceotes, We construct bag of copies of X' with marked 2-cells. This bag is processed by applying a subgraph GNN to the bag of the corresponding marked A..1 augmented Hasse graphs. Here, X represents the complex X' with a distinct "marking" feature added to the cell features of cell Similarly, Hm..., denotes the Augmented Hasse graph H.A., with
marking added to the nodes corresponding the elements of cell
over a fixed set of nodes. Subgraph GNNs are strictly more expressive than MPNNs, demonstrate strong experimental performance, and have quadratic runtime complexity as opposed to On -2y)) for (2e,, tery + C2e,, terz equivariant updates.
Following the above discussion, we define the subcomplex layer (SCL) updates. Let (u, e) be tensor diagram edge labeled by "SCL", connecting layers t and t++ (in which case e and are both labeled by C ter2). The message ma,,v E ( ter2 is computed by
mu,o(I, 8) =
MLP r=0rr==
(1) (1) D..y (co) (x).y) h (co) (v) h
BST, (v).y)
where he.. y ;= Ee'EE, b and Oz Ey he, This update can be viewed as applying a subgraph update to bags of augmented Hasse graphs, as shown in Figure] 7 Additional details are provided in Appendix D For review of subgraph networks, see Appendix A.
Replacing (3e, with C Since C3e, can be identified with Re. equivariant linear layers of the form L C3., + C3er can be identified with 3-IGN layers acting on augmented Hasse graphs of the form H(co) The GNN literature offers several candidates for efficient 3-IGN substitutes. The first option we considered is PPGN (Maron et al. 2019), which matches 3-IGN's 3-WL expressive power with runtime of ((122.)) Another option using subgraph networks with node marking, which results in the SCL update rule above with r = r2 = r. These networks have runtime of O(VI- (E') and are strictly more expressive than MPNNs (> 2-WL), but are less powerful than 3-IGNs (Frasca et al, 2022). We experimented with both versions and found no significant performance improvement using PPGN. Therefore, continue with the subgraph version, but note that since PPGN can implement subgraph networks - all theoretical results hold for the PPGN case well.
6.1 EXPRESSIVE POWER OF SCALABLE MULTI-CELLULAR NETWORKS
Topological and metric properties. In Section 4.2, proved that HOMP models cannot distin- guish CCs based on diameter, orientability, planarity or homology. We now examine SMCN with respect to each of these limitations. First, SMCN fully mitigates HOMP's inability to compute diameters.
Proposition 6.2. pair of CCs with different diameters can distinguished by an SMCN model.
Next, SMCN can distinguish between cylinder and a Möbius strip, implying that it is strictly better than HOMP at detecting planarity and orientability
Proposition 6.3. There exists an SMCN model that separates the Möbius strip and the cylinder.
Finally, we offer two results demonstrating SMCN's ability to distinguish CCs based on their ho- mology groups. The first result examines the 0-th homology group.
8

---

Published as a conference paper at ICLR 2025
Proposition 6.4. Any pair of CCs with distinct 0-th homology groups can be distinguished by SMCN.
The second result generalizes homology groups of any order in the case of two-dimensional surfaces embedded in R
Proposition 6.5. Let X" be a pair of CCs whose underlying topology corresponds to a 2- dimensional surface (with without boundary) embeddable in RR. If X and X' differ in any homology group, there exists an SMCN model that distinguishes them.
A full exploration of SMCN's ability to capture homology groups of any order, orientability and
planarity is left for future work. Collectively, Propositions 6.2 6.5 suggest that SMCN is strictly better than HOMP at leveraging topological properties of CCs. Rigorous formulations and proofs
of these propositions appear in Appendix The following proof sketch for Proposition 6.3
Proof sketch of Proposition 6.3 The key distinguishing Cyl,,p and Möb is their boundary 1-cells. In our case, these are the 1-cells that are incident exactly one 2-cell, i.e. their B1.2-degree is 1, so they can easily be detected by an SMCN model. As illustrated in F the boundary of Cyl,.p forms two cycles of length while the boundary of Möba.p forms a single cycle of length 2p. This standard example of a pair of graphs that are indistinguishable by MPNNs but are distinguishable by expressive graph models such as subgraph networks. We can use an SCL update to simulate a subgraph network on the boundaries, separating the two CCs.
Figure Boundary 1-cells.
Lifting and Pooling, In Section 4.3 we discuss HOMP's inability to expressively leverage the sparse higher-order cells generated by common lifting and pooling methods. The next proposition, proved in Appendix F.2 suggests that SMCN is able to leverage this information to greater extent.
Proposition 6.6. There exist CCs, generated from graphs by standard lifting and pooling methods, that HOMP cannot distinguish but SMCN can. The SMCN model can be constructed to have runtime O(maee no T22), where mideg is the maximal degree w.r.t any natural neighborhood function.
7 EXPERIMENTS
The lack of CC benchmarks has been recognized as a challenge in TDL (Papamarkou et al. 2024). To address this, we introduce three novel CC benchmarks designed to assess the ability of TDL models to capture topological/metricc properties, and evaluate both SMCN and other HOMP archi- tectures on them. In addition, we adopt the setup of Bodnar et al. (2)21a), applying cyclic lifting on real-world graph benchmarks. For an in-depth discussion of experimental details, see Appendix G A comparison of the expressive power of SMCN and all baselines is available in Appendix F3
Torus dataset. The torus dataset consists of pairs of CCs, each comprising one more disjoint tori (see Definition B.4). These pairs are chosen to be HOMMPindistinguuisabll despite differing in basic metric/topological properties: they either have distinct homology groups, or they differ in the diameters of some of the components. Models are evaluated by counting the number of pairs they can to separate in a statistically significant way. following the protocols outlined in (Wang Zhang 2024). In our experiments, HOMP was unable to distinguish any of the pairs, while SMCN was able to distinguish all pairs.
Predicting topological and metric properties. We construct two additional benchmarks in which models are tasked with predicting topological and metric properties of CCs lifted from ZINC Sterling & Irwin 2015) molecular graphs. The predicted properties are the (0, 1, 1,, -iisse- (Equation 24). and the second-order Betti number (rank of the second homology group). In Ap- pendix B we show that HOMP is incapable of fully capturing either property. Table Tableepreseent both the MSH and the accuracy of predicting the target values (18 possible values for cross-diameter and 6 for Betti numbers) across three TDL models: SMCN, CIN, and custom HOMP architecture tailored for this prediction task.
TThe targets are normalized have standard deviation of

---

Published as a conference paper at ICLR 2025
Table 1: SMCN outperforms MPNNs HOMP and expressive GNNs on graph regression and
classification tasks. SMCN results reported 5 runs with seed 1-5.
Model
Reference
ZINC
MOLHIV
MOLESOL
MAE (U)
ROC-AUC (1)
RMSE (L)
GCN
Kipf & Welling
2016
0.321 = 0.009
76.06 + 0.97
L.14 0.036
GIN
Xu et al. (2018)
0.163 1 0.004
75.58 1.40
1.173 1 0.057
CIN
Bodnar al. (2021a)
0.079 = 0.006
80.94 + 0.57
1.288 = 0.026
CIN+
Giusti et al. (2023)
0.077 + 0.004
80.63 1 0.94
CIN CycleNet
Yan ct al. 20224)
0.068
Cellular Transformer
Ballester al. (2024
0.080
79.46
PPGN
Maron et al. (2019)
0.079 = 0.005
PPGN+ (6)
Puny ct al.
2223
0.071 + 0.001
DS-GNN
Bevilacqua et al
2023
0.087 = 0.003
76.54 1.37
0.847 + 0.015
DSS-GNN
Bevilacqua ct all 20/21
0.102 + 0.003
76. + 1.66
SUN
Frasca et 2022
0.083 = 0.003
80.03 0.55
GNN-SSWL
Zhang et al.
2023b
0.082 = 0.003
GNN-SSWL+
Zhang et al.
2022bb
0.070 + 0.005
79.58 + 0.35
0.837 + 0.019
Subgraphormer
Bar-Shalom et al.
(2023)
0.067 = 0.007
80.38
0.832 = 0.043
Subgraphormer PE
Bar-Shalom et al.
(002:))
0.063 + 0.001
79.48 + 1.28
0.826 + 0.010
SMCN (ours)
This paper
0.060 + 0.004
81.16
0.90
0.809 0.037
The benchmarks detailed above empirically verify SMCN's superior ability capture topologi- cal/metric properties of CCs. This is demonstrated for both synthetically generated data as well lifted molecular graphs, complementing theoretical results from Sections 4 and 6.1 demonstrating that the expressivity gains of SMCN lead to improved learning of topological/metric invariants.
Real-world graph benchmarks. We evaluate SMCN on ZINC- 12K (Sterling & Irwin 2015). MOL- HIV, and MOLESOL (Hu et al. 2020). We compare SMCN to several HOMP baselines as well as range of expressive graph architectures. As seen in Table [ SMCN outperforms both HOMP architectures and expressive graph methods across all three benchmarks, underscoring the value of expressively leveraging higher-order topological information on graphs.
CONCLUSION
In the first part of the paper, we analyzed the expressiv- ity limitations of HOMP from a topological perspec- tive, proving its inability capture the diameter, ori- entability, planarity, and homology of input CCs. SMCN
Table 2: Accuracy and normalized MSE scores of predicting the cross- diameter and the second Betti number of lifted ZINC graphs.
Model
Cross-diameter diameter
2nd Betti number
Accuracy (1) (SESEE) (L)
Accuracy (?) MSE (L)
3.00% 1000000003330000 0.0091
:: 25.22%/0.313.
0.3799
Custom HOMP
67.87 = 22.20% /0.0684 0684 + 0.0323
81.76 + 10.06% 0.0208
92.78 0.53%% /0.011 0.0008
99.61 1: 0.12% 0.12%%/0.002 /0.0024 1: 0.0005
Additionally, we showed that there exist CCs generated through common graph lifting methods which are HOMP-indistin indistinguishable despite differing in easy-to-compute topological invariants. In the second part of the paper, we introduced MCN, inspired by k-IGNs, and its more scalable version, SMCN. We proved that, analogously to IGNs, MCN can reach full expressivity for CCs. We addi- tionally showed that SMCN tractably addresses many of HOMP's expressivity limitations. Finally, presented three novel benchmarks designed to evaluate TDL architectures' ability capture topological/metric information. We evaluated SMCN on both benchmarks as well as real-world graph benchmarks. SMCN outperformed HOMP architectures pirically supporting our theoretical findings. On the real-world graph benchmarks, SMCN outper- formed both HOMP architectures and expressive graph architectures, demonstrating the value of expressively leveraging higher-order topological information.
expressivity benchmarks, em-
Limitations and future work. The components that make SMCN more expressive have runtime that scales super-linearly in the number of cells, making SMCN intractable for larger CCs. Future research may aim to design more scalable alternatives to SMCN. Additionally, although we have shown that SMCN is strictly better than HOMP in distinguishing CCs based on orientability and homology, it remains unclear if it is able to fully capture these properties. Future work can explore SMCN limitations in expressing topological and metric invariants. Finally, future research can aim develop more complex benchmarks that include broader range of topological properties.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank Beatrice Bevilacqua for insightful discussions. YG is supported by the the UKRI Engineering and Physical Sciences Research Council (EPSRC) CDT in Autonomous and Intelligent Machines and Systems (grant reference EP/S022050//), FF funded by the Andrew and Erna Finci Viterbi Post-Doctoral Fellowship. FF partly performed this work while visiting the Machine Learning Research Unit at TU Wien led by Prof. Thomas Gärtner. MB is supported by EPSRC Turing AI Wordd-Le Research Fellowship No. EP/X040062/1 and EPSRC AI Hub on Mathematical Foundations of Intelligence: An "Erlangen Programme" for AI No. EP/Y028872/1.
HM a he Robert J. Shillman Fellow, and is supported by the Israel Science Foundation through a personal grant (ISF 264/23) and an equipment grant (ISF 532/23).
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. arXiv preprint arXiv:2006. 15646, 2020.
Rubén Ballester, Pablo Hemn andez-Garc'ia Mathilde Papillon, Claudio Battiloro, Nina Miolane, Tolga Birdal, Carles Casacuberta, Sergio Escalera, and Mustafa Hajij. Attending to topolog-
ical spaces: The cellular transformer. ArXiv, 0tos/2405.14094 2024. URL https://api.
Jacob Bamberger. A topological characterisation of weisfeiler-leman equivalence classes. In Topo- logical, Algebraic and Geometric Learning Workshops 2022, pp. 17-27. PMLR, 2022.
Guy Bar- Shalomh Beatrice Bevilacqua, and Haggai Maron. Subgraphormer: Subgraph GNNs meet graph transformers. In NewrlPS 2023 Workshop: New Frontiers in Graph Learning, 2023. URL
httts:://ppeneett
net www.:nettoooooroooooo ?id=e8ba 9Hu1 mM
Guy Bar-Shalom, Yam Eitan, Fabrizio Frasca, and Haggai Maron. A flexible, equivariant framework for subgraph gnns via graph products and graph coarsening. arXiv preprint arXiv:2406.09291, 2024.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. arXiv preprint arXiv:2110.02911 2021.
Beatrice Bevilacqua, Moshe Eliasof, Eli Meirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph gnns by learning effective selection policies. arXiv preprint arXiv:2310.20082, 2023.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://wwa wandb. com/ Software available from wandb.com.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. Y. Dauphin, P. Liang, J.d Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a. URL https: http:///peeeeeeeeeeeeeeee net/ Strr/forrne forum? d=UPP ZCMVESSC
Beygelzimer,
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial net- works. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. PMLR, 18-24 Jul 2021b. htRhstts::/ pttttp:://proceedingge mlr wwtps/m....pp.ss.....m.. press/v139/ bodnar21a. html
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein.
Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45()):657-666) 2022.
11

---

Published as a conference paper at ICLR 2025
Michael Bronstein.
subgraphs for more expressive gnns. Eowardsdat dasidddnceecee com/ December 2021.
Using
https://
Michael Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesies, and gauges. arXiv preprint arXfv:2104.13478, 2021.
Davide Buffelli, Farzin Soleymani, and Bastian Rieck.
Cliqueph: Higher-order information for graph neural networks through persistent homology on clique graphs. arXiv preprint arXiv:2409.082 2024.
Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning graphs. Advances in neural information processing systems, 34:27029-27042, 2021.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. Advances in Neural Information Processing Systems, 34:1713-1726, 2021.
Tamal K Dey, Facundo Mémoli, and Yusu Wang. Multiscale mapper: Topological summarization via codomain covers. In Proceedings of the twenty-seventh annual acm-siam symposium on discrete algorithms, pp. 997-1013. SIAM, 2016.
Vijay Prakash Dwivedi, Chaitanya Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02422 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Pro- cessing Systems, 35:31376-31399 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, and Pietro Liò. Cin++: En- hancing topological message passing. arXiv preprint arXiv:2306. 03561, 2023.
Aric Hagherg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and func- tion using networkx. Technical report, Los Alamos National Lab((LNNL), Los Alamos, NM (United States), 2008
Mustafa Hajij, Bei Wang, and Paul Rosen. Mog: Mapper on graphs for relationship preserving clustering, arXiv preprint arXiv: 11442 2018.
Mustafa Hajij, Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. arXiv preprint arXiv:2010.00743. 2020.
Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáena and Karthikeyan Natesan Ramamurthy. Higher-order attention networks. arXiv preprint arXiv:2206.0000 00600 2(3):4, 2022a.
Mustafa Hajij. Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenzz Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K Dey, Soham Mukherjee, Shreyas N Samaga, et al. Topological deep learning: Going beyond graph data. arXiv preprint
arXiv:2206.00660 2022b.
Mustafa Hajij. Mathilde Papillon, Florian Frantzen, Jens Agerberg, Ibrahem AlJabea, Ruben Ballester, Claudio Battiloro, Guillermo Bernárdez, Tolga Birdal, Aiden Brent, et al. Topox: a suite of python packages for machine learning on topological domains. arXiv preprint (0442402..224), 2024.
12

---

Published as a conference paper at ICLR 2025
Jason Hartford, Devon Graham, Kevin Leyton-Brown, and Siamak Ravanbakhsh. Deep models of interactions across sets. In International Conference on Machine Learning, pp. 1909-1918.
PMLR. 2018.
Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. ISBN 0-521- 79160-X; 0-521-79540-0.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borg- wardt. Topological graph neural networks. arXiv preprint arXiv:2 2021.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-22133,, 2020.
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. In The Interna- tional Congress of Mathematicians, 2022.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-320, 2005.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks.
Advances in Neural Information Processing Systems, 32, 2019.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ArXiv, bbss/600.00290, 2016. URL /ttpo://apl..eemattcccss
CorpusID:3144220
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanic Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint wtX.::2202.131/1111 2022.
Liheng Ma. Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pp.
PMLR, 2023.
Yao Ma, Suhang Wang, Charu C Aggarwal, and Jiliang Tang. Graph convolutional networks with eigenpooling. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 723-731, 2019.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXiv: 11220099/, 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, pp. 4602-4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 241))15885-15923, 2023.
Theodore Papamarkou, Tolga Birdal, Michael M Bronstein, Gunnar E Carlsson. Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, al. Position: Topological deep learning is the new frontier for relational learning. In Forty-fost International Conference Machine Learning, 2024.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In Interaational Conference on Machine Learning, pp. 18191-28222 PMLR, 2023.
Bastian Rieck. On the expressivity of persistent homology in graph learning. arXiv preprint arXiv:2302.09826, 2023.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, pp. 287-297. Springer, 2008
Gurjeet Singh, Facundo Mémoli, Gunnar E Carlsson, et al. Topological methods for the analysis of high dimensional data sets and 3d object recognition. PBG@ Eurographics, 2:091-100, 2007.
Teague Sterling and John J Irwin. Zinc 15- ligand discovery for everyone. Journal of chemical information and modeling, 55(1 (3:1))2324-2337, 2015.
Yogesh Verma, Amauri H Souza, and Vikas Garg. Topological neural networks go persistent, equiv- ariant, and continuous. arXiv preprint arXiv:2406.03/66 164, 2024.
Yanbo Wang and Muhan Zhang. An empirical study of realized gnn expressiveness. In Forty-first International Conference Machine Learning. 2024.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.008220 2018.
Zuoyu Yan, Tengfei Ma. Liangcai Gao. Zhi Tang, Chao Chen, and Yusu Wang. Cycle invariant positional encoding for graph representation learning. Learning on Graphs Conference, pp. 4-1. PMLR, 2024.
Rex Ying, Jiaxuan You. Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hicrarchical graph representation learning with differentiable pooling. ArXiv, abs/ 0oss/1806.00 088008 2018. URL httphhtss://// //ap:://ap.... semant wachhlar........o..ooooco..cc..e org/ wtt//orgg//ooo Corpus ID: 49420315
Jiaxuan You, Jonathan M Gomes-Selman. Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10737-10745, 2021.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey. arXiv preprint arXiv:2308.0822: 2023a.
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisnn tests. In International Conference on Machine Learning, pp. 41019-41077. PMLR, 2023b.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprini arXiv:2301.09500 2023c.
Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. arXiv preprint arXiv:2406.04336. 2024.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances Neural Information Process- ing Systems, 34:15734 157477, 2021.
14

---

Published as a conference paper at ICLR 2025
The Appendix is organized follows:
In Appendix A.1 we give an overview of expressive GNN architectures relevant to this
paper.
Appendix
we give an illustrative example of CC neighbourhood funcitons.
In Appendix B we prove results from Section regarding the expressivity of HOMP archi-
tectures. In B. we prove Theorem 4.2 (topological DoMM--iniittingusshabiitt criterion),
in B.2 we prove Theorem
4.3 (topological blindspots) and in B.3 we address lifting and
pooling.
In Appendix give in-depth description of the MCN framework, introduced in Section 5
In Appendix we give an in-depth description of the SMCN framework, introduced in S
In Appendix give formal definition of CC isomorphism and prove Proposition 5.1
(MCN can distinguish any pair of non-isomorphic CCs).
In Appendix analyze the expressive power of SMCN, proving all results from Section
6.1
In Appendix G we give further details regarding the results presented in Section well as the experimental setup.
A BACKGROUND
A.1 OVERVIEW OF EXPRESSIVE GNN ARCHITECTURES USED IN THE PAPER
The expressivity of GNNs is typically evaluated terms of their separation power, i.e. their ability to assign distinct values to non-isomorphic graphs. Seminal works by Morris et al. (2019) and Xu al. (2018) demonstrate that the expressive power of MPNNS equivalent that of the I-WL test WWessfellrr & Leman 1968). These findings inspired the development of more expressive GNNs, with expressive power surpassing that of the 1-WI. test, albeit often requiring greater computational resources. In this paper we focus on two such architecturres: invariant graph networks (IGNs)
Maron et al., 2018 2019) and subgraph neural networks Bevilacqua et al. (202T); Frasca et al. et al. (2023b).
Invariant graph networks. Maron et al. (0018 proposed a principled approach to design expres- sive GNN architectures by leveraging the inherent symmetries of graphs.
More specifically, given a graph G with adjacency matrix E RRax and node feature matrix X E Ra an IGN first encodes this graph as a tensor T E I (d+x((+1)) where T... holds the adjacency matrix A and the last d channels hold the node features on their diagonal, i.e. T X,, and Th = 0 for i * iz. The symmetry group S, acts naturally on R" x(d+1) by:
Tijik T, 100. 18), O Sn.
Notice that for any graph tensor T and permutation Sn, the tensors T and σ T represent the same graph. This action can be easily generalied to the tensor space I8* by:
oT inm.
((1)......
1(())
(8)
For any integers k. W,, c/ Maron et al. (0018) finds basis to the space of all linear maps L In* xe + gnn xe' which satisfy
L(o T) = a L(T).
(9)
These are called equivariant linear maps. a k-IGN stacks lyaers is of the form
U(T) = 3 Σ (T),
(10)
TET
where (Lyher basis the space equivariant layers from R "1 x0y to Rn" xes for some
k ki A and cr, C2 N, {wy]ver learnable parameters and / is non-linear activation
15

---

Published as a conference paper at ICLR 2025
function. The k-IGN architecture proven in Maron et al. (2019) to be expressive the k-WL test, extending the capabiliities of MPNNs, which were shown to possess expressivity equivalent to the 1-WL test. Despite this I-IGNs have runtime complexity of O(n") making them impractical to use. To address this, other expressive GNNs have been proposed, offering a balance between the computational complexity and expressive power of 3-IGNs and MPNNs. One such family of architectures is subgraph neural networks.
Subgraph neural networks. Subgraph neural networks, (You et al. 2021 ?: Cotta et al. 2021 Bevilacqua et al.) 202I), rely graphs, with each graph in the set representing an augmented version of the original. Some policies include node deletion, where each graph in the set is created by removing single node from the original graph; k-ego policies, where each graph is generated by extracting the k-neighborhood of a specific node; and node marking, where each graph is obtained by assigning a unique node feature to single node in the original graph. Subgraph GNNs then process sets of graphs by independently applying MPNN updates to each graph in the set, while also incorporating cross-graph updates to exchange information between the graphs. [Bevilacqua et al.] (2021) has shown that subgraph GNNs are strictly more expressive then MPNNs, while |Fasca et al. (2022) has shown they are strictly less expressive then 3-IGNS. With runtime complexity of Old . n²) where d is the maximum degree of the input graph, subgraph GNNs offer a compelling trade-off: they are more expressive than MPNNs while remaining more scalable than 3-IGNs. Subgraph GNNs have demonstrated strong empirical performance in studies such as [Bevilacqua et al. (2021). Frasca et al. (2022). and Zhang et al. (2023b), among others, establishing them robust and effective choice for GNN architectures. For an in depth discussion on subgraph neural networks see Broostein (2021).
predefined policy that transforms input graph into set of
A.2 NEIGHBORHOOD FUNCTION ILLUSTRATION
The following is an example of the standard neighborhood functions introduced in Section For the CC in Figure D the following relations hold:
{A} E ((,)(
{A} Ao, ((D)).
{A} E (o,((()))
{C,D) E (lA,).
(C,D) $ ((A,
(C,D, ((E,F)) (E).
(C ((E,F,))
(A, E C0.2, EJ).
(B,D) E..D)(D).)(
(F,G, E (o)).
(B) E (T,(BBB
(B) $ D)).
(B) e B),(((,,,C.D)).
. [B) & (IC,
HOMP can be viewed as performing parallel message passing on the connectivity structures defined by these neighborhood functions.
B EXPRESSIVITY LIMITATIONS OF HIGHER-ORDER MESSAGE-PASSING
B.1 A TOPOLOGICAL CRITERION FOR HOMP INDISTINGUISHABILITYY
In this section we formally restate and prove Theorem 4.2
16

---

Published as a conference paper at ICLR 2025
Figure 9: CC example for neighborhood function illustration. Nodes are labeled A,... G, cells are comprised of subsets of nodes, 1-cells represented by orange edges, and 2-cells represented as blue faces. E.g. {E, F, H) is a 2-cell, {A, C is 1-cell.
Theorem B.1 (HOMP-indd) indistigguishabblity criterion, restatement of Theorem 4.2 Let X and X' be CCs of dimension l with no cell features such that [Xo] [gg.. If X and X' admit decompositions into connected components
==
L
2, X'
Z',
(11)
ZEC(X)
Z'EC(X))
such that 3X that is covers each of the connected components E C(X), C(X'), then for every HOMP model M, M(X) =M(x).
A combinatorial complex X' is said be connected if its Hasse graph, defined by g (V. E) with V = X' and & = {(z. y) x C rk(xx) = rk(y) - 1}, is connected. To prove Theorem B.I we first state and prove two lemmas.
Lemma B.2. Let X + X be a covering map. In addition, let M be HOMP model with T layers, and let h and h denote the cell feature maps of X and X at layer evaluated on cells
(t) E X and x' e X respectively. Under these conditions, h h for t = ..... T, x' E X.
Proof. We use induction on l. For = 0, as both CCs have initial cellular feature maps, HOMP initializes he _ by assigning constant feature all cells and the claim holds trivially, Assume the claim holds for some t E (O.....T), The HOMP update rule reads:
h ((+1)
MLP(0 Nick(z)
(h(), (h()h('))
NEN nut yEN(x))
(12)
6 ((+1)
MLP()) Na (h (1)
(12), (6))
NEN aat y'EA(("")
Since p covering map, M(aa)) is bjectively mapped M(p(x')) for every x' E and every neighborhood function A E N nat- Additionally, rk(p(z')) rk(x'). This, along with the fact that is permutation invariant, and the induction hypothesis implics that:
(
Wark (h (
(L
Makk((()) p( h
(13)
(ar
vEA(o(('))
17

---

Published as a conference paper at ICLR 2025
Thus, combining Equation 12 and Equation 13 we get h
(6+1) p(wr))
Lemma B.3. If is connected and p : & - X is a covering map, Vx E X, 1x) =
Proof. Since p is surjective and rank- preserves,,,, the above is equivalent to Vz, y E X. (1)
lp- (x)]. Since X' is connected, it suffices to show that this equality holds for any 2, y É X such that
y E (xx) for some function N N nat- We first show that for any natural neighborhood function
N E W nst and cell æ E X' the sets {W(x') | x' E p (x)) are pairwise disjoint. To see this,
assume by contradiction that for a pair of cells 44.42 E P (x) we have (xx1) (W(2))))))))))))))) # 0. If z' E *N((21)) (2(2)) then there is a neighborhood function No E N nat such that o' 11,22 E (z).. Given that p(x1) = p(x2),, this would imply that P is not injective on (2),, contradicting the definition of a covering map. Now, since y E (xx), for any x' E p- there exists a y' E (=')) such that p(y/) = y. Since the set (W(x') x' E p (x)} is pairwise disjoint this implies that
lp [w)l 2 (x=)( Since y E (zx), there exists a neighborhood function N E Aatt such
that x E (v), implying by the same reasoning above that Ip (w) & Ip (z)). We thus have
lp- (v) lp [z)] which concludes the proof.
O
We are now ready to prove Theorem B.1
Proof. Let X be a combinatorial complex that covers all connected components 2 E C(x) and Z' E C(2") via maps the maps {Pz) {Az)zec(x) and 2(ec(()) respectively. Let M be HOMP model with T layers and let h()), h)(0, and h(() denote the cell feature maps of X, X", and & respectively at layer f. Lemma B.2 implies that for every 2 E C(X), z' E C(X") and every E 2, z' E Z' we have
h h(T)
Vy E Pz (z),
(14)
h (T) k Vy E (
This implies that the sets of unique values corresponding to the multisets (h x E B. (hTT)
x' E E'D and (h y E B are the same. Let Byy myy ny be the number of times the value in
appear in the multisets ( (T) E XB. (h x' E X' } and ( (T) y E LB respectively.
Since each Z, Z' are connected, we can use Lemma B.3 to get that V2 Z, V2' E Z', P (2)
Xol and ( E.l
[ol This implies that Vy E X [
Zol |
Zil [x
ny -yy
Σ
n'y ny
Σ
(15)
ZEO(X)
Z'EC(2")
Since E2 1Zpl = | = 1 = Σ Σz Zg1. this implies that Vy E X, ny = niy We
have shown the set of unique values corresponding to multisets (h.") ( E and hh (T) x' e X' is the same, and that the number of times each value appears the multisets is the same, thus
the two multisets are equal. Since the readout of a HOMP model can is a function this multiset, X and X' are indistinguishable by HOMP.
B.2 TOPOLOGICAL AND METRIC LIMITATIONS
In this section, we rigorously state and prove all results regarding HOMP's inability to express topological/metric properties, presented in Section B We begin by defining the É-dimensional torus CCs. As we will later see. this class provides us with examples of indistinguishable CCs that differ in both the diameter and all homology groups.
E-dimensional torus CCs. An l dimensional torus is Cartesian product of é cycles. More for- mally:
Definition B.4 (d-dimensional torus CCs). For a sequence of integers Pl.... Pe, the torus T Tp a combinatorial complex (S, X, rk) defined by:
S [p1] [pe],
(16)
18

---

Published as a conference paper at ICLR 2025
X {sk 8 E. {0,1), K1 + +... + he r):
(17)
where 8/ is defined by:
Sk f k' E 10. K 5 k)
(18)
The sum + k' is coordinate where coordinate result is taken modulo Pj, and k' S if Kj S Kj, Vj E {}.
By slight abuse of notation, we sometimes refer to the set of cells of the torus by Tp pi.....pe well. We note that the torus 7 pp.....p: as defined above is only one possible realization of the E-dimensional torus as combinatorial complex. An example of two-dimensional torus can be seen in Figure I(a) As the next lemma shows, all l dimensional tori are locally isometric.
Lemma B.5. Let Tp....pp and Ty.....' be two E-dimensional tori such that Vj E {I....,.} PJ.P3 2 3. The torus pp.pt....pprrt covers both Tp.....ps and pp.....'h.
(PI,... (Pe,...,DE), p' (1/1.... 1/), p (fI,... .p) (pi ./i..... Additionally, denote by S, S, and X, X" X the nodes and cell sets of p. To and Tp respectively. Define p - S. p - S' by:
Proof. Denote
................................ Pe p/).
( = s mod d(()) = a mod p',
(19)
where ă mod == (31 mod Pi..... & mod pe). We extend p and p' to X' by p(z) = {p(s)
8 E 2}. We now prove that p is a covering map. We start by showing that Vr E {0. (0....e) E).
p(X.) = Xr (i.e, p is pank-preserving). Recall that all elements & are of the form šy for some SeS S and E {0, 1) such that h +... ke = r. Since p < p. for every k' S k:
(=+k' k'
mod p) mod p (& mod p) + (k' mod p) p(3) + k mod p.
(20)
Therefore,
p(šx) p()) Xx
(21)
and p is rank- aank-preserving. To show that is covering map, all that remains to show that preserves natural neighborhood functions and that it is surjective. For the former, notice that since p
is defined on the node set S, for every x. U, 2 E X have:
x S y - p(x) S ply).
z. C p(z), ply) p(2).
2 S "C p(=) S p(y).
Thus, P preserves all natural neighborhood functions. Finally, since Pi....,P 2 3 it is easy to check that for any y,y X and N e N nnti:
y E Nx)) = p(x) # ply)-
(22)
This implies that is a covering map. An equivalent argument shows that p' is also covering map, completing the proof.
Lemma B.5 gives rise to the following useful corollary.
Corollary B.6. If and Tpi... are {-dimensional tori such that P1 PP p/ p/ (i.e. Tp.....pr. and T pp.....p/ have the same number of O-cells) and Vjj {f....., (), Pj.p's 3, then for every HOMP model M, M(T, ((p......p)) p()......)))
Proof. Both Tp Tp.....pr Pr. and T2 Ty connected, have the same number of O-cells pe P1 "g..PP. Pe p/ ..P (Ty..... )o). and are covered by T pp../....... Therefore, Theorem B.1 implies that T pr....p and Ty W.... are indistinguishable by HOMP.
Note, that tori with the ric properties. In the following we use the family of l dimensional tori to produce examples of topologicallyymetrrically distinct CCs that are indistinguishable by HOMP.
number of nodes still differ number of topological and met-
19

---

Published as a conference paper at ICLR 2025
Diameter. For given adjacency neighborhood function (co).Ari.2 the Peddmmeeeemtter of combinatorial complex X' defined by:
diam(co)) (x) max (cco)Arr.r (1,2²); 2, EXr,
(23)
where Arc nz
is the shortest path distance with respect to neighborhood function (co)Arr,r2* Additionally, for (1....,f)). the (21, k) cross diameter is defined by:
diam (ao) (X) max min ( 2z,
(24)
=Ex, z'Sy yeX,
In this section we show that HOMP is unable to compute diameters of CCs, using (-dimensional tori as a counter example. Corollary B.6 implies that any pair of E-dimensional tori with the same number of nodes (0-cells) is indistinguishable by HOMP, therefore it is enough to construct such tori with different diameters. E.g. the tori T4,4,32 and T&,8,8 have the same number O-cells but different diameters and cross-diameters for any (co)adjacency function and k 1, 2,2,3, 3. This can be extended to tori of any dimensions. More formally we have the following proposition for the (0, 1) -iiameter.
Proposition B.7. If p'Tp.....pp and Tp:..... are E-dimensional tori satisfying
1. P1 .... Pt = 1/1 ... p/p
2. Vj E {I...., {}, P.. 2 3.
and
3. E ビ 14
then
diam A (Tpr + Ao. a (Tei....pi)
(25)
but for any HOMP model M,
M(T Mc) M(T pi)))...)))
(26)
Proof. Conditions and 2 imply that T pe and Tp of are indistinguishable by HOMP. To see that they have different diameters, observe that the graph induced on the nodes of Tpp.... by the adjacency neighborhood Ao.1 is the Cartesian product of the cyclic graphs Cyc(p)).... Cyc(p:). Consequently, since the diameter of a Cartesian product is equal to the sum of diameters over the factors of the product, we have:
Ai. (Ipi
Σ (iam(Cyc(p;)) =
Pj 2
P 2
1=1
j=1
j=1
(27)
diam diam (Cc((p)))
j=1
= diam Ao. (T pt))
Homology and Betti numbers. The r-th homology group of a cellular complex 8 encodes the structure of "r-dimensional holes" in the space (e.g. circle has a single 1-dimensional hole, sphere has a single 2-dimensional hole, etc). We denote the r-th homology of CC X by H.).). The rank of the r-th homology group (i.e. the size of the minimal generating set) is called the r-th Betti number, denoted by b, (2Y'.
Proposition B.8 (HOMP cannot distinguish complexes based on homology). Let T Tp be an L-dimensional torus and T' = T pi....pt L T Tpp....?? be disjoint union of two disconnected tori. If P1 ...... Pt pj .p....pp + př .., and Vj {I....,f), Ps.p), P),P),p} > 3, then T and T are HOMP-indistingushabbl but have different homology groups and Betti number of all orders: 'rr (0, f), (T) + (T"),, (T) + (T")..
?
"Homology is defined for general combinatorial complexes, only for simplicial cellular complexes.
20

---

Published as a conference paper at ICLR 2025
Proof. First, Lemma B.5 implies that the T, Tı, and T2 have common cover. Thus, since T and T" have the same number of cells, Theorem B.1 implies they are HOMP iniiiniiiist Additionally, for every (T) z(() (see e.g. Hatcher (2002) and since, T' is disjoint union of T1 and T2, HT" = (T; (T,) = z x Z = Therefore, Vr E {o...., ( (T) + HT")") and b, (T) ()) + 2({)) b, (T)).
Orientability. We now turn our attention to HOMP's capability to to detect another common topo- logical property: orientability. Loosely speaking, surface is orientable if one can distinguish be- tween an "inner" and an "outer" side of the surface. A common example two locally isomorphic surfaces where one is orientable and the other is not is the Möbius strip and cylinder. For an in- depth discussion about orientability and the Möbius strip see Hatcher (2002). We now realize both of these surfaces cellular complexes. A visualization of the construction can be seen in Figure We begin by defining two auxiliary functions.
1(b)
Definition B.9. For h. p E N define Payl Pmmb
z2 z2 by
(s) = (81, 82 mod p) Peyl
(28)
h.P Pmin (s)
(81,82 82 mod
82 mod 2p S p
(29)
(h +h+11- $1 mod r) $2 mod 2p > p.
h.P Using Payl and Pmmb we can costurct the cylinder and the Möbius strip.
Definition B.10 (Cylinder as CC). Given two integers h. p, the cylinder Cyl is a 2-dimensional combinatorial complex (S, X' rk) defined by:
S [h] x [p].
(30)
X {sk 8 E S E 1) k1 k2 =r,
r, pop
+ k) E S}.
(31)
X = Xo U Xi U22
(32)
where 8% is defined by:
8k (0y 1 k)) W' E [0,1), Sk..
(33)
Definition B.11 (Möbius strip as CC). Given two integers h, the Möbius strip Möb,,p is 2-dimensional combinatorial complex (S, X, rk) defined by:
S [h] ip].
(34)
X₂ = {sk 8 E S,
{0, 1) k1 + K2 = Pr + k) S}.
(35)
X Xo U U U
(36)
where 8k is defined by:
Sk
P s + k) K
(37)
We now show HOMP is unable to distinguish between CCs based orientability:
Proposition B.12 (HOMP cannot detect orientability). For any two integers h.p N such that h.p 2 3, and for every HOMP model M, Cyhn, and Möbn.p are HOMP-indissinguishuble but Cyln,p is orientable as a topological space while Möba.r not.
Proof. First, the fact that the cylinder orientable, whereas the Möbius strip is not is well known (see e.g. |Hatcher (2002) for proof). As for HOMP-indistinuuisaably consider the wide cylinder Cyl,22 with height h and perimeter 2p. We show that Cyl, covers both Cyl, p and Möb,, Since the two CCs are connected and have the same number of nodes, Theorem B. implies that they are HOMP-indistinguisshhle Denote by Š, 5oyl, smob and X. 2 mob the sets of nodes and cells of Cyl,,2p' Cyl,,p and Möb;,, respectively. Define p Š + Seyl and p' S - Smib by h.p
h.pl and p' Pmmsh g" p = Payl g
It's easy to verify that p($) = Seyt and p' p'(š) = Smis thus p and
21

---

Published as a conference paper at ICLR 2025
p' are well defined and surjective. p. p.pl induce maps P(S) + P(S and P(S) - P(Smih); by abuse of notation we refer to these maps by p. as well. To show that and pf are covering maps, we first show that they are rank- punk-presg (i.e. that p(X,,) X.S1 and p',,,) = X,r and then show that they are local isomorphisms. Recall that all elements of X, are of the form Sy for some 8 E S and k E {0, 1 such that 1 + l2 For every k' S k
P(Porr (3 k')) Poyth. (p(B) + k'),
(38)
so p(8))) = p(8)x- Additionally,
p((gg) 20 ( +k))
h.p (p'
81 S p
(39)
Pmmoo (p)(5) k-k,,K6))
$1 > p.
80
(p((3) (0'(3) + (-1,
81 Sp
($5)
(40)
$1 > p.
By the definitions X,, 2 and X we now have p( = Xد and p' p'(2,) = =xTmub as needed.
Since and p' are extended to P(5) from S, for every I, V, E X
x S y = p(x) S plu) and (z) S p'v))
= p(z), ply) S p(2) and ,'(x), (y) E (zz))
= = , p(=) C p()), ply) and p²(=) S p'(x),
Therefore, pnd p' preserve all natural neighborhood functions. Finally, since h. p 2 for v y X
and N E nat.2 y E (xx) > p(x)= * p(y) and o' (x) # p'()). This implies that and p' are local isomorphisms, completing the proof.
Planarity. A topological space considered planar if it can be continuously embedded in IR2. Proposition B. 12 provides us with the following corollary.
Corollary B.13 (HOMP cannot detect planarity). There exist pairs of cellular complexes X, X" such that the induced topology of X is planar while the induced topology of X' not, but X and X" are HOMP-indee indistinguishable.
Proof. The CCs Cyln,p and Möb;,p for p, h 2 HOMP-indistinguushabll according Proposi- tion B.12 The Möbius strip is not planar (see e.g.. Hatcher 2002)), whereas the cylinder is.
B.3 LIFTING AND POOLING
In this section, we rigorously state and prove Proposition 4.4 We begin by focusing on lifting
operations, proving Proposition (..4 triangular lifting, as used in Bodnar et al. (2021b) and Bodnar et al. (202 Next, we address pooling operations, proving the proposition for MOG pooling (Hajij et al. 2018). which was used to in conjunction with HOMP in Hajij et al. (022b).. While we only provide proofs for these triangular lifting and MOG, we note that this phenomenon generalizes to other lifting and pooling methods as well.
Lifting,
We first define triangular lifting on graphs, denoted by 3-CL.
Definition B.14 (Triangular lifting). The triangular lift of graph G = (V,E) {) is combinatorial complex denoted by 3 CL(G), with S V, V, = {{ o} a e V}, X1 = E, and X = {(x V 2, y 2).
We now formally state Proposition 4.4 for triangular lifting
Proposition B.15. There exist pairs of graphs and g' such that the combinatorial complexes
X' CL) and 3X" = (G') are indistinguishable by HOMP. This occurs despite the fact that the cross diameter diam?.., (X) is finite while diam? (X') ) is infinite.
22

---

Published as a conference paper at ICLR 2025
Proof. Given n, k N where k > 3, the star graph Star is constructed follows. We begin with cyclic graph of length n & with nodes d1...., On-k where a; ~ 0j + i i-j = =1 Secondly, we add & additional nodes, denoted as 61 b1..... . bg, and connect them to the existing graph via by ~ an-i and by ~ an-itl. with all index computations carried out modulo n k. We consider pair of graphs and g' defined by g ,t and g' Starn,, Starn, where represents disjoint union. See Figure for for an illustration of the case k = 3,n = 2.
mod n-k.
X'
X
Figure 10: A pair of indistinguishable CCs produced by triangular lifting. The left-hand CC covers each connected component of the right-hand
hand CC.
Since n & 3. the only triangles in G and G' are of the form {be, ainx 0in++)) Denote the combinatorial complexes constructed from g and g' by applying triangular lifting as X' and X', respectively. Additionally, denote 3 (LC(rSt by X Since X' consists of two disconnected copies of X²' and the complexes X' and X' are of equal size, Theorem B. implies that in order to show HOMP cannot distinguish between X' and X", it suffices to show that X' is cover of X. Letting ad S" be the node sets corresponding to CCs X, X', we construct a covering map p: S S* defined by:
p(a:) = a mod n-k
(41)
p(b;) = b/ mod k-
Note that p induces map from P(S) to P(S*) where P(-) denotes the power set. We abuse notation and refer to this function by a as well. We notice that p is surjective, and that for any pair of nodes u, in graph G we have:
u u~ v == p(u) ~G- p(v).
(42)
This implies that preserves triangles as well. addition, since n n >> 3 p is locally injective. Thus, P is covering map, and X and X' are indistinguisable by HOMP. Finally, it is evident that diam? (2")
since it consists of two disjoint connected components, each containing non-empty set of nodes (0-cells) and triangles (2-cells). Conversely, diam (X) < oo because consists of a single connected component.
Pooling. For the pooling example we focus the Mapper algorithm [Singh et al. (007); Hajij
et al. 2018); Dey et al. (2016), a topology preserving pooling algorithm which was previously used combination with HOMP Hajij al. (2022b). We now define mapper on graphs (MOG), pooling procedure that takes a general graph as input and produces 2-dimensional combinatorial complex.
Definition B.16 (Mapper on graphs). Let G (V,E) be graph, g - RR be a node function, and U = {Ua)ae an open covering of IR. The MOG pooling of the graph, MOG(G) = (S,X, rk)
is given by the following consturction.
1. Compute the pucl-back cover g" (4) {g (g--(UU)) (Ua))
2. Construct VMOG to be the set connected components of the sub-graphs induced by g" (4)).
3. Construct the pooled CC to be (S, X, rk) with nodes S V. cells X VUEU and rank
0 E V
rk(x)=
x E 3
VMOG-
23

---

Published as a conference paper at ICLR 2025
In the context of shape detection, natural choice for g is the average shortest-par distance g(v) = Mij Evev d(u, v), as it only depends on the graph structure and is thus invariant to geo- metric transformations of the features. As for the covering U. natural choice is {(p-i, n7 +e HEN for hyper-parameters 7/, e E R. We now formally state Proposition 4.4 for MOG pooling.
Proposition B.17. There exist pairs of graphs 9 and g' such that the combinatorial complexes X MOG(G) and X' gO) are indistinguishable by HOMP. This occurs despite the fact that the (0, 1, 2) cross diameters of the two CCs are different.
5//5
p *
Two combinatorial complexes constructed by MOG pooling and their common cover. The two cells constructed by the MOG algorithm are marked in blue and the covering map is defined based on the node labels.
Figure 11:
Proof. We begin with base example. Let and G' be the two graphs depicted at the bot- tom of Figure II before applying the MOG lifting procedure, and denote their node sets by S {81, .s,,..., _8 and S'
-6.....,%). with the order shown in the Figure. Note that the sets P1 = {81, 82, 85, 86} P2 = (13.81) form a partition of S, and nodes within the same parti- tion set are automorphic (i.e., there exists graph automorphism mapping one node the other). The same holds for Pf = { s/. s $6} PS {sg, s/4. Thus, the function g. defined as the av- erage shortest path distance (SPD) of each node, constant on each of these sets. This implies that by choosing a sufficiently fine covering (i.e. selecting small enough 17), the 2-cells deñned by the MOG algorithm for graphs G and g' will be x = {81,82) x2 = {sg, 84), I3 {85, 86) and o {s' 222 2 (s's, ' connected components). Defining X' MOG(G) and X' MOG(g"), we now aim to show that HOMP cannot distinguish between these two CCs. Figure II depicts X, X'' and an additional com- binatorial complex X' which covers both of these complexes. Since X' and X' are connected and of the same size, Theorem B.T shows that these complexes are indistinguishable by HOMP. An- other quick calculation shows that diam? An, (X) = 3 while diam Ao, (x') = 2 concluding the base example.
{s/, 56) respectively (We split sets Pi and Pf to their
To demonstrate that this phenomenon occurs in larger graphs where the MOG procedure produces a small number of 2-cells, we expand upon the aforementioned example. For each integer n > 3 let Cyc(n) denote the cyclic graph of length with the node set V., {uI...., Jn where v; Uú and only if i- = +1 mod n. Define Gn = g x Cyc(n), G' = G' x Cyc(n), where x denotes the Cartesian graph product. We now demonstrate that the proof above remains valid for Gn. and G' for any n 2 3. First, defining Pt,, = P1 x Vn, Pa, = P2 x V,, where here x denotes set cartesian product, notice that since all nodes in P; G isomorphic, and all nodes in V,
24

---

Published as a conference paper at ICLR 2025
Cyc(n) isomorphic, all nodes in P.,n are In isomorphic. The same holds for Pí.n = P1 x Vna P2,, P/ x Vn. Thus, again, the function g defined as the average shortest path distance of each node, is constant on each of these sets. This implics that by choosing sufficiently fine covering, the 2-cells defined by the MOG algorithm for graphs 9, and 9 will be Zi,7 22 V. and Ti.n = x x Vn respectively for all i E [3]. Defining X, = MOG(G,). Xr = MOG((() we now aim show that HOMP cannot distinguish between these two CCs.
We define & to be the 1-skeleton of X, Gn 9 Cyc(n) and Xr to be the CC whose 1-skeleton In and whose 2-cells are: {ar V E 82). Let S S, S S" be the covering maps from X to X' and X' respectively. as depicted Figure 11 Define Pn. SSx Vn S V, by (s, (p(s), v) and P/a S Vn S x Vn by Pr,ss, v) = (s), By the definitions of Nn, Xy and &n, these two maps are covering maps from Xr to Xx, respectively. Since Xn Xt, are connected and are of the same size Theorem B. implies they are indistinguishable by HOMP. Secondly Since Gn is graph cartesian product, for every us, (8', v') E x' gVn, we have:
dę, ((s, (s', e')) 8s) + (eyc(m)(e,)))
(43)
Thus, is easy to check that: diam Ao, (R,, diam? (X) = diam"A,, (X,) diama.,, (X*) = 2 concluding the proof.
The same reasoning shows that
C CELLI-CELLULAR NETWORKS
In this section we motivate and formally define MCN, expanding the discussion in Section 5 We rigorously define both the equivariant linear updates and the general tensor diagram forward pass.
Multi-cellular cochain spaces As discussed in Section | (E + 11-tue ls E Ne+1, the space of k-multi-celluuar cochains is defied by:
given an Ê-dimensional CC X' and an
ck (X, = (h hy X
x
X Rd..
(44)
Multi-cellular cochain spaces are natural generalization of standard cochain spaces, providing way to represent diverse types of CC data. For example, when k c;, we get that Ch: (X, IRd) is the space of function he, Xr - Rdd, i.e. C* (X, (X.R)) is the space of all possible i-rank cell features (i.e. C = C³ ). In addition, for any pair of integers r2, the incidence neighborhood function Br,.z can be encoded the map h Xr. x Xrz + Rd defined by:
{
Bri.ra otherwise.
h(z,y)
(45)
Thus Br..,, can be regarded as an element of the space Cary tCrg, Finally, neighborhood functions of the type (co) can be similarly encoded as the map h X²2 + Rd defined by:
h( v) {
E (co) (x)
(46)
otherwise.
Thus Aro) can be regarded as element of the space C2er..
Multi-cellular cochain spaces recover many linear spaces studied in several previous works. For example, Cker matches the features space of k-IGN layer operating on r-cells, and Ce., terz corresponds to the input space of the exchangeable matrix layers introduced in Hartford et al. (018))
Equivariant linear maps between multi-cellular cochain spaces. Let X' be combinatorial complex. We define n, = |xrl. representing the size of X, For a tuple k = (ko...., we define the product space x = Xxe .... Xhe, The group Sna X... X Sn, is denoted by G. We aim to find a basis for the space of equivariant linear layers C² C*(X,, Bdd) CK (X for each pair of tuples k. K.. Since the space C can be identified with R xx.xn xd the space of linear maps between the two can be considered as the space of matrices:
ck Ck 1Rn0 x.. xnx ke x xxx x.
(47)
25

---

Published as a conference paper at ICLR 2025
where we use & to denote the tensor product of vector spaces. The index set corresponding this
space of matrices is X x [d] x² x [d"].
Notice that the group G acts naturally on 2 X For each G-orbit y and integers ji [di]. ja E [d2], we define a matrix B7.Jidd
ITd"" to x xx..xxx. x
ke xdx x x
2 xd';
[ (a, E), E7 i1 fi, i2 = 82
B Ba.hjaa a,11.bii2
(48)
otherwise.
Here [mo] ko x [m/] 2 b [no]% x ... x [mi] i [d] ln E [d"]. If hh C* and h' -Bo we have:
h'(b); = Eiabley h(a), j
(49)
otherwhise.
where here by abuse of notation b were used interchangeably to describe multi-indices and multi- cells. These maps were established as a basis for the space of all equivariant linear functions L :
R" fo xx-xx xd + R3 F6 x...x,, H/2 xd in Maron et al. 2018) and thus can be used to characterize the space of equivariant linear layers L C + C² This framework encompasses many layers from previously studied models. For example, by setting & k' k er, the space of equivariant linear layers corresponds to the space of k-IGN layers, which take as input graphs defined on the k-rank cells of the input complexes (i.e. graphs whose node sets are X,)) Similarly, with k' e, ey for r * r' E N, this space aligns with the space of linear maps used to construct the exchangeable matrix layer as described in Hartford et al./ (2018).
We can now use this basis to construct learnable equivariant linear layers by taking a parametric linear combination of the basis functions:
F(h) 3
Tihida Brshssh
(50)
To construct MCN, We augment HOMP architectures with these equivariant layers. This is embod- ied by incorporating equivariant linear layers into the tensor diagram scheme. Figure 5 depicts MCN tensor diagram. We now describe the components of the MCN scheme.
Diagram. Similar HOMP tensor diagrams, MCN tensor diagrams are layered directed graphs with labeled nodes and edges. Each node is labeled by a multi-cellular cochain space, extending the class of node labels used in HOMP tensor diagrams. Directed edges with source and target nodes labeled by ger can be labeled by any neighborhood function, while edges between nodes labeled by other types of multi-cellular cochain spaces are labeled with the new label "equiv".
Input. The input to the MCN model is determined by the 0-th layer of the tensor diagram, whose nodes can be labeled by the following types of multi-cellular cochain spaces: (1) nodes labeled by C which take the r-rank cell features input; (2) Nodes labeled by C ter, which take the matrix form of the incidence neighborhood Br,r, as input; (3) Nodes labeled by C which take the matrix form of the (co)adjacency matrices Ar.
Update. At each layer of MCN tensor diagram, if is node labeled by Ch compute multi-cellular cochain (1)) e C* by
h
Mu, (x)
(51)
())
where xc E Ck and pred(v) denotes the set of predecessor nodes in the diagram. Here messages My,v E Ck are computed based on the label of the edge (u, v). If the edge is labeled by neigh- borhood function N,, (in which case and u are labeled by standard cochain spaces), the message
My.y computed by
MLP u.v (h (u) (h()).
(52)
(x)(())
26

---

tensor diagrams Published as a conference paper at ICLR 2025
Note that this is the exact message used in HOMP tensor diagrams. If the label is "equiv", the message is computed as described in Equation 50 By slight abuse notation, we often denote the collection of multi-cellular cochains associated with the nodes in layer by h("), For all other labels, the message follows the standard tensor diagram update process. The last layer of the tensor diagram contains a single node representing a final readout layer (See Appendix G.I for implementation details of both the update computation and the possible readout layers used in this paper).
D SCALABLE MULTI-CELLULAR NETWORKS
In this section, we provide an in-depth description of the SMCN model presented in Section 6 To construct SMCN, We augment MCN diagrams, reducing the number of possible node labels and adding new "SCL" update. Figure depicts SMCN tensor diagram. We now describe the components of the MCN scheme. For the rest of this section, we borrow the notation scheme of Appendix
Diagram. Similar to HOMP and SMCN tensor diagrams, like MCN, layered directed graphs with labeled nodes and edges. Each node is labeled by a multi-cellular cochain space C* but unlike MCN we restrict k such that Σ < Thus reducing memory complexity. Like before, directed edges with source and target nodes labeled by C can be labeled by any neighborhood function, while edges between nodes labeled by other types of multi-cellular cochain spaces can be labeled with the new label "equiv". Additionally, directed edges with source and target nodes labeled by gerte,' can labeled by 'SCI."
The input the SMCN model is identical to the input the MCN model. As will now show, the matrix form of neighborhood functions B Br.ra play a similar role to that of node marking
Input.
policies in subgraph networks [Bevilaqqua et al. (202T): Frasca et al. (2022); Zhang et al. (2023b). Subgraph networks process feature maps of the form h V
where V is a set of nodes.
Node marking policies employ an initial feature map of:
{ ==
(v, u)
00) (v,
(53)
otherwise.
Similarly, SCL updates process cochains of the form h: : Xr x Xr, + 1Rd, and the matrix form of Br,rr satisfies:
{
x cy
B v)
(54)
otherwise.
The SMCN update is computed in the same way as the MCN update is computed (see Appendix C), where the message of directed edge (u, v) labeled by "SCL." is computed by
Update.
(2, =
MLP
( h( (n (co)A - (00) ( (2)1 b ba, (2)) (x), ITT (0).
(nSyy-
r=0,-=0
(55)
where if Qi C Xr, and Q2 Xr² Eyeq, br.-' The SCL update can be considered aggregation of subgraph updates the aug- mented Hasse graphs induced by the input CC. For each choice of r, r' the compotation inside the aggregation function in Equation 55 identical to CS-GNN (Bar-Shalom et al.) (224)) update on the augmented Hasse graph (see Definition 6.1 H((o))rryr where the set of "super-nodes"
of cells, he. Ex'e,, ha and h
Xx, and the connectivity of the super nodes is given according to the Hasse graph H Aro More
specifially, for rı 12 = 0, r, r' we recreate the GNN-SSWL+ Zhang et al. 2023b update.
Computational complexity. The computational complexity of SMCN depends on the choice of multi-cellular cochains spaces in the tensor diagram. For C'-, te ( te updates the worst- case computational complexity for the most general model is O (E2.d. d. nry m,,)) where is the maximal degree w.r.t any neighborhood function. In our experiments, taining a single type of multi-cellular cochains spaces resulting in models with a runtime complexity
CCS-NN is subgraph model which uses subsets of nodes construct the bag of subgraphs. These sets of nodes are termed "super-nodes".
27

---

Published as a conference paper at ICLR 2025
of O( no n1) and O(d no n2)). As we demonstrate in Proposition 6.6 SMCN architectures with runtime Old ny n2) are still strictly more expressive than HOMP. This is useful, since in most natural cases n2 < ng. This allows for flexibility in trading off computational complexity and expressive power.
MCN EXPRESSIVE POWER E
In this section, we analyze the expressive power MCN defined in Section 6 We begin by formally defining CC isomorphism, described in Haju et al. (2022b).
Definition E.1 (CC isomorphism). pair of CCs (S, (S, (S', X², x²rrk) are isomorphic if there exists a bijective map X' + X' such that:
1. rk(x) rk' (p(x)) E X,
2. x C y p(x) C p(y) Wr,yER'
Is there exists isomorphism P : X - X' we say that X' and X' are isomorphic; if such an isomorphism does not exist, we say that X' and X' are non-isomorphic.
Proposition E.2 (MCN expressive power). If X and X' are non-isomorphic there exists an MCN model M such that
M(X) + M(X").
(56)
Proof. First, let H -V,8) and H' (V',') be the Hasse graphs of X and X respectively, defined by
v= X,
(57)
='=
(58)
E ((x,V) Ex X x S y. rk(x)) = = rk(y) - 1},
(59)
8' = ((x''')) x' d' rk'))' rk' (2/) 1 1}.
(60)
was shown in Hajij al. (202bb) that a pair of CCs isomorphic and only if their corresponding Hasse graphs isomorphic. Therefore, in our case, H. and H' are non-isomorphic graphs. Since any pair of non-isomrephic graphs of size n are n WL distinguishable, and I-IGNN networks can distinguish between any pair of k-WL indistinguishable graphs (see Maron et ( (2119), it is enough to prove that there exists a MCN model which is able to simulate any k-IGN network on the Hasse graphs. Let be the adjacency matrix of H. and define n |, n2 |X, for all E {O....,f). A can be decomposed into block matrices A A for 11, E {0. {} defined by:
Onpxny
ri + r2 +
A 11:T2
(61)
1,
where Br is the matrix form of neighborhood function Br,.z. matrices '' can be view as a multi-cellular cochains hr E C te (X, R) so A can be realized as an element of Q ==
ter (X, R). Recall that all neighborhood matrices Br,,,, given input the MCN model and so we can recover A. To show that MCN can simulate any k-IGN update on A, we need to show that can compute L(AA for any S, Squeiiiirr linear function : Q - Q where Q represents taking the tensor product of Q with itself & times. Let G < S, be the subgroup of permutations preserving the subsets {l....,
x X Cer
{no + I...., no + 7uJ..... {no + + + 1,.... noo + n G = Smo X ... x Sn, C [n]] Since G is a subgroup of Sn, all S, equivariant linear maps are also G-equivariant. Thus is enough to show that we are can compute L(h) for all G-equivariant lincar maps L Q&k Q*k'
The space Q X" x C te () can be embedded into the multi-cellular cochain space Cle+s (X, (R((1)))) via the following map:
T(h) ... m2) ni 0==000=0
h (Fry
(62)
where || stands for concatenation, 1 = (I,..., 1) E g!+1 is the all ones vector, H, E X, is a cell of rank and h Q composed of the multi-cellular cochains h hirr E Cer, (X, R). MCN can
28

---

Published as a conference paper at ICLR 2025
any linear function L Chk (X, (()))))))))) (X (X,,((+)))) which is G-equivariant, and so can compute L(h) for all linear maps as defined above, concluding the proof.
F SMCN EXPRESSIVE POWER
F.1 TOPOLOGICAL AND METRIC PROPERTIES
In this section, we formally demonstrate the SMCN's ability to mitigate many of the expressive limitations demonstrated in Appendix B We begin by providing useful lemma that allows to leverage several expressivity results from the subgraph GNN literature in our setting. We then pro- vide in-depth discussion on the ability of SMCN to express each one of the four aforementioned metric/topological properties: diameter, orientability, planarity, and homology.
Lemma F.1. For any CS-GNN (Bar-Shalom et al. 2024) model M operating on the Hasse graph Haao) ry using cells of rank 2 T1 as super-nodes, there exits an SMCN model M', such that for any CC of dimension 2 12, M(H((co)Annrr)) -M') (X).
Proof. First, note that the incidence matrix Br,, E Ceri ter is equivalent to the "simple node marking" defined in BBar-Shalom et al. (2024), so SMCN can recover the input to the CS-GNN architecture, Second, by taking
(I, MLP(x, v) = and r' T1,
MLP
(63)
otherwise
for some fixed MLP, Equation 55 becomes identical to the CS-GNN update.
Remark F.2. For the case where
(i.e. super-nodes are regular Hasse graph nodes) the CS-
GNN architecture becomes equivalent to GNN-SSWL+ (Zhang et al. 2023b).
Diameter. We first show SMCN is capable of fully leveraging the information provided by the (cross) diameters of an input CC. see Appendix B for definition.
Proposition F.3 (SMCN can compute diameters). I X" are CCs such that
diam's, A,,,, (X) # diam"A,, (X'),
(64)
for T1, T2, r E N with T1 S S, then there exists an SMCN model M such that M(X) + M(X')
Proof. In Zhang et al. (2033), it was shown that GNN-SSWL+, with standard node marking applied graph G (V, E), can compute a final feature representation:
(T) h 1
= dg(u,v) v) for 1 V.
(65)
By taking the maximum over ha,e, GNN-SSWL+ can distinguish between graphs with different diameters. Similarly, It was shown in Bar-Shalom et al. (2024) that CS-GNN with standard node marking applied graph G (V,E) and super-node set V can compute final feature represen- tation
(T' h 3,0
dS, for V and S E V*
(66)
By taking the maximum over h S. CS-GNN with standard node marking can distinguish between graphs with different cross diameters. Thus, applying Lemma [.T and Remark F.2 on the Hasse graph H.r...n with X as "super-nodes" we get that SMCN can distinguish between CCs with different (cross) diameters.
Orientability and planarity. We now show SMCN is able to separate the cylinder and the Möbius strip. This implies that SMCN is strictly better than HOMP at detecting planarity and orientability. Understanding SMCN's ability to fully detect orientability or planarity still and open question and left for future work.
Proposition F.4 (SMCN can separate a cylinder and a Möbius strip). For any two integers h E N such that h p 2 3, there exists an SMCN model M, such that:
M M(Cyln.p) # M(Möhn.p)
(67)
29

---

Published as a conference paper at ICLR 2025
Proof. First, using the terms "edge" and "1-cell" interchangeably. define two types of edges Cyly,p and pö An edge æ E X1 called an interior edge if [=), > 1, otherwise it's called boundary edge. We denote the boundary edge graph (node set are the nodes contained in the boundary edges and edge set is the boundary edges themselves) a CC X' by 0.Y. We construct the model by first using a B1,2 aggregation to get the cochain h E C (X,
h ha) (x) dega, (2).
(68)
Next, we use an equivariant linear update construct the defined by:
cochain (22) E 2 (X, R?)
,P3 d (11) deg (I2),
(69)
where, || denotes concatenation. Recall that the matrix form of co.A1,0 defines a cochain ccoA1 (2e1 which can be used as input to SMCN. Using DeaA1, can now construct
3
degs... (2 (x1) (#2))
(70)
Finally, using stack of equivariant linear layers, we can construct fourth cochain h MLP(h We use the Memorization Theorem Yun et al. 2019), and choose MLP that sat- isfies
(4)
[1 a-b=c- 0 otherwise.
MLP b,
(71)
(4( represents the adjacency matrix of 0X. @Cyl,,p is composed of two disconnected cycles of length p: aMöb,.p is composed of a single cycle of length 2p. These two graphs are distinguishable by subgraph architectures like GNN-SSWL+. Thus, using Lemma ET and Remark F.2 can continue the construction of M so that it will be able to differentiate between Cyln.p and Möb
Homology. We first show that SMCN is able to count the number of connected components i.c. the 0-th homology.
Proposition F.5 (SMCN can count connected components). Let X, be CCs. If the number of connected components of the augmented Hasse graphs H.Ar and H' H'A.g.n is different for some 01,72 E N then there exists an SMCN model M such that M(X) + M(X').
Proof. For graph G. C(g) represents the set of connected components of G, and Gv denotes the connected component of node E V. Using Lemma F. and Remark F.2] it suffices to show that GNN-SSWL+ can distinguish graphs with different numbers of connected compo- nents. It was shown in Zhang et al. (2023b) that adding additional aggregation of the form hy + Evey ha to GNN-SSWL- does not affect its capacity to separate graphs. Therefore, for the remainder of this proof, include this aggregation in GNN-SSWL+, As previously demon- strated, GNN-SSWL+ can compute a feature vector of the form:
du for u, v V. a,e
(72)
If u and v in different connected components, their distance is encoded -1 Let g : [-1, > IR continuous function such that:
50 if -1
91 (x)
(73)
[
if 2 --
We can approximate 91 using an MLP and apply it to (t) to obtain:
(++1) 0 if & Gn.
(74)
if u E G..
We now take (t+2)
Evev h (++1)
to get
h ((+2)
GGul-
(75)
30

---

Published as a conference paper at ICLR 2025
Define 22[1,||] + R to be
1
g2(x)
(76)
We can approximate 92 using an MLP and apply it to ha. to obtain
(++2)
(143)
(77)
It was shown in Zhang et al. (2023b) that the final output of GNN-SSWL+ model can be computed based on the final feature vector Nu.. by
hout
Σ M,DEV
(78)
Applying this to ba.o we get
(f+3)
V G'EC(G) VEg- 19
bont Σ W.EVV
Σ
Σ M= [[|C(())
(79)
Gall
C-EC(
Now let G, G' be a pair of graphs with different number of connected components. If these two graphs have a different number of nodes, they can be easily distinguished by GNN-SSWL+. On the other hand, if they have the same number of nodes they can be distinguished by GNN-SSWI+ based on Equation 79 Thus, we have shown that an augmented GNN-SSWL+ model can distinguish between HArg.r2 and H'' Ar and therefore, there exists an SMCN model that can separate X and 2"
Since the 0-th homology satisfies Ho(x)- z/((xi additionally get the following corollary.
Corollary F6 (SMCN can compute the 0-th homology). If X are CCs such that the 0-th ho- mology group of their induced topological spaces are different, then there exists an SMCN model M such that M(X)) + M(X").
Exploring SMCN's capacity to differentiate between CCs based on their higher-order homology groups is left for future work. As a first step, we show that SMCN can successfully separate a natural family of CCs two-dimensional surfaces embeddable in R based on any homology group/Betti number.
Proposition E.7 (SMCN can compute homology groups of surfaces). Let X, be two cellular complexes that are realizations of 2-dimensional manifolds (with or without boundary) M, M' which are embeddable in R3. If E N such that H,MM) + H,(M") then there is an SMCN model M such that M(X) * M(X').
Proof. First, since M is 2-dimensional, the only non-trivial homology groups it may have are of order S r
The 0-th homology group of M, of the form Ho(M) A where Kg is the number of MM's connected components. Furthermore, as each connected component of M is connected 2-dimensional manifold with a boundary that can be embedded in IR3 it must either be orientable or have non-empty boundary. If such a component is orientable, then by the Poincaré duality, its second homology group Z. On the other hand, if has a boundary, 1-dimensional cellular complex, and thus its second homology group is trivial. Therefor, (2(M) z²a where l2 is the number of connected components of M with no boundary. Finally, since M embeddable in R33 its 1-st homology groups is H1 (MM) z for some integer ky. The Fuler characteristic of the manifold M defined by ko h1 + h2 can be computed using the number of cells of X' using the following formula:
homotopic to
x(M) = 12 ki + kn = |
|
+ [2]-
(80)
Thus in order to separate X' from X" we need to be able to construct SMCN model that is able to separate CCs that are different either one of the following three quantities:
1. The Euler characteristic.
2. The number of connected components.
31

---

Published as a conference paper at ICLR 2025
3. The number of connected components with no boundary.
Computing the Euler characteristic is be computed by standard HOMP updates, as it is a function of the sizes of No. 1,, and Xg. For the second quantity, we have seen SMCN models can separate CCs with a different number of connected components in Proposition F3 As for the third quantity, connected component of X' has a boundary if and only if it contains 1-cells whose degree with respect to the neighborhood function B1, is exactly 1. We can use a stack of standard HOMP layers compute the l-cells features
h2 (o x is in the same connected component as a boundary edge otherwise.
(81)
Using h, we can adjust the proof of Proposition E.5 by summing in Equation 79 only over 1-cells for which h = O, resulting in the number of connected components of X' with no boundary. This shows that SMCN can distinguish CCs based on either one of the aforementioned three properties, concluding the proof.
F.2 LIFTING AND POOLING
In this section, we rigorously state and prove Proposition 6.6 which appears in Section 6.1 for graph triangular lifting and for the MOG (graph Mapper) pooling algorithm. Corresponding results for the HOMP case can be found in Appendix B.3 We start with triangular lifting (Definition 14).
Proposition F.8. There exist pairs of graphs G and G' such that the combinatorial complexes X 3-CL(G) and X' =g') are indistinguishable by HOMP. but can be distinguished by an SMCN model with asymptotic runtime O(maey Bo "02 - T) where ny is the number of nodes in the original graph, n2 is the number of 2-r22kkk cells constructed by triangular lifting m is the maximal degree and T is the number of layers.
Proof. In Proposition B.15] we find a family of graph pairs whose triangular lifts are indistinguish- able by HOMP despite having different diameters of type diam" In Proposition F.3 we saw that using only SCL updates, SMCN can compute this type of diameter and is thus able to distinguish between the aforementioned pairs of CCs. Recall the SCL update rule:
(2, =
MLP (n.9) 1/0 ( -=0,-==0
(1)) 110 (co)) (s), (co)A , (x)) h (e. h8g (w). (x))
where if Qi S X,, and Q2 S. Xr are sets of cells, har == Ex'O, h and h Eyee. hz.y'. Observing the proof of Proposition F3 we note that order to be able com- pute diam It is enough to use only values corresponding to = r' 1, 0, 2. the asymptotic runtime of this type of SCL layer is O 7h n2). Thus the overall runtime of our SMCN model is O(maeg no n2 T), completing the proof.
We now move to MOG pooling.
Proposition F.9. There exist pairs of graphs G and G' such that the combinatorial complexes X MOG(G) and X" = MOG(G") are indistinguishable by HOMP, but can be distinguished by an SMCN model with asymptotic runtime O(d no n2 . 'T) where no is the number of nodes in the original graph, n2 is the number 2-rank cells constructed by mapper dd is the maximal degree and the number of layers.
Proof. In Proposition B.17 we saw a family of graph pairs for which the CCs obtained by MOG pooling are indistinguishable by HOMP despite having different (0, 1, 2) cross diameters. Propo- sition [.3 we saw that using only SCL updates, SMCN can compute this type of diameter and is thus able to distinguish between the aforementioned pairs of CCs. As seen in the proof above, by choos- ing an appropriate aggregation function X the runtime of each SCL layer becomes O(d no m22 (note that by stacking layers that use this aggregation we are still able to compute diam ". the overall runtime of our SMCN model is O(d no n2 T), completing the proof.
). Thus n
32

---

Published as a conference paper at ICLR 2025
F.3 COMPARING THE EXPRESSIVE POWER OF SMCN WITH BASELINES
Section 7 compares the empirical performance of SMCN with several relevant baselines. In this sec- tion, we briefly discuss the expressive power of SMCN in comparison to each one of these baselines.
GNNs. In Section 7 we evaluate SMCN against various MPNNs (c.g., GIN, GCN), subgraph net- works (e.g.. DS-GNN (Bevilacqua et al. (02T), SUN (Frasca et al. 2022). , GNN-SSWI+ {Zhang et al. 2023b)) and other expressive GNNs (e.g. PPGN (Maron et al. 2019), PPGN+ (Puny et al.) 2023 ). It important to note that since GNNs are designed to process graphs, a meaningful compar- ison of expressivity with SMCN is only valid when SMCN is applied to lifted graphs (see discussion in Section 4.3 Among all MPNNS and subgraph networks, GNN-SSWL+ is the most expressive. using the Ao,1 neighborhood function (which corre- sponds to the original graph), it follows that SMCN is at least as expressive as all the MPNNs and subgraph networks, regardless of the chosen lifting procedure. Furthermore, SMCN can implement edge deletion subgraph policies, which, as demonstrated in |Bevilaquua et al. (202T), are capable of distinguishing certain instances of graphs that are indistinguishable by the 3- 3-WL test. Since the expressivity of GNN-SSWEL test, follows that SMCN is strictly more expressive than all the aforementioned MPNNs and sub- graph networks. Finally, the expressive power of PPGN and PPGN+ has also been shown to be bounded by the 3-WL test (Maron et al., 2019, Puny et al. 2023). indicating that there are instances of graphs distinguishable by SMCN but not by PPGN or PPGN+. A comprehensive comparison of the expressive power of PPGN and SMCN is deferred to future work.
Since SMCN can implement GNN-SSWL
has been shown in Zhang et al. (2023b) to be bounded by the 3-WL
Topological neural networks. We compare SMCN with four topological neural networks: CIN [Bodnar et al., 2021a), CIN++ GGusti et al. 2023). CIN + CycleNet (Yan et al., 2024) and Cellular Transformer (Blllester et al., 2024). SMCN can directly implement CIN and CIN++ through the use of suitable tensor diagrams, establishing it as at least as expressive as these architectures. Fur- thermore, CIN and CIN++ are HOMP-based architectures. As demonstrate in Section 66.1 SMCN can distinguish between CCs that HOMP architectures cannot, making it strictly more expressive.
Additionally, CycleNet processes graphs by applying BasisNet + spectral embedding (Lim et al. 2022) to the I-Hodge Laplacian of the input graph. The resulting output is then used as edge features, which are subsequently processed by a final CIN applied the graph lifted to a cellular complex by cyclic lift. In cases where the input graphs are simple and undirected, the 1-Hodge Laplacian is exactly equal to the coadjacency matrix co.o,11 (plus a diagonal term of 2/ which can be ignored). SMCN can apply subgraph GNNs to the coAoo, Hasse graph, and use the resulting features as inputs for a CIN model. This reduces our proof to demonstrating that subgraph GNNs are more expressive than BasisNet. As recently shown in /hang al. (2024). BasisNet spectral embedding is strictly less expressive than PSWL, a subclass of subgraph GNNs that is itself less expressive than the base subgraph GNN used in SMCN. This shows that SMCN is strictly more expressive that CIN + CycleNet.
Finally, the Cellular Transformer breaks equivariance with respect to G = S., .... Sn, using Laplacian positional encoding, allowing to gain expressivity. Architectures that break equivariance often fully expressive, but they can also incorrectly differentiate between instances of isomor- phic CCs. Consequently, the Cellular Transformer is not a fair comparison to SMCN in terms of expressivity.
G EXPERIMENTAL DETAILS
Setup. All models are implemented in PyTorch (Paszke et al., (219)) using the Py Torch Geometric framework Fey & Lenssen 2019). We used TopoNetX (Hajij et al. (022)) and NetworkX (Hagberg) et al. 2008) to perform lifting operations. Hyperparameter tuning carried out using Weights and Biases (Biewald 2020). All experiments were conducted on a single NVIDIA A100-SXM4-40GB GPU. For each experiment, we report the mean and standard deviation over 5 runs with random seeds from 1 to 5. Reported test scores are computed at the epoch achieving the best score.
G.1 MODEL IMPLEMENTATION
The SMCN framework is highly flexible, allowing for a wide range of model construction ap- proaches. To narrow down the search space, we focus two types of tensor diagrams, sequen- tial and parallel, each composed of smaller blocks and updates formally defined below. As in the main body, we sometimes omit the subscript in h, when the rank is clear from context. We also
33

---

Published as a conference paper at ICLR 2025
the notation he Exeeha hg. Additionally, Cat(x y| == MLP, (MLP(()) MLP)(y)). All MLPs have single hidden layer.
the augmented concatenation operator
Initialization. the case X' lifted from a graph with node and edge features, these features are used the 0 and 1 cochains respec- tively. Otherwise, the O, and cochains are initialized with zeros. In case the initial features are categorical we apply an embedding layer. Similarly to Bodnar et al. (2021a), we initialize the 2-cell cochain by
Moi
Asia
t
(h2 (
)m (16))
h Da'
(82)
C
C
C22
x' oo
Figure 12: CIN Block.
CIN block.
The first HOMP block consider is the CIN block from Bodnar et al. (201a)). whose
tensor diagram illustrated Figure 12 A CIN block updates the cochains h h and h2 via the following update rules. For x E 2o.
(c)
(1+1) M.P
co+
Σ
MLP
(
h 11
(83)
(x)
for x E Mi,
h [(+1) = Cat (1+c)) + - (x)())
(
Σ
MLP (1
h (t)
0,2
((m,ar)
(84)
and for E X2.
h(t1) = MLP!!' ((1 E2) h2) + h + (x))
(0)1
(85)
where if x X,, Elx,x') Ey Xx41 x, S v) and co. c), ci c2 non-leamablee hyperparameters.
Custom HOMP block. In addition CIN blocks, also "custom HOMP" blocks that are designed to minimize the influ- ence of 1-cells in the block update, thereby reducing dependence on the edge structure of graphs. Empirical results, as shown in Table 2 demonstrate that this approach improves performance on certain topological property prediction tasks. The exact update for this block defined via the following rule. For No.
An,1
Fo.a
CO
Cl
Figure 13: Custom HOMP.
h (++1) = Cat (1 + h)) (0
(o)) ||(1 + h) + (0
1
(86)
for x X1.
(1+1) =h.0)
(87)
and for x E X
h h(+1) MLP(() (11+ h2) + h (
(88)
Multi-cellular cochain initialization.
SCL layers take as input multi-cellular cochains of the form bo.1 E Cu,1 and b E Co,2. These multi-cellular cochains are initialized with
(0)
(+) (b = (LP(*) r,1 (Ah (2) )., + MLP( r.2 (hh )r.)) + MLP(t)
r33 (mark(21, +2),
(89)
where mark mark(x1, x2) a marking strategy. Similarly to Zhang et al. 2023b) and Bar-Shalom et al.
2024 consider two marking strategies: (1) binary marking:
{
E Bo,
markp (2))
(90)
otherwise.
(2) distance-based marking:
markp (x1, 22)
min d (21,2), =EB)o((2)
(91)
where d'A., is the shortest path distance on H.A.,
34

---

Published as a conference paper at ICLR 2025
SCL updates.
We two types of SCL updates, 1-SCL and 2-SCL, defined by
h (++1) = Cat 21,22
(1+ (1+t)) ((+1))
21.
Σ
MMP(()
(h.).,,
((m)
(t)
I (1++e))i00
+ h nn Bo (m)
of ('1))
(92)
for rj E No. 22 E An.and and
(((1)) Cate 21:22
+
E # A
MLP!2
(D))2)
h ((
h (o.2
(93)
for x1 E No, 22 E X2, respectivley.
SCL pooling. To HOMP block after an SCL block need to pool the information from multi-cellular cochains to standard cochains. This done via an SCL pooling block, defied by
(ho) [ MLP(2) (DD..)a.
MLP(()
Σ
(+) (horr)
E'E
(94)
(h,) ( ((bb.))xozz) = MLP
Σ
Readout.
All tasks considered in this paper require predicting a single value per input CC. There- fore, we employ a final readout layer of the form:
ham
MLP
aggo
(
(T)
x E xbB) aggi ((h x E 21
agg2
((h!T) a E x2B) agg: ((h a E 20 E 2i))
(95)
(h 2i a E No 22 E 12
agg
where T is the final layer and agg, are either mean aggregation, sum aggregation, or the zero func- tion.
Tensor diagrams. We use types of tensor diagrams: sequential and parallel, both illustrated in Figure [4 In sequential tensor diagram, a stack of HOMP blocks is followed by a stack of SCL updates and then another stack of HOMP blocks. The parallel tensor diagram uses concurrent stacks of HOMP and SCL layers. Both the types of blocks/layers and the number of blocks/layers within each stack are treated as hyperparameters in the model.
G.2 SYNTHETIC BENCHMARKS
Torus dataset. To construct the torus dataset first select three parameters: which specifies the number of nodes the smallest CC the dataset, M which specifies the number of nodes the largest CC, and n, which specifies the maximum number of connected components in any CC within the dataset. The dataset is then constructed by iterating over all possible choices for the number of nodes and connected components, generating all possible disjoint unions of 2-dimensional tori with the specified parameters. We then select all the pairs that have the same size (number of nodes). As mentioned in the main text, each such pair is indistinguishable by HOMP despite differing basic metric/topological properties: they either have distinct homology, or they differ in the diameters of some of the components. In our experiments, we use m 18 (the smallest size that admits indistinguishable pairs), M 40, and n 3, resulting in 223 pairs.
To evaluate the ability of both HOMP and SMCN to distinguish between each pair, we follow the training and evaluation protocol presented in Wang & Zhang (2024). For each pair, we generate 64 copies where the order of cells is randomly permuted. The model is then trained to minimize the cosine similarity between the outputs corresponding to the two CCs in each pair. We measure the number pairs where the output difference is statistically significant. Our results show that, while HOMP fails to distinguish any of the pairs, SMCN successfully differentiates all of them.
35

---

Published as a conference paper at ICLR 2025
We use SMCN model implementing sequential tensor diagram composed of two CIN blocks, followed by four 1-SCL updates, and concluding with two additional CIN blocks. In comparison, the HOMP model consists of a stack of four consecutive CIN blocks, designed to have a comparable number of learnable parameters. The readout layer of both models uses a zero function as the aggregation for all multi-cellular cochains and sum aggregation for all standard cochains. All models are trained for 20 epochs on each individual pair using a constant learning rate of 0.001. The embdding dimension used by all models is 128.
Lifted ZINC cross-diameter. We construct CC dataset by adding cycles of length S 18 as 2- cells to graphs taken from the ZINC-12K dataset (Sterling & Irwin 2013). We remove edge and node features, and predict the (0, 1, 2) cross diameter, computed by:
max min d (1,
(96)
='Eo. y/
where d'A., (2,, x') is the shortest path distance w.r.t the original graph. Training targets are nor- malized to have mean O and standard deviation 1. The model is trained using an MSE loss. At test time, we evaluate both the MSE of the normalized target as well as the accuracy in predicting the cross-diameter value, which has 18 possible outcomes. We compare three architectures: the first two are HOMP models which employ a stack of four CIN blocks, and a stack of four custom HOMP blocks respectively. The third is an SMCN model, which implements sequential tensor diagram constructed by a single stack of six 2-SCL blocks, followed by a non-learnable pooling procedure constrained to a budget of 500K learnable parameters. The readout layer of all three models is defined according to Equation (93 where aggı: ag83. agg, are taken be the zero function and aggg: aggz are taken be the mean function. Models are trained for 200 epochs using a constant learning rate of 0.0001. The hidden dimension used by all models 64.
as described in Equation 94 All models
Lifted ZINC second Betti number. For the second topological property prediction task we tested our model's ability to learn to predict the second order Betti numbers- the ranks of the second homology group. To this end we constructed our benchmark dataset the following way: We started with the ZUNC-FULL datasets (containing 250k: molecular graphs), lifting all graphs to CCs as in the cross-diameter task. We then computed the second Betti number for each of the lifted graphs and randomly selected 850 samples from each of the 6 most common values (which were 0, 1, 2, 3, 4 and 6), resulting in a balanced dataset of size 5,100. We used 60%, 20%, 20% random split for training, validation, and test sets. As before, we remove all node and edge features, and normalized training targets to have mean 0 and standard deviation The models are then trained using an MSE loss. At test time we evaluated both the MSE of the normalized target as well as the accuracy of predicting the seconnd Betti number. We use the same models reported in the last experiment with the same exact hyperparameters.
The results of both lifted ZINC experiments are presented in Tables 2 Following the experimental setting of (Rieck, 2023) in which TDL models are tasked with learning metric properties of graphs taken from the MOLHIV dataset (Hu et al. 2020), we report the model's accuracy in predicting the correct target value. We additionally provide the normalized MSE score of the model.
SMCN significantly outperforms both HOMP methods in learning both the cross-diametes and the second Betti numbers, achieving higher accuracy as well as significantly lower standard deviation indicating a more stable learning process. This is particularly evident in the custom HOMP model, which, although it surpasses the CIN model in performance, suffers from considerably larger standard deviation. Additionally, the SMCN model achieves strong results after a significantly lower number of epochs compared to both HOMP models, as illustrated in Figure 15
Moreover, the results of the three synthetic experiments further demonstrate SMCN's superior ca- pability in capturing the topological properties of CCs compared existing HOMP architectures. While our theoretical analysis established that SMCN can express topological information beyond the capabilities of any HOMP architecture, the synthetic experiments validate that SMCN models can effectively learn and leverage these properties in practice.
G.3 REAL- WORLD GRAPH BENCHMARKS
ZINC Dataset (Sterling& & Irwin 2015; Dwivedi et al. 2023). The ZINC- dataset comprises 12,000 molecular graphs, extracted from the ZINC database, which is collection of commercially
36

---

Published as a conference paper at ICLR 2025
CIN Blacs
CIN Block
ICCCL
r-SCL
Block
CIN Block
(a) Sequential
(b) Parallel
Figure 14: Experiments using types of SMCN tensor diagrams. Sequential diagrams 14(a) stacks CIN blocks and SCL updates; Parallel diagrams [4(b) performs SCL. updates and CIN blocks
in parallel.
available chemical compounds. These molecular graphs vary in size, ranging from 9 to 37 nodes each. In these graphs, nodes correspond to heavy atoms, encompassing 28 distinct atom types. Edges in the graphs represent chemical bonds, with three possible bond types. We perform regression on the constrained solubility (logP) of the molecules. The dataset is pre-partitioned into training, validation, and test sets, containing 10,000, 1,000, and 1,000 molecular graphs, respectively.
For this experiment, we use SMCN model implementing sequential tensor diagram. The archi- tecture consists of a single CIN block, followed by a stack of five 1-SCL layers, and concludes with an additional CIN block. Each CIN block has an embedding dimension of 85, while each SCL layer uses an embedding dimension of 70, resulting in a model with fewer than 500k parameters, as out- lined in Dwivedi et al. (2023). The readout layer is defined according to Equation 955, where aggz- aggregation. Since we observed
aggs, and agg4 zero functions, and aggo and agg, are following the approach of et al. that this model converges slowly, we trained it for 2000 epochs, 2023). The learning rate is initialized 0.001 and decays by factor of 0.5 every 300 epochs.
OGB Datasets (Hu et al., 2020). MOLHIV and MOLESOL molecular property prediction datasets, adapted by the Open Graph Benchmark (OGB) from MoleculeNet. These datasets employ unified featurization for nodes (atoms) and edges (bonds), encapsulating various chemophysical properties. The task in MOLHIV is to predict the capacity of compounds to inhibit HIV replication. The task in MOLESOL is regression water solubility (log solubility in mols per liter) for common organic small molecules.
For both datasets, we use an SMCN model that utilizes a parallel tensor diagram. For MOLHIV the architecture consists of two CIN blocks, and tow parallel 2-SCL blocks. CIN blocks have an embedding dimension of 64 and dropout between layers with probability of 0.2 while SCL layers have embedding dimension of 24 and dropout in between layers with probability of 0.5. The final SCL layer is followed by a non learnable pooling operation as per Equation 94 The readout layer defined according to Equation 95 where agg3. and agg. are functions, and aggn- agg, and agg, are a mean aggregation. The mdoel is trained for 100 epochs with a constant learning rate of 0.0001.
37

---

Published as a conference paper at ICLR 2025
2-nd Betti Number Accuracy
accuracy
0.8
0.6
0.4
0.2
epoch
0
50
100
150
Cross Diameter Accuracy
accuracy
0.8
0.2
epoch
0
50
100
150
Figure 15: The accuracy per epoch of both synthetic lift experiments. SMCN is depicted in green, Custom HOMP depicted in blue and CIN depicted in yellow.
38

---

Published as a conference paper at ICLR 2025
Table 3: Accuracy the MUTAG dataset.
Model
Accuracy
GIN Xu et al.
2018)
89.4 + 5.6%
CIN (Bodnar& et al.
2021a
92.7 = 6.1%
PPGN (Maron et al. 2019)
90.6 = 8.7%
DS-GNN (Bevilaqqua et a.. 2021
91.0 = 4.8%
DSS-GNN (Bevilacqua al.
2021
91.1 + 7.0%
SUN (Frasca et al. 2022)
92.7 + 5.8%
SMCN (ours)
92.5 = 6.2%
Table 4: Train time (seconds per epoch). Time measurements from training each of the models. Measures are averaged across 10 epochs, starting from epoch number 20.
SMCN
GNN-SSWL+
CIN
ZINC
7.39 + 0.17
9.65 + 0.19
5.35 0.33
MOLHIV 17.70 + 0.42
51.02 + 0.25
14.34 + 0.27
For MOLESOL the architecture consists of two custom HOMP blocks, and two parallel 1-SCL layers. HOMP blocks have embedding dimension of 16 while SCL. layers have embedding dimension of 228 where neither block uses dropout. The final SCL block is followed by a non learnable pooling operation per Equation 94 The readout layer is defined according to Equation 95 where agg2- aggs. and agg, are zero functions, and agg, and agg, are a mean aggregation. The model trained for 200 epochs with constant learning rate of 0.0001.
MUTAG. The MUTAG dataset, part of the TUDataset benchmarks (Morris al.) 2020), comprises 188 molecular graphs. The task is to identify mutagenic molecular compounds, which are relevant for the development of potentially marketable drugs (Kazius al., 2005 Riesen Bunke 2008). Our training setup and evaluation procedure adhere to those outlined in Xu et al. (2018). For this experiment, the SMCN model utilizes a sequential tensor diagram constructed with a single stack of six 2-SCL blocks, followed by non-learnable pooling procedure, as detailed in Equation 94 Results are presented in Table
G.4 RUNTIME EVALUATIONS
To empirically measure the runtime differences between SMCN, subgraph GNNs and HOMP, ran several wall clock measurements for data set construction, single epoch training and test set evaluation. We evaluate the SMCN variants used for the ZINC and MOLHIV experiments, GNN- SSWL+ which is the backbone subgraph GNN for SMCN, and CIN, a standard HOMP model. Runtime was evaluated across 10 runs, all experiments ran on a single NVIDIA A100 48GB GPU. Dataset construction times (in seconds) are:
ZINC: 322.21 + 8.764,
MOLHIV: 678.01 + 11.38.
We used the same lifting procedures and dataset construction for both SMCN and CIN so construc- tion times are identical. Results for the train/test times appear in Tables 4 and respectively Jedeessivveyss SMCN incurs a computational overhead of approximately 23% on the MOLHIV benchmark and 38% on ZINC benchmark compared CIN (trade-off for its improved predictive performance). Additionally SMCN consistently surpasses subgraph networks in runtime, achieving 2.9x speedup on MOLIIIV
Table 5: Test time (seconds per full test set inference). Time measurements for inference over the entire test set. Results are averaged over 10 runs.
SMCN
GNN-SSWL+
CIN
ZINC
0.93 - 0.08
1.04 + 0.03
0.71 = 0.05
MOLHIV 2.09 + 0.15
3.07 + 0.03
2.02 = 0.12
39

---

Published as a conference paper at ICLR 2025
and 1.3x speedup ZINC. This improvement over subgraph networks stems from the fact SMCN uses fewer subgraphs updates and leverages higher order topological information instead.
40


Reviews:
[{"review_id": "hiVU1vp1eY", "reviewer": "Reviewer_TNgH", "summary": "This work studies the expressivity of Topological Deep Learning (TDL) architectures, particularly focusing on the limitations of Higher-Order Message Passing (HOMP) for distinguishing combinatorial complexes. The first half of the paper extends Bamberger’s (2022) work on the expressivity limitations of message-passing Graph Neural Networks (GNNs), which characterized, using covering maps, graphs that GNNs cannot distinguish. In a similar vein, this paper reveals \"topological blindspots\" in HOMP frameworks: (1) complexes that share a cover are indistinguishable by HOMP, and (2) HOMP cannot distinguish complexes that differ in important topological and metric properties such as diameter, orientability, planarity, and homology. In the second half, the authors address these limitations by adapting techniques from expressive graph architectures that process features over tuples of nodes. Similarly, the work extends HOMP with multi-cellular feature spaces and equivariant linear updates. This extension, Multi-Cellular Networks (MCN), achieves full expressive power, allowing it to (1) distinguish non-isomorphic complexes and (2) differentiate complexes based on properties like diameter, 0-th homology group, and also distinguish between a Moebius strip and a cylinder (which disagree on planarity). The work also introduces a more computationally scalable version of MCN, aptly called SMCN.  Lastly, the authors empirically validate MCN and SMCN on benchmarks designed to capture topological expressivity, demonstrating the superiority of these architectures over standard HOMP and expressive GNN models.", "questions": "1. The authors demonstrate that HOMP can be extended to achieve full or greater expressivity with components that may make the proposed models computationally impractical for large combinatorial complexes. Is this an inherent limitation that comes with achieving full/greater expressivity, or did the authors only intend to demonstrate that such levels of expressivity are achievable and the proposed extensions sufficed for that purpose?\n2. Could the authors give recommendations or guidelines for which additional multicellular nodes and connections to include in the MCN and SMCN models? For example, how should a practitioner choose and connect multicellular nodes in the MCN and SMCN layers as in the example in Figure 5?\n3. Could the authors expand their real-world benchmarks with some more tasks/datasets? For example, the TUDatasets or trajectory classification tasks from Bodnar et al. (2021).\n4. Are the group actions in Section 5 required to be compatible with the underlying complex? For example, are permutations that exchange nodes while fixing higher-dimensional (rank) simplices allowed?\n5. Could the authors make their code publicly available?\n6. Could the authors provide a brief account of Bamberger (2020) in the main text to help contextualize how earlier methods relate to and may have motivated the approaches developed in the first half of this work?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(++++) **Novelty and Relevance**: This work is new and addresses questions of significant importance and urgency for the Topological Deep Learning (TDL) community.\n\n(++++) **Theoretical Contribution**: The theoretical contribution is strong, rigorous, and sound. The answers provided to the question considered by the work are satisfying.\n\n(++) **Empirical Validation**: The authors validate their models with real-world and synthetic benchmarks designed to capture topological expressivity, demonstrating clear improvements over standard HOMP and expressive GNN models.\n\n(++) **New Benchmarks**: The work introduces benchmarks that test models on topological invariants to assess TDL expressivity, which will serve as a valuable tool for the TDL community.", "weaknesses": "(---) **Presentation**: The architecture descriptions may be opaque for readers unfamiliar with TDL. Section 5 gives examples of CC data that the new multicellular nodes can encode, but it is unclear which nodes and connections should be included and when. For example, the choice of multicellular nodes and connections such as in the example tensor diagrams in Figure 5 would benefit from additional explanation.\n\n(---) **Limited Empirical Evaluation**: The proposed architectures are benchmarked on only three-world datasets.\n\n(--) **Related Work**: Although Section 4 extends Bamberger’s (2020) result, this work is only mentioned once in Section 4.1. An earlier mention in Section 2 (Previous Work) would help readers place this work within a broader research context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0HnmHWlxsE", "reviewer": "Reviewer_sF9V", "summary": "The paper presents a new way to define expressivity but from a topological perspective. The paper shows that existing Topological Deep Learning (TDL) models have trouble estimating certain important topological properties such as diameter, orientability, planarity, and homology. The authors then propose a new model called MCN and its scalable version SMCN that can capture the topological properties better. The paper also presents new benchmarks focusing on learning topological properties of complexes.", "questions": "1. For Figure 5, can you elaborate more on colored nodes of SMCN and MCN? I think this part can be improved to make it clearer for the audience.\n2. For Figure 7, the superscript for \\mathcal{X} and \\mathcal{H} isn’t discussed in the main text, so it is confusing.\n3. Can the authors comment on the lifting and runtime complexities with respect to CIN? I think the paper only mentions the runtime complexity and neglects the discussion. It is also helpful to include an experiment on wall-clock training/inference time to see the model scalability in practice when comparing with other TDL models.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The paper presents a novel essential perspective that differentiates TDL and deep learning on graphs, which used to be compared under the same umbrella previously (in terms of graph expressivity and benchmarks). This work partly bridges the gap between TDL and traditional computational topology methods, which largely focus on homology. The paper also presents theoretical insights showing that higher-order message passing is incapable of capturing certain topological metrics. The experiments also support these insights. The experiments also constrain on parameter budgets to show the effectiveness of the method with respect to the baseline. The paper acknowledges the weakness of MCN if we consider higher-order spaces, so the authors present a scalable version that leverages subgraph GNNs to encode higher-order features. The novel benchmarks are a great contribution which can facilitate a better comparison standard for TDL methods.", "weaknesses": "The paper is hard to follow and the presentation is not good. For example, the authors can be more explicit on lines 309 and 310 and discuss (1), (2), and (3) more instead of stating them. The notations involve many upper scripts and lower scripts while not explaining their purposes clearly make the formula confusing (line 319 and 320). The paper isn’t self-contained; for example, the paper can discuss more about IGN as the model itself leverages an architecture similar to IGN. The same thing applies to Subgraph GNNs. Please also refer to the question section for further comments on clarity. Also, even when the paper focuses on expressivity from a topological perspective, I think it would be helpful to include a brief section discussing the proposed method with respect to graph expressivity so that there is a smoother transition between deep learning on graphs and TDL. Lastly, please refer to question 3 for experiments on runtime and lifting time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IyqdmnTZJ9", "reviewer": "Reviewer_8Wou", "summary": "The paper presents an in-depth exploration of Topological Deep Learning (TDL) architectures through the lens of Higher-Order Message Passing (HOMP). The authors investigate HOMP's expressivity limitations in capturing topological invariants (e.g., orientability, planarity, diameter, and homology) in combinatorial complexes and propose two novel architectures: Multi-Cellular Networks (MCN) and Scalable Multi-Cellular Networks (SMCN). These architectures aim to enhance HOMP’s expressivity in distinguishing between topological structures. Empirical evaluations using newly designed benchmarks and real-world graph datasets demonstrate that SMCN outperforms existing models, highlighting the potential of using expressive topological information in TDL.", "questions": "1.\tTo enhance readability and comprehension, the main paper should be more self-contained by clearly explaining topological invariants—such as diameter, orientability, planarity, and homology. For clarity, consider presenting formulas or examples within the main text (e.g., rather than relying solely on descriptions on line 233).\n\n2.\tIn the introduction of the concept of CC covering, an illustrative case could help readers grasp this concept more intuitively.\n\n3.\tCould the authors discuss the proposed method in relation to relevant research? For instance, [1] proposed a cycle-invariant positional encoding where cell/cycle features are initially encoded using an invariant network and subsequently incorporated into a standard GNN as additional edge features. A comparison would contextualize SMCN’s contributions within the broader landscape of topological GNN methods.\n\n[1] Yan Z, Ma T, Gao L, et al. Cycle invariant positional encoding for graph representation learning. LoG 2024.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe authors provide a rigorous examination of HOMP’s expressivity limitations concerning fundamental topological and metric invariants, establishing the groundwork for understanding the weaknesses in current TDL approaches.\n\n2.\tThe introduction of MCN and SMCN provides new pathways for achieving higher expressivity. The authors demonstrate that MCN can theoretically achieve full expressivity, while SMCN offers a computationally feasible alternative, balancing expressivity with scalability.\n\n3.\tSMCN demonstrates substantial improvements over traditional HOMP and GNNs, validating the model's efficacy in capturing and leveraging topological features in learning tasks.", "weaknesses": "1.\tWhile SMCN offers a scalable alternative to MCN, it still encounters significant challenges in managing large and complex combinatorial complexes due to its super-linear scaling with respect to the number of cells. It would be beneficial for the authors to provide a comparative analysis of SMCN’s runtime performance against existing HOMP methods and other GNNs, such as CIN (Bodnar et al., 2021) and the backbone subgraph GNN used in SMCN.\n\n2.\tThe paper would benefit from a more detailed rationale for why topological invariants—such as diameter, orientability, planarity, and homology—are critical for machine learning models to differentiate. Specifically, it would be helpful to address the importance of these invariants in machine learning tasks, either through empirical evidence, theoretical reasoning, or relevant literature.\n\n3.\tThere appears to be a discrepancy between SMCN’s theoretical expressivity and its empirical accuracy. For instance, it is unclear why SMCN does not achieve full accuracy in predicting cross-diameter and the second Betti number, which warrants further investigation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)