Why the Metric Backbone Preserves Community Structure
Authors: Maximilien Dreveton
Charbel Chucri
Matthias Grossglauser
Patrick Thiran
Venue: NeurIPS 2024 poster (2024)
Keywords: community detection
graph sparsification
stochastic block model
Primary area: probabilistic_methods
TL;DR: The metric backbone of a weighted graph is the union of all-pairs shortest path; despite its tendency to delete intra-community edges, the metric backbone preserves the community structure and is an efficient graph sparsifier.

Abstract: The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is obtained by removing all edges $(u,v)$ that are not the shortest path between $u$ and $v$. In networks with well-separated communities, the metric backbone tends to preserve many inter-community edges, because these edges serve as bridges connecting two communities, but tends to delete many intra-community edges because the communities are dense. This suggests that the metric backbone would dilute or destroy the community structure of the network. However, this is not borne out by prior empirical work, which instead showed that the metric backbone of real networks preserves the community structure of the original network well. In this work, we analyze the metric backbone of a broad class of weighted random graphs with communities, and we formally prove the robustness of the community structure with respect to the deletion of all the edges that are not in the metric backbone. An empirical comparison of several graph sparsification techniques confirms our theoretical finding and shows that the metric backbone is an efficient sparsifier in the presence of communities.

Why the Metric Backbone Preserves Community Structure
Maximilien Dreveton
Charbel Chucri
EPFL
EPFL
maximilien, mexxiiileen..rreeetoneeppp..
charbel. www.bee.ccccri@p11....
Matthias Grossglauser
Patrick Thiran EPFL patrick, thinankethirrr ch
EPFL
matthias, berthias.grossgglene hro.iias..goosggaussrrpppp......
Abstract
The metric backbone of a weighted graph the union all-pairs shortest paths. It is obtained by removing all edges (u,v) that
the shortest path between w and v. In networks with well-separated communities, the metric backbone tends preserve many inter-community edges, because these edges serve as bridges connecting two communities, but tends to delete many intra-community edges because the communities are dense. This suggests that the metric backbone would dilute or destroy the community structure of the network. However, this is not borne out by prior empirical work, which instead showed that the metric backbone of real networks preserves the community structure of the original network well. In this work, we analyze the metric backbone of broad class of weighted random graphs with communities, and we formally prove the robustness of the community structure with respect to the deletion of all the edges that are not in the metric backbone. An empirical comparison of several graph sparsification techniques confirms our theoretical finding and shows that the metric backbone is an efficient sparsifier in the presence of communities.
Introduction
Graph clustering partitions the vertex set of graph into non-overlapping groups, so that the vertices of each group share some typical pattern or property. For example, each group might be composed of vertices that interact closely with each other. Graph clustering is one of the main tasks in the statistical analysis of networks 30).
In many scenarios, the observed pairwise interactions are weighted. In proximity graph, these weights measure the degree of similarity between edge endpoints (e.g.. frequency of interaction in social network), whereas in a distance graph, they measure dissimilarity instead (for example, the road network or travel times a flight network). To avoid confusion, we refer to the weights in a distance graph as costs, that the cost of a path will be naturally defined as sum of the edge costs on this path [
length of segments
Distance graphs obtained from real-world data typically violate the triangle incquality. More precisely, the shortest distance between two vertices in the graph not always equal the cost of the direct edge, but rather equal to the cost of an indirect path via other vertices. For example, the least expensive
'Tii additive property does not hold for similarity weights, but proximity graph can be transformed into distance graph by applying an isomorphic non-line non-linear transformation on the weights [6]
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

flight between two cities is often a flight including one or more layovers. An edge whose endpoints are connected by an indirect shorter path is called semi- moni-metric; otherwise, it is called metric.
We obtain the metric backbone of a distance graph by removing all its semi-metric edges. It has been experimentally observed that the metric backbone retains only small fraction of the original edges, typically between 10% and 30% in social networks (35). Properties of the original graph that depend only on the shortest paths (such as connectivity, diameter, and betweenness centrality) are preserved by its metric backbone. Moreover, experiments on contact networks indicate that other properties (such as spreading processes and community structures) are also empirically well approximated by computing them on the metric backbone, rather than on the original graph [8].
The preservation of these properties by the backbone highlights well-knowe empirical feature of complex networks: redundancy. This is the basis for graph sparsification: the task of building a sparser graph from a given graph so that important structural properties are approximately preserved while reducing storage and computational costs. Many existing network sparsifiers identify the statistically significant edges of a graph by comparing them to a null-model [34 43). These methods typically require hyperparameters and can leave some vertices isolated (by removing all edges from a given vertex). Spectral sparsification aims at preserving the spectral structure of graph but also relies on a hyperparameter, and the edges in the sparsified graph might have different weights than in the original graph [37]. In contrast, the metric backbone parameter- and automatically preserves all properties linked to the shortest path structure. Moreover, all- pairs shortest paths can be efficiently computed 33.. This makes the metric backbone an appealing mechanism for sparsification.
Among all the properties empirically shown to be well preserved by the metric backbone, the community structure is perhaps the most surprising. Indeed, if network contains dense communities that are only loosely connected by a small number of inter-community edges, then all shortest paths between vertices in different communities must go through one of these edges. This suggests that these "bridge" edges are less likely to be semi-metric than intra-community edges, where the higher density provides shorter alternative paths 2 This in turn implies that metric sparsífication should thin out cotra-comuuntty edges more than inter- nnterccommunity edges, thereby diluting the community structure. The central contribution of this paper is show that this intuition is wrong.
To do so, we formally characterize the metric backhone of a weighted stochastic block model (wSBM). We assume that the vertices separated into & blocks (also referred to clusters communities). An edge between two vertices belonging to blocks a and d is present with probability Pas and is independent of the presence or absence of other edges. This edge, if present, has weight sampled from a distribution with edf Fab. and this weight represents the cost of traveling through this edge. We denote by mb the probability that an edge between vertex in block a and a vertex in block b is present in the backbone 3l Under loose assumptions
the costs distributions Fab and the probabilities Pab. we show that pab /yab = (1 + o( Daatt//eee Ped for every a, b, c, d E [k]. This shows that the metrie backbone thins the edge set approximately uniformly and, therefore, preserves the community structure of the original graph. Moreover, we also prove that a spectral algorithm recovers almost exactly the communities.
We also conduct numerical experiments with several graph clustering algorithms and datasets to back up these theoretical results. We show that all clustering algorithms achieve similar accuracy on the metric backbone as on the original network. These simulations, performed on different types of networks and with different clustering algorithms, generalize the experiments of [8). which are restricted to contact networks and the Louvain algorithm. Another type of graph we consider are graphs constructed from data points in Euclidean space, typically by kernel similarity measure between g-nearest neighbors (g-NN) 15). This is an important technique for graph construction, with applications in non-linear embedding and clustering. Although q controls the sparsity of this embedding graph, this procedure is not guaranteed to produce only metric edges, and varying often impacts the clustering performance. By investigating the metric backbone of g-NN graphs, we notice that it makes clustering results more robust against the value of q. Consequently, leveraging graph sparsification alongside N- facilitates graph construction.
In fact, this intuitive observation at the core of one of the very first community detection algorithms 17 'The events (f( v) is metric) and 1((w, æ) is metric} are in general not independent, but the probability that (u, v) is metric depends only the cluster assignment of vertices and
2

---

The paper is structured as follows. We introduce the main definitions and theoretical results on the metric backbone of wSBMs in Section 2 We discuss these results in Section 3 and compare them with the existing literature. Sections 4 and 5 are devoted to numerical experiments and applications.
Finally, we conclude in Section
Code availability We provide the code used for the experiments: https://github. com/ Charbel-
Notations The notation n, denotes the vector of size n whose entries are all equal to one. For any vector
R and any matrix B R=xm we denote by Amin minla]a]] To and Bmin = ming,6 Bas. and similarly for T maxx and Bmax- Given two matrices A and B of the same size, we denote by A @ B the entry-wise matrix product (i.e., their Hadamard product). A" the transpose of matrix A. For vector we denote diag(z) the diagonal matrix whose diagonal element (a, a) is a..
The indicator of an event A is denoted 1 [[A). Binomial and exponential random variables are denoted by Bin(n. p) and (A), respectively. The uniform distribution over an interval [a, bj is denoted Unif(a, b). Finally, given cumulative distribution function F, we write X ~ F for random variable X sampled from F. iee., P(X S x) = F(x), and we denote by f the pdf of this distribution. We write whp (with high probability) for events with probability tending to 1 as n -> 0o.
2 The Metric Backbone of Weighted Stochastic Block Models
2.1 Definitions and Main Notations
= [n|] is the set of vertices, E V is the set of undirected edges, and c: E + R., is the cost function.The The cost of a path (u,,-.. Up) naturally defined as _ c(uy 19+1), and shortest path between u and v a path of minimal cost starting from vertex u and finishing at vertex u. We define the metric backbone the union of all shortest paths of G.
Let G = (V, E. c) be an undirected weighted graph, where V
Definition 1.
The metric backbone of weighted graph G GV, E, where e represents the edge cost is the subgraph Gmb (V, E't cmb) of G. where Emm C E is such that E Emmh if and only if belongs to shortest path from two vertices in G, and cbbb; Fum - 14; + c(e) is the restriction of to gub
We investigate the structure of the metric backbone of weighted random graphs with community structure. We generate these graphs as follows. Each vertex u E [n] is randomly assigned to the cluster a E [k] with probability Ta- We denote by 2n E [k] the cluster of vertex Conditioned on Zu and Z,. an edge (u, v) is present with probability Pa..., independently of the presence or absence of other edges. If an edge (u.r) is present, it is assigned cost c(u. v). The cost c(u, v) sampled from Fz... where F = (Fat) denotes collection of cumulative distribution functions such that Fab Fba- This defines the weighted stochastic block model, and we denote (z, G) ~ wSBM(n, T. p. F') with G = ([n], E, c)) 2 E [k]" and
(2)
II Z=..
u=1
((E
II 1SwcuSh
Mllu)eE (1 Prnew Pzoze
) [(l,,0]EE)
P E,2)
II {u,o)EE
P (c(u, v) Zus 20),
and c(u, v) 2. = 2. = is sampled from Fat-
The wSBM is direct extension of the standard weighte)) SBM into the weighted setting. SBM is the predominant benchmark for studying community detection and establishing theoretical guarantees of recovery by clustering algorithms [1]. Despite its shortcomings, such low clustering coefficient, the SBM is analytically tractable and is a useful model for inference purposes (32
Throughout this paper, will make the following assumptions.
3

---

Assumption 1 (Asymptotic scaling). The edge probabilities Pas between blocks and b can depend on n, such that Pab. Ba with pn w(n log n) and aa is independent n. Furthermore, the number of communities k, the matrix B. the probabilities Ta and the edf Fab are all fixed (independent of n.). We also assume Tmin > and Bmin > O.
To rule out some issues, such as edges with a zero cost we also assume that the probability distributions of the costs have no mass at O. More precisely, we require that the cumulative distribution functions Fab verify Fas = and (0) Xub > O, where F" denotes the derivative of F (i.e., the pdf). The first condition ensures that the distribution has support R and mass at 0, and the second ensures that, around a neighborhood of 0, Fab behaves as the exponential distribution Exp(Xab) (or as the uniform distribution Uni A-="))
Assumption 2 (Condition on the cost distributions). The costs are sampled from continuous distribu- tions, and there exists A (Aab)a.b with Aab > 0 such that (0) 0 and Pa (0) Aab-
We define the following matrix
T= o B] diag(r),
(2.1)
where B and A are defined in Assumptions D and 2 minimum and maximum entries of the vector T-
Finally, we denote by Tmin and Tiax the
Remark 1. Assume that A = A1+1k with À > 0. We notice that Ta = AE Bab. Denote by , d the vector whose a-entry da is the expected degree of vertex in community a. We have d, n E. TaPab. Then Tmin Admin (np,.) and Tmax Admax where dmin and dmax are the minimum and maximum entries of d.
d (d1, ...
2.2 Cost of Shortest Paths in wSBMs
Given path (u1,... upp), recall that its cost is E c(uy: My+1), and the hop count is the number of edges composing the path (that is, the hop count of (ui.-.. Up) is p-p-11 1).
For two vertices u, E V. we denote by C(u, e) the cost of the shortest path from to v The following proposition provides asymptotics for the cost of shortest paths in wSBMs.
Proposition 1. Let (z, G) wSBM(n, T. F). Suppose that Assumptions 7 and 2 hold and let Tain and maax be defined following Equation 2.1). Then, for two vertices and v chosen uniformly at random in blocks and b, respectively. We have whp
(Tmaax) S
nPn C(u, v) S (Tmiin) log n
To prove Proposition [ in the first stage, we simplify the problem by assuming exponentially distributed weights. We then analyze two first passage percolation (FPP) processes, originating from vertices and v, respectively. Using the memoryless property of the exponential distribution, analyze two first passage percolation (FPP) processes, originating from vertex and v, respectively. Each FPP explores the nearest neighbors of its starting vertex until it reaches q neighbors. As long as o (Vn), the two FPP processes remain disjoint (with high probability). Thus, the cost C(u, v) is lower-bounded by the sum of (i) the cost of the shortest path from
its g-nearest neighbor and of (ii) the cost of the shortest path from v to its g-nearest neighbor. On the contrary, when w( (/)). the two FPPs intersect, revealing a path from u to v. and the cost of this path upper-bounds the cost Clu, v) of the shortest path from u to v. In the second stage, we extend the result to general weight distributions by noticing that the edges belonging the shortest paths have very small costs. Moreover, Assumption 2 yields that the weight distributions behave as an exponential distribution in a neighborhood of We can thus adapt the coupling argument of (23 to show that the edge weights distributions do not need to be exponential, as long as Assumption Proposition provided in Section A
2 is verified. The proof of
4 AAn edge (u, v) E E such that c(u, v) = yields the possibility of teleportation from vertex u to vertex u.
'ee notice that, given wSBM, whp there only one shortest path.

---

2.3 Metric Backbone of wSBMs
Let (2, (n, n, p, F) and denote by Gmub the metric backbone of G. Choose two vertices and v uniformly at random, and notice that the probability that the edge (u, v) is present in Gumb depends only 2u and &e. and not on zw for between a vertex in community a and a vertex in community appears in the metric backbone, i.e.,
{u, v). Denote by pi the probability that an edge
Pab
P ((u,))
v)
Gub||
Zu 0. Ze b)
The following theorem shows that the ratio
Pat. scales θ log
Pao
rpp.
Theorem 1. Let (z, G) ~ wSBM(n, J, F) and suppose that Assumptions) / and hold. Let Tmin and max be defined after Equation (2.1. Then
(1 (1+ ((1)) Tmax
Aab
7Pn
mub
I (1+
Aab
log Pob
Tiii
We prove T'eoorem in Appendix [B.1] Theorem I shows that the metric backbone maintains the same proportion of intra- and inter-community edges in the original graph. We illustrate the theorem with two important examples.
Example Consider weighted version of the planted partition model, where for all a, [k] we have n. = 1 /k and
Po if b go otherwise,
Bab
where Po and qo are constant. Assume that A Algl Tmin Tmax Ak-1 (po + (k 1)4o), and Theorem states that
T with A > 0. Using Remark
I we have
kpo logn
kgo
log
p mb
(1 (1+) Po + (l: 1)40 n
and
q gmh
(1 (1+
Po + (k: 1)go n
In particular,
gmb
(1 (1)) Ra. go
quab
Example 2. Consider stochastic block model with edge probabilities Pab Babpn such that the
vertices different communities have the same expected degree If A = Al 12. then
Bas log
mb Pab
(1 ((1)
d
2.4 Recovering Communities from the Metric Backbone
In this section, we prove that a spectral algorithm on the (weighted) adjacency matrix of the metric backbone of wSBM asymptotically recovers the clusters whp. Given an estimate å [4]" of the clusters 2 E [k]]", we define the loss as
loss 2, 8) =
inf Ham (z, (2,000) 2), oESym(k)
where Ham denotes the Hamming distance and Sym(k) is the set of all permutations of [k).
Algorithm 1: Spectral Clustering on the weighted adjacency matrix of the metric backbone
Input: Graph G. number of clusters &
Output: Predicted community memberships è E [k]*
Denote Wmmb e R xx the weighted adjacency matrix the metric backbone Gmb of be an cigen-decomposition of Wmb, with eigenvalues ordered in decreasing absolute value (lo) 2
2 Let W/mb = ΣT1 ay 'I'
(a,) ) and eigenvectors " Un Rd Denote U [u1, ux] Ba and Σ diag(or, (11 ,ak)
Let 2 E [ be (1 + -ppproxxima solution of i-mma performed the of U B
The following theorem states that, as long as the matrix T defined in 2.1 is invertible, the loss of spectral clustering applied on the metric backbone asymptotically vanishes whp.
5

---

Theorem 2. Let (2, ~ wSBM(n, T,P, F) and suppose that Assumptions 7 and 2 hold. Let μa be the minimal absolute eigenvalue of the matrix T defined in (2.I). Moreover, assume that Tmax Tmin and μ. + O. Then, the output of Algorithm 7 7n G verifies whp
loss(2, 2, 2) = o 12² logn
We prove Theorem 2 in Appendix B.2 We saw in Example I and 2 that the condition Tmax mmin
verified in several important settings. The additional assumption fr = 0 (equivalent to T being invertible) also often holds: in the planted partition model of Example [ T is invertible if po o qo-
3 Comparison with Previous Work
The metric backbone has been introduced under different names, such as the essential subgraph [29]. the transport overlay network [41) or simply the union of shortest path trees [39] In this section, we discuss our contribution with respect to closely related earlier works.
3.1 Computing the Metric Backbone
Computing the metric backbone requires solving the All Pairs Shortest Path (APSP) problem, classic and fundamental problem in computer science. Simply running Dijkstra's 's algorithm on each vertex [E] is the number of edges in the original graph 14, whereas [29 proposed an algorithm running in O(nm' + n² log n) worst-case time, where m' the number of edges the metric backbone. APSP has also been studied in weighted random graphs in which the weights are independent and identically distributed [6] [6].
of the graph solves the APSP in O n² log n.) worst-case time, where
In particular, the APSP can be solved in Onn²) time with high probability on complete weighted graphs whose weights are drawn independently and uniformly at random from [0, 1 333.
However, practical implementations of APSP achieve faster results. For example, in [24]. an empirical observation regarding the low hop count of shortest paths is leveraged to compute the metric backbone efficiently. Although exact time complexity is not provided, the implementation scales well for massive graphs, such as a Facebook graph with 190 million nodes and 49.9 billion edges, and the empirical running time appears be linear with the number of edges [24] Table 1 and Figure 5]. Additionally, our simulations reveal that some popular clustering algorithms such as spectral and subspace clustering have higher running times than computing the metric backbone.
3.2 First-Passage Percolation in Random Graphs
To study the metric backbone theoretically, we need to understand the structure of the shortest path between vertices in random graph. This classical and fundamental topic of probability theory is known as first-passage percolation (FPP) 19]. The paper (23) originally studied the weights and hop counts of shortest paths the complete graph with iid weights. This was later generalized to Erdös-Rényí graphs and configuration models (see, for example, (28 [2] and references therein).
Closer to our setting, (55 studied the FPP on inhomogeneous, random graphs. Indeed, SBMs are a particular case of inhomogeneous random graphs, for which the set of vertex types is discrete (we refer to [7] for general statements on inhomogeneous random graphs). Assuming that the edge weights are independent and EExp(A)-distrbbute) (25) established central limit theorem of the weight and hop count of the shortest path between two vertices chosen uniformly at random among all vertices. Using the notation of Section 2 this result implies that mps. C(u, v) converges probability to 7 where 7 is the Perron- Farron-Frobenuus eigenvalue of XB diag(T).
Ing n.
The novelty of our work is two-fold. First, we allow diffferent cost distributions for each pair of communities, whereas all previous works in FPP on random graphs assume that the costs are sampled from a single distribution. Furthermore, we examine the cost of path between two vertices, u and v, chosen unifrrml at random among vertices in block a and in block b, respectively. This differs from previous work (and, particular, (25) in which vertices u and v are selected uniformly at random among all vertices. As result, even for single cost distribution. Proposition I cannot be obtained directly from 25 Theorem 1. 1.2]. This difference is key, as this proposition is required to establish Theorem[]

---

The closest result to Theorem apppearing in the literature is [39 Corollary I]; it establishes a formula for the probability Pue that an edge between two vertices u and exists the metric backbone of random graph whose edge costs are rid. This previous work does not focus on community structure, so the costs are sampled from a single distribution. More importantly, the expression of pub given by 33 Theorem 2 and Corollary 1] is mainly of theoretical interest (and we use it in the proof of Theorem Indeed, understanding the asymptotic behavior of puv requires a complete analysis of the cost (u, v) of the shortest path between and [39] propose such analysis only in one simple scenario (namely, a complete graph with exponentially distributed costs).
Experimental Results
In this section, test whether the metric backbone preserves graph community structure in various real networks for which a ground truth community structure known (see Table in Appendix C.I for overview).
As in many weighted networks, such as social networks, the edge weights represent a measure (e.g., frequency) of interaction between two entities over time, need preprocess these proximity graphs into distance graphs. More precisely, given the original (weighted or unweighted) graph G' == (V, E, s), where the weights measure the similarities between pairs of vertices, we define the proximity p(u, v) of vertices u and v as the weighted Jaccard similarity between the neighborhoods of u and u, Le..
p(u, v) EmeNat() min(s(u, w), s w)}
EmENa(()UNN(()) max w) s(v, w)}
where Nei(u) fw E V: (u.w) ( E} denotes the neighborhood of u, i.e., the vertices connected to u by an edge. If G is unweighted (s(e) = for e E), we simply recover the Jaceard index (Nei(w) Nei(o)UNNi(o]] We note that other choices for normalization could have been made, such as the Adamic-Adar index (2). We refer to 110 for an in-depth discussion of similarity and distance indices.
Once the proximity graph G (V, E.p) has been computed, we construct the distance graph D = (V,E,e where c: E + R4 is such that
E c(c)
1.
p(e)
This is the simplest and most commonly used method for converting a similarity to distance [36].
We then compute the set Emb of metric edges of the distance graph D, and let Gmbb (V, Fmm mb) where yiub; Emb [0, 1]; e p(e) is the restriction of p to Emb,
We will also consider the two following sparsifications (with the corresponding restrictions of e to the sparsified edge sets) to compare the resulting community structure:
the threshold graph G = -V, E", p²), where an edge e e E is kept in E iff p(e) 2 0;
the graph T (V, E p obtained by spectral sparsification on G. We use the Spielman-
Srivastava sparsification
implemented in the PyGSP package [13
For both threshold and spectral sparsification, we tune the hyperparameters so that the number of edges kept is the same as in the metric backbone: |b=b|] = |E = |E* We provide in Table 3 (in
Appendix) some statistics on the percentage of edges remaining in the sparsified graphs.
For each proximity graph G' and its three sparsifications Gmb GO and G we run graph clustering algorithm obtain the respective predicted clusters gmb"", 20 and gas, We show, Figure | the adjusted Rand inde (ARI) obtained between the ground truth communities and the predicted clusters for three widely used graph clustering algorithms: Bayesian algorithm [31. Leiden algorithm [3 and spectral clustering [4). We use the graph-tool implementation for the Bayesian algorithm, with an exponential prior for the weight distributions. The Leiden algorithm implemented at
'The Rand index (RI) measures similarity between two clusterings based on pair counting. This index is "adjusted for chance" because a random clustering could lead to a large RI. The ARI is modification of the RI such that two random clusterings (resp.. identical clusterings) give ARI of 0 (resp.. of 1) (22.
7

---

https://gi ghubb..............g com/ htm//ttraaggeidenagg For spectral clustering, we assume that the algorithm knows the correct number of clusters in advance, and we use the implementation from scikit-learn
Or gna Grapn
na Grapn
no Grapn
1.4
Spacra Sporsiirr
Scors
Spacisi Scars
20c-
2.66
6.6
0.4
0.4
0.4
Sohoo
5choo
Dacaod.
Da.and
Dv.aod
(a) Bayesian MCMC
(b) Leiden
(c) Spectral Clustering
Figure 1: Effect of sparsification the performance of clustering algorithms on various data sets. We observe that the metric backbone and the spectral sparsification retain equally well the community structure across all data sets and for all clustering algorithms tested. Thresholding often yields several disconnected components of small sizes, impacting the performance of clustering algorithms on G
We highlight the difference between the metric backhone and the threshold subgraph of the Primary school data set in Figure 2 We observe, in Figure 22 that the edges in red (which are present in the backbone but not in the threshold graph) are mostly inter-community edges. On the contrary, in Figure 2b, the blue edges (which are present in the threshold graph but not in the backbone) are mostly intra-community edges. Despite this difference, the metric backbone retains the information about the community structure, as shown in Figure [|
(a) Metric Backbone
(b) Threshold Subgraph
Figure 2: Graphs obtained from Primary school data set, after taking the metric backbone (Figure 2ab and after thresholding (Figure 2 are drawn using the same layout. Vertex colors represent the true clusters. Edges present in the metric backbone but not in the threshold graph are highlighted in red. Edges present the threshold graph, but not in the metric backhone, are highlighted in blue.
Application to Graph Construction Using N-NN
In large number of machine-learning tasks, data does not originally come from graph structure, but instead from cloud of points F1, Fy where each v. belongs metric space (say R&d for simplicity). The goal of graph construction is to discover proximity graph G = ([m), E. from the original data points. Graph construction commonly done through the q-nearest neighbors NN-NN). Given similarity function sim: Rd x Rd R4, that quantifies the resemblance between two data points, we define the set (uu, q) genearest neighbors
[n.. More precisely, N (u, q) the subset of [n]] {u} with cardinality g such that for all E W g) and for all g N(,,, we have
sim( Rv) 2 sim sim(r,, Tw).
We also note that the threshold graph G is often not connected. Hence, we ignored all components comprising less than nodes before running spectral clustering.

---

The edge set E is composed of all pairs of vertices (2, u) such that u E NNv, q) or E ((u,q) and the proximity Pue associated with the edge (u, v) is (Suo + son)/2, where
sim Tuu Te) TieEN(e q),
8 uv
0
otherwise.
In the following, we use the Gaussian kernel similarity sim( TT.) = exp
I 2
where
d (wx)
dg (z:) is the Euclidean distance between Iu and its q-NN. In Appendix C.2 using another similarity measure.
we provide results
We investigate the effect of graph sparsification on graphs built by q-NN. We sample
10000
images from MNIST [26) and FasHionMNIST [22. and use the full HAR (3] dataset (n = 10299).
From the sampled data points, build the q-NN graph Gg. as well as its metric backbone Grub and its spectral sparsification G We then compare the performance of two clustering algorithms, spectral clustering and Poisson learning. Poisson learning a semi-supervised graph clustering algorithm and was recently shown to outperform other graph-based semi-supervised algorithms (9] Results of spectral clustering using another similarity measure are presented the Appendix.
We compare the ARI of clustering algorithms on g-NN graphs and its sparsifications (metric backbone and spectral sparsification) for various choices of the number of nearest neighbors q. The results are shown in Figure 3 (for spectral clustering) and Figure (for Poisson-learning). Unlike the spectral sparsifier, the metric backbone retains high ARI across all choices of q. Interestingly, the performance on the original graph often decreases with q. which is a hyperparameter of the graph construction step. Applying a clustering algorithm on the metric backbone comes with the two advantages of significantly reducing the number of edges in the graph and of making its performance robust against the choice of the hyperparameter q. Indeed, a larger value of q creates more edges but with higher distance (cost), which are therefore more likely to be non-metric.
Original Backbona
0.575
Metric Backbone
0.48
Spectral Sparsifirr
Spectral Spansifier
0.550
0.525
Original Graph
c 0.500
Mutric Bac thone
0.44
Spectral al Sparsifeer
0.42
0.36
0.450
0.40
20
80
100
80
20
60
100
(a) MNIST
(b) Fashion MNIST
(c) HAR
Figure 3: Performance of spectral clustering on subsets of MNIST, FashionMNIST datasets, and on the HAR dataset. The ARI is averaged over 10 trials; error bars show the standard error of the mean.
0.74
Original Graph
0.54-
Original Graph
0.72
Spectral Sparsifier
Metric Bacibone
0.52
0.64
Spectral Spars
Backbone
0.70
0.62
0.50
0.68
0.60
0.66
Metric Backbone
Original Graph
0.58
0.62
Spectra Sparsifer
0.56
20
80
60
40
(a) MNIST
(b) FashionMNIST
(c) HAR
Figure 4: Performance of Poisson learning on subsets of MNIST, FashionMNIST datasets, and the HAR dataset. The ART is averaged over 100 trials, and error bars show the standard error of the mean.
Finally, we compare in Table T the ARI obtained on the g-nearest neighbor graph using q = 10 (as it is a common default choice) with the metric backbone graph of g-nearest neighbor graph with
In other words, an edge (u, v) is present if at least one of its two endpoints is in the geneasst neighborhood of the other.

---

Vn/2.. Moreover, we compute an approximation of the metric backbone by sampling uniformly random 2 logg n vertices and taking the union of the log n shortest-path trees rooted at each one of them instead of the union of all n shortest-patie trees. This produces graph Gmub whose edge yn/2
set is subset of the edges of the true metric backbone G v//22" We observe that Gmbb retains the vm/2
community structure albeit being typically twice sparser than the 10-nearest neighbor graph G1o-
Algorithm
Data set
G10
Čmub vn/2
ARI
0.533
0.563 + 0.011
MNIST
Edges
550, 653
373, 379 + 3,08 018
ARI
0.411
0.425 + 0.006
Spectral clustering
FashionMNIST
Edges
578, 547
272, 0 857
ARI
0.519
0.492 + 0.001
HAR
Edges
77, 526
37, 535 + 977
ARI
0.814
0.821 0.021
MNIST
Edges
550, 653
379.379 3, 3,018
ARI
0.526
+ 0.010
0.544 + 0.014
Poisson learning
MashIonMNIST
Edges
578,547
272, 063 + 857
ARI
0.618 + 0.039
0.636 0.037
HAR
Edges
77, 526
37, 535 + 977
Table 1: Comparison of clustering on full data sets. G10 denotes the 10-nearest neighbors graph, and Gmb denotes the approximate metric backbone of the /7/2-nnerrett neighbor graph. We vn/2 approximate the metric backbone by sampling only 2 log shortest-path trees.
Additional discussion The performance of clustering algorithms the g-nearest neighbor graph G, tends to decrease when increases. Indeed, a larger introduces many low-similarity edges, which can act as noise. Spectral sparsification preserves the spectral properties of the graph, but this becomes ineffective if the spectral properties of Gg are insufficient to recover the communities (as attested by the poor performance of spectral clustering for large values of in Figures 3a and Sap. However, when the performance of spectral clustering on G, remains stable as is varied, so does the performance of spectral clustering the spectral sparsified graph C (as seen in Figures 3b 8b). In contrast, the metric backbone preserves the shortest paths rather than spectral properties. Because the shortest paths robust the addition of numerous low-similarity edges the perfor- mance of clustering algorithms on the metric backbone Gmmb remains stable when increases. This holds regardless of whether the performance on the original graph G, is stable or decreases with increasing Finally, sparsified graphs obtained by metric sparsification are more consistent across different values of q than those obtained via spectral sparsification. For instance, dataset with Gaussian kernel similarity, the metric backbone G and G have both approximately 70k edges, with 64k edges in common. In contrast, the spectrally sparsified graphs G and Ges also with around 70k edges each, share only 22k edges in common.
the MNIST
6 Conclusion
The metric backbone plays crucial role in preserving several essential properties of network. Notably, the metric backbone effectively preserves the network community structure, although many inter-community edges belong shortest paths. In this paper, we have specifically proven that the metric backbone preserves the community structure in weighted stochastic block models. Moreover, our numerical experiments emphasize the performance of the metric backbone as a powerful graph sparsification tool. Furthermore, the metric backbone can serve as preprocessing step for graph construction employing g-nearest neighbors, alleviating the sensitivity associated with selecting the hyperparameter y and producing sparser graphs.
*Consider, for example, an adversary adding an arbitrary number of edges with a cost of w wSBM. Proposition proves that this addition does not affect the metric backbone, as none of these high-cost edges will be included in any shortest path.
Jog 11
in
10PP
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, ((())6644-6531, 2017.
[2] Lada A Adamic and Eytan Adar. Friends and neighbors the web. Social networks, 25(3))211- 230, 2003.
[3] Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Jorge Luis Reyes-Ortiz, A public domain dataset for human activity recognition using smartphones. In 21st European Symposium on Artificial Neural Networks (ESANN' 13), 2013.
[4] Konstantin Avrachenkov and Maximilien Dreveton. Statistical Analysis of Networks. Boston- Delft: now publishers, 10 2022.
[5] Afonso Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44(4):2479 - 2506, 2016.
[6] Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra. First passage percolation on random graphs with finite mean degrees. The Annals of Applied Probability, 20(5):1907- 1965, 2010.
[7] Béla Bollobás, Svante Janson, and Oliver Riordan. The phase transition in inhomogeneous random graphs. Random Structures Algorithms, 31(1):3-122, 2007.
[8] Rion Brattig Correia, Alain Barrat, and Luis M Rocha. Contact networks have small metric backbones that maintain community structure and are primary transmission subgraphs. PLoS Computational Biology, 1902)ee010854, 2023.
[9] Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepcev. Poisson learning: Graph based semi-supervised learning at very low label rates. In International Conference on Machine Learning, pages 130--1316. PMLR, 2020.
[10] Shihyen Chen, Bin Ma. and Kaizhong Zhang. On the similarity metric and the distance metric. Theoretical Computer Science, 21)224--5) 2009.
[11] Gabor Csardi and Tamas Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems: 1695, 2006.
[12] Fraser Daly, Matthias Schulte, and Seva Shneer. First passage percolation on Erdós Erdös-Rényi graphs with general weights. arXiv preprint arXiv:2308. /2/49, 2023.
[13] Michaël Defferrard, Lionel Martin, Rodrigo Pena, and Nathanaël Perraudin. PyGSP: Graph signal processing in Python, October 2017.
[14] Edsger Wybe Dijkstra. A note two problems in connexion with graphs Journal of the ACM (Numerische Mathematik, 1:269-271, 1959.
[15] Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference World wide web, pages 577-586, 2011.
[16] Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10(1):57-77, 1985.
[17] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7811-7226 2002.
[18] Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via semidefinite programming. IEEE Transactions on Information Theory, 62(5):2788-277) 2016.
[19] John M Hammersley and Dominic JA Welsh. First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Bernoulli 1713, Bayes 1763, Laplace 1813: Anniversary Volume. Proceedings of an International Research Seminar Statistical Laboratory University of California, Berkeley 1963, pages 61-110. Springer, 1965.
11

---

[20] Refael Hassin and Eitan Zemel. On shortest paths in graphs with random weights. Mathematics of Operations Research, 10(4):557-564 1985.
[21] Reinhard Heckel and Helmut Bölcskei. Robust subspace clustering via thresholding. IEEE Transactions on Information Theory. 61(11):6320 63400066322220 2015.
[22] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2:193-218, 1985.
[23] Svante Janson. One, two and three times n/nn for paths in a complete graph with random weights. Combinatorics, Probubility and Computing, 8(4):347-361, 1999.
[24] Vasiliki Kalavri, Tiago Simas, and Dionysios Logothetis. The shortest path is not always a straight line: leveraging semi-mi cemi-metricity in graph analysis. Proceedings of the VLDB Endowment, 99):6722-63, 2016.
[25] István Kolossváry and Júlia Komjáthy. First passage percolation on inhomogeneous random graphs. Advances in Applied Probability, 47(2):589 610, 2015.
[26] Yann LeCun, Corinna Cortes, and Christopher JC Burges. The MNIST database of handwritten digits. http::/yann.
http://yyaanneeu..ccco wew.nn cow ctt.ecumntcomeeeeemmmmm/////// 1998.
[27] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statisties, 43(1):215 237, 2015.
[28] Lasse Leskelä and Hoa Ngo. First passage percolation on sparse random graphs with boundary weights. Journal of Applied Probability, 56(2):458 471, 2019.
[29] Catherine C. McGeoch. All-pairs shortest paths and the essential subgraph. Algorithmica, 13:426-441, 1995.
[30] Mark EJ Newman. Networks. Oxford University Press, 07 2018.
[31] Tiago P Peixoto. Nonparametric weighted stochastic block models. Physical Review E, 97(1):012306, 2018.
[32] Tiago P. Peixoto and Alec Kirkley. Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection. Phys. Rev. E, 108:024309, Aug 2023.
[33] Yuval Peres, Dmitry Sotnikov, Benny Sudakov, and Uri Zwick. All-pairs shortest paths in (nn)) time with high probability. Journal of the ACM (JACM), 60(4):1-25, 2013.
[34] M Ángeles Serrano, Marián Boguná, and Alessandro Vespignani. Extracting the multiscale backbone of complex weighted networks. Proceedings of the national academy of sciences, 106(16):6483- 64880068888888888,88888888888888 2009.
[35] Tiago Simas, Rion Brattig Correia, and Luis M Rocha. The distance backbone of complex networks. Journal of Complex Networks, 9(6), 2021.
[36] Tiago Simas and Luis M Rocha. Distance closures on complex networks. Network Science, 3(2):227-268, 2015.
[37] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal Computing, 1016):1933-11 2011.
[38] Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. From Louvain to Leiden: guarantecing well-connected communities. Scientific reports, 91):5233,, 2019.
[39] Piet Van Mieghem and Huijuan Wang. The observable part a network. JEEE/ACM Transac- tions on Networking. 17(1)933-155, 2009.
[40] Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17:395-416 2007.
12

---

[41] Huijuan Wang, Javier Martin Hernandez, and Piet Van Mieghem. Betweenness centrality in weighted network. Physical Review E, 7744)0466,,, 2008.
[42] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv preprini arXiv: / 170..07747 2017.
[43] Ali Yassin, Abbas Haidar, Hocine Cherifi, Hamida Seba, and Olivier Togni. An evaluation tool for backbone extraction techniques weighted complex networks. Scientific Reports, 13(1):17000, 2023.
[44] Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the theorem for statisticians. Biometrika, 102(2):315-322 2015.
13

---

A Proof of Proposition 1
Let set up some notations before proving Proposition 1 We let G) wSBM(n, p: where the model parameters verify Assumptions [ and and we denote by and ė the cost and the extended cost associated with G, respectively. We let I,..... I' be the communities, i.e. l' {w E [n]: Aw a}, and we denote by ni,, my their respective sizes, i.e., nhe [Ta.- As k (1), the concentration of multinomial distributions ensures that aa (1 o(1))=,n whp.
A.1 Particular case of exponentially distributed costs
Proof of Proposition for exponentially distributed costs. We firstly assume that Fab Exp(Aab) with Aab 0. It is immediate notice that (fab)ab verify Assumption
Let u, be two vertices chosen uniformly at random in Io and I's respectively, so that 2, a and
2, = b. To explore the neighborhood of vertex u, we consider first passage percolation (FPP) on G starting from u. More precisely, for any > O, we denote by B(u, = {w E V: C(u, w) - f the set of vertices within a cost t of u, and by
(g) = min {+2 0: [B(u, () 2 1
the cost going from u to its g-th nearest neighbor (with the convention that min 0 = oo). In particular, (uu, C4) is the set of the y nearest neighbors of u. Let U(g) (U), ... Un(g)) be the collection of sets such that Uz(g) is the set vertices that are in the q nearest neighborhood of u and in community l, i.e.
Ue(g) B(u, Cu(()) nrz.
Finally, denote by S(u, 9) the matrix whose entry See (u, q) is equal to the number of edges going from Uz(4) to Pe (U)(()))
The outline of the proof is as follows. In first step (i), we study the FPP starting from vertex u to obtain upper and lower bounds on the cost C. (V' logn) for going from a to its yn log neneassst neighbor 10 More precisely, we will establish that
nPa Cu (Vnlogn) log
1 1+
(A.1)
2Tmin
holds whp. By symmetry, the same upper bound also holds for C.(Vnoogi
Next, we will show in step (ii) that B(u, vn log n B(u, vn logg))) * 0 whp. Together with the upper bound (A.I), we can then upper bound the cost C(u,, v) of the shortest path from u to Indeed, let w1 E B u, vn log n) n B(v /n log n) (such a wi exists whp by step (ii), and consider the path P= w u, where u - w1 and w1 - denote the shortest path from to wi and from w to u, respectively. Because the cost C(u, v)) of the shortest path from u to v aopeerbbunded by the cost of the path P, we have whp
1 + o1) log
C(u,v) < C(u, w1) C(w1,v) v) <
Tmin
n2p
where the second inequality holds because wi E B(u, log n B(e, loglo)) n). which enables to use the upper bound (A.I). This establishes the desired upper bound on C(u, r).
To lower-bound Clu,, v), we will establish that
1 o1)
npn Cu (V log n
I
(A.2)
2Tmax
logn
holds whp. Again, similar bound holds for C. (vn/ (Vn/logn) by symmetry.
Finally, we will show in step (iii) that B u. Cul h///o/ll))) n B (1. (u, Co.CC(///logg) logn) = 0) whp.
Combining this with the lower bound (A.2) we conclude then that whp
+ o(1) logn
Clu, v)
Tmax 1pPm.
10 Because n log n is not necessarily integer we should write [ V/nlogna but we drop the [ andd to avoid overburdening the notations.
14

---

(i Upper and lower bounds on Culyn/ logn) and Cu(.nlogn). In this paragraph, we will establish (A.I) and (..))
key property of the FPP is to notice that, conditioned on S(u, :) (S(u, 1),... S(u, n)), the random numbers (q 1) C. (2) are independent and exponentially distributed, such that
Culq + 1) - (g) S(u,-) ~ Exp
Σ E.P
See
(A.3)
Indeed, Cg + 1) (g) is the difference in the cost of traveling from u to its (q + 1)-th nearest- neighbor minus the cost from a and its q-th nearest neighbor. In other words,
Cu + 1) - Cu(g) S(u,.) w wrerrrAUarlg
min
Cww':
(A.4)
wED
with Canor ~ Exp(Aes Statement A.3) follows because min (Exp(A), Exp(x)) ~ Exp(A + p))
Let q Vogo... The number of edges See (u, between the Ue(g) and Te (e)(e(()) is binomially distributed such that
Su ~ Bin ((U(()) x (2) PPct)
The number of vertices in L' is ng (n) and the number of vertices in UUe (4) verifies (Ue s q < n. Therefore,
E [Ser (u, 4)] = [Ur(g)] (ne - |U> (4)l) per (1 (1)) (Ue(g) nepe-
Hence E [Ser (), > 1, and the concentration of binomial distributions ensure that whp
See (u, 9) (1 o(1) (U((g) (ne -Ue(9)))pe (1 + o(1) (e(()) nepe.
(A.5)
Therefore, using ne (1 (1)) and per Bee we have from A.4)
1 +(1))
[C.(q + 1) C. [- = Σ, [v(()) Ee ne
= npn E. (ee()) Ee Te Aer Be
We notice that E, (Ue(a)) Texe UT (q)TTI where T (A@ B) diag(T) the operator
defined in (2.1 Then, using Ee((e()) = q, we have
mmiu S
[Vell9)1 Σ
Tede Bee S Tmaxq.
(A.6)
Therefore,
1+ (11)
1+
< E Ca -
S
(A.7)
nPn mmax
npx Tmin
This bound is uniform in S(,, Thus, using the total law of probability and summing over all 1 S q S Vnlogn leads to
I o() <
npn E.C. / n logn) <
1+0(1)
(A.8)
2Tmax
log n
2Tmin
where we used Σ Eynloge log n y- = 2- n + log log ((1).
Let us now upper-bound the variance of C. (Vnlogn) By the law of total variance, have
Var [Cu(Vnlogg)
E Vaa Cal ( logn) S(u,))) +)] + Var [ [CCC(C/noonn SS I]]
(A.9)
The first term the right-hand side of (A.9 can be upper bounded by proceeding similarly for the expectation. Indeed, we have
1 o()(1) n² 2222TT2 min 9²
Var [Cu + Ca(g) S(u. <
15

---

and the independence of Culq + 1) Cg conditioned on S(u, :) leads to
vn lologg n-1
Var (lg (
Σ
Var (Cala+11) Cx(2) S(u,))
Vnlogn
1 + (11
Σ
q
n² pm -
min
9=1
+ o(1) π²
(A.10)
n² ph m 6
To upper bound the second term on the right-hand side of A.9
we notice that
V log
Var E (Cu(vnlog (S(u.))
Var
1)
Vnlogn-1
Var
I]]
where the first line holds by the linearity of the conditional expectation, and the second one by the independence of Cu(g + 1) (g) conditioned on S(u, -). Moreover, recall that Var(X) S
aa2/2///// if S X s b. Hence, using the upper and lower bound on C.(q C.) obtained
in A.7
leads to
+ o(1)
Var [[Cu(q Ca(4) S(u, -II s
"PPnFming
nnp Tmaxq
+ o(1)
4
11p:.mmin
and therefore
1 o1) x²?
Var Cu( n log n)
S(u, -)
(A.11)
4n 2 p T
Combining (A.10) and A.Il into A.9
provides
5 o(1)
Var (C((Vllggn)
(A.12)
67 min
n²pp
This upper bound A. 12 ensures that Var [Cu(vn log
= (EE [Ca [Ca(Vnlogn))) and there-
fore an application of Chebyshev's inequality ensures that
1 1 o(1)
npn C.,, (Vnlogn)
1 o
2Tmax
logn n
2Tmin
with high probability. Likewise, by symmetry for FPP starting from instead of u, we find
1 ++o(1) o(1)
I npn C. (Vnlogn) I
1+o(1)
2Tmax
logn
2Tmin
This establishes (A.I). Moreover, we establish A.2) by doing slight modification of this proof.
More precisely, we sum over all q S /n/ /n/log instead of all g I vn log in step (A.8). We obtain
the same bound as in A.8 because EV log q-d 2 (log log log n) + ((1..
(ii) B(u, Co B(v Co Co(vn Co + whp. For ease of notations, us shorten by B,, B(u, C. (v log n)) the set of the /n log nearest neighbours of and by B, (g) the set of the nearestt neighbours v. We also denote by w, the q-nearest neighbor of A key property that the two FPPs (starting from vertex and starting from vertex v) independent of each other as
16

---

long they do not intersect. To make this rigorous, we denote by Q the random variable counting the number of steps made by the FPP starting from without intersecting with B,, i.e.
Q = min {q E [n]: B. n (.(()) 0}.
now show that P (QQ > g) o(1) whenever q >> vn/ log n. which implies that B, n
By (Vnlog)) o 0. Using 6 Lemma B.1], we have
P ( > m) = E II (
(A.13)
where ((9) denotes the conditional distribution given B,, and (4). We further notice that
Q (4) ( >
= 1-0(() (Q
and that the event {Q > 4--4-11 is equivalent to the event {wi $ B.. 1 & B. i.e. the FPP starting from has yet collided with the one starting from w. Conditionally on this event, all vertices within the same block have an equal probability of being chosen at the q-th step of the FPP. Therefore.
( (Q =0=1
Σ EE(k]
P (wgg Bu Wg ET, q 1)P (wy E Te)
=
Σ
Tel
(wg E r'e).
EE[A]
Because ΣeEjy |B, nirl Vn n, we have that max; [B,, nlrl (onl2=-Vnnkkln VVllogn. Moreover, Tel & (1 + o(1) Tmax whp and Eee(s] (wt- E Pe) 1. Therefore.
max(e(k) |B, eTel
( (Q = g g-
P (w, E Tr)
minselu
Tel
[E[K]
1 1 ++0(1)
logn
x maa
n
Going back to A.13 this implies that
+ ((1)
log
(Q > m) S
Tmax
n
which indeed goes when m
> /n/ /n/logn.
(iii) B(u, Cu Culyn/ log n n Blv Col / / log n1) 0 whp. We proceed similarly to step (ii) by considering the FPP starting from v, and denote by wy the g-nearest neighbor of v. For ease of notations, let us denote in this paragraph B,, = u, C., (n/logm) and Bz(g) (v, C. (q)). Note that, in contrast to step (ii), we now look at the FPP up step v /n/ log instead of the FPP up to step /n log n. We define
Q = minig E [n]: B. n.n. (B((g) # #).
We have
P (Q = P P B. Q> - Q>>--1)((29-1
BB, Tel
(wg -
Tel
telk
Recall that if + with > 0 then maxt 2 1 m.
17

---

where, as in step (ii). the second equality holds because all vertices within the same block have the same probability of being chosen at the next step of the FPP as long as the two FPP have not collided.
Using [ 2 (1 + o(1)) Tiin n and [B, nTel S [Bul S /n/ log n leads
1 (
P = 4) V
Tuin /n log
Therefore,
n/ log n
1+ o(1)
PP (B, n nB #0)
=
PQQ - S
Tmin log = o(1).
This concludes the proof of Proposition | when Fab ~ Exp(Aab).
A.2 General case
Proof of Proposition @ with non-exponentially distributed costs. In this section, the probability den- sities Fat are regular (see Assumption 2 but not necessarily exponentially distributed. We adapt the argument provided at the beginning of Section 2 of (23). The strategy is to transform the graph G (V, E. c) generated from a wSBM((n, n, F)) into a graph Gexp = (V, E, Cexp) with the same vertices and edge set but where the costs Cexp are obtained from F. and are exponentially distributed so that Geep has the same distribution as a wSBM (1z, π, (Exp(Aat))..o We will then show that the
(V,
shortest paths in Geep and G' are the same.
Fd (0). Let Faol Let Sab be the density function of the edf Fan, and remember that Aab = Fa
be the generalized inverse function 12 of Fab- By regularity of Fas (Assumption 2 we have lim Fas(t/t = das and thus lim F (t)/t - > >ui- We also denote by Jos (x) = Aabe Aanz
and by Gao(z) = e duse the density and cumulative distribution functions of Exp(Aat))
We first show that Proposition]] 1 hholds for uniformly distributed edge weights, i.e., when fab(z) lz (z E [0, (. Denote by Fas the cdf associated to fab. and let (2, G) ~ wSBM(nn n. F) where G EV,E.c). We construct the graph Gexp = (V, E, Cexp) such that for all (w, w²) E with 2 = l and znx = l' we have Cexp (w, w²) = G ((w, w²)). Note that the (unweighted) edges of G and Gexp are the same, only the costs and Coxp differ. Since Xee w. w') ~ Unif 1) we have Cexp (w, w') ~ Exp(Aee) In particular, Gexp has the same distribution of weighted SBM whose costs are exponentially distributed, i.e., (z, Gexp) wSBM(n, p, G) with G = (Gab)a.
Let P(u, v) (resp., (uxp(u, v)) be the shortest path from C(u, v) (resp., by Cexp (w,v), v)) its cost. We know from Section A.l that Cexp(u, u) θ
in G (resp., in Gexp), and denote by logn whp. 13pm
Suppose that the edge (w, w²) E E belongs to (u, v). From Gexp (w, w') I Cexp (u, v) we notice that Cexp( w/) ( log=) ), and hence by Assumption we have Cexp (w,w') o(1). Moreover, by definition of Cexp we have
c(w, w') Cexp (W, w')
1 Gee (Cepp w'))
Aee
Cexp (w, w')
Recall that lim,--0 Get (t)/t= Awe. Thus, we have for any > 0 and for large enough, 1 - < clw.ww)) < 1 + e. This holds for any edge (w, w/) belonging to (uxp(u, Therefore, the sum of Geap (M0 "
the costs c(w, w²) over Pexp(u, 2) is at most (1 + e)Cpxp (u, v), and hence C(u,e) v) (1 + e)Coop (u, v).
(A.14)
Similarly, if (w, w') E P(u, v). then the upper bound (A.14) together with Assumption iimpy that C(u, v) (1). This in turn implies c(w, w') = o(1) and hence 1 - Casep 2077
e(w,.w"
1 1 Thus,
summing over all edges in P(u, v) leads
(1 - C)x (u, v) < C(u,v).
(A.15)
More precisely, we define F.5 (1) = inf R: Fa(x) 2 t}. Because the edf Fas is increasing, F is dell-defined.
18

---

Combining (A.14) with A.15 shows that Proposition holds for uniformly distributed edges weights.
Finally, if the costs c(w, w') are sampled from general distributions Fas verifying Assumption 2 then we construct the graph Gunif = (V, E, Cunit) where Cunit (1, v) = A Fz. (c(u, u)). We have
Gunit (u, v) ~ Uni 2..) and we apply the previous reasoning (by replacing the exponential distributions with uniform distributions) to conclude.
B Proof of Sections 2.3 and 2.4
B.1 Proof of Theorem 1
Proof of Theorem 4 Let G = (V, F, c) be a wSBM, and let u. E V be two arbitrary distinet
vertices such that Zu = a and 2, = b. Then, adapting the proof 13 of (39 Corollary IJ, we can write
Pab
----- Guo (a) log(1 os dr, mb
(B.1)
where (x) is the probability density function of the weight of the shortest path between and and Fas(x) = -Ie (at(x)dr is the cumulative distribution function of the length of an edge between two vertices belonging to communities a and b.
Proposition ensures that, with high probability. the cost C(u, v) is a random variable whose support is lower and upper bounded by 1+o(1) logn and 1++(1) logn
Tmin np., respectively. Its density function (x) tends therefore to zero outside these two bounds, and hence by setting the log(-) factor in Equation [B.1) to the lower and, respectively, the upper bound of the support of C(u, v), and by integrating next the pdf (x) over the whole interval, Equation (B.I) implies that
Tmax npp
++ [(L)
o(1) log
))
(1 (1-Pao Fab (1+ (1+o(L) log
o(L)
log Pab
I Pab S -log
Tmax
n2p
Tiin npn
We finish the proof using Fab (I+o(1)) logn))
= (1+ + o(1))
log and Fab (1++([1) log Tmintipn
Tminiinn
Tmaxetin
log Tiaxx nP (1 + dab
(Assumption 2
B.2 Proof of Theorem 2
Let G (V, c) be the original graph and Gumb = (V, Emb, cmub) its metric backbone. Let E C be the subset of edges whose cost no more than 0:
Proof of Theorem
(u, E E - c(u, v) < 0,
and which is the edge set of the corresponding threshold graph G = "V,,E,,,), where e is the restriction of c to E.
Denote by W, Wmb, T R the adjacency matrices of G, Gmb, and G respectively.
Overview of the proof. To prove Theorem 2 the key idea is choose threshold & large enough such that the threshold graph contains the metric backbone (i.e., Fub C E²), but not too large so that the adjacency matrices Wmb and 8 are not too different.
Lemma ensures that, for any > 0, we have maxxi Clu, v) S 3+c log
= o(1).
Tinin 1ppm.
Hence, Emb C E whp soon 0 3+e Ing
Tiin APr. We choose 0
lng.2 and we proceed by Timin APp
conditioning on the event Eum C E which occurs with high probability given our choice of 0.
We will first prove that the clusters exactly be recovered using the eigenvectors of EW/mb Then, using SawiisKahan'ss Theorem [44] Theorem 21, we show that the clusters can also be recovered from the adjacency matrix W/b provided that !| EW is small enough. More precisely, obtain an upper-bound on loss(2, (2, 2) that depends on || EWmbjj. The main ingredients of the proof are thus (i) the justification of the choice in Lemma D and (ii) the careful upper-bounding of mb EW
We note that (39 state the result for weighted Erdös Rényi random graph, but their proof holds for wSBM well.
19

---

Starting point: eigenstructure of the expected adjacency matrix EW and Davis-Kahan. Let Z E {0, 1]mx be the one-hot encoding of the true community structure 2 [k] i.e.
[ {
if 2 = a.
Vu E [n], Va E
[
Zua
(B.2)
0
otherwise.
For any two vertices u, v belonging to communities and b, respectively, we write EW Let M = (Mab) E R We have
ue Mab-
EW ZMZ
Denote by |01| 2 lōkl the & eigenvalues of EWmb, and by u1.... Ug their associated eigenvectors. Let E. (11, ok) E R and Ü [ū,,-. ... üg. Bonk We have
EW USUT.
(B.3)
Let A = diag( / E B be the diagonal matrix whose diagonal elements are /ami; We have
VeTk
ZMZ (Z AMA (ZA (A -)-
Notice that ZA-1 E R has orthonormal rows (indeed (Z -
T because 7 = A²), Let ODO be eigendecomposition of the symmetric real-valued matrix AMA A (that is, D E B k*k is a diagonal matrix whose diagonal elements are decreasing order (in absolute value) and O R kxl is orthonormal matrix). Then
ZMZ (za- p (ZA-
an eigendecomposition of ZMZ (because za-10 is orthonormal), Hence, going back (B.3 we have Σ = D and U = 20 for some orthonormal matrix O E IR fxck
Because Ū ZA '0, 0, two vertices in the cluster if and only if their corresponding rows in are the same. In other words, the spectral embedding of the expected graph EW is condensed into & points (A- (0))'),.."" (A- of R Consequently, k-means U recovers the true clusters (up to a permutation).
Next, 27 Lemma 5.3] ensures that any (1 + 6) solution E of the k-means problem on UE verifies
loss(2, 2) < 4(4 + 2c) min IUO - 0|
(B.4)
Og0xxk
where Oaxk denotes the group of orthonormal k-by-k matrices and || || is the Frobenius norm. Davis-Kand Kahan's 's Theorem [4 Theorem 2] ensures the existence of an orthogonal matrix O e O O such that
IUO- s 23/2 Wmub EW
(B.5)
where || denotes the matrix operator norm.
Let us now establish an expression of |ox]. eigenvalues
Observe firstly that AMA and MA have the same
From Lemma we have
log n
log* n n Pm.
(A @ B)ab
S mab <
(A ② B)
2T2
n² n2Pp
2r min
max
The definition of T =
[A ④ B diag(n (T) in 2.1 and the fact that A = n diag(m) further imply that
Tab log² n
Tab log² n
(MA²) ab Σ
2 max
npn
2T
npn
Recall that 0 4 log and y is the smallest (in absolute value) eigenvalue of T. Using the assumption Tiin =
Tman RPs
Tmaxx we obtain that MA²
8 8log T and thus
STais
# 0 log
σk STmin
(B.6)
Therefore, combining B.4p. B.5) and B.6). obtain
8Tmin
W EWmb
loss(2 2, 2) s (4 + ke
(B.7)
#
Blog n
LLet A, B be two symmetric matrices of the same size. Let X be an eigenvalue of ABA, with corresponding eigenvector Multiplying both sides of ABAr Ax by A, get A By Ay with Ax.
20

---

Core of the proof: concentration of Wmhh around EW"h. We finish the proof by showing that || E| 100 (lylogn) whp. First, by triangle inequality, we have
mb EW I | - w - E W W0
+ I EW"I
(B.8)
For ease of the exposition, we will upper-bound the term of (B.8) in the following order: (i) the second term | EW and then (ii) the first term | W E
[ W ||-
(i) Let us first study | - - - The matrix X = /0 is symmetric with zero-diagonal whose entries {XXmm u < ) are independent [0. 1]-valued random variables. Moreover, Lemma shows that IE [x zu Ze = b] Pab (logg/n)) Thus, [88 Theorem 5] ensures that for any
e > O there exists d' > such that
(1w0- - 2 é' 2'00 Ovlog S n
(B.9)
(ii) Next, let us study ||W=b_ we [Wmb_ Wo] 2l. Denote = (Wmb, W /0. By Lemma 1 and our choice of 6, we have Emm S E" (for large enough). Moreover, W ur = Wmmb for all {u, r E Fmm n E = Fuub, Hence,
W
if {u, o) E E \ and EYwv otherwise.
FW
if {u, of E Eumb, otherwise.
Lumb
Y uu
0
We can thus rewrite the matrices Y and EY as Y = R W /0 and EY = R R EW"/ where Q denote the Hadamard (entry-wise) matrix product and R E 10, jx is defined by
Rus = {
if (u, E E Emmb
Rue
otherwise.
Let Ee, be the event that all rows of have at most ej logn non-zero entries (with ej > 0), iee.
Eer Vu E [n]: Σ 1(Rav * #0} S c1 logn
Because Eub C E we have
1 RR #
Ruv 1f(u, Emb I 1)(u,)) E E
Thus, 0 S Egy where
E,,0 Vuu [n]: Σ E E²} s ci log n
Hence, P(Ee,) 2 P(E,, s). Recall also that 1((u, v) E Ed} ff(uu, w) s 0}. Thus, by Lemma 2 for any co there exists a e₁ such that
PP (E 1 1 50
(B.
Conditioned on the high probability event E every row of the matrix R has at most e₁ log non-zero elements. Moreover, W/0 is symmetric and has bounded (hence sub sub-gausee (abs-gaussia)) entries. Therefore [5] Corollary 3.9] ensures the existence of constants C, C" > O such that
P R (Wo EWO) /0 2 C Colog + t ( -C'
Using t C" Vlog n. and because Y EY R (Wo CPp--EWP -WW) /0, we obtain the following statement: for any there exists d' such that
P (IY EY 2 c'vlogn Eci) nc
Using B. we finally obtain
(IwWTh wo [w/b Wo] || 2 d0 c0vlogg) 5 2n
(B.
21

---

Conclusion Using [.8. B.9 and (B.11. we have
W ||
El
I
2c' 2' logn.
(B.12)
with probability at least 3n c The proof ends by combining [..12 with (B.7).
B.3
Additional Lemmas
Lemma 1. Let G2 wSBM(n, T. p. F) and suppose that Assumptions and 2 hold. Then,
3 log
max C(u,v) s (1 + o()) Tmin nPn
u,ee(n)
Proof. We proceed in the proof of Proposition by firstly assuming that Fab Exp(Aat). The extension to more general weight distributions follows from the same coupling argument presented in Section A.2 and is thus omitted.
We use the same notations as in the proof of Proposition Recall in particular the notations C. (g(g) and X (u, q). Because we established that B(u, C. log n B(v, Co log n)) * whp, we have
cu s CulV/llogn) + Co((nlogg))
Therefore,
max C(u, & max (Cul V logn) + C. CC log
2 max C logn)
Using union bound, we obtain for any & > 0.
P max Culy
2t) 1 Σ (Cu(Vnlogy 2t)
u
=
nPP CC- (V log 2 2()
(B.13)
where u" denotes an arbitrary vertex chosen in [m]. For any > O, we have (by Chernoff bounds)
P (Ca.. ( 2() e e 50 (vālonm)
(B.14)
Recall from A.3) that C.. (4+1) Cu- (4) S(u, are i.i.d. Exp((,) with 0g Ee,r Sew (u, As for X Exp(#) we have E[e*X] 0/(0 s) = 1 s/(B - s),
g).
vn
Vnllog log
CC. (v R) [S(u.))
II
E (C (o S(u,
Voglon
1 + Og
q=1
log Σ
exp
log
1 +
0g
Vn
< exp
0g
Let 0 e 1/6. From Equations
A.5 and A.6 have whp (for n large enough)
0 2 (1 c)pp. Tming.
22

---

Choose (1 pe) Tmin and let on be a diverging sequence verifying an = =lvvn n) to be chosen later. We split the sum as follows
logo
vn log
8
0g
0g
a +1
We have for any 15 q an
1
2E
0g 2 1pn
1 1-c
N
min
q
while for an 2 we have (1 -2 I (for large enough) and thus
(I-e-
1 1 2c
1 2c
0g s s 2 Taing
2 nPn Tminn
2 np Amingi - -2e),
On
and thus
log
ag
vnllog
Σ 9=1
0g 8 S (1 - 2e)
2
q=
Recalling that n
2q=m+1 q 1 S bog(n/m) for any m 2 1 (by integration) further leads to
Va Valog n
Σ
8
I (1 - 26)
(1 (1+ aog + 1 1 2t
1
log
V/n log
]
0g 09-8
O'n
Therefore,
E Cu (Vnloogn) S(u,)) )]
s exp 2c)
+1g + 1 2e
1
log
V n log n
Because the hantt side of this last upper bound does not depend on S(u, :), we have by the total law of probabilities,
E Co. (vn m) s exp (1-26) 26) (/ log ana) + 1 2c
(Vn (Vnlog log
)))
log
(B.15)
On
We choose Ox = [Vogg]] Because an w(1), On = o(log n). and e fixed, we have for n large enough,
1 ( - an) S
log n
V Vnllo ni
log 2
log
(1 + 3c)
1 - 2e
On
where the second inequality uses < 1/6. Thus, we can rewrite the inequality BB.5 (for n large enough) as
c (v l)
I exp (1 (1-2e) 21) 4e) log
exp (1 + 22)
log 2
Let = (3 + e') logn/ (2mpp miin) with e' = 15c. Recall that = (1 - 26 22) Tmin T From B.14 we obtain
(V-(lV/lgg)) 21) < e -1 (1-2c)(3+e)) loy" (1++2) J0nm
p
e lagn 18-8--20 (2-8e-2e'+ee)
< log n(1+c)
where in the last line uses -8c 2cc él 6c 30c² 2 (using < 1/6). Because 1 ++>> we have P (Car log o(n-1), and we conclude using (B.1)..
0
23

---

Lemma 2. Let G), ~ wSBM(n, T, F.P.F) F) and suppose Assumptions and be two constants (independent of n., and let O co mpn.
hold. Let cu. c1 > 0
log
Denote
Eg,0
Vu E [n]:
Edlcu o) 50) s (4 01) log
==1
Then, (E),,) 2
Proof. For + E [n]] such that and 2n = b, we have (recall that the probability of having an edge (u, v) E E is pubs and the cost this edge is sampled from Fat)
P (c(u, v) S 01 Zu a, b) = Pab Fas(O..
Recall also that, by Assumption ! we have Pot = BabPn and by Assumption Fas(2r) = =(1 d(1)) Let > O. Using the law of total probability, obtain
P (c(u, v) $ 8) S (1+ o(1)) Bmax
where Bmax Sa Bus and Amax maxisa,bse Aab- Thus, for large enough have
P v) s 0) <
For case of notations, let = 2B max max Ppn and č = 4Bmax + + c1
For [n]] we denote d, E.= [cc(u,)) v) 0). We have
P
max du ēlog 1 Σ wEIn]
(d. 2 člogn).
(B.16)
WE/n]
Moreover, for any t 0, we have
E [c' I (1- pe + poet)" S uPa "
(c
where the second inequality used log(1 + x) < Let ē > O. Using Chernoff's bounds, we have
(du 2 nl I nnploee-
Let & 1. Because el and npa 2B max maxax max logn, obtain (d., ē log n) We finish the proof by letting ē Pimaxdmaxet + Ci and using B.
dog 4B Amseen))
Lemma 3.
Let (z, G) wSBM(nn, D, F) and suppose Assumptions I andd 2 hold. Let
log nPn
Denote W the weighted adjacency matrix of G, and 8 the weighted adjacency matrix of the threshold graph. Let u, [n] such that zu = and zy = b. We have E W 02 /2.
uo S O0. Proof. We have w 1WW
Moreover, W. W.. o 0 is sampled from Fas. Thus,
[ [
Pat [W W.. (W av I ()]]
Denote also fas the pdf of Fab. Recall by Assumption that fat dab + Oz)). Because 0 << 1 we have
8²
EE
[ uv
= Pab Nab
2
Lemma 4. Let (2, wSBM(n, R, F) and suppose Assumptions 1 and 2 hold. Let
c log np.
Denote W the weighted adjacency matrix of G, and mmb the weighted adjacency matrix of the metric backbone of G. Let u, v E [n] such that zn and bu b. We have
1
log" n n2 Pm
log n n² Pr.
27 2 max
(A
④
ab
<
E
WDmb] uv
2-2 min
(A ④
ab
24

---

Proof. Let u E [n] be two arbitrary vertices such that zu = and b. We have W ())((,)((() E Fmmb.. Recall from Proposition that
7Pn C(u,t) & (Tmin)
(Tmax)
log n
whp, where C(u, v) is the cost of the shortest path from u to v. Therefore,
E [mm]]
E v((uv) (u, v) E Emb]
c(u,v) 1 log
S E c(u, v)1l
Tmin npn
log
= Pabdab
FminnPp
where we used Lemma
with
In Tmin npa
Similarly,
E Wrmb]
IE ((lu,))1 c((,,) v)
1 log
Tiax npn
1
log
-Paddet
Fmaxx1Pn
Recalling that Pas = Babpas we obtain
1
log
1
log n n² Pr.
(A B)
$ E
[mm]]
1
(A ② B)
2-2
n²Pp Pr.
2r2
C Additional Numerical Experiments
C.1 Additional Material for Section 4
Data set
[E]
k
d
High school
327
5,818
9
36
Primary school
242
8,317
11
69
DBLP
3,762
17,587
193
9
Amazon
8,035
183,663
195
46
Table 2: Dimensions of networks considered. High school and primary school data sets are taken from http: /wwww/wwwwwc/oco///// sociopatterns org where the weights represent the number of interactions between students. DBLP and Amazon data sets are unweighted and taken from https::/ssmt stanford. .ew.forr.ddd/aaaaa/ d denotes the average unweighted degree, i.e., E/n
Data set
High school
Primary school
DBLP
Amazon
mg
0.29
0.34
0.82
0.72
B
Table 3: Ratio of edges kept by the metric backbone in various real graphs.
We highlight the difference between the metric backbone and the spectral sparsification of the Primary school data set in 3) Whereas Figure highlights a clear pattern between the metrie backbone and the threshold graph, finding from Figure 5 anny pattern in the edges present in the metric backbone but not in the spectral sparsification (and vice- vice-versa) much harder. Although both sparsified graphs preserve the community structure very well, they do so by keeping very different set of edges.
25

---

Metric Backbone
(b) Spectral Sparsifier
Figure 5: Graphs obtained from Primary school data set, after taking the metric backbone (Figure Sa and after spectral sparsification (Figure (5b). drawn using the same layout. Vertex colors represent the true clusters. Edges present in the metric backbone but not in the spectral sparsifier graph are highlighted red. Similarly, edges present the spectral sparsifier graph, but not in the metric backbone, are highlighted in blue.
We preprocessed the DBLP and Amazon datasets by only keeping components where the second eigenvalue of the normalized Laplacian of each component that is kept is larger than 0.1. This ensures that we do not consider communities that are not well-connected.
We additionally show in Figure [6 the performance of the three clustering algorithms (Bayesian, Leiden, and spectral clustering) on four other data sets. As do not have any ground truth for these additional data sets, we computed the ART between the clustering obtained on the original network and on the sparsified network. We observe that the largest ART is almost always obtained for the metric backbone. This shows that the metric backbone is the sparsification that best preserves the community structures of the original networks.
Metre Bacchone
Metr Baccbone
Netr Bacdonn
1.5
Suberar
3.5
buberuphh
3.2
bulpuuph
0.0
0.5
64
0.4
044
15
Dasead.
Da.eod.
Da..add
(a) Bayesian MCMC
(b) Leiden
(c) Spectral Clastering
Figure 6: Effect of sparsification on the performance of clustering algorithms compared the results of the same clustering algorithms ran on the original graph.
C.2 Additional Material for Section S
Number of edges in the g-nearest neighbor graph and metric backbone We show in Figure the number of edges in Gg and Grub (we do not show the number of edges of the spectral sparsified G because the hyperparameters of G chosen such that Gmbb and G have the same number of edges).
Exploring another similarity measure Finally, provide additional evidence supporting the robustness of the metric backbone with respect to the number of nearest neighbors q by providing the results of another clustering algorithm, namely threshold-based subspace clustering (TSC). TSC a subspace clustering algorithm and was shown to succeed under very general conditions on the high-dimensional data set to be clustered (I]]. TSC performs spectral clustering nenarsst neighbors graph obtained using the following similarity measure
sim(Za, σ.) exp (-2 arccos (< Zu, Ze >)).
26

---

1e4
1c4
1e4
Original Graph
Original Graph
Original Graph
Number of Edgge
50
Number of Edges
80
Backbone
Number of
40
20
20
40
60
80
100
20
40
60
100
20
40
60
80
100
(a) MNIST
(h) FaSHionMNIST
(c) HAR
Figure 7: Number of edges in the genearest neighbour graph (built using Gaussian kernel similarity) and its metric backbone.
Because in Section 5 we showed the performance of spectral clustering using the Gaussian kernel similarity, these additional experiments also show the robustness our results with respect to the choice of the similarity measure. Figure 8 shows the performance of TSC G2 and its sparsified versions Gmb and Gg and Figure shows the number of edges (before and after sparsification).
Original Graph
Original Graph
Driginal Graph
Metric Backbone
0,46
Metric Backbone
Metric Backbone
Sparsifier
Sparsifiar
Sparsifier
0.44
0.42
0.55
0.40
0.50
0.38
0.45
20
40
80
100
20
60
80
20
40
60
100
9
(a) MNIST
(b) Fashion MNIST
(c) HAR
Figure& 8: Performance of TSC subsets of MNIST and FashionMNIST datasets, and the HAR dataset. The plots show the ARI averaged over 10 trials, and the error bars show the standard error.
104
Driginal
80
Graph Metric Dackbone
80
Original
Number of Eriggss
60
Metric Backbone
Number of Eriges
Number of Erigge
60
Metric Backbone
40
30
20
20
40
60
80
100
20
40
60
100
(a) MNIST
(b) FNSH
HAR
Figure 9: Number of edges remaining in each graph, using dot product similarity.
Computing Resources All experiments were run on a standard laptop with 16GB of RAM and 12th Gen Intel(R) Core(TM) 17-I2 CPU.
To compute the full metric backbone, we used the igraph distances implementation [ It takes around 7 minutes for graphs with 10, 000 vertices and 10. For the same graph, computing the spectral sparsification takes around minutes. In general, computing the spectral sparsification was 2 to 3 times slower than computing the metric backbone. Computing the approximate metric backbone takes around 100 seconds for 70, 000 vertices and q = 132 on our C++ implementation.
For spectral clustering and TSC algorithms, the bottleneck is the clustering part: running the scikit- learn implementation spectral clustering takes 3.5 hours for MNIST and hours for Fashion- MNIST while we only needed 100 seconds to obtain the metric backbone approximation.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state all the theoretical and numerical claims made in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our work points out the assumptions made the different theorems (especially Assumption [. The numerical section (done only using real data) highlights that the results are robust model misspecification (by going from weighted SBM to real data sets). We used several types of data sets (such as social networks, interaction networks, images), and several clustering algorithms to show how the method generalises well. Computational efficiency is discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
28

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper are numbered and cross- referenced. All assumptions are clearly stated referenced in the statement of all the theorems, The proof's are in the suppiemental material, but we provide a proof sketch of the main results in the main text.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: we release all the code and data used to perform the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
29

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
we release all the code and data used to perform the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
//nips.ccpputee wwtpcccccppccccceee copollccggiieee wwwedeeeeeoeebbbmeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: we present in the core of the paper all the detail necessary to appreciate the numerical results. The supplement (Appendix C contains additional information (such as network statistics). Finally, we also release the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: the results are accompanied by error bars, showing the standard error.
Guidelines:
30

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details about compute resources are included in the appendix
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp://neurii: http:///nnnnpppc.cp/c/p//////aaa http:pubbb..iiiiiiciciceeeeeeeee
Answer: [Yes]
Justification:
We respect the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is no direct societal impact of the work performed.
31

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: we cited all the original papers that produced the code of the various algorithms, packages and datasets used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
32

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
33

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "nimbonv4fX", "reviewer": "Reviewer_JByP", "summary": "The authors investigate the shortest-path backbone that is the union of all-pair shortest paths in a weighted graph, and show that it preserves the community structure in weighted Stochastic Block Model (wSBM) with high probability. A key finding in their proof is that the metric backbone maintains the same proportion of intra- and inter- cluster edges as in the original wSBM graph. Then the classic Spectral Clustering algorithm is able to reconstruct the embedded communities with high probability. Their experimental results confirm that the shortest-path backbone can preserve community structures in real datasets, and is also an efficient sparsifier in the presence of communities.", "questions": "1. I am not sure whether it is proper to say that it is intuitive that metric sparsification should dilute the community structure (in Line 56), since for the simplest case of unweighted graphs, the metric backbone clearly maintains all edges and the community structure will be preserved certainly.\n\n2. It seems that the Spectral Clustering algorithm (Algorithm 1) deals directly with the edge weights of wSBM that is introduced by the exponential distribution for a distance metric. But the Spectral clustering process works only for similarity-based graphs. Why don’t the authors need to change the distance metric into a proximity one before Spectral Clustering?", "limitations": "The authors haven’t discussed the limitations in the main paper, but in the checklist instead.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The technical contribution is solid.\n2. The paper is well written and the presentation of proof ideas is clear.", "weaknesses": "The theoretical results seems to heavily depend on the property of wSBM, and are hardly generalized to much wider well-clustered graphs. It is possibly more interesting to figure out in what conditions the metric backbone is able to preserve communities in a given well-clustered graph. This is a much closer scenario to the observations in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JByP, \n\nWe thank you for your time in evaluating our submission and we are grateful for your comments. Please find below responses to the questions raised in your reviews. \n\n\n* Intuitively, keeping only the shortest paths and deleting everything else could destroy all structures unrelated to the shortest paths (such as the communities). This is indeed not the case on unweighted graphs, as the metric backbone does not remove any edge, hence the whole structure is preserved. However, community structure and shortest paths appear to act as two antagonists in graph sparsification, because removing edges that belong to a large number of shortest paths destroys these shortest paths (and graph connectivity) but can reveal communities as disconnected components of the sparsified graph (see ref. [17]). \n Moreover, when the metric backbone keeps only a small fraction of the edges of the original weighted graph, one could expect that the fractions of inter- and intra-community edges might be affected differently by the deletion of non-shortest path edges. Our work shows that this is not the case. \n\n* We acknowledge that spectral clustering is an umbrella term that encompasses various techniques involving the eigenstructure of a matrix characterizing a graph topology. Spectral clustering on the normalized Laplacian of the graph (which is the version implemented in popular libraries such as scikit-learn) requires weights to be similarities between node pairs and not distances. Because we are directly working with the graph adjacency matrix, we can handle weights being either similarities or distances. Nonetheless, we also acknowledge a typo in line 2 of Algorithm 1: the eigenvalues should be ordered in decreasing *absolute* value (note that this is already the case in the proof, see for example line 582). \n\n As a naive justification of why ordering in absolute value handles all cases, consider an unweighted SBM with two communities of the same size, and the probability of intra- (resp., inter-) community edge $p$ (resp., $q$). The eigenvalues of $\\mathbb E A$ are $n(p+q)/2$ (multiplicity 1), $n(p-q)/2$ (multiplicity 1) and $0$ (multiplicity $n-2$). When $p\\ne q$, we indeed have $|n(p+q)/2| > |n(p-q)/2| > 0$. But the relationship $n(p+q)/2 > n(p-q)/2 > 0$ does not hold if $p<q$. \n\n\n[17] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821–7826, 2002.", "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": "", "extra_scores": {}}, {"review_id": "3X5sGkjdwj", "reviewer": "Reviewer_Qqxh", "summary": "This work focuses on the metric backbone of weighted graphs, which is the union of all-pairs shortest paths. The study analyzes the metric backbone of a class of weighted random graphs with communities and formally proves the robustness of the community structure regarding the removal of non-metric backbone edges. An empirical comparison of graph sparsification techniques also confirms the theoretical finding and shows the metric backbone is an efficient sparsifier in the presence of communities.", "questions": "The authors may explain the drawbacks mentioned in the weakness section.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Provides a formal analysis and proof to explain the robustness of the community structure in the metric backbone of weighted random graphs with communities, which fills a knowledge gap in understanding this phenomenon.\n- Confirms the theoretical finding through an empirical comparison of graph sparsification techniques, providing practical evidence and validation.\n- Identifies the metric backbone as an efficient sparsifier in community-present networks, which has practical applications in graph processing and analysis in various fields where community structure in networks is relevant.", "weaknesses": "- This sentence needs to be clearer: \"This suggests that the metric backbone would dilute or destroy the community structure of the network. \" What does the dilution of community structure mean? The term \"preserve\" may also be defined formally or mathematically. \n- It claims that Algorithm 1 can recover the community structure from the metric backbone, but why the input is the original graph G?\n- Although in Section 3.1, the authors claim that it is feasible to have metric backbones on networks with millions and billions of nodes, the experiments are mostly for networks with thousands of nodes. Why? Can the running time be included in the experiment?\n- Comparison with other graph sparsification methods or other data sets may be added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Qqxh, \n\nWe thank you for your time in evaluating our submission and we are grateful for your comments. Please find below responses to the questions raised in your reviews. \n\n\n* By dilution of community structure, we mean that the metric backbone could delete a larger proportion of inter-community edges than intra-community edges. We plan to make these statements more precise in the final version (see our answer to Reviewer JByP as well). \n \n* The input of Algorithm 1 is a graph; however, Theorem 2 is stated for Algorithm 1 when the input is the metric backbone of a weighted SBM. We acknowledge that this is confusing. To clarify, we plan to modify the exposition of Algorithm 1 by adding a step to compute the metric backbone $G_{mb}$ of the input graph $G$, which is then followed by performing spectral clustering on $G_{mb}$.\n\n* We discuss the running time of our implementation in Appendix C due to page limitations, but we will move this discussion to the main text in the final version. In summary, computing the metric backbone is faster than spectral sparsification (where we used an external library), and running spectral clustering took significantly longer. \n\n* We compared the metric backbone with the threshold graph (a naive but still commonly used technique) and spectral sparsification (one of the most popular and efficient graph sparsification techniques). We also provide additional experiments in Appendix C. This comparison demonstrates that the metric backbone is a competitive sparsifier. The goal of this paper is to highlight that the metric backbone preserves community structure, which is why we limited the baselines for comparison. A comprehensive review and comparison of all graph sparsification techniques could be the topic of an interesting review paper but would go beyond the scope of the current paper.", "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": "", "extra_scores": {}}, {"review_id": "WSKWm8vc5r", "reviewer": "Reviewer_uKT3", "summary": "The authors analyze the metric backbone (= all the edges that are on  some shortest path) and it's relation to clustering.\n\nThey show that under weighted SBM model (with equal expected degree for all nodes), metric backbone\n1) the metric backbone approximately maintains the edge probabilities of blocks\n2) spectral clustering appplied to metric backbone recovers SBM.", "questions": "- Does the result hold for other sparsification methods?\n- Can Theorem 2 be stated with tmin < tmax?\n- is lambda in Remark 1 needed assumption?", "limitations": "The paper has a conclusions section but the authors do not discuss the limitations nor future work. Few sentences about the future steps would be helpful. Negative societal impact is not applicable for this paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The main contribution of the paper are the two theorems Theorem 1 and Theorem 2. Both are interesting and non-trivial results, providing connections between metric backbone and SBM models. Of these two theorems Theorem 2 is the more interesting one.", "weaknesses": "While theorems are interesting some assumptions seems to be very unrealistic. For example, Theorem 2 only works if tmin and tmax are the same. Is it possible to formulate it similarly as Theorem 1.\n\nMoreover, while the edge probabilities are proportionally retained, the same (probably) doesn't hold for weights, as I assume the min cost of the cheapest path from u to v goes to 0.\n\nDo these result also hold for other sparsification methods? such as simply deleting the edges independently with some given probability? I am guessing that Theorem 1 holds (and even stronger version) but I am not sure about Theorem 2.\n\nOther questions/remarks:\n\n- Assumption 1: p_n >> ...  what does >> means here exactly? that log n /  n in o(p_n)?\n- Remark 1: tmin and tmax assume that there is Lambda = lambda * 1 * 1^T. Is this the assumption also in Theorem 1 and Theorem 2?\n- The only difference in tmin and tmax is dmin and dmax. Why not use them directly in Theorem 1-2? Or, probably,  dmin / n and dmax / n since  those converge to a non-zero real number.\n- Leveraging the memoryless ... processes. Unclear sentence, please reword.\n- be defined after Equation 2.1. -> be as defined in Remark 1.\n- maintains the same proportion -> maintains approximately the same proportion", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer uKT3,\n\nWe thank you for your time in evaluating our submission and we are grateful for your comments.\nPlease find below responses to the questions raised in your reviews.\n\nAnswers to the main questions:\n\n* Other sparsification methods can maintain the community structure (as shown in Figure 1) but lose other important properties such as distances and even connectivity. In weighted SBM specifically, retaining edges independently with probability $p$ preserves the community structure, resulting in a weighted SBM with the same weight distribution but lower edge density $\\rho_n p$. Therefore, if $\\rho_n p = \\Omega( \\log n / n)$, this sparsification preserves the community structure (in the sense that one could derive an analogue of Theorems 1 and 2 for this naive sparsification) but it destroys other important graph properties and structures; and notably the shortest paths will \\emph{not} be preserved. \n In contrast, our work shows that preserving the shortest paths also preserves the community structure, even though it may sacrifice other properties, such as of course the edge weight distribution.\n \n* While we assume $\\tau_{\\min} = \\tau_{\\max}$, we note that this holds true in significant settings, such as the Planted Partition Model or general SBM with the same expected degree in each community (and $\\lambda_1 = \\cdots = \\lambda_k$). Upon closer examination of the proof of Theorem 2, we found that a weaker condition suffices, specifically $\\frac{\\tau_{\\min}}{\\tau_{\\max}} = \\Theta(1)$. This condition is automatically satisfied under Assumptions 1 and 2. \n The assumption $\\tau_{\\min} = \\tau_{\\max}$ is only used twice in the proof of Theorem 2: at lines 581 and 604; all other steps already allow $\\tau_{\\min}$ and $\\tau_{\\max}$ to differ. \n Removing strict equality in line 604 amounts to replace equation (B.6) by $\\sigma_k = \\frac{1}{8} \\frac{ \\tau_{\\min} }{ \\tau_{\\max} } \\tau \\mu \\log n$; if $\\tau_{\\min}$ and $\\tau_{\\max}$ are of the same order, this only changes the constant in front of the quantity $\\tau \\mu \\log n$ and does not affect the asymptotic scaling. \n Modifying line 581 is more involved, as we need to find the asymptotic scaling of the $k$-th largest eigenvalue of $\\mathbb E W^{mb}$ without explicitly knowing the values of the matrix $\\mathbb E W^{mb}$ (indeed, the upper and lower-bounds derived in Lemma 4 do not match when $\\tau_{\\min} \\ne \\tau_{\\max}$). Yet, this can be handled as well; we first write $\\mathbb E W_{ub}^{mb} = c_{ab}$ where $a$ and $b$ are the community of vertices $u$ and $v$. Next, we can process similarly as in the paragraph between lines 585 and 592 to derive a relationship analogous to equation (B.3). \n\n We appreciate you raising this point, as it strengthens our result, and we plan to modify the proof and statement of Theorem 2 accordingly. \n\n\nAnswers to the other remarks:\n\n* Indeed, the cost of the shortest path between $u$ and $v$ goes asymptotically to zero. \n \n* Remark 1 is here to relate $\\tau_{\\min}$ and $\\tau_{\\max}$ to the average degrees, in the particular case where $\\lambda_1 = \\cdots = \\lambda_k$. This provides a simple intuition of what these quantities mean.  However, restricting all $\\lambda_a$ to be equal is not needed in Theorems 1 and 2. When they are different, the relation between $\\tau_{\\min}$, $\\tau_{\\max}$ and the average degrees does not hold anymore, which is why we keep $\\tau_{\\min}$ and $\\tau_{\\max}$ in the main theorems.", "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": "", "extra_scores": {}}, {"review_id": "ytNJvZqpp9", "reviewer": "Reviewer_bM2e", "summary": "For weighted distance graphs, the metric backbone corresponds to the union of the shortest paths. This work shows that the community structure of a graph can still be detected from this backbone. This is surprising, since inter-community edges often serve as bridges between communities, so one would expect them to be overrepresented in the metric backbone.\nExperiments are performed to demonstrate this behavior on real-world networks.", "questions": "In line 132, you write \"Or as the uniform distribution\", but this seems like an odd and unnecessary statement. It makes sense that you want to point out the resemblance to the exponential distribution for taking minima, but it's unclear how the resemblance to the uniform is necessary.\n\nAt first, I was a bit confused with the fact that the inequalities given in Proposition 2.1 do not depend on a or b. Perhaps you could comment on that in the text. For example, you could comment on the fact that there will always be pairs whose distances fall below this interval, but that their fraction vanishes, and that one expects intra-community distances to be smaller.", "limitations": "The authors have addressed the limitations of the results.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to read.\n\nThe problem is interesting and the described theoretical behavior is surprising.\n\nThe overview given in Section 3.2 is helpful.", "weaknesses": "The experimental setup in Section 4 seems somewhat overcomplicated. Is this a standard method for converting weighted networks to distance networks? If so, refer to works where this methodology is studied.\nAlso, it is worth pointing out that if the proximity graph is generated from some weighted SBM, then this distance-conversion will introduce dependencies between the edge weights.\n\nSimilarly, the setup of Section 5 is also quite complicated without providing much motivation or justification. The obvious way of converting points to a distance network would be to consider the complete graph with weights corresponding to the Euclidean distance, but I understand that then every edge belongs to the metric backbone. Please explain why this complicated construction is needed.\nAlso, the label placement of Figure 2a is a bit inconvenient as it blocks the blue line.\n\nMoreover, while the results of Section 4 are interesting, the results of Section 5 are not convincing.\n\nMinor comments:\n* In the denominator of $p(u,v)$ given below line 251, you write $u\\in\\text{Nei}(u)\\wedge\\dots$ instead of $u\\in\\text{Nei}(u)\\wedge\\dots$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer bM2e,\n\nWe thank you for your time in evaluating our submission and we are grateful for your comments. Please find below responses to the questions raised in your reviews.\n\n * The methodology used in Section 4 is relatively standard, as we took it from previous papers on the metric backbone (see references [8] and [36] for example). We acknowledge that these transformations involve two non-linearities (the first one to transform the unweighted graph into a weighted graph, and the second one to transform the weights into distances). The theoretical Section 2 does not involve those transformations (as we consider weighted SBM where the weights are distances). \n \n* Using a Gaussian kernel to compute similarities between pairs of points is also standard. For example, this is exactly what is implemented for spectral clustering in scikit-learn (when one does not provide an adjacency matrix but a set $n$ points in $\\mathbb R^d$). \n\n* Indeed, the result of Proposition 2.1 does not depend on $a$ nor $b$. This is because we upper and lower-bound the cost of the shortest path between $u$ and $v$, and these bounds do not match (except in some particular settings). Deriving matching lower and upper bounds should lead to a value that depends on $a$ and $b$. We will add this comment in the text.\n\nWe also thank you for pointing out some typos and will correct them.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: There is general agreement among the reviewers that this submission is a technically solid contribution to network theory with high impact and good evaluations.  In particular, the authors prove a robustness result about the metric backbone of weighted random graphs that had been observed experimentally but so far without a proof.  They further provide additional experimental validation of their result.
Decision: Accept (poster)