Why the Metric Backbone Preserves Community Structure

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.

Strengths

The paper is well-written and easy to read. The problem is interesting and the described theoretical behavior is surprising. The 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. 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

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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have addressed the limitations of the results.

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.

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

- Does the result hold for other sparsification methods? - Can Theorem 2 be stated with tmin < tmax? - is lambda in Remark 1 needed assumption?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

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.

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.

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. - Confirms the theoretical finding through an empirical comparison of graph sparsification techniques, providing practical evidence and validation. - 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. - 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

The authors may explain the drawbacks mentioned in the weakness section.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Yes.

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.

Strengths

1. The technical contribution is solid. 2. 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.

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?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors haven’t discussed the limitations in the main paper, but in the checklist instead.