Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity

We thank the reviewer for the positive review and constructive feedback. We address the concerns and questions raised by the reviewer below:

• Role of topology in ML (W2): The reviewer raises an important question that is central to the wider ongoing research in TDL: "What is the significance of topological information to machine learning tasks?" This is indeed an open problem in TDL, highlighted as Open Problem 9 in a recent position paper [5]. In response to this question, numerous TDL approaches attempt to incorporate topological information, either by lifting objects such as graphs into topological spaces (e.g., HOMP models) or to inject specific topological features directly into the learning pipeline [2, 6, 10, 11, 12]. The papers that develop these approaches often show they have desirable theoretical properties, or empirically demonstrate improved performance, suggesting that incorporating topology can meaningfully enhance model capabilities. Section 2 of the paper reviews several methods, which use topological and metric invariants closely related to our discussion. For example, persistent homology [2,6] relies on homology, while architectures such as [7] use metric features closely related to the graph diameter. Additionally, properties like planarity are of interest, as many real-world graphs, such as those representing molecular structures and electrical circuits, are planar. Collectively, these approaches demonstrate both theoretical and practical advantages, often enhancing the expressive power and performance of base models like MPNNs, which do not inherently incorporate topological information.

  In this context, our paper makes two key contributions to the TDL literature. First, we show that despite being the de facto standard TDL architecture, HOMP is unable to capture fundamental topological properties—often the same properties that other methods explicitly integrate into models (e.g. homology in [2,6] and diameter in [7]). This limitation highlights the need to design more expressive TDL architectures to fully investigate topology's contribution to learning processes. To that end, we introduce the SMCN framework, which enables models to access a broader range of topological properties. We demonstrate that this framework improves performance on standard graph benchmarks. These findings advance our understanding of the role of topology in machine learning, suggesting a correlation between a model's ability to capture topological information and its empirical performance over real world benchmarks.

• Runtime concerns (W1): In the revised version (to be uploaded within the discussion period), we will provide a wall-clock training/inference comparison of all of SMCN, CIN and subgraph GNNs as well as a more emphasized runtime complexity analysis. See the next comment for timing analysis. Additionally, we note that:

  • Generally, as is common in GNNs, methods that enhance expressivity often come with increased runtime complexity [1,3,4]. Our approach provides another datapoint on this spectrum.
  • SMCN is a general framework and runtimes can change for different specifications, e.g. for ZINC we use a version of SMCN with runtime complexity of $O(d \cdot n_0 \cdot n_1)$ and for MOLHIV+MOLESOL+synthetic experiments we use a version with runtime complexity of $O(d \cdot n_0 \cdot n_2)$.
  • As mentioned in proposition 6.6, SMCN architectures with runtime complexity $O(d \cdot n_0 \cdot n_2)$ are still more expressive than HOMP approaches like CIN, but have a better runtime complexity then subgraph methods, since in most relevant, real-world settings $n_2 \ll n_0$ (e.g. number of cycles is smaller then number of nodes).

• Comparison to Yan et. al (Q3): We thank the reviewer for introducing us to this relevant paper. We will make sure to add a comparison of our approach to this paper in the next version. In terms of experimental results, CycleNet got a score of 0.068 on ZINC while our model got a score of 0.060. In terms of expressive power we provide a proof sketch showing that SMCN is more expressive than CycleNet:

  • First, recall that CycleNet leverages BasisNet + spectral embedding [8] applied to the 1-Hodge Laplacian of the input graph. The resulting output is then used as edge features, which are subsequently processed by a final MPNN applied to the graph. In cases where the input graphs are simple and undirected, the 1-Hodge laplacian is exactly equal to the 1-0 coadjacency matrix (plus a diagonal term of $2\mathbf{I}$ which can be ignored). SMCN can apply subgraph GNNs to the $co\mathcal{A}_{1,0}$ Hasse graph, and use the resulting features as inputs for an MPNN. This reduces our proof to demonstrating that subgraph GNNs are more expressive than BasisNet. As recently shown in [9], 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 completes the proof.

We greatly appreciate the reviewer’s positive feedback and constructive criticism. We address the concerns and questions raised by the reviewer below:

• Clarity: We thank the reviewer for their insightful suggestions! We’ll integrate these notes in the revised version of the paper (to be uploaded within the discussion period). Specifically, we’ll make an effort to add further discussion and illustrations to elaborate on neighborhood functions (equations (1), (2) and (3)), multicellular cochains (lines 309 and 310) and group action indices (lines 319 and 320). We note that due to length restrictions, some of these might be added to the Appendix.

• IGN and subgraph GNNs overview: We’ll additionally add a deeper overview of IGNs and subgraph GNNs in the Appendix.

• Graph expressivity: We note that the SMCN and MCN frameworks introduced in the paper are both direct generalizations of the HOMP framework, including CIN [2]. As demonstrated in [2], CIN is strictly more expressive than MPNNs, and this property extends to both SMCN and MCN. Furthermore, the SMCN framework subsumes subgraph-based architectures like ESAN and GNN-SSWL+ [1,6], making it at least as expressive as these methods. The expressive power of these architectures has been thoroughly studied [3,6], providing additional context for understanding the expressivity of SMCN relative to other graph-based approaches. This discussion will be added to the Appendix.

• Figure 5 tensor diagram node clarification (Q1): These nodes represent types of multicellular cochain spaces, we will elaborate on them in the updated version.

• Figure 7 notation clarification: Thank you for this comment! The superscript indicates cell/node marking in the complex/graph (e.g., a subgraph layer can process a bag of graphs with marked nodes) will add a clarification in the updated version.

• Runtime analysis: In the revised version, we will include a wall-clock training and inference time comparison between SMCN, CIN, and subgraph GNNs. For your convenience, we also provide this comparison below:

  • Dataset construction times (seconds):

    • ZINC: 322.21 ± 8.764
    • MOLHIV: 678.01 ± 11.38

  • Train time (seconds) / performance:

    Dataset	SMCN	GNN-SSWL+	CIN
    ZINC	7.39 ± 0.17 / 0.060 ± 0.004	9.65 ± 0.19 / 0.070 ± 0.005	5.35 ± 0.33 / 0.079 ± 0.006
    MOLHIV	17.70 ± 0.42 / 81.16 ± 0.90	51.02 ± 0.25 / 79.58 ± 0.35	14.34 ± 0.27 / 80.94 ± 0.57

  • Test time (seconds) / performance:

    Dataset	SMCN	GNN-SSWL+	CIN
    ZINC	0.93 ± 0.08 / 0.060 ± 0.004	1.04 ± 0.03 / 0.070 ± 0.005	0.71 ± 0.05 / 0.079 ± 0.006
    MOLHIV	2.09 ± 0.15 / 81.16 ± 0.90	3.07 ± 0.03 / 79.58 ± 0.35	2.02 ± 0.12 / 80.94 ± 0.57

  All experiments were done on an NVIDIA A100 48 GB GPU. We used the same lifting procedures and dataset construction for both SMCN and CIN so construction time is the identical. 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. The improvement over subgraph networks stems from the fact SMCN uses fewer subgraph updates and leverages higher order topological information instead.

References:

[1] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2110.02910, 2021.

[2] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in neural information processing systems, 34:2625–2640, 2021.

[3] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and HaggainMaron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376–31390, 2022.

[4] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.

[5] 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, volume 33, pages 4602–4609, 2019.

[6] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. International Conference on Machine Learning, pages 41019–41077. PMLR, 2023.

Timing analysis:

• Dataset construction times (seconds):

  • ZINC: 322.21 ± 8.764
  • MOLHIV: 678.01 ± 11.38

• Train time (seconds) / performance: | Dataset | SMCN | GNN-SSWL+ | CIN | |--------------|------------------|------------------|------------------| | ZINC  | 7.39 ± 0.17 / 0.060 ± 0.004 | 9.65 ± 0.19 / 0.070 ± 0.005 | 5.35 ± 0.33 / 0.079 ± 0.006 | | MOLHIV | 17.70 ± 0.42 / 81.16 ± 0.90 | 51.02 ± 0.25 / 79.58 ± 0.35 | 14.34 ± 0.27 / 80.94 ± 0.57 |

• Test time (seconds) / performance: | Dataset | SMCN | GNN-SSWL+ | CIN | |--------------|------------------|------------------|------------------| | ZINC  | 0.93 ± 0.08 / 0.060 ± 0.004 | 1.04 ± 0.03 / 0.070 ± 0.005 | 0.71 ± 0.05 / 0.079 ± 0.006 | | MOLHIV | 2.09 ± 0.15 / 81.16 ± 0.90 | 3.07 ± 0.03 / 79.58 ± 0.35 | 2.02 ± 0.12 / 80.94 ± 0.57 |

All experiments were done on an NVIDIA A100 48 GB GPU. We used the same lifting procedures and dataset construction for both SMCN and CIN so construction time is identical. 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. The improvement over subgraph networks stems from the fact SMCN uses significantly fewer subgraphs updates and leverages higher order topological information instead.

References:

[1] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2110.02910, 2021.

[2] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.

[3] 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, volume 33, pages 4602–4609, 2019.

[4] Zhang, Bohang, et al. "Rethinking the Expressive Power of GNNs via Graph Biconnectivity." The Eleventh International Conference on Learning Representations.

[5]  Omri Puny, Derek Lim, Bobak Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks. In International Conference on Machine Learning, pages 28191–28222. PMLR, 2023.

[6] 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.

We thank the reviewer for highlighting the strengths of our paper, particularly its novelty and relevance to the TDL community. We also appreciate the reviewer’s constructive feedback and address their comments below:

• Limited Empirical Evaluation (W2 + Q3): While our work has a strong theoretical focus, we also place significant emphasis on experimental validation. Not only have we introduced several novel benchmarks that address a gap in the field (the torus dataset and topological property prediction tasks), but our paper also includes more extensive experimental evaluation compared to typical theory-focused papers. For instance, [4] (Outstanding Paper Award at ICLR 2023) evaluates only on a single real-world dataset (ZINC) alongside synthetic experiments, [5] (Oral Presentation at ICML2023) explores three real-world benchmarks (matching ours) with one synthetic experiment, and [6] (200+ citations) presents no real-world benchmarks at all.

  Nevertheless, in response to this feedback, we will make an effort to expand our real-world evaluation in the revised version by adding experiments on several datasets from the TUDatasets repository. Finally, we note that we cannot include the trajectory classification tasks from Bodnar et al. (2021) as these rely on cells with orientation, which is out of the scope of our architecture.

• Presentation (W1 + Q2): Due to the paper's page limit, we only provided an overview of the architectures in the main text, providing a more in-depth description in the Appendix. Specifically, in Appendix B and C, we provide a more thorough description of the general MCN and SMCN frameworks respectively. In addition, as the SMCN framework offers a versatile space of layers and updates, in Appendix F.1 we focus on two potential types of SMCN implementations and thoroughly describe their exact forward pass. Despite this, we agree the main text explanations could be clearer. In the revised version (to be uploaded within the discussion period), we will:

  • Add details to section 5 to explain what nodes to use and when for each of the examples.
  • Expand the description of Figure 5 to better illustrate the relationship between node types and update rules
  • Add specific guidelines for practitioners on selecting appropriate multicellular structures.

  Overall, we observe that SCL layers updating edge features, combined with "sequential tensor diagrams", tend to increase the risk of overfitting but perform well on tasks like ZINC, where the training and test distributions are closely aligned. In contrast, SCL layers that update 2-cells, paired with "parallel tensor diagrams", are more effective for tasks sensitive to overfitting. All relevant definitions, including those of "sequential" and "parallel" tensor diagram are provided in Appendix F1.

• Related Work (W3 + Q6): We agree that the connection to Bamberger (2020) should be better contextualized. We will:

  • Add a dedicated mention in Section 2 explaining Bamberger's work on covering maps.
  • Clarify how our topological criterion extends their results.

• Computational practicality (Q1): The trade-off between expressivity and computational complexity is well-documented in machine learning, particularly in graph learning (e.g. [1,2,3]). Our work provides another data point in this trade-off. Moreover, our framework is flexible – specific instantiations can make different complexity trade-offs. For example, we can design models whose complexity primarily depends on the number of 2-cells, which are typically much fewer than nodes or edges. This enables practitioners and other researchers to find the optimal expressivity/computation trade-off for their application. We will clarify these points in the revised manuscript. Additionally, as discussed in the general comment, the runtime of our architecture is comparable to that of CIN (a standard HOMP architecture) and is better than that of subgraph GNNs, see next comment for timing analysis.

• Group actions compatibility (Q4): Thank you for this important question! No, the group actions do not need to be compatible with the underlying complex structure. The group acts on the enumeration of the cells, not on the complex itself. For example, a cell permutation can reorder the cells c₁ = {s₁, s₂}, c₂ = {s₃, s₄} to c₁ = {s₃, s₄}, c₂ = {s₁, s₂}, effectively shuffling the cell labels while preserving the internal structure of each cell. We will clarify this point in the revised text.

• Code availability (Q5): Yes, we will make our code publicly available as soon as possible. We are currently in the process of cleaning and organizing it to ensure it is user-friendly for public release. We aim to publish the code within the discussion period, and commit to making it available before submission of the camera-ready version.