Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: This paper proposes to augment graph neural networks with awareness of global graph information based on memory neural networks.

While this work attempts to leverage the memory networks for latent representation transformation, so as to preserve global graph structural information, there exist many recent developed graph neural models which aims to inject global-level graph structure into the embedding generation. To name a few for reference:
Deep Graph Infomax, ICLR.
Position-aware Graph Neural Network, ICML.
However, the proposed models (MemGAT and MemGCN) are mainly compared to some representative graph neural network architectures, like GCN and GAT, which is insufficient to demonstrate the effectiveness of the new graph neural method.

As a general graph neural network model, the evaluation experiments on only the node classification task can hardly comprehensively justify the rationality of the proposed approach. Other benchmark tasks, such as link prediction or node clustering, could be considered in the evaluation section. Additionally, it would be interesting to discuss the latent influence between memory dimensions and graph network depth.

Another important dimension of evaluation lies in the model efficiency study. How is the computational cost of the proposed MemGNN (MemGCN and MemGAT) framework as compared to other alternatives, such as GCN and GAT, can be investigated. Due the pairwise relation learning with attention mechanism, the GAT-based neural architecture could be more time-consuming. What is the additional cost brought by the designed memory neural network with multi-dimensional latent representation projection.

From the evaluation results, we can observe that GAT- and GCN-based graph neural networks provide different performance with respect to split methods (e.g., random split and standard split). It would be interesting to provide some insights and clarifications to discuss this point, in order to understand the memory graph neural network better.
review_title: Official Blind Review #3

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
The paper proposes a new class of neural networks augmented by memory nodes. The authors studied variants of GCN, and GAT with memory nodes and specifically designed edge attention functions and aggregators. The proposed models achieved competitive performance compared to state-of-the-art methods. 

Clarity. 
Overall, the paper is well-written. Theoretical results are introduced with concise discussions and pictorial examples. They made the results more accessible. 

Quality/significance (pros)
	1. The authors found the cases where LUMP-GNNs fail and they prove it in theorem 1. 
	2. The authors theoretically and empirically prove that memory-augmentation helps to identify locally indistinguishable graphs with different multiset feature representations in theorem 2 and Figure 3. 
	3. The ablation study shows that the proposed modules are effective and provide significant improvement in some settings.
	
Weaknesses (cons)
	1. The authors should compare their work with GNNs with non-local operations, e.g., LatentGNN [1]. The paper also studies the limitations of local GNNs (not specifically LUMP) but the resulting model is similar to memory augmented GNNs and it has skip connections and augmented by convolution in the latent node space.
	2. It's an interesting technique to improve the expressive power of GNNs but the augmentation requires significant modifications of the original GNNs. If the technique is applicable to general GNNs in a plug-and-play manner, it would be more useful.
	3. Depending on the edge weights, the models may behave differently. The handcrafted edge weights from the truncated diffusion matrix naturally raise the question of whether they are necessary to show the effectiveness of the proposed technique.
	
Question. 
	1.  In the aggregation scheme of MemGCN, $M_v^{(l=1)} = \lambda W^{(l)} m_v{(l)} \cdots$, 
'$m_v``$' has no nonlinear function whereas MemGAT has a nonlinear function for WRITE, .e.g,  $\alpha_{vv}^{(l)} \sigma^{(l)} (m_v^{(l)})$. Is this a typo? Otherwise, provide intuition why MemGCN should not use nonlinear activation functions for messages from memory nodes. 
	2. Unlike memGCN, memGAT adjusts the effect of messages from memory nodes within the attention mechanism. Is the main reason why the MemGAT significantly underperforms MemGCN in table 2 even though the vanilla GAT consistently outperforms the vanilla GCN?

[1] Zhang, Songyang, Xuming He, and Shipeng Yan. "Latentgnn: Learning efficient non-local relations for visual recognition." International Conference on Machine Learning. 2019.

--- Post Rebuttal ---
I read the author feedback.  The typo in Question 1 is fixed and the issue with the edge weights is addressed. However, the proposed method requires model-specific modifications and cannot be applicable to other tasks on graphs, e.g., link prediction. Due to the limitations, I will keep the original rating.
review_title: Interesting model augmentations for GNNs

final_score: rating: 5: Marginally below acceptance threshold
review_content: ==========Summary==========

In this paper, the authors study how to enhance the expressive power of GNNs by memory augmentation. In particular, the authors focus on the cases of the "locally indistinguishable" property, demonstrate why existing GNNs fail to differentiate such structures, and propose a memory augmentation strategy to break the tie. Starting from theoretical analysis, the authors suggest how to apply memory augmentation to GCN and GAT. Empirical results on public benchmark datasets suggest the effectiveness of the proposed method.

==========Reason for the rating==========

At this moment, I am standing between 5 and 6. Overall, the authors tackle the expressive power enhancement problem from an interesting angle, and the technical insights are well presented. My main concern is on the gap between real-life data distribution and theoretical assumptions. While it is theoretically interesting, it is unclear how much difference "locally indistinguishable" structures make in reality. 

==========Strong points==========

1. The authors investigate how to enhance the expressive power of GNNs from a unique perspective.

2. The core idea is well presented with logical reasoning based on theoretical and concrete evidences.

3. Empirical results suggest the proposed technique is promising in node classification tasks.

==========Weak points==========

1. The authors may need to clarify the scope of the theoretical results. Do the theoretical result still hold for the cases where node attributes are multi-dimensional numerical values? For the assumption in Section 3.1 "We will assume the set $\mathcal{X}$ to be countable, then by (Xu et al., 2019, Lemma 4), the range of $h^{(l)}_v$ , denoted $\mathcal{H}^{(l)}$, is also
countable for any given parameterization and any layer l.", what is the exact implication?

2. The authors may share a few concrete examples from real-life data that suggest it is valuable to differentiate locally indistinguishable structures. Although the prediction results suggest the effectiveness, it is critical to confirm it is locally indistinguishable structures that make this difference.

3. For the results presented in Table 1 and Table 2, the authors may need to consider identical train/validation/test splits for all the baseline methods for fair comparison.

==========Questions during rebuttal period==========

Please address and clarify the weak points above. 

==========Post rebuttal==========

I appreciate the authors' effort on answering my questions. Meanwhile, the authors' response does not fully address my concerns. I keep my rating as it is. 
review_title: Review comments on Paper 2966

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes to enhance GNNs with memory networks. The authors prove that existing GNNs cannot distinguish two nodes in two graphs which are local isomorphic, then they propose introducing additional nodes for a graph that connect to all existing nodes, which help distinguish neighborhood structure for the given two nodes. This paper is basically well written and easy to follow. The idea of combining memory networks and GNNs is also novel and interesting. The experimental results demonstrate the efficacy of the proposed method. However, I have the following concerns:

1. How should we understand local isomorphism intuitively? What are the connection and difference between the conventional isomorphism and local isomorphism? Can the proposed analysis be generalized to the conventional graph isomorphism? I think the paper goes a little quick from Definition 1 to Theorem 1. It would be better to put more words here to clearly demonstrate the concept of local isomorphism.

2. The authors provide an example in Figure 1 and 2 to show the limit of existing GNNs and that an additional memory node is able to distinguish the two subtrees. However, the example only works in the case of two graphs. In a single graph, adding an additional node that connects to all nodes does not provide such ability to distinguish two nodes. Since the used datasets are all single graph, I was wondering what the benefit of introducing an additional node is.

3. The theoretical part is nice to read, however, they are all existence theorems, which neither tells us how to find such solutions or provides performance guarantees for the proposed method. The proposed method seems more likely to address a very special case where two nodes (in two graphs respectively) cannot be distinguished, but this case rarely happens in practice.

4. In experiments, I was wondering why the authors uses diffusion matrix rather than the original adjacency matrix, since it makes readers unclear that the performance gain is brought by the memory mechanism or the diffusion matrix. It would be more convincing to use original adjacency matrix in the proposed method, or add (Klicpera et al., 2019) as a baseline.

review_title: This paper addresses a very special case that rarely happens in practice

Meta-review: In this paper, the authors proposed a method to handle the problem of LUMP GNN architecture. This problem is indeed important and the proposed method has some merits. However, the proposed approach is only applicable to node classification.  Moreover, the proposed approach shows the similar theoretical results of Sato et al 2020. In the paper, it can be applicable to any GNN tasks because it only adds random features to each node. Therefore, the novelty of the proposed method is limited.  I encourage authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 
Decision: Reject