Graph neural networks have shown promising results on representing and analyzing diverse graph-structured data such as social, citation, and protein interaction networks. Existing approaches commonly suffer from the oversmoothing issue, regardless of whether policies are edge-based or node-based for neighborhood aggregation. Most methods also focus on transductive scenarios for fixed graphs, leading to poor generalization performance for unseen graphs. To address these issues, we propose a new graph neural network model that considers both edge-based neighborhood relationships and node-based entity features, i.e. Graph Entities with Step Mixture via random walk (GESM). GESM employs a mixture of various steps through random walk to alleviate the oversmoothing problem and attention to use node information explicitly. These two mechanisms allow for a weighted neighborhood aggregation which considers the properties of entities and relations. With intensive experiments, we show that the proposed GESM achieves state-of-the-art or comparable performances on four benchmark graph datasets comprising transductive and inductive learning tasks. Furthermore, we empirically demonstrate the significance of considering global information. The source code will be publicly available in the near future.
This paper presents two models, namely GSM and GESM, to tackle the problem of transductive and inductive node classification. GSM is operating on asymmetric transition matrices and works by stacking propagation layers of different locality, where the final prediction is based on all propagation steps (JK concatenation style). GESM builds upon GSM and introduces a multi-headed attention layer applied on the initial feature matrix to guide the propagation layers. The models are evaluated on four common benchmark datasets and achieve state-of-the-art performance, especially when the training label rate is reduced.
Overall, the paper is well-written and its presentation is mostly clear and comprehensible (see below). The quantitative evaluation looks good to me, especially since an ablation study shows the contributions of all of the proposed features.
However, there are a few weak points which should explain my overall score:
1. The proposed GSM model is not new and only re-uses building blocks from the related work. [1] shows that removing non-linearities is an effective procedure for node classification. [2] investigates the massively stacking of propagations. The procedure of feature concatenation from different locality has been studied in [3]. Applying asymmetric normalization is a standard aggregation scheme for GNNs, e.g., in [4].
2. The GESM model is not fully understandable since it is missing a formal description for computing $\alpha$. It is only said that $\alpha$ is computed using the concatenation of features from the central node and its neighbors. Can you elaborate how exactly you compute $\alpha$, especially since the concatenation of neighboring features results in a non-permutation invariant architecture? In addition, in contrast to the reported results in Tables 3 and 4, Figure 4 indicates that the benefits of GESM are negligible.
3. The final prediction layer with weight matrix W_1 operates on all propagation layers, resulting in a parameter complexity of $O(s  h c)$, where $c$ is the number of classes. With $s=30$ and $h=512$, this results in 15.360  c parameters (!!!), whereas GCN [5] only uses 16  c parameters. Hence, I do not think it is fair to promote your model as efficient as vanilla GCN. In addition, the final matrix multiplication results in a computational complexity of $O(n  s^2  h^2  c)$ which does not nearly match your reported complexity.
Furthermore, I do wonder why your model is not heavily overfitting with such an amount of parameters. For example, this is the reason [3] does evaluate its model on a larger training split instead of a smaller one.
4. As your work is quite similar to [1, 2], it would be beneficial to also include the respective results of those methods in Tables 2 and 3. In addition, their differences and similarities should be discussed in detail.
5. Since the used benchmark datasets are already reasonably explored, authors are advised to include evaluation on other datasets as well, e.g., from [6].
6. The transition matrix $P$ is missing self-loops to match with the results of Figure 1. Since you already define $P$ analogously to $\hat{\tilde{A}}$, you should focus on one notation for consistency reasons.
[1] Wu et al.: Simplifying Graph Convolutional Networks
[2] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank
[3] Xu et al.: Representation Learning on Graphs with Jumping Knowledge Networks
[4] Hamilton et al.: Inductive Representation Learning on Large Graphs
[5] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks
[6] Shchur et al.: Pitfalls of Graph Neural Network Evaluation
----------------------------
Update after the rebuttal: The authors have addressed several issues and improved their manuscript. I greatly appreciate the effort and the new experimental results. However, the main weak point that the novelty of the approach is limited remains valid of course. Therefore, I am still more inclined to rejecting the paper. I have raised my score from "1: Reject" to "3: Weak Reject".
I have raised my score from "5: Weak Reject" to "6: Weak Accept".