- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper discusses four types of higher-order graph representations and their integration into deep learning through higher-order neural network architectures. It then conducts a meta-analysis of ten survey papers, highlighting gaps in the literature, particularly the limited attention given to portability and transfer learning across different higher-order representations.
Critical strengths
- The paper is overall well written and well organised.
- Portability and transfer learning across higher-order representations are relevant and potentially valuable research directions.
- The paper provides a useful illustrative example showing how the ability to distinguish higher-order structures depends on the representation, propagation rule, and input features.
Critical weaknesses
- Overstatement of the contribution. The authors state that they aim to "fill these knowledge gaps and connect the mathematical dots among multiple fragmented representation frameworks". However, the paper primarily reviews existing representations and identifies open research directions, rather than establishing new connections between these mathematical frameworks. Therefore, I find this claim stronger than what the paper delivers.
- Clarification of expressivity claims. The authors suggest that general analytical results on the expressivity of higher-order neural networks remain relatively rare (Lines 380–383). However, several theoretical results already exist, including those of Bodnar et al. (2021) on the expressive power of simplicial and cellular neural networks (Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks [1] and Weisfeiler and Lehman Go Cellular: CW Networks [2]). I am not necessarily disputing the authors' claim, but I would appreciate a clarification of what they mean by "general and analytic statements" in this context, ideally with an example and a reference to a result that fits this description.
- Distinction between higher-order representations and their algebraic constructions. I am not convinced that cochain complexes should be presented on the same footing as hypergraphs, simplicial complexes, and cellular complexes in Section 2.1. While the latter describe underlying combinatorial or topological structures, chain and cochain complexes are algebraic constructions that can be associated with such structures, for instance through the corresponding boundary and coboundary operators. In this sense, they appear more naturally as algebraic representations of the underlying structures rather than as an analogous category of higher-order networks. I think the taxonomy would benefit from making this distinction more explicit, particularly given the paper's emphasis on separating mathematical abstractions from their algebraic instantiations.
- Ambiguity of the central position. The paper moves between portability, principled representation selection, and automated model adaptation without sufficiently clarifying their conceptual relationship or identifying which constitutes its primary thesis. While portability and transfer learning are presented as central questions in the abstract and introduction, the conclusion advocates principled representation selection (Lines 454–456) and ultimately automated model selection and adaptation (Lines 484–485). Although these objectives are related, the connections between them are not sufficiently developed. As a result, the paper sometimes appears to pursue several directions without establishing a sufficiently clear overarching argument.
- Limited development of the proposed perspective. Although the paper identifies relevant open problems, it could provide a more concrete conceptual account of portability and explain what distinguishes it from established transfer-learning settings. In particular, the relationship between Open Problems 2–4 and the central objective of portability could be developed more explicitly. This would help establish a more coherent research agenda and clarify how the proposed directions contribute to the main position.
References
[1] Bodnar, C., Frasca, F., Wang, Y., Otter, N., Montufar, G. F., Lió, P., & Bronstein, M. (2021). Weisfeiler and Lehman go topological: Message passing simplicial networks. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research, 139, 1026–1037.
[2] Bodnar, C., Frasca, F., Otter, N., Wang, Y. G., Liò, P., Montúfar, G., & Bronstein, M. M. (2021). Weisfeiler and Lehman go cellular: CW networks. Advances in Neural Information Processing Systems, 35, 2625-2640.
Questions for authors
- Could the authors clarify the central objective of the paper and the relationship between portability, principled representation selection, and automated model adaptation? This is related to weaknesses 4-5 and is essential to my assessment.
- Could the authors clarify what they mean by "general and analytic statements" about expressivity, ideally by providing an example of such a result and an appropriate reference?
5 comments
Response to Reviewer bHA8 - Part 2
Q: Distinction between higher-order representations and their algebraic constructions. I am not convinced that cochain complexes should be presented on the same footing as hypergraphs, simplicial complexes, and cellular complexes in Section 2.1. While the latter describe underlying combinatorial or topological structures, chain and cochain complexes are algebraic constructions that can be associated with such structures, for instance through the corresponding boundary and coboundary operators. In this sense, they appear more naturally as algebraic representations of the underlying structures rather than as an analogous category of higher-order networks. I think the taxonomy would benefit from making this distinction more explicit, particularly given the paper's emphasis on separating mathematical abstractions from their algebraic instantiations.
A: We thank the referee for this careful point and agree. A cochain complex is an algebraic construction on an underlying simplicial or cell complex, defined through its coboundary operators, and so it belongs as much to the algebraic instantiations of Section 2.2 as to the abstractions of Section 2.1. We list it in Section 2.1 because one line of work, built on discrete exterior calculus, takes cochains (discrete differential forms) as its primary modeling object, and our meta-analysis tracks this as a separate vernacular. As suggested, Section 2.1 now states this distinction explicitly.
Q: Ambiguity of the central position. The paper moves between portability, principled representation selection, and automated model adaptation without sufficiently clarifying their conceptual relationship or identifying which constitutes its primary thesis. While portability and transfer learning are presented as central questions in the abstract and introduction, the conclusion advocates principled representation selection (Lines 454–456) and ultimately automated model selection and adaptation (Lines 484–485). Although these objectives are related, the connections between them are not sufficiently developed. As a result, the paper sometimes appears to pursue several directions without establishing a sufficiently clear overarching argument.
A: Our central thesis is that higher-order graph learning cannot choose among its many representations in a principled way until trained models can be ported between them, and that this capability is missing from the field today. The paper is built to establish both halves of this claim. Section 2 shows that representation choices are consequential: the same data admit several abstractions and algebraic encodings, and our Gram-mate experiment shows that a single encoding can discard or expose structure depending on the propagation rule. Section 3 shows that the field has no way to move between these choices. All ten organizing works discuss translating data between representations, but none addresses transferring a trained model, and our broader search of primary work found none either. Section 4 explains why this gap matters and what stands in the way of closing it. Principled representation selection and automated adaptation, discussed in the conclusion, follow from the thesis, since both require comparing or switching representations without retraining from scratch. This conclusion is not obvious: each representation's literature looks complete from within, and the gap becomes visible only when they are read side by side, as our meta-analysis does. The introduction and conclusion now state this thesis in one sentence.
Response to Reviewer bHA8 - Part 3
Q: Limited development of the proposed perspective. Although the paper identifies relevant open problems, it could provide a more concrete conceptual account of portability and explain what distinguishes it from established transfer-learning settings. In particular, the relationship between Open Problems 2–4 and the central objective of portability could be developed more explicitly. This would help establish a more coherent research agenda and clarify how the proposed directions contribute to the main position.
A: We thank the referee for pressing on this. By portability we mean reusing a model trained on one higher-order representation on another representation of the same data, without retraining from scratch. Established transfer-learning settings, such as fine-tuning or domain adaptation, keep the representation and change the task or the data distribution, so the source model applies to the target as it is. Portability changes the representation, and with it the operator the model is built on. For example, a hypergraph network propagates through incidences and a simplicial network through boundary operators, so the two share no parameters. Porting a model therefore requires correspondences between representations.
The open problems are organized around these correspondences. Open Problem 1 asks whether representations that disagree about the data can share a latent space through which models are ported. Open Problems 2-4 ask whether random walks, notions of dimension, and spectra supply the correspondences that could ground that space. Open Problem 5 asks what porting through that space costs in expressivity. As requested, we've updated Section 4 to clarify these relationships explicitly.
Q: Could the authors clarify the central objective of the paper and the relationship between portability, principled representation selection, and automated model adaptation? This is related to weaknesses 4-5 and is essential to my assessment.
A: Our central objective is the thesis stated in our response to Weakness 4: higher-order graph learning cannot choose among its representations in a principled way until trained models can be ported between them, and this capability is missing today. In our view, the three notions the referee highlights (portability, principled representation selection, and automated model adaptation) form a chain in which each depends on the one before. That is, portability is a prerequisite for principled representation selection, which in turn is a prerequisite for automated model adaptation.
Portability is needed for principled selection because choosing between, for example, a hypergraph and a simplicial complex for a task requires comparing them with what the model has learned held fixed. Today, changing the representation means training a new model, so any comparison confounds the representation with the training run (Section 4). Principled selection is in turn needed for automated adaptation, because an agent that changes representations as new evidence arrives makes this same choice repeatedly and without human judgment (Section 5). It can do so reliably only if each choice rests on evidence, not intuition.
Portability is therefore the foundation of the chain. Without it, representation choices cannot rest on evidence, whether they are made by researchers or by agents, which is why portability is the focus of our paper.
Q: Could the authors clarify what they mean by "general and analytic statements" about expressivity, ideally by providing an example of such a result and an appropriate reference?
A: We had originally attempted to communicate what we mean by “general and analytical statements” about expressivity (and give examples) in definition elsewhere in the text: “Expressivity is an account of which structures a model can and cannot tell apart, like isomorphism based expressivity tests (e.g. the Weisfeiler-Leman hierarchy) and motif count based expressiveness.”
In our updated manuscript, we have included additional text to make this even clearer, and included additional references (Bodnar et al. ICML 2021, and Bodnar et et al. NeurIPS 2021) on papers that do contribute such results.
Response to Reviewer bHA8 - Part 1
We sincerely thank you for your thoughtful comments. We greatly appreciate that you find our portability and transfer learning across higher-order representations are potentially valuable research directions. We are here to provide detailed replies to your comments and hope we can resolve your major concerns. We have revised our manuscript accordingly and uploaded a highlighted PDF.
Q: Overstatement of the contribution. The authors state that they aim to "fill these knowledge gaps and connect the mathematical dots among multiple fragmented representation frameworks". However, the paper primarily reviews existing representations and identifies open research directions, rather than establishing new connections between these mathematical frameworks. Therefore, I find this claim stronger than what the paper delivers.
A: We have revised the sentence the referee quotes so that it matches what the paper delivers: the introduction now says that we aim to identify these knowledge gaps and begin connecting the mathematical dots among the fragmented frameworks, and the abstract says that we identify mathematical connections among them.
To show concretely what connecting the dots means, the new Appendix D works through one example: propagation over the triangles of a graph, encoded in three ways, as a simplicial complex whose triangles are filled, as a hypergraph whose hyperedges are the triangles, and as an order-3 adjacency tensor. As we explain there, three short identities relate the encodings. The hypergraph incidence matrix is half the product of the unsigned simplicial boundary matrices. Summing the tensor over one index gives the hypergraph's triangle-weighted adjacency matrix. And the tensor's quadratic propagation equals one hypergraph message-passing layer with a squaring activation, minus terms that depend only on that adjacency matrix. So for linear, unsigned propagation through the triangles, the three encodings agree, and they come apart through the nonlinearity, which is what our Gram-mate experiment also shows.
The example is illustrative and does not cover all cases. Connecting all of the mathematical dots is the research program we advocate, and no single paper can complete it. Our contribution is to pose that program explicitly. We separate three choices the literature often conflates (the abstraction, its algebraic instantiation, and the learning rule), use the meta-analysis to locate where the frameworks fail to connect, namely the transfer of trained models, and define in Section 4 what a successful connection must achieve and which open problems stand in its way. The triangle example shows that once the problem is posed this way, connections become concrete and checkable.
Q: Clarification of expressivity claims. The authors suggest that general analytical results on the expressivity of higher-order neural networks remain relatively rare (Lines 380–383). However, several theoretical results already exist, including those of Bodnar et al. (2021) on the expressive power of simplicial and cellular neural networks (Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks [1] and Weisfeiler and Lehman Go Cellular: CW Networks [2]). I am not necessarily disputing the authors' claim, but I would appreciate a clarification of what they mean by "general and analytic statements" in this context, ideally with an example and a reference to a result that fits this description.
A: Thanks for mentioning these references, we are indeed aware of both of them and agree they do show that there is at least some prior work in this area. We previously did not cite them explicitly only because they already implicitly present in our meta-analysis, and surveys by Besta et al. and Papamarkou et al. have a rating of “substantive” for “expressiveness” precisely because these two surveys cite and discuss both of these references.
Because these constitute some of the only work we found on this topic, we still concluded that results on the expressivity of higher-order neural networks remain relatively rare.
We have cited these works explicitly in the updated manuscript to highlight that the literature is not completely silent on these topics, even if results are rare.