- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper tackles the problem of applying Topological Deep Learning (TDL) architectures to large graphs, for which lifting procedures can exacerbate computational difficulties by inducing the need to materialise a combinatorially large number of additional higher-order structures.
The authors advocate for an approach whereby lifting is applied only after graph minibatching, posterior to merging graph clusters in output from a graph partitioning procedure. This allows to only materialise the higher order structures for each minibatch allowing applications to graphs which, after lifting, would induce a too large higher-order domain that would potentially be hard to fit in memory and deal with. At the same time, by lifting only after clusters are merged, this approach allows to retain higher-order structures supported across partitions.
The authors experiment with various graph datasets and TDL architectures, exploring aspects such as variations in runtime, memory footprint and performance. They then run ablation studies on the impact of design choices, including inference and partitioning scheme.
Critical strengths
- (S1) The paper motivation is relatively clear and the authors present it in an understandable way.
- (S2) The authors work on an extensive set of datasets and architectures, proposing a valuable stratification of the former ones.
Critical weaknesses
-
(W1) Critically, the reviewer finds the methodological contribution rather thin: essentially, the proposed method is a simple application of ClusterGCN (Chiang et al, 2019) whereby minibatches are lifted to capture the contained higher-order structures by downstream topological deep learning architectures. Importantly, the authors are not very explicit abut this. In fact, partitioning and stochastically combining partitions at training time is not their contribution, rather ClusterGCN's. While they do cite and actually mention the contributions by ClusterGCN in the related works, they are not upfront enough on the fact that, e.g., only card (4) in Figure 1 (a) is their contribution, the rest is ClusterGCN. As another example, the method presented in section 3.1 is essentially ClusterGCN except for the minibatch-wise lifting procedure.
-
(W2) Results presented in Section 3.3 (Theoretical Guarantees) are mostly reasonably trivial. With due respect, the reviewer deems it rather trivial that "A structure can be recovered only if its supporting cluster fit within one minibatch", and that, in the limit, if one runs enough epochs the probability to observe every observable structure approaches one. It is basically obvious that increasing q also increases the number of observable structures and their recovery probability. The authors report various statistics for different values of q, but it is not clear what is the take home message. These results depend on many other factors, including the clustering approach and the size of the partitions. Generally speaking, this section whole section does not provide any interesting insight. ... More interesting results could investigate, instead, the inter-relation between the partitioning procedure and the lifting function or non-random cluster merging approaches that leverage the graph structure to improve the coverage probability. There is not much in the paper and these results in particular that is really specific to higher-order topological domains beyond graphs.
-
(W3) The experimental section is not well structured and clear. The authors propose a series of questions, but then proceed to discuss results in a way that is sometimes confusing.
- Often, seemingly relevant tables and figures are relegated to appendix with much clarity on this choice.
- Separating the computational gains from performance in different sections (4.2, 4.3) does not really help: computational gains are only relevant for reasonably interesting performance (and "viceversa"). Figure 3 puts the two together, but it is quite hard to parse.
- It is not clear what corresponds to GCN + Cluster-TNN in Table 1: is it just ClusterGCN?
- There is essentially no mention and discussion on the utilised lifting procedures by the various considered approaches. It is understandable that the method is to be shown agnostic to the lifting procedure, yet there is not even one mention to the various lifting procedures, and whether they can explain differences in the performance. This is a work on Topological Deep Learning, after all, the reviewer deems it striking that the authors do not discuss these components at all.
-
(W4) The presented results are either somewhat expected, rather underwhelming, or not discussed much in their nuances
- Section 4.2: Isn't it expected that the method allows for lower GPU footprint? It would be more interesting to compare them to other approaches for scalable training?
- Except for OGBN-Products, it does not seem that higher-order methods are significantly better than the basic GCN approach, see, e.g. Coauthor Physics and Reddit. What is the point then?
- The method seems not to be compared to other approaches for scalable TDL.
- There is a lot of variability on results across various TDL methods, why is that and how can we interpret these, and in relation to the proposed contributions? This is not clear or discussed much in the main paper.
Questions for authors
Does the GCN baselines use a comparable inference ensembling scheme ensuring, e.g., comparable results in Table 1?
3 comments
W3. Discussion of Lifting Procedures
We thank the reviewer for the comments. GCN + Cluster-TNN in Table 1 is GCN run through the same workflow with the identity lifting, that is Cluster-GCN mini-batching combined with our ensemble inference.
We acknowledge that the paper does not analyse whether the choice of lifting explains the differences in performance between models. Our focus is feasibility, and the pipeline is agnostic to the lifting and applies to any lifting that can be evaluated on an induced subgraph (Section 3.1). We therefore use TopoBench's default lifting for each domain (Appendix A.2.1 and B.2.1): closed one-hop neighbourhood hypergraphs (EDHNN, UniGNN), a cycle basis with cycles of length at most nine (CWN, TopoTune), and a clique complex up to dimension two (SCN, SCCNN). Comparing liftings within a domain at this scale is what the pipeline now makes possible, and we see it as a natural extension.
W4. Performance Expectations, Nuances, and Comparisons with Scalable Baselines
The lower GPU footprint is expected in direction, and our measurements quantify it (83.2% mean reduction over 21 comparisons) and show that the binding limit can often be CPU-side construction. For example, for TopoTune on Reddit, mean peak CPU memory is 480.1 GB during full-graph preprocessing, compared with a mean run-wide peak of 11.81 GB under Cluster-TNN (Section 4.2). For other scalable TDL approaches, please see our reply to Reviewer Rzz4 (W2.A): FastHGNN and SaNN operate on an already constructed domain, so a matched comparison is only possible where the full domain fits.
On the comparison with GCN, higher-order models do not uniformly outperform GCN. Our claim is that these comparisons can now be made at this scale, not that TNNs always win, as we emphasise in the revised manuscript. On OGBN Products, however, EDHNN, SCN and SCCNN outperform GCN (86.51%, 87.03% and 88.63% vs. 85.81%), and on the three controlled datasets the best model is a TNN under both settings (Table 1). These differences motivate comparing higher-order representations across datasets, a task enabled at scale by the common Cluster-TNN workflow.
The variability comes largely from the models rather than from the batching. It is already present under full-graph training with the same liftings: on Cora Full, full-graph accuracy ranges from 46.40% (TopoTune) to 70.81% (SCCNN), compared with 56.45–70.32% under Cluster-TNN (Table 1). Models that share a domain also differ in architecture, for example in the neighbourhood operators they use on the same complex (Table 5: CWN uses the rank-1 upper adjacency, TopoTune also a two-hop rank-0 upper adjacency), and they differ in how much they rely on cross-cluster structure: on Cora Full, removing cross-cluster edges costs TopoTune 10.01 pp but CWN only 0.66 pp, although both use the same cycle-basis lifting (Table 2).
Q1. Clarifying Inference Ensembling in GCN Baselines
Yes, all Cluster-TNN results in Table 1, including the GCN baseline, use the same inference protocol, and all full-graph results, including GCN, use full-graph inference, as the Table 1 caption states. GCN is therefore evaluated under the same conditions as the higher-order models in both settings.
The ensemble benefit is also not specific to TNNs. Table 2 reports the gain of ensemble over single-pass mini-batch inference for every model, and for GCN it is +2.51 pp on Cora Full, +0.05 pp on Amazon Ratings, and +0.65 pp on Questions. More generally, ensemble inference "yields higher mean than a single-pass in all 21 comparisons" (Section 4.4), with gains from 0.04 to 4.65 pp (Table 2), and these 21 comparisons include GCN on all three datasets.
Response to rebuttal
I would like to genuinely thank the authors for their responses.
My main concerns however still remain, mostly in relation to the depth of the contribution. The additional methodological substance on top of ClusterGCN is thin and I believe the current additional analyses are not interesting enough to compensate that. The current theoretical claims seem to be become less trivial only for a specific lifting procedure, thus limiting its impact. Experimentally, the authors acknowledged that more analyses and studies are possible by lifting after batching, and I believe that some should minimally be addressed already in this paper.
I believe the paper still requires additional work to be ready for publication and I maintain my current score.
We thank the reviewer for the thorough review, for recognizing the clear motivation (S1) and the breadth of datasets and architectures (S2), and for the concrete suggestions on what a more informative analysis would study. We respectfully disagree, however, with two of its conclusions: that the contribution is a thin application of Cluster-GCN (W1), and that the structural analysis is trivial and not specific to higher-order domains (W2).
The batching is Cluster-GCN's, and the paper builds on it explicitly (Section 3.1). What we add is lifting within each mini-batch, which lets the mini-batch control both the construction of the higher-order domain and the execution of the model. As a result, an entire family of existing TNNs, across all three higher-order domains, trains unchanged on Reddit and OGBN Products, where full-domain execution exceeds the available resources for several of them. Below, we answer each point and the question in turn.
W1. Methodological Novelty and Relationship to Cluster-GCN
We agree that partitioning and stochastic cluster grouping are Cluster-GCN's contributions. The paper credits Cluster-GCN as the methodological foundation (Section 2) and introduces our batching as "following the multi-cluster batching scheme of Cluster-GCN" (Section 3.1), but this should be clear from the start. In the revised version, we state this in the introduction. However, we see this simplicity as a strength: full lifting is what has kept TDL benchmarks small, and batching before lifting lets any TNNs and liftings run unchanged on graphs where it fails. What changes for TDL is the role of cross-cluster edges: for a GNN they carry messages, but for a TNN they do both: decide whether higher-order structures exist at all and thereby allow them to carry the messages. In fact, our ablation reflects this: on Cora Full, removing them costs GCN 0.08 pp but TopoTune 10.01 pp (Table 2). The core contribution is the ability to scale an entire family of architectures: higher-order TNNs from all three domains now train on large benchmarks like Reddit and OGBN Products (Table 1). It also includes the recovery analysis and the measurement of full-domain construction costs.
W2. Depth of Theoretical Guarantees and Alternative Partitioning Strategies
We respectfully disagree that the analysis is trivial or not specific to higher-order domains. Its starting condition, that a structure is recovered exactly when its supporting clusters share a mini-batch, is an assumption on the lifting procedure. It holds trivially for graphs (the identity lifting) and holds for the neighbourhood and clique-complex liftings, but it can fail for cycle-basis lifting, where restricting the graph can change the selected basis (Appendix C.1). On Cora Full, the analytical prediction matches the measured recovery of hyperedges, triangles and simple cycles, while cycle-basis recovery falls below it for exactly this reason (Figure 7, Appendix C.13.2).
The lifting also determines how many clusters a structure needs: a graph edge spans at most two, whereas a triangle can span three, a retained cycle up to nine, and a neighbourhood hyperedge has no fixed bound (Section 3.3, Appendix C.13.1). This separates lifting families: on Coauthor Physics, complete neighbourhood hyperedges reach only 62.8% recovery even at q=1,000, whereas both 2-cell families exceed 99.8% (Appendix C.13.1). Therefore, observability does not imply exposure: on Questions at q=20, every cellular and simplicial 2-cell is observable, yet only 22.0% and 31.9% of their supports are encountered within 200 epochs (Appendix C.13.1).
The reviewer is right that these quantities depend on the partition. For predictive performance, a new sweep over K and q (see our reply to Reviewer CeGJ, Q4) shows that the higher-order models vary by at most 3.9 points on Questions and 2.3 points on Amazon Ratings, while GCN on Questions is the most sensitive. We thank the reviewer for the suggestion to study the interplay between partitioning and lifting, which we find convincing. Our ablation points in this direction: on Cora Full, METIS improves GCN by 0.98 pp but EDHNN, UniGNN and SCCNN by 5.3–6.5 pp. Structure-aware cluster merging is a natural extension that we plan to investigate.