Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariance

We thank the reviewer for their thorough review and are happy that they find our work to be well-motivated and our approach to be elegant and thoroughly evaluated.

Weakness 1, Question 2: Other Variations using the Novel Laplacians

There are several ways to use our novel Laplacians for convolutions. Since the main focus of our paper lies on properly handling both signal modalities and the novel Laplace operators, we aimed not to overcomplicate the propagation scheme. Doing so would, for example, leave it open whether the success comes from our analysis or the more complex framework. We believe the success of using Laplacians as convolution operators makes a strong point in favor of our claim: By adequately treating different modalities a huge performance boost can be achieved already.

As asked by the reviewer, we extend our evaluation by a ChebNet-style [3] model and a GCN-like convolution $I - L/2$ in Table 17. The Chebyshev polynomials we use are detailed in Appendix E.1. The GCN-like baselines performs sub-par, potentially because the alternative convolution operator interferes with complex phase shifts used by EIGN to encode direction. The ChebNet variant performs exceptionally well. It even outperforms the basic EIGN, likely due to its increased receptive field and model complexity. We believe this showcases nicely the merits of our work: Our operators can be easily used in more complicated propagation schemes and achieve even better results. This motivates further work that builds on our analysis. We are very thankful for that pointer!

Weakness 2: Baselines

As requested by other reviewers, we extend our evaluation by two additional baselines:

• Following [1], we use the Laplacians of our work to create positional edge embeddings and feed them into a transformer (MagNet baseline).
• We also follow the suggestion of another reviewer and consider a different mechanism to encode directed edges, following recent work on directed node-level problems [2] (DirGNN baseline). We report their performance in Tables 4,5,9-14 and find that EIGN outperforms both baselines.

Weakness 3: Formatting

• We add full stops to equations where needed.
• We clarify that B^H means the conjugate transposed.
• We capitalize Laplacian in the References.

Question 1: Sign-Invariant Activation

The tanh activation meets this criterion and is used in previous orientation equivariant architectures [4]. In general, any odd (and non-linear) function is possible (sin, sinh, sgn, ...).

Question 3: Node Signals

Yes, the boundary operators of our proposals define a natural mapping to and from the node-level domain. Each boundary map translates node signals to orientation equivariant/invariant signals respectively.

Question 4: Weighted Signed Graphs

We see no problem in applying this to weighted graphs as well: Instead of using values of magnitude 1 in the boundary operators, using $\pm w^{1/2}$ recovers a weighted Laplacian operator. Similarly, one can define independent Laplacian convolutions for positive and negative edges, thus also covering signed graphs. Similar to the DirGNN baseline [2], one challenge would be to ensure information exchange between both edge types. By using the Magnetic Laplacians for both mechanisms one could represent signed and directed edges simultaneously. The datasets we study, however, do not support this data modality. If the reviewer has a pointer for a scenario where this modeling paradigm is needed, we would be very curious to hear that. We add a pointer regarding this direction to the future work section of our manuscript.

We again want to thank the reviewer for their helpful input. Especially the high efficacy of more complex propagation schemes using our Laplacians like a ChebNet showcases the merits of our study. If we left some points inadequately addressed we would be very happy about further discussions.

References

[1] Geisler, Simon, et al. "Transformers meet directed graphs." International Conference on Machine Learning. PMLR, 2023.

[2] Rossi, Emanuele, et al. "Edge directionality improves learning on heterophilic graphs." Learning on Graphs Conference. PMLR, 2024.

[3] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in neural information processing systems 29 (2016).

[4]: Roddenberry, T. Mitchell, Nicholas Glaze, and Santiago Segarra. "Principled simplicial neural networks for trajectory prediction." International Conference on Machine Learning. PMLR, 2021.

We thank the reviewer for their extensive review and are happy they find our paper clear, well-motivated, and unique from other works. We also agree that our evaluation including novel tasks is a significant contribution to the field.

Weakness 1, Question 2: Presentation on Figure 2

We discuss in the updated manuscript that the orientation can not encode edge direction as it is chosen arbitrarily. Models that are orientation equivariant for directed edges can not capture problem constraints that may arise in practice. We elaborate on this extensively in the new Appendix B.

Question 1: Non-arbitrary orientation of directed edges

This is an artifact of an earlier version of the paper and we removed it from our updated manuscript. The orientation assigned to directed edges plays no role for the boundary operators. From an implementation perspective, we overload orientation to encode edge direction. From a theoretical perspective, this is inconsequential and we apologize for the confusion.

Weakness 2: Model Comparison

We add two additional baselines:

• Following [1], we use the Laplacians of our work to create positional edge embeddings and feed them into a transformer (MagNet).
• We follow the suggestion of reviewer s2oj and consider a different mechanism to encode directed edges, following a node-level GNN [2] (DirGNN). Both are detailed in Appendix D.3 and thoroughly evaluated in Tables 4,5,9-14. EIGN outperforms both. Concerning MagNet [1], this approach does not adequately model equivariant signals and suffers from the same shortcomings as other fully orientation invariant baselines (MLP, LineGraph, ...).

Weakness 3, Question 3: Scalability

All Laplacians can be constructed without materializing boundary operators, as detailed in Table 7. The Laplacians are highly sparse and have as many non-zero entries as there are edge pairs that are connected through a shared node. Thus, EIGN has the same runtime complexity as all line-graph-based models. If the line graph has $F$ edges, the complexity of each layer is in $\mathcal{O}(F)$. We choose boundary operators in our paper as they theoretically motivate our approach and also provide some intuition.

Weakness 4: Intuition for Magnetic Laplacian

There are different approaches to distinguish directed and undirected edges. Using instead a real number to shift directed signals is less expressive: One could not distinguish the effect of a directed edge from a rescaled real input on an undirected edge. For the Magnetic Laplacian, since complex phase shifts are only induced by directed edges, the complex phase uniquely identifies directed edges. We use this concept as it has recently been shown to be very effective in encoding the topological structure of partially directed graphs on the node level [1].

Question 4: Invariant Boundary

Previous work on topological methods uses the equivariant boundary operator which is also sometimes referred to as a signed incidence matrix. The node Laplacian is constructed from this operator as well. To the best of our knowledge, the fully invariant boundary is not used in previous work. If the reviewer can point us to a paper that already uses this operator, we will adapt our manuscript accordingly.

Question 5: Phase Shift q

We provide an ablation regarding $q$ in Figure 7. Indeed, this hyperparameter needs to be chosen carefully as discussed in Appendix E. As correctly pointed out by the reviewer, too large values induce ambiguities or make the phase shift irrelevant altogether. We chose $q = 1/m$ to mitigate any issue from arising and justify this choice also empirically. Overall, both too small or too large values may result in worse model performance, while $1/m$ achieves satisfactory results over all datasets.

We want to thank the reviewer for the very detailed questions. If our updated manuscript and additional experiments still leave some concerns unanswered we are happy for any additional pointers.

References

[1] Geisler, Simon, et al. "Transformers meet directed graphs." International Conference on Machine Learning. PMLR, 2023.

[2] Rossi, Emanuele, et al. "Edge directionality improves learning on heterophilic graphs." Learning on Graphs Conference. PMLR, 2024.

Question 4: I think these works [1,2,3] use the notion of upper/lower adjacency, which is very similar to your $L_{inv}=B_{inv}^T B_{inv}$ with the diagonal set to 0. Another work [4] also constructs a similar notion under the name of down Laplacian matrix. You can take a look at their official repository, where they have few examples as well.

Given that all of the concerns are addressed, I will raise my score. Thank you very much for your thoughtful response.

[1] Bodnar et al., Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks, ICML'21.

[2] Bodnar et al., Weisfeiler and Lehman Go Cellular: CW Networks, NeurIPS'22.

[3] Truong and Chin, Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes, AAAI'24.

[4] Hajij et al., TopoX: A Suite of Python Packages for Machine Learning on Topological Domains.

Finally, to address the reviewer's examples:

1. Indeed, for the Magnetic Node Laplacians, the complex parts of signals can cancel out but remain largely distinguishable. Consider two very simple graphs of undirected and directed edges respectively: v1 - v2 - v3 and v1 -> v2 -> v3. In the case of only uniformative node features (constant 1), for the undirected case v2 will have $1 - \sqrt{2} - \sqrt{2}$. For the directed case, the v2 will have $1 - \sqrt{2}exp(i\pi q) - \sqrt{2}exp(-i\pi q) = 1 - 2\sqrt{2}cos(\pi q)$. Both are real, but not the same and, thus, distinguishable.
2. For a sequence of directed nodes v1 -> v2 -> ... -> vn, the information of v1 will be shifted by $nq\pi$ when reaching vn without reaching an MLP which may nullify the phase shift. However, we chose $q=1/m$ to bound the maximum path length which prevents this from happening. Again, since in practice learnable transformations are used, a model can learn to mitigate this cancellation. We also ablate the choice of $q$ in Figure 7.
3. For a sequence v1 -> v2 - v3 - ... - vn, the information of v1 that reaches vn does not encode at which point in the sequence a directed edge occured only if no learnable mappings are used. In practice, the model can simply learn to keep track of how many hops information "has travelled" and therefore distinguish the example graph from v1 - v2 -> v3 - ... - vn.

We thank the reviewer for their insightful comments, in particular for their alternative proposal to encode edge direction. We believe this comparison supports Magnetic Laplacians to encode directionality. We also hope that we were able to motivate why our paper is placed well in the current literature. If any concerns remain we would be very happy to discuss them further.

References

[1]: Roddenberry, T. Mitchell, and Santiago Segarra. "HodgeNet: Graph neural networks for edge data." 2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019.

[2]: Roddenberry, T. Mitchell, Nicholas Glaze, and Santiago Segarra. "Principled simplicial neural networks for trajectory prediction." International Conference on Machine Learning. PMLR, 2021.

[3]: Bodnar, Cristian, et al. "Weisfeiler and lehman go topological: Message passing simplicial networks." International Conference on Machine Learning. PMLR, 2021.

[4]: Schaub, Michael T., et al. "Signal processing on higher-order networks: Livin’on the edge... and beyond." Signal Processing 187 (2021): 108149.

[5]: Papamarkou, Theodore, et al. "Position: Topological Deep Learning is the New Frontier for Relational Learning." arXiv preprint arXiv:2402.08871 (2024).

[6]: Rossi, Emanuele, et al. "Edge directionality improves learning on heterophilic graphs." Learning on Graphs Conference. PMLR, 2024.

We thank the reviewer for their thorough and elaborate review and are happy that they, too, find the problem that our work studies to be important and well-addressed by our paper.

Relevance to ICLR and Impact

We strongly believe that this work is relevant to the community. Recently, there has been a growing interest in topological methods for various settings [1-5]. All of these assume equivariant signals for edges exclusively whilere there are basically no real-world applications which meet these strict assumptions. Consequently, this comes at the cost of greatly sacrificing model performance. While there are no established benchmarks for settings with equivariant and invariant signals, we believe that our paper bridges a relevant gap toward practical applications:

Real-world settings almost always come with both signal modalities. Domains include traffic and electrical engineering - as studied in our paper - but also hydraulics, water flow networks, electrical grids, pneumatics, engineering (statics, as buildings could be modelled as graphs) where there are yet no benchmarks available. In practically all aforementioned applications, orientation-invariant signals are crucial: Pipe diameter, material properties, etc. heavily influence the nature of the problem. Critically, none of the existing works (we highlight [1-4], but many more exist) can be effectively applied to any of these settings because of their restrictive assumptions - as is supported by our evaluation.

Magnetic Laplacians

We appreciate the concerns regarding the Magnetic Laplacians and the example-based justification by the reviewer. We think that investigating a propagation scheme according to [6] is a good suggestion and we thank them for the detailed description. Nevertheless, while we do not claim that the Magnetic Laplacian is as general as [6], neither the theoretical arguments are complete nor do we find that the proposed approach outperforms EIGN. We elaborate on the theoretical arguments in detail below but, in short, the argument neglects the existence of the additional learnable mappings. Due to the learnable mappings, it is hard to argue about phase shifts canceling out as the model can learn to mitigate this behavior. Without learnable mappings, [6] also can not distinguish the aggregation for directed and undirected edges through different mappings.

We included a comparison with [6] and detail this additional experiment (Appendix D.3, L. 1353). We construct three different boundary operators for each modality: One for undirected edges, one for incoming edges, and one for outgoing edges. Each of them is associated with a separate trainable weight matrix in the adopted version of EIGN. We add the resulting baseline (DirGNN) to all our evaluations (Tables 4,5,9-14) and conduct the same hyperparameter search as for all models.

Even though this baseline satisfies joint orientation equivariance and invariance, EIGN still outperforms. One reason may be the sparsity structure of the corresponding Laplacians: The first will only propagate information between undirected edges only, while the other two will only propagate information between edges that are incoming/outgoing regarding a shared node. This heavily limits the expressivity of these operators as information between directed and undirected edges can only be exchanged over multiple layers. Note that all three message-passing schemes combined recover only a subset of the adjacency structure of our Laplacians. In Table 7, only the third and the last two lines are represented by this baseline. Furthermore, this high sparsity limits the capability of models to predict orientation equivariant targets from only orientation invariant features which is done through inter-modality Laplacians (see L. 489). In simulation tasks, the baseline falls back to predicting mostly zeros as well.

Again, we do not want to make any claims as to which approach is "the most general" to represent directed edges. Many node-level models can not easily be transferred to the edge level without severe limitations. The Magnetic Laplacian is one framework that recently saw success and can be applied rather elegantly. In our updated manuscript (L. 528), we acknowledge different strategies that can also benefit from the theoretical groundwork regarding equivariance and invariance.

We also want to highlight that how directed edges are differentiated is only one part of our contribution: Formalizing and satisfying the joint orientation equivariance and invariance desiderata is the key to effectively addressing general edge-level problems.

We thank the reviewer for their review and are happy they like the presentation and our perspective on the importance of different signal modalities.

Novelty

The key contribution of our paper is jointly modeling both edge-level modalities. Since prior work [1-3] does not handle with and without orientation simultaneously, it is highly ineffective in practically all applications. While each modality has been discussed in prior work individually, to the best of our knowledge, no work even mentions this issue/limitation that arises in essentially all applications that contain orientation equivariant signals. Already discussing this issue is a valuable contribution to the field. This is also acknowledged by the other reviewers: "clever design" (s2oj), "work unique compared to prior works" (mjjQ), "non-trivial" (fGAT).

Combining the modalities is non-trivial: Previous notions of equivariance must be adapted and edge direction must be modeled in a principled way, which is also a novel contribution. Our empirical results strongly underline this point: Simply relying on existing work and combining both signal types performs significantly worse.

We conduct additional experiments to show that the success of EIGN is not due to its complexity but its inductive biases that come from our theoretical considerations:

• Two new baselines: A transformer with direction-aware positional encodings, and a GNN similar to EIGN that uses a different mechanism to encode edge direction. The transformer has more parameters than EIGN (see Table 17).
• Even though EIGN and the baselines were tuned over the same hyperparameter space, we ablate variants of the baselines with larger hidden dimensions to match EIGN's number of parameters.

Table 17 of our updated manuscript shows that EIGN still significantly outperforms. If the reviewer still views this experiment as insufficient evidence for the merits of our theoretical analysis and resulting model, we would be very happy for pointers to additional experiments we can conduct.

Theoretical Contribution

We first formalize edge-level problems from a theoretical perspective and propose suitable desiderata - joint orientation equivariance and invariance in the presence of directed and undirected edges. While already the formalization is a novel aspect that due to the negligence of prior work is an important contribution on its own, designing operators that meet the requirements is highly non-trivial. Especially, the interactions $L_{inv \rightarrow equi}$ and $L_{equi \rightarrow inv}$ have no comparable equivalent in the literature. Naturally, we design these operators with the clear goal of satisfying the novel equivariance and invariance conditions while being flexible enough to be used in future work. For example, we show that our Laplacians can be used in sophisticated message-passing schemes like Chebyshev polynomials, as requested by reviewer fGAT, which exemplifies the utility of our Laplacians beyond our work.

We want to stress that our theoretical contribution spans multiple aspects: We identify and formally address shortcomings of previous concepts (Definitions 4.1-4.2), and develop suitable operators to address them. Theorem 4.1. follows from carefully designing Laplcians that satisfy the new desiderata. Essentially, we split the otherwise lengthy proof into three parts, Lemmata 4.1-4.3., and Theorem 4.1. follows from their composition.

Q1: Number of Trainable Parameters

We report the number of parameters for all baselines and larger variants (see above) in Table 17. EIGN outperforms all baselines even when they have a similar number of parameters.

Q2: Sensitivity to Hyperparameters

We thank the reviewer for pointing this out. We provide two additional ablations regarding the hyperparameters of EIGN:

• Figure 7 shows the sensitivity to the phase shift q and discusses appropriate choices from a theoretical perspective.
• Table 16 shows EIGN's performance among the hyperparameter configuration space it was tuned: For a large range of values, EIGN outperforms all baselines.

Overall, we are very grateful for these questions. If we did not fully resolve the reviewer's concerns, we would greatly appreciate further clarification.

References

[1]: Roddenberry, T. Mitchell, and Santiago Segarra. "HodgeNet: Graph neural networks for edge data." 2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019.

[2]: Bandyopadhyay, S., K. Das, and M. N. Murty. "Line hypergraph convolution network: Applying graph convolution for hypergraphs. arXiv 2020." arXiv preprint arXiv:2002.03392 (2002).

[3]: Geisler, Simon, et al. "Transformers meet directed graphs." International Conference on Machine Learning. PMLR, 2023.