Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work focus on modeling directed graph in the spectral domain, which is not handled well by current spatial and spectral methods. The major contribution is using the Hermitian matrix to encode direction information.
main_review: 
This paper proposed a graph neural network for directed graphs. To encode direction, the Hermitian matrix is used as a Laplacian substitute in normal graph convolution.

### 1 Motivation 
- Directed graph is not well handled by the current graph neural network, and the author clearly presents the pros and cons of spectral and spatial methods, showing a new approach is needed.
- The example in the introduction shows a suitable potential to address the directionality. However, it is not clear if the Hermitian matrix can distinguish forward, backward, bi-direction, and no link.
- In the spatial method, what is the benefit to consider a neighbor even it is not connected through a directed link? 

### 2 Presentation- Overall, the presentation is good, but there exist several weaknesses. 
- Sections 2 and 3 present a workflow that is very similar to the most popular graph convolution. Obviously, it is better to focus on the proposed component.
- several related works are missing such as ICML 21 Directed Graph Embeddings in Pseudo-Riemannian Manifolds, and ICLR 20 DIMENet

### 3 Technical analysis- The paper proposes Hermitian matrices as a substitute for graph Laplacian.
- The major concern is that how the Hermitian matrix can distinguish directions. In the definition of phase matrix in line 103, how to tell (1) no link between u and v, from (2) bi-directional link between u and v ? Do they both equal to zero?
- The phase matrix is as large as the adjacency matrix, there may be an efficiency issue when the graph is large.

### 4 Experiment- The proposed method has been evaluated on both synthetic and real-world graph datasets.
- The results of link prediction well support the proposed method, but the performance on the node classification task is not significantly better than the baselines.
- Since there might be an efficiency issue, efficiency evaluation is expected.

### After rebuttal
The author well cleared my concerns and the score was updated.

limitations_and_societal_impact: - describe how the proposed method distinguishes forward, backward, bi-direction, and no link.
- discuss and study the efficiency problem: how much will the additional phase matrix and its multiplication take?
- present the implementation of multiplication between complex matrices
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to use magnetic Laplacian within GNNs to better capture the direction information. They introduce a spectral GNN based on this and show the performance on some node and link prediction tasks.
main_review: The paper is well-written and easy to follow. It also has a good justification of why their method works, and in practice they show that they are getting good results on some node and link prediction benchmarks. The idea is not new in graph signal processing community but it seems it is the first time that is being incorporated into GNNs as an inductive bias. There are three main concerns/questions that I have:

1- Sparse representation of graphs is very important as many real-world graph problems deal with huge graphs. However it seems that the exponential of phase matrix is dense because even if there is no connection between two nodes the exp(phase) will be 1. Can you comment on this?

2 - One simple baseline for directed graphs can be decoupling the incoming edges from outgoing edges for each node, learn two disentangled representations, and then aggregate them. Any thoughts how this simple baseline would perform compared to  your model? Also, approaches such as Graph diffusion convolution (GDC) [1], or Graphormer [2] should also be able to capture direction information using diffusion and structural self-attention, respectively. I wonder how such models would perform compared to yours.

3- Also I have two concerns regarding the performance and scalability of the proposed models. Especifically, it seems that all your evaluations are performed on transductive taks and it is not clear how your method would work on inductive tasks. Moreover, the benchmarks that you have chosen are fairly small with maximum of  3,312 nodes for node prediction and 11,701 nodes for link prediction tasks. I recommend to evaluate on more realistic directed benchmarks such as ogbn-papers100M, ogbn-arxiv, ogbn-mag, ogbl-citation2, ogbl-wikikg2. (Thanks for explicitly mentioning this in limitations section: "is not scalable to large graphs in 
its current form (although this may be addressed in future work)."

4- Finally, I couldn't find information about how you would treat edge features in your framework if available. 


[1] https://proceedings.neurips.cc/paper/2019/hash/23c894276a2c5a16470e6a31f4618d73-Abstract.html

[2] https://arxiv.org/abs/2106.05234

After receiving the author responses and also reading the reviews of the other reviewers, I decided to increase the score. However, I still think showing results for inductive tasks and tasks with edge features can make the paper stronger.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the design of graph neural networks for directed graphs. In particular, it uses the magnetic Laplacian, a complex-valued Hermitian matrix that encodes edge directions via a phase parameter, as a matrix from which convolutional filters are formed. By defining this matrix, the authors demonstrate how it can be used in place of more traditional Laplacians in a few existing graph neural network architectures. This approach is then empirically verified on synthetic and real datasets, where the utility of the the magnetic Laplacian for encoding edge directionality is demonstrated.
main_review: I will begin by discussing the strengths of this paper, then move on to the weaknesses, followed by some brief comments.

**Strengths**

1. The presentation of this paper is quite nice. It is simple, well-structured, and readable. The magnetic Laplacian is defined and explained clearly, and the convolutional networks are well-explained in the context of the existing literature. The experiments are also described well. This paper was very easy to read and understand.

2. The "MagNet" architecture is not overly dependent on a particular convolutional structure, as indicated by the authors explaining how to use the magnetic Laplacian in multiple contexts. This makes the proposed approach appealing, as it is basically a drop-in change that is appropriate for handling directed graphs.

3. The empirical validation is quite convincing. The authors were quite thorough in describing their experiments, and designed the synthetic datasets carefully to demonstrate how MagNet can fully leverage the directed information while approaches based on symmetrized matrices can't. Moreover, the results on real data, including common benchmarks, are strong. Another strength of the proposed approach is in the selection of the parameter $q$ via cross-validation. Since $q$ reflects the utility of the directional information in the dataset, it is useful itself as an output of the model for interpretation of the dataset's properties, e.g., the importance of directionality in the Cora/CiteSeer networks for link prediction, but not for classification. They also compare to a good spread of other neural approaches.

4. The magnetic Laplacian is a novel addition in this context, which I have not seen before in a paper on graph neural networks.

**Weaknesses**

1. Some reasonable approaches were not addressed in the experiments. In the introduction, it is noted that the magnetic Laplacian has been used recently for community detection and clustering. On at least some of the experiments, it seems like it would be appropriate to apply these simple approaches to compare to, especially given that the node data on the synthetic dataset is randomly sampled.

2. The description of how $q$ was selected is vague. I can only guess how it was done: this should be described in more detail, perhaps in the supplement.

3. There are no comments on complexity. Although it is mentioned that this approach is not scalable in its current form in the Limitations section, there is no discussion on this in the body of the paper. I would have liked to see a better explanation of this, perhaps via a simple description of the computational complexity. This comment also holds for the selection of the $q$ parameter as mentioned above.

4. The neural architecture itself is not particularly novel, as it is directly adapted from previous papers. However, I do not view this as much of a weakness, since the point of this paper is the use of the magnetic Laplacian as a way to encode the directed structure, as well as the tuning of the parameter $q$.

**Comments**

1. Overall thoughts: this paper does not advance the field in terms of graph neural network architectures, their training, or theoretical underpinnings. However, it does introduce an operator, namely the magnetic Laplacian, that is likely unfamiliar to many in the community. By combining graph neural networks with proper parameter selection for the magnetic Laplacian, this approach proves effective in handling data on directed graphs. For this reason, I recommend this paper for acceptance.

2. This is not an important question to address, but perhaps it could improve the presentation. A common way to describe the graph Laplacian for undirected graphs is as the product $L=BB^\top$, where $B$ is the signed incidence matrix. Given that the magnetic Laplacian is Hermitian, it admits a similar factorization for some matrix other than $B$. Does it admit a factorization in terms of a modified incidence matrix?

**Editorial** (no influence on decision)

1. Line 42, "informatio" is misspelled

2. Lines 104-105, "component-wise" and "componentwise" are not consistent

3. Lines 58,189, and elsewhere, "link-prediction" and "link prediction" are not consistent

4. The plot in Figure 2 isn't very attractive. Perhaps the legend should be separated from all the plots to emphasize that it is shared, as well as to make it more readable.

5. Some of the citations do not look very good. Please take another pass on these, with a particular focus on capitalization. Some problematic citations I noticed were [7],[9],[10],[15],[18],[23],[25],[28],[29]. There are also inconsistencies on venue citation, for instance between [1],[20], and [36], or in capitalization between [10] and [11]. I would suggest using the `@string` macro in BibTeX to ensure consistent venue naming, e.g.,

```
@string{iclr={International Conference on Learning Representations}}

@article{
title={Absurdly Deep Convolutional Neural Networks},
author={A. Authors},
journal=iclr,
}
```

**After Rebuttal**

Thanks to the authors for considering my comments as well as the comments of the other authors. I am not sure if the paper is in the top 50% of accepted papers, but I still believe that it should be accepted. Thus, I am keeping my score the same. The authors have done a good job with this work.
limitations_and_societal_impact: The societal impact is not notable compared to other graph neural network literature. Limitations on scalability are mentioned at the end, but should be discussed more in the body of the paper, as mentioned in the main review.
review_title: null

Meta-review: The paper proposes a new GNN for directed graphs using magnetic Laplacian. Specifically, the authors use a complex operator encoding edge direction via phase. This is an interesting approach, which was appreciated by the reviewers. The authors provided detailed responses that addressed the reviewers' comments in a satisfactory manner. The AC recommends acceptance.  

Decision: Accept (Poster)