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
Primary area: learning on graphs and other geometries & topologies
Keywords: topological deep learning, message passing, higher order message passing, expressivity, graph neural networks, gnns, topology, homology, symmetry

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.

Decision: accept (oral)
Reviewer scores: 8, 8, 8

Reviews and discussion:
<thread>
creation date:
1730582985338

thread_type:
official_review

<thread_object>
creator: reviewer_8wou

<content>
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.

strengths:
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.

weaknesses:
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.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730599358367

thread_type:
official_review

<thread_object>
creator: reviewer_sf9v

<content>
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.

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.

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.
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730667270075

thread_type:
official_review

<thread_object>
creator: reviewer_tngh

<content>
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.

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

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.

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

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?
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731863843342

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank all the reviewers for their positive evaluations and constructive feedback. We underscore four key contributions of our paper mentioned by the reviewers:

1. Our paper addresses a fundamental and unexplored question in TDL (**TNgH**, **sF9V**).
2. Our theory section answers this question, exposing a fundamental limitation of a large class of TDL architectures (**TNgH**, **sF9V**, **8Wou**). 
3. We construct provably expressive architectures and empirically demonstrate their improved performance (**TNgH**, **8Wou**).
4. We construct valuable datasets and benchmarks (**TNgH**, **sF9V**).

Additionally, in response to reviewers' inquiries regarding computational practicality, we conducted a runtime comparison between SMCN, CIN and the backbone subgraph GNNs. SMCN incurs computational overhead of approximately 23% on the MOLHIV benchmark and 38% on ZINC compared to CIN (trade-off for its improved predictive performance). Additionally SMCN consistently outperforms subgraph networks in runtime, achieving a ~2.9x speedup on MOLHIV and a ~1.3x speedup on ZINC.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732463611384

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Updated Manuscript and Code

comment:
Dear reviewers, we express our sincere appreciation for the positive evaluations. We have updated the manuscript incorporating your suggestions, with all changes highlighted in light blue for easy reference. We additionally provide code for three of our experiments in the supplementary material, the entire repo would be added to the camera ready version.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper provides a thorough examination of the expressivity limitations of Higher-Order Message Passing (HOMP) architectures in Topological Deep Learning. It identifies specific "topological blindspots" in HOMP, such as its inability to distinguish between complexes differing in topological and metric properties like diameter, orientability, planarity, and homology. To address these limitations, the authors propose two new architectures: Multi-Cellular Networks (MCN) and Scalable Multi-Cellular Networks (SMCN). MCN achieves full expressive power, allowing it to distinguish non-isomorphic complexes and differentiate key topological features. SMCN offers a computationally scalable variant of MCN, maintaining strong expressivity while reducing complexity. The authors also introduce benchmarks designed to evaluate topological expressivity, demonstrating empirical improvements of the proposed methods over baseline HOMP and GNN models on these benchmarks and real-world graphs. Overall, this work conducts a strong generalization of the existing extensive studies on GNN expressive power to TDL. 

**Strengths**  The research is strong across many aspects including theoretical analysis, algorithmic design, and extensive evaluation. In particular, the systematic extension of the notion of GNN expressive power to TDL is impressive and useful. 

**Weaknesses** The main concern is about presentation and clarity. The paper is difficult to follow, particularly for readers unfamiliar with TDL. Complex notations and insufficient explanation of architectural components (e.g., Figure 5 and the superscripts in Figure 7) reduce accessibility. Moreover, in practice, the complexity of the proposed methods, compared with other more efficient models with even better empirical performance should be better justified. 

Overall, I think this work is a solid theoretical contribution to the field of graph and geometric deep learning, though empirical value deserves further justification and more intuitive exposition is also recommended.