Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a method to construct graph embeddings that are well-tuned for answering shortest-distance queries (SDQs), based on betweennes centrality distance sampling. The main idea appears to be that the betweenness centrality measures helps identify nodes that could serve as landmarks for distance calculations, hence an distance-oriented embedding anchored on betweenness centrality is bound to perform well. Distance are resampled from walk paths, and a step of other methods based on pointwise mutual information (PMI) optimization is abandoned.
main_review: The paper presents an interesting approach to a difficult problem, yet also presents opportunities for improvement in terms of motivation, breadth of experimental comparison, and scope of experiments.

The motivation argument appears to be false: it is claimed that one should take into account remote nodes under a graph’s shortest distance metric, yet it is not clear why such remote nodes should be relevant. It is argued that PMI optimization should be avoided, as that reflects local similarity rather than distance. It is shown that this approach can accommodate an optimization objective of global distance matrix reconstruction.

The method is compared experimentally to classic graph embedding methods on several real world datasets. Out of the methods compared to, the most recent one appears to be DADL. While the work of Shaosheng et al., GraRep, is referenced several times, that is not used in the experimental comparison. Besides, most recent advances in graph representation learning, including methods such as NetMF, NetSMF, VERSE, FREDE, and ProNE, are not included in the comparison. A vague claim is made that the proposed method should outperform existing ones in other application, yet no evidence is provided.

The largest graph use in the comparison comprises some 5K nodes. There is no suggestion that the proposed embedding would scale to graph sizes typically appearing in graph embedding applications. The complexity analysis appearing in Table 1 appears to reflect a sparse graph, as discussion in Section A.5. That complexity would allow running the algorithm on larger data, yet no experiment to that effect is shown.
summary_of_the_review: The paper presents an interesting approach to a difficult problem, yet also presents opportunities for improvement in terms of motivation, breadth of experimental comparison, and scope of experiments.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this work the author(s) proposed a framework for node embeddings that captures better shortest path distances for undirected graphs. Specifically, the authors propose a new random walk framework based on betweenness centralities, and a distance resampling strategy that uses the shortest path distances, and the betweenness centrality scores and is shown to capture well shortest path distances (Proposition 1).  The authors also evaluate their framework experimentally, verifying that compared to other popular node embedding methods, it can be used to represent shortest path distances faithfully. 
main_review: 

- The authors in their abstract state "embedding-based distance prediction has made a breakthrough in both efficiency and accuracy", but the experimental results do not illustrate such a performance, at least for prior methods. 

- Continuing on the previous point, Chanpuriya et al. proved in their paper "Node Embeddings and Exact Low-Rank Representations of Complex Networks" that one can obtain low-dimensional embeddings that perfectly encode the graph structure, and thus all-pairwise shortest path distances. While the authors do not correlate the shortest path distances to Euclidean or some other distance in the embedding, it is a worthwhile competitor method as in contrast to node2vec/deepwalk is provably encoding the fully graph structure.  

- I would expect to see some toy synthetic experiments that illustrate the power of using BCs over the standard RW based node embedding methods. For instance, it is clear that the proposed RW in the dumbell graph is more likely to explore soon nodes from the second clique.  

- Following up on the example, there are plenty of other random walks one can define  that bias the random walk to escape from low conductance sets (e.g., biasing the walk towards nodes that are incident to high effective resistance edges etc.), and thus explore the graph in a more BFS-like way. 

- The computational overhead (Time and memory) occurred by the proposed framework is significant. Why would one prefer to use this approach for shortest path distance computation? While it is clear that if one has a good embedding method for downstream machine learning tasks, and this method also can yield accurate shortest path distance estimation (or even in a relative sense, as in the spirit of theorem 2), that is fine. But this is not the case here, or at least it has not been illustrated that the resulting node embeddings are useful for downstream ML tasks.  See for instance, this set of papers related to shortest path distances. 

              1. Abraham, I., Delling, D., Fiat, A., Goldberg, A. V., & Werneck, R. F. (2011, July). VC-dimension and shortest path algorithms. In International Colloquium on Automata, Languages, and Programming (pp. 690-699). Springer, Berlin, Heidelberg.
              2. Cohen, E., Halperin, E., Kaplan, H., & Zwick, U. (2003). Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5), 1338-1355.
              
- There should be at least a comparison to such combinatorial approaches, or solid experiments that show that embeddings you propose are also useful in other tasks (or ideally both). 

- Theorem 1 is not clear. How do you let k tend to infinity? What about graphs with n->inf, but with constant diameter (e.g., dumbell graph). Improving the readability of the theorem would be helpful. 
 
- Finally, the writeup can be improved. E.g., claims as the one in the abstract "It should also outperform existing methods in other graph structure-related applications" should be avoided without concrete proofs or experimental evidence.  

- Report total run times for all methods. 
summary_of_the_review: Based on my comments above, I suggest that the paper is not ready yet for publication, despite having some interesting ideas. I look forward to the authors' addressing my  comments above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new graph shortest distance embedding method. This method uses a betweenness centrality based random walk to sample paths in the graph and distance resampling step before optimization. They show that the estimated distance after embedding has a linear dependence with the original distance in the graph They also show that this embedding method preserves the shortest distance relation between points. In experimental results, they show that this algorithm achieves better accuracy than previous algorithms.  
main_review: Strength: This paper proposed a novel approach for graph shortest distance embedding. The betweenness centrality based random walk and distance resampling techniques are interesting, which more efficiently explore the graph and preserve the shortest distance information. They also provide theoretical analysis and justification for this method. The experimental results also show the effectiveness of this new algorithm. 

Weakness: The notations in section 3 are slightly complicated. Especially, some notations are used and discussed in high-level ideas without explanation and definition. 

Questions:
1. In proposition 1, should the embedding distance matrix take an opposite sign, since the current linear expression is negative? 
2. For proper parameter alpha and sufficiently large distance pair vi and vj, does proposition 1 imply a constant distance distortion for this embedding? 


After responses:
Thank other reviewers for their comments and discussions. Also, the authors' responses clearly answered my questions. I think this paper provided some interesting ideas. But, I agree with other reviewers that this paper can be improved by polishing the statement of claims and including those valuable discussions and comparisons. Especially, those comparisons with LPCA and combinatorial approaches. 

summary_of_the_review: The method proposed in this paper is interesting. Two techniques used in this new algorithms and analysis of this algorithm are non-trivial. This algorithm also achieves a good performance in experiments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a new Shortest Distance Query technique, namely, the Betweenness Centrality-based Distance Re- sampling (BCDR). The objective of this technique is overcome some drawbacks of traditional embedding-based distance prediction methods based on truncated random walks and point-wise Mutual Information (PMI). These drawbacks are a limited distance exploration and the lack of preservation of the shortest distance relation due to local optima. BCDR uses betweenness centrality to create a random walk that occupies a wider distance and uses Distance Resampling (DR) instead of PMI to preserve the relationship of distances. The paper presents theoretical guarantees of performance to address the exploration range and the intractability of shortest distance on paths. The experiments on three real datasets and simulated datasets show the performance evaluation with respect to baselines, exploration distance, and preservation of distance relation (and violation of the probability distance relation)
main_review: Among the strengths, we can mention a couple. Using the betweenness centrality to guide the random walk to scape local constraints of the truncated random walker is intriguing and based on the evidence provided it seems promising.
The method considers not only ensuring the random walk takes into account longer distance associations among nodes but also the representation of shortest distances.
With respect to the drawbacks, random walks, even when betweenness is consider, can be affected by cycles in the graph structure. How is this handle by the technique is not thoroughly described in the article.
Also, while the paper is relatively well organized, there are many details that are defer to the appendix, including the proofs of the main theorems. There should be at least a sketch of the proof in the main body of the paper to have a self-contain text.
Finally, random walk betweenness centrality is a hot topic of research and is relevant and complementary to the main idea of the paper. Thus, works in this area should be cited.
summary_of_the_review: Overall, the paper has strengths as I highlighted above that merit publication as long as the clarifications on the policy for dealing with cycles and the clarifications on the proofs is provided. I recommend also including some related work on betweenness centrality for random walks and random walk betweenness centrality.
review_title: null

Meta-review: The authors propose a new methods for graph shortest distance embedding method called BCDR based on betweenness centrality. Then they show that the method is competitive both theoretically than experimentally with existing work.

After a discussion with the reviewers and after considering the nice changes in the paper and explanation in the rebuttal we agree that the paper contains some very interesting ideas but it is not probably ready for publication. The comparison with previous works is, in fact, still a bit limited and it should be extended. In addition the algorithm should also be tested on larger datasets.
Decision: Reject