Why the Metric Backbone Preserves Community Structure

Dear Reviewer bM2e,

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

• 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).

• 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$).

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

We also thank you for pointing out some typos and will correct them.

Dear Reviewer uKT3,

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

Answers to the main questions:

• 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 not be preserved. 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.

• 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. 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. 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. 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).

We appreciate you raising this point, as it strengthens our result, and we plan to modify the proof and statement of Theorem 2 accordingly.

Answers to the other remarks:

• Indeed, the cost of the shortest path between $u$ and $v$ goes asymptotically to zero.

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

Dear Reviewer Qqxh,

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

• 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).

• 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}$.

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

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

Dear Reviewer JByP,

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

• 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]). 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.

• 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).

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

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