Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper presents an algorithm to learn shortest-path (SP) representation of nodes in a graph. Existing strategies to learn SP are based on random-walks that, based on the structure of the graph, have limitations in terms of performance as well as distance preservation. The authors propose a method called Between Centrality-based Distance Resampling or BCDR that accomplishes two things. First, by using a centrality-based random walk approach, it ensures a better exploration of the possible paths and thus yield better distance preservation. Second, it uses a distance resampling strategy to improve the performance of the learning task. Authors provide theoretical proofs to support the algorithmic choices in the BCDR algorithm. A comparison with several existing methods on several benchmark data sets is provided to show that BCDR allows for improvements, both in terms of distance preservation accuracy and performance (speed).
strength_and_weaknesses: Strengths:
- The paper addresses an intellectually challenging and important problem
- The proposed method is novel and is supported by theoretical arguments and empirical evaluation

Weaknesses:
- It is not clear if the implementation will be made public which could impact the reproducibility of the results

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and the ideas are presented clearly. The organization is good. Based on the related work presented in the paper and on my limited literature search, I believe that the idea of using between centrality and distance resampling for the task of shortest path based representation learning is novel.
summary_of_the_review: Overall, the paper seems to make significant contributions and presents and easy to understand paper that will be of interest to the conference audience and the community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an approach for overcoming some of the deficiencies of random-walk graph exploration in learning a low-dimensional shortest path (SP) representation of graphs.  After identifying the drawbacks of generating SP representations via random walks, they propose an alternative representation based on betweenness centrality (BC), and argue that BC allows a wider range of exploration as well as better prospects for identifying high-quality shortest paths between test points at runtime.  In order to improve the fidelity of distance relations within the learned SP representation graph, they adapt a distance resampling learning strategy originally used with random walks, and then give theoretical guarantees on the relationship between learned pairwise distances and the original graph distances.  They then provide an empirical evaluation showing substantial improvement in performance over a large range of competing methods.

strength_and_weaknesses: Strengths:

1) The proposal of BC-based walks for this problem is well motivated through a discussion of the drawbacks of uniform random walks, with excellent illustrations on example graphs.  The authors argue that although truncated random walks are relied upon as a heuristic to generate a set of representative SPs from which paths from a test pair of nodes can be estimated, such truncated random walks have only a limited exploration range due to their tendency to remain in the vicinity of the start node.  The authors address this by augmenting random walk by reweighting the probability of selection of a node according to its betweenness centrality - the number of shortest paths that contain the node as a proportion of all shortest paths in the graph (excluding paths that start or end at the node in question).

2) The authors provide a theoretical justification for their distance resampling method, showing that as the number of SP observations increases, distances in the learned embedding tend to a linear relation with the original graph distance.  The distance resampling method adapts an existing strategy for learning node-level embeddings of arbitrary paths so as to preserve point-wise mutual information. In order to encourage embeddings with more faithful distance preservation and better coverage, the authors use shortest paths instead of arbitrary paths, generated using BC-augmented walks.  Although the learning framework is essentially the same, the authors use a negative sampling regularization upon which their theoretical guarantees depend.

3) An extensive empirical evaluation against 8 competing algorithms, including most if not all of the recent state-of-the-art methods, for 5 large real-world graphs. The results are impressive, with the authors' 3 proposed variants consistently and substantially outperforming these benchmarks in terms of accuracy (mAE and mRE). Of the benchmark methods, only CatBoost was able to remain competitive.

Weaknesses (and questions):

1) Very significant presentational issues exist in the paper (see below). 

2) Close variants of SP representation learning are not considered. Can the method be applied to unweighted graphs?

3) The BC-based node selection reweighting proposed in Eq. 3 seems not to take into account the proportion of shortest paths through a neighbor of node v that also go through v itself (or equivalently, avoid v). Could such information be leveraged in improving the characteristics of the SP search, and the paths produced thereby?

clarity,_quality,_novelty_and_reproducibility: The idea of using betweenness centrality to improve SP random walks is intuitively appealing, and appears to be both novel and useful.

Although the paper is reasonably well-organized, there are significant presentational issues: frequent errors of grammar and idiom, very terse explanations in parts, undefined notation (particularly in Eq. 4), overloaded notation (sigma), and many hidden details.  Despite the complexity of the material, the paper could be much more clear and self-contained than it currently is.

Even with the presentational issues in the main body of the paper, the supplementary material does provide much useful information, including full proofs of the theoretical claims (as well as new claims not appearing in the main body), and important details regarding the data sets and implementation. Much of this should be at least referred to within the main paper.

summary_of_the_review: The idea of using betweenness centrality to improve SP random walks seems to be new, and the empirical performance is impressive and bear out the theoretical guarantees provided. However, the paper is dragged down by presentational issues and a lack of clarity and completeness in exposition. With sufficient attention to exposition, greater precision in the notation, and the inclusion of proof sketches in the main body, this could be an excellent paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose an efficient procedure for evaluating and characterizing shortest path distances by exploring a random walk procedure biased by betweenness centrality thereby better exploring important connections between communities in the random walk process used to access shortest paths (SP). Using this biased sampling strategy they infer a graph embedding Z based on the procedure based on the negative sampling approach of Milokov et al. augmented to account for betweenness centrality and they find that their procedure more accurately establish the SP distances when compared to a range of current approaches quantifying SP considering six networks with favorable processing usage.
strength_and_weaknesses: Strengths: 
The proposed BCDR provides good performance that performs well contrasted alternative procedures quantifying SP distances. 
The approach utilizing betweenness centrality is sound and the mathematical derivations and procedure proposed carefully designed. 
The embedding procedure used to quantify Z is efficient and performs well evaluating all shortest paths approximately

Weaknesses:
The approach appears rather straightforward and the importance quantifying accurately SP should be better motivated. Clearly, SP have important applications, however, it would be interesting to highlight the utility quantifying SP accurately in downstream tasks as SP is not a particularly good predictor for several graph representation learning tasks such as link-prediction, node classification, community detection etc in comparison to state-of-the-art GRL approaches. It would therefore strengthen the papers to further motivate the importance of explicitly characterizing accurately SP in terms of important downstream tasks relying on such accurate quantification. 

The approach relies on the tuning of a weight decay term \alpha. It should be discussed what the impact of this parameter is and its tuning experimentally. The approach further relies on the embedding dimensionality of Z this is not discussed nor is the impact of dimensionality accessed, this needs to be clarified. It is very unclear how these parameters should be set and their impact on the results. How were they tuned for the presented results in Table 2? 

clarity,_quality,_novelty_and_reproducibility: The paper is in general well written and clear in its presentation. The central idea using betweenness centrality seems rather straightforward and not particularly novel, however, the approach has merits as demonstrated in the experimentation when compared to existing procedures.  The reproducibility of the results are somewhat unclear relying on tuning of \alpha and the dimensionality of Z which is not discussed and carefully investigated in terms of impact. This hampers reproducibility as these parameter-settings seem critical whereas additional parameter tuning such as path lengths etc. also need to be set. The manuscript thus needs to much more carefully discuss the settings and impacts of the multiple critical parameters needed for the BCRD as also highlighted in Algorithm 1.
summary_of_the_review: A well written paper based on a simple idea of exploring betweenness centrality when quantifying SP using random walks. The central idea using betweenness centrality is not particularly innovative but the approach has merits as demonstrated in the experimentation when compared to existing procedures.  

Whereas the results are compelling demonstrating enhanced recovery of SP distances in graphs at favorable computational demands, the importance of such quantification in downstream tasks in which graph representation learning approaches (GRL) are typically considered state-of-the-art is unclear.  

The BCDR relies on the setting of multiple hyperparameters but lacks careful investigation and justification of the settings of these parameters.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a method to compute embeddings suitable for fast and exact prediction of shortest path distances in a large graph.
strength_and_weaknesses: Strengths:
- the empirical results look promising

Weaknesses
- it is unclear how the training paths ('random sp walk') are constructed from the random walks
- it remains unclear how the present work relates to path2vec both conceptually and practically


clarity,_quality,_novelty_and_reproducibility: My main critique with the current work is that I don't understand the necessity of first sampling random walks based on sampled betweenness-centrality and then extracting shortest paths from the random walks. If shortest paths are sampled anyways to estimate BC, why can't these paths directly be used as contexts for the training of the model.
Moreover, why not use shortest paths of certain max length as training data? 
The authors should either argue more clearly on the necessity of the approach or empirically show the drawbacks of the 'natural' approach.


Minor Issues:
- p1: runtime of $k$ sp-computations on an unweighted graph should be $O(kN)$, not $O(kN^2)$.
- p2: Table 1 reports asymptotic runtime and space requirements. What are the last three colums doing there? To which graph are you referring and how does this relate to the asymptotic results?
- p5: what is a 'random SP walk'?
summary_of_the_review: I recommend to reject the paper at the current point in time.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors introduce a new technique to compute shortest path embeddings of a graph. Classic approaches to compute shortest path embedding are based on truncated random walks. The authors first describe the drawbacks of such approaches and then present a new algorithm that uses random walk biassed by node centrality to obtain higher accuracy estimators.

The paper presents some interesting ideas and the experimental results on recovering the shortest path distance are nice.

Although the paper has some fundamental shortcoming that should be addressed before publication. First, the writing of the paper should be improved. The revised version is in a better state compared with the submitted one but the paper would still benefit by an in-depth rewriting. Second, the authors should motivate the problem of distance embedding more clearly. The reviewers were thankful for adding A.1.1, although all the reported examples are on planar graphs for which better distance oracles exist.

Overall, the paper presents some nice interesting ideas but it is not yet ready for publication at this stage.
justification_for_why_not_higher_score: The problem studied in the paper is not well-motivated and the quality of writing should be improved before acceptance.
Decision: Reject