Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity
Topological Deep Learning;Message Passing;Higher Order Message Passing;Expressivity;Graph Neural Networks;GNNs;Topology;Homology;Symmetry
Yes
No ethics review needed.
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?
2. 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?
3. 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).
4. 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?
5. Could the authors make their code publicly available?
6. 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?
(++++) **Novelty and Relevance**: This work is new and addresses questions of significant importance and urgency for the Topological Deep Learning (TDL) community.

(++++) **Theoretical Contribution**: The theoretical contribution is strong, rigorous, and sound. The answers provided to the question considered by the work are satisfying.

(++) **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.

(++) **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.
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.
(---) **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.

(---) **Limited Empirical Evaluation**: The proposed architectures are benchmarked on only three-world datasets.

(--) **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.
Yes
No ethics review needed.
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.
2. For Figure 7, the superscript for \mathcal{X} and \mathcal{H} isn’t discussed in the main text, so it is confusing.
3. 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.
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.
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.
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.
Yes
No ethics review needed.
1.	To 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).

2.	In the introduction of the concept of CC covering, an illustrative case could help readers grasp this concept more intuitively.

3.	Could 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.

[1] Yan Z, Ma T, Gao L, et al. Cycle invariant positional encoding for graph representation learning. LoG 2024.
1.	The 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.

2.	The 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.

3.	SMCN demonstrates substantial improvements over traditional HOMP and GNNs, validating the model's efficacy in capturing and leveraging topological features in learning tasks.
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.
1.	While 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.

2.	The 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.

3.	There 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.
@inproceedings{
anonymous2024topological,
title={Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=EzjsoomYEb},
note={under review}
}
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.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Topological Deep Learning Message Passing Higher Order Message Passing Expressivity Graph Neural Networks GNNs Topology Homology Symmetry
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/beb659ff34c9b9302c5f225d547046ab9d2f22f9.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission