Learn Low-dimensional Shortest-path Representation of Large-scale and Complex Graphs
Authors: Haoyu Wang
Chun Yuan
Lei Li
Jiahui Jin
Venue: Submitted to ICLR 2023 (2023)
Keywords: shortest-path distance
graph representation learning
random walk

Abstract: Estimation of shortest-path (SP) distance lies at the heart of network analysis tasks. Along with the rapid emergence of large-scale and complex graphs, approximate SP-representing algorithms that transform a graph into compact and low-dimensional representations are critical for fast and scalable online analysis. Among different approaches, learning-based representation methods have made a breakthrough both in response time and accuracy. Several competitive works in learning-based methods heuristically leverage truncated random walk and optimization on the arbitrary linkage for SP representation learning. However, they have limitations on both exploration range and distance preservation. We propose in this paper an efficient and interpretable SP representation method called Betweenness Centrality-based Distance Resampling (BCDR). First, we prove that betweenness centrality-based random walk can occupy a wider exploration range of distance due to its awareness of high-order path structures. Second, we leverage distance resampling to simulate random shortest paths from original paths and prove that the optimization on such shortest paths preserves distance relations via implicitly decomposing SP distance-based similarity matrix. BCDR yields an average improvement of 25% accuracy and 25-30% query speed, compared to all existing approximate methods when evaluated on a broad class of real-world and synthetic graphs with diverse sizes and structures.

Under review as a conference paper at ICLR 2023
LEARN LOW-DIMENSIONAL SHORTEST-PATH REPRE- SENTATION OF LARGE-SCALE AND COMPLEX GRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
Estimation of shortest-path (SP) distance lies at the heart of network analysis tasks. Along with the rapid emergence of large-scale and complex graphs, ap- proximate SP-representing algorithms that transform graph into compact and low-dimensional representations are critical for fast and scalable online analysis. Among different approaches, learning-base based representation methods have made a breakthrough both in response time and accuracy. Several competitive works in learning-bast methods heuristically leverage truncated random walk and op- timization the arbitrary linkage for SP representation learning. However, they have limitations on both exploration range and distance preservation. We propose in this paper efficient and interpretable SP representation method called Be- tweenness Centrality-based Distance Resampling (BCDR). First, we prove that random walk can occupy wider exploration range of distance due to its awareness of high-order path structures. Second, we lever- age distance resampling simulate random shortest paths from original paths and prove that the optimization on such shortest paths preserves distance relations via implicitly decomposing SP distance- based similarity matrix. BCDR yields an av- erage improvement of 25% accuracy and 25-30% query speed, compared to all existing approximate methods when evaluated on broad class of real-world and synthetic graphs with diverse sizes and structures.
betweenness centrality-
INTRODUCTION
Estimation of shortest-path (SP) distance lies the heart of many network analysis tasks, such as centrality computation (Schönfeld & Pieffer 202Tb. node separation (Houidi et al. 2020), com- munity detection (Zhang et al. a |020 Asif al. 2022), which also directly contributes to enormous downstream applications, including point of interest (POI) search (Qi et al. 2020 Chen et al. 202 Ta)
social relationship analysis (Carlton| 2020 Melkonian et al.) 2021), biomedical structure predic- tion Yue et al.) [0199] Sokolowski & Wasserman (021) learning theory Yang et al. 2021 Yuan ctt al. 2021). optimization (Rahmad Syah et al.) 2021; Jiang et al., 2021b). etc. Nowadays, a key challenge of computing SP distance is the prohibitive complexity in very large and complex graphs. e.g., for a sparse undirected graph with N nodes and queries, the time complexity of A (Hart al. 1968) and Dijkstra algorithm (Thorup & Zwick 2004) are up to OKNN and O(KN log N)
For unweighted and weighted graph, respectively.
Regarding this issue, various methods (Cohen al. 2003 Fu. 2013 Akiba et al. 2013 Delling et al. 2014] Farhan et al., 2019; Liu et 2021) attempt answering exact distance in microseconds online via indexing or compressing techniques, which suffer huge storage costs on all pair SP dis- tance representations and fail to reflect latent sub-structures in graphs for scalable queries (see Fig- ure Tp. Highly concise SP representation for large-scale and complex graphs remains to be studied yet. Regarding this, a surging number of approximate SP-representing algorithms that transform a graph into compact and low-dimensional representations are thus critical for fast and scalable online analysis. They can be categorized into oracle-based (Thorup & Zwick 2004 Baswana & Kavitha 2006). landmark based (Potamias et al.] 2009 Sarma et al.) [2010] Gubichev et al.) 2010) and learning based (Rizi et al., 2018 Schlötterer et al. 2019 Qi et al. 2020 Jiang al. (02 SP representation methods. Among these categories, learning based methods are of high accuracy and short response time (see Table owing much to flexible node embeddings in metric space.

---

Under review as a conference paper at ICLR 2023
app sorraaa spesersiann
Fow Jaye
Mr
bg Nr
Lgg mr
P
P
(a)
(b)
(c)
(d)
Figure 1: Differences between approximate (ours.) and exact (PLL (Akiba et al., 2013). effi- cient implementation of the hub-labeling method) SP representation methods regarding storage cost (megabytes, MB) and response time (nanoseconds, ns), We simulate a group of Bernoulli random graphs with [V] nodes, and each edge is filled independently with probability p. (a) and (c) show the storage cost of exact representations increases dramatically relative to the graph size. (b) and (d) reflect longer response time of exact methods, induced by random access to massive information.
Table I: Overall comparison of approaches to SP representation on DBLP dataset A.8.4) PTC: pre- processing time complexity, PSC: preprocessing space complexity. RTC: response time complexity, TSC: the total storage cost for answering online distance queries, RT: real response time, AL; accu- racy loss which is measured by mRE (see Equation D.. N: the number of nodes in the graph, L(N): the average label size of each node which increases along with N, D: the amortized degree on each node. On, L. n, d, w, I, c and ,3 are hyperparameters corresponded models.
Calegories
Method
PTC
PSC
RTC
ISC
KT
AL
Hub labeling
PLL
(Aloba et al. 2013
O[NE(N))
O[L(N))
611.2 MB
2104.4 ms
Orade-based
ADO
Thorup & Zwick
2004
OlanA R))
OlegN 4))
O(au)
9.950 MB
8, 5,598 os
D-4985
Landmarks based
LS (Potiin & 2009
O(NN)
OILN)
O(O)
331.6 MD
12. 12,094 ms
0.3939
Leaming-hasel hased
Onion
2010
Ola uA)
OidN)
O(d)
19.35 MB
82,25
1.1897
Rigel
Kiaohan et al.
20
Ola² + n.:
OldY)
Old D)
35.37 MB
5. 5,657 ms
L.0682
DADL ef 2018
O([[4] + N
OldY +c)
Old D)
35.37 MB
T.502
0.20116
Perh2 (Kuiizzy
2019
O[1IA] + w(]N)
OldY t
D)
35.37
T. 7.700 ms
HALK Schiollerer dl
2019
0 + w
OldY +c)
Old D)
35.37 MB
7, 7,704 ms
0.3077
CalBootESDD Diang 2021a
OQLLI +c)
O(()cc)
41.16 MB
9,270
0.0890
BCDR (ours.)
0((1 WNN
OQAIN +
O[L]c DJ
39.19 MB
7,7 ms
0.0798
BCDR.FQ (ours.)
0104 (NN
OddY t
O(4)
58.82 mg
0.1840
Several competitive works in learning- based methods (Rizi et al. 2018 Schlötterer et al. 2019
heuristically leverage truncated random walk and optimization of node-cooccurrence likelihood on the arbitrary linkage learn SP representations, which once achieved the oftte-of-theaan perfor- mance approximation quality. However, they are not without limitations on efficiency and inter- pretability. On one side, a random walk is an unstrained node sequence from the root, possessing limited exploration range of distance, thus resulting in uncaught distance relations with remote nodes. This is because each transition on nodes is not implied for a specific direction to move to- wards beyond the root, especially after several walk steps, which restricts it from visiting remote nodes under limited walk steps (see Figure[ap. On the other side, the optimization on arbitrary link- age reflects excessively versatile local similarity among nodes, which preserves inaccurate distance relations from original graphs to the embedding space. In fact, it exerts a too-general metric over nodes' correlation, wherein the more edges or paths exist between two nodes, the stronger corre- lation they share. That means there are many ways to simulate a strong correlation for two nodes (e.g., add mutual edges, delete an edge to other nodes) even if some of the operations do not influ- ence their actual SP distance (see Figures 2c and 2d) A detailed statement of related works on SP representation and motivation for estimating accurate SP distance can be found in Appendix A..
In this paper, we address the above shortcomings by proposing an efficient and interpretable SP rep- resentation method called Betweenness Centrality- -based Distance Resampling (BCDR). It improves the approximation quality of SP representations with two components. The first is betweenness cen- trality (BC)-based random walk which explores a wider range distance correlation on the graph due to its awareness of high-order path structures. To method that combines betweenness centrality and random walk to learn SP representations. We prove that BC-based transition is prone jump out of local neighborhoods compared random
best knowledge, there is no existing
2

---

Under review as a conference paper at ICLR 2023
(a)
(b)
(c)
(d)
Figure 2: Distance confusion in previous SP representation learning. (a) random walk from U/ has much difficulty in exploring beyond current community to te. (b): node similarity on random paths misleads the measurement SP distance since the walk from ea is prone to steer clear of on for starters and back to U/ the end, causing extremely weak correlation between va and o6 even though they have an immediate edge. (c): a sufficient number of 2-hop links between ue and va induce a shorter distance in embedding space than that of ug and Va. (d): t and ve sharing substantial connection are mapped closed to each other even if they have a large SP distance gap, while the divergence of distance between Ub, Ue and Va also plagued with extraction.
transition. The second is distance resampling which preserves accurate SP distance relations via im- plicitly decomposing an SP distance- based similarity matrix. In essence, simulates the observation of random SPs from original walk paths and exerts desirable constraints on node representations to preserve distance relations over the graph.
We summarize the major contributions follows: i) We propose BC-based random walk as an efficient strategy for exploring a wider range of SP distance within limited walk steps (see Section 3.1). ii) We propose distance resampling preserve accurate distance relations among nodes to learn an interpretable SP representation (see Section B.2p. iii) We evaluate BCDR with a broad class of real-world and synthetic graphs, and it yields an average improvement of 25% accuracy and 25-30% query speed compared to all existing methods (see Section 4
2 PRELIMINARY
Notation: G= EV denotes an undirected graph. with V = {fy} being the set of nodes and E' [(0,, 2₁}} being the set of undirected edges, and N = =V] A [E. We use Znxa to represent a matrix comprising embedded vectors of nodes, where d is the embedding size, and the i-th row of is corresponded with v,. path Pij of length 1 E N4 on graph G is an ordered sequence of nodes (E;, Ca,, .... Va U2), where each node except the last one has an edge with the subsequent node. The shortest path Piş is one of the paths with the minimum length Diy between and Uy. Also, the SP distance matrix D comprises (Diz) A node v; 's neighborhood. NG is set of nodes with an edge with 0, i.c., N₁ = {oy (1), 11) ) E E}. For high-order neighborhoods of vs Ag(h) is defined as set of nodes h-hop away from 0; i.e., (oylDis h). To avoid confusion with the symbol of paths, we use P(-) represent a probability distribution in this paper. A truncated random walk W; rooted at node of length 1 is a random vector of (W! W.t .... ,W)), where Wikk is node chosen from the neighborhood of node W for k 1,...,, 4, with the initial probability P(W! v) 1. W; is categorical distribution of nodes W,, and the probability of each node in W; represents the frequency of occurrence on the sampled paths.
Problem Definition & Metrics: The evaluation of approximate SP representation methods is di- vided into two stages, For the offline stage, the processing time and memory usage when construct- ing SP representations are evaluated. and the storage size of such representations considered. For the online stage, the query speed, memory usage, and approximation quality are evaluated. There- into, to evaluate query speed and memory usage, a million times of query requests for arbitrary node pairs are performed, then the memory and average response time for each node pair are recorded. For approximation quality, the commonly used metrics are mean of relative error (mRE) and mean of absolute enror (mAB). For group of SP distance queries Q {(vi, b;)}, mRE is defined as the relative loss of the estimated value Dig with respect the real value Dij, while mAE measures the
3

---

BC( Under review as a conference paper at ICLR 2023
absolute gap between them:
mRE = QI
1 Σ
DD -Dsl
1 mAE: = QQ]
Σ
Dis - Dijl
Dij
(1)
(MGNy)EQ
3 METHOD
Although random walk (RW) is universally accepted as an efficient serialization strategy of simi- larity measurement on graphs (Grover & Leskovee 2016 Zhuang Ma 2018), we argue that the intuitive practice of RW in representing SP structures has several limitations. Consider walk path p = (Va, Pla, Vay. Vo, E Pa sampled by stochastic selection on neighborhoods from root node V/- Distance measured along p (i.e., the order the walk) is not consistent with that the graph (see Figure 2b) since the node sequence unstrained, i.e., for Va Pa, E p, S j 4 Daa, S Daay where and indices of node Va; and Va, p. and 1 S i,j < Therefore, optimizing node co-occurrence likelihood on such walk paths incurs two problems.
Problem Limited exploration range of distance. The exploration range of rooted random walk is not in proportion to its length since each transition the walk has agnostic tendency to move towards or beyond the root after a few steps (see Figure 2a
2. Problem 2: Intractability distance relations on paths. The distance measured on
walk paths may not actually reflect the SP distance on the graph because of the unbalanced number of edges between different nodes (see Figure 2e and 2d).
In this section, we describe in detail our method as decent way of representing SP structures. We discuss two techniques named BC-bused random walk and distance resampling to address the above problems, respectively, and present the corresponding theoretical analysis for their interpretability. A time and space-efficient implementation of BCDR to integrate these techniques is available in Appendix A.2
3.1 BA-BAD RANDOM WALK FOR WIDER EXPLORATION RANGE OF DISTANCE
(V, (V.E) E) undirected graph. Vs Usr are arbitrary nodes in V. (x((v) represents the number of shortest paths between V. and ot that pass Ue and at is the total number of shortest paths between Us and Ut, Then say that BC of 0 is
Definition 1. (Betweenness Centrality) Define G = (V.
(1)
BC(=:) Σ
Oat
To address Problem [ we propose BC-based random walk. As defined in Definition 1 determines the probability of located SPs of arbitrary node pairs Thus, we consider node with a large BC value vitally significant to drive the walk to move away from the root node, since it reveals easy way of traveling to property, in BC-based random walk We = (W a W Wi,.., on node Va, we prefer choosing nodes with the largest BC values among their neighborhoods when simulating walk paths, i.c.
other nodes with minimal steps. And leverage this
BC(um)
P(W = Um Wi = v..) EVDEN, BC(²k)) Um N
3
Theorem proved in Appendix A.3 indicates that BC-hased random walk is prone to transit from (! to No. (+) leading to a wider exploration range measured by the intrinsic graph's SP distance. components, i.e., final nodes fü (va( and con- nective nodes en(v)), Thereinto, nodes in fr (v,)) have no edge with with.A?!h+1) (h++1) while nodes e (v.) have several edges with ((++)) as illustrated in Figure 3a Our method significantly improves the performance when the number of final nodes [ (v.)) is larger or there are more edges from (v.)
Specifically, for each node va, (v(h) comprises
ea (v.) (see analysis in Remark

---

Under review as a conference paper at ICLR 2023
Structural Blas
Observation
Node-leval Embedding
10
Random
Embedding for Aroitrary Lirkage
BC Random
Distance Recampling
Random
Embedding for Distance
Potts
(a)
Figure 3: (a): high-order neighborhoods' structure of Va- BC-based random walk enhances the transition from fr. to en and e사 to Ea+1, prone to jump out of local neighborhoods. (b): comparison between general RW-based graph learning and BCDR. Distance resampling transforms the observa- tion into random shortest paths, which exerts desirable constraints on learning SP representations.
Practically, pre-computing BC value each node is time-consuming,, which takes least O(N time. To address this problem, we estimate BC by leveraging breadth-first search (BFS) from a fixed number of landmarks, since nodes with large BC values tend to be visited first by BFS from any landmark. We show in Algorithm and Appendix I that this process could be involved in the simulation of distance triplets without introducing extra time complexity.
Finally, we conclude that BC-based random walk is a competitive walking pattern regarding explo- ration range of SP distance, since it possesses a strong tendency to jump out of local neighborhoods. We further verify our conclusion by comparing it with existing RW techniques in Section 4.2.
3.2 DISTANCE RESAMPLING FOR SP DISTANCE PRESERVATION
To address Problem 2 we propose distance resampling- We first illustrate general RW-based graph learning paradigm in Figure 3b and clarify the differences between ours and other approaches. The basic idea of RW-based methods is to learn node-level embeddings Z from pieces of observation (i.e., walk paths), and Z thus reflects the structural bias graphs. Specifically, for the naive RW strategy and its variants utilized in other approaches, the observation is a set stochastic paths re- flecting the property of arbitrary linkage between nodes, which asks Z to preserve point- wise mutual information (PMI) similarity (proved in Levy & Goldberg (2014); Shaosheng et al. (2015). Unfor- tunately, the PMI similarity shares no direct connection with SP distance and causes the problems depicted in Figure 2d and [d] To fit Z with correct information about SP structures, we intend to observe random shortest paths instead. This practice is feasible since the SP problem always has optimal substructures, i.e., the subpath between two nodes on any SP could also be extracted as an SP between these nodes. However, the prohibitive complexity of computing all pairs of SPs for- bids us from performing such sufficient observation (see both technical and empirical comparisons between utilizing BCDR and directly sampling SPs for optimization in Appendix (p.7).i(AA.)). By way of an alternative, we propose resampling strategy to transform BC random paths into approximate random SPs with efficient linear processing time and better performance.
Initially, we formulate the SP representation problem from the RW-based learning perspective. we refer to random SP walk W; as ideal walking pattern whose transition reflects the probability of each shortest path passing through o,. It means paths sampled from W. are prone to be SP rooted at V2- For sufficient observation SPs, thus have optimization objective W;, i.e. ((Z) = Be,e [log Pi.iz. (W, [z.) To reduce optimization complexity, we replace the intrinsic probability normalization by negative sampling, according to Mikolov et al. (2..(2200))) b), i.e.,
(n - P(x)) (og Dog (Z.2,)) + XB Pv (og 2.2Z)1
0(
(4)
V.E
since we prefer an informative instead of the accurate probability. Thereinto, P,, is the dis- tribution of negative sampling over the graph, À denotes the number of negative samples, and
5

---

Under review as a conference paper at ICLR 2023
(ax) (1 + - It is notable that W; each node 2 is backbreaking to extract, since it requires a traversal on all SPs passing through Vs- To address this, we revisit the node distribution Pw, on BC-based random walk W, and construct a distribution Qw, resampled from Pw. as an efficient approximation to Piv. i.e.,
PCBC(( Qw:(u)) EW; a Pak (U
(5)
where a is hyper-paramese controlling the weight decay by the distance, <<<k <.
Finally, we maximize the following approximate objective Ln on W; (instead of C, on W i..
(Z) P(cs) (Bny~en (v) flog e l (Z,Z,)) + AlE Pv) o( ((-zzzz)) NEV
We show in Proposition that optimization of Equation G conforms to implicitly decompose an SP distance-based similarity matrix where for any Vo and v/ located far away from each other under the SP metric (i.e., small Das) should be mapped with low similarity in the embedding space (i.e., large (Das)) ). Also, further discussion in Remark 2 shows that such similarity matrix D shares strong connections with the real SP distance matrix D) on graphs.
Proposition 1. Let G be undirected graph, W; be the categorical distribution of nodes on the puths sampled by BC-based random walk. Negative sampling on each node vn takes a uniform distribution on W.. Then, for sufficient observation of W1s WN, maximizing En defined by Equation 6 with embeddings Z is equivalent to decomposing SP distance-based similarity matrix D ZZ" where for any Va and vb, the distance between them in the embedding space varies linearly with respect to distance Dah, namely,
Dab ZaZz loge
Dab log a
(7)
where is a small constant related to the negative samples, which is independent of ub. and a is the hyper-parameter defined in Equation 3
where <<
Proposition is proved in Appendix A.4 by deriving the extreme point of É., regarding Z.
Then, we consider the preservation of SP distance relations. Some studies on metric learning (Her- mans et al. [017]] Zeng al.) 2020) have revealed that a triplet of samples (Va, Ub, Ue) being easy to learn means 2 shares strong correlation with v., the distance between U and D2 in the embedding space should be shorter than that of t. and Va- With this property, we have the following theorem (proved A.6 by directly applying Proprosition []. which indicates that our method consistent with distance relations under the intrinsic SP metric.
Let D be a global distance matrix defined graph G and Das be graph's 's SP distance between node v. and Ub. Then for any nodes Va, Ub, Vi E G,
Theorem 1. Each symbol here follows the definition in Proposition !
(Dab DDc) Dac) 50
(8)
In conclusion, we discuss here the significance of distance resampling for preserving accurate dis- tance relations. It exerts two implicit constraints on to learn an interpretable SP representation. First, as stated in Proposition I the distance measured in the embedding space shares strong neg- ative correlation with that measured on the graph. Second, for any node triplet, the distance relation between any two of them is preserved according Theorem The two constraints are further verified in Section 4.3 against existing techniques.
3.3 EFFICIENT IMPLEMENTATION OF BCDR ALGORITHM
We also provide time and space-efficient implementation of BCDR to integrate the above tech- niques in Algorithm[] [ Like previous learning-based SP representation methods (Rizi et al.) 2018), we first transform the graph into low-dimensional embeddings (i.e., ZNxd) and learn a distance predictor 9s (Rd, Rdd + R by observed distance triplets ((Z., Zo. Dat)). Then, the predictor do will be involved in answering online distance queries. In addition, similar to Diang et al. (2021a), also improve the prediction results via gradient boosting techniques. The detailed designs of these procedures are described in Appendix A.2, and an ablation study to evaluate their impact on performance is provided in Appendix
A.11 A.11

---

Under review as a conference paper at ICLR 2023
4 EXPERIMENTAL EVALUATION
In this section, show the comprehensive performance of BCDR with 5 real-world graphs of different sizes and 6 synthetic graphs of different structures. Specifically, we evaluate BCDR on 3 small graphs (i.e., Cora, Facebook, and GrQc) and 2 large graphs (i.e., DBLP and Youtube) for its scalability (see Section 4.1), and evaluate it on synthetic graphs for its representational capacity of complex structures (see Section 4.2 and 4.3) Our method is compared with strong baselines from both approximate SP representation and general graph representation learning (GRL). In the experiments, we also provide two variants of BCDR, i.e. BCDR-FC and BCDR-FQ. for accelcrating the construction and querying process, respectively. A detailed description of the datasets, including statistics and visualization, is thoroughly provided in Appendix A.8
4.1 PERFORMANCE OF APPROXIMATE SP DISTANCE QUBRY
We compare BCDR with other learning- based SP representation methods (i.e., Orion (Xiaohan et al.
2010). Rigel (Xiaohan et al.] (01TT) DADI. (Rizi et al.] 2018), Path2Vec (Kutuzov et al. 2019). HALK (Schlötterer et al. 2019)) and CatBoost-SDP (Jiang et al. 2021a) as well other approx- imate methods, including landmark-based (i.e., LS (Potamias et al. 2009) and oracle-based (i.e., ADO (Thorup & Zwick )004)) techniques. All of the above models are run with six 3.50GHz Intel Xeon(R) CPUs and 128GB memory, and the precomputed representations of each model are serial- ized by Pickle. Each baseline generally follows the default parameters discussed in its paper with some trivial changes, so that its performance can be evaluated in unified way. The detailed param- eter setups of each model are provided in Appendix AA. Like previous works, we initially compute all pairs of SP distance on each graph by BFS and take a uniform sampling to select 1, 000, 000 distance triplets {Va. Ub. Dao)} as test samples. All of the baselines, including ours, are purely im- plemented in Python 3.9 and evaluated under the same environment. Since only unweighted graphs are considered, the outputs of each model are quantized to integer when evaluating accuracy loss. Some of the experimental results isons with GRL models). We can see from the table that our model not only outperforms previous models regarding accuracy loss for all graphs but also shares competitive results on other metrics.
shown in Table 2
(see Appendix A0 for extended compar-
In detail, for accuracy loss (mAE and mRE), BCDR answers arbitrary queries with the minimum error due to wider exploration range of distance and variants of BCDR without boosting module (i.c., BCDR-FQ and BCDR-FO -FC) also achieve the highest accuracy against other RW-based learning approaches (i.e., DADL and HALK) within almost the least storage cost. For offline processing time (PT), memory usage (PMU), and storage cost (SC), the results show BCDR possesses powerful scalability against the growth of graph scale. Even for a graph with millions of nodes, the offline processing could be completed within several hours, and the memory usage is close to the graph size. This is because we perform BC-based random walks with fixed length on each graph, and the size of walk data is further reduced by distance resampling. In addition, although CatBoost- to point out that this method does not learn any representation of nodes and completely optimizes all pairs of distance in a boosting way, which subsequently suffers higher time and space cost for online queries. For response time (KT) and memory usage (QMU) in querying, we see BCDR-FC models share similar low memory overhead since each distance query
optimization. Notably, the
seems to achieve strong scalability on these metrics, we need
and most other learning-basse could be answered by checking the node embeddings and graph adjacency matrices. Furthermore, BCDR-FQ and Orion could answer such a query within tens of nanoseconds due to the absence of double-checking on adjacency matrices.
Besides, to evaluate the impact of critical components and syper-parameters in BCDR, we further conduct an ablation study in Appendix [p.ld where we discuss 6 different modifications BCDR as well as an investigation on 9 critical parameters to show their impacts on different metrics.
4.2 EXPLORATION RANGE OF DISTANCE
As stated in Section 3.1 the exploration range of distance could be widened by BC-based random walk (BC-RW), since the latter helps to jump out of local neighborhoods. Here, compare BC- RW with existing renowned walk strategics, including naive random walk (NRW) (Perozzi et al. 2014 Zhuang & Ma 2018), second-order random walk (SORW) (Grover & Leskovee 2016). and
7

---

Under review as a conference paper at ICLR 2023
Table 2: Performance comparison of approximate methods on SP distance queries. PT: processing time when constructing SP representations, PMU: processing memory usage, SC: space cost on stor- ing SP representations, RT: average response time of answering distance query, QMU: querying memory usage. mAE and mRE are the accuracy metrics. DNF means it did not finish in one day. We bold the top three performances, and highlight the top one with an underline.
Daraset
Model
FT
PMU
SC
RT
QML
mAF
mRE
AIX
0.3179
6:205 MB
0.95KI5
MB
9,813
11.89 MB
2.1070
0.4256
0.6355
2,952
10:92 MB
1,0599
0.2008
Orion
61.31
15.06 MB
0.1655
63.87 m
0.1654 MB
3.0542
0.5242
Rigel
61.36 9
15.06 MB
0.1655 MB
4,587 m6
0,24N2 MH
3.0464
0.5164
Cora
DADI
08.22
27.36 MB
0.16% MB
6. 798
0.2486 MB
1.0822
0.1862
Vee
172.9
2,870
6.
3,2000
0,6066
HALKK
6.715
0-10%
6. 00-022
0.2486 MB
1,77002
0,3993
CatBooa--SDD SPP
9.582
0,4144 MB
0:4711 MB
8. 0887 06
4,285 MB
0.8907
0.1585
BCDR (ours.)
10.55 85
2,979 MB
0,4079 MB
6,370
4. 4.0625 MB
0,50466
0.1411
BCDR-FQ PQ (ours.)
2.728
0.16%
50.05
0.1657
0.7349
0.1247
BCDR-FC (ours.)
35,60 5
2,728 MB
0,16 MB
6. 6,850 mS
0,2488 MB
0,8243
0.1384
ADO
1991
11.10 MB
1.78 MB5
8. 10h
10.34 M15
1,1512
0.000
3.382
4,390 MB
0.9929 MB
11. 664
12.28 MB
0,9566
0.3924
80.53
21.00
60.81
0.2418
1,7770
0.88G4
Rigel
80.31
21 MB
0,2411 MB
4,976 ms
1,588 MB
1.7531
0.8625
Facebook
Ves
DADL
284.5
176.3 s
5.459 MB
42. MB
0.3489 MI
0,3459 MB
8. 000011
8. 1.282
1,588 MB
1,588 MB
1.4263
0.2250
0.5489
0.0792
HALK
21.28
0,9004
0,3517
CaiBoost SDP
12.84
1.74 MB
0,6890 MB
8, 9.955 D5
1.504 MB
0,0203
0.0159
BCDR (ours.)
142.7 5
8,504 MB
1,210 MB
8. 208
5.402 MB
0.0106
0.0044
BCDR-FO (ours.)
160.8
5.213 MB
0.2459 MB
53.78
0,2421 MB
0.0978
0.0385
BCDR-FC((urs.)
5,213
8.
1,588 MB
0.1463
0.0478
ADO
1.322 5
17.75 MB
2322 MB
13, 355 ms
19.19 MB
18777
0,3582
ES
2,099
5.722 MR
1.315 MB
11, 825
13.60 MB
1.1538
0.2007
Orion
14
0.3202
62.80
0,3201 MB
3.0632
0.4849
Rigel
98.00 00
21.33 MB
0.3292
4,872 n
0,5519 MB
3.499
0,4810
GrIQ
DADI
103.0 6
53.00 MR
0.3242 MB
6, 912 m5
0.5523 MB
0,9812
0.1630
Vath2Ves
$33.0
5.632 MB
0.3342 MB
6. 9.9998
0.5528 MB
1,1339
0.7231
HALK
0.5523 MH
1,1095
0.2063
CatRoow-SDDP
11,03
0L9305
0.7846
9. 0.0
4.500 MB
022215
0.1416
BCDR (ouns.)
69. 61
5,907 MB
0.7916 MB
6, 452
4.367 MB
0.7043
0.1274
BCDR-FQ (ours.)
67.95 98
5.351 MB
0.3242 MB
$1.90
0.3204 MB
0.5743
0.1501
BCTR.FC (curs.)
58.30
5.351
0.3242
0.6523
0.1442
AEX
37, 022
8, MB
199. MB
8. 398 BS
5, 380 MB
3,0891
0,4885
LS
5,838
349.0 MB
50.02 MB
12,094
311.6 MB
2,5000
0.3939
Orion
5,531
321.8 MB
19.36 MB
82.25
19.35 MB
3.5014
0.5165
Rigel
5,523 s
321.8
19.36
ms
3.5043
O.51G4
DBLP
Ves
DADL
27. 453
2. 650
L. 958 MB
100.9 MB
19.36 MB
19 MB
7. 7.000
7. 7.2 m5
35.37 MB
35.37 MB
3,9174
1.27553
0.2016
0.8097
HALK
1,270
649.6 MB
19.36 MB
7. 70.004
35.37 MB
1.8477
0.3077
CatBoost SDP
244.4
56.47
9,270
0.5492
0,0890
BCDR (ours.)
1,009 5
80.04 MB
41 82 MB
7, 247 ns
38. 19 MB
0.4923
0.0798
BCDR-FO (ours.)
1,026 s
$3.52 MB
19.36 MB
58.82 ms
19.35 MBB
1,3018
0.1840
BCDR-FC FC (ours.)
999.8
53.52 MB
19.36 MB
7,617
35,37 MB
1.1014
0.1580
LS
87, 902
1, 258 MB
286.7 7 MB
16, 672 n5
1,217 MB
2,0159
0.4091
Orion
50, 484
1, 251 MB
69.36 MB
163.9 ms
69.26 MB
2,8642
0.5473
21,266
1,251
2,86-1
0.5473
Youtube
Path2Voc
DADL
28,
DNF
6, 953 MB
69.27
7, 70.7881
114.9 MB
1.1144
0.2163
HALK
5,971
2, 187 MB
69.27 MB
7, 7.766
114.9 MB
1.9035
0.3860
CalBoost
190..
0.4022
0.0724
BCDR (ours.)
9,217'
295.2 MB
141.6 MB
7,393 ms
118.7 MB
0.3297
0.0676
BCDR-FO (ours.)
7,893 s
179.8 MB
69.27 MB
63.78 ms
69.27 MB
0.9604
0.1704
BCDR-FC (ours.)
6,000
179.8 MB
69.27 MB
6.156
114.9 MB
0,9083
0,1745
random surfing (RS) (Cao et al. 2016). We also consider a DFS-like random walk (DFS-RW) as a strong baseline by setting a very small in Node2Vec for deep exploration. The methods are tested on synthetic graphs with divergent structures. We randomly sample 20 root nodes and, for each root, simulate 10 walks show how many nodes with different distance explored at each step of the walk. The ideal situation for rooted walk paths with a fixed length is to cover up to nodes l-hop away from the current root. The results on circle graphs are shown in Figure 4 We can see from the results that our proposed BC-RW is much more competitive in exploring a wider range of SP distance. Further results and analysis on different graph structures are presented in Appendix A.12
4.3 PRESERVATION OF DISTANCE RELATIONS
As discussed in Section 3.2 distance resampling is proposed to preserve accurate distance relations via implicitly decomposing an SP distance-bass similarity matrix. Here, we show its interpretabil- ity for SP representations by visualizing the properties of embedded vectors Z when compared with
8

---

Under review as a conference paper at ICLR 2023
Figure 4: Exploration range of distance of different walk strategies on circle graphs. Column from left to right: different walk strategies, i.e, NRW, SORW, RS, DFS-RW, BC-RW (ours.).
the maximum likelihood optimization on other biased random walks. Environment configuration follows the previous section.
First, we evaluate the relation of distance measured on graphs and embedding spaces for each node pair. Specifically, distance on the embedding space is measured by inner product Z for given nodes Y; and Vy. and that on the graph measured by SP distance. Initially, we learn embedded vectors from walk paths simulated by each walk strategy and randomly sample 100 source nodes with 100 destinations for each source. The results on circle graphs are shown in Figure S (refer to Appendix A. extended results other graphs), which indicates that embeddings enhanced by distance resampling have a better tendency to maintain a linear relationship on the distance metric between the original graph and embedding space. The results also verified analysis in Remark regarding relations between the SP distance- based similarity matrix D and the distance matrix D.
Figure 5: Row 1: measured distance from the embedding space and the original graph. Row 2: whether distance relations violated in the embedding space. Columns from left to right: em- beddings learned by different walk strategies,i.e. NRW, SORW, RS, DFS-RW, and BC-RW (ours.), respectively. For ours, walk paths further simulated by distance resampling.
Second, try to find out how much the probability distance relation is violated in the embedding space, i.c., whether pair of nodes with larger SP distance is corresponded with less embedded sim- ilarity as described in Theorem [ We randomly take 10, 000 node triplets {v,, Ub v.)). and record if Equation is satisfied. The results on circle graphs are shown in Figure 5 to Appendix A.13 for extended results on other graphs). The figure confirms that our model much more satisfactory in preserving distance relation than existing methods. This is because BC-RW provides sufficient observation on each node by locating many remote nodes with a sequence of centralized nodes on graph, and thus distance resumpling based on such observation could preserve distance relations of each node within its exploration range.
5 CONCLUSION
In this paper, propose novel graph SP representation method called Betweenness Centrality- based Distance Resampling (BCDR) and discuss two significant techniques for an efficient and interpretable SP representation. The experimental evaluation indicates that BCDR improves the ap- proximation quality with a shorter response time for SP distance queries and possesses strong scala- bility to large-scale and complex graphs. Notably, the produced node representations by method also reflect the highly-efficient paths for high-order message passing in GNNs, which appears to be helpful for structural graph pooling and inference. We leave it for our future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
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.
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349-360, 2013.
Muhammad Asif, Hassan Raza, and Muhammad Imran Manzoor. A novel approach for tenuous community detection in social networks. International Journal of Data Analytics (LJDA), 3(1): 2022.
Grégoire Aujay, Franck Hétroy, Francis Lazarus, and Christine Depraz. Harmonic skeleton for real- istic character animation. In SCA 2007-ACM-SICCO H/CGRAPH/Eurographhee Symposium on Computer Animation, pp. 151-160. Eurographics Association, 2007.
Egon Balas. Tutorial paper x: A class of location, distribution and scheduling problems: mod- elling and solution methods. Belgian Journal of Operations Research, Statistics, and Computer Science, 22(2):36-69, 1982.
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.1 1119000CSS20006222
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.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In Proceedings of the AAAI conference artificial intelligence, vol- ume 32, 2018.
Mingming Chen, Ning Wang, Guofeng Lin, and Jedi S Shang. Network-basse trajectory search over time intervals. Big Data Research, 25:100221 2021a.
Wei Chen, Christian Sommer, Shang- Hua Teng. and Yajun Wang. Compact routing in power-law graphs. In International Symposium on Distributed Computing, pp. 379-391. Springer, 2009.
Yu Chen, Hanchao Ku, and Mingwu Zhang. Pp-oeq: A distributed privacy- prenecrireerring optimal close- query scheme for social networks. Computer Standards & Interfaces, 74:103484, 2021b.
Edith Cohen, Eran Halperin. Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2003.
2-hop labels. SIAM Journal on Computing,
Manuel Costa, Miguel Castro, R Rowstron, and Peter Key. Pic: Practical internet coordinates for distance estimation. In 24th International Conference on Distributed Computing Systems, 2004. Proceedings., pp. 178-187. IEFF, 2004.
Frank Dabek, Russ Cox, Frans Kaashoek, and Robert Morris. Vivaldi: A decentralized network coordinate system. ACM SIGCOMM Computer Communication Review, 34(4):15-25 26,, 2004.
Daniel Delling, Andrew V Goldberg, Thomas Pajor, and Renato F Werneck. Robust distance queries on massive networks. In European Symposium on Algorithms, pp. 321-333. Springer, 2014.
Anna Veronika Dorogush, Vasily Ershov, and Andrey Gulin. Catboost: gradient boosting with categorical features support. arXiv preprint 18/00 1363, 2018.
10

---

Under review as a conference paper at ICLR 2023
Mihaela Enachescu, Mei Wang, and Ashish Goel. Reducing maximum stretch in compact routing. In IEEE INFOCOM 2008-The 27th Conference on Computer Communications, pp. 336-340. IEEE, 2008.
Muhammad Farhan, Qing Wang. Yu Lin, and Brendan McKay. A highly scalable labelling approach for exact distance queries in complex networks. Network, 400(3B):8B, 2019.
Ada Wai-Chee Fu, Huanhuan Wu, James Cheng, and Raymond Chi-Wing Wong. Is-label: an independent-set based labeling scheme for point-to-point distance querying. Proceedings of the VLDB Endowment, 6(6):457-468, 2013.
Lucia Galovičová, Petra Borotová, Veronika Valková, Nenad L Vukovic, Milena Vukic, Jana Stefániková, Hana Dúranová, Przemyslaw Lukasz Kowalczewski, Natália Čmiková, and Miroslava Kačániová. Thymus vulgarís essential oil and its biological activity. Plants, 10(9): 1959, 2021.
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 on Information and Knowledge Management, CIKM 2010, Toronto, Ontario, Canada, October 26-30, 2010, 2010.
Peter E Hart, Nils J Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 102):100-107, 1968.
Alexander Hermans, Lucas Beyer, and Bastian Leibe. In defense of the triplet loss for person re- identification. arXiv preprint arXiv: 2017.
Omar Houidi, Oussama Soualah, Wajdi Louati, and Djamal Zeghlache. Dynamic vnf forwarding graph extension algorithms. IEEE Transactions on Network and Service Management, 17(3): 1389-1402, 2020.
Liying Jiang, Yongxuan Lai, Quan Chen, Wenhua Zeng, Fan Yang, and Fan Yi. Shortest path distance prediction based on cathoost. In International Conference on Web Information Systems and Applicatioon,, pp. 133-143. Springer, 2021a.
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, 2021b.
Andrey Kutuzov, Mohammad Dorgham, Oleksiy Oliynyk, Chris Biemann, and Alexander Panchenko. Making fast graph-based algorithms with graph metric embeddings. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 3349-3355, Flo- rence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 16555/1 URL /ttpp:://eeaaaatoooooooooooo
1325
James R Lee. Volume distortion for subsets of euclidean spaces. Discrete Computational Geom- etry, 41(():590- 615, 2009.
Sanghwan Lee, Zhi-Li Zhang, Sambit Sahu, and Debanjan Saha. On suitability of euclidean em- bedding of internet hosts. ACM SIGMETRICS Performance Evaluation Review, 34(1):157-168, 2006.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. :ttp::ioon.ht:::::
edde data June 2014.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27:2177-21885 2014.
Ziyi Liu, Lei Li. Mengxuan Zhang, Wen Hua, Pingfu Chao, and Xiaofang Zhou. Efficient strained shortest path query answering with forest hop labeling. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 1763-1774, IERR, 2021.

---

Under review as a conference paper at ICLR 2023
Yun Mao, Lawrence K Saul, and Jonathan M Smith. Ides: An internet distance estimation service for
large networks. IEEE Journal on Selected Areas in Communications, 24(12):2273-2283) 2006.
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: 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- 311 11-111111 19, 2013b.
TS Eugene Ng and Hui Zhang. Predicting internet network distance with coordinates based ap- proaches. In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pp. 170-179. IEEE, 2002.
TS Eugene Ng and Hui Zhang. A network positioning system for the internet. In USENIX Annual Technical Conference, General Track, pp. 141-154, 2004.
João Nogueira. A large-scale and decentralised applicationlevel multicast infrastructure, 2014.
Ruksar Parveen and N Sandeep Varma. Friend's recommendation on social media using different algorithms of machine learning. Globul Transitions Proceedings, 2021.
B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. Pro- ceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, 03 2014. doi: 10. 145/2623330.2623733
Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. Don't walk, skip! online learn- ing of multi-scale network embeddings. In Proceedings of the 2017 JEEE/ACM International Conference on Advances Social Networks Analysis and Mining 2017, pp. 258-265, 2017. 2017.
Martin Poirier and Eric Paquette. Rig retargeting for 3d animation. In Graphics interface, pp- 103-110, 2009.
Michalis Potamias, Francesco Bonchi, Carlos Castillo, and Aristides Gionis. Fast shortest path distance estimation in large networks. In Proceedings of the 18th ACM conference on Information and knowledge management, pp. 867-876, 2009.
Jianzhong Qi. Wei Wang. Rui Zhang, and Zhuowei Zhao learning based approach to predict shortest-path distances. In Angela Bonifati, Yongluan Zhou, Marcos Antonio Vaz Salles, Alexan- der Böhm, Dan Olteanu, George H. L. Fletcher, Arijit Khan, and Bin Yang (eds.), Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020, Copen- hagen, Denmark, March 30 April 02, 2020, pp. 367-370. OpenProceedingssoog. 2020. doi: .020 .34
00.5441/002/eeb.2222..3 URL httpt:t///// | http:p:://a...crg//..34/00//0//0
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, Ema 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-1258 08 2021. doi: 10.1928/TELKOMNIKK.. 19i4.18872..
Satish Rao. Small distortion and volume preserving embeddings for planar and euclidean metrics. In Proceedings of the fifteenth anmual symposium on Computational geometry, pp. 300-306, 1999.
Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-ave aware overlay construction and server selection. In Proceedings. Twenty-Fite Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pp. 1 1190-1199. IEFF, 2002.
12

---

Under review as a conference paper at ICLR 2023
Sean C Rhea, Patrick R Eaton, Dennis Geels, Hakim Weatherspoon, Ben Y Zhao, and John Kubia- towicz. Pond: The oceanstore prototype. In FAST, volume 3, pp. 1-14, 2003.
Fatemeh Salehi Rizi, Joerg Schloetterer, and Michael Granitzer. Shortest path distance approxima- tion using deep learning techniques. In 2018 IEEE/ACM International Conference Advances in Social Networks Analysis and Mining (ASONAM), pp. 1007-1014. IEEE, 2018.
Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290655000;2323-23336 2000.
A. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. A sketch-based distance oracle for web- scale graphs. Proceedings of the Third International Conference on Web Search and Web Data Mining, WSDM 2010, New York, NY, USA, February 4-6, 2010, 2010.
Jörg Schlötterer, Martin Wehking, Fatemeh Salehi Rizi, and Michael Granitzer. Investigating ex- tensions to random walk based graph embedding. In 2019 IEEE International Conference on Cognitive Computing (ICCC), pp. 81-89. IEEE, 2019.
Mirco Schönfeld and Jürgen Pfeffer. Shortest path-based centrality metrics in attributed graphs with node-individual context constraints. Social Networks, 2021.
C. Shaosheng, L. Wei, and X. Qiongkai. Grarep: Learning graph representations with global struc- tural information. In Proceedings of the 24th ACM international on conference on information and knowledge management, pp. 891-900, 2015.
Yuval Shavitt and Tomer Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEF/ACM Transactions on Networking, 16(1):25-36, 2008
Marcus Sokolowski and Danuta Wasserman. A candidate biological network formed by genes from genomic and hypothesis scans of suicide. Preventive Medicine, 152:106604, 2021.
Liying Tang and Mark Crovella. Virtual landmarks for the internet. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, pp. 143-152, 2003.
M. Thorup and U. Zwick. Approximate distance oracles. Journal of the Acm, 52(1), 2004.
Konstantin Tretyakov, Abel Jemas-Cervantes, Luciano
Jaak Vilo, and Marlon Dumas. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, CIKM 11, pp. 1785-1794, New York, NY, USA, 2011. Association for Computing Machinery, ISBN 97814503071 178. 178. doi: 10.1145/2063376220638444 brg/10.1145/2063300
URL https://doi.
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- 548, 2018.
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 preprini arXiv:2101.03464, 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.
13

---

Under review as a conference paper at ICLR 2023
Xiang Yue, Zhen Wang, Jingong Huang. Srinivasan Parthasarathy, Soheil Moosavinasab, Yungui Huang. Simon Lin, Wen Zhang, Ping Zhang, and Huan Sun. Graph embedding on biomedical
networks: methods, applications and evaluations. Bioinformatics, 36(4):1241-125 10 2019.
ISSN 1367-4803. doi: 10. 000100//boinfommaccc//hz7111,, URL https: http:pp://dc..org//1// wr0/ 1093/
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 Porritiiss-Simllttiion and Computation, pp. 1-15, 2021.
Kaiwei Zeng, Munan Ning, Yaohua Wang, and Yang Guo. Hierarchical clustering with hard-batch triplet loss for person re-identification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13637-13665 2020.
Weitong Zhang, Ronghua Shang, and Licheng Jiao. Complex network graph embedding method based shortest path and moea/d for community detection. Applied Soft Computing, 97:106764, 2020.
Han Zheng, Eng Keong Lua, Marcelo Pias, and Timothy Griffin. Internet routing policies and round-trip-times. In International Workshop Passive and Active Network Measurement, pp- 236-250, Springer, 2005.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph-hased semi-supervised classification. In Proceedings of the 2018 World Wide Web Conference, pp. 499-508, 2018.
A
APPENDIX
A.1
RELATED WORK
A.1.1 ESTIMATION OF ACCURATE SP DISTANCE
As important global measurement graphs, SP distance reflects the minimum travelling cost from node to node, similar to the geodesic distance on manifolds. Along the rapid emergence of large-scale graphs in many areas, space- and time-efficient estimation of accurate SP distance is urgently required in many downstream applications, In this part, we investigate the direct impact of SP distance estimation in different fields by discussing several real-world scenerios.
Case 1: find nearest points of interest in road and social networks Points of interest (POIs) (Chen et al. 2021a) are specific point locations that someone may find useful interest- ing, e.g. hotels, campsites, fuel stations, etc. real road network may contain millions of nodes, while thousands of users may issue SP distance queries simultaneously for searching the nearest. POI from their location, like 'iidiing restaurants within 5 km distance' or 'ranking restaurant search results by distance'. To achieve such demands, learning to accurately and fast answer SP distance with limited computing resources is high significance. Specifically, utilizing limited computing resources means the algorithm should be space- and time-efficient. Thereinto, less storage overhead enables the representations to be stored in users' mobile devices instead of centrally computing SP on the server. And less query time ensures that the computation of SP distance can be processed in real-time (since some POIs may change their positions frequently over time).
Case 2: construct skeleton graph from mesh for 3D animation In the literature of 3D animation, animating an articulated character requires constructing a skeleton graph to control the movement of the surface, i.e., place the skeleton joints inside the character and specify which parts of the surface are attached to which bone. critical technique (Aujay et al. 2007]; Poirier Paquette, 2009) to automatically embed skeleton into character relies computing harmonic function under the SP metric on mesh graphs. This requires finding a group of nodes that locally maximize SP distance with the user-defined node. Since the mesh of a deliccte--essribeee character may have tens or hundreds of vertices, estimating and finding such nodes with the longest SP distance accurately and fast are also well-motivated.
14

---

Under review as a conference paper at ICLR 2023
Case 3: estimate latencies in communication networks In large-scale communication networks, the latencies between Internet hosts are defined as a round-trip measurement from one to another (i.e., SP distance). which is utilized for performance optimization in many network applications such as content distribution networks (Ratnasamy et al. 2002), multicast systems (Nogueira 2014). distributed file system (Rhea al. 2003), etc.
A.1.2 APPROXIMATE SP REPRESENTATION
Hard-coding Perspective Compared with exact SP representations that improve query speed at the expense of huge storage costs, approximate methods are designed find compact and scalable representation of high performance both in time and space. The basic idea of these methods is to reduce the complexity of SP distance matrices. Thorup and Zwick (Thorup & Zwick, 2004) initially observe that a hierarchical sparse sampling of nodes could significantly reduce the number of elements in the distance matrix, and all pairs of SP distance are thus approximately represented by the distance relations on those nodes with bounded error. They also provide a time-efficient algorithm to compute the pruned distance relations. Several later extensions (Baswana & Kavitha 2006 Enachescu et al. [2008] [Cen et al.) (209) are proposed to improve the processing time and space on specific graphs. However, these methods still have limitations on space complexity and accuracy. First, the sampled distance relations take (a
space which is not linear to the number of nodes N, thus inducing scalable problems on large graphs. Second, the bounded error is often unacceptable
graphs with smaller diameters since even the most accurate model (with ag = 2) allows three times the error of real distance.
Addressing these issues, landmark-bast -based distance estimation methods (Potamias et al. 2009 Gu- bichev et al. 2010 Sarma et al. 2010) are proposed. Instead of sampling hierarchical sets of nodes, landmark- based methods only preserve distance relations between a fixed number of nodes (called landmarks) to others on the graph, and all pairs of SP distance could be bounded by their distance related to landmarks according to triangle inequality (Zheng et al., 2005 Lee al. 2006 Mao al., 2006 i.e.. for any nodes Va and Ub.
max Dai Daal S Dab S min Dai + Dal LE
B,EL
where Das denotes the SP distance between v, and vb. L denotes the set of landmarks. The average accuracy could be optimized by selecting proper landmarks that covers as many SPs possible. Unfortunately, finding the optimal finite set of landmarks with the minimal size has been proved to be Na-hard, which mapping to a set-cover problem (Balas) 1982). Therefore, several heuris- tic selection strategies are discussed to tight Equation 9 by leading Dub almost near to its upper bound (Potamias et al. 2009). Other efforts (Gubichev et al. 2010; Tretyakov et al. 2011) are made to store SP trees for each landmark instead of distances at the cost of extra storage and response time. Nevertheless, the approximation performance in these models relies highly on graph struc- tures, since less-centralized graphs (e.g.. grid-like graph) and graphs of large diameters (e.g.. large planar graph) require a large number of distributed landmarks to cover remote pairs of nodes.
Learning Perspective Instead of the hard-coding techniques mentioned above, our work steps forward from a learning perspective of SP distance estimation, which constructs general and scalable representations for arbitrary graphs. Under the low-rank assumption of SP distance matrices, the basic idea of tearning-based methods is to transform the graph into metric space while preserving the distance between pairs of nodes. As the embedding space is low-dimensional and continuous, extracting distance from sarming-based SP representations is fast and scalable. However, directly optimizing the distance between all pairs is time-consuming which takes at least O(N2) time for computing distance and subsequent optimization. Towards this, many graph coordinate systems (Ng & Zhang 2002; Tang & Crovella, 2003 Costa et al. 20044] Dabek et al., 2004 Ng & Zhang 2004) have been studied the past years. To reduce processing complexity, a feasible Tearning procedure for very large graphs later proposed in Orion (Xiaohan et al. 2010) contains three steps. First, perform breadth-firs search (BFS) from a small landmark set L and record node pairs as well as their distance training triplets {(V1, Va, D(a)) where va E I,, Va E V. Second, create graph coordinate system M by preserving distance relations among nodes in L, i.e.,
Σ ID Diyl
arg min LM= [EEL
(10)
B.yEL
15

---

Under review as a conference paper at ICLR 2023
where u.M denotes the embedded vector corresponding the node Us and Dij denotes the geodesic distance between vgM and U/ measured on M. Third, fix I,M and calibrate distance between other nodes and landmarks iteratively. Among these steps, the metric tensor defined on M significantly af- fects the accuracy of distance estimation, and models regarding embedding in euclidean space (Rao)
1999
Lee 2009 Xiaohan et al. (010)) and hyperbolic space (Shavitt & Tankel 2008 Xiaohan et al.
2011
are well studied respectively.
Inspired by the great success in graph representation learning (GRL.) further work (Rizi et al. 2018 Schlötterer et al., 2019) including ours treats M as an agnostic but definite manifold learned by GRL techniques and estimates distance based on learnable metric criteria (usually multi-layer percep- tron). Therefore, the learning task here is converted from "calibrate the position of each node" to "learn powerful metric criteria to extract distance everywhere. This novel paradigm achieves higher accuracy with reduced training time despite the fact that we are unsure about whether general GRL models could embed sufficient information infer all pairs of SPs. In this paper, we thus discuss an interpretable SP representation learning method and improve the comprehensive performance of SP distance estimation.
A.1.3 GRAPH REPRESENTATION LEARNING
Graph representation learning (GRL) organizes symbolic objects (such as nodes, edges, and clus- ters) in way such that their similarities on the graph are well-preserved in the low-dimensional embedding space. Currently, most of these methods focus on preserving arbitrary linkage on graphs by considering high-order adjacency matrices, and are categorized into matrix factorization (MF) and random walk (RW) approaches. Thereinto, our work shares strong connections with general RW approaches, which embed remote nodes' correlation within linear complexity compared with MF methods. The basic idea of RW-based learning methods proposed in Deepwalk (Perozzi et al., 2014) is dump complicated linkage structure on graphs into a few fixed-length node sequences in a statistical view and learn node embeddings to reflect their co-occurrence on walk paths us- ing a skip-gram algorithm (Mikolov et al. 201 (b) The learning process to solve a maximum likelihood optimization problem based on observed sequences, i.e., for any nodes v' and lbb
arg max log ô (Z.2%% + P log (- -z. Zz,Z()1 2nn
(11)
where Z. denotes the embedded vector of va. À denotes the number of negative samples, o(-) de- notes the sigmoid function where ((x) =(1 - - --- and (-) denotes a probability distribution of the negative sampling. Several practical strategies are proposed in the past few years to sim- ulate structure-awart traversal on graphs in RW-based methods (Grover & Leskoved 2016 Cao jet al. 2016; Perozzi et al. 2017 Chen et al.) (0088). detail, to enhance sensibility on divergent structures, Node2Vec (Grover & Leskovec| (016) exploits a biased random walk strategy to per- form combinatorial traversal on graphs, including breadth-first search (BFS) and depth-first search (DFS), which explores both neial-neighoorhood linkage and correlation with remote nodes simulta- neously. To reflect the locality around each node, a random walk with restarting mechanism (called random surfing) is applied in learning point-wise mutual information (PMI) representations (Cao et al. 2016). For capturing multi-scale representations of different-orde neighhorhoods, hierarchi- cal random walks by skipping some of the nodes on paths also proposed (Perozzi et al.) 2017 Chen et al. 2018). Recently, Schlotterer et al. (Schlötterer et al., 2019) observed that RW-based methods perform better than others in exploring wide range of distance and evaluated these meth- ods as being helpful for SP distance estimation. However, specific and insightful investigation of RW-based SP representation remains to be studied. this paper, we discuss a novel biased random walk strategy toward high-order SP exploration and provide an explicit optimization algorithm for pisseree-preserved representation.
A.2 EFFICIENT IMPLEMENTATION OF BCDR ALGORITHM
We discuss here an efficient implementation to integrate the techniques mentioned in Section 3.1 and 3.2 Our algorithm is presented in Algorithm| | including constructing SP representations and answering online distance queries. The description and analysis of these procedures are provided as follows.
16

---

Under review as a conference paper at ICLR 2023
Algorithu I: construct SP representations & answer distance queries
Input: inpar graph G (V. E). set of landmarks distance queries of node pains Q. dimension of embeedingg d. number walk paths on each node Wa.. length of walk paths l... BC decay coefficient Ç. number resampled walk paths on each node Wost, length of resumpled walk paths lout distance decay coefficient o, training epochs m, learning rate
fy. usage of fast query r, usage of boosting x-
Output: representation Z. predictor ge- estimated distance (optional: regressors by b2. global representation Z')
Def sim_DT with aC (G. L):
36. Def cens__CDB (G. d, L, Way lan S. Wast lout, a, 171 v) T.n <- aim. DT wwt...t..BB... (C, LI, P list[
distance triplets := list
37
approximate BCss
dict (wy 00 Vo, E V)
for 12 SE do
for each lundmark n, e. do
D, +- sim_BC_Kalk (G. ",, Whe Ins 71
7/(ss] <
probabillitie of candidates nodes Pi = dict
for each node uj V reached by BFS from v, do append (y. D.p) T
41
for E keys do P((ey) = (.1)). end
>/1y] +- 7/1l 20g
43
end end
for walk from wout do
sample walk path p. of length lown by normalized P. append p. to P
return 7
Def a Lim_BC_Naal (G. vo who, Li. 73:
end
15
distance mup D. : dict 0)
end
visit counter B == dict(y; O, Ve, e V} for walk from 0 to Min do
maximize Equation with Zxxa and Py skip-gram. define learnuble distance predictor go (B", B for each epoch from 0 to mn do LMSE (1a. vn) =
i
sign set = {
current node length 0; :-
52
lo Zu) Datl", V(v., Dat) T minimize L.sE with şi at the learning rate t by SGD.
while c < Lo,
probubilities of the next candidate nodes
5
F. :- dict()
end if' then
for E E. A E S, do
define CadBoost by, ba.
P [ry] (- 7.14 (2- tanb(s - Blr:D)
2' (2/1Z = list (P Vey E 1.) Train b, by (Z) ZZ) Dat.
by E then
D.joy] min(DDlv,),. D.(u.) +-1
Train by by (Z), Zi (Z, end
(Z,, 2.)..o Zo3) Dor
else
26
end
D.joal = D.(vo] +1
return Z, ( 2', b,, bu]
end
< Def query_ECDR (Q. Z, 95- 2" BCDR
sample next on from normalized P
estimated distance DIv., 2/]
Sz. Zn): V(va, v.) E
S
if'x tten 45
| Die,, 1y] by ZZ Zg (2 Z,), D(v,,
G +- 4 + B(cm] Blon] +1
end
if 7 then
end end
4
Dic., vol + 1, Viv,, QN
end
return D.
return D
A.2.1 SIMULATION OF DISTANCE TRIPLETS & BC WALK
To simulate distance triplets (line 1 to 11), we perform BFS from fixed number of landmarks L and record their distance to each node on the graph (line 6 and 7). L comprises nodes that are selected by heuristic strategies (e.g., by their degrees in descending order randomly), and the simulated triplets with linear complexity reflect a sufficient group of distance relations among V x V for metric learning. Before simulating BC walk paths, pre-computed BC of each node is also required first, which takes at least O N M) time on unweighted graphs for an exact solution. To reduce the time complexity, we consider a time-efficient approximation by integrating this process into the above simulation of distance triplets (line 8). Intuitively. BC((a, measures some kind of relationship between Ug and the centers of the graph, and nodes with larger BC values possess shorter average SP distance to any node on the graph. Since BFS visits each node just in ascending order of distance, we thus estimate BC on each node by the average distance to all landmarks in L without introducing extra time complexity.
Then, in the simulation of BC walk paths (line 12 to 35), we are interested in "nodes on these walk paths" instead of the full paths themselves, and the former with their distance to the root 0; (i.e., D.) will be passed to feed subsequent construction (line 39). Therefore, we enlarge the node coverage by a decay mechanism on BC to diverge different walks. Note that BC-based random walk possessing the ability to explore remote nodes tends to choose the paths that are prone to travel further, which causes ignorance of nodes some dead ends. Addressing this, as stated in line 22, the probability of transiting to a node with large BC will be saturated after a sufficient number of walks passing through it, which means some rare paths are getting much easier be visited later.
17

---

Under review as a conference paper at ICLR 2023
A.2.2 LEARNING EMBEDDINGS & DISTANCE PREDICTOR
To learn node embeddings Z on SP structures (line 37 to 49), we initially sample a group of BC walk paths as distance maps } } (line 39), and then resample from them to feed the skip-gran gram algorithm by considering distance decay and BC (line 42 and line 45), which preserves the property of distance relations discussed in Theorem | Besides, the resampling process also provides a shape transform of observed node sequences from Win x lin to Wout lout- Let / (Winlin) (uwout//u)) > 1, and this property leads the actual time cost of learning embeddings to be reduced to its 1/3, compared with learning directly on the original paths.
For the learning of the distance predictor (line 37, and line 50 to 54), we utilize two-layer fully connected neural network as the predictor, which takes the concatenation of two nodes' embeddings as input, and outputs scalar to indicate the distance (line 50). The predictor model is learned from distance triplets T by minimizing a mean squared error (MSE) between the predicted value and the real distance using the stochastic gradient descent (SGD) technique. Finally, the parameter of neural network @ and node embeddings Z are stored as graph SP representations.
To improve the prediction results, we further integrate the distance predictor with CatBoost tech- niques (Dorogush et al. 2018). Initially, we treat the feature of nodes as combination of global features and local features. Thereinto, local features are already represented by Z, since we have constructed SP representations on each node locally. For the global feature of any node e; we directly leverage the distance to each landmark as its global embedding Z! Then, we train two Cat- Boost regressors (i.e., b,, b2) in turn. The first regressor b takes global features of two nodes as input and predicts their distance as output (line 58), while the second regressor b2 takes as input not only such global features, but the distance predicted from both global (i.e., b1 (Zz. Z1,)) and local (i.e.. go (Za, Zb)) features. Finally, the outputs of by are regarded as the final prediction results of SP distance.
A.2.3 ANSWERING DISTANCE QUERIES
For distance queries, We provide two versions with different properties based on the same SP repre- sentations. As revealed in previous studies of learning- based SP representation methods, the distance relations in local neighborhoods are really hard to converge, which causes decline in average accu- racy (Rizi et al. 2018 Kutuzov et al. 2019). For an input query pair (Va, 0b), it is helpful to alleviate such decline if we perform an extra search among first-order neighbors (i.e., search in the adjacency matrix) to judge if (va, v6) is an edge in the graph. Since this practice prolongs the total response time, we also preserve a fast version (BCDR-FQ) without neighbors searching for some potential applications.
A.2.4 PARALLELISM
The implementation of BCDR is easy to be highly parallelized. In detail, the construction of SP representations could be divided into three parts, including simulating distance triplets, performing BC-based random walk, training embeddings, as well as the distance predictor. First, the BFS from each landmark could be parallelized at a thread level up to the size of the landmark set. Second, for the simulation of BC walk paths, the paths from different roots could also be simulated simultane- ously. Third, the training process in the skip-graa sii-gram algorithm and neural network could be locally parallelized by matrix computations.
A.3 THEOREM FOR CLARIFYING THE SIGNIFICANCE OF BC-BASED RANDOM WALK
of nodes that are h-hops away from Va and (((h) = -Wa as the number of nodes in the set. Nodes in AA)) could be divided into two sets, i.e. en(v.) and fn(va). Thereinto, ex(va) comprises nodes that have an edge with the nodes in ((h+1) (called connective nodes), and [t(va) comprises the other nodes (called final nodes). The BC value of each node is approximated by considering only the shortest path of nodes within range of k-hops locally. Let PR(N()) + (((b+1)) represent the probability to transit from N((h) to N 1h+1) by naive random walk, and (b(N - >N(h+t) represent that by BC-based random walk. Let PR([((Vaa) - ex(va)) be the probability of transition from J (va) en (Va). E(va) is the
Theorem 2. Define Nohh) = Day = hi
18

---

Under review as a conference paper at ICLR 2023
eccentricity of Vo- E(va) maXuEG Dab. Then, for sufficient large E(va), any node vo E G and any h > 1,
Pa(Na (1) + +Na )
B(k)
+C
(12)
PR(Na NNattt))
A2 1 +C>0
lim
((k) +C
B- -1-h
A1
(13)
A len(va)l
A2 (va) - en (va))
C 0.
[vn)
Proof. We simplify symbols Adhh Nath) en (va); Su as No. NR, cn. Jn for short.
NA #(
(oylos )
i=h
(14)
NR = #
U
fuglus E((T))
i= m=
where #-)) is counting function indicating the number occurrence times specified nodes, i.e., the cardinality of sampled set.
According the definition in Theorem 2
we have Nv. = |eal + [Sa]- Since only nodes in en
could travel from N₁ to N1+1, We firstly consider PR(en - en+1leл + NN+1) and PB (ex Ch+1leh N1+1).
For general random walks, the choice of destination is based on uniform sampling, thus causing
PR(En + entilen + NN+11) lea+1l
(15)
Nu+1
For BC-based random walk, need calculate BC value of nodes of ea+1 and fa+1 for starters. Let BC((x+1) and BC(f++1) represent the BC value of nodes in ea+1 and fn+1 respectively, and the correspond legal SPs counts come from sources as (Na + Nat2). (Na + W (Wi+1 + 2 and (N++1 > Nh+1). And we use BC([- + .) as the BC gain from the specified source, then
BC(LÝ, Nn+23) NANE+2
BC(LN, *N++1) Nn(1fa-1l + 1
(16)
BC([N++1 + NN+23) Nn42(1fhual len+1l889)
BC([NN+1 - Wh+13) = N2.119(2)
where B( means average BC gain between nodes in ca-1 and N and 8 means average BC gain between nodes both in ex+1, which are constantly related with G. Therefore, we have
+ BC(( = NANA42 + (Na + Na + +
(17)
Likewise, we calculate
BC(Jx+1) -N (a(1/n+1 len+1l Nx42(110+11 +ett1 (0) + N N2 =(NA + N4 + N2+11 3(2)
(18)
To compare the above BC(e++1) and BC(fh+1).
BC((++)
(Na + N2+2) N 9
9(2)
(19)
BC(E
NaN142 + (Nr + N142)len+11e (3()) + N442lfoull + N2 N24,,0? B!?)
19

---

Under review as a conference paper at ICLR 2023
note that for any Ny and (a.))) = No Nx - Ny where 2. y E {0, (v,)),
N lim
lim k-+0(va)-1-A ((a.)) (-1(we)-1-h
((k) = 0
(20)
Equation 18 is reduced to
BC(fn+1)
(x))))
c(h2)))))
28 c(k))
(21)
BC(en+1)
1 2c(K)m|en+11 c(k)]fn+zl + c(
Then, we perform weighted random sampling based on BC and get
|ex+1
Ps(en entilen - Nh+1)= leh+1 + 21 (k))
(22)
Now, we consider the relation between Pn((N - W + Nh+11) and PB(Nr + N1t1).
PB(Nn + Nn+1) = PB(e)))B(es) + +N++1)
PR(Nn + +N++1)
PR(EA) PR *N++1
PB(Na-1 + en) PB (B + PB))B(() + ee)
PR(NA-1 + eh) PR(NN-1 + PR(h - en)
P + en) Pn(Na-1 + en)) -PPp(h - en)
-1+ PR(NA-1 + en) + PR(NN-1 7 fn)PA(fn eh)
(23)
Pn(sn + en)e
Pn(Nn-1 + )x) + PR(NN-1 + [n) + en)
[ui[1 - 21 ((k)][1 - -Pr(Sh -e,]]
-1+
(1 + [ + -215n18f' (kk)) Prk)) + +n))
PR(Sn + en)e
PR(N + en) + PR + fn)PP(fh - +))
Pn(fa >en)e (tNN--1-,,)+PP(M. Palla B(k) =
1/ (a+
Let C =
Since C is non-negative value independent of k. finally we get
PB(Nn Nn+1) 1 B(k) +C
(24)
PR(Nn N141)
where
lim B(k) + +C= A2 11 C.
(25)
1-+8(v.)-1--
A
Remark 1. Equations 12 and 13 in Theorem 2 give definite conditions under which BC-based random walk travels further than random walk. Since nodes in U. 's h-order neighborhood (() could always be divided into en (va) and (v(Va) like Figure 3a BC-based random walk improves exploration distance beyond local loops and dead ends in contrast with naive rundom walk by two aspects. On one side, even if ((h) comprises a larger number of nodes in fu(va) than en (v())) and thus A decreases, BC-based random walk tends to transit in en (v())) to get near with the next desired set Nohh (b++1) On the other side, even if nodes in (va) have fewer links those in en (va) and thus A2 increases, BC-based random walk tends to transit between filVa (Va) and en en(va) instead of looping within Jn (Va) well No (h)1)
20

---

Under review as a conference paper at ICLR 2023
A.4 PROOF OF PROPOSITION
I
Proof. In Proposition
1 we optimize an approximate objective Ln instead of Lm, i.e.
(z) P(s))
{ (B (V) log o (Z.2,)) AI 0e- fog o( (-
(26)
VIEV
Here, we rewrite the negative sampling item of Equation 26 as
E Pu 8( (-Z,Z = Σ P((x)l:))log((-ZZZ1
VEEW;
(27)
= -.
Σ
Then, for each pair of vs E V and vy Wi, we get independent objective by combing similar items from the total likelihood 6n. and reach
(n( ΣΣ Z,)
BYEV oyEW,
(28)
CZ, Z2) P(v,, 2/y log (- Z,Z,) (-zz())))))))
(P log a( (Z.z,))
Let δ zz", for each node pair (Va, Ub) with SP distance Dan, consider
Das Z arg max L' ('Z,,, Zb)
(29)
Zn.Zo
Remember that Qw, is distribution resampled from Pw,, efficient approximation to Pw:. i.e,
BC
Qw. (11) Eewww a Das BCC(K)
(30)
Denote (C(v)) by no. according to Equation 30 the joint distribution of each pair (Va, v2) could be formulated
P(va, v6) P((a)) P(velva) P(va) a Pahmo
(31)
Then, consider the formualtion of PA, (ublva), Recall that the negative sampling is a uniform distri- bution on Wa which are simulated by BC-based random walk, and the probability of v. occurrence relies on 7 and Wa. Thus there holds
Pa (voluva))
Tb
(32)
n(va)
where x(wa) is in proportion with the number of nodes covered by W. on the graph. Furthermore, Equation 29 could be rewritten as
A P(va)r Ol
Des arg max Ja Patry yo log (Das) + k(va)
(33)
D.s
Solve the above problem by just let 8C( be equal to zero, i.e.,
8Dab
aL(ca, vb)
A P(v.)a" Das) k(v,) ploahooo + Das) =
(34)
a
After simplification, we get
A x(Va)
Dab = Das log a log
(35)
Let 6 = >va) and there holds
Dab -log + Das log
(36)
n
21

---

Under review as a conference paper at ICLR 2023
A.5 REMARK FOR THE RELATIONSHIP BETWEEN DISTANCE MATRIX & DISTANCE-BASEE BASED SIMILARITY MATRIX
Remark 2. Equation in Proposition I reveals the linear projections between elements in Đ and D. Thereinto, - log is big positive constant with respect to [og] - llog X/, and Dub log is a negative value that decreases linearly with SP distance Dab- It indicates that there exists a finite distance range N+, for each node vb E {vzz Daz S n),, the distance relation between va and Vn could be well-optimized by converging ZuZz - Dab > 0. It also reveals that the significance of distance resampling is to preserve the SP distance relations between nodes which are well-observed on given arbitrary walk paths. Besides, although the similarity matrix D could not directly tell the absolute distance, also shares similar properties with D, i.e. if we fix vo as the source node in path, the comparison between the similarities of (Va, 0b) and (Vas ve) just reflects the SP distance relations between them. This practical property discussed in Theorem
A.6 PROOF OF THEOREM T
Proof. In terms of node pair (Vas 0b), as proved in Proposition their similarity Dab in the embed- ding space varies linear with respect to the SP distance Das on the graph, i.e.,
Dab lloge Das log
(37)
Likewise, for (Va ve). there holds
Dael log + Dac log a
(38)
where 0 < a < 1 and e relies on Wa which is independent of vs and Ue.
Then, consider the distance relation of Va. Up and ve. there holds
(Dab (Dub Doc) (Dab ((Das Dac)) log log a (Dab Dac)² S 0.
(39)
A.7 MOTIVATION OF BCDR PROCEDURE AGAINST DIRECTLY SAMPLING SPS
We further clarify in this section the motivation for leveraging BCDR instead of directly sampling SPs. As a prerequisite, it should be acknowledged that we need sampled SPs as observation to opti- mize node embeddings Z. However, to perform sufficient observation on all pairs of shortest paths is time-consuming, which takes at least ((N²) time on sparse unweighted graphs. Towards this. an intuitive idea is to sample a limited number of paths that starts only a few nodes (landmarks). But it will introduce strong bias on the landmarks and ignore many shortest paths far away from them. To alleviate this bias, in BCDR, we hope to observe shortest paths rooted at all nodes on the graph (instead of the landmarks only). Therefore, we need some strategies to overcome the huge complex- ity of directly sampling these paths (since requires performing BFS on all nodes). The proposed strategy is BC-based random walk where we intend to equip 'random walk' with the awareness of high-order SP structure and make the sampled walk paths much more likely to be certain shortest paths. This strategy is comparatively efficient since the sampling complexity is proportional to its path length I. Then the subsequent module DR further resampled from these paths for implicitly preserving SP distance relations on Z.
According to the above discussion, a brief procedure of BCDR with its motivation could be summa- rized as follows.
estimate BC just by BES from only few nodes (landmarks). motivation: determine which node is prone to trigger high-order explorations of SP distances.
perform BC-based random walk.
motivation: observe the potential shortest paths rooted each node sufficiently.
leverage DR for resampling approximate random shortest paths.
motivation: implicitly preserving distance relations on observed paths.
22

---

Under review as a conference paper at ICLR 2023
optimize Z from the observation of the resampled paths. motivation: reflect the SP structure on the graph instead of arbitrary linkage.
Each step above possesses linear complexity with respect to N (number of nodes in the graph).
Besides, we are convinced of the necessity of BCDR procedure and would like to explain it carefully from both technical and empirical perspectives.
From a technical perspective, directly leveraging shortest paths as observation to optimize has few shortcomings.
Prohibitive Complexity of Sufficient Observation. Observing all pairs of SP distance requires at least O(N2) time for sparse unweighted graphs. Alternatively, insufficient observation with linear complexity will cause loss in accuracy (see experimental results below).
Inflexible Path Length for Optimization. Since we leverage the skip-gram algorithm for op- timizing Z. it should be clear how long the sliding window size is, serving to reconstruct the distance relations between nodes. But shortest paths rooted significantly divergent path lengths, which causes difficulty in determining proper sliding win- dow size on different paths, i.c., a longer window helps to capture long-distance correlation but causes indistinguishable in shorter paths and vice versa. Alternativey,, if we only select shortest paths of a certain fixed length, paths shorter than this length will be ignored, thus impairing the performance.
certain node factually possess
Correspondingly, the BCDR procedure overcomes the above shortcomings as follows.
Linear Complexity of Such Observation. Instead of directly simulating shortest paths, sam- ple paths by BC-based random walk and transform the paths into approximate random shortest paths by DR. Both of these operation share linear time complexity. Also, the optimization on such resampled paths is proved to share similar properties with that on real shortest paths by Proposition 1 and Theorem
Flexible Path Length for Optimization. Since the paths are resampled from random paths, the number and length of them (i.e., Wout: (out) could be customized. We are thus able to fix them at certain proper length for subsequent optimization.
From an empirical perspective, we further construct and evaluate 6 competitive baselines which have the same architecture and hyper-parameters as BCDR, but adopt different intuitive strategies to directly optimize on shortest paths. The basic description of these baselines is stated as follows.
Shortest Paths on Landmarks only (SPoL) Since need anyway perform BFS from landmarks to acquire distance triplet for learning distance predictor, we intuitively retrieve the shortest paths starting from the landmarks. This operation introduces little extra time cost. The size of landmark set is the same as BCDR (i.e., L = 80)
Shortest Paths on Landmarks only with Fixed Length (SPoL-F) This is similar to SPoL but restricts the output walk length certain level (the same BCDR, i.e., loue 10).
Shortest Paths on All Nodes (SPoN) In BCDR, we perform BC random walk on each node Va to locate its position the graph. Here, directly sample shortest paths from v, any other nodes instead. Specifically, for each source node we take uniform sampling over V to acquire the destination nodes, and retrieve the shortest paths between them. The number and max length of shortest paths on each node is the same as BCDR (i.e., Wout 40, lout 10).
Shortest Paths on All Nodes with Fixed Length (SPoN-F) This is similar to SPoN but restricts the output walk length (the same as BCDR, i.e., lout 10).
Shortest Paths on Arbitrary Node Pair (SPoANP) We randomly select a group of node pairs (v,, v2) and retrieve one of the shortest paths between them by BFS. The number of paths the same as the total number of walk paths on all nodes in BCDR (i.e., N x Woo)).
Shortest Paths on Arbitrary Node Pair (SPoANP-F) This is similar to SPoANP but restricts the output walk length (the same BCDR, i.e., lout 10).
All of the above baselines are evaluated on GrQe dataset, and the experimental results are presented in Table
23

---

Under review as a conference paper at ICLR 2023
Table 3: Comparisons between BCDR and directly sampling SPs by different intuitive strategies. PT: pre-proeessing time, ST: time of sampling paths, mAE: mean of Absolute Error, mRE: mean of Relative Error.
Model
PT
ST
mAE
mRE
SPoL
60.71
15.36s
0.9703
0.1641
SPoL-F
60.46s
15.63
1.2874
0,1961
SPoN
283.0 s
235.5
1.0411
0.1645
SPoN-F
2,702 8
2,656
1.2961
0.1969
SPoANP
282.1
234.4
1.3564
0.2047
SPoANP-F
6,341
6,290
1.3294
0,2003
BCDR
69.61
27.66
0.7043
0.1274
We from the table that BCDR outperforms all the baselines in approximation quality (i.e., mAE and mRE) within proper time. Specifically, SPoL possesses desirable pre-processing time since only the shortest paths rooted landmarks are considered. But they are plagued with insufficient observation of other shortest paths that do not pass through landmarks. SPoN and SPoANP suffer huge complexity when retrieving shortest paths on the whole graph. and perform even worse due to the uncertainty of reasonable sliding window size, From SPoL-F, SPoN-F, and SPoANP, we see that even if the path length is fixed, some uncaptured shorter paths will also cause loss in accuracy.
A.8 DATASETS
To thoroughly evaluate our proposed method, conduct experiments real-world graphs and synthetic graphs with divergent properties on sizes, structures, diameters, etc. Thereinto, real-world graphs are extracted from Stanford Large Network Dataset Collection (Leskovec & Krev] 2014), and synthetic graphs are simulated according to specific rules described in AA8.6 The visualization results of each graph are illustrated in Figure 6 and the corresponding statistics are presented in Table 4 In the experiments, we show the efficiency and scalability of BCDR on real-world graphs of different sizes and test on smaller synthetic graphs with different structures further analysis of exploration range and distance preservation. Here are brief descriptions of these graphs:
A.8.1 CORA
This is graph that 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.8.2 FACEBOOK
This is graph that describes the relationship among Facebook users by their social circles (or friend lists), which is collected from group of test users. Facebook has also encoded each user with reindexed user ID protect their privacy.
A.8.3 GRQC
This graph recorded from the e-print arXiv in the period from January 1993 to April 2003, which represents co-author relationships based their submission. Each undirected edge (e,, v,) represents that an author v; is co-authored a paper with another author vy. one paper is owned by k authors, complete subgraph of & nodes is generated correspondingly.
A.8.4 DBLP
This is graph collected computer science bibliography that provides comprehensive list of research papers in computer science. As an undirected collaboration network, each edge reflects the corresponding two authors who have at least one paper together.
24

---

Under review as a conference paper at ICLR 2023
(a)
(c)
(d)
(
(g)
(h)
(i)
(k)
Figure 6: Visualization results of the graphs used for evaluation. (a): Cora. (b): Facebook. (c):
GrQc. (d): DBLP. (e): YouTube. (f): CG. (g): TG. (h): TCG. (i): TRG. (j): SG. (k): NG.
A.8.5 YOUTUBE
This is a graph constructed from users' social relations on a video-sharing website Youtube, Each node represents user, and each edge indicates friendship between two users.
A.8.6 SYNTHETIC GRAPHS
We also construct some smaller graphs reflecting one or some of the typical sub-structures which are frequently occurred in complex graphs. The simulation rules of each graph are listed as follows.
Circle Graph (CG): this is graph that contains several circles of different sizes. The sim- ulation of circle graphs takes an iterative process where for each newly introduced circle, there are limited number of nodes (called exit nodes) connected to the previous circles.
25

---

Under review as a conference paper at ICLR 2023
Table 4: Statistics of the graphs used for evaluation. N denotes the number nodes, M denotes the number of edges, RoBC denotes the range of BC, mBC denotes the average BC on nodes, 'D denotes the diameter of a graph, BFS denotes the average processing time of breadth-firs search on all nodes. Each graph is considered an undirected and unweighted graph in the SP representation problem.
N
M
M/N
D
RoBC
mBC
BFS
Cora
2, 708
10, 787
3.9834
21
375.20
2.7174
0.0074 8
Facebook
4, 4,039
176, 437
21.846
8
1,306.9
0.8993
0.0191
GrQe
5,242
30, 042
5.7310
17
148.43
2.7219
0.0148
DBLP
317, 080
0494, 866
3.3110
21
1, 140.9
2.0795
46.0907
YouTube
1, 134, 890
5, 975, 248
5.2650
20
691.0986 S
CG
197
216
1.0964
46
0.6058
0.1032
TG
384
984
2.5625
100
0.4987
0.0928
TCG
242
594
2.4545
31
0.4891
0.0551
TRG
134
133
0.9925
12
0.6416
0.0630
SG
550
585
1.0636
85
0.3068
0.0528
NG
200
364
1.8200
28
0.2914
0.1215
Triangle Graph (TG): this a graph possessing several cliques which are linearly connected
mutually.
Tri-cirele Graph (TCG): this is graph that combines the properties of circle graphs and triangle graphs. Here, each circle is simulated by connecting triangle sub-graphs end to end.
Tree Graph (TRG): this is graph that is generated from one root to several leaves recur- sively. 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 (SG): this is a graph shaped like a spiral line. We first simulate a line graph and add edges between nodes with exponentially increased distances by their indices the line.
Net Graph (NG): this is graph containing grid-like connections between nodes. We define small probability of dropping those edges stochastically.
A.9 BASELINE & PARAMETER SETUP
The parameter setups of each baseline are listed as follows. For the oracle-based method, ono is set to for the best accuracy, as discussed the previous work. For the landmark-based method, we choose sufficient size of the landmark set [L] 128 and take the constrained strategy, i.e., for each landmark selected, nodes within two hops are discarded from consideration. For learning- based methods, the embedding size d is fixed 16. In addition, the number of selected landmarks in learning-basee methods up to 80 for small graphs (i.e., Cora, Facebook, and GrQe) and 24 for large graphs (i.e., DBLP and Youtube). Other hyper-parameters of each model follow the default configurations discussed in their works. For the baselines proposed in road networks. the coordinate- related features are omitted in their models, since there's 's no coordinate assumption in our graph datasets. For general GRL methods, all of the baselines follow the default configurations and are further trained by linear regression to extract the distance between any two nodes.
For our proposed method, we simulate win = 20 walks on each node, and each walk is truncated at a length of 4m = 40. Each landmark is selected randomly up the size of landmark set [T.] The number of negative samples is set to 1. The process of distance resampling outputs Wout = 40 walks with each walk at a length of lout = 10. The decay coefficients of BC and distance are fixed as Ç = 10, rate & = 0.01 for 15 epochs and train the CatBoost regressors with a grid search for their best parameters at the offline stage. For large graphs (i.e., DBLP and YouTube), we adjust the above parameters by |L| = 5, Win = 2, = 1.0. For BCDR-FC, the number of walks is reduced by a half for every graph. For BCDR-FQ, take the raw outputs of the distance predictor without searching
0.35. We train the distance predictor using two-layer perceptron with learning
26

---

Under review as a conference paper at ICLR 2023
Table 5: Parameter settings of evaluation on real-world graphs. Smaller graphs include Cora,
FaceBook, and GrQc. Larger Graphs include DBLP and YouTube.
Parameters
for Smaller Graphs
for Larger Graphs
d
16
16
80
Win
20
lin
40
40
Wont
40
40
lout
10
10
10
(x
0.35
0.35
epochs
15
15
first-order neighborhoods the graph (i.e., set r True). The boosting module is only utilized in BCDR and disabled BCDR-FQ and BCDR-FC (i.e. set X = Falsc). We summarized the critical parameter setting to reproduce results in Table 2 as follows.
A. EXTENDED COMPARISONS WITH GRL MODELS ON APPROXIMATION QUALITY
We present in Table the experimental results of comparisons to general GRL. models. Here, only the approximation quality (i.c., mAE and mRE) evaluated, and the metries are exerted directly on the representations without quantizing the outputs to integers or checking adjacency matrices. We see from Table that although general embeddings by GRL methods could preserve some local SP structures, our proposed method with explicit SP constraint possesses better approximation quality for the SP distance queries.
Table 6: Extended comparison to general GRL models approximation quality
Cora
Facebook
GrQe
Model
mAE
mRE
mAE
mRE
mAE
mRE
LLE (Roweis & Saul
2000
5.6265
0.8445
1.9921
0.6841
4.8849
0.7105
LE Roweis & Saul
2000
5.6393
0.8455
2.0312
0.6998
5.0046
0.7366
Ahmed
2013
5.6249
0.8440
1.8743
0.6383
4.8562
0.7125
DeepWalk (Perozzi et al.
2014
1.5183
0.2425
0.9323
0.3289
2.8002
0.4169
GraRep (Shaosheng et al.
2015
2.6206
0.3830
2.8702
1.0479
4.2445
0.6292
Node2Vee (Grover & Leskovee
2016
1.3072
0.2115
0,8541
0, 0,2993
1.5156
0.2278
NetMF Quu
2018
4.1736
0.6025
1.6982
0.6163
3,8799
0.5779
VERSE (Tsitsulmn
2018
2.8895
0.4049
1.1092
0.3729
3.3436
0.4689
I.PCA (Chanpurya et al.
2020)
2.2813
0.3337
2.1373
0.8611
2.4526
0.3475
BCDR (ours.)
0.9768
0.1605
0.4804
0.1770
1.0490
0.1684
A.11 FURTHER INVESTIGATION ON BCDR FRAMEWORK
A.11.1 ABLATION STUDY OF BCDR FRAMEWORK ON APPROXIMATION QUALITY
We discuss here the impact on approximation quality of different components in BCDR framework. In addition to those plausible post processing operations described in Algorithm D (i.e.. enable т, or not), we also explore other operations that influnces approximation quality when pre-processing graphs. The modifications to BCDR are stated as follows, and the corresponding results evaluated on Facebook and DBLP are shown in Table
checks on adjacency. The outputs of BCDR are accepted as predictions of SP distance without checking if there is any immediate edge between each node pair (i.e., set 7 True).
no global features. SP distances are solely predicted by the two-layer neural network, and the boosting module based global distances to landmarks is omitted (i.e., set x False).
27

---

Under review as a conference paper at ICLR 2023
local features. SP distances solely predicted by the boosting module, and the learn- ing process of the two-layer neural network on local features is omitted.
no BC. Node representations are learned without BC-based random walk. For any nodes, each transition in simulating walks considers its first-order neighbors equally, ignoring their BC values.
no DR. Node representations are learned without distance resampling. The resampling rule
(i.e. Equation 5) is replaced by a uniform sampling.
degree selection. In simulation of distance triplets and BC values, the landmarks lected in descending order of degree, instead of random selection.
We see from the table that the full approach of BCDR achieves the best performance on approxima- tion quality. also reveals that all of the components significantly improve the prediction results. Specifically, for the checks adjacency, it is notable that learning- based methods SP represen- tation show much difficulty in catching distance to first-order neighbors. Checking adjacency of input node pairs is necessary for accurate SP prediction. For global and local features, SP distance predicted from global features performs better than that from local features. It means leveraging global distances each landmark helps lot in locating a node the graph. Furthermore, BCDR combines both global and local features for prediction and shows superior performance compared either of them. For representing local features (i.e., BC and DR), we see that both BC-based random walk and distance resampling help to enhance the node representations with high-order SP structures, making easier to extract distances to remote nodes. For landmark selection, we find that random selection of landmarks is more necessary for BCDR than other existing strategies. This because we need to estimate BC values by performing BFS from these landmarks, and any as- sumption on landmark distribution will lead to unfair numerical estimation. If only landmarks with large degrees are selected, the BC value of nodes located in dense regions will be estimestimated, which impairs the efficiency of BC-based random walk.
Table 7: Ablation study of BCDR framework on approximation quality
Facebook
DBLP
Model
mAE
mRE
mAF
mRF
BCDR no checks on adjacency
0.0253
0.0180
0.5677
0.0907
BCDR- no global features
0.1138
0.0378
1,0070
0. 0.1484
BCDR no local features
0.0453
0.0171
0.5385
0.0855
BCDR- no BC
0.0210
0.0086
0.5437
0.0839
BCDR- no DR
0.0285
0.0142
0.5093
0.0808
BCDR- degree selection
0.3820
0.1139
1.1524
0.1611
BCDR full approach
0.0106
0.0044
0.4923
0.0798
A.11.2 FURTHER INVESTIGATION ON CRITICAL PARAMETER SETTING OF BCDR
Then, we further investigate the parameter settings of BCDR and discuss 9 critical parameters for their impacts on performance. Notably, although we describe rather detailed settings of parameters in Appendix [A.9 the proposed method BCDR is factually robust and effective, and its performance does not sensitively rely on any one of them. Here, we show the impacts of these parameters on related metries and how easily tune them in any unweighted graphs, both conceptually and prac- tically. The next discussion and evaluation of each parameter follow its order in Table 5
d: the dimension of node-level embeddings (i.c., Z). In our experiment, d is not fine- tuned parameter but fixed at certain value (i.e., d 16) among different models to fairly eval- uate their performance. This parameter could improve the performance size of embeddings could dump more valuable information about SP structures at the expense of higher storage cost and deficiency in query speed. To verify this, We test BCDR with different = (2, 4, 16, 64, 128, 256} on Facebook and GrQe to evaluate their performance under these met- rics.
accuracy since large
From the Table 8 and we see that the accuracy loss could be cut down by increasing d, but it will lead to significant deterioration in storage cost and query speed. As discuss low-dimensional
28

---

Under review as a conference paper at ICLR 2023
and accurate SP representation in this paper, the results also reveal that even at rather lower dimen- sion of embeddings (like d = 4), the distance relations on the graph could be well well-preserved.
Table 8: Impacts of on the performance of BCDR evaluated on FaceBook
16
64
128
256
Storage
0.1307 MB
0.1924 MB
1.210 MB
3.160 MB
5.944 MB
8.579 MB
mAE
0.0902
0.0150
0.0202
0.0499
0.0310
0.0130
mRE
0.0347
0.0075
0.0091
0.0212
0.0122
0,0064
Query Time
4,089 ns
4,664 ms
8,334
22,430
41,142 ns
81,188
Table 9: Impacts of d on the performance of BCDR evaluated on GrQe
16
64
128
256
Storage
0.2240 MB
0.3023 MB
0.7916 MB
2,750 MB
5.415 MB
10.86 MB
mAE
0.8719
0.8954
0.7089
0.6867
0.6746
0.677
mRE 0.1548
0.1555
0.1259
0. 0.1227
0.1201
0.1209
Query Time
2,421 ns
3,011 ns
6, 570 ns
20,837 ns
39, 479 ns
79,023 ns
L]: the number of landmarks for constructing distance triplet and estimating BC. This pa- rameter mainly affects accuracy and pre-processing time since involving more landmarks helps to alleviate harmful inductive bias on a certain part of the graph but suffers higher computing overhead. It is also observed in the previous works (Rizi al.) 2018) that for large graphs with strong central- ity on few nodes, the number of landmarks could be reduced without much loss of accuracy. We evaluate BCDR with group of landmarks (lZ {10, 20, 40, 80, 1603) Facebook and GrQe, to see their impacts on the two metrics.
Table 10: Impacts of |L| on the performance of BCDR evaluated on FaceBook
L Pre-processing Time
10
20
40
80
160
127.8
134.3
142.5
157.5
187.5
mAE mRE
0.0342
0.0297
0.0148
0.0193
0.0124
0.0134
0.0108
0.0063
0.0096
0.0062
Table 11: Impacts of LL on the performance of BCDR evaluated on GrQu
10
20
40
80
160
Pre- Pre-pracessing Time
47.47
52.95
64.35
83.75
123.7
mAE
0.9922
0.6837
0.7383
0.7112
0.7065
mRE
0.1591
0.1185
0.1266
0.1217
0.1231
The results in Table 10 and 11 show that the pre-processing time graphs increases linearly with [L] since performing BFS from the added landmarks needs extra traversal on the whole graph for O(N + .M) time. It is also interesting to that the number of landmarks large enough for the best performance diverges for dense and sparse graphs, i.e., it generally takes more than 40 landmarks for Facebook but only 20 landmarks necessary for GrQc. Specifically, for relatively dense graphs (i.c.. Facebook), each node shares weaker centrality due to the enriched links, which means we need observe more landmarks to cover more SPs on the graphs (according to the hub-labeling theory in (Cohen et al. 2003)). But for sparse graphs (i.e., GrQc), as long several nodes with strong centrality are well-observed, SP distance between most node pairs could be preserved, resulting in tolerance of reduced landmarks.
Win: lin: the number and length of sampled BC walks each node. These parameters affect the accuracy and pre- pr-processing time. When we simluate BC walks rooted at a certain node, a large win makes it sufficient to observe the local structure of each node (like BFS), while large
29

---

Under review as a conference paper at ICLR 2023
in allows wider exploration the graph to let the distance with remote nodes be seen (like DFS).
Like the previous evaluation, we test Win = (5, 10, 20, 30, 40) and in = {5, 10, 20, 40, 60, 80} to investigate their impacts, respectively.
Table 12: Impacts of Win the performance of BCDR evaluated on FaceBook
Win
Pre- processing Time
128,5 s
143.7 s
186.3 s
228.2
273.5 s
mAE mRE
0.0136
0.0454
0.0113
0.0188
0.0062
0.0061
0.0182
0.0056
0.0093
0.0027
Table 13: Impacts in on the performance of BCDR evaluated on FaceBook
Lin
5
10
20
40
60
80
Pre-processing Time 126.9
1
145.9
182.8
215.4
114.0
mAB mRE
0.0133
0.0145
0.0725
0.0081
0.0320
0.0370
0.0065
0.0067
0.0304
0.0037
0.0132
0.0184
Table 14: Impacts of win on the performance of BCDR evaluated on GrQe
Win Pre-pracessing Time 112.2 s
5
10
20
30
40
114.5
118.8 s
125.1 s
130.2
mAE
0.7227
0.6671
0.6581
0.6930
0.7115
mRE
0.1250
0.1195
0.1166
0.1245
0.1259
Table 15: Impacts of ln the performance of BCDR evaluated GrQq
Lip
5
40
60
80
Pre- pre-ppocessing Time
114,0 s
1
117.8 s
1
119.7
120,8
mAE
0.7460
0.6765
0.7074
0.6643
0.6895
0.6926
mRE
0.1280
0.1146
0.1217
0.1171
0. 1227
0. 0230
The experimental results from Table 12 to 15 show the accuracy of BCDR is not sensitive to these
parameters, owing much the efficiency of BC walk and well-preserved distance relations by DR. Intuitively, we recommend setting lin proportional to the diameter of the graph, which makes the whole graph observed from any nodes. Also, Win could be reduced when the connectivity on the graph is relatively weak since the local structures quite simple to explore.
Wout; lout: the number and length of resampled paths (by DR) each node. These param- eters control the shape of output node sequences to subsequently optimize Z under skip-gram procedure. To avoid much loss of information and preserve the correlation in BC walks, we intend to keep the scale of outputs similar to that of inputs, i.e., Wouthous = Mwwmlin) To accelerate the optimization process, we could further shorten lout and keep this scale (by correspondingly expanding Wout). Note that this reshaping operation does not apparently change the locality nor impair the performance since DR resamples nodes from high-order neighborhoods with respect to their distance from the root, thus resulting in well-defined convergence, as shown in Prop. 1. In the experiment, we the scale output node sequences as half of the scale of BC walks (i.e., Wouthout Winhin/ /2 400), and test different combinations of their settings as (Wonts 4m) {(200, 2), (100, 4), (50, 8), (40, 10), (25, 16), (16, 25), (10, 40), (8, 50), (4, 100), (2, 200)).
The results in Table 16 and 17 reveal that the pre-processing time dramatically increases along with lout- This is because we utilize the whole sequence to optimize ro-occurrence likelihood between the root and nodes in this sequence, which requires joint training with large number of node embeddings proportional to Lout- It is also shown that the accuracy does not significantly fluctuate pre-procssiing time, indicating relatively small lout will help reduce the off-line time cost.
30

---

Under review as a conference paper at ICLR 2023
Table 16: Impacts of (Wouts loux) on the performance of BCDR evaluated on FaceBook
(Wout: loue)
(200,2)
(100,4)
(50,8)
(40,10)
(25,16)
(16,25)
(10,40)
(8,50)
(4,100)
(2,200)
Pre-processing Time
176.3
154.1 s
148.6
1
s
170.5
2
236.8
1,521 501.0's
mAE
0.0237
0.0217
0.0249
0.0258
0.0303
0.0128
0.0127
0.0360
0.0083
0.0237
mRE
0.0097
0,0093
0.0107
0.0T08
0.0136
0.0059
0.0043
0.0145
0.0041
0,0098
Table 17: Impacts of (Woats lout) on the performance of BCDR evaluated on GrQc
(Wout: loue)
(200,2)
(100,4)
(50,8)
(40,10)
(25,16)
(16,25)
(10,40)
(8,50)
(4,100)
(2,200)
Pre-processing Time
73.00
7
77.78
80.03
88.09 s
106.2
151.1s
191.4
512.2
1,709
mAE
0.7829
0.7107
0.6811
0.6780
0.7170
0.7129
0.6970
0.6751
0.7340
0.6986
mRE
0.1389
0.1225
0.1209
0.1225
0.1274
0.1204
0.1240
0.1212
0.1295
0.1263
S, az the decay coefficient of BC values and distance weights. These parameters mainly affect the performance accuracy by dominating the intrinsic behaviors of BC walk and DR, respec- tively. Thereinto, Ç determines how frequently a node could he enrolled in the current BC walk, which helps to diverge the direction of different walks from one root. Likewise, a determines how frequently a node with more hops from the root could be selected into resampled paths, which helps to distinguish neighbors of different orders. Like the previous evaluation, we test BCDR with Ç = (-1,,, 0, 1,2, 4, 10, 20} and f0.1, 0.3, 0.4, 0.5, 0.9, 0.98} to show their impacts.
Table 18: Impacts of ( and a on the performance of BCDR evaluated on FaceBook
0
2
10
20
mAE
0.0522
0.0146
0.0061
0.0243
0.0137
0.0143
0.0131
mRE
0.0186
0,0069
0.0026
0.0099
0.0053
0.0056
0.0052
0.1
0.2
0.3
0.4
0.5
0.9
0.98
mAE
0.0104
0.0418
0.0506
0.0096
0.0252
0.0197
0.0341
mRE
0.0046
0,0204
0.0178
0.0046
0,0125
0.0096
0.0159
Table 19: Impacts of ( and a on the performance of BCDR evaluated on GrQq
0
2
4
10
20
MAE 0.6419
0.6865
0.6844
0.6717
0.7219
0.6734
0.6879
mRE
0.1146
0.1234
0.1209
0.1214
0.1235
0.1175
0. 1209
O
0.1
0.2
0.3
0.4
0.5
0.9
0.98
MAE
0.7216
0.6780
0.7036
0.7441
0.7006
0.7281
0.7258
mRF
0.1237
0.1202
0.1239
0.1295
0.1234
0.1267
0.1290
From the Table 18 and 19 we see the accuracy of BCDR is not sensitive to these parameters, but a fine-tuning process could improve the performance on specific graphs
For choices of Ç. it depends on the fluctuation of centrality on neighbor nodes. Specifically, for relatively dense graphs (like Facebook) with flattened centrality on neighbors, a larger ( resists the frequency decaying of most preferred walk paths, leading to efficient exploration for high-order distance relations. On the contrary, a quick BC decaying (smaller () makes the priority of neighbor nodes indistinguishable dragging down the performance like a naive random walk, since many neighbors possess similar centrality on such graphs.
For choices of or as discussed in Remark 2, it reflects trade-off between quality (i.e., preserves accurate distance relations) and quantity (i.c., embeds more relations with a widened range of nodes). In detail, a smaller a slows down the process Das + 0, allowing relations between node pairs with larger distance Das to converge. i.c., Z, + Das > 0, but it causes nodes possessing similar distance from the root indistinguishable due to the noise in the embedding space, and vice versa.
31

---

Under review as a conference paper at ICLR 2023
Number of epochs. The number of epochs determines if it is sufficient to learn NN distance predictor. To produce the results of Table 2 in (Rizi et al. 2018). Here, we evaluate its impact on accuracy loss and pre-procsssing time.
we just leverage the empirical value as discussed
Table 20: Impacts of the number of epochs the performance of BCDR evaluated FaceBook
Num. of epochs
10
40
Pre- processing Time
121.2 s
125.3
130.7 s
139.7 s
150.1 s
160.0
194.7
mAE
0.0174
0.0136
0.0167
0.0121
0.0107
0.0176
0.0259
mRE
0.0087
0.0067
0.0083
0.0057
0.0048
0.0070
0.0T(M
Table 21: Impacts of the number of epochs on the performance of BCDR evaluated on GrQc
Num. of epochs
2
5
10
15
20
40
Pre-processing Time
44.67
47.92
54.69
68.03
79.85
92.09
141.5
mAE
0.6888
0.6913
0.7071
0.6786
0.6803
0.6884
0.7047
mRE
0.1225
0.1257
0.1263
0.1158
0.1197
0.1194
0.1225
The results in Table 20 and 21 show that learning with 15 epochs is generally appropriate for many real-world graphs. It also reflects that training the distance predictor with more iterations may cause an over-fitting problem since the training data (distance triplets) extracted from few landmarks, which induces harmful inductive bias on a certain part of the graph.
A.12 EXTENDED RESULTS ON EXPLORATION RANGE OF DISTANCE
The extended results on all synthetic graphs are shown in Figure 7 We analyze the significance of utilizing BC-RW for wider range of exploration different structures follows.
For CGs and TCGs, BC-RW tends to choose the exit nodes of each circle since they provide large BC gain by splitting all SPs between inner nodes and outer nodes regarding the current circle.
For TGs, transitions on every triangle clique tend to move forward along the trunk road since the number of nodes beyond the current clique is often larger than that of inner nodes, contributing to more SPs.
For TRGs, each transition from the root to leaves appears to be biased since subtrees with more descendants contribute to more SPs and possess larger BC values.
For SGs, there are many shorteuts that link some nodes on the trunk road, and the BC values shortcut nodes and other nodes are usually on par. BC-RW possesses a slight advantage by keeping relatively good balance these nodes.
For NGs, most of the nodes are passed through by SPs with similar probabilities, and BC- RW is hard tell the proper direction for deeper exploration like other walk strategies.
A.13 EXTENDED RESULTS ON PRESERVATION OF DISTANCE RELATIONS
The extended results of distance preservation are shown in FigureRand These figures confirm that our model is much more satisfactory in preserving distance relation than existing methods except for TGs. For most graphs, BC walk paths provide sufficient observation on each node by locating many remote nodes with sequence of center nodes on graph, and thus the resampling process based on such observation could preserve distance relations in the exploration range. For TGs, however, there are many final nodes (i.e., leaves) possessing trivial significance BC walks which are insufficiently observed for calibrating their distance relations well.
32

---

Under review as a conference paper at ICLR 2023
Lergs
Figure 7: Exploration range distance when taking different walk strategies tested on six synthetic graphs. Row from top to bottom: different synthetic graphs including CG, TG, TCG. TRG, SG, and NG. respectively. Column from left to right: different walk strategies including NRW, SORW, RS, DFS-RW, BC-RW (ours.), respectively.
33

---

Under review as a conference paper at ICLR 2023
Diliro
Figure 8: Measured distance from the embedding space and the original graph. Row from top to bottom: different graphs including CG, TG, TCG, TRG, SG, and NG, respectively. Column from left to right: embeddings learned by different walk strategies.ie., NRW, SORW, RS, DFS-RW, and BC-RW (ours.), respectively. For ours, walk paths are further simulated by distance resampling.
34

---

Under review as a conference paper at ICLR 2023
Distance preservation among node triplets the embedding spaces. Row from top to bottom: different graphs including CG, TG, TCG, TRG, SG, and NG, respectively. Column from left to right: embeddings learned by different walk strategies.ie.. NRW, SORW, RS, DFS-RW, and BC-RW (ours.), respectively. For ours, walk paths are further simulated by distance resampling.
Figure 9:
35


Reviews:
[{"review_id": "xBOeEIPG2Zp", "reviewer": "Reviewer_MJqQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "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).", "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.", "strength_and_weaknesses": "Strengths:\n- The paper addresses an intellectually challenging and important problem\n- The proposed method is novel and is supported by theoretical arguments and empirical evaluation\n\nWeaknesses:\n- It is not clear if the implementation will be made public which could impact the reproducibility of the results\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "PAKDg_Y3dm", "reviewer": "Reviewer_WYyv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "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.\n", "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.\n", "strength_and_weaknesses": "Strengths:\n\n1) 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).\n\n2) 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.\n\n3) 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.\n\nWeaknesses (and questions):\n\n1) Very significant presentational issues exist in the paper (see below). \n\n2) Close variants of SP representation learning are not considered. Can the method be applied to unweighted graphs?\n\n3) 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?\n", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ENhYHuSjsn", "reviewer": "Reviewer_87wC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "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.", "summary_of_the_review": "I recommend to reject the paper at the current point in time.", "strength_and_weaknesses": "Strengths:\n- the empirical results look promising\n\nWeaknesses\n- it is unclear how the training paths ('random sp walk') are constructed from the random walks\n- it remains unclear how the present work relates to path2vec both conceptually and practically\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2Vfoy2sRaJ0", "reviewer": "Reviewer_VC9e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "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.", "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.  \n\nWhereas 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.  \n\nThe BCDR relies on the setting of multiple hyperparameters but lacks careful investigation and justification of the settings of these parameters.", "strength_and_weaknesses": "Strengths: \nThe proposed BCDR provides good performance that performs well contrasted alternative procedures quantifying SP distances. \nThe approach utilizing betweenness centrality is sound and the mathematical derivations and procedure proposed carefully designed. \nThe embedding procedure used to quantify Z is efficient and performs well evaluating all shortest paths approximately\n\nWeaknesses:\nThe 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. \n\nThe 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? \n", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject