BCDR: Betweenness Centrality-based Distance Resampling for Graph Shortest Distance Embedding
Authors: Haoyu Wang
Chun Yuan
Venue: ICLR 2022 Submitted (2022)
Keywords: graph representation learning
graph shortest path distance
shortest distance query
graph embedding
random walk

Abstract: Along with unprecedented development in network analysis such as biomedical structure prediction and social relationship analysis, Shortest Distance Queries (SDQs) in graphs receive an increasing attention. Approximate algorithms of SDQs with reduced complexity are of vital importance to complex graph applications. Among different approaches, embedding-based distance prediction has made a breakthrough in both efficiency and accuracy, ascribing to the significant performance of Graph Representation Learning (GRL). Embedding-based distance prediction usually leverages truncated random walk followed by Pointwise Mutual Information (PMI)-based optimization to embed local structural features into a dense vector on each node and integrates with a subsequent predictor for global extraction of nodes' mutual shortest distance. It has several shortcomings. Random walk as an unstrained node sequence possesses a limited distance exploration, failing to take into account remote nodes under graph's shortest distance metric, while the PMI-based maximum likelihood optimization of node embeddings reflects excessively versatile local similarity, which incurs an adverse impact on the preservation of the exact shortest distance relation during the mapping from the original graph space to the embedded vector space.
		
To address these shortcomings, we propose in this paper a novel graph shortest distance embedding method called Betweenness Centrality-based Distance Resampling (BCDR). First, we prove in a statistical perspective that Betweenness Centrality(BC)-based random walk can occupy a wider distance range measured by the intrinsic metric in the graph domain due to its awareness of the path structure. Second, we perform Distance Resampling (DR) from original walk paths before maximum likelihood optimization instead of the PMI-based optimization and prove that this strategy preserves distance relation with respect to any calibrated node via steering optimization objective to reconstruct a global distance matrix. Our proposed method possesses a strong theoretical background and shows much better performance than existing methods when evaluated on a broad class of real-world graph datasets with large diameters in SDQ problems. It should also outperform existing methods in other graph structure-related applications.

Under review as a conference paper at ICLR 2022
BCDR: BETWEENNESS CENTRALITY-BASED DIS- TANCE RESAMPLING FOR GRAPH SHORTEST DIS-
TANCE EMBEDDING
Anonymous authors Paper under double-blind review
ABSTRACT
Along with unprecedented development in network analysis such as biomedical structure prediction and social relationship analysis, Shortest Distance Queries (SDQs) in graphs receive increasing attention. Approximate algorithms of SDQs with reduced complexity are of vital importance to complex graph appli- cations. Among different approaches, embeddding -based distance prediction has made a breakthrough in both efficiency and accuracy, ascribing to the significant performance of Graph Representation Learning (GRL). Embeedding-based dis- tance prediction usually leverages truncated random walk followed by Pointwise Mutual Information (PMI)-based optimization embed local structural features into dense vector each node and integrates with subsequent predictor for global extraction of nodes' mutual shortest distance. It has several shorteomings. Random walk as unstrained node sequence possesses limited distance explo- ration, failing to take into account remote nodes under graph's 's shortest distance metric, while the PMI-based maximum likelihood optimization of node embed- dings reflects excessively versatile local similarity, which incurs an adverse im- pact the preservation of the exact shortest distance relation during the mapping from the original graph space to the embedded vector space.
To address these shortcomings, we propose this paper novel graph shortest distance embedding method called Betweenness Centrality-based Distance Re- sampling (BCDR). First, we prove in statistical perspective that Betweenness Centrality(BC)--ee random walk can occupy a wider distance range measured by the intrinsic metric the graph domain due to its awareness of the path struc- ture. Second, we perform Distance Resampling (DR) from original walk paths be- fore maximum likelihood optimization instead of the PMMl- optimization and prove that this strategy preserves distance relation with respect any calibrated node via steering optimization objective to reconstruct a global distance matrix. Our proposed method possesses strong theoretical background and shows much better performance than existing methods when evaluated on a broad class of real- world graph datasets with large diameters SDQ problems.
INTRODUCTION
Shortest Distance Queries (SDQs) in graphs focus on determining the minimum distance between arbitrary node pairs, defined as sum of related edge weights. Despite the fact that Shortest Path
Queries (SPQs) (Weil 2012 Sommer 2014 Wang et al.) 202T) are already renowned in graph struc- ture exploration, SDQs play an essential role in increasing applications, such as social relationship
analysis (Carlton 2020 Melkonian et al. 2021 Chen et al. 2021 Zaki et al.) 2021 Parveen &
Varmal (0221) \arma|20211, biomedical structure prediction Yuue et al. [019 Galovičová et al. 2021 Sokolowski & Wasserman 2021). learning theory (Yang al. |02 Yuan et 2021), optimization (Melkonian
et al. 2222]] Rahmad Syah et al. 2021: Jiang et al. 2021). l). etc. The key challenge in the SDQ prob- lem is the prohibitive complexity in very large graphs. e.g., for undirected dense graph with N nodes and & queries, the time complexity of A (Hrt et al. 1968) and Dijkstra Algorithm(Thee Thorup & Zwick 2004) are up to Olk and (I:N log N) for unweighted and weighted graph, respectively.

---

Under review as a conference paper at ICLR 2022
Table 1: Overall comparison of approaches to shortest distance query.
Accuracy loss of approximate methods are evaluated on facebook A.7.2) by mRE 2). N Nunumerr of nodes, T-lk length, Wwwindow size, (-number of landmarks, d-dimension of embedding space,
0, c-constant independent of N.
Objective
Method
Model
Ofi-Line Time
Space
Time
Accuracy Loss
Exact
Compress
((N)) 0( log
O(N2)
O(EN)
Exact
Index
O(N2)
O(KN log N)
Exact
Cache
O(N)
O(N) O(N2)
Approximate Oracle
O(aN++))
O(aN++
O(ka:
2(a 1)
Approximate Landmark
O N (N)
O(IN)
O(kl)
0.523
Approximate Embedding Orion
Oa log N cN)
O(dN)
((kd)
0.688
Rigel
O log N cN)
O(dN)
O(kd)
0.369
DeepWalk Walk
O log
M)
O(dN)
O(kd)
0.329
Vode2Vee
OTKN log
Mc
O(dN) O(kd)
0.299
DADL
OTKN log N M)
O(dN)
O(kd)
0.228
BCDR(ours.)
O(TKK log N (3T O(dN)
((kd)
0.177
(a)
(b)
(c)
(d)
Figure 1: Distance confusion of conventional model in embedding. (a) random walks rooted at Va have much difficulty in exploring beyond current community to ve- (b): Weight decay on walks causes instability of shortest distance since walks rooted at va have large probability to steer clear of Uú for starters and back to Ug as the end, which results in a extremely weak correlation between Va and ib despite the fact that they have an immediate edge. (c): A sufficient number of 2-hop links between Ve and Ua induce a shorter distance in embedding space than that of 2 and ea- (d): 2b and ee sharing substantial connection deserve to be mapped closed each other even if they have large shortest distance gap, while the divergence of distance between Ub, Ue and Va is also plagued with extraction.
To address this issue, surging number of approximate algorithms in a wide range of fields have been proposed in the past few years. They can be categorized into oracle-based (Thorup & Zwick] 2004 Baswana & Kavitha (2006). landmark-basee (Sarma et al.) 2010 Gubichev et al. embedding- based distance prediction methods (Xiaohan et al.) 2010, 2011] Rizi et al. 2018). Among these categories, embedding- based methods are of high accuracy with significantly reduced complexity (see TabldT), owing much to rapid advances of representation learning in graphs (Perozzi et al. 2014 Grover & Leskovee 2016).. Embedding-brie based methods tackle the SDQ problem with two stages. First, they embed local structural features into dense vector each node, which preserves the essential information for indicating where the node is. Then, for arbitrary node pairs in the training set, subsequent predictor extracts mutual shortest distance globally via their embedding tuples and minimizes the mean of square loss between a predicted value and the real one. As predictors serve as a non-linear metric in the embedding space, the performance of embedding- based models depends highly on the first stage. These methods usually embed graph structures by leveraging truncated random walk to serialize node's neighborhood in statistical perspective and maximize co-occurrence likelihood of nodes in one walk path to reflect their correlation, which is also proved to implicitly factorize a Pointwise Mutual Information (PMI) matrix (Levy Goldberg 2014 Shaosheng al. 2015).
Although existing embedding- based methods have achieved great success, they have several short- comings. On one side, random walk is an unstrained node sequence from the root, possessing limited distance exploration. This is because each transition on nodes is not implied for a specific direction to move towards beyond the root, especially after several walk steps, which is back- breaking to accommodate correlation with remote nodes under graph's 's shortest distance metric (see Figure Tap. On the other side, the PMI-based optimization reflects excessively versatile local sim-
2

---

Under review as a conference paper at ICLR 2022
ilarity, which is not guaranteed for shortest cestance-preserveee mapping from the original graph space to the embedded vector space. As a matter of fact, it exerts a too-general metric over nodes' correlation, wherein the more links paths exist between two nodes, the stronger correlation they share. That means we have many ways to claim a shorter distance for two nodes (e.g., by adding mutual edges, deleting links to other nodes) even if some of the operations do not change their actual shortest path distance (see Figures Ic [d).
In this paper, we address the above shortcomings by proposing novel graph shortest distance em- bedding method called Betweenness Centrality-based Distance Resampling (BCDR). Here, random walk paths are simulated by considering nodes' betweenness centrality on each transition for cov- ering a wider distance range of nodes. Then, a sampling process of nodes based on their mutual shortest distances performed before optimization of co-oceurrence likelihood to preserve pair- wise distance relation during the mapping from graph to the embedding space.
We summarize our major contributions as follows.
We propose Betweenness Centrality (BC)-based random walk for accommodating correlation with nodes of wider distance range under the intrinsic graph metric (see Section 3.1 To the best of our knowledge, there is no existing method that combines betweenness centrality and random walk for the graph representation. We prove in a statis- tical perspective that the transition driven by nodes' BC value tends to explore high order proximity of the root due to the awareness of local path structure.
We propose Distance Resampling (DR) strategy to preserve nodes' mutual shortest dis- tance during the mapping from graph to the embedding space (see Section[.22 We prove that by sampling node sequences from original walk paths before maximum likelihood op- timization instead of PMI-based optimization, the objective can be steered to reconstruct a global distance matrix, and for any calibrated node, it strictly preserves the shortest distance relation to other nodes on the graph.
We evaluate BCDR and compare it with existing embedding- based methods with broad class of real-world graph datasets with divergent diameters. BCDR shows a much bet- ter empirical performance in solving the SDQ problem than existing embedding- based methods (see Section 4).
2 NOTATION & PROBLEM DEFINITION
2.1 NOTATION
G = CV,V, F)) denotes an undirected graph, with V = {vi, u,,,,, Vivi} being the set of nodes and E (2) represents an undirected edge between nodes i, and Ug. A node Vs's neighborhood N; is a set of nodes with edge with V; i.e., .V; {u5l(u, 0z) E E}. We use Z to represent an embedding matrix, where d is the embedding size. For any matrix B, the symbol B; represents the i-th row of B, and B, represents the element at i-th row and j-th column. A truncated random walk W; rooted at node e; of length 1 is a random vector of (W:, W? .... ..!)) where W is a node chosen from the neighborhood of node W for k k= 1,...,,, with WP: == Ug. P; is finite set of walk paths sampled from W., and W, is the multiset of nodes on the walk paths in P..
being the set of edges. An edge eij = (v;, 22)
2.2 PROBLEM DEFINITION
An arbitrary path p of length / E N on graph G is an ordered sequence of nodes (V1, U141)) where each node except the last one has an edge with the subsequent node, i.e., (2,, U1+1) E E for
1 i < I. The shortest path Pıy is one of the paths with the minimum length i between nodes 2s and ey, with the shortest distance Dij defined as the length of p.y. The global distance matrix D comprises }
An embedding based model learns two mappings FF and G for structure embedding and mutual distance extraction, respectively, as follows.
F: G + Rd,
g (RR)) +
3

---

Under review as a conference paper at ICLR 2022
A shortest distance query Q be simply defined set of node pairs, i.c., Q {(111, U12), (121, U22)...., (V) v Q1,2)). For each node pair Uy), the model intends to find out approximation Dij ( F(e;)) nearest real Dij. The commonly used metrics of ap- proximation quality are mean of Relative Error (mRE) and mean of Absolute Error (mAE). mRE is defined as the relative loss of the prediction value with respect to the real value, while mAE measures the absolute gap between the prediction value and the real value, i.e.,
Dis -0-1 -Dul Dij
mRE = Q
mAE: = Q
Σ
Dig - Disl
(2)
(OLO))EQ
(oLP))EQ
3 METHOD
Random walk as a serialization strategy of similarity measurement has been widely used in many graph representation and learning methods, aiming to model long-range dependency of nodes (Grover & Leskovec 2016) Zhuang & Ma 2018). The optimization of maximizing co- occurrence likelihood of nodes on walk paths also yields an impressive performance structure extraction via approximating PMI matrix Levy & Goldberg, 2014). But in terms of the shortest distance representation of a graph, we contend that this intuitive approach has several lim- itations the performance. Consider walk path p (Va: Vay Bag ... vaa) E Pa sampled from a general random walk Wa from root node Va- As an unstrained sequence of nodes, the distance measured along the walk path p is not consistent with that the graph (see Figure lb i.e., for Va,, Vaj E
network-
i i j +> Daa, S Daaj where and j are indexes node Va and Va, on p and 1 S Sij Using the aforementioned unstrained walk paths for maximizing co-occurrence likelihood incurs two problems.
(3)
1. Problem 1: Limited exploration range of walks. Each transition on walks only considers local structure of the current node, causing agnostic tendency to towards or beyond the root node under the graph's shortest-distance metric after a few steps (see Figure lTa).
2. Problem 2: Intractability of shortest distance on paths. Distance measured on walk paths may not actually reflect the graph's shortest distance because of the unbalanced num- ber of links between different nodes (see Figure Ic and Id].
In this section, we describe in detail our proposed method, which is decent way of encoding shortest distances using BC-based random walk plus distance resampling strategy, and present theoretical analysis for its interpretability and efficiency. More specifically, we first present BC- based random walks and distance resampling, and then an algorithm to integrate them. We provide an intuitive complexity explanation. Additionally, we discuss the connection to Multidimensional Scaling (MDS) and graph structure decomposition in Appendix A. and A.2 respectively.
3.1 BC-BASED RANDOM WALK
Definition 1. (Betweenness Centrality) Define G = (V, undirected graph. Vi Us are arbitrary nodes in the node set V. (v)(v)) represents the number of shortest paths between Us and Vt that pass Us, and ast is the total number of shortest paths between v, and Us. Then say that BC of 0e is
(v)(
BC((:)
Σ efiigt
(4)
Ost
To address Problem I propose BC--ased random walk. As defined in Definition I BC(;;) determines the probability of u; located on shortest paths of arbitrary node pairs. Thus, we consider node with large BC value vitally significant to drive the walk move away from root node, since
4

---

Under review as a conference paper at ICLR 2022
it reveals easy way of traveling to some nodes with minimal cost. And to leverage this property, in BC-based random walk W. = (W), W.....W...... on node ta we prefer choosing nodes with the largest BC values among their neighborhoods when simulating walk paths, i.e.,
BC(W)) W/ EN
PWW 11-1)
(5)
EuReN BC((x))
where Ny; is the neighborhood of e/-
The following theorem, proved in Appendix A.3 indicates that a BC-based random walk tends to
transit from ~²t _N2 M leading to deeper exploration measured by the intrinsic graph's shortest distance. also reveals that our method performs better when the number of final nodes (V() is larger there are more links between final nodes fu (va) to connective nodes e, (va) at any h-order neighborhood of Ua-
Theorem 1. Define Ndth) = toy Day h as a set of nodes that are h-hops away from Va and (n((a) = || as the number of nodes in the set. Let the number of the nodes that have con- nection with nodes in 11h+1) (called connective nodes) be e (Va) and the number of other nodes (called final nodes) be (v())). The BC we use an approximate value by considering only the shortest path of nodes within range of k-hops locally. Let (N(Nn (va) + Nn+1 (Va)) repre- sent the probability to transit from nodes of No. (va) to NN+1(Vo) by a general random walk, and V N1+1(v,) represent that by BC-based random walk. Let P + e (v.)) be a transition from fa (Va) nodes to en( Then, for any node Va in graph G and any h > 1,
(B(Na(Va) + Nnt)(Ua)) 1 B(k) +C PR(N (Na + N4+1(va))
(6)
A2 1
lim B(k) + +C= --1
+C>0
A1
(7)
en(va)
1
A fva
A2 pn(ff(va) + (e((va))
where C 2 O. and E(va) is the eccentricity of va. E(va) max,, Dab.
3.2 DISTANCE RESAMPLING
To address Problem 2 we propose a Distance Resampling (DR) strategy, which is inspired by
Sampling-Importe Iesooortanc-eRRsamllnnn (SIR) method (Smith & Gelfand 1992). Let (z(11, 02) be random vector of the node tuple. Define p(vz) as the joint distribution reflecinng the real shortest
distance of U1, U2 on the graph. We have
max Ev. = E f(v1, 22)((112(1)))))
(8)
Vi
as a probabilistic objective for representing the shortest distance D12, where f is a normalized learnable density function determined by nodes' mutual distance in the embedding space. According to the rearrangement inequality, the above equation arrives at the maximum when f(1 12) varies consistent with p(u1, 02), which means f indicates the shortest distance metric on the graph with respect to any U1, 02 as p does. Therefore, the critical issue is to extract accurate p(U1, 22) in a graph. Let q(v.) be the joint distribution reflecting distance relation on sampled walks. We try leverage walk paths to approximate p. Here, we adopt simple but effective resampling by considering both their mutual distance D12 as well as BC values.
Without loss of generality, let represent the root node of walks and 1 be the j-th node on walk path (i.e., sampled from WA). Our objective is thus to sample from W; to generate new random vector W = (Vi!, W ..., W/ of length i. Then, each node v2 sampled from Vi can be described weighted resampling in original walk paths W; based on Dij and BC(r;), i.e.
p(eyle:)
E Euyrp(yyoo))//u]]
Σ
Σ
f(a u;)a(us ( (x)
EV.
Di PC
~ Σ NEV eyEW
Σ
f(0, ((r,))))(11)1))
Emew. D. (C(e))
5

---

Under review as a conference paper at ICLR 2022
where is hyper-paramene parameter of the weight decay coefficient paths.
Reminiscent of previous discussions on relating maximizing co-occurrence likelihood with matrix factorization, we demonstrate the connection between the above intuitive design and graph shortest distance metric. As we perform distance resampling for walk paths, the objective to learn an optimal node embedding is therefore interpreted as
arg max 2
Zj)]
(10)
p(s)) (y VVEV
o (Z.Z,) + AE (ww o (
Thereinto, f(Z,, 2,) log o (Z,Z,) pv (v<(e)) is the distribution of negative sampling. our algorithm, PN be specified as weighted random sampling over all occurred nodes in W; (sim- ulated based on Equation 5) by occurrence frequency. i.c.,
(N((ul #( occurs in W.)
(11)
#(W)
where #(-) is counting function indicating the number of occurrence times of specified nodes, i.e., the cardinality of a sampled set.
Proposition 1. Define G = EV, as an undirected graph. Zivix d is the embedding matrix of V corresponding maximizing likelihood objective Ex Z,)] defined in Equation TO (v(vva)a) is the negative sampling distribution of from W. simulated by Equation 77 Let the weight decay coefficient in distance resampling a, 0 < a < Then, the inner product of em- bedding matrix corresponds to global distance matrix, i.e. ZZT D. For any Vo and any us that is n-hops away from Va. the distance between them in the embedding space varies linearly with respect to distance n, namely,
Das n log a log A
(12)
where A is a constant independent of vb-
Proposition is proved in Appendix A.4
Proposition I indicates that optimization of Equation 10 conforms to reconstruct global distance matrix where nodes far away from each other the graph under shortest distance metric(i.e., large Dab) should be mapped with large distance in the embedding space(i.e., large Das). We can also conclude that D.s varies linearly with respect to the distance n between two nodes, while is constant independent of 2/ but related to Ca. which means when we fix the source destination) node as any destination (or source) node ub's 's distance with could be compared with each other (we call that distance is measurable with respect to calibrated node v.)).
Consider the preservation of shortest distance relation. Some studies metric learning (Hermans) al. 2017 Zeng et al. 2020) have revealed that tuple of samples (Va, Ub M2) being easy to learn means If 2/ shares strong correlation with 2,,, the distance between U; and c, in the embedding space should shorter than that of v. and Va- With this property, we have the following theorem, which indicates that our method is consistent with distance relation under intrinsic graph metric. This will be used in the prediction task described next.
Let D be a global distance matrix defined on graph G and Dub be graph shortest distance between node and Ub- Then for any nodes Vay Ub, Vi. E G.
Theorem 2. Each symbol here follows the definition Proposition ?
(Dab Dac) -Dacel
(13)
The proof is presented in Appendix A.5
3.3 ALGORITHM
Our BCDR algorithm is presented in Algorithm It contains three steps. First, pre-computation of the BC value (line 21) is required for each node on the graph. Second, for each node e; we sample batch of walk paths P; guided by the BC value according Section 3.7 (line to 20). Meanwhile,

---

Under review as a conference paper at ICLR 2022
Table 2: Statistics of graph datasets and their train & validation & test sets.
RoBCerange of BC, mBC-mean of BC, L-landmark nodes,
T 7ttrain set. V-validation set, È-test set.
E]
E E
Diameter
RoBC
mBC
L
[7]
[V]
Cora
708
10, 787
3.9834
21
375.20
2.7174
100
100 x
800 30
1. 1,600 10
Facebook
4. 039
176, 437
21.846
8
1,306.9
0.89931
100
100 V
800 50
1, 1,600 20
GrQc
242
30,042
5,7310
17
148.43
2.7219
100
200 x [
800 70
1,600 x 30
distance relation of each node with is also recorded for subsequent resampling. Third, for each node we resample nodes in W. by their distances with v and BC values to formulate P. (line 25 to 34), which is optimized by maximizing pair- mir- co-occurrence likelihood (line 37). This embedding algorithm takes O Wue [V] log |V++ (wnn wou [V of time complexity and O(winlin + Wous of space complexity for any sparse graph (detailed analysis is presented in Appendix [.6 The above result reveals a feasible way of reducing time complexity by just taking larger Win kn and smaller Wouthout in BCDR. This practice is applied in our experiments.
Algorithun BCDR Enbeddiag, Alaocittm
Impust: impul graph
eubolaaing inpat cemple Sius tnlppu sample thes inpst lengih cuppet longlt weightt dessy nomailzstion
Det oc. Xa.k (G. D,D, 11:
pre-ontiuut BC of each mode
(C((s)
for wath it to ii Via
13 Wilk path or 1
visit rigs set 8, -m (1)) cureet mode to to lmugth om re Izegth cm Da for ic do while c <he de
cistsnce mop 2) (sy O0
A (oyley A.A.Aty y 8))
D), Kaik (G. Mon
tben
by c. D.Acg
nomullie Pory edfinailty + Da.ry E/2
2) softmaxd
Pory
E.M
pdoyles) - Rlis -5
oic
sumple by Ao by Bo-)
plyyln) e....... end end
(isl (3]
mint D. 1.6
sample walk pals P. (fi,itiy -Ryy (olllutthhhh append P.
2it,, (ul. v. Dulksps for toss lites.
Dite +1
end
ta & Ba 2.
x Equation
mn rml
2
4 EXPERIMENTAL EVALUATION
In this section, we evaluate our model's 's performance with several graph datasets and compare it with conventional embedding-basse based methods for SDQ tasks.
4.1 DATASETS
We test model using three real-world graph datasets well some simulated datasets. As this paper focuses on the shortest distance prediction of connected and undirected graphs, we make a trivial change for some directed graphs by simply eliminating the direction each edge. For graphs with multiple connected components, we repeatedly add one edge between two unconnected components until the whole graph is connected. The graphs we use are of complex inner connections and divergent diameters. The basic information of these datasets is outlined in Table 2 (columns 2 to 7). The detailed information is presented Appendix A.7
We define T, V. and & datasets for train, validation, and test, respectively. Each of them is composed of (14, uj, Dzy). As simulations of the above sets in huge graphs have to be of O(VV)) or less complexity, in experiments, we initially select group S of nodes as sources, and for each source U; S, a destination set D with their shortest distances to the source is randomly collected. Then, |S| [D,] input node pairs are simulated. The detailed setup for each dataset is presented in Table 2 (columns to 11).
4.2 PARAMETER SETUP
We compare our method with conventional graph embedding models based on random walk as well matrix factorization (see Appendix A.8). We simulate 40 walks each node for random walk- based methods, and each walk is truncated at a length of 40. Sliding window size and negative sampling size are fixed at 20 and 5, respectively, for each dataset. Node2Vec takes hapereparameter
7

---

Under review as a conference paper at ICLR 2022
Table 3: Performance comparison of embedding- models
Cora
Facebook
GrQq
LLE
5.6265
0.0400
0.8445 + 0.0086
1,9921 + 0.0731
0.6841 + 6.0029
4.8849 + 0.1003
0.7105 + 0.0165
GF
5.6219 + 0.0876
0.8110 + 0.0111
1.8713 2 0.0717
0.0717
0.6383 = 0.0284
4.8562 + 0.0516
0.7125 2 0.0084
5.6393 0.0782
0.8455
+-00132
2.0312 0.0625
0.6998 0.0248
5.0046 0.0242
0.7366 0.0044
DeepWalk
1.5183 + 0.065-1
0.2125=
0.9323 + 0.0272
0.3289
- 0.0137
2.8002 + 0.1449
0.4169 + 0.0227
Node2Vec
1,3022 0.0236
0.2115
4-00088 0.0038
0.8541 + 0.0436
0.29913
0.0166
1.5156
0.06811
0.2278 + 0.0087
DADL
1.1349
0.0180
0.1790
0.0001
0.6150 + 0.0325
0.2279
0.0135
1.3624
0.1366
0.2033
0.0183
BCDR
0.9768 0.0245
0.1605
+ 0.0443
0,4804 + 0.0406
0.1770 + 0.0156
1,0490 + 0.06634
0.1684 0.0058
p = = Regularization r of GF set 1.0. DADL takes the Hadamard operator for embedding aggregation. Like previous research (Zhuang & Ma 2018), linear regression is utilized as predictor for general graph embedding models.
For our model, we take the same configuration as previous random bask-based models using input walk length in 40 and input sample size Win = 40. In order to keep complexity of parameters equal to or even less than that of baselines, the multiplication of output length lout and output sample size Wout fixed at 40, with lout = 10, Wout 160 for Cora and GrQe and low 40, Wout = 40 for Facebook. Mcanwhile, the weight decay coefficient is set to 0.1 for Cora and GrQe datasets and 0.98 for Facebook. To avoid dramatically unbalanced values BC, we also take smoothed normalization (7 True) in all datasets except Facebook. Finally, all of the above models use the Adam optimizer with a learning rate 6 = le for training, and embedding dimension is fixed 16 for every dataset.
4.3 PERFORMANCE OF PREDICTION ACCURACY
To compare embedding-basse methods, we train each model on each dataset up 500 iterations and save the results every 10 epochs. The best models are selected by their mAE and mRE scores on validation set V. Each model is evaluated 5 times independently on each dataset, and their average performance is recorded. The resulting mAE and mRE are reported in Table 3 Some comparisons with the latest GRL methods and further discussion are presented in Appendix [A.9 and run-time
test compared with general random walk is reported in Appendix AA We can see from the table that our model outperforms previous models significantly for all three datasets.
4.4 RESULT OF EXPLORATION DISTANCE
exploration distance under intrinsic graph metric plays an indispensable role in modeling wider range of node correlation. Here, we compare our BC-based random walk with existing renowned walk strategies, including DeepWalk (Perozzi et al., 2014 Zhuang & Ma 2018). Node2Vec (Grover & Leskovec) 2016), and Random Surfing (Cao et al. 2016). We use TG(20, 1,3, 10) as a test graph of large diameters. We randomly sample 20 root nodes and, for each root, simulate 10 walks with length 10 to show how many nodes in different order proximity visited. The ideal situation for a batch of walk paths with length / is to cover up to nodes ( hop away from the current root. The results are shown in Figure From the figure, we can see that our BC-based walk is much more competitive regarding exploration distance. A further illustration of diverse graph structures is presented in Appendix A.11
As stated in Section 3.1
A.11
4.5 PRESERVATION OF DISTANCE RELATION
We have also evaluated the property of shortest distance preservation during the mapping from the original graph space into embedded vector space. First, we test distance variation in the embedding space when adjusting the shortest distance between nodes on the graph, taking the same configu- ration of simulation dataset TG(20, 1, 3, 10). Distance in the embedding space is measured by inner product Z for any node e, and Uy. We initially train embedding vectors using walks sim- ulated by each model and randomly sample 20 source nodes with 100 destinations for each source. The results are shown in Figure which indicates that our model has a better tendency to maintain linear distance relation for the mapping.
8

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
Figure 2:
Exploration distance of different random walk strategies tested graph TG(20, 1, 10).
(a): general random walk in DeepWalk. (b): Nece2Vec. (c): Random Surfing. (d): BC-based random walk(ours.).
(
(b)
(c)
(d)
Figure 3: Distance relation during mappings when taking different random walk strategies. (a):
general random walk in DeepWalk. (b): Node2Vec. (c): Random Surfing. (d): BCDR(ours.).
Second, try to find out how much the probability distance relation is violated in the embedding space. We randomly take 10000 node triple (ea 2/ v,). and record if they violate Equation 13 The results shown in Figure The figure confirms that our model is much more satisfactory preserving distance relation during mappings.
(a)
(b)
(c)
(d)
Figure 4: Distance preservation in the embedding spaces of different models. (a): general random walk in DeepWalk. (b): Nede2Vec. (c): Random Surfing. (d): BCDR(ours.).
5 CONCLUSION
In this paper, we propose a novel graph shortest distance embedding method called Betweenness Centrality-based Distance Resampling (BCDR). It improves the graph embedding for the shortest distance representation with two components we propose in this paper. The first is Betweenness Centrality-base random walk to accommodate long-distance correlation on graphs by covering wider range of nodes under the intrinsic graph metric. The second is distance resampling strategy to preserve shortest distances during the mapping from graph to the embedding space via recon- structing global distance matrix. The experimental evaluation indicates that BCDR possesses better capacity than existing graph embedding methods to extract distance structure from original graphs. BCDR can be integrated into graph-based learning models (especially in graph neural net- works), which should improve their performance on graph structure recognition. This will our future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Principal Component Analysis and Factor Analysis, pp. 150-166. Springer New York, New York, NY. 2002. ISBN 978-0-387-22440- doi: 10.1007/0-387-22440-8.. URL https://doi.
org/10. 10./00.01 0000/100700000 387 22440-24222 8_
A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola. Distributed large- scale natural graph factorization. In Proceedings of the 22nd international conference on World Wide Web, pp. 37-48, 2013.
S. Baswana and T. Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 591-602, Oct 2006. doi: 10. N0.1109/FOCS22006.22
David M Blei, Andrew Y Ng, and Michael Jordan. Latent dirichlet allocation. the Journal of machine Learning research, 3:993-1022 2003.
Ulrik Brandes and Christian Pich. Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos, 17(7):2303, January 2007. doi: 10. 10.1142//021817777001118888 84000
Shaosheng Cao. Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Jason Carlton. The shortest distance between two people is story: Storytelling best practices in digital and social media marketing. Journal of Digital & Social Media Marketing, 8(2):108-115, 2020.
Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Ad- vances Neural Information Processing Systems, 33, 2020.
Yu Chen, Hanchao Ku, and Mingwu Zhang. Pp-oeq: A distributed privacy-preserving optimal closeness query scheme for social networks. Computer Standards & Interfaces, 74:103484, 2021.
Mária Ercsey-Ravasz and Zoltán Toroczkai. Centrality scaling in large networks. Physicul review letters, 105(3):038701, 2010.
Robert Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962.
Lucia Galovižová, Petra Borotová, Veronika Valková, Nenad I. Vukovic, Milena Vukic, Jana Stefániková, Hana Dáranová, Przemystaw Euuassz Kowalc7ewski, Natália Čmiková, and Miroslava Kačániová. Thymus vulgarís essential oil and its biological activity. Plants, 10(9): 1959, 2021.
Rainer Gemulla, Erik Nijkamp. Peter J Haas, and Yannis Sismanis. Large-scale matrix factorization with distributed stochastic gradient descent. Proceedings of the 17th ACM SIGKDD interna- tional conference Knowledge discovery and data mining, pp. 69-77, 2011.
A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In the 22nd ACM SIGKDD International Conference, 2016.
A. Gubichev, S. Bedathur, S. Seufert, and G. Weikum. Fast and accurate estimation of shortest paths in large graphs. In Proceedings of the 19th ACM Conference Information and Knowledge Management, CIKM 2010, Toronto, Ontario, Canada, October 26-30, 2010, 2010.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions Systems Science and Cybernetics, 4(2):100-107, 1968.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense the triplet loss for person re- identification. arXiv preprint arXiv: 0703.0773777777 2017.
Shijie Jiang, Yang Wang. Guang Lu, and Chuanwen Li. DIsm: Distance label based subgraph matching on gpu. In Asia- Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference Web and Big Data, pp. 194-200. Springer, 2021.
10

---

Under review as a conference paper at ICLR 2022
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap. stanford. edu/ data June 2014.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 11:2177--2185 2014.
Vardges Melkonian et al. Mathematical models for social partitioning problem. American Journal of Computational Mathematics, 11(01):1, 2021.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv:1301.3781, 2013a.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp- 3111-3119, 19, 2013b.
Ruksar Parveen and N Sandeep Varma. Friend's recommendation social media using different algorithms machine learning. Global Transitions Proceedings, 2021.
B. Perozzi, R. AI-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. Pro- ceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Min- ing, 03 2014. doi: 10.1 0..144/2223330022222222
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pp. 459-467, 2018.
Bayu Rahmad Syah, Mahyuddin Nasution, Erna Nababan, and Syahril Efendi. Sensitivity of shortest distance search in the ant colony algorithm with varying normalized distance formu- las. TELKOMNIKA Indonesian Journal of Electrical Engineering, 19:1251-1259, 08 2021. doi:
10. WEWTTTEKKOOOAAVVY 18877.
Fatemeh Salehi Rizi, Joerg Schloetterer, and Michael Granitzer. Shortest path distance approxima- tion using deep learning techniques. In 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 1007-1014. IEEE, 2018
S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500))2323- 2326, 2000.
A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. ftetch-based distance oracle for web- scale graphs In Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010, New York, NY, USA, February 4-6, 2010, 2010.
C. Shaosheng, L. Wei, and X. Qiongkai. Grarep: Learning graph representations with global struc- tural information. In Proceedings the 24th ACM international on conference on information and knowledge management, pp. 891-900, 2015.
A. F. M. Smith and A. E. Gelfand. Bayesian statistics without tears: A sampling-resampping per- spective. The American Statistician, 46(2):84-88, 1992 doi: 10. URL
992. . 1 04 75856
Marcus Sokolowski and Danuta Wasserman. A candidate biological network formed by genes from genomic and hypothesis-free scans of suicide. Preventive Medicine, 152:106604, 2021.
Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 46 (4):1-31,2014
B. Tenenbaum, V. De Silva, and C. Langford. A global geometric framework for nonlinear dimensionality reduction. science, 23115530) 2000.
M. Thorup and U. Zwick. Approximate distance oracles. Journal of the Acm, 52(1), 2004.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference, pp. 539-559-44 548, 2018.
11

---

Under review as a conference paper at ICLR 2022
Ye Wang, Qing Wang, Henning Kochler, and Yu Lin. Query-by-sketch: Scaling shortest path graph queries on very large networks. In Proceedings of the 2021 International Conference on Manage- ment of Data. pp. 1946-1958, 2021.
Fang Wei. Tedi: efficient shortest path query answering graphs. In Graph Data Management: Techniques and Applications, pp. 214-238. IGI global, 2012.
Z. Xiaohan, A. Sala, C. Wilson, Z. Haitao, and Z. Ben Y. Orion: Shortest path estimation for large social graphs. In Proceedings of the 3rd Wonference on Online Social Networks, WOSN' 10, pp- 9, USA, 2010. USENIX Association.
Z. Xiaohan, A. Sala, Z. Haitao, and Z. Ben. Fast and scalable analysis of massive social graphs. CoPR, 07 2011.
Yiding Yang, Xinchao Wang, Mingli Song, Junsong Yuan, and Dacheng Tao. Spagan: Shortest path graph attention network. arXiv preprint arXiv:2101033644 2021.
Huilin Yuan, Jianlu Hu, Yufan Song. Yanke Li, and Jie Du. A new exact algorithm for the shortest path problem: An optimized shortest distance matrix. Computers & Industrial Engineering, 158: 107407, 2021.
Xiang Yue, Zhen Wang, Jingong Huang, Srinivasan Parthasarathy, Soheil Moosavinasab, Yungui Huang. Simon M Lin, Wen Zhang, Ping Zhang, and Huan Sun. Graph embedding biomedical networks: methods, applications and evaluations. Bioinformatics, 36(4):1241-12511 10 2019. ISSN 1367-4803. doi: 10.100//ooonffrmmaiiccct///////
http://t.........../.e/./.. URL/actss: /tllattps:///ci.rrggg/ org. 1093/
bioinformatics:/onn
Abeer A Zaki, Nesma A Salch, and Mahmoud A Mahmoud. Performance comparison of some centrality measures used in detecting anomalies in directed social networks. Communications in Ctaristic-SSimllttin and Computation, pp. 1-15, 2021.
Kaiwei Zeng, Munan Ning, Yaohua Wang, and Yang Guo. Hierarchical clustering with hard-batee batch triplet loss for person re-identification. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 13657-13665, 2020.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph- based semi-supervised classification. In Proceedings of the 2018 World Wide Web Conference, pp. 499-508, 2018.
A APPENDIX
A.1 CONNECTIONS TO MDS
Our algorithm also shares some connection with conventional MDS methods in global distance met- ric. Take view of original MDS. Input data X distributes in agnostic high-dimensional euclidean space and mutual distance between samples is extractable as a global distance matrix D A ap- proximate distance matrix DY calculated by embedding matrix Y endeavor to be optimized closest to D by Frobenius norm, i.e.,
minl =I - YY
(14)
Here, we suppose D and Y have been double-centered for stability, and finally, Y could be de- duced as the group of top-d leading eigenvectors in DX Then, as non-linear version of MDS, Isomap (Tenenbaum et al., 2000) generalizes D as distribution on manifold and utilizes short hops measure the mutual distance between samples. Deriving from the above idea, we regard the global distance matrix x as a canonical metric on graphs and exert embedding matrix Z to reconstruct it. Different from previous work, we encounter prohibitive complexity acquire all ele- ments in D X and leverage an iterative process to approximately minimize the accuracy loss between D and x
12

---

Under review as a conference paper at ICLR 2022
Cora Tacebokk
Sora ErSr
13-
0.0
13-
0.6
6.2
8.0
1.80
1500
750
1750
(a)
(b)
Figure 5: Converge analysis LPCA on different datasets (a): LPCA loss. (b): Frobenius norm error
Table 4: Converge time and Accuracy Comparison between LPCA and BCDR(ours.).
Cora
Facebook
GrQc
Time
mRE
Time
mRE
Time
mRE
LPCA (Chanpuriya al. 2020)
82.60s
0.3445
2587s 774.0s
0.8272 0.1599
1163s 264.8s
0.3952
BCDR(ours.)
113.7s
0.1576
0.1603
A.2 CONNECTIONS TO GRAPH STRUCTURE DECOMPOSITION
newly published work (Chanpuriya al. 2020) provides an exciting perspective embed com- plex sparse graphs perfectly into low-rank representations, which is helpful for downstream ML tasks. Nevertheless, we need to address the limitation of LPCA in shortest distance prediction as follows.
First and most importantly. should be clarified that perfect representation graph structure is not equal to that of graph shortest path structure, since they have large calculation gap. According Floyd-Wared Warshall algorithm (Floyd 1962), even if each node aware of all related path structures, inference of the exact shortest path structure also needs up O(N*) complexity. Second, LPCA has poor embedding performance on some relatively dense graphs, despite converging fast on sparse graphs. We test this method the three real-world datasets used in this paper, and illustrate the converge curve in Figure 3 The converge time is reported Table The results show LPCA meets bottleneck the centive-denee graph (Facebook) and consumes long time converge.
Compared to the above method, the motivation of this paper is to directly embed graph shortest distance matrix with sub-linear time complexity for fast and accurate online queries of shortest. distance. To the best of our knowledge, there no existing embedding method that could directly and perfectly represent shortest path structures in linear time. Moreover, our method takes a more flexible objective to represent shortest distances, since only high-level restrictions are implicitly exerted on the embedding space by Equation and 13
A.3 PROOF OF THEOREM 1
Proof. We simplify symbols (v.))), en (va), f'r (va)
Nn, Ch Sn. for short.
(ow)
NA = #(
U
{sylos E A
i=h
(15)
NA = #(
U
(uyle =(
i=max (0.A--+1)
13

---

Under review as a conference paper at ICLR 2022
According to definition in the theorem, we have N₁, en+thh fu. Since only en nodes could travel from Nh to N4+1, We firstly consider PR(EA + eh+1 Cc/, - N1+1) and P3 (e - ea+1/Ch - NN+1).
For general random walk, the choice of destination is based uniform sampling, thus causing
Pu(en- En+1len Nu+1)
Ch+1
(16)
N4+1
For BC-based random walk, we need calculate BC value of ca+1 and fx41 nodes for starters. Let (C(En+1) and BC(J++1) represent the BC value of nodes in ex+1 and Sn+1 respectively, and the 3 correspond legal shortest path counts comes from 4 sources as {Nr Na+2h. {NA, Na+1).
{N++1 N and {N++1 NN+1J. And we BC((- + -}) the BC gain from the specified source, then
BC([NA - NN+2)) NaNn+2
BC([Na - Nn-13) = - -Na[Jnt1 0 (x+11
(17)
BC((Nx+1 + Nn-2)) Nn+2(fu41 11413!1)
BC((N + Nx+1)) = 3(
where ( means average BC gain between nodes in eh+1 and N 1+2. and B.22 means average BC gain between nodes both in ea+1, which are constantly related with G. Therefore, we have
BC(e = NNN + (N + 1 + NN42/141 + N
(18)
Likewise, we calculate
BC(fx+1) =N 2 0+ (J + eeti .0) + Nx+2(131) + eati -0) + 1
=(NA 7 + 1
((2)
(19)
To compare the above BC((e+1) and BC(f++1).
BC(fn+1)
(N + N + +N2
(20)
(C(e
NaNA+2 + (ÑA + Nx42)en (00) + N442f44 + N N7
note that for any Nj and N(ww) = No N= - Ny where j, E (0, E(va),
N₂ lim c(k) = 0
lim
(21)
k+E((v)) N(m.g)
1-
Equation 19 is reduced to
BC(fk+1)
2((k))()) + +c(22))(() + 2c ( + c(k)snt1 + c(K2))!?) = 20(2)((k)
(22)
BC(eN+1)
Then, we perform weighted random sampling based on BC and get
Ch+1
PB(c, + Cxtilen N2+1)
Cat1 + 2fh+119 ((()))
(23)
14

---

Under review as a conference paper at ICLR 2022
Now, consider the relation between Pa(N,, Nh - N1+1) and (N - eN+1lNa N1-1).
PB(NA - Nn+1) Pe(eN)pB(en + Nht1)
PR(N, + Nh+1) PR(EN)PA + Nh-1)
PN(N - cn) PBl (N fh)PB( (fp - ch)
PR( + en) + pn Nn-1 - (n) - e
=1+ [pn(Na-1 + en. pn (N
en)] presn + eh.
Pn(NN-1 + en. + PM P - fn)pr((n - ch)
Pn(fn + En.e
(24)
PR(NN-1 + ep) + pR 1- - [n]pR([n + en)
fa - 2/n <(k))[] 22
-pn(Jh + en)
= +
(1 fn len + 2/r c(H))pp((h - en)
pR(fA + en)E
pn P cn) + Pn ft)PR(Jh + ex)
Let C' (N,,, 1-m%))+x(N, (f B(k)
pa((-
fu/1-20,07 pn Since
(1+ th % +2 (()))
C' is non-negative value independent of k, finally get
(N + Nn+1) = =1 B(k +
(25)
PR (R - Nk+1)
where
B(k) +C= A2 -1 C.
lim 1-1((=))---k
(26)
A
A.4 PROOF OF PROPOSITION
Proof. Initially, we rewrite the negative sampling item of Equation 10
E Bus-pw(oulss 2.ZD)) (-Z44=))))
Σ (N (us) (es) a ((,Z
ds
(27)
= ((
Σ
PN (r(c of (-z,Z%))
o.EWMMes
Then, for each pair of v; E V and Vy W,, we get independent objective by combing similar items in overall likelihood expression Ep. [Z; Z;)], and get
(0,-p/((Zi,) = Σ Σ ((v,,
W.E VeEW,
(28)
C(v;, = p(ri, Uz) log (- (Z,ZZ,)) + Xp(r:)px(()(e)) log al ol
Let D ZZT, for each node pair (Vay 2b) with mutual shortest distance Das,. consider
Dab Z, = arg max L(va, 0b) Ze 2n
(29)
Suppose vi is n-hops away from Ua, and denote BC(v)) by 7b. according to Equation
p(u. v.) = p(v.) p(vp v.)) = p(va) a amm
(30)
Note that PAv (vy) (ea) is negative sampling in walk set W, W. (Equation 11 which selected by BC- based random walk locally restricted to e, according Equation 5 we have
pN (Vslva) k(va)1
(31)
15

---

Under review as a conference paper at ICLR 2022
where x(va) is related with the neighbor structure of Va- Then, Equation 29 could be described as
Dab
arg max p(va) (aaaaaa"n" Tb log a (Das) + Ap(v))n(Ua)) 77 log a (-Dat)
(32)
Dab
Solve the above problem by just let dL(va.va) be equal to zero, i.c..
aD
Vl(va: vb) = p(va)a" Das) )p(ua)n(ws)rz0001 + Dut) = 0
(33)
aD After some simplification, we get
Dah n log An(Ua)
(34)
Let A = -Ax(U,) and there holds
Dab n log a log A
(35)
A.5 PROOF OF THEOREM 2
Proof. Let Up and U2 in graph be n and m-hops away from v respectively. In terms of node pair (Va, Ub). as proved in Proposition 1 their mutual distance Dab in the embedding space varies linear with respect to the graph shortest distance n, i.e.,
Daail 'n logga a log Al -n loga + log A
(36)
Likewise, we have for (Vas ve)
|Dael Im log a log A| = - log a log
(37)
where 0 < < and A is independent of and ve.. Then, consider the distance relation of vaa %
and Vee there holds
(Dab - Doe) (Dbe)) = - (m)mmm - n)) log a = log a (n - m)² N
(inmm)²
(38)
A.6 COMPLEXITY ANALYSIS OF BCDR EMBEDDING ALGORITHM
We analyze the complexity of Algorithm as follows.
The first step depends on the algorithm used for BC calculation, wherein some approximation meth- ods could reduce complexity to O(VV)) or O log [V))(Baandes & Pich 2007 Eresey- Toroczkai 2010). Then, in the second step, for each walk rooted at each node (line 23), we use loop(line 2 to 20) up to win times for generating nodes the walk. Normalization of (lie to 18) is calculated for Lin times for each node, and summation of y is up to O(E) during the whole routine. Therefore, it takes totally Ow IVI + (E)) time complexity. Fi- nally, as for the third step. line 26 to 33 re-weights explored area of every node v; which need loops up wonknn/V V times. For the sake of resampling Woutlout nodes, line 34 also requires nor- malization by O Oo Line 37 use maximum likelihood optimization which occupies Ow IV |o [ Woutloue/ V || (E') time complexity (Mikollo al. 2013a). As for space complexity, distance map D; and p(u; (o;) are stored temporarily up to Owwintia) while visit sign set S, is up to O(w,)) For dumped and resampled walk paths, O((wan + Wouthen (VD) space is required. Finally, our embedding algorithm takes (Wootl?u 2 V log [V] +w + louel [ (F() time complexity and O(winlen oouthont [V]) space complexity. Especially, for sparse graph, time complexity is reduced to OW out [V] VVIlog log [V| + (Winlin + Woutlout)]V]])
A.7 COMPLEMENTARY INFORMATION OF DATASETS
This part provides detailed information about graph datasets we used, and presents some visualiza- tion result in Figure 6
16

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(c)
(f)
Figure 6: Visualization of graph datasets. (a): Cora. (b): Facebook. (c): GrQe. (d), (e), (f)
1,, 1,3, 10).
A.7.1 CORA
Cora graph dataset describes the citation relationship of papers, which contains 2708 nodes and 10556 directed edges among them. Each node also has predefined feature with 1433 dimensions.
A.7.2 FACEBOOK
Facebook dataset[[eskovee & Krevl 2014) describes the relationship among Facebook users by their social circles(or friend lists), which is collected from a group test users. Facebook has also encoded each user with reindexed user ID to protect their privacy.
A.7.3 GRQC
Arxiv GR-QC (General Relativity and Quantum Cosmology) collaboration network Leskovee & Krevl 2014) is recorded from the e-print arXiv in the period from January 1993 to April 2003, which used to represent co-author relationship based on their submission. We suppose undirected edge (vs, vÿ) if an author co-authored paper with another author dy. If one paper is owned by k authors, complete graph of k nodes is generated correspondingly.
A.7.4 TEST GRAPH (TG)
We define TG r, as a parameterized graph simulation for SDQ tasks. ols is the number of sub-graphs represent communities, and is the number of nodes in each community. e and r determine the inner and outer connectivity of each community, respectively. TG is guaranteed to be an undirected and connected graph in our experiment, which is also expected be sparse and of large diameter. Some simulation results of TG(20, 1,3, 10) that we used in Section 4.4 and are presented in (ig (e), (f).
A.7.5 OTHER GRAPHS
We also use some other graphs with diverse structures this paper. The visualization these graphs shown in Figure 7 We deseribe each graph follows.
17

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
(c)
(f)
Figure Visualization of some synthetic graphs with diverse structure. (a): circle graph. (b): triangle graph. (c): tri-circle graph. (d): tree graph. (e): spiral graph. (f): net graph.
Circle Graph: a graph that contains several circles of different sizes. The simulation of circle graphs takes iterative process where for each newly introduced circle, there are limited number of nodes (called exit nodes) connected to the previous node set.
Triangle Graph: a graph possessing several cliques which are linearly connected mutually.
Tri-circle Graph: graph that combines the properties circle graphs and triangle graphs.
Here, each cirele is simulated by connecting triangle sub-graphs end to end.
Tree Graph: graph that is generated from one root to several leaves recursively. There is no cycle in tree graphs. To control the tree structure, we define splitting probability that is decayed exponentially with current depth.
Spiral Graph: a graph shaped like spiral line. We first simulate line graph and add edges between nodes with exponentially increased distances by their indices on the line.
Net Graph: a graph containing grid-like connections between nodes. We define small probability to drop those edges stochastically.
A.8
BASELINE ALGORITHM
We outline all the baseline models used in performance comparison as follows.
A.8.1 LLE
Locally Linear Embedding(LLE)) Roweis Saul 2000) is an effective method of dimensional re- duction that preserves the local linear combination property of nodes. In contrast with previous PCA[Jll (002) and LDA (DA Blei et al.) 2003) which are guaranteed to discover an optimal reduction in euclidean space, LLE that addresses local distance relation gives more compact representation for non-linear manifolds.
A.8.2 LE
Analog to Laplace-Beltrami Beltrami operator on manifolds, Laplacian Eigenmap(LE)) Eieenmap (Rwweis & Saul 2000) leverages graph Laplacian matrix to generate embedding vectors. The objective of L. is minimize
18

---

Under review as a conference paper at ICLR 2022
Table 5: Performance comparison with other GRL techniques
Cora
Facebook
GrOe
mAA
mRE
mAE
mKK
mAE
mKE
GraRep Shanshens 2
2.4036
0.3444
2.7975
4.2283
0.0088
1.5179
VERSE Tists e 2m
223466
0.4140
1.1653
0.38050
3.39925
0.4761
LPCA
CTampany e 21A1
2,3730
01.3445
2,0306
0,8272
2,7971
0.3002
0.1605
0.4804 00446
0.005K
mutual distance edges by Le loss, which maps nodes with more first-order links closer to each other.
A.8.3 GF
Graph Factorizationn(i)))
et al. 2013) utilize matrix factorization methods(Gemulla et al.,
2011 to deal with graph structure exploration. By approximating the graph adjacency matrix on bundle of random nodes, GF is of high efficiency for large graphs.
A.8.4 DEEPWALK
DeepWalk(Peree Perozzi al. 2014) is random walk-based embedding method to represent graph structure. This method derives from skip Ship-gram(Mikolo et al.] (201a)) and nega- tive sampling [Mikolov et al. 2013b) learn each node representation by predicting its context.
complexity
A.8.5 NODE2VEC
Mode2Vec(Groves & Leskovec 2016) improves DeepWalk by performing a parametrized random walk. For each transition, Node Vec considers second-order proximity decide the next node be near or far from the previous node, which allows exploration both in local and global scopes.
A.8.6 DADL
DADL et al. 2018 leverages conventional GRL methods to embed local structure on each node, which implies some similarities between the current node and its neighbors. Then, by con- sidering different binary operations over node embeddings deep learning techniques, this method outperforms conventional ones in the shortest distance prediction task.
A.9 FURTHER COMPARISON IN ACCURACY
We also evaluate embedding method with the latest GRL techniques. Parameter setup takes the same configuration as stated in Section ex2iepppt for some trivial modification match the embed- ding dimension d 16. All compared models take default parameters. We list out the comparison among these methods in Table 55) Moreover, we further illustrate the relation between prediction accuracy and path length for each method both sparse graph (GrQc) and relatively-dense graph (Facebook). The sampling firquency of different path lengths in each dataset is presented in Figure g Length-level prediction accuracy is presented in Figure
The experimental results show our method outperforms others mainly benefited by decent represen- tations node pair's similarity in a large range of shortest distance. On the one hand, BC-based walk occupies wider range of shortest paths on each node, making remote nodes available before embedding. On the other hand, the distance resampling strategy discerns nodes by different order proximity to preserve their mutual shortest distance.
A.10 RUN TIME BCDR AND GENERAL RANDOM WALK
As is stated in Section 4.2
the time complexity of BCDR could be adjusted by sampling parameters
Win, Wouts lin, lout- To keep the capacity of accomodating large shortest distance, Win and Inn are fixed as the previous. Define 8 as the compressing coefficient of path length, and use lout 40 3. Wout is thus adapted for inputs, i.e., Wout Tout
40
The comparasion between BCDR
19

---

Under review as a conference paper at ICLR 2022
1.20
2.3-
6.14
1.0
5.0
0.5
1.5
15
2.0
2.5 weeth
1.0
3.5
4.6
4.5
1.00
94th
p4th lenatt
(a)
(b)
Figure 8: Sampling frequency of different path lengths. (a): Facebook dataset. (b): GrQe dataset.
1.76
21.
1.7
192
1.29
1.2
bodr. 18C
A82
12
0.30
1.00
04th knet
042h Inret
(a)
(b)
Figure 9: Length-level prediction accuracy (a): Facebook dataset. (b): GrQe dataset.
and general random walk method is provided in Figure 10 and for run time and corresponding accuracy, respectively.
The experimental results reveal that our method could reduce time complexity with high accuracy keep pace with general random walk in sparse graphs, but for relatively-dent graphs(like Face- book), there is some room for further optimization.
A.11 FURTHER DISCUSSION ON WALKING PATTERNS
We test the performance of BC-based walk and other walking patterns six synthetic graphs. The statistics of these graphs we simulated are listed in Table 6 To address the aspect of getting out of local cliques or circles, provide another BFS-like searching pattern where each transition tends to choose the edges that could get out of the local clique by considering imity (with probability Pout 0.901). Properties and visualization of these graphs are presented in Appendix AA7.55 And traversal results are illustrated in Figure 12 to Figure 17 The fluctuation of BC value on each graph is illustrated in Figure
to second-order prox-
The results are analyzed as follows.
For circle graphs and tri-circle graphs, BC-based walk tends to choose the exit nodes of each circle since they share a large BC gain by locating on the shortest path between inner nodes and outer nodes.
20

---

Under review as a conference paper at ICLR 2022
(a)
(h)
(c)
Figure 10: Comparison run time between BCDR and general random walk. (a): Cora dataset (b): Facebook dataset. (c): GrQc dataset.
6.0
Beeut
610
(a)
(b)
(c)
Figure 11:
Comparison of accuracy correpsonding to run time presented in Figure 10 dataset (b): Facebook dataset. (c): GrQe dataset.
(a): Cora
For triangle graphs, transitions on every triangle clique tend move forward since the num- ber of nodes beyond the current clique is often larger than that of inner nodes, contributing to more shortest paths.
For tree graphs, each transition appears to move forward from the root the leaves, and all walking patterns show similar exploration.
For spiral graphs, although some exit nodes are located on the circle, BC gains on exit nodes and inner nodes on circles usually on par, which misleads the direction choice of the next transition. Thus, BC-based walk only performs slightly better than others.
For net graphs, all walking patterns are limited on exploration distance, since BC values on different nodes do not change considerably.
To conclude, the above results show that BC-based walk possesses better all-around performance to capture remote nodes with large shortest distances.
21

---

Under review as a conference paper at ICLR 2022
Table 6: Statistics of six synthetic graphs
Circle
Triangle
Tri-circle
Tree
Spiral
Net
V
262
352
234
207
550
100
E
281
853
559
206
585
178
V
1.0725
2.4233
2.3889
0.9952
1.0636
1.78
avg. Degree diameter
2.1412
4.8438
4.7735
1.9855
2.1255
3.55
32
100
26
18
101
18
(c)
(d)
(c)
Figure 12:
Exploration distance of different random walk strategies tested on circle graph. (a):
General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
(a)
(b)
(c)
(d)
(e)
Figure 13: Exploration distance different random walk strategies tested on triangle graph. (a):
General random walk (b): Vece2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
(b)
(c)
(d)
(e)
Figure 14: Exploration distance of different random walk strategies tested tri-circle graph. (a): General random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
(b)
(c)
(d)
(c)
Figure 15: Exploration distance of different random walk strategies tested on tree graph. (a): Gen-
eral random walk (b): Node2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
22

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(d)
(e)
Exploration distance different random walk strategies tested on spiral graph. (a): General random walk (b): Vece2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
Figure 16:
(a)
(b)
(c)
(d)
(e)
Figure 17: Exploration distance of different random walk strategies tested net graph. (a): General random walk (b): Nede2Vec. (c): Random Surfing. (d): BFS-like search. (e): BC-based random walk(ours.).
(a)
(b)
(c)
(d)
(e)
(f)
Figure 18: Fluctuation of BC value on each graph. (a): circle graph. (b): triangle graph. (c): tri-circle graph. (d): tree graph. (e): spiral graph. (f): net graph.
23


Reviews:
[{"review_id": "pnfh-jXYyR", "reviewer": "Reviewer_FZhh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nThe 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.\n\nThe 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SlJfkxzgEB2", "reviewer": "Reviewer_28dr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n- 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. \n\n- 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.  \n\n- 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.  \n\n- 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. \n\n- 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. \n\n              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.\n              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.\n              \n- 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). \n\n- 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. \n \n- 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.  \n\n- Report total run times for all methods. ", "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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P4nE_fJJXyY", "reviewer": "Reviewer_UCXV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\nThe method considers not only ensuring the random walk takes into account longer distance associations among nodes but also the representation of shortest distances.\nWith 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.\nAlso, 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.\nFinally, 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_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)", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GZSyTWecKrR", "reviewer": "Reviewer_7mP1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nWeakness: The notations in section 3 are slightly complicated. Especially, some notations are used and discussed in high-level ideas without explanation and definition. \n\nQuestions:\n1. In proposition 1, should the embedding distance matrix take an opposite sign, since the current linear expression is negative? \n2. For proper parameter alpha and sufficiently large distance pair vi and vj, does proposition 1 imply a constant distance distortion for this embedding? \n\n\nAfter responses:\nThank 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. \n", "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.  ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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