Improving Graph Neural Networks by Learning Continuous Edge Directions

Authors: Seong Ho Pahng, Sahand Hormoz
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Directed Graphs, Graph Laplacian, Continuous Edge Directions, Graph Ensemble Data

Abstract:
Graph Neural Networks (GNNs) traditionally employ a message-passing mechanism that resembles diffusion over undirected graphs, which often leads to homogenization of node features and reduced discriminative power in tasks such as node classification. Our key insight for addressing this limitation is to assign fuzzy edge directions---that can vary continuously from node $i$ pointing to node $j$ to vice versa---to the edges of a graph so that features can preferentially flow in one direction between nodes to enable long-range information transmission across the graph. We also introduce a novel complex-valued Laplacian for directed graphs with fuzzy edges where the real and imaginary parts represent information flow in opposite directions. Using this Laplacian, we propose a general framework, called Continuous Edge Direction (CoED) GNN, for learning on graphs with fuzzy edges and prove its expressivity limits using a generalization of the Weisfeiler-Leman (WL) graph isomorphism test for directed graphs with fuzzy edges. Our architecture aggregates neighbor features scaled by the learned edge directions and processes the aggregated messages from in-neighbors and out-neighbors separately alongside the self-features of the nodes. Since continuous edge directions are differentiable, they can be learned jointly with the GNN weights via gradient-based optimization. CoED GNN is particularly well-suited for graph ensemble data where the graph structure remains fixed but multiple realizations of node features are available, such as in gene regulatory networks, web connectivity graphs, and power grids. We demonstrate through extensive experiments on both synthetic and real graph ensemble datasets that learning continuous edge directions significantly improves performance both for undirected and directed graphs compared with existing methods.

Decision: accept (poster)
Reviewer scores: 6, 3, 5, 8

Reviews and discussion:
<thread>
creation date:
1729299437685

thread_type:
official_review

<thread_object>
creator: reviewer_xqhx

<content>
summary:
This paper proposes a novel framework for undirected and directed graphs called Continuous Edge Direction (CoED) GNN, based on the insight to assign fuzzy edge directions in a novel complex-valued Laplacian matrix. The paper includes empirical comparison to various GNNs on both synthetic and real-world datasets, and theoretically shows the expressive power of CoED.

strengths:
- The paper is generally well-written and well-motivated.
- The topics of expressive power, directed GNNs, and oversmoothing in GNNs are significant.
- The proposal of fuzzy edge directions is novel and effective.
- The statements are theoretically and empirically grounded.

weaknesses:
- No source code is provided.
- It would be better to show the runtime comparison explicitly, e.g. via a table, when comparing CoDE with MagNet etc.
- 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.
- In line 315, it is not clear where $\alpha$ should appear in the formula.
- Table 1 compares a CoED version without edge direction learning, how about with edge direction learning for node classification?
- (bonus) It would be better to show the ultimate directions (visualized) for some directed or undirected graphs to show more insights.

Reference:

[1] He, Y., Reinert, G., & Cucuringu, M. (2022, December). DIGRAC: digraph clustering based on flow imbalance. In Learning on Graphs Conference (pp. 21-1). PMLR.

questions:
- What is the runtime comparison explicitly, e.g. via a table, when comparing CoDE with MagNet etc.?
- 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. How are they compared empirically?
- In line 315, where should $\alpha$ appear in the formula?
- Table 1 compares a CoED version without edge direction learning, how about with edge direction learning for node classification?

Reference:

[1] He, Y., Reinert, G., & Cucuringu, M. (2022, December). DIGRAC: digraph clustering based on flow imbalance. In Learning on Graphs Conference (pp. 21-1). PMLR.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730465322387

thread_type:
official_review

<thread_object>
creator: reviewer_sbm9

<content>
summary:
This paper leverages "fuzzy edges" to improve the flow of information across a graph. CoED GNN learns directions (coefficients) for each edge. This is achieved through a complex-valued fuzzy Laplacian. Experiments on both synthetic and real-world datasets demonstrate CoED GNN's good performance in node classification and regression tasks, attributed to its ability to optimize long-range feature propagation.

strengths:
1. The fuzzy Laplacian enables CoED GNN to handle directional message passing, preserving the discriminative features over longer distances.
2. CoED GNN shows performance gains in diverse datasets, highlighting its adaptability to both synthetic and real-world applications.

weaknesses:
1. The edge directions are essentially edge weights. GAT can also learn edge weights, and it even leverages node features while doing so, unlike CoED GNN. Since GAT utilizes more information, it should perform better. At the very least, the weights learned by GAT should not be worse than those learned by CoED GNN. It is puzzling that GAT performs worse than CoED GNN in the experimental results provided by the authors. The authors should provide theoretical provements to show that CoED GNN is superior.
2. The authors should explain why CoED GNN can alleviate the problem of homogenization of information across the graph. Also, the authors should  provide experimental validations.

questions:
1. Could the authors provide theoretical analysis of the superiority of CoED GNN over GAT?
2. 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.
3. Could the authors provide explanation and experimental results to show that CoED GNN can alleviate the problem of homogenization of information across the graph?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730618777105

thread_type:
official_review

<thread_object>
creator: reviewer_qzrj

<content>
summary:
The paper presents a novel graph neural network architecture named Continuous Edge Direction (CoED) GNN, which improves upon traditional GNNs by introducing the concept of fuzzy edge directions. These directions allow for more effective feature propagation by varying continuously, enabling more controlled information flow between nodes. CoED GNN utilizes a complex-valued Laplacian that represents these fuzzy directions, where the real and imaginary parts correspond to opposite directions of information flow. The architecture is especially effective in graph ensemble settings, where the structure is static but node features vary, such as in gene regulatory networks and power grids.

strengths:
1. The paper is well-written, and the motivation of the model is reasonable.
2. The idea of learning optimal edge directions, and using phase angles to scale the direction-aware information flow is intuitive and interesting.
3. Theoretical Analysis appears to be rigorous and formally describes the expressive power of the proposed model

weaknesses:
1. Directed graph Laplacians have been extensively explored in previous studies, including seminal works like those by F. Chung [1] and on Hermitian Laplacian [2]. The introduction of the fuzzy graph Laplacian is a significant contribution of this work. However, while comparisons have been made with the magnetic Laplacian, it would be beneficial to extend these comparisons to include contemporary directed graph Laplacians to fully contextualize its advancements and differences.

2. 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, $\mathrm{Sigmoid}(f(u_i, u_j))$ and $1- \mathrm{Sigmoid}(f(u_i, u_j))$ , to scale the information flow? This approach might offer a simpler alternative to using complex values. Furthermore, related work such as superGAT [3] enhances GAT by identifying important neighbors, a concept that could potentially be extended to directed graphs. By incorporating the separate message-passing strategy of DirGNN—which independently considers in-edges and out-edges—we could apply superGAT to each direction separately. Subsequently, the two representations could be combined to produce the final node representation.

3. While the concept of learning optimal edge directions is intriguing, I find the experimental results presented in the paper unconvincing. Firstly, as illustrated in Table 1, the CoED model achieves the best results in only one out of the five datasets examined. Secondly, the paper omits experiments on several pertinent datasets commonly used in related works, notably those employed by DirGNN, which is frequently referenced in this study. Specifically, there are no results included for datasets such as SNAP-PATENTS, ROMAN-EMPIRE, and ARXIV-YEAR, despite DirGNN reporting significant findings on these along with various other baselines. Incorporating these datasets could enhance the persuasiveness of the results. Thirdly, I view SAGE as a specific instantiation of DirGNN, implying that the performance of DirGNN should be at least as good, if not better, than that of SAGE. To enhance DirGNN's performance, particularly on the Texas and Wisconsin datasets, I experimented with incorporating an MLP layer following the final layer of DirGNN. This modification has significantly improved its performance. Additionally, the Texas and Wisconsin datasets are relatively small, and the Chameleon and Squirrel datasets reportedly contain significant amounts of duplicate data [4]. Therefore, I believe these datasets may not be the most suitable for evaluating the model's performance. The authors might consider using the AM-Photo, AM-Computer, or Citeseer datasets, as employed in [5], to provide a more robust assessment.

   

[1] Laplacians and the Cheeger inequality for directed graphs. 

[2] Graph signal processing for directed graphs based on the hermitian laplacian.

[3] How to find your friendly neighborhood: Graph attention design with self-supervision. 

[4] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?

[5] Digraph Inception Convolutional Networks.

questions:
See Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730791788110

thread_type:
official_review

<thread_object>
creator: reviewer_b7qy

<content>
summary:
Traditional GNNs often suffer from feature oversmoothing due to their diffusion-like message-passing mechanism over undirected graphs. To address this, the authors propose the Continuous Edge Direction (CoED) GNN framework that assigns differentiable fuzzy edge directions to graph edges, allowing features to preferentially flow in one direction and introducing a complex-valued Laplacian for directed graphs with fuzzy edges.

strengths:
The paper is well-written and offers an intriguing evaluation on graph ensemble data, where the graph structure remains fixed but multiple realizations of node features and targets exist—an important task that demands attention. Additionally, the authors demonstrate that their method is more expressive than the Magnet Laplacian.

weaknesses:
1. The paper omits important baselines and related work, such as [3], which share similar concepts and should be included for a comprehensive comparison.
2. If the theorem is highlighted in the abstract and introduction, it should be mentioned explicitly in the main paper for consistency and emphasis.
3. 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.


References

[1] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. arXiv preprint arXiv:2302.11640.

[2] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.

[3]Finkelshtein, Ben, et al. "Cooperative graph neural networks." ICML 2024.

questions:
1. 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.
2. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732446007241

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We sincerely thank all the reviewers for their invaluable feedback and insightful suggestions. We are delighted that the reviewers found our paper “well-written” (**b7qy**, **QZRJ**, **xqhX**) and “well-motivated” (**QZRJ**, **xqhX**). The reviewers noted that our paper “offers an intriguing evaluation on graph ensemble data…an important task that demands attention” (**b7qy**) and that the “the topics of expressive power, directed GNNs, and oversmoothing in GNNs are significant” (**xqhX**). The reviewers also wrote that the idea of learning continuous edge directions is “intuitive and interesting” (**QZRJ**) and that the “proposal of fuzzy edge directions is novel and effective” (**xqhX**). The reviewers also highlighted our theoretical analysis, stating that it is “rigorous and formally describes the expressive power of the proposed model” (**QZRJ**) and that the “statements are theoretically and empirically grounded” (**xqhX**). Finally, the reviewers highlighted our empirical results as well, writing, “CoED GNN shows performance gains in diverse datasets, highlighting its adaptability to both synthetic and real-world applications” (**SbM9**).

We have significantly improved our manuscript based on the reviewers’ feedback and suggestions and have uploaded a revised version. The revisions are marked in blue. We address all the individual comments below, but the key improvements to the paper are summarized here:

- We have significantly increased the benchmarking of the node classification task in Table 1. We have included additional datasets, including Roman-Empire, Arxiv-Year, SNAP-patents, Citeseer, AM-Photo, AM-Computers, and filtered versions of Squirrel and Chameleon (**b7qy**, **QZRJ**) and have included additional baselines such as Cooperative GNN (**b7qy**), SAGE implementation of DirGNN, and additional forms of Laplacians for directed graphs (**QZRJ**).
- In Supplemental Section G, we describe how CoED GNN is different from GAT (**SbM9**), provide empirical evidence that CoED GNN outperforms a modified GAT architecture where edge weights are tuned to be consistent across incoming and outgoing messages (**QZRJ**), and provide empirical evidence that CoED GNN alleviates the problem of feature homogenization (**SbM9**).
- We have included a comprehensive run time analysis in Supplemental Section I (**b7qy**, **xqhX**).
- In Supplemental Section H, we provide a visualization of the learned continuous edge directions (**xqhX**).


We thank the reviewers again for their thoughtful consideration of our manuscript. We hope that the revised manuscript and our replies to the individual reviewers below have addressed all the concerns and questions. We look forward to answering any additional questions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733013008475

thread_type:
official_comment

<thread_object>
creator: area_chair_tlzq

<content>
title:
Reminder: Please Review Author Responses

comment:
Dear Reviewers,

As the discussion period is coming to a close, please take a moment to review the authors’ responses if you haven’t done so already. Even if you decide not to update your evaluation, kindly confirm that you have reviewed the responses and that they do not change your assessment.

Thank you for your time and effort!

Best regards, AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents a novel framework for graph neural networks (GNNs) that introduces fuzzy edge directions using a complex-valued Laplacian. This approach addresses key challenges in traditional GNNs, such as feature oversmoothing and limited expressiveness for directed graphs. The proposed CoED GNN enhances information flow between nodes by assigning differentiable edge directions, enabling controlled and adaptive message passing. This framework shows promise, particularly in scenarios involving static graph structures but varying node features, such as graph ensemble tasks. The authors provide a solid theoretical foundation for the expressiveness of their model and demonstrate its effectiveness on both synthetic and real-world datasets.

**Strengths**

Novelty: The introduction of fuzzy edge directions and a complex-valued Laplacian is innovative and provides a fresh perspective on improving GNN performance.

Empirical Evaluation: The evaluation includes both synthetic and real-world datasets, showcasing the model's adaptability across diverse scenarios.

Relevance to Graph Ensemble Tasks: The paper addresses graph ensemble tasks, a valuable yet underexplored application area in graph learning.

**Weaknesses**
While the reviewers raised concerns regarding the selection of datasets (especially commonly used heterophilic ones) and baseline comparisons, I find these points less critical given the primary application focus on graph ensemble tasks. However, I identified a few areas for improvement that could strengthen the final version:

Potential Overfitting and Task Limitations. Assigning a freely trainable parameter to each edge introduces the risk of overfitting, particularly in tasks outside the graph ensemble domain where the number of parameters might far exceed the available labels. This concern aligns with the authors' response to Reviewer b7qy, where masking nodes resulted in notable performance degradation. I suggest to emphasize the primary focus on graph ensemble tasks in the introduction/motivation and explicitly discuss the model's limitations on commonly used heterophilic graphs. This clarification would help future researchers better understand the scope of the approach.

Expressive Power and WL Test Comparisons. The proposed framework's expressive power comparisons with standard GNNs and magnetic Laplacians, framed through the lens of WL tests, require clarification. The framework's edge-specific parameters inherently break permutation symmetry, which the WL tests assume to preserve. I suggest to address this distinction explicitly in the final version and provide a more extensive comparison with magnetic Laplacians, particularly regarding expressive power. Additionally, several relevant works on magnetic Laplacians were not discussed. I recommend incorporating those fundamental references to provide a more comprehensive discussion:

1. MA Shubin. Discrete Magnetic Laplacian. Communications in Mathematical Physics, 1994.

2. Zhang et al. Magnet: A Neural Network for Directed Graphs. NeurIPS 2021.

3. Fanuel et al. Magnetic Eigenmaps for Community Detection in Directed Networks. Physical Review E, 2017.

4. Fanuel et al. Magnetic Eigenmaps for the Visualization of Directed Networks. Applied and Computational Harmonic Analysis, 2018.

5. Furutani et al. Graph Signal Processing for Directed Graphs Based on the Hermitian Laplacian. ECML PKDD 2019.

6. Geisler et al. Transformers Meet Directed Graphs. ICML 2023.

7. Huang et al. What Are Good Positional Encodings for Directed Graphs? arXiv 2024.


Despite the identified weaknesses, I believe the paper's strengths in novelty and relevance outweigh its limitations. The innovative contributions and targeted applications suggest a promising direction for future research, leading me to lean toward acceptance.