Why the Metric Backbone Preserves Community Structure

Authors: maximilien  dreveton
charbel  chucri
matthias  grossglauser
patrick  thiran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 18:55:31

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.

Main paper: 
 introduction: 
 Graph clustering partitions the vertex set of a 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 [4, 30] .In many scenarios, the observed pairwise interactions are weighted. In a proximity graph, these weights measure the degree of similarity between edge endpoints (e.g., frequency of interaction in a social network), whereas in a distance graph, they measure dissimilarity instead (for example, the length of segments in a road network or travel times in a flight network). To avoid confusion, we refer to the weights in a distance graph as costs, so that the cost of a path will be naturally defined as the sum of the edge costs on this path. 1Distance graphs obtained from real-world data typically violate the triangle inequality. More precisely, the shortest distance between two vertices in the graph is not always equal to the cost of the direct edge, but rather equal to the cost of an indirect path via other vertices. For example, the least expensive 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-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 a 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 a well-known 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 a 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 is parameter-free and automatically preserves all properties linked to the shortest path structure. Moreover, all-pairs shortest paths can be efficiently computed [14, 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 a 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 sparsification should thin out intra-community edges more than inter-community edges, thereby diluting the community structure. The central contribution of this paper is to show that this intuition is wrong.To do so, we formally characterize the metric backbone of a weighted stochastic block model (wSBM). We assume that the vertices are separated into k blocks (also referred to as clusters or communities). An edge between two vertices belonging to blocks a and b is present with probability p ab and is independent of the presence or absence of other edges. This edge, if present, has a weight sampled from a distribution with cdf F ab , and this weight represents the cost of traveling through this edge. We denote by p mb ab the probability that an edge between a vertex in block a and a vertex in block b is present in the backbone. 3 Under loose assumptions on the costs distributions F ab and on the probabilities p ab , we show that p mb ab /p mb cd = (1 + o(1))p ab /p cd for every a, b, c, d ∈ [k]. This shows that the metric 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 a Euclidean space, typically by a kernel similarity measure between q-nearest neighbors (q-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 q often impacts the clustering performance. By investigating the metric backbone of q-NN graphs, we notice that it makes clustering results more robust against the value of q. Consequently, leveraging graph sparsification alongside q-NN facilitates graph construction.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 6.We provide the code used for the experiments: https://github.com/ Charbel-11/Why-the-Metric-Backbone-Preserves-Community-Structure Notations The notation 1 n denotes the vector of size n × 1 whose entries are all equal to one. For any vector π ∈ R n and any matrix B ∈ R n×m , we denote by π min = min a∈[n] π a and B min = min a,b B ab , and similarly for π max and B max . 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 T is the transpose of a matrix A. For a vector π, we denote diag(π) 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 Exp(λ), respectively. The uniform distribution over an interval [a, b] is denoted Unif(a, b). Finally, given a cumulative distribution function F , we write X ∼ F for a random variable X sampled from F , i.e., P(X ≤ 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 → ∞. 
definitions and main notations: 
 Let G = (V, E, c) be an undirected weighted graph, where V = [n] is the set of vertices, E ⊆ V × V is the set of undirected edges, and c :E → R + is the cost function.The cost of a path (u 1 , • • • , u p ) is naturally defined as p-1q=1 c(u q , u q+1 ), and a shortest path between u and v is a path of minimal cost starting from vertex u and finishing at vertex v. We define the metric backbone as the union of all shortest paths of G. Definition 1. The metric backbone of a weighted graph G = (V, E, c) where c represents the edge cost is the subgraph G mb = (V, E mb , c mb ) of G, where E mb ⊆ E is such that e ∈ E mb if and only if e belongs to a shortest path from two vertices in G, and c mb :E mb → R + ; e → c(e) is the restriction of c to E mb .We investigate the structure of the metric backbone of weighted random graphs with community structure. We generate these graphs as follows. Each vertex u ∈ [n] is randomly assigned to the cluster a ∈ [k] with probability π a . We denote by z u ∈ [k] the cluster of vertex u. Conditioned on z u and z v , an edge (u, v) is present with probability p zuzv , independently of the presence or absence of other edges. If an edge (u, v) is present, it is assigned a cost c(u, v). The cost c(u, v) is sampled from F zuzv where F = (F ab ) 1≤a,b≤k denotes a collection of cumulative distribution functions such that F ab = F ba . This defines the weighted stochastic block model, and we denote(z, G) ∼ wSBM(n, π, p, F ) with G = ([n], E, c), z ∈ [k] n and P (z) = n u=1 π zu , P (E | z) = 1≤u<v≤n p 1{{u,v}∈E} zuzv (1 -p zuzv ) 1{{u,v}̸ ∈E} , P (c | E, z) = {u,v}∈E P (c(u, v) | z u , z v ) , and c(u, v) | z u = a, z v = b is sampled from F ab .The wSBM is a direct extension of the standard (non-weighted) 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 as a low clustering coefficient, the SBM is analytically tractable and is a useful model for inference purposes [32] .Throughout this paper, we will make the following assumptions.Assumption 1 (Asymptotic scaling). The edge probabilities p ab between blocks a and b can depend on n, such that p ab = B ab ρ n with ρ n = ω(n -1 log n) and B ab is independent of n. Furthermore, the number of communities k, the matrix B, the probabilities π a and the cdf F ab are all fixed (independent of n). We also assume π min > 0 and B min > 0.To rule out some issues, such as edges with a zero cost, 4 we also assume that the probability distributions of the costs have no mass at 0. More precisely, we require that the cumulative distribution functions F ab verify F ab (0) = 0 and F ′ ab (0) = λ ab > 0, where F ′ denotes the derivative of F (i.e., the pdf). The first condition ensures that the distribution has support R + and no mass at 0, and the second ensures that, around a neighborhood of 0, F ab behaves as the exponential distribution Exp(λ ab ) (or as the uniform distribution Unif([0, λ -1 ab ]). Assumption 2 (Condition on the cost distributions). The costs are sampled from continuous distributions, and there exists Λ = (λ ab ) a,b with λ ab > 0 such that F ab (0) = 0 and F ′ ab (0) = λ ab .We define the following matrixEQUATIONwhere B and Λ are defined in Assumptions 1 and 2. Finally, we denote by τ min and τ max the minimum and maximum entries of the vector τ = T 1 k .Remark 1. Assume that Λ = λ1 k 1 T k with λ > 0. We notice that τ a = λ b π b B ab . Denote by d = ( d1 , • • • , dk ) the vector whose a-entry da is the expected degree of a vertex in community a. We have da = n b π b p ab . Then τ min = λ dmin (nρ n ) -1 and τ max = λ dmax (nρ n ) -1 , where dmin and dmax are the minimum and maximum entries of d.Given a path (u 1 , • • • , u p ), recall that its cost is p-1 q=1 c(u q , u q+1 ), and the hop count is the number of edges composing the path (that is, the hop count of (u1 , • • • , u p ) is p -1).For two vertices u, v ∈ V , we denote by C(u, v) the cost of the shortest path from u to v. 5 The following proposition provides asymptotics for the cost of shortest paths in wSBMs.Proposition 1. Let (z, G) ∼ wSBM(n, π, p, F ). Suppose that Assumptions 1 and 2 hold and let τ min and τ max be defined following Equation (2.1). Then, for two vertices u and v chosen uniformly at random in blocks a and b, respectively. We have whp(τ max ) -1 ≤ nρ n log n C(u, v) ≤ (τ min ) -1 .To prove Proposition 1, 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 u and v, respectively. Using the memoryless property of the exponential distribution, we analyze two first passage percolation (FPP) processes, originating from vertex u and v, respectively. Each FPP explores the nearest neighbors of its starting vertex until it reaches q neighbors. As long as q = o( √ n), 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 u to its q-nearest neighbor and of (ii) the cost of the shortest path from v to its q-nearest neighbor. On the contrary, when q = ω( √ n), the two FPPs intersect, revealing a path from u to v, and the cost of this path upper-bounds the cost C(u, 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 to the shortest paths have very small costs. Moreover, Assumption 2 yields that the weight distributions behave as an exponential distribution in a neighborhood of 0. 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 2 is verified. The proof of Proposition 1 is provided in Section A.Let (z, G) ∼ wSBM(n, π, p, F ) and denote by G mb the metric backbone of G. Choose two vertices u and v uniformly at random, and notice that the probability that the edge (u, v) is present in G mb depends only on z u and z v , and not on z w for w / ∈ {u, v}. Denote by p mb ab the probability that an edge between a vertex in community a and a vertex in community b appears in the metric backbone, i.e.,p mb ab = P (u, v) ∈ G mb | z u = a, z v = b .The following theorem shows that the ratio B ab = p 0 if a = b, q 0 otherwise,where p 0 and q 0 are constant. Assume that Λ = λ1 k 1 T k with λ > 0. Using Remark 1, we have τ min = τ max = λk -1 (p 0 + (k -1)q 0 ), and Theorem 1 states thatp mb = (1 + o(1)) kp 0 p 0 + (k -1)q 0 log n n and q mb = (1 + o(1)) kq 0 p 0 + (k -1)q 0 log n n .In particular, p mb q mb = (1 + o(1)) p0 q0 . Example 2. Consider a stochastic block model with edge probabilities p ab = B ab ρ n such that the vertices of different communities have the same expected degree d. If Λ = λ1 k 1 T k , thenp mb ab = (1 + o(1))B ab d log n n .In this section, we prove that a spectral algorithm on the (weighted) adjacency matrix of the metric backbone of a wSBM asymptotically recovers the clusters whp. Given an estimate ẑ ∈ [k] n of the clusters z ∈ [k] n , we define the loss asloss(z, ẑ) = 1 n inf σ∈Sym(k) Ham (z, σ • ẑ) ,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 backboneInput: Graph G, number of clusters k Output: Predicted community memberships ẑ ∈ [k] n Denote W mb ∈ R n×n + the weighted adjacency matrix of the metric backbone G mb of G Let W mb = n i=1 σ i u i u Ti be an eigen-decomposition of W mb , with eigenvalues ordered in decreasing absolute value (|σ1 | ≥ • • • ≥ |σ n |) and eigenvectors u 1 , • • • , u n ∈ R n Denote U = [u 1 , • • • , u k ] ∈ R n×k and Σ = diag(σ 1 , • • • , σ k ) Let ẑ ∈ [k] n be a (1 + ϵ)-approximate solution of k-means performed on the rows of U ∈ R n×kThe 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. Theorem 2. Let (z, G) ∼ wSBM(n, π, p, F ) and suppose that Assumptions 1 and 2 hold. Let µ be the minimal absolute eigenvalue of the matrix T defined in (2.1). Moreover, assume that τ max = τ min and µ ̸ = 0. Then, the output ẑ of Algorithm 1 on G verifies whploss(z, ẑ) = O 1 µ 2 log n .We prove Theorem 2 in Appendix B.2. We saw in Example 1 and 2 that the condition τ max = τ min is verified in several important settings. The additional assumption µ ̸ = 0 (equivalent to T being invertible) also often holds: in the planted partition model of Example 1, T is invertible if p 0 ̸ = q 0 . 
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.Computing the metric backbone requires solving the All Pairs Shortest Path (APSP) problem, a classic and fundamental problem in computer science. Simply running Dijkstra's algorithm on each vertex of the graph solves the APSP in O(nm + n 2 log n) worst-case time, where m = |E| is the number of edges in the original graph [14] , whereas [29] proposed an algorithm running in O(nm ′ + n 2 log n) worst-case time, where m ′ is the number of edges in the metric backbone. APSP has also been studied in weighted random graphs in which the weights are independent and identically distributed [20, 16] .In particular, the APSP can be solved in O(n 2 ) time with high probability on complete weighted graphs whose weights are drawn independently and uniformly at random from [0, 1] [33].However, practical implementations of APSP can 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 to 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.To study the metric backbone theoretically, we need to understand the structure of the shortest path between vertices in a 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 on the complete graph with iid weights. This was later generalized to Erdős-Rényi graphs and configuration models (see, for example, [28, 12] and references therein).Closer to our setting, [25] 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 Exp(λ)-distributed, [25] established a 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 nρn log n C(u, v) converges in probability to τ -1 , where τ is the Perron-Frobenius eigenvalue of λB diag(π).The novelty of our work is two-fold. First, we allow different 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 a path between two vertices, u and v, chosen uniformly at random among vertices in block a and in block b, respectively. This differs from previous work (and, in particular, [25] ) in which vertices u and v are selected uniformly at random among all vertices. As a result, even for a single cost distribution, Proposition 1 cannot be obtained directly from [25, Theorem 1.2] . This difference is key, as this proposition is required to establish Theorem 1.The closest result to Theorem 1 appearing in the literature is [39, Corollary 1] ; it establishes a formula for the probability p mb uv that an edge between two vertices u and v exists in the metric backbone of a random graph whose edge costs are iid. This previous work does not focus on community structure, so the costs are sampled from a single distribution. More importantly, the expression of p mb uv given by [39, Theorem 2 and Corollary 1] is mainly of theoretical interest (and we use it in the proof of Theorem 1). Indeed, understanding the asymptotic behavior of p mb uv requires a complete analysis of the cost C(u, v) of the shortest path between u and v. [39] propose such an analysis only in one simple scenario (namely, a complete graph with iid exponentially distributed costs). 
experimental results: 
 In this section, we test whether the metric backbone preserves a graph community structure in various real networks for which a ground truth community structure is known (see Table 2 in Appendix C.1 for an 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, we need to 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 v, i.e.,p(u, v) = w∈Nei(u)∩Nei(v) min{s(u, w), s(v, w)} u∈Nei(u)∪Nei(v) max{s(u, w), s(v, w)} ,where Nei(u) = {w ∈ 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) = 1 for all e ∈ E), we simply recover the Jaccard index|Nei(u)∩Nei(v)| |Nei(u)∪Nei(v)| .We note that other choices for normalization could have been made, such as the Adamic-Adar index [2] . We refer to [10] 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, c) where c :E → R + is such that ∀e ∈ E : c(e) = 1 p(e) -1.This is the simplest and most commonly used method for converting a similarity to a distance [36] .We then compute the set E mb of metric edges of the distance graph D, and let G mb = (V, E mb , p mb ) where p mb : E mb → [0, 1]; e → p(e) is the restriction of p to E mb .We will also consider the two following sparsifications (with the corresponding restrictions of c to the sparsified edge sets) to compare the resulting community structure:• the threshold graph G θ = (V, E θ , p θ ), where an edge e ∈ E is kept in E θ iff p(e) ≥ θ;• the graph G ss = (V, E ss , p ss ) obtained by spectral sparsification on G. We use the Spielman-Srivastava sparsification [37] , 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:|E mb | = |E θ | = |E ss |.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 G mb , G θ , and G ss , we run a graph clustering algorithm to obtain the respective predicted clusters ẑ, ẑmb , ẑθ and ẑss . We show, in Figure 1 , the adjusted Rand index6 (ARI) obtained between the ground truth communities and the predicted clusters for three widely used graph clustering algorithms: Bayesian algorithm [31] , Leiden algorithm [38] and spectral clustering [40] . We use the graph-tool implementation for the Bayesian algorithm, with an exponential prior for the weight distributions. The Leiden algorithm is implemented at https://github.com/vtraag/leidenalg. For spectral clustering, we assume that the algorithm knows the correct number of clusters in advance, and we use the implementation from scikit-learn. 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 backbone and the threshold subgraph of the Primary school data set in Figure 2 . We observe, in Figure 2a , 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 1 . 2a ) and after thresholding (Figure 2b ), 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 in the threshold graph, but not in the metric backbone, are highlighted in blue. 
application to graph construction using q-nn: 
 In a large number of machine-learning tasks, data does not originally come from a graph structure, but instead from a cloud of points x 1 , • • • , x n where each x u belongs to a metric space (say R d for simplicity). The goal of graph construction is to discover a proximity graph G = ([n], E, p) from the original data points. Graph construction is commonly done through the q-nearest neighbors (q-NN). Given a similarity function sim : R d × R d → R + that quantifies the resemblance between two data points, we define the set N (u, q) of q-nearest neighbors of u ∈ [n]. More precisely, N (u, q) is the subset of [n]\{u} with cardinality q such that for all v ∈ N (u, q) and for all w ̸ ∈ N (u, q) we have sim(x u , x v ) ≥ sim(x u , x w ).The edge set E is composed of all pairs of vertices (u, v) such that u ∈ N (v, q) or v ∈ N (u, q),8 and the proximity p uv associated with the edge (u, v) is (s uv + s vu )/2, wheres uv = sim(x u , x v ) if v ∈ N (u, q), 0 otherwise.In the following, we use the Gaussian kernel similarity sim(x u , x v ) = exp -∥xu-xv∥ 2 d 2 K (xu), where d K (x i ) is the Euclidean distance between x u and its q-NN. In Appendix C.2, we provide results using another similarity measure.We investigate the effect of graph sparsification on graphs built by q-NN. We sample n = 10000 images from MNIST [26] and FashionMNIST [42] , and use the full HAR [3] dataset (n = 10299). From the sampled data points, we build the q-NN graph G q , as well as its metric backbone G mb q and its spectral sparsification G ss q . We then compare the performance of two clustering algorithms, spectral clustering and Poisson learning. Poisson learning is 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 in the Appendix.We compare the ARI of clustering algorithms on q-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 4 (for Poisson-learning). Unlike the spectral sparsifier, the metric backbone retains a 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 a higher distance (cost), which are therefore more likely to be non-metric. Finally, we compare in Table 1 the ARI obtained on the q-nearest neighbor graph using q = 10 (as it is a common default choice) with the metric backbone graph of a q-nearest neighbor graph with q = √ n/2. Moreover, we compute an approximation of the metric backbone by sampling uniformly at random 2 log n vertices and taking the union of the 2 log n shortest-path trees rooted at each one of them instead of the union of all n shortest-path trees. This produces a graph Gmb √ n/2 whose edge set is a subset of the edges of the true metric backbone G mb √ n/2 . We observe that Gmb √ n/2 retains the community structure albeit being typically twice sparser than the 10-nearest neighbor graph G 10 .Data set G 10 Gmb √ n/2The performance of clustering algorithms on the q-nearest neighbor graph G q tends to decrease when q increases. Indeed, a larger q 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 G q are insufficient to recover the communities (as attested by the poor performance of spectral clustering for large values of q in Figures 3a and 8a ). However, when the performance of spectral clustering on G q remains stable as q is varied, so does the performance of spectral clustering on the spectral sparsified graph G ss q (as seen in Figures 3b and 8b ). In contrast, the metric backbone preserves the shortest paths rather than spectral properties. Because the shortest paths are robust to the addition of numerous low-similarity edges, 9 the performance of clustering algorithms on the metric backbone G mb q remains stable when q increases. This holds regardless of whether the performance on the original graph G q is stable or decreases with increasing q. Finally, sparsified graphs obtained by metric sparsification are more consistent across different values of q than those obtained via spectral sparsification. For instance, on the MNIST dataset with Gaussian kernel similarity, the metric backbone G mb 30 and G mb 40 have both approximately 70k edges, with 64k edges in common. In contrast, the spectrally sparsified graphs G ss 30 and G ss 40 , also with around 70k edges each, share only 22k edges in common. 
conclusion: 
 The metric backbone plays a crucial role in preserving several essential properties of a network. Notably, the metric backbone effectively preserves the network community structure, although many inter-community edges belong to 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 a preprocessing step for graph construction employing q-nearest neighbors, alleviating the sensitivity associated with selecting the hyperparameter q and producing sparser graphs. 9 Consider, for example, an adversary adding an arbitrary number of edges with a cost of ω log n nρn in a wSBM. Proposition 1 proves that this addition does not affect the metric backbone, as none of these high-cost edges will be included in any shortest path. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Details about compute resources are included in the appendix C.Guidelines:• The answer NA means that the paper does not 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: Let us set up some notations before proving Proposition 1. We let (z, G) ∼ wSBM(n, π, p, f ) where the model parameters verify Assumptions 1 and 2, and we denote by c and c the cost and the extended cost associated with G, respectively. We let Γ 1 , • • • , Γ k be the k communities, i.e., Γ a = {w ∈ [n] : z w = a} , and we denote by n 1 , • • • , n k their respective sizes, i.e., n a = |Γ a |. As k = Θ(1), the concentration of multinomial distributions ensures that n a = (1 + o(1))π a n whp.Proof of Proposition 1 for exponentially distributed costs. We firstly assume that F ab ∼ Exp(λ ab ) with λ ab > 0. It is immediate to notice that (f ab ) ab verify Assumption 2.Let u, v be two vertices chosen uniformly at random in Γ a and Γ b respectively, so that z u = a and z v = b. To explore the neighborhood of vertex u, we consider a first passage percolation (FPP) on G starting from u. More precisely, for any t > 0, we denote by B(u, t) = {w ∈ V : C(u, w) ≤ t} the set of vertices within a cost t of u, and byC u (q) = min {t ≥ 0 : |B(u, t)| ≥ q + 1} ,the cost going from u to its q-th nearest neighbor (with the convention that min ∅ = ∞). In particular, B(u, C u (q)) is the set of the q nearest neighbors of u. Let U (q) = (U 1 (q), • • • , U k (q)) be the collection of sets such that U ℓ (q) is the set of vertices that are in the q nearest neighborhood of u and in community ℓ, i.e.,U ℓ (q) = B(u, C u (q)) ∩ Γ ℓ .Finally, we denote by S(u, q) the matrix whose entry S ℓℓ ′ (u, q) is equal to the number of edges going fromU ℓ (q) to Γ ℓ ′ \U ℓ ′ (q).The outline of the proof is as follows. In a first step (i), we study the FPP starting from vertex u to obtain upper and lower bounds on the cost C u ( √ n log n) for going from u to its √ n log n-nearest neighbor 10 . More precisely, we will establish thatnρ n log n C u n log n ≤ 1 + o(1) 2τ min (A.1)holds whp. By symmetry, the same upper bound also holds for C v ( √ n log n).Next, we will show in step (ii) that B(u, √ n log n) ∩ B(v, √ n log n) ̸ = ∅ whp. Together with the upper bound (A.1), we can then upper bound the cost C(u, v) of the shortest path from u to v. Indeed, let w 1 ∈ B(u, √ n log n) ∩ B(v, √ n log n) (such a w 1 exists whp by step (ii)), and consider the path P = u → w 1 → v, where u → w 1 and w 1 → v denote the shortest path from u to w 1 and from w 1 to v, respectively. Because the cost C(u, v) of the shortest path from u to v is upper-bounded by the cost of the path P, we have whpC(u, v) ≤ C(u, w 1 ) + C(w 1 , v) ≤ 1 + o(1) τ min log n nρ n ,where the second inequality holds becausew 1 ∈ B(u, √ n log n) ∩ B(v, √ n log n), which enables to use the upper bound (A.1). This establishes the desired upper bound on C(u, v).To lower-bound C(u, v), we will establish that1 + o(1) 2τ max ≤ nρ n log n C u n log n (A.2)holds whp. Again, a similar bound holds for C v n/ log n by symmetry.Finally, we will show in step (iii) that B u, C u ( n/ log n) ∩ B v, C v ( n/ log n = ∅ whp.Combining this with the lower bound (A.2), we conclude then that whpC(u, v) ≥ 1 + o(1) τ max log n nρ n .(i) Upper and lower bounds on C u ( n/ log n) and C u ( √ n log n). In this paragraph, we will establish (A.1) and (A.2).A key property of the FPP is to notice that, conditioned on S(u, •) = (S(u, 1), • • • , S(u, n)), the random numbers C u (q + 1) -C u (q) are independent and exponentially distributed, such thatC u (q + 1) -C u (q) | S(u, •) ∼ Exp   ℓ,ℓ ′ λ ℓℓ ′ S ℓℓ ′ (u, q)   . (A.3)Indeed, C u (q + 1) -C u (q) is the difference in the cost of traveling from u to its (q + 1)-th nearestneighbor minus the cost from u and its q-th nearest neighbor. In other words,C u (q + 1) -C u (q) | S(u, •) = min w∈Uc(q) w ′ ∈Γ c ′ \U c ′ (q) c ww ′ , (A.4) with c ww ′ ∼ Exp(λ cc ′ ). Statement (A.3) follows because min {Exp(λ), Exp(µ)} ∼ Exp(λ + µ).Let q ≤ √ n log n. The number of edges S ℓℓ ′ (u, q) between the sets U ℓ (q) and Γ ℓ ′ \U ℓ ′ (q) is binomially distributed such thatS ℓℓ ′ (u, q) ∼ Bin (|U ℓ (q)| × |Γ ℓ ′ \U ℓ ′ (q)| , p cc ′ ) .Γ ℓ ′ is n ℓ ′ = Θ(n) and the number of vertices in |U ℓ ′ (q)| verifies |U ℓ ′ (q)| ≤ q ≪ n. Therefore, E [S ℓℓ ′ (u, q)] = |U ℓ (q)| (n ℓ ′ -|U ℓ ′ (q)|) p ℓℓ ′ = (1 + o(1)) |U ℓ (q)| n ℓ ′ p ℓℓ ′ .Hence E [S ℓℓ ′ (u, q)] ≫ 1, and the concentration of binomial distributions ensure that whpS ℓℓ ′ (u, q) = (1 + o(1)) |U ℓ (q)| (n ℓ ′ -|U ℓ (q)|)p ℓℓ ′ = (1 + o(1)) |U ℓ (q)| n ℓ ′ p ℓℓ ′ . (A.5) Therefore, using n ℓ ′ = (1 + o(1))π ℓ ′ n and p ℓℓ ′ = B ℓℓ ′ ρ n , we have from (A.4) E [C u (q + 1) -C u (q) | S(u, •)] = 1 + o(1) ℓ |U ℓ (q)| ℓ ′ n ℓ ′ λ ℓℓ ′ p ℓℓ ′ = 1 + o(1) nρ n ℓ |U ℓ (q)| ℓ ′ π ℓ ′ λ ℓℓ ′ B ℓℓ ′ .We notice that l |U ℓ (q)| ℓ ′ π ℓ ′ λ ℓℓ ′ B ℓℓ ′ = U T (q)T 1 k where T = (Λ⊙B) diag(π) is the operator defined in (2.1). Then, using ℓ |U ℓ (q)| = q, we haveτ min q ≤ ℓ |U ℓ (q)| ℓ ′ π ℓ ′ λ ℓℓ ′ B ℓℓ ′ ≤ τ max q. (A.6) Therefore, 1 + o(1) nρ n τ max q ≤ E [C u (q + 1) -C u (q) | S(u, •)] ≤ 1 + o(1) nρ n τ min q . (A.7)This bound is uniform in S(u, •). Thus, using the total law of probability and summing over all 1 ≤ q ≤ √ n log n leads to1 + o(1) 2τ max ≤ nρ n log n EC u ( n log n) ≤ 1 + o(1) 2τ min , (A.8)where we used√ n log n q=1 q -1 = 2 -1 (log n + log log n) + Θ(1).Let us now upper-bound the variance of C u √ n log n . By the law of total variance, we haveVar C u ( n log n) = E Var C u ( n log n) | S(u, •) + Var E C u ( n log n) | S(u, •) . (A.9)The first term on the right-hand side of (A.9) can be upper bounded by proceeding similarly as for the expectation. Indeed, we haveVar [C u (q + 1) -C u (q) | S(u, •)] ≤ 1 + o(1) n 2 ρ 2 n τ 2 min q 2 ,and the independence of C u (q + 1) -C u (q) conditioned on S(u, •) leads toVar C u ( n log n) | S(u, •) = √ n log n-1 q=1 Var (C u (q + 1) -C u (q) | S(u, •)) ≤ 1 + o(1) n 2 ρ 2 n τ 2 min √ n log n q=1 q -2 ≤ 1 + o(1) n 2 ρ 2 n τ 2 min π 2 6 . (A.10)To upper bound the second term on the right-hand side of (A.9), we notice thatVar E C u ( n log n) | S(u, •) = Var   √ n log n-1 q=1 E [C u (q + 1) -C u (q) | S(u, •)]   = √ n log n-1 q=1 Var [E [C u (q + 1) -C u (q) | S(u, •)]] ,where the first line holds by the linearity of the conditional expectation, and the second one by the independence of C u (q + 1) -C u (q) conditioned on S(u, •). Moreover, recall that Var(X) ≤ (b -a) 2 /4 if a ≤ X ≤ b. Hence, using the upper and lower bound on C u (q + 1) -C u (q) obtained in (A.7) leads toEQUATIONEQUATION1 nρ n τ min q 2 ,and therefore EQUATION( √ n log n) = o E C u ( √ n log n) 2, and therefore an application of Chebyshev's inequality ensures that1 + o(1) 2τ max ≤ nρ n log n C u n log n ≤ 1 + o(1)2τ min with high probability. Likewise, by symmetry for a FPP starting from v instead of u, we find1 + o(1) 2τ max ≤ nρ n log n C v n log n ≤ 1 + o(1) 2τ min .This establishes (A.1). Moreover, we establish (A.2) by doing a slight modification of this proof. More precisely, we sum over all q ≤ n/ log n instead of all q ≤ √ n log n in step (A.8). We obtain the same bound as in (A.8) because√ n/ log n q=1 q -1 = 2 -1 (log n -log log n) + Θ(1). (ii) B(u, C u ( √ n log n)) ∩ B(v, C v ( √ n log n)) ̸ = ∅ whp.For ease of notations, let us shorten byB u = B(u, C u ( √ n log n))the set of the √ n log n nearest neighbours of u and by B v (q) the set of the q-nearest neighbours of v. We also denote by w q the q-nearest neighbor of v. A key property is that the two FPPs (starting from vertex u and starting from vertex v) are independent of each other as long as 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 v without intersecting with B u , i.e.,Q = min {q ∈ [n] : B u ∩ B v (q) ̸ = ∅} .We now show that P (Q > q) = o(1) whenever q ≫ n/ log n, which implies thatB u ∩ B v ( √ n log n) ̸ = ∅. Using [6, Lemma B.1], we have P (Q > m) = E m q=1 Q (q) (Q > q | Q > q -1) , (A.13)where Q (q) denotes the conditional distribution given B u and B v (q). We further notice thatQ (q) (Q > q | Q > q -1) = 1 -Q (q) (Q = q | Q > q -1) ,and that the event {Q > q -1} is equivalent to the event{w 1 ̸ ∈ B u , • • • , w q-1 ̸ ∈ B u }, i.e., the FPP starting from v has not yet collided with the one starting from u. 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 (q) (Q = q | Q > q -1) = ℓ∈[k] P (w q ∈ B u | w q ∈ Γ ℓ , Q > q -1) P (w q ∈ Γ ℓ ) = ℓ∈[k] |B u ∩ Γ ℓ | |Γ ℓ | P (w q ∈ Γ ℓ ) . Because ℓ∈[k] |B u ∩ Γ ℓ | = √ n log n, we have that 11 max ℓ |B u ∩ Γ ℓ | ≥ k -1 √ n log n. Moreover, |Γ ℓ | ≤ (1 + o(1))π max n whp and ℓ∈[k] P (w q ∈ Γ ℓ ) = 1. Therefore, Q (q) (Q = q | Q > q -1) ≥ max ℓ∈[k] |B u ∩ Γ ℓ | min ℓ∈[k] |Γ ℓ | ℓ∈[k] P (w q ∈ Γ ℓ ) ≥ 1 + o(1) π max log n n .Going back to (A.13), this implies thatP (Q > m) ≤ 1 - 1 + o(1) π max log n n m ,which indeed goes to 0 when m ≫ n/ log n.(iii) B(u, C u ( n/ log n)) ∩ B(v, C v ( n/ log n)) = ∅ whp.We proceed similarly to step (ii) by considering the FPP starting from v, and denote by w q the q-nearest neighbor of v. For ease of notations, let us denote in this paragraphB u = B u, C u n/ log n and B v (q) = B (v, C v (q)).Note that, in contrast to step (ii), we now look at the FPP up to step n/ log n instead of the FPP up to step √ n log n. We defineQ = min{q ∈ [n] : B u ∩ B v (q) ̸ = ∅}.We haveP (Q = q) = P (w q ∈ B u | Q > q -1) P (Q > q -1) = ℓ∈[k] |B u ∩ Γ ℓ | |Γ ℓ | P (w q ∈ Γ ℓ | Q > q -1) P (Q > q -1) ,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 |Γ ℓ | ≥ (1 + o(1))π min n and |B u ∩ Γ ℓ | ≤ |B u | ≤ n/ log n leads to P (Q = q) ≤ 1 π min 1 + o(1) √ n log n .Therefore,P (B u ∩ B v ̸ = ∅) = √ n/ log n q=1 P (Q = q) ≤ 1 + o(1) π min log n = o(1).This concludes the proof of Proposition 1 when F ab ∼ Exp(λ ab ).Proof of Proposition 1 with non-exponentially distributed costs. In this section, the probability densities F ab 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, π, F ) into a graph G exp = (V, E, c exp ) with the same vertices and edge set but where the costs c exp are obtained from F and are exponentially distributed so that G exp has the same distribution as a wSBM (n, π, (Exp(λ ab )) ab ). We will then show that the shortest paths in G exp and G are the same.Let f ab be the density function of the cdf F ab , and remember that λ ab = F ′ ab (0). Let F -1 ab be the generalized inverse function 12 of F ab . By regularity of F ab (Assumption 2), we have lim t→0 F ab (t)/t = λ ab and thus lim t→0 F -1 ab (t)/t = λ -1 ab . We also denote by g ab (x) = λ ab e -λ ab x and by G ab (x) = 1 -e -λ ab x the density and cumulative distribution functions of Exp(λ ab ).We first show that Proposition 1 holds for uniformly distributed edge weights, i.e., when f ab (x) = λ ab 1(x ∈ [0, λ -1 ab ]). Denote by F ab the cdf associated to f ab , and let (z, G) ∼ wSBM(n, π, p, F ) where G = (V, E, c). We construct the graph G exp = (V, E, c exp ) such that for all (w, w ′ ) ∈ E with z w = ℓ and z w ′ = ℓ ′ we have c exp (w, w ′ ) = G -1 ℓℓ ′ (λ ℓℓ ′ c(w, w ′ )). Note that the (unweighted) edges of G and G exp are the same, only the costs c and c exp differ. Since λ ℓℓ ′ c(w, w ′ ) ∼ Unif(0, 1) we have c exp (w, w ′ ) ∼ Exp(λ ℓℓ ′ ). In particular, G exp has the same distribution of a weighted SBM whose costs are exponentially distributed, i.e., (z, G exp ) ∼ wSBM(n, π, p, G) with G = (G ab ) a,b .Let P(u, v) (resp., P exp (u, v)) be the shortest path from u to v in G (resp., in G exp ), and denote by C(u, v) (resp., by C exp (u, v)) its cost. We know from Section A.1 that C exp (u, v) = Θ log n nρn whp.Suppose that the edge (w, w ′ ) ∈ E belongs to P exp (u, v). From c exp (w, w ′ ) ≤ C exp (u, v) we notice that c exp (w, w ′ ) = O( log n nρn ), and hence by Assumption 1 we have c exp (w, w ′ ) = o(1). Moreover, by definition of c exp we havec(w, w ′ ) c exp (w, w ′ ) = 1 λ ℓℓ ′ G ℓℓ ′ (c exp (w, w ′ )) c exp (w, w ′ ) .Recall that lim t→0 G ℓℓ ′ (t)/t = λ ℓℓ ′ . Thus, we have for any ϵ > 0 and for n large enough, 1 -ϵ < c(w,w ′ ) cexp(w,w ′ ) < 1 + ϵ. This holds for any edge (w, w ′ ) belonging to P exp (u, v). Therefore, the sum of the costs c(w, w ′ ) over P exp (u, v) is at most (1 + ϵ)C exp (u, v), and henceC(u, v) < (1 + ϵ)C exp (u, v). (A.14)Similarly, if (w, w ′ ) ∈ P(u, v), then the upper bound (A.14) together with Assumption 1 imply that C(u, v) = o(1). This in turn implies c(w, w ′ ) = o(1) and hence 1 -ϵ < c(w,w ′ ) cexp(w,w ′ ) < 1 + ϵ. Thus, summing over all edges in P(u, v) leads to(1 -ϵ)C exp (u, v) < C(u, v).(A.15)Combining (A.14) with (A.15) shows that Proposition 1 holds for uniformly distributed edges weights.Finally, if the costs c(w, w ′ ) are sampled from general distributions F ab verifying Assumption 2, then we construct the graphG unif = (V, E, c unif ) where c unif (u, v) = λ -1 zuzv F zuzv (c(u, v)). We have c unif (u, v) ∼ Unif([0, λ -1zuzv ]) and we apply the previous reasoning (by replacing the exponential distributions with uniform distributions) to conclude. -log 1 -p ab F ab 1 + o(1) τ max log n nρ n ≤ p mb ab ≤ -log 1 -p ab F ab 1 + o(1) τ min log n nρ n .We finish the proof using F ab Proof of Theorem 2. Let G = (V, E, c) be the original graph and G mb = (V, E mb , c mb ) its metric backbone. Let E θ ⊆ E be the subset of edges whose cost is no more than θ:(u, v) ∈ E θ ⇐⇒ c(u, v) ≤ θ,and which is the edge set of the corresponding threshold graph G θ = (V, E θ , c θ ), where c θ is the restriction of c to E θ .Denote by W, W mb , W θ ∈ R n×n + the adjacency matrices of G, G mb , and G θ , respectively.Overview of the proof. To prove Theorem 2, the key idea is to choose a threshold θ large enough such that the threshold graph contains the metric backbone (i.e., E mb ⊆ E θ ), but not too large so that the adjacency matrices W mb and W θ are not too different.Lemma 1 ensures that, for any ϵ > 0, we haveP max 1≤u,v≤n C(u, v) ≤ 3+ϵ τmin log n nρn = 1 -o(1).Hence, E mb ⊆ E θ whp as soon as θ ≥ 3+ϵ τmin log n nρn . We choose θ = 4 τmin log n nρn , and we proceed by conditioning on the event E mb ⊆ E θ , which occurs with high probability given our choice of θ.We will first prove that the clusters can exactly be recovered using the eigenvectors of EW mb . Then, using Davis-Kahan's Theorem [44, Theorem 2] , we show that the clusters can also be recovered from the adjacency matrix W mb , provided that ∥W mb -EW mb ∥ is small enough. More precisely, we obtain an upper-bound on loss(z, z) that depends on ∥W mb -EW mb ∥. The main ingredients of the proof are thus (i) the justification of the choice of θ in Lemma 1 and (ii) the careful upper-bounding of ∥W mb -EW mb ∥.Starting point: eigenstructure of the expected adjacency matrix EW mb and Davis-Kahan. Let Z ∈ {0, 1} n×k be the one-hot encoding of the true community structure z ∈[k] n , i.e., ∀u ∈ [n], ∀a ∈ [k] : Z ua = 1 if z u = a, 0 otherwise. (B.2)For any two vertices u, v belonging to communities a and b, respectively, we write EW mb uv = m ab . Let M = (m ab ) ∈ R k×k . We haveEW mb = ZM Z T . Denote by |σ 1 | ≥ • • • ≥ |σ k | the k eigenvalues of EW mb , and by ū1 , • • • , ūk their associated eigenvectors. Let Σ = diag(σ 1 , • • • , σk ) ∈ R k×k and Ū = [ū 1 , • • • , ūk ] ∈ R n×k . We have EW mb = Ū Σ Ū T . (B.3) Let ∆ = diag( √ nπ) ∈ R k×k be the diagonal matrix whose diagonal elements are √ nπ 1 , • • • , √ nπ k .We haveZM Z T = Z∆ -1 ∆M ∆ Z∆ -1 T . Notice that Z∆ -1 ∈ R n×k has orthonormal rows (indeed Z∆ -1 T Z∆ -1 = ∆ -1 Z T Z∆ -1 = I K because Z T Z = ∆ 2 ). Let ODO T be an eigendecomposition of the symmetric real-valued matrix ∆M ∆ (that is, D ∈ R k×k is a diagonal matrix whose diagonal elements are in decreasing order (in absolute value) and O ∈ R k×k is an orthonormal matrix). Then Because Ū = Z∆ -1 O, two vertices are in the same cluster if and only if their corresponding rows in Ū are the same. In other words, the spectral embedding of the expected graph ZM Z T = Z∆ -1 O D Z∆ -1 O T is an eigendecomposition of ZM Z T (because Z∆ -1 O is orthonormal).EW mb is condensed into k points (∆ -1 O) 1• , • • • , (∆ -1 O) k• of R k .∥U O -Ū ∥ F ≤ 2 3/2 k 1/2 ∥W mb -EW mb ∥ |σ k | , (B.5)where ∥ • ∥ denotes the matrix operator norm.Let us now establish an expression of |σ k |. Observe firstly that ∆M ∆ and M ∆ 2 have the same eigenvalues. 14 From Lemma 4, we have1 2τ 2 max (Λ ⊙ B) ab log 2 n n 2 ρ n ≤ m ab ≤ 1 2τ 2 min (Λ ⊙ B) ab log 2 n n 2 ρ n .The definition of T = [Λ ⊙ B] diag(π) in (2.1) and the fact that∆ 2 = n diag(π) further imply that 1 2τ 2 max T ab log 2 n nρ n ≤ M ∆ 2 ab ≤ 1 2τ 2 min T ab log 2 n nρ n .Recall that θ = 4 loss(z, z) ≤ (4 + 2ϵ)2 5 k 8τ min µ • ∥W mb -EW mb ∥ θ log n 2 . (B.7)Core of the proof: concentration of W mb around EW mb . We finish the proof by showing that ∥W mb -EW mb ∥ = O θ √ log n whp. First, by a triangle inequality, we have∥W mb -EW mb ∥ ≤ ∥W mb -W θ -E W mb -W θ ∥ + ∥W θ -EW θ ∥ (B.8)For ease of the exposition, we will upper-bound the term of (B.8) in the following order: (i) the second term ∥W θ -EW θ ∥, and then (ii) the first term ∥W mb -W θ -E W mb -W θ ∥.(i) Let us first study ∥W θ -EW θ ∥. The matrix X = W θ /θ is symmetric with zero-diagonal, whose entries {X uv , u < v} are independent [0, 1]-valued random variables. Moreover, Lemma 3 shows thatE [X uv | z u = a, z v = b] = p ab λ ab θ = Θ(log n/n).Thus, [18, Theorem 5] ensures that for any c > 0 there exists c ′ > 0 such thatP ∥W θ -EW θ ∥ ≥ c ′ θ log n ≤ n -c . (B.9) (ii) Next, let us study ∥W mb -W θ -E W mb -W θ ∥ 2 . Denote Y = -W mb -W θ /θ.By Lemma 1 and our choice of θ, we haveE mb ⊆ E θ (for n large enough). Moreover, W θ uv = W mb uv for all {u, v} ∈ E mb ∩ E θ = E mb . Hence, Y uv = W θ uv θ if {u, v} ∈ E θ \E mb , 0otherwise, andEY uv = EW θ uv θ if {u, v} ∈ E θ \E mb , 0 otherwise.We can thus rewrite the matrices Y and EY as Y = R ⊙ W θ /θ and EY = R ⊙ EW θ /θ, where ⊙ denote the Hadamard (entry-wise) matrix product and R ∈ {0, 1} n×n is defined byEQUATIONLet E c1 be the event that all rows of R have at most c 1 log n non-zero entries (with c 1 > 0), i.e.,E c1 = ∀u ∈ [n] : n v=1 1{R uv ̸ = 0} ≤ c 1 log n .Because E mb ⊆ E θ , we have1{R uv ̸ = 0} = R uv = 1{(u, v) ∈ E θ \E mb } ≤ 1{(u, v) ∈ E θ }.Thus, E c1,θ ⊆ E c1 , whereE c1,θ = ∀u ∈ [n] : n v=1 1{(u, v) ∈ E θ } ≤ c 1 log n .Hence, P(E c1 ) ≥ P(E c1,θ ). Recall also that 1{(u, v) ∈ E θ } = 1{c(u, v) ≤ θ}. Thus, by Lemma 2, for any c 0 > 0 there exists a c 1 > 0 such thatP (E c1 ) ≥ 1 -n -c0 . (B.10)Conditioned on the high probability event E c1 , every row of the matrix R has at most c 1 log n non-zero elements. Moreover, W/θ is symmetric and has bounded (hence sub-gaussian) entries. Therefore [5, Corollary 3.9] ensures the existence of constants C, C ′ > 0 such thatP R ⊙ W θ -EW θ /θ ≥ C log n + t E c1 ≤ e -C ′ t 2 .Using t = C ′′ √ log n, and because Y -EY = R ⊙ W θ -EW θ /θ, we obtain the following statement: for any c > 0, there exists c ′ > 0 such thatP ∥Y -EY ∥ 2 ≥ c ′ log n E c1 ≤ n -c .P ∥W mb -W θ -E W mb -W θ ∥ ≥ c ′ θ log n ≤ 2n -c . (B.11)Conclusion Using (B.8), (B.9) and (B.11), we have∥W mb -EW mb ∥ ≤ 2c ′ θ log n, (B.12)with probability at least 1 -3n -c . The proof ends by combining (B.12) with (B.7).Lemma 1. Let (z, G) ∼ wSBM(n, π, p, F ) and suppose that Assumptions 1 and 2 hold. Then,max u,v∈[n] C(u, v) ≤ (1 + o(1)) 3 τ min log n nρ n .Proof. We proceed as in the proof of Proposition 1 by firstly assuming that F ab ∼ Exp(λ ab ). 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 1. Recall in particular the notations C u (q), U ℓ (q) and X ℓℓ ′ (u, q). Because we established thatB(u, C u ( √ n log n)) ∩ B(v, C v ( √ n log n)) ̸ = ∅ whp, we have C(u, v) ≤ C u ( n log n) + C v ( n log n). Therefore, max u,v C(u, v) ≤ max u,v C u ( n log n) + C v ( n log n) = 2 max u C u ( n log n).Using a union bound, we obtain for any t > 0,P max u C u ( n log n) ≥ t ≤ n u=1 P C u ( n log n) ≥ t = nP C u * ( n log n) ≥ t , (B.13)where u * denotes an arbitrary vertex chosen in [n]. For any s > 0, we have (by Chernoff bounds)P C u * ( n log n) ≥ t ≤ e -st E e sC u * ( √ n log n) . (B.14) Recall from (A.3) that C u * (q+1)-C u * (q) | S(u, •) are i.i.d. Exp(θ q ) with θ q = ℓ,ℓ ′ λ ℓℓ ′ S ℓℓ ′ (u, q). As for X ∼ Exp(θ) we have E[e sX ] = θ/(θ -s) = 1 + s/(θ -s), E e sC u * ( √ n log n) | S(u, •) = √ n log n q=1 E e s(C u * (q+1)-C u * (q)) | S(u, •) = √ n log n q=1 1 + s θ q -s = exp   √ n log n q=1 log 1 + s θ q -s   ≤ exp   √ n log n q=1 s θ q -s   .Let 0 < ϵ < 1/6. From Equations (A.5) and (A.6), we have whp (for n large enough)θ q ≥ (1 -ϵ)nρ n τ min q.Choose s = (1 -2ϵ)nρ n τ min and let α n be a diverging sequence verifying α n = o( √ n log n) to be chosen later. We split the sum as follows√ n log n q=1 s θ q -s = αn q=1 s θ q -s + √ n log n q=αn+1 s θ q -s .We have for any1 ≤ q ≤ α n θ q -s ≥ nρ n τ min q 1 -ϵ - 1 -2ϵ q ≥ nρ n τ min qϵ,while for α n ≥ q we have (1 -2ϵ)α n ≤ ϵ (for n large enough) and thusθ q -s ≥ nρ n τ min q 1 -ϵ - 1 -2ϵ q ≥ nρ n τ min q 1 -ϵ - 1 -2ϵ α n ≥ nρ n τ min q(1 -2ϵ),and thus√ n log n q=1 s θ q -s ≤ (1 -2ϵ)   1 ϵ αn q=1 1 q + 1 1 -2ϵ √ n log n q=αn+1 1 q   .Recalling that n q=m+1 q -1 ≤ log(n/m) for any m ≥ 1 (by integration) further leads to√ n log n q=1 s θ q -s ≤ (1 -2ϵ) 1 ϵ (1 + log α n ) + 1 1 -2ϵ log √ n log n α n .Therefore,E e sC u * ( √ n log n) | S(u, •) ≤ exp (1 -2ϵ) 1 ϵ (1 + log α n ) + 1 1 -2ϵ log √ n log n α n .Because the right-hand side of this last upper bound does not depend on S(u, •), we have by the total law of probabilities,E e sC u * ( √ n log n) ≤ exp (1 -2ϵ) 1 ϵ (1 + log α n ) + 1 1 -2ϵ log √ n log n α n . (B.15)We choose α n = ⌈ √ log n⌉. Because α n = ω(1), α n = o(log n), and ϵ is fixed, we have for n large enough,1 ϵ (1 + log α n ) ≤ ϵ log n 2 1 1 -2ϵ log √ n log n α n ≤ (1 + 3ϵ) log n 2 ,where the second inequality uses ϵ < 1/6. Thus, we can rewrite the inequality (B.15) (for n large enough) asE e sC u * ( √ n log n) ≤ exp (1 -2ϵ)(1 + 4ϵ) log n 2 ≤ exp (1 + 2ϵ) log n 2 . Let t = (3 + ϵ ′ ) log n/(2nρ n τ min ) with ϵ ′ = 15ϵ. Recall that s = (1 -2ϵ)nρ n τ min . From (B.14) we obtain P C u * ( n log n) ≥ t ≤ e -(1-2ϵ)(3+ϵ ′ ) log n 2 +(1+2ϵ) log n 2 = e -log n 2 (2-8ϵ-2ϵϵ ′ +ϵ ′ ) ≤ e -log n(1+ϵ) ,where in the last line we uses -8ϵ -2ϵϵ ′ + ϵ ′ = 6ϵ -30ϵ 2 ≥ ϵ (using ϵ < 1/6). Because 1 + ϵ > 1,we have P C u * ( √ n log n) ≥ t = o(n -1), and we conclude using (B.13). Then, P (E c1,θ ) ≥ 1 -n -c1 .Proof. For u ̸ = v ∈ [n] such that z u = a and z v = b, we have (recall that the probability of having an edge (u, v) ∈ E is p ab , and the cost of this edge is sampled from F ab )P (c(u, v) ≤ θ | z u = a, z v = b) = p ab F ab (θ).Recall also that, by Assumption 1, we have p ab = B ab ρ n and by Assumption 1F ab (x) = (1 + o(1))λ ab x. Let ϵ > 0.Using the law of total probability, we obtainP (c(u, v) ≤ θ) ≤ (1 + o(1))B max λ max θρ n ,where B max = max 1≤a,b≤k B ab and λ max = max 1≤a,b≤k λ ab . Thus, for n large enough we haveP (c(u, v) ≤ θ) ≤ 2B max λ max θρ n ,For ease of notations, let p θ = 2B max λ max θρ n and c = 4B max λ max c 0 + 1 + c 1 .For u ∈ [n] we denote d u = n v=1 1{c(u, v) ≤ θ}. We haveP max u∈[n] d u ≥ c log n ≤ u∈[n] P (d u ≥ c log n) . (B.16)Moreover, for any t > 0, we have 1) ,E e tdu ≤ 1 -p θ + p θ e t n ≤ e np θ (e t -where the second inequality used log(1 + x) ≤ x. Let c > 0. Using Chernoff's bounds, we have 1) .P (d u ≥ c log n) ≤ e -tc log n+np θ (e t -Let t = 1. Because e 1 -1 ≤ 2 and np θ = 2B max λ max c 0 log n, we obtainP (d u ≥ c log n) ≤ e -log n(c log n-4Bmaxλmaxc0) .We finish the proof by letting c = 4B max λ max c 0 + 1 + c 1 and using (B.16). Proof. We haveW θ uv = W uv 1{W uv ≤ θ}. Moreover, W uv | W uv ̸ = 0 is sampled from F ab . Thus, E W θ uv = p ab E [W uv 1{W uv ≤ θ}] . Denote also f ab the pdf of F ab . Recall by Assumption 2 that f ab (x) = λ ab + O(x). Because θ ≪ 1 we have E W θ uv = p ab λ ab θ 2 2 .Lemma 4. Let (z, G) ∼ wSBM(n, π, p, F ) and suppose Assumptions 1 and 2 hold. Let θ = c log n nρn . Denote W the weighted adjacency matrix of G, and W mb the weighted adjacency matrix of the metric backbone of G. Let u, v ∈ [n] such that z u = a and z v = b. We have1 2τ 2 max (Λ ⊙ B) ab log 2 n n 2 ρ n ≤ E W mb uv ≤ 1 2τ 2 min (Λ ⊙ B) ab log 2 n n 2 ρ n .Proof. Let u, v ∈ [n] be two arbitrary vertices such that z u = a and z v = b. We haveW mb uv = c(u, v)1{(u, v) ∈ E mb }. Recall from Proposition 1 that (τ max ) -1 ≤ nρ n log n C(u, v) ≤ (τ min ) -1whp, where C(u, v) is the cost of the shortest path from u to v. Therefore,E W mb uv = E c(u, v) ∩ (u, v) ∈ E mb ≤ E c(u, v)1 c(u, v) ≤ 1 τ min log n nρ n = p ab λ ab 1 2 log n τ min nρ n 2 ,where we used Lemma 3 with θ = 1 τmin log n nρn . Similarly,E W mb uv ≥ E c(u, v)1 c(u, v) ≤ 1 τ max log n nρ n = p ab λ ab 1 2 log n τ max nρ n 2 .Recalling that p ab = B ab ρ n , we obtain We highlight the difference between the metric backbone and the spectral sparsification of the Primary school data set in Figure 5 . Whereas Figure 2 highlights a clear pattern between the metric backbone and the threshold graph, finding from Figure 5 any pattern in the edges present in the metric backbone but not in the spectral sparsification (and vice-versa) is much harder. Although both sparsified graphs preserve the community structure very well, they do so by keeping a very different set of edges. 5a ) 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 in red. Similarly, edges present in the spectral sparsifier graph, but not in the metric backbone, are highlighted in blue.1 2τ 2 max (Λ ⊙ B) ab log 2 n n 2 ρ n ≤ E W mb uv ≤ 1 2τ 2 min (Λ ⊙ B) ab log 2 n n 2 ρ n .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 we do not have any ground truth for these additional data sets, we computed the ARI between the clustering obtained on the original network and on the sparsified network. We observe that the largest ARI 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. Number of edges in the q-nearest neighbor graph and its metric backbone We show in Figure 7 the number of edges in G q and G mb q (we do not show the number of edges of the spectral sparsified G ss q because the hyperparameters of G ss q are chosen such that G mb q and G ss q have the same number of edges).Exploring another similarity measure Finally, we 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 is a subspace clustering algorithm and was shown to succeed under very general conditions on the high-dimensional data set to be clustered [21] . TSC performs spectral clustering on a q-nearest neighbors graph obtained using the following similarity measure sim(x u , x v ) = exp (-2 arccos (< x u , x v >)) . Because in Section 5 we showed the performance of spectral clustering using the Gaussian kernel similarity, these additional experiments also show the robustness of our results with respect to the choice of the similarity measure. Figure 8 shows the performance of TSC on G q and its sparsified versions G mb q and G ss q , and Figure 9 shows the number of edges (before and after sparsification). Computing Resources All experiments were run on a standard laptop with 16GB of RAM and 12th Gen Intel(R) Core(TM) i7-1250U CPU.To compute the full metric backbone, we used the igraph distances implementation [11] . It takes around 7 minutes for graphs with 10, 000 vertices and q = 10. For the same graph, computing the spectral sparsification takes around 15 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 scikitlearn implementation of spectral clustering takes 3.5 hours for MNIST and 2 hours for Fashion-MNIST while we only needed 100 seconds to obtain the metric backbone approximation.NeurIPS Paper Checklist 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 3. 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 a 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 well-specification, 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 on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence 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). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: We respect the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).This additive property does not hold for similarity weights, but a proximity graph can be transformed into a distance graph by applying an isomorphic non-linear transformation on the weights[36].In fact, this intuitive observation is at the core of one of the very first community detection algorithms[17].The events 1{(u, v) is metric} and 1{(w, x) is metric} are in general not independent, but the probability that (u, v) is metric depends only on the cluster assignment of vertices u and v.An edge (u, v) ∈ E such that c(u, v) = 0 yields the possibility of teleportation from vertex u to vertex v.We notice that, given a wSBM, whp there is only one shortest path.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 a modification of the RI such that two random clusterings (resp., two identical clusterings) give an ARI of 0 (resp., of 1)[22].We also note that the threshold graph G θ is often not connected. Hence, we ignored all components comprising less than 5 nodes before running spectral clustering.In other words, an edge (u, v) is present if at least one of its two endpoints is in the q-nearest neighborhood of the other.Because√ n log n is not necessarily integer we should write ⌈ √ n log n⌉ but we drop the ⌈ and ⌉ to avoid overburdening the notations.Recall that if x1 + • • • + x k = m with x ℓ ≥ 0 then max ℓ x ℓ ≥ k -1 m.More precisely, we define F -1 ab (t) = inf{x ∈ R : F ab (x) ≥ t}. Because the cdf F ab is increasing, F -1 ab (t) is well-defined.We note that[39] state the result for a weighted Erdős-Rényi random graph, but their proof holds for a wSBM as well.Let A, B be two symmetric matrices of the same size. Let λ be an eigenvalue of ABA, with corresponding eigenvector x. Multiplying both sides of ABAx = λx by A, we get A 2 By = λy with y = Ax. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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.

2. 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: limitations: The authors haven’t discussed the limitations in the main paper, but in the checklist instead.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- It claims that Algorithm 1 can recover the community structure from the metric backbone, but why the input is the original graph G?
- 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?
- Comparison with other graph sparsification methods or other data sets may be added.
questions: questions: The authors may explain the drawbacks mentioned in the weakness section.
limitations: limitations: Yes.
paper_summary: paper_summary: The authors analyze the metric backbone (= all the edges that are on  some shortest path) and it's relation to clustering.

They show that under weighted SBM model (with equal expected degree for all nodes), metric backbone
1) the metric backbone approximately maintains the edge probabilities of blocks
2) spectral clustering appplied to metric backbone recovers SBM.
strength_weakness: strength_weakness: 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.

Moreover, 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.

Do 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.

Other questions/remarks:

- Assumption 1: p_n >> ...  what does >> means here exactly? that log n /  n in o(p_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?
- 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.
- Leveraging the memoryless ... processes. Unclear sentence, please reword.
- be defined after Equation 2.1. -> be as defined in Remark 1.
- maintains the same proportion -> maintains approximately the same proportion
questions: questions: - Does the result hold for other sparsification methods?
- Can Theorem 2 be stated with tmin < tmax?
- is lambda in Remark 1 needed assumption?
limitations: 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.
paper_summary: paper_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.
Experiments are performed to demonstrate this behavior on real-world networks.
strength_weakness: strength_weakness: 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.
Also, 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.

Similarly, 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.
Also, the label placement of Figure 2a is a bit inconvenient as it blocks the blue line.

Moreover, while the results of Section 4 are interesting, the results of Section 5 are not convincing.

Minor comments:
* 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$.
questions: 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.

At 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: limitations: The authors have addressed the limitations of the results.

Comments: comment: Thank the authors for their response. I keep my score.
I thank the authors for the response. The response adequately addresses my main concerns. I encourage the authors to improve the description of the experiments to incorporate the above answers (in particular, include references to show that this is a relatively standard approach).

My overall rating remains unchanged.