Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a method GLINKX that combines knowledge graph embedding, ego embeddings, and label propagation to tackle node classification on both homophily and heterophily graphs. Experiments are conducted on several OGB benchmarks and show some effectiveness.
strength_and_weaknesses: Strength:
- The proposed method is light-weight and thus can be used for large graphs.

Weaknesses:
- The proposed method is not applicable to many graphs as it requires knowledge graph embeddings to provide node positional encodings. 
- The novelty of the paper is quite limited. It's a incremental combination of the existing methods.
- Experimental results do not show better performance on homophily graphs.
- On heterophily graphs, there are lots of many other approaches that need to be compared with.
clarity,_quality,_novelty_and_reproducibility: Novelty is quite limited. The proposed method is a direct combination of several existing works, e.g., GCN, LINKX, Label propagation.

Clarity needs improvements. The motivations of the paper are not quite clear. Some existing works can already automatically balance the homophily and heterophily while learning for the downstream tasks. Authors need to justify what's new against these existing works.

Writings of this work needs to be polished a lot, addressing the typos, grammar issues, and better presentations.

summary_of_the_review: Regarding the details of some weaknesses above:
- Using knowledge graph embeddings as the pre-trained position encodings does not make sense, especially on the datasets where no knowledge can be used for pre-training, e.g., Cora, Citeseer, etc. There's no relation semantic at all.
- On homophily graphs, the proposed method actually does not perform better even than a two-layer GCN. On heterophily graphs, the proposed method performs better than the baseline methods used in the paper, but there are many other more powerful GNN models in the literature and the authors are suggested to compare with those methods.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes an extension of LINKX to be robust on both heterophilic and homophilic graphs.
strength_and_weaknesses: # Strengths:
1. Building scalable shallow method is a very important problem in the area of Graph Neural Networks.
# Weaknesses:
1. The paper and the algorithm are both difficult to follow and understand.
2. Since scalability is the primary goal, some information on training time, memory usage etc. would have been useful.
3. Albeit, the related work cites several papers, but comparison seems to drop them due to the fact that these methods are not scalable. However, there are a few datasets of fairly small size in the experiment, so at least for those, the numbers for these other methods can still be reported, if only to understand whether there is a trade-off involved between accuracy and scalability, and how much is it?
clarity,_quality,_novelty_and_reproducibility: The paper writing can be improved significantly. 
1. How is a graph treated as a Knowledge Graph? Simply saying that one learns Pytorch Biggraph embedding seems to be pointless. Why does it make sense to treat a general graph as a Knowledge Graph? How does it encode positional information? 
2. Many odd typos. For example, Algorithm 1 says Loss is maximized. I am assuming it should be minimized. Also, the notations can be improved to understand what they are. For example, Algorithm 1 says "learn distribution of a node's neighbors", but the y's are still running over the training data. So, it is extremely confusing, where is the neighbor information? What is backward label propagation in stage 3? the expression seems identical to the stage 2.
3. Why does this method capture long range information which is required for heterophily? There seems to some justification in Theorem 2, but the Theorem 2 statement is hard to follow and understand. However, it still seems that the model is utilizing 2 hop information. However, does that mean that the paper is claiming that 2-hop information is sufficient for heterophily? How does one prove this?
4. Comparisons with non-scalable models can still be done for smaller datasets, if only to understand the trade-off between scalability and accuracy.
5. Include training time, memory usage etc. information to show the scalability aspect of the model.

The novelty aspects are difficult to determine and lack of clarity makes the work hard to reproduce.
summary_of_the_review: The paper proposes an extension of LINKX model to address both heterophily and homophily. However, the paper requires significant rewrite to clearly highlight how the algorithm works and why should we expect it to work for heterophilic scenario. The experiment should still compare with non-scalable methods on datasets which are small enough. Also, the paper should report training time, memory usage etc. to understand the scalability aspect of the model.

As it stands, I am inclined to reject the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of GNNs under homophily and heterophily and the authors propose a scalable unified framework named GLINKX for this problem. The proposed GLINKX works in three separate stages:
- Making use of KEG to learn positional embeddings.
- Propagating information about labels from node's neighbors.
- Propagating the predicted labels and making final predictions.

GLINKX is also guaranteed with theories. Experimental studies on large-scale homophilous and heterophilous graphs demonstrate the effectiveness and efficiency of the proposed method.
strength_and_weaknesses: Strengths:
- The paper is well-organized and easy to follow and the target problem of GNNs for homophilous and heterophilous graphs is very important.
- The proposed method is effective and efficient in handling homophily and heterophily of large-scale graphs with some theoretical guarantee.
- Extensive experiments have been conducted to demonstrate the superiority of the proposed method from different aspects.

Weakness:
- The novelty of this paper is limited: the proposed framework is the combination of KGEs and LP.
- There are different ways to get positional embeddings, i.e., the embeddings that can preserve global/local structures of graphs. For example, traditional structural role discovery methods such as RolX [1] and network embedding methods such as node2vec [2]. So the questions are:
1) what are the reasons to make use of KGEs as PEs?
2) it is possible to compare different PEs?
- If there are errors/noises from the 1st stage of PEs, is it possible to handle the noises in the following stages?

There are also some minor concerns:
- Page 3: what is the meaning of \epsilon?
- Page 4: circumventing the to do
- Page 5: Alg. 1 (??)

[1] RolX: Structural Role Extraction & Mining in Large Graphs

[2] node2vec: Scalable Feature Learning for Networks

clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is well-organized and easy to follow.

Quality: This paper is of good quality with detailed discussion and comprehensive experiments.

Novelty: Technically, the novelty of this paper is limited because the proposed framework is a combination of existing methods, e.g., KEGs and LP.

Reproducibility: it should be possible to implement the method and reproduce the results from the description given in the paper.
summary_of_the_review: This paper studies an interesting and important problem. Overall this paper is well-organized and easy to read. Experiments from different aspects have been conducted. However, I have some concerns about the novelty and the selection of one component. Therefore, I will recommend a weak rejection of the paper, which I am willing to turn into an acceptance if all issues are addressed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extends LINKX by considering the monophily with monophilous label propagation. A graph is monophilous if the label of a node is similar to that of its neighbors’ neighbors.  To this end, it proposes two stages label propagations to meet the monophily property. Experimental evaluations show the marginal performance improvement.

strength_and_weaknesses: Strength
- It is interesting to make LINKX both inductive by using label propagation.

Weaknesses 
- This is not the first to consider monophily in GNNs, such as H2GCN and EvenNet, although this may be the first to imcorporate it with label propagation.
- The writing and organization are poor. Many components are redundant, such as the propagation formula in main body, algorithm and figure 1.
- Some parts of the paper is not clear, such as the meaning of Figure 3.
- The experimental evaluations are insufficient. The employed datasets are too little. Besides, the performance improvements is marginal compared with LINKX.
clarity,_quality,_novelty_and_reproducibility: - The novelty, clarity should be improved. 
- The reproducibility is acceptable.
summary_of_the_review: My main concerns are the weak novelty, poor writing and insufficient evaluations.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a method GLINKX that uses (1) knowledge graph embeddings (representing graph positional information), (2) node features, and (3) a novel Monophilous Label Propagation (MLaP) approach utilizing node labels. They also provide theoretical justification, which justify the benefits of their design based on error bounds (particularly the parametric model in MLaP, and the two-stage design). 

In general, reviewers find the problem interesting and important, and appreciate the novel theoretical grounding in the form of error bounds. However, there are a number of key issues which multiple reviewers agreed upon:

**Comparison with baselines:**
- Reviewers noted that the method lacks comparison with GNNs designed for the heterophily setting. In the author response, they state that one reason is that GNN based methods are not as scalable as LINKX. However, this would be more convincing if performance results on the time / memory consumption in practice were provided. 
- Reviewers also mentioned that the method also does not clearly outperform higher order GCNs (with >1 layer). The authors state in their response that the fair comparison is to 1-layer GCNs, since their method is also 1 layer, but without results showing that GLINKX can also improve its performance with higher number of layers, or performance results showing that its time / memory consumption compares favorably, this is still not fully convincing. 

**Clarity:**
- Reviewers pointed to a number of issues related to clarity. Many of these have been resolved, and I thank the authors for their efforts in improving the clarity. However, I believe that the paper would still benefit from making the idea of using knowledge graph embeddings clearer and more self-contained, particularly for readers who are not already familiar with such methods

In the end, reviewers and AC agree that while the work has intriguing ideas, due to the above issues, the work is not yet ready for publication at ICLR. The reviews offer a number of helpful suggestions for improvement, so I encourage the authors to continue improving the paper based on the reviews for future submissions.
justification_for_why_not_higher_score: The major issues were those related to comparison with baselines (as mentioned in my review), particularly w.r.t. heterophily GNNs, higher order GNNs, and the lack of computation time / memory results.
Decision: Reject