Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a novel mechanism to efficiently improve learned graph representations. It proposes an independent second layer built upon base GNN representations that can improve the performance and expressivity of the base GNN. This mechanism is the Geodesic pooling layer. The horizontal version works by pooling the node representations along the shortest path between a pair of nodes. The vertical version works by pooling the nearest neighbors to the target node along any shortest path between the nodes of interest. 

The paper then proposes different techniques for using these geodesics for node-level, edge-level, and graph-level tasks. 

For experimentation, they do experimental testing across different domains. They test on link prediction tasks for knowledge graphs and link prediction on OGB datasets. They also test on graph classification using TU and OGB datasets. Node classification tasks are not experimentally tested.

The results show very good results on edge level and graph level tasks.

There is also a bit of theoretical analysis showing that the model can distinguish certain types of graphs (r-regular) with a high and controllable likelihood. In addition there are good synthetic examples where existing works would fail to distinguish certain graphs or edges. 
strengths_and_weaknesses: Originality:

++ Work is original. Ideas are novel. 

-- Should be comparison to how this differs from path based reasoning methods (many exist for KG completion)

Quality:

++ The work is a complete work and is of generally high quality. The ideas are well motivated. 

++ This approach seems very well attuned to link level tasks and would certainly be of interest to people working with these tasks (e.g. Knowledge Graph Completion). It also seems like it is better than the baselines in graph completion.

-- Does not seem like there would be any advantage to using this on node-level tasks as there is basically no difference to existing GNNs. It is essentially sampling neighbors of a node and then applying another GNN on top of that. 

-- Also, no testing of node level tasks

-- The KG completion task should not necessarily be considered state of the art. I think the baselines are fair for comparison, but there are other methods that take advantage of the textual data available via language modeling for better inductive knowledge graph completion. I think the authors should mention that they exclude text based inductive models for KG completion. Or they could add these baselines and see how they compare?

Including:

Wang, Bo et al. “Structure-Augmented Text Representation Learning for Efficient Knowledge Graph Completion.” Proceedings of the Web Conference 2021 (2021): n. pag.

Daza, Daniel et al. “Inductive Entity Representations from Text via Link Prediction.” Proceedings of the Web Conference 2021 (2021): n. pag.

-- The theoretical analysis is limited to to r-regular graphs with no node features. This is not a common occurance, but does slightly support the idea that there may be an advantage over standard GNNs. However, in general, this work does not deal well with how node features affect the analysis. Authors state "For simplicity, we use homogeneous graphs to illustrate our ideas and methods" but the analysis likely does not hold up as well for non homogenous graphs. 

-- Small note: GNNs often use only a few layers because there is no performance advantage (e.g. over smoothing), not because of computational cost. (line 174)

+- Small note: The horizontal geodesic seems like a good idea for connecting far nodes, however, there is still a max depth. 

Clarity:

++ The writing is generally precise and clear. 

-- The use of the v1 and v3 splits  for inductive kg completion is slightly cherry picked (the full table is in the appendix)

Grammar/Spelling:

Figure 4: distingshui -> distinguish

questions: 1) For node level tasks, how is the geodesic approach any different to sampling neighbors of a node and running a GNN? (maybe with included feature indicating node of interest). Does not seem like this approach would confer any advantage or difference in this realm.

2) Since you use a max distance cutoff, how often do the graphs have links that are beyond the max distance? Does the model still predict these links in practice or does the model learn to never predict links between "disconnected" nodes?

3) How would the presence of node features affect or limit the analysis?
limitations: Limitations/questions surround the node level tasks, analysis under the presence of node features.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper deals with supervised learning on graph structured data for which the most common framework of GNN is limited in expressivity by 1-WL test in terms of its identifying capacity of graphs. More expressive GNN models operate on either higher order tuples of nodes or involve preprocessing of substructures, both of which involve more computation which is not scalable to large graphs. In this paper, the authors propose using the geodesic information between pairs of nodes which includes full shortest-path information. The method includes horizontal geodesic (set of nodes in shortest path) and vertical geodesic (1-hop neighbors which occur in any shortest path). Experimental results on Link Prediction and graph prediction datasets are shown as empirical evidence for the proposed approach.
strengths_and_weaknesses: ### Strengths:
1. The paper addresses an important problem of finding efficient ways of improving the expressivity of the GNNs.
1. **Novelty**: Although the use of shortest path information or distance encodings is shown by some recent works for improving expressivity of GNNs, I find there is good enough novelty in exploring this approach further by incorporating full geodesic information. I find the “vertical” and “horizontal” geodesics proposed to be interesting ways of incorporating the geodesic information explicitly. 
1. The geodesic method can distinguish graphs which go beyond distinguishing capacity of mere distance encodings.
1. Experimental results on Link prediction datasets seem to be good.
1. Paper is well written and the presentation is clear. I especially appreciate the intuitive explanations with example graphs to show how “vertical” and “horizontal” geodesics are helpful. However, more annotations in Figure 4 would be helpful.

### Weaknesses:
1. **Permutation invariance**: The method belongs to randomization based techniques to improve expressive power of GNNs since one random shortest path is chosen in computing horizontal geodesic and hence cannot guarantee permutation invariance. This in itself is not a weakness, however, it needs to be acknowledged and the paper needs to be clearly positioned accordingly. 
At least some experiments should show comparison with randomization based expressive GNNs like RNI (Abboud  et al. (2020)) and PF-GNN (Dupty et al. (2021))
1. Since the aim of the paper is primarily to go beyond 1-WL GNNs, then it should present experiments where GD-GNN is able to identify graphs not identifiable by 1-WL GNNs like on Circular skip link, Strongly regular graphs etc.. Most papers on the topic of expressive GNNs do exactly this. Such experiments are missing. It would be helpful to see the comparison with higher-order K-GNNs, PPGNN (Maron et al.(2019)), RNI, PF-GNN in order to assess where GD-GNN stands in comparison with other more expressive models.
1. It is not clear how exactly the geodesics are generated efficiently. For ex, how to find vertical geodesics of a pair of nodes. Naively, you would need to  find all shortest paths between nodes and take subset of 1-hop neighbors. Naive way of generating geodesic would take not less than O(n^3) time which is all pairs shortest path. Is  there an efficient way of computing geodesics of all nodes at once? 
1. I don’t understand “decoupling” and its usefulness as it is said in line 155-158. What do you mean running GNNs only once? Why can’t we preprocess geodesic information and then use it along with GNN message passing. For ex, preprocess horizontal geodesic, run GNN message passing and pool embeddings from geodesic subset of nodes and repeat this iteratively. Comparing both GNN and geodesic computation, I see that GNN is more efficient than computing geodesics and don’t understand why run GNN only once. Also, do vertical and horizontal geodesics have any learnable parameters?
1. Results on link prediction are impressive. However, the results on graph prediction are not and the baselines used are dated. Since, the motivation of the  paper is to build more expressive GNN, other more expressive models like K-GNN, RNI, PF-GNN should be shown. If the performance is not at par, it is not an issue, however, it should be acknowledged.
1. One of the claim is runtime efficiency compared to other expressive models. However, in worst case, I believe the runtime of GD-GNN is also not less than O(n^3), since the subgraph around a node can be O(n) size. This is same as 3-WL time complexity. Please clarify the worst case runtime in terms of number of nodes n.  Also, in runtime experiments, are you also taking the geodesic computation into account?
1. Ablation study can be expanded. You can test vertical geodesic by instead taking all neighbors of pair of nodes and not just neighbors which are part of shortest paths. This would show if vertical geodesic is important. For horizontal geodesic, you can test does full shortest path is needed or few hop nodes in the shortest path are good enough. You can vary number of hops for ablation.
1. In Section 3.3, the paper first discusses all node, link and graph prediction tasks but doesn’t show experiments on node prediction. 
1. For link prediction tasks, I think it would be better to compare with other methods like Position-aware GNNs (You et al.(2019)) which also in a way tries to capture shortest path information.

**Overall**, I find the idea and theme of the paper novel and significant. However, in the present form there are many issues as identified in the weaknesses which makes the paper somewhat in borderline.

### References:
1. Abboud  et al. (2020). "The surprising power of graph neural networks with random node initialization." arXiv preprint arXiv:2010.01179
1. Dupty et al. (2021) "PF-GNN: Differentiable particle filtering based approximation of universal graph representations." International Conference on Learning Representations.
1. You et al.(2019) . "Position-aware graph neural networks." International conference on machine learning. PMLR


########################

Update:
I Thank the authors for the response and additional experiments. Based on the revision, I'm updating the rating and would be happy to see the paper at the conference.

questions: Please address the weaknesses mentioned above.

limitations: I did not find limitations of the approach being discussed in the paper. There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Among existing graph neural networks (GNNs), standard GNNs are efficient but cannot distinguish structures beyond 1-WL test, while subgraph extraction or customized labeling methods are powerful but require much more computation. This paper proposes a new graph neural network (GNN) architecture, which seeks for a new sweet point between efficiency and effectiveness. The idea is to first compute node representations with a standard GNN, and then readout augmented node/edge/graph-level representations via geodesics. The authors propose two variants for Geodesic GNN, namely horizontal and vertial geodesics. Experiments on both link prediction and graph classification tasks show that geodesic GNNs achieve results on par with SotA models, while only take time similar to standard GNNs.

The contributions of this paper include:

1. Propose geodesic GNNs that are both effcient and effective.
2. Theoretically prove geodesic GNNs are more powerful than 1-WL test.
3. Empirically show that geodesic GNNs achieve good results in both performance and time.
strengths_and_weaknesses: Strength

- The idea of using geodesics for readout seems novel to the community. It fills an important gap in GNNs beyond 1-WL test.
- The proposed geodesic GNNs are more powerful in theory, and trades off efficiency and effectiveness better in experiments.
- Geodesic GNNs are general and have the potential to be applied to most standard GNNs.
- The paper is well written and easy to follow.

Weakness

- Although the authors propose node-level representations for geodesic GNNs, there is no experiments on node classification tasks to verify its efficiency and effectiveness.
- The authors are ambiguous about the time complexity of geodesic GNNs. In general, the complexity of geodesic GNNs should between standard GNNs and subgraph extraction. The condition for “GD-GNN maintains the good efficiency of basic GNN models” is that the geodesic readout can be amortized by the cost of the GNN. This is only true for some simple geodesic readout functions, like the two proposed in the paper. The authors should make this more explicit to the readers. Also the time complexity in Appendix B is too optimistic.
questions: - Line 55: Why are higher-order GNNs at least cubic complexity? Could you provide a reference to that?
- Line 125: Taking link prediction as an example
- Line 151: Why is the shortest path viewed as a chain of nodes with embeddings one? What are the embeddings discussed here?
- Line 179: You may provide a motivating example here.
- Line 198: If the pooling layer is a small plain GNN, is geodesic GNNs as slow as SEAL?
- Line 214: Why are geodesic nodes close to $v$ ignored here?
- Line 220-224: To my understanding, this property has been discussed in NBFNet[1] and RED-GNN[2] before. It’s better to cite them to provide a fair context.
- Line 297-299: If I understand correctly, the main advantage of GD-GNN over NBFNet is that it avoids the cost of GNNs in subgraph extraction, but GD-GNN still needs to perform subgraph extraction for each query. Why is GD-GNN efficient in any scenario? Is it over-claiming?
- Appendix B: The time complexity analysis is too optimistic. The authors seem to use the average degree of a node in the full graph / in a local subgraph interchangeably, and assume they are small constants. This may not be true. For example, for a scale-free graph, the average degree may be a constant, but the average degree in a local subgraph may not! This is because every node is likely to be connected to nodes with large degrees, and therefore a lot of subgraphs contain nodes with large degrees. I suggest including the complexity of standard GNNs, SEAL, NBFNet for a fair context.
- Table 3: Why does NBFNet cause OOM? Could you give an explanation?

[1] Zhaocheng Zhu et al. Neural bellman-ford networks: A general graph neural network framework for link prediction. NeurIPS 2021.

[2] Yongqi Zhang, and Quanming Yao. Knowledge graph reasoning with relational digraph. WWW 2022.
limitations: The authors don’t discuss the limitations and societal impacts in the paper. I would suggest the authors adding one paragraph to discuss that. For example, some limitations could be that GD-GNN can only be applied with simple geodesic readout, otherwise it may still have time complexity issues.
review_title: null

Meta-review: metareview: I must say that I am impressed with authors' diligence in the rebuttal, adding new experiments and revising the paper. The paper had many issues in the original submission, although it was still well-written. The reviewers are more convinced about the paper after the rebuttal. I would recommend a (weak) acceptance with some (unaddressed) concerns. 

To improve the expressivity power of GNN, in this paper the authors developed a mechanism (Geodesic pooling) for improving learnt graph representations, by using an independent second layer based on GNN.  They presented good results on edge level and graph level tasks. The reviewers believe the method is novel and worth the acceptance if the many issues raised could be resolved. 

More details: GNN are prone to map different nodes in a graph to the same embedding vectors in the embedding space even if they are far away from each other in the graph. Specifically, if the local structure of two nodes are similar, the convolution layer maps both of them to the same embedding vector. The paper proposes to include geodesic information to help to distinguish nodes with similar local structures. However, for a graph classification task, it requires computing the shortest path between two many pairs of nodes which could be computationally expensive. In addition, the paper does not cite and compare to other important baseline. For instance, a simple and effective solution is to simply provide geometrical embedding vectors as initial node attributes to the GNN. Some works that can be cited and compared against:

Graph Neural Networks with Learnable Structural and Positional Representations

The Necessity of Geometrical Representation for Deep Graph Analysis

Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding

Inductive Graph Embeddings through Locality Encodings

confidence: Less certain
Decision: Accept