Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new type of anchor-based GNN by implicitly exploiting node positioning within customized message passing steps of MPNN. The framework consists of an anchor labeling strategy and a specified propagation path with the utilization of Bellman-Ford algorithm, to enable its positional awareness. The empirical results on small synthetic and real datasets show the effectiveness of implicit positional encoding, and achieve comparable results against other anchor-based models.
main_review: Strength:
This paper explores how to implicit learn graph position embeddings with anchor indication, and then propose a new strategy for message propagation under MPNN, which is clearly distinguished from other position-aware GNNs.

Weaknesses:

• The proposed framework (GIR) has limited theoretical contributions and  application scenarios, i.e., incapable of inductive settings, only tested on small-scale dataset. The empirical results lack the support for the key claim that the combined procedure of distance computing and encoding is more beneficial than the separated two-stage way.

• The authors only differentiate GIR with other position-aware GNNs, but do not present the connection and difference between previous works [1] (first propose max-pooling of MPNN to mimic Bellman-Ford Alg).

• The authors do not include the complexity discussion of the proposed method, especially regarding the part of labelling indication and 
modified message passing and the cost comparison between implicit and explicit encodings. The introduction of relaxation process also raises the concern for the proposed method working on large-scale datasets. 

• The notation system used in this paper appears to be very confusing. Several symbols are not properly defined, such as $f_p$, $g_a$ in Def 1. 

[1] Veličković, Petar, et al. "Neural execution of graph algorithms." arXiv preprint
arXiv:1910.10593 (2019).


Typos:
In Def 1, $\mathbb{N} \in \mathbb{B}$ should be $\mathbb{N} \subset \mathbb{B}$?
In Def 2, $f_{\mathbb{N}}(z) = f(z, N)$ should be $f_{\mathbb{N}}(z) = f(z, \mathbb{N})$?
Reference for position-aware embeddings should be Def 1 instead of Def 2?
summary_of_the_review: This paper presents an implicit way to learn graph positional embedding. However, the manuscript is not yet ready to be published. It does not provide a clear empirical investigation or a solid theoretical examination for how the implicit positional encoding is better than the explicit way. The content, organization and experiments also need to be further polished and enhanced.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors propose the anchor-based framework for position encoding. 

It is well known that the message-passing framework inherently has a limitation to encode graph structure and sometimes fails to discriminate isomorphic subgraphs.

Graph Inference Representation exploits the distance relaxation process of the Bellman-Ford shortest path algorithm.

The authors show that the MPNN framework can keep track of the shortest paths using anchors.

To this end, the authors introduce the anchor labeling strategy for MPNNs mimicking the Bellman-Ford algorithm.

It has a more specialized structure and outperforms baseline models.
main_review: As the authors mentioned, the MPNN framework has inherent limitations, especially in position-aware embeddings.

So this work can bring some value to the GNNs community.

I have a question about GIR framework.

In Anchor Selection, it is determined in a heuristic way, degree centrality. 

Because anchors are important components in the GIR framework, I believe there should be various attempts to choose the measure of importance for anchors.

In addition to degree centrality, Eigenvector Centrality, Katz Centrality, PageRank, Betweenness Centrality, Closeness Centrality, Harmony Centrality, and Clustering coefficient can be candidates for anchor selection. 

Even some might be suited for effective coverage. 

Or, additional trainable neural networks can be used. Could you explain how did you choose the measure and provide evidence as well?
summary_of_the_review: I would recommend this paper be accepted if other issues do not arise.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a GNN method (GIR) that incorporates the paths produced by the BFS algorithm in the message passing algorithm, such that it enables the method to mimic the shortest path algorithm. This way, the method is able to learn positional embeddings implicitly. The experiments are conducted both on synthetic and real-world datasets.
main_review: **Pros:**

- The idea of capturing positional information in the node embedding in an implicit way by constraining the propagation path in a way similar to BFS is interesting and could lead to powerful results.
- I appreciate the formalisation of positional-aware embeddings and the alignment between the proposed method and the BFS algorithm.

**Cons:**

- While the empirical results show some improvements in certain scenarios, it is not clear from the paper why or when the implicit positional encoding is superior to explicitly encoding of the shortest path. When the interactions between intermediate positional encoding (mentioned in the abstract) are useful, and why is it better to learn them instead of specifying them for each layer? A clear discussion in this regard would be useful to emphasize and clarify the theoretical contribution of this paper.
- Even if I find this idea as having big potential, I found the paper very hard to follow. The distinction between A-position-aware and {A}-position-aware is not clearly explained in the text even if it is a central element in the paper, as most of the experimental section refer to these two setups.
- The experiments presented in Table 5 are not enough explained in the text. What is the intuition for the difference in performance between GIR, GIR-A, GIR-O, and why is the ranking different from one dataset to another. What additional information brings each one of them? Moreover, I found the way the experiments are presented (too many abbreviations) difficult to follow.
- As the authors mentioned, the number of anchors and the way you pick them to influence the amount of structure captured by the algorithm, ranging from complete lack of structure to a normal message passing algorithm. Very few anchors or a bad way to choose them could lead to a great loss of information in terms of structure, eventually leading to poor results. An ablation study on how the results changed depending on this choice, or at least some intuition on what properties the SelectAnchor method should fulfil, would be useful.

Minors: The definitions for the concepts introduced are confusing, and some notations are not consistent along the paper. N is well-known for the set of natural numbers, so I recommend picking a different letter in definition 2. On page 7, there is a typo: I think it should be PGNN-F instead of PGNN-E; On page 7, Datasets paragraph, it should be Definition 1 instead of Definition 2; Same on the last paragraph before section 3.4; Multiple inconsistent usages of normal vs mathbb letters to denote sets (e.g. in Definition 2).
summary_of_the_review: Overall, I agree that the method could be useful and could improve the GNN methods in situations when the positional encoding is important. However, the current form of the paper lack clarity and I consider that many aspects of the method/experiments should be better present in order to be clearly delivered to the community.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes the Graph Inference Representation (GIR) model, which first applies an anchor indication strategy and a forward process that mimics Bellman-Ford algorithm. The authors theoretically show that the proposed pipeline should be able to capture positional embeddings implicitly, and empirically show that the proposed pipeline can achieve superior performance on simulated and real-world datasets.
main_review: Strengths:

1. The idea of mimicking Bellman-Ford algorithm sounds interesting and novel to the reviewer.

Weaknesses:

1. The presentation of the paper could be improved. The notation is a bit overwhelming, especially in Sec 3.3.  What's the difference of $\mathbb{B}$ and $\mathbb{N}$? What does $\mathbf{f}_{\mathbb{N}} (z) = f(z, N)$ mean? In addition, I suggest the authors to try to avoid using too many abbreviations in the experiment section as it's really hard to follow, e.g, Table 2, 4 (dist-u,a,au, -AA -A -M -O, etc.). Even the algorithm detail is not super clear to me. What does line 6 mean?

2. The experiments between MPNN and GIR in Table 2 is not consistent. I'm wondering why. It occurs to me that GIR has no significant benefts over MPNN.

3. The empirical study seems not sufficient. There's no large-scale experiments. 

Questions:

1. Though the selection of anchors seem deterministic. I'm wondering what's the variance of selecting different anchors? Or what's the selecting of selecting 1 more or 1 less achors?

Post rebuttal

I thank the authors for the updates. The notation system looks better in the revised version, though I believe it is possible to deliver this paper in a clearer way. As for the empirical performance, I'm not convinced by the authors that MPNN-A is also a GIR framework (it's basically adding one hot labels to label nodes). Summarizing above, I believe this submission could be more impactful after careful revising. I will retain my original rating as borderline reject. 
summary_of_the_review: interesting idea, but the presentation is hard to follow and the empirical results do not seem very significant
review_title: null

Meta-review: This paper proposes to encode positions of nodes in graphs by anchor-based GNN with customized message passing steps. All reviewers raised significant concerns on this paper, including novelty of the message passing steps, experiments, writing and clarity, etc. The authors have actively responded to reviewer comments, but many of the concerns are still not addressed. Thus, the paper needs some work in order to be competitive.
Decision: Reject