Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work considers the limitation of graph neural networks that cannot consider the directions. It proposed directional graph networks to overcome this limitation. The concerns for this work are as below:

1.	I do not quite understand the motivation of this work. In section 2.1, the authors explain that a big limitation of current GNN methods is that they cannot process directions. This is not case. In most message passing GNNs, they can rely on the adjacency matrix during message passing process. If a specific direction is desired, it is feasible to modify or design the adjacency matrix accordingly. This fact is also true on the grid graphs. Thus, I don’t quite buy the motivation of this work. The authors need to clarify this motivation and illustrate why the direction limitation is not resolvable by manipulating the adjacency matrix. 
2.	The data augmentation is proposed in Section 2.7. The authors claimed that the advantage of the proposed method is that it does not influence the data but applied on kernels. However, there may be some issues here for changing kernels. In this work, the kernel is acting as a kind of message passing directions on the graph. The message passing patterns are an important part of the graph. If the patterns or connections are changed, the graph will change consequently. From this perspective, if the proposed method changes the kernel and modify graph connections, this cannot be considered as a strict data augmentation since the modified graphs can have totally different properties as the original ones. Thus, I would like the authors to provide a clarification on this point.
3.	The number of datasets used in the experimental parts is quite limited. These datasets are not commonly used in the community. The authors may want to clarify this and add more datasets for comprehensive evaluations. 
review_title: Review for Directional Graph Networks

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper provides a theoretical framework that allows to directional convolutional kernels in any graph, e.g., generalize CNNs on an n-dimensional grid. In the framework, gradients of the eigenvectors of the graph Laplacian are used to define “directions” on the graph.

The proposed method is well-motivated and seems to be theoretically justified (I did not fully understand the details and check the proofs). My main concerns are:

1.	The theoretical development is difficult to follow. The proposed method is not clearly described. It is hard for readers to find in the paper what are the steps of the proposed algorithm and understand how it works. It would be better to describe the algorithm step by step.

2.	I have some doubts about the practical value of the proposed method because it requires eigen-decomposition of the Laplacian matrices. Though the authors provide complexity analysis in the appendices, it would be more informative to provide a runtime comparison with SOTA methods such as the vanilla GCN. 

================ Post Rebuttal =============================================================

Thank the authors for the updates.

In the latest version, the algorithm flow is clearly stated in Figure 1, and now I can understand how the algorithm works. The authors also reported additional results on running time in the latest version, which are informative. 

Here is what I think after reading the paper again.

1.	This paper proposes a novel idea. Defining directions on graphs is not a well-addressed problem in current GNN models, and using the gradients of the low-frequency eigenvectors of the Laplacian to define directions seems novel and interesting to me.  

2.	The insight and analysis are not clear. Section 2.4 is still difficult to follow after the updates. More importantly, I am not sure about the correctness of the theorems and corollaries. 

       The K-walk distance is supposed to reflect the difficulty of passing information between two nodes, and a larger distance means more difficulty. In the paper the K-walk distance is defined as the average number of times that a K-step random walk from one node to hit another (formal definition given in Page 18), which really puzzles me, because frequent visits indicate ease of message passing. Did the authors confuse hitting probabilities with hitting times? 


review_title: The algorithm is not clearly described and may not be scalable.

final_score: rating: 7: Good paper, accept
review_content: Summary:
The authors propose a convolution as a message passing of node features over edges where messages are aggregated weighted by a "direction" edge field. Furthermore, the authors propose to use the gradients of Laplace eigenfunctions as direction fields. Presumably, the aggregation is done with different direction fields derived from the Laplace eigenfunctions with lowest eigenvalues, which are then linearly combined with learnable parameters. Doing so allows their graph network to behave more like a conventional CNN, in which the kernels have different parameters for signals from different directions. The authors achieve good results on several benchmarks. Furthermore, the authors prove that their method reduces to a conventional CNN on a rectangular grid and have theoretical results that suggest that their method suffers less from the "over-smoothing" and "over-squashing" problems.

Strong points:
The proposal is highly novel. It is a simple and scalable modification to conventional graph nets that shows a strong performance increase in the benchmarks. The paper is mostly clearly written. The theoretical analyses contribute to the understanding of the work.

Weak points:
- It is unclear how parameters are used in their model. I presume that they apply the directional derivative with several edge fields and then linearly combine with learnable parameters, but this is not stated explicitly. Furthermore, for different graphs with different spectra, how are the parameter shared? Simply by their order?
- As the authors note at the end of Sec 2.4, the Laplace eigenvectors can not uniquely be identified, only the eigenspace of a certain eigenvalue. For example, this means that when Lanczos’ method is applied to two isomorphic graphs in different orderings, different eigenvectors can be returned. The authors propose to overcome the arbitrary-ness of the sign by taking the absolute value after each dictional derivative. Still, when an eigenvector is used from a degenerate eigenspace, the method appears not equivariant to node re-orderings. The authors state that in their datasets, the first non-trivial eigenvector is always non-degenerate, but the experiments also use higher eigenvectors. Are these also non-degenerate? Or is that model not equivariant? This also means that when using the proposed method on a square grid, which the authors do on CIFAR10, the method is not equivariant to node re-orderings.

Recommendation:
I recommend to accept this paper, as it proposes a simple to use method to build more powerful graph nets. In spite of my concerns about equivariance, it appears to perform well in relevant benchmarks.

Opportunities for improvement:
- The paper could be improved by more directly addressing the concerns about equivariance. Are some of the proposed models indeed not equivariant on certain graphs? Do we care that the model is not always equivariant? 
- It would be interesting to see if the authors could prove that the resulting model is more expressive than a conventional graph networks, for example by comparing theoretically or experimentally to the expressiveness of Weisfeiler-Lehman tests.

### Post rebuttal
My previous rating still applies. If accepted, I encourage the authors to more clearly state in the final version that their method is not applicable (without additional - and arguably inelegant - random augmentation) to graphs with degenerate eigenvalues and in particular symmetric graphs. The necessity of taking the absolute value to ensure invariance to the sign of the eigenvector should also be more clearly stated.
I share reviewer #1's concerns about corollaries 2.5 and 2.6. These should be clarified or removed from the final version. Nevertheless, I think the novelty of the approach justifies acceptance. It is a simple modification that may bring the expressive power of graph networks closer to that of pixel CNNs.
review_title: Great novel graph method which brings graph nets closer to CNN - but questions about equivariance

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Revision History**
- Oct. 27th 2020: Submit the initial comment.
- Nov. 20th, 2020: Fix the "Correctness" part for better readability.


**Review summary**

The use of vector fields on a graph to define directed convolution is an interesting idea. In addition, the proposed GNN is theoretically sound in that it is an extension of CNNs on a grid graph in a certain sense (Theorem 2.7). Empirically, the proposed GNN performs better than existing methods. Nevertheless, I am not confident that the proposed method effectively reduces the over-smoothing and over-squashing problems theoretically or empirically. Regarding the data augmentation, although the proposed augmentation method works empirically, I am not sure the soundness of the method.

**Summary of the paper**

This paper proposed DGN (directional graph neural network), which employs directional aggregations using a vector field on a graph. Specifically, it proposed two types of aggregations: Directional averaging and Directional derivative matrix, which use eigenvectors associated with a graph Laplacian. DGN generalized a CNN when the underlying graph is a grid graph. Also, it proposed a data augmentation method using vector fields. This paper claimed that the proposed methods reduce the over-smoothing and over-squashing problem and perform well compared to existing methods.

**Claim**

If I understand correctly, the main claims of this paper are as follows. I assume them and evaluate the paper based on whether it supports them.
- Claim 1: The lack of propagation directions in existing GNNs limits the discriminative power of GNNs (Section 2.1, Paragraph 2)
- Claim 2: Existing GNNs that used asymmetric graph kernels do not use the graph topology and directional flow (Section 1, Paragraph 2). 
- Claim 3: DGN generalizes CNNs on a grid (Section 1, Paragraph 4) and existing aggregation (Section A.1).
- Claim 4: DGN works as a countermeasure of over-smoothing and over-squashing problems (Section 2 Corollary2.5, Corollary 2.6). In particular, DGN theoretically and empirically allows message passing across distance layers (Section 1, Paragraph 5).
- Claim 5: Proposed data augmentation method using a vector field on a graph is effective.

**Soundness of the claims**

Can theory support the claims?
- Regarding Claim 1 and 2, this paper did not compare (at least directly) with existing methods theoretically.
- Claim 3 is supported by Theorem 2.7.
- Claim 4 is supported by Corollary 2.5, 2.6. (But I am not entirely sure their correctness. See "Correctness" section.)
- Claim 5 is not theoretically supported. But I am uncertain whether this paper argues that this claim has theoretical justifications.

Can empirical evaluation support the claims?
- Claim 1 is empirically supported by comparing GCN, GraphSage, GIN, and MoNet in the experiment in Figure 5.
- Claim 2 is empirically supported by the comparison with GAT and GatedGCN in the experiment in Figure 5.
- Claim 3 is theoretical. So, it is OK that no experiments correspond to it.
- Claim 4 is validated indirectly by comparing the proposed model with existing ones known to be suffered from the over-smoothing and over-squashing problem. If I do not miss any information, this paper did not compare the proposed method with anti-over-smoothing methods such as DropEdge [Rong et al., 20].
- Claim 5 seems to have some support from the empirical assessment (Figure 6). But I am not perfectly certain of their correctness. (See "Correctness" section.)

[Rong et al., 20] Rong, Y., Huang, W., Xu, T., & Huang, J. DropEdge: Towards deep graph convolutional networks on node classification. ICLR 2020.

**Significance and novelty**

Novelty
- The idea of using a vector field for directional message passing is novel, to the best of my knowledge.

Relation to previous work
- The authors mentioned existing GNNs that employed asymmetric kernels (such as GAT or DimeNet). Although they discussed the difference of the proposed model from them in detail, I think is these models are based on different design principles. (of course, it would be great if this paper discusses the difference in more details)
- As I wrote previously, this paper did not compare the proposed method with existing anti-over-smoothing methods.

**Correctness**

Is the theory correct?

- Theorem 2.3: I think the statement of Theorem2.3 is informal. I would recommend to write the formal statement somewhere, at least in the appendix.
- Section 2.4: This paper wrote that "These results from theorem 2.3 and conjecture 2.4 have the following immediate corollaries" (the sentence after Conjecture 2.4). This sentence is not appropriate, as it reads that this paper derives corollaries from a conjecture, which is not proven yet. Considering that, it looks that Corollary 2.4 and 2.5 are not proven theoretically.
- Conjecture 2.4: I could not understand what "one step direction of $\nabla \phi_i$" meant.  I understand it when a vector field in a Euclidean space. However, since $\nabla \phi_i$ is a function on the set of edges on a graph, this analogy does not hold. I want this paper to clarify it.
- Theorem 2.7: The proof seems correct. The idea is to pick eigenvectors $\phi_1, \ldots, \phi_D$ that only change along each axis and take vector fields $\nabla \arccos(\phi_d)$ as basic components.
- Definition 4: Regarding the data augmentation (Definition 4), I understand the intuition that we "rotate" a vector field in the reverse direction instead of rotating an image. However, I could not understand whether the definition is sound.  Specifically, if I understand correctly, I expect that $F'_1 = F_1$ and $F'_2=F_2$ when $\theta = 0$. However, the latter one does not hold in general. Let us decompose $F_2$ into directions that is parallel and perpendicular to $F_1$ as $F_2 = F_2^{\parallel} + kF_2^{\perp}$ ($k=\|F_2-F_2^\parallel\|$). Then, it holds $F_2'|_{\theta=0}=F_1\cos \alpha+F_2^\perp\sin \alpha=F_2^{\parallel}+F_2^\perp\sin \alpha$. This does not equal $F_2$ in general.

Is the experimental evaluation correct?
- In Section 2.7, this paper proposed the random distortion of a vector field as Definition 5. However, if I do not miss anything, it only defined the concept and did not discuss its theoretical nor empirical properties. Therefore, I do not think the proposed augmentation method is justified.
- In Figure 6, when the maximum rotation angle is $45^\circ$,, the training and test accuracy of the dx method is worse than the baseline. I want this paper to discuss the behavior.

Is the experiment reproducible?
- Yes

**Clarity**

Can I understand the main point of the paper easily?
- Yes. The background of the proposed method is explained in Section 2.2. The proposed method is explained in Section 2.3. Proofs are easy to understand. The explanations are easy to understand.

Is the organization of paper well?
- Yes. I did not find any problem regarding the organization of the paper.

Are figures and tables appropriately made?
- Yes

**Additional feedback**

- Section 2.3, Figure 2: Should we replace $u_i$ with $x_{u_i}$, as $u_i$ is a label for the node itself?
- Section 2.4, Theorem 2.3: There seems to be inconsistency of ranges the index $i$ runs in different places. Specifically, they assume that indices of $\lambda_i$ and $\lambda_i'$ run through $i=0, ..., n-1$ in one place and $i=1, ..., n$ in another place. Also, it should be explicitly written that $\lambda_i$'s are sorted (either in ascending or descending order) because otherwise $\lambda_1$ and $\lambda_2$ are undefined. 
- Section 2.5, page 5, last line: figure 2.5 → figure 3
- Section 3, page 7, paragraph 3: How can we determine $k$?
- Section 4, page 7, paragraph 1: What does $i$ in $B^i_{dx}$ and $B^i_{av}$ indicate? (index of the eigenvector?）
- Section C.3, page 15, Make $D^{-1/2}$ bold
- Figure 4 referred to $B_{av}$ as av, while Figure 5 referred as smooth. I would recommend to make them consistent.
- In Equation (8), they normalized the length of the vector field to 1 in the definition of the perpendicular component of a vector field. However, I think we usually refer to the unnormalized vector field (i.e., denominator of (8)) as a perpendicular component.

review_title: Review Comment #1 

Meta-review: The main merit of the paper is to try to address some important issues about GNN, e.g. expressivity power and data augmentation, from a novel perspective and using well grounded mathematical tools. Unfortunately, however, this novel perspective is also introducing some confusion about its meaning in the context of graphs. In fact, it is not clear how, in the general case, direction as introduced in the paper makes sense, especially when considering the data augmentation approach. Moreover, although well grounded mathematical tools are used, proofs of theorems, as well as justification of related corollaries, are not sufficiently clear to guarantee their correctness.

In summary, a potentially interesting contribution that needs more work to better clarify motivations, grounding to common graph concepts, better presentation of the theoretical results.
Decision: Reject