Node-level random walk has been widely used to improve Graph Neural Networks. However, there is limited attention to random walk on edge and, more generally, on $k$-simplices. This paper systematically analyzes how random walk on different orders of simplicial complexes (SC) facilitates GNNs in their theoretical expressivity. First, on $0$-simplices or node level, we establish a connection between existing positional encoding (PE) and structure encoding (SE) methods through the bridge of random walk. Second, on $1$-simplices or edge level, we bridge edge-level random walk and Hodge $1$-Laplacians and design corresponding edge PE respectively. In the spatial domain, we directly make use of edge level random walk to construct EdgeRWSE. Based on the spectral analysis of Hodge $1$-Laplcians, we propose Hodge1Lap, a permutation equivariant and expressive edge-level positional encoding. Third, we generalize our theory to random walk on higher-order simplices and propose the general principle to design PE on simplices based on random walk and Hodge Laplacians. Inter-level random walk is also introduced to unify a wide range of simplicial networks. Extensive experiments verify the effectiveness of our random walk-based methods.
Paper
References (53)
Scroll for more · 38 remaining
Similar papers
Peer review
Summary
The authors generalize node-level random walk positional and structural encoding to edge-level (1-simplex) and higher-order simplex random walks. They focus on the edge-level for both theoretical and empirical results. Their approach is motivated primarily through theory, and then expanded empirically to the algorithm level. In addition, the authors prove important results about their new algorithm, allowing their architecture to be strictly more expressive than 1-FWL. Empirically, their results outperform their selected baselines.
Strengths
The paper's strengths lie in their novel approach to generalizing node-level random walks to edge-level and beyond. Although no empirical evidence is provided for the higher-levels, we see convincing empirical evidence that edge-level features contribute to the overall performance of the model. To the best of my knowledge, this is one of the first times that Hodge Laplacians have been used in GNN contexts, allowing the authors to apply their algorithms to practical examples.
Weaknesses
The paper's weaknesses lie in the lack of extremely convincing empirical results and the lack of clarity in the paper. Empirically, the authors' new algorithms generally perform slightly better than their baselines; however, in around half the datasets provided, there exist other models which perform better than their algorithms. If possible, it would be more convincing to build their new algorithms on the current state-of-the-art models. Experiments on synthetic datasets that require models to be strictly more expressive than 1-FWL would also be helpful here (presumably, models with the proposed algorithms would perform drastically better). The paper is unclear at times. Although the theory is interesting by itself, the importance of the results that were derived is not clear, and the algorithms are not explicitly defined anywhere. Explicit "algorithm" sections describing EdgeRWSE and Hodge1Lap would add much to the paper. Finally, the authors mention a "novel Random Walk Message Passing scheme" for the first time in the experiments section, with no prior explanation anywhere else in the paper. It seems a bit isolated from the rest of the paper; I would rather it be described in the body or in a separate manuscript entirely, instead of trying to fit into an already dense paper. There also exist many grammar and syntactical mistakes scattered throughout the paper (examples: line 150 typo, 173 grammar, 263 typo).
Questions
1. Are the new proposed approaches equivalent to RWSE and other approaches in terms of theoretical time complexity and practical compute time, memory, and parameters? 2. Why were GINE, GPS, and GATEDGCN chosen as base models to augment?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
1 poor
Contribution
3 good
Limitations
The authors do not include many limitations in their work, but based on my understanding of the work, I believe that all limitations are implicitly addressed. I believe there are no potential negative societal impacts of their work.
Summary
A major issue with graphs is the absence of positional information on nodes, which decreases the representation power of GNNs to distinguish e.g., isomorphic nodes. An approach to tackle this issue is to introduce Positional Encoding (PE) and Structural Encoding (SE) of nodes and inject it with node features. Most PE and SE techniques are based on node-level (0-simplices ) and edge-level (1-simplices ) random walk features. This paper analyzed the theoretical expressivity of node-level and edge-level random walks. The authors also introduce EdgeRWSE and Hodge1Lap, new edge-level random walk-based features that make GNNs more powerful. The authors analyzed theoretically the expressivity of these methods. They also introduced and generalized the study to random walks on higher-order simplices. The proposed approaches were tested empirically on many datasets and achieved competitive results with state-of-the-art methods.
Strengths
- The paper is well-written and organized. I appreciated sections about 0-simplices,1-simplices and high-order simplices. - It introduces a reasonable way to facilitate the expressivity of GNNs through positional and structural encodings. - The paper studied and analyzed the theoretical expressivity of node-level, edge-level random walks. - The paper generalized the random walks to high-order simplices and analyzed their expressivity.
Weaknesses
The main weaknesses of the paper have to do with the empirical analysis. - The combination of GNNs with EDGERWSE and HODGE1LAP has been tested only for GPS and GINE architectures. To validate the assumption that ‘EDGERWSE and Holde1LAp improve the performance of GNNs’, the combination should be tested for other GNN architectures as well, e.g., GIN, PNA, etc. Especially since the proposed positional and structural encoding is applicable to any standard GNN. - The experiments have been performed for graph-level tasks only (mainly graph classification and graph regression tasks). What is the performance of such approaches on node classification tasks? - The comparison with previous random walk-based PE and SE is missing, i.e., methods in papers [31,1,30,19]. EDGERWSE and Holde1LAp should be compared with the PE and SE baselines using the same GNN architecture. - The time complexity for generating EDGERWSE and Holde1LAp is missing.
Questions
In the weaknesses part above, I have included most of my questions to the authors. One more question follows below. - From Tables 1, 2 in the main paper and Tables 1, 2 in the supplementary material, I couldn't see a huge improvement in the performance when using EDGERWSE and Holde1LAp methods. Could you please further elaborate on this point?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Some of the limitations of the proposed methodology have been discussed in the paper.
We are looking forward to your reply
We thank reviewer for the review points, and we have answered your questions in detail while making every effort to improve the experiments. We are looking forward to your reply to see if we have properly addressed your concerns. Your response will definitely help to make a more reasonable decision on our paper.
Reviewer response
I would like to thank the authors for their detailed responses. Discussing the main issues raised in my review, namely experiments on node classification, comparison to other random walk-based PE/SE, and complexity analysis, definitely help to better understand the functioning of the proposed methodology. Considering the comments of the other reviewers, I have accordingly modified my score.
Summary
The paper studies random walks over simplicial complexes to construct novel positional and structure encoding methods for improving graph neural networks. In particular, the authors propose two strategies to construct edge embeddings, namely EdgeRWSE (via random walks on the edges) and Hodge1Lap (via spectral analysis of the Hodge 1 Laplacian). Finally, these constructions are theoretically generalized to higher order simplices for generic simplicial complexes.
Strengths
The paper is clearly written. The contributions are relevant and the ideas proposed seem novel. In particular, I liked the idea of using the Hodge Laplacian's kernel to enrich the GNN with some information about the graph's cycles.
Weaknesses
Section 6 generalises the method to higher order simplexes but it doesn't seem necessary in the main paper, which instead discusses only normal graphs. This generalisation is not used in the experimental section either. I feel like Section 6 could be safely moved in the supplementary material to keep the paper more focused on the main applications and contributions, but I am open to discussions about this. This could free some space to include the details about the RWMP method, which is currently missing from the main paper.
Questions
lines 248-249: the use of the terms sign-invariant and basis-invariant seems confusing since I don't see a group action. It seems more natural to describe this issue in terms of "uniquess only up to a sign / change of basis". I would at least mention this fact more explicitly to motivate the choice of words sign/basis-invariant. lines 268-272: while the kernel space of $L_1$ can count all cycles (as a vector space, it has a dimension per cycle), detecting individual cycles is - as far as I know - a more complex problem which boils down to finding particular sparse bases for the first (co)homology group (i.e. the kernel of $L_1$). The projection of the constant vector $\boldsymbol{e}$ in eq. 5 only spans a 1 dimensional subspace of the (co)homology group so it can not detect all cycles. For this reason, I find the claim that Hodge1Lap can extract cycles in a natural way requires some further comments and clarification. line 289: could you provide some intuition about why the lifting is done this way? For example, why is the lifting done to a 2-times larger space rather than a $(k+1)!$ times larger one (one copy for every permutation of the nodes in a simplex)?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
2 fair
Contribution
3 good
Limitations
There is not explicit discussion of the limitations of the method.
Summary
Positional and structural encodings have been widely studied, especially in the context of graph transformer architectures where such encodings often make up for the lack of inductive bias provided by the original graph, due to dense connectivity in the attention mechanism. RWSE (random walk structural encodings) are common approach based on random walk probabilities of a node returning to itself after differing numbers of steps. The authors build on this work, drawing from theory of simplicial complexes and Hodge deRham theory, to propose a set of edge-level positional encodings. They provide theoretical analysis of the proposed technique and evaluate its effectiveness by incorporating the positional encodings into MPNNs and/or graph transformers on a number of datasets, including ZINC, as well as datasets from the OGB and LRGB collections.
Strengths
The authors consider an interesting question around positional and structural encodings, which have been widely studied. The authors introduce an interesting approach using Hodge Laplacians that build on previous work.
Weaknesses
-The paper seems a bit rushed and has some typos. The paper can benefit from some careful proofreading. -Given that this work proposes GNNs based on techniques related to simplicial complexes, I would have liked to see experimental comparisons to some existing architectures based on simplicial complexes (e.g., [3], [4], [28] in the paper) or other topological baselines. -The experimentation on OGB benchmarks has very little explanation. I would like to see more details about the setup and design choices. I find the authors' approach interesting but think the experimental evaluation section could be stronger in general. I'd be willing to raise my score upon answers to the below questions and some actions to address the points stated above.
Questions
-The experiments on ZINC appear to use a standard MPNN (GINE) for the purposes of testing out the authors' random walk simplicial complex based approach. On the other hand, the experiments on OGB appear to be based on GPS framework which uses a combination of graph transformers and MPNNs. Is there a reason for this choice? Have you tried using the proposed random walk simplicial encodings with GPS/graph transformers on ZINC? This would be interesting, as positional and structural encodings are particularly critical for graph transformer architectures where the inductive bias provided by the original graph is lost due to dense connectivity. -Suggestion: It should be noted that for several of the LRGB datasets you consider in the appendix, there are improved results, so the results by the authors are not quite SOTA. For instance, the recent Exphormer [1] paper improves on GraphGPS numbers for most of the LRGB datasets. Please include this baseline.. -It is not clear to me which results are new among the theorems (e.g., Thms. 5.2, 5.3 and the ones in the appendix) as opposed to previously known. It would be good for the authors to clarify this [1] Exphormer: Sparse Transformers for Graphs - Shirzad, Velingker, Venkatachalam, Sutherland, Sinop. ICML 2023.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
I could not find a discussion about the limitations of the authors' proposed technique. However, it is possible that I have missed it. Societal impacts are not relevant to this work.
We are looking forward to your reply
We thank reviewer for the review points, and we have answered your questions in detail while making every effort to improve the experiments. We are looking forward to your reply to see if we have properly addressed your concerns, as you said you are wiling to raise your score if these questions are addressed. Your response will definitely help to make a more reasonable decision on our paper.
Summary
Authors propose leveraging the random walk on different orders of the simplicial complex domain to enhance graph neural networks both in their performance and in the understanding of their theoretical expressivity. $\textbf{Node level}$ Authors frame existing positional encoding (PE) and structure encoding (SE) methods in the context of random walk on 0-th order simplices and the traditional graph Hodge Laplacian $\mathbf{L}_0$. Using this framework, they provide a theoretical expressivity bound for RWSE, a SE method, and provide an intuitive explanation of its nature. They summarize PE methods and their expressivity bounds from the literature. $\textbf{Edge level}$ Authors introduce two novel edge-level PE and SE methods: - EdgeRWSE, which directly generalizes random walk on nodes to edges, with 3 variations: full (upper and lower adjacency), down adjacency directed, and down adjacency undirected. Authors test the directed/undirected down variations on graph regression (not competitive). Authors test a variation on graph-level classification (not competitive, overfits). - Hodge1Lap, the first sign / basis invariant edge-level PE, with 1 variation based on the spectra of the Hodge 1 Laplacian. Authors test sign invariant and sign / basis invariant Hodge1Lap on graph regression (SOTA). Authors test a variation on graph-level classification (competitive). - Random Walk Message Passing, a new random walk method based on a metric of node feature similarity. Authors test it on graph regression (SOTA) and show that it can improve the performance of Hodge1Lap (competitive). $\textbf{k-level}$ Authors extend the theoretical framework of the random walk on simplicial complex arbitrary order $k$ by proposing: - a method that extends RWSE to $k$-order. - inter-order random walk, a method that utilizes the upper/lower boundary neighborhoods of a $k$-simplex. Supplementary materials provide mathematical proofs for expressive bounds, further theoretical analysis of proposed methods, explain RWMP and provide further experiments on MNIST, CIFAR10, and LRGB.
Strengths
- This paper presents a comprehensive and wholesome approach to higher-order random walk, addressing 0, 1, and higher orders in a systematic manner. - It offers a thorough and detailed background in preliminaries, providing a solid reference for the underlying concepts. The supplementary materials are additionally thorough. - Authors provide intuitive explanations for the theoretical bounds and the functioning of the PE/SE methods. Reframing pre-existing methods in a fresh, accessible way is a valuable contribution. In the same vein, observed performance increases are supported by a sound theoretical justification, lending credibility to the results obtained. - The regression experiments conducted on top of the GINE model are convincing, demonstrating the effectiveness of the proposed methods in graph regression tasks. - The introduction of the clever new method RWMP opens the door to a new and flexible class of random walks based on the concept of a "feature distance" metric. This could be the first such method of many, as new metrics are defined on different feature orders with different probabilities.
Weaknesses
- Implementing the (appropriate) proposed methods on higher-order datasets would have been a significant contribution. Based on the increased performance of Hodge1Lap which benefits from upper adjacency schemes, I would have been very interested to see the full EdgeRWSE, and the inter-order random walk in action. Lifted benchmark datasets, including Zinc 12k [1] are common in topological deep learning research to allow for comprehensive testing of proposed methods. - While the paper introduces a valuable theoretical bound for a pre-existing method at the node level, this remains a case-by-case study of theoretical expressivity. This section would have been much more meaningful if it generalized this special case to a systematic method for bounding PE/SE methods from the random walk framework. - Authors make no mention of other discrete topological domains, cellular/cubical complexes being the most obvious, and how their proposed methods extend to datasets defined on these domains. This low-hanging fruit would be an important contribution to the cellular complex domain which only differs from the simplicial complex in the construction of higher-order features. - It would have been preferable to observe the proposed methods integrated with a wider range of neural network architectures, beyond just GINE, GPS, and GatedGCN. While the authors argue that the simplicity of these architectures showcases the power of their methods, I am still curious to see how these techniques impact the performance of more complex models like transformers and subgraph variations. Are there still significant improvements observed in these cases? - There are many syntax and grammatical errors in the text that could be easily caught with spell-checking software like Grammarly. Here are $\textit{some}$ examples : - line 106: "there are still limited research" should be "there is still" - line 108: "establish several connection" should be "establish several connections" - line 109: "provide theoretically expressive bound" should be "provide a theoretically expressive bound" - line 129: "resistance in electrical network" should be "resistance in an electrical network" - line 484 in supplementary materials: "an function" should be "a function" 1. Bodnar, Cristian, et al. "Weisfeiler and Lehman Go Cellular: Cw networks." Advances in Neural Information Processing Systems 34 (2021): 2625-2640.
Questions
- Could the proposed methods generalize to discrete domains without orientation, where the adjacency matrix is set-type (all positive) as in hypergraphs? And if so, how would their design/performance compare to previously introduced methods [1,2]? - Is there an intuitive explanation for the state-of-the-art (SOTA) results achieved in the long-range graph benchmark task, particularly in relation to the additional reach that random walk methods gain from neighborhood structures? From my perspective, these impressive results should have been included in the main text. It could be direct proof of the benefits of simplicial complex-based random walks. - What variations of EdgeRWSE and Hodge1Lap were used in the graph classification benchmark task? They are not specified in the table or in the text. 1. Carletti, Timoteo, et al. "Random walks on hypergraphs." Physical Review E 101.2 (2020): 022308. 2. Chitra, Uthsav, and Benjamin Raphael. "Random walks on hypergraphs with edge-dependent vertex weights." International conference on machine learning. PMLR, 2019.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
- The authors highlight the overfitting behavior of EdgeRWSE in graph classification. It would have been interesting to see how different variations of EdgeRWSE compare in terms of overfitting when applied to datasets with higher-order features. Additionally, it would have been valuable to understand if this overfitting limitation is also at play in the non-competitive performance on Zinc 12k. - A significant limitation left unaddressed in the paper is the single topological domain. While the paper focuses on simplicial complexes, all of its proposed methods and Hodge Laplacian theory could fit into a larger framework of topological domains, including cellular complexes and hypergraphs. Each random walk could be generalized to such domains and tested on respective datasets. If any theoretical reasons prevent such an extension, the authors should clearly outline and explain the reasoning behind this limitation.
Thanks for the detailed answer. Regarding the ability to detect cycles, my comment regarding the one-dimensional subspace referred to the fact you only project the constant vector $\textbf{e}$. As a result, the output of the linear operation $P_{proj, 0} \textbf{e} = UU^T \textbf{e}$ "probes" only a one-dimensional subspace of the kernel of $L_1$. From Corollary 3.10-11, I understand that the scalar $[UU^T \textbf{e}]_j$ contains some information about the cycles the node $j$ belongs to. For example, *if no cycles overlap*, $[UU^T \textbf{e}]_j$ tells whether the node $j$ belongs to a cycle or not. However, it seems to me this provides no information about which cycles each node belongs to. For this reason, it seems the model is only able to detect whether the graph contains cycles or not, but it is not able to distinguish different cycles and, therefore, detect them. This observation seems to also fit the intuition that the feature $UU^T \textbf{e}$ only catches the information contained in a 1-dimensional subspace, while detecting individual cycles requires the whole kernel of $L_1$. Moreover, when cycles overlap or the graph contains 2-simplexes, this information is further "diluted" over multiple nodes (see Corollary 3.11 and following discussion): do I understand correctly that only nodes belonging to tree-like leaf subgraphs will have zero values? While this construction can be useful in graphs where cycles are clearly distinguished and non-overlapping, it seems less powerful when generic graphs are considered (this seems related to the fact that a cycle basis is rarely unique so the statement "a node belongs to a cycle" might not be well defined). Is my understanding correct?
Further clarifications on Hodge1Lap
Thank you for your response. Your understanding is basically right, but here are some points we want to further explain. - Hodge1Lap is an edge-level PE, which provide information about edges instead of nodes. Thus, every word 'node' in your previous comment should be replaced with 'edge'. - You are right that projecting the constant vector to the kernel space of $\mathbf L_1$ will result in element $j$ equals to 1 if edge $j$ is in a cycle, and 0 otherwise. It's unable to distinguish different cycles, nor indicating which cycle an edge belongs to. However, besides the projection method, we proposed another implementation variation of Hodge1Lap (namely ABS), see line 345 of main text and line 360-362 of supplementary. This variation can distinguish and detect different cycles, which we explain as follows. In the original text, this implementation can be described as $\sum_i MLP(|v_i|)$, where $||$ indicates taking element-wise absolute values, and $v_i$ refers to the interested eigenvectors (e.g. orthogonal basis of kernel space of $\mathbf L_1$, in case that we are discussing detecting cycles). For simlicity, we first do not consider overlapping or 2-simplexes, then every eigenvector $u_i$ corresponding to zero eigenvalues has the following properties: (i) the elements corresponding to edges that are not in any cycles are zero; (ii) the elements corresponding to edges from the same cycles have identical absolute values, while those of edges from different cycles (almost surely) have different absolute values. These properties can be easily verified, as any $v_i$ can be represented as a linear combination of $u_i$ described in Theorem 3.9. Therefore, $\sum_i MLP(|v_i|)$ obtains different values for edges from different cycles, hence distinguishing and detecting them. In practical implementations, we further apply a random projection technique to make Hodge1Lap more robust to the choice of basis $v_i$: $\sum_j MLP(\sum_i \alpha_{ij}|v_i|)$, where $\alpha_{ij}\sim \mathcal N(0,1)$ are random variables, and $j=1,\dots,J$ where $J$ is the maximum number of projection. Through this design, the model can explicitly learn different cycles and implicitly maintain basis invariance. - For cases where there are overlap or higher order simplexes, the computed PEs are indeed different from cases without them. However, the information is not 'diluted', as long as the model is able to learn the difference. As for 'nodes belonging to tree-like leaf subgraphs will have zero value', we guess you are actually referring to the shared edge between two cycles. And we can also mitigate this zero value of shared edge via computing $|\mathbf U||\mathbf U|^T \mathbf e$ (in which the shared edge of two cycles will have a larger value) instead of $\mathbf U\mathbf U^T \mathbf e$. In summary, the projection method indeed can only indicate whether an edge is in a cycle, but not which cycle it belongs to. However, this is still beneficial for cases where cycles are not dense, e.g. in most molecular graphs. Moreover, the ABS implementation of Hodge1Lap and the random projection technique are fully capable of distinguishing and detecting different cycles, even in cases where cycles are dense or overlapped. This is extremely beneficial for generic graphs, proving the effectiveness of Hodge1Lap. Hope that we have addressed your questions. Please let us know if you need more further clarification.
Thanks for the quick and detailed answer! I would encourage to include this discussion in the paper, since it seems very helpful to understand the capacity and the limits of the proposed approach. > Thus, every word 'node' in your previous comment should be replaced with 'edge'. That is true, sorry for my mistake! > You are right that projecting the constant vector to the kernel space of will result in element equals to 1 if edge is in a cycle, and 0 otherwise. It's unable to distinguish different cycles, nor indicating which cycle an edge belongs to. Thanks for clarifying this! I'd again encourage the authors to mention this in the discussion in page 6. > However, besides the projection method, we proposed another implementation variation of Hodge1Lap (namely ABS), see line 345 of main text and line 360-362 of supplementary. [...] > In the original text, this implementation can be described as $\sum_i MLP(|v_i|)$, where [...] and $v_i$ refers to the interested eigenvectors (e.g. orthogonal basis of kernel space of $L_1$, in case that we are discussing detecting cycles) I feel this design choice seems important to go beyond the limitation above but I don't think this design is clearly described in the original manuscript. In particular, I am still unsure how the vector $v_i$ is built: the paper mentions "summing over absolute values of eigenvectors" (l. 345), do you mean $v_i = \sum_j |u_j|$ where $[u_j]_j$ is the eigenvectors basis described in Theorem 3.9? As argued above, the projection $v_i = P\_{proj,i}e$ of just the constant vector $e$ only leads to 0 or 1 features on the edges so it is not a good choice of $v_i$. Moreover, is the construction $\sum_j MLP(\sum_i a_{ij} |v_i|)$ described in the paper? I quickly checked the manuscript but I couldn't see it (sorry if I missed it). How do you apply this construction over different graphs? (Do I understand correctly that the index $i$ ranges over the unique eigenvalues? Then, the $L_1$ matrix of different graphs might have different number of unique eigenvalues, right?). > the elements corresponding to edges from the same cycles have identical absolute values, while those of edges from different cycles (almost surely) have different absolute values Could you clarify what the values will be? If we use $v_i = \sum_j u_j$ where $[u_j]_j$ is the eigenvectors basis described in Theorem 3.9, the entries of $v_i$ encode the cycle length (according to Thrm 3.9). Why do you think these values are almost surely different? Cycles with similar lengths seem like something that can occur commonly in general graphs. Moreover, if you assume the basis in Theorem 3.9, how do you compute it in practice (since numerical methods will return a random orthogonal basis, not necessarily this one)? This seems related to the typical problem of finding a sparse basis for homology I was referring to in my initial review. Overall, I feel like some more space in the main paper could be dedicated to clarify these important design choices
Thank you for your suggestions! We will definitely include these systematic discussion as well as details of Hodge1Lap construction (including random projection technique) in the revision paper. As for your questions, we think the followings can be answered together: (1) do you mean $|v_i|=\sum_j u_j$ where $u_j[j]$ is the eigenvectors basis described in Theorem 3.9? (2) Could you clarify what the values will be? Why do you think these values are almost surely different? (3) if you assume the basis in Theorem 3.9, how do you compute it in practice (since numerical methods will return a random orthogonal basis, not necessarily this one)? The answer would be: $v_i$ are **not** $u_j$ described in Theorem 3.9, instead, they are **arbitrary random basis**, i.e. linear combinations of $u_j$, as long as they span the same subspace as $u_j$ (they don't even have to be orthogonal). One example would just be the random orthogonal basis returned by numerical methods, obviously, both these random basis $v_i$ and those $u_j$ in Theorem 3.9 span the kernel space of $\mathbf L_1$. We want to **make use of the randomness** to make the values corresponding to different cycles **different** from each other. Let us see an example, suppose we have a graph with ten edges, where edge $0,1,2,3$ form a 4-cycle, edge $5, 6, 7, 8, 9$ form a 5-cycle, and edge $4$ connects these two cycles. The basis from Theorem 3.9 will be $u_1=[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]^T, u_2=[0,0,0,0,0,1,1,1,1,1]^T$. However, the $v_i$ we use here are different from them. Instead, they are any random orthogonal basis (also linear combinations of $u_i$), for instance, $v_1=0.1 u_1+0.9u_2=[0.1,0.1,0.1,0.1,0,0.9,0.9,0.9,0.9,0.9], v_2=-0.4u_1+0.6u_2=[-0.4,-0.4,-0.4,-0.4,0,0.6,0.6,0.6,0.6,0.6]$. Then obviously in either $|v_1|,|v_2|,|v_1+v_2|$, the values of different cycles are different, so that $\sum_{i=1}^2 MLP(|v_i|)$ would result different values for different cycles, but the same for edges within one cycle. Therefore, the model is able to distinguish that there are two different cycles, as different cycles (almost surely) correspond to different values. Moreover, the random projection technique is applied to improve the generalization power of the ABS form of Hodge1Lap, i.e. by training with random coefficients $\alpha_{ij}\sim \mathcal N(0,1)$, the model do not rely on specific concrete values of $v_i$, but make use of statistical information about these cycles. In our experiments, we observe that either the deterministic version (directly use the basis returned by numerical values) or the random projection version works well. We report the former implementation as "ABS" Hodge1Lap in Table 1 of main text. Again, we admit that the above "ABS" implementation is not basis invariant (i.e. the output is determined by input basis $v_i$), while the projection method described in the main text is basis invariant (as we project the vectors into the kernel space spanned by the basis). However, the "ABS" version can distinguish different cycles, and may have more generalization power due to randomness. Experiments show that both two designs have good performance. Additionally, it's remarkable that traditional LapPE that make use of eigenvectors of graph Laplacian (Hodge-0 Laplacian) suffer from the same problem (the output relies on the choice of basis), but LapPE is still widely adopted, e.g. in GPS and many other experiments. In this sense, our "ABS" version of Hodge1Lap is the natural extension of traditional LapPE. We will definitely include these detailed discussion into the new version of our paper to let readers better understand. Sorry for the confusion and hope that we have addressed your questions.
Thanks for the clarification! Again, I encourage the authors to include this discussion in the main paper, since it seems particularly important.
Thank you for your answer and the new experiments. Regarding 2., section 4 of the paper would benefit from this concise list of expressivity theorems. Regarding 3, this gained performance form cellular representation is so exciting! Cellular complexes do in fact have a strict definition as a topological domain, explained well in a paper already cited [3. Weisfeiler and Lehman Go Cellular:] Regarding question 1, I think it would be worth explicitly mentioning that this method naturally extends to hypergraphs. It is not a trivial question and would widen this work's contribution to the field without requiring any additional proofs or experiments. Regarding question 3, the paper should absolutely be specifying what versions of EdgeRWSE and Hodge1Lap it refers to in all experiments, without assuming the reader can figure it out themselves. Naming the method used is a critical component to any Result section.
Thank you for your valuable review points and suggestions! We have made every effort to address all your questions and implement all your suggestions. We are glad at your acknowledgement. Regarding 2, we will add this list of expressivity theorems of node-level PE to section 4 of our paper revision. Regarding 3, we will include the discussion and results on cellular complex extensions and give some preliminary expressivity results in the revision. Regarding question 1, we appreciate your suggestion and will explicitly explain in the revision that our methods naturally extend to hypergraphs. Regarding question 3, we will explain the variations of our methods in the paper. Hope that we have addressed all your concerns. Please inform us if you have more questions.
Thank you
We sincerely appreciate the valuable suggestions by reviewer. We will include all these new theoretical results, experiments and discussions during rebuttal to make our paper more contributive. Now that since we have solved all your questions and implemented all the suggestions you have put forward (there are even more results in our replies to other reviewers), we are wondering if you are willing to raise your score. Thank you!
I thank the authors for largely implementing my feedback. I have modified my score accordingly.
Thank you for acknowledgement
Thank you for your valuable acknowledgement! We sincerely appreciate your feedbacks, and we believe that the final version of our paper will be more contributive after we include these new results.
I thank the authors for their detailed responses. I appreciate the new results and am interested to see how the reorganization of the paper would look like. I will maintain my score for now.
Thank you for your review points and your reply. We are glad that you are satisfied with our responses and the new results. For the final version of our paper, we will reorganize the paper and improve our writing to make it clearer, and include all these new results as well as more details to enrich the paper. We believe that our paper will be a huge contribution.
Looking forward to your reply
Dear reviewer, We sincerely appreciate your review points. However, while other reviewers have positively acknowledged our efforts, you haven't replied to our rebuttal yet. We put great effort into your review points and tried our best to address your concerns during the rebuttal period. Therefore, we genuinely hope that you could reply to us and give your final decision, especially given that you have promised to raise your score if your concerns are addressed. Your response is of great importance for our paper to be evaluated fairly. Thank you!
Decision
Accept (poster)