Improving Graph Neural Networks by Learning Continuous Edge Directions

Response

We thank the reviewer for the invaluable feedback and suggestions. We are delighted that the reviewer found our paper well-written and well-motivated, and our topics significant. We are also glad that the reviewer found our proposal of fuzzy edge directions novel and effective and our statements grounded both theoretically and empirically. We address in detail the weaknesses and the questions raised by the reviewer. > No source code is provided. We thank the reviewer for raising this point. We now include the source code for our analysis: https://anonymous.4open.science/r/coed-gnn-0347 > What is the runtime comparison explicitly, e.g. via a table, when comparing CoED with MagNet etc.? The reviewer raises an important point. In the revised manuscript in Supplementary Section I, we provide extensive runtime comparison between CoED and the baseline models. Since the only additional source of computes in CoED are the in- and out- fuzzy propagation matrices (Eq. 2 in the manuscript), CoED shows comparable runtime to DirGNN. Notably, CoED achieves much faster forward and backward pass time compared to Magnet or GAT even when we perform layerwise edge directions learning—where we compute propagation matrices from different phase angles at each layer. > The paper uses the idea of separate aggregation of in- and out- information in addition to self. [1] does something similar and is based on flow imbalance in its objective. It would be better to add some discussion and comparison in experiments. We thank the reviewer for bringing this relevant reference to our attention. This paper uses the concept of flow imbalance to assign nodes of directed graphs to clusters. While we cannot do a direct empirical comparison to this node clustering method, as our learning tasks are either node classification or regression, we believe our continuous edge direction learning can provide a more finely-tuned imbalance profile for this algorithm to pick up on. Clustering directed graphs is an important area of research, and we are interested in exploring the application of our continuous edge direction learning in this direction. In the revised manuscript, we now include a discussion of reference [1] and how it conceptually relates to our work. > In line 315, where should α appear in the formula? We have clarified this in the revised manuscript. > Table 1 compares a CoED version without edge direction learning, how about with edge direction learning for node classification? The reviewer raises an important point. In Table 1, we benchmark performance of node classification against baseline models without learning the edge directions. First, this is done because our main goal for Table 1 is to directly compare our proposed fuzzy Laplacian, and the corresponding architecture, to alternative forms of Laplacian, such as the magnetic Laplacian. Second, because CoED learns continuous edge directions by directly optimizing for the learning task and without relying on node features, it requires access to all of the nodes of the graph during the training. Masking a subset of nodes as test nodes would mean that the directions of the edges connected to the test nodes will not be learned during training. In fact, the directions of those edges will be tuned to improve the performance of the training nodes at the expense of the test nodes, resulting in diminished performance. Therefore, CoED is best suited for graph ensemble data (for example, the synthetic and real-world data sets used in our paper) where the multiple realization of node features and their corresponding target values exist for the same graph and thus we do not need to mask the part of a graph during the training. In the revised manuscript, we have added additional text to make this point abundantly clear. > (bonus) It would be better to show the ultimate directions (visualized) for some directed or undirected graphs to show more insights. We thank the reviewer for this helpful suggestion. We have included a visualization of the learned continuous edge directions for the Perturb-seq data (an originally undirected graph, where nodes are genes, and edges are gene-gene interactions) in the revised manuscript in the newly added Section H of the supplement. Again, we thank the reviewer for the tremendously helpful comments and feedback. We hope that we have addressed all remaining concerns of the reviewer. We are of course happy to answer any further questions.

Response part 1

We thank the reviewer for the helpful feedback and suggestions. We are glad that the reviewer found the proposed fuzzy Laplacian for long-range directional message-passing to be a strength of our paper and highlighted the observed performance gains across diverse data sets. We now address the questions and weaknesses raised by the reviewer. > Could the authors provide theoretical analysis of the superiority of CoED GNN over GAT? The reviewer raises an important point. It is indeed true that GAT can also learn edge weights. However, GAT does so solely based on the features of the nodes spanned by the edge. Our proposed method learns the continuous edge directions to optimize the learning task directly and can learn edge directions even when the node features are not informative. This is why, CoED outperforms GAT in our synthetic data sets and the real data sets. Importantly, to learn edge directions independently from the node features, we need data sets of graph ensembles where multiple realizations of the nodes (and their corresponding regression target values) are provided on the same graph during training. To make this point abundantly clear, in the revised manuscript, we have included a new Supplementary Section (Appendix G). There, we propose a toy model of a linear graph that forms a closed loop. The input node features are random (and therefore uninformative). The output node features are the same as the input features but shifted by one node across the graph in the clockwise direction. GAT cannot learn the optimal direction of information transmission because the features contain no information about this direction. CoED on the other hand directly learns the edge directions to optimize the regression task independent of the node features and can therefore correctly predict the output values. We hope this example clarifies why CoED GNN is superior to GAT for certain classes of problems. Our evaluation of real-world graph ensemble datasets demonstrate that this is true for many important real-world problems. > In Equation (1), why $(L_F){ij}=\text{exp}(i\theta{ij})$ ?Is the first i the imaginary unit? If so, the authors should use different letter to denote the $i$th node. The reviewer is absolutely correct. The first i in the exponent is meant to denote an imaginary unit. We have changed them to the upright style character $\mathrm{i}$ in the revised manuscript.

Response part 2

> Could the authors provide explanation and experimental results to show that CoED GNN can alleviate the problem of homogenization of information across the graph? We thank the reviewer for this important question. In the revised manuscript, in Supplementary Section G, we provide an explanation and empirical evidence why CoED GNN alleviates the homogenization (or oversmoothing problem) on graphs. When a graph is undirected, aggregating information across the neighbors of a node repeatedly is akin to diffusion of information across the nodes. This is because when node i sends information to node j, node j also sends information to node i. Diffusion prohibits long-range information transmission across the graph and results in a rapid convergence of the node features to the averaged feature across all the nodes. In contrast, directed edges allow information to flow instead of diffuse. This is because node i can now send information to node j without receiving information in return (if there is a directed edge from node i to node j). This flow of information allows long-range information transmission without excessive averaging across nodes alleviating both the oversmoothing problem and improving the performance in tasks that require long-range information transmission. To demonstrate this experimentally, in Figure G.3 of the revised manuscript, we plot the performance of CoED as a function of model depth, which corresponds to the number of hops used to transmit information, for the synthetic dataset of the triangular lattice with node features obtained from CIFAR images. Compared to the baseline of GAT, CoED shows continued improvement in performance with increasing model depth, indicating that oversmoothing has been alleviated. To show this even more directly, we also compute the Dirichlet energy of the node features on this graph and plot it as a function of number of times the graph Laplacian is applied to the node features (again equivalent to the number of times information is transmitted by hopping across neighboring nodes). When the undirected graph Laplacian is used, the node features rapidly converge to a fixed value and exhibit low Dirichlet energies. In contrast, when the directed graph Laplacian is used, computed from the learned edge directions, the Dirichlet energy reduces less rapidly, indicating that homogenization is occurring more slowly. We thank the reviewer again for extremely helpful feedback and suggestions. We are of course happy to answer any additional questions. If there are no further questions, we kindly ask the reviewer to consider re-evaluating our manuscript under a new light and potentially upgrading the score if appropriate.

Follow-up on Revised Manuscript for Discussion Period

Dear Reviewer SbM9, As the ICLR discussion period draws to a close today, we wanted to thank you once again for your thoughtful feedback, which has been invaluable in refining our work. We have carefully considered and addressed all your comments in the revised version of our paper. We believe that the updated manuscript (especially the newly added Supplemental Section G) effectively addresses the points you raised and significantly improves the clarity and rigor of our work. We kindly ask you to review the revised version if time permits. Your insights and further engagement would be greatly appreciated as the discussion period concludes. Thank you again for your time and expertise. Best regards, The authors

Response part 1

We thank the reviewer for extremely helpful feedback and suggestions. We are delighted that the reviewer found the paper well-written, the model reasonable, and the idea of using continuous edge directions for enhancing information flow on graphs intuitive and interesting. We are also glad that the reviewer found our theoretical analysis used to formally describe the expressivity of our model to be rigorous. We now address the weaknesses raised by the reviewer in detail. > Directed graph Laplacians have been extensively explored in previous studies, [...] it would be beneficial to extend these comparisons to include contemporary directed graph Laplacians to fully contextualize its advancements and differences. We agree with the important point raised by the reviewer. In the revised manuscript, we have extended our comparisons to other types of Laplacians for directed graphs besides the magnetic Laplacian. The Hermitian Laplacian [2] is indeed the magnetic Laplacian. However, the Laplacian introduced by Chung [1], where a Hermitian Laplacian is constructed from the transition matrix of the graph, is an alternative Laplacian for directed graphs. To our knowledge, the Chung Laplacian and the magnetic Laplacian are the only other Laplacians proposed for directed graphs. We now compare the performance of the Chung Laplacian when applied to node classification (revised Table 1) to that of the fuzzy Laplacian. In addition, we have also included a comparison of the Chung Laplacian to the fuzzy Laplacian when applied to our synthetic data sets (revised Table 2). In all cases, we observe an improved performance when the fuzzy Laplacian is used. > From my perspective, employing phase angles to dictate continuous edge directions is designed to adaptively modulate the weights from in-neighbors and out-neighbors. However, could we alternatively employ a shared learnable function f, , such as, Sigmoid(f(ui,uj)) and 1−Sigmoid(f(ui,uj)), to scale the information flow? [...] Furthermore, related work such as superGAT [3] enhances GAT by identifying important neighbors, a concept that could potentially be extended to directed graphs. [...] The reviewer raises an interesting point. It is possible to learn edge weights based on the features of the two nodes connected by an edge, for example in the form of Sigmoid(f(ui,uj)), and then impose that outgoing and incoming messages are consistent by requiring that the edge weight in the opposite direction is given by 1−Sigmoid(f(ui,uj)). However, such edge weights, although consistent with the edge directions, are still functions of the features of the nodes. The key distinction of our method is that the continuous edge directions are learned directly through optimization of the learning task over the entire graph and not as a function of node features. Our synthetic data set of the triangular lattice graph with random node features (Figure 3 and Table 2), where node features are completely uninformative, illustrates this most clearly. To demonstrate this empirically, we implemented the reviewer's suggestion and constructed an attention-like model as proposed by the reviewer: edge weights were computed from the node features with the constraint that the learned edge weights in opposite directions sum to one. We then applied this model to the new synthetic data of the triangular lattice graph with node features obtained from CIFAR images. In this dataset, the features of the two nodes connected by an edge are mostly identical and therefore it would be difficult to learn informative edge-weights from these features. For example, the pair of node features, {$(u_i, u_j) | j \in \mathcal{N}(i) $}, and the resulting edge weights {$f(ui, uj) | j \in \mathcal{N}(i) $} may be all identical. Therefore, the model with the explicit correspondence between i→j and i←j directions, which we call “self-consistent (SC)-GAT”, could still suffer if features are uninformative. We added the discussion of CoED vs. GAT in the supplemental section G of the revised manuscript, and empirically demonstrate that CoED outperforms SC-GAT in Figure G.3. CoED outperforms this model because it can learn edge directions without relying on the node features.

Response part 2

> Furthermore, related work such as superGAT [3] enhances GAT by identifying important neighbors, a concept that could potentially be extended to directed graphs. [...] The idea of extending the superGAT [3] framework to directed graphs is interesting and insightful. superGAT extends GAT by predicting whether an edge should exist between two nodes based on the features of those nodes. As described above, this approach is still conceptually different from our method and more limited because it relies on the edge features to modulate the attention between two neighboring nodes. Although extending superGAT to directed graphs is beyond the scope of our manuscript, to test this idea empirically, we applied a similar approach called [1] Cooperative GNN (or Co-GNN) to our synthetic data set where node features are not informative for learning the edge directions. Similar to superGAT that predicts whether an edge should exist between two nodes based on their features, Co-GNN uses the features of a node and that of its neighbors to classify a node as one that either broadcasts to its neighbors (which amounts to making outgoing edges), listens to its neighbors (incoming edges), does both, or neither. As shown in Figure G.3, CoED outperforms Co-GNN because it can learn the optimal edge directions without relying on node features. > While the concept of learning optimal edge directions is intriguing, I find the experimental results presented in the paper unconvincing. [...]. The authors might consider using the AM-Photo, AM-Computer, or Citeseer datasets, as employed in [5], to provide a more robust assessment. We thank the reviewer for excellent suggestions on applying CoED to larger and more representative data sets. In the revised manuscript, we have done exactly as the reviewer suggested. 1) We have evaluated CoED’s performance on Roman-Empire, SNAP-patents, and Arxiv-Year. As shown in revised Table 1, CoED outperforms the other baseline models in these datasets . 2) As suggested by the reviewer, we have incorporated the SAGE instantiation of DirGNN so that DirGNN can either be run with GCN-, GAT-, or SAGE- convolution depending on which performs better. In the revised Table 1, DirSageConv was chosen from hyperparameter search for Texas, Wisconsin, Citeseer, AM-Photo, and AM-Computers. 3) In the revised manuscript, we now use the filtered versions of Chameleon and Squirrel data sets to address the reviewer’s concern. CoED’s ranking compared with the other baselines did not change. 4) Finally, we now also include benchmarking on the AM-Photo, AM-Computer, and Citeseer datasets as suggested by the reviewer. CoED is again one of the top models on these datasets. We hope these additional experiments address the reviewer’s concern with benchmarking for the node classification task. We would also like to emphasize that the main result of our paper is not that CoED outperforms existing models in node classification tasks. Rather, we include Table 1 to provide empirical evidence that our proposed architecture using the fuzzy Laplacian can outperform Magnet (which uses the Hermitian Laplacian) and the newly added architecture based on the Chung Laplacian. We have revised the text to reflect this point more clearly. We hope that we have addressed all the concerns raised by the reviewer. We are happy to answer any additional questions. If there are no further questions, we kindly ask the reviewer to consider re-evaluating our paper in a new light and potentially consider upgrading their score. [1] Finkelshtein, Ben, et al. "Cooperative graph neural networks." ICML 2024.

Follow-up on Revised Manuscript for Discussion Period

Dear Reviewer QZRJ, As the discussion period for ICLR concludes today, we wanted to reach out and thank you again for your valuable feedback, which has been instrumental in refining our work. We have carefully addressed all your comments and incorporated the suggested changes into the revised version of our paper. We believe the updated manuscript thoroughly resolves the concerns you raised and enhances the clarity and impact of our work (see in particular, the revised Table 1, and the newly added Supplemental Section G). We would greatly appreciate it if you could take a moment to review the revisions. Your expertise and further input would be invaluable as the review process comes to a close. Thank you again for your thoughtful engagement. Best regards, The authors

Response part 1

We thank the reviewer for tremendously helpful feedback and suggestions. We are pleased that the reviewer found the paper well-written, the evaluation on graph ensemble data intriguing, and highlighted our expressivity comparison to magnetic Laplacian. Below we address the weaknesses and questions raised by the reviewer. > The paper omits important baselines and related work, such as [3], which share similar concepts and should be included for a comprehensive comparison. We thank the reviewer for this suggestion. In the revised manuscript, we have included multiple additional baselines, including reference [3] (Cooperative GNNs, or Co-GNNs) suggested by the reviewer. We include Co-GNN as a baseline both in the node classification task, where edge directions are not learned (revised Table 1), and also apply it to our synthetic triangular lattice data (newly added Supplemental Section G). In both node classification and our synthetic data, CoED outperforms Co-GNNs. This is because although Co-GNN assigns distinct roles to each node (such as listen, broadcast, do both, or neither), it does so relying on the features of a node and its neighbors. CoED, in contrast, learns the continuous edge directions by directly optimizing for the learning task and can therefore learn optimal edge directions even when the node features are uninformative. This is particularly apparent in the new synthetic triangular lattice problem where node features are created from the RGB pixel values of images in the CIFAR dataset. Here, most neighbors have identical features which are completely uninformative for learning edge directions. Lastly, the continuous edge directions allow for more complex information transmission across graphs than assigning one of four possible roles to each node. > If the theorem is highlighted in the abstract and introduction, it should be mentioned explicitly in the main paper for consistency and emphasis. We thank the reviewer for this suggestion. In the revised manuscript, we explicitly mention the theorem in the main text. > The evaluation on node classification tasks is unconvincing: Only one homophilous dataset is included in the study. The Chameleon and Squirrel datasets used are known to be problematic [1], and it is advisable to use filtered versions for more reliable results. The heterophilous datasets used for evaluation are all quite small, and the results do not approach the current state-of-the-art. To more robustly validate the claims, experiments on larger-scale heterophilous datasets [1][2] are necessary. We agree with the reviewer on all of these points and have addressed them in the revised manuscript. 1) We now have included Citeseer, AM-Photo, AM-Computers as additional homophilic data sets in Table 1. 2) We have replaced the Chameleon and Squirrel datasets with the filtered versions as suggested by the reviewer in the revised table. The conclusion that CoED performs well on these data sets relative to the baselines still holds. 3) In the revision, we have included multiple larger-scale heterophilic datasets. These are Roman-Empire, Arxiv-Year, and SNAP-Patents. Importantly, CoED consistently ranks as one of the best performing models on these data sets, highlighting the benefits of our proposed architecture and the fuzzy Laplacian for node classification on heterophilic graphs.

Response part 2

> What is the runtime of the proposed methods, and how does it compare to the baselines? Providing a detailed runtime analysis would enhance the evaluation. In the revised manuscript, we provide a table of runtimes for CoED and representative baseline models in Supplementary Section I. The only additional computes in CoED are due to the in- and out- fuzzy propagation matrices (Eq. 2 in our paper) during the forward pass. Except for layerwise edge direction learning, CoED needs to compute them only once so it adds minimal overhead compared to DirGCN which shares the similar AGGREGATE and UPDATE steps. Even when learning edge directions at each layer separately, CoED achieves faster forward and backward pass times compared to other baseline models like GAT or Magnet. > For the node classification task, how does the performance change if the edge direction is made learnable? Prior work, such as [3], suggests that it will likely improve performance. We thank the reviewer for raising an important point. Because CoED does not learn the edge directions from the features of the nodes (as is done by GAT or Co-GNN), it needs access to all of the nodes of the graph during training. If a subset of the nodes are set aside for testing then the directions of the edges incident to the test nodes will not be learned and in fact will be tuned to optimize classification of the training nodes at the expense of the test nodes. Empirically, we observe a decrease in performance when a subset of nodes are masked as test nodes and edge directions are learned (as in the node classification task in Table 1). Our method is most useful when applied to Graph ensemble data where the graph structure is held constant across multiple realizations of node features and corresponding target values. In this setting, we split the realizations of features and targets. Therefore we can use the entire nodes to learn the edge directions without the need for masking a subset of nodes as test nodes. As shown in Table 2 and Table 3 of the manuscript, learning edge directions in graph ensemble data significantly improves performance. We have added text to the revised manuscript to make this point more clear. Again, we thank the reviewer for their invaluable feedback and insightful comments. We hope that our answers above address the reviewer’s concerns. We are of course more than happy to answer any additional questions. If there are no further questions, we kindly ask the reviewer to consider reevaluating our work from a fresh perspective and potentially upgrading their score.