Efficient Sparsification of Densely Connected Clusters

Authors: Joyentanuj Das, Suranjan De, He Sun
Primary area: learning on graphs and other geometries & topologies
Keywords: densely connected components, graph sparsification, clustering

Abstract:
When modelling a real-world dataset as a graph, groups of highly correlated data items correspond to densely connected vertex sets (clusters), and efficient algorithms that find these clusters have broad applications in various data analysis tasks. In this paper we study densely connected clusters in graphs and introduce two sparsification algorithms that preserve the structure of  these clusters in both undirected graphs and directed ones. We show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.

Decision: reject
Reviewer scores: 8, 5, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1729886680755

thread_type:
official_review

<thread_object>
creator: reviewer_q1we

<content>
summary:
This paper proposes a sparsification method that maintain the strucutre of clusters for undirected and directed graphs. Specifically, the authors present two nearly-linear algorithms. Also, the authors provide a thorough theoretical analysis and expereimental results using synthetic datasets.

strengths:
- Thorough theoretical analysis.

weaknesses:
- What are the practical advantages of addressing the considered problem? What is the motivation?
- Some notations such as $\omega_G$ and $vol_G$ are used without being clearly defined.
- The algorithms assume that the input graphs exhibit clearly defined cluster structures. What if the clusters are less well-defined? Does it impact the effectiveness of sparsification?
- The experiments are conducted using only synthetic datasets. The effectiveness of real-world datasets are not tested.
- How sensitive are the algorithms with respect to the parameters?

questions:
Please find the questions in the **weaknesses**.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730443044811

thread_type:
official_review

<thread_object>
creator: reviewer_5rub

<content>
summary:
The sparsification algorithm presented in this paper effectively handles densely connected clusters in both undirected and directed graphs. The article provides sufficient proofs demonstrating the method's time efficiency. However, the writing is somewhat confusing, making it difficult to clearly explain the approach used. Additionally, the experiments lack relevant data validation and comparative analysis.

strengths:
1.The paper offers sufficient theoretical foundation with detailed analysis of Cheeger constants and spectral theory, providing solid proof of the algorithm's effectiveness.

2.The sparsification algorithm significantly speeds up existing clustering methods while effectively handling densely connected clusters in both undirected and directed graphs.

3.The algorithm is applicable to both undirected and directed graphs, demonstrating its flexibility and usefulness across different types of graph structures.

weaknesses:
1. The structure of the article is confusing, and the method is not clearly explained. The article should highlight its contributions and clearly describe the solution ideas and working methods. Additionally, the use of symbols and lemmas, as well as the arrangement of proofs, should be more detailed.
    - For example, what’s vol_{G} and w_{G} is not explained in the intro when Equations 1.1 is introduced.
    - A_i \cup B_i \neq \emptyset for different i,j \in [k], typo?
2. The experiments lack relevant work. The absence of extensive testing with different algorithms on multiple datasets may impact the algorithm's universality and reliability.
3. The experiments are only conducted on synthetic datasets without real-world datasets. It would be better to provide more experiments on real-world datasets.  
4. While the algorithm shows improved efficiency empirically, the trends may need further explanation. For example, the improvement seems larger when the dataset is larger, while on directed graphs the improvement seems smaller when the dataset is larger (with 2000 and 5000 vertices, respectively). Further explanations are needed here, whether there are some gaps between the implementation and theoretical analysis.

questions:
How do you plan to improve the structure of the article to enhance clarity? Will you include more detailed descriptions of the solution ideas and working methods?

Can you explain why the 5000-vertex setting in Figure 3 (a) takes less time compared to 4000-vertex setting? Will you consider testing the effectiveness of this method on a real-world dense dataset?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730476695073

thread_type:
official_review

<thread_object>
creator: reviewer_lppm

<content>
summary:
The paper proposes efficient sparsification algorithms to preserve densely connected vertex sets in undirected and directed graphs.

strengths:
The paper proposes efficient sparsification algorithms to preserve densely connected vertex sets in both undirected and directed graphs.

weaknesses:
1. Notations (e.g., w_G(V_1, V_2), vol_G(V_1 \union V_2)) and concepts (e.g., k pairs of densely connected clusters) are introduced in the introduction but are not defined.

2. The significance of the proposed algorithms is not clear.

3. The experimental results are not convincing.

questions:
Notations (e.g., w_G(V_1, V_2), vol_G(V_1 \union V_2)) and concepts (e.g., k pairs of densely connected clusters) are introduced in the introduction but are not defined, and therefore I was confused right from the beginning when reading the paper. In fact, I still do not fully understand what "k pairs of densely connected clusters" actually means, I can understand there are k disjoint subsets of vertices in the graph and the induced subgraph of each subset of vertex may form a cluster (i.e., a densely connected subgraph), but where do you get k pairs of densely connected clusters from k disjoint subsets of vertices? Therefore, it is very difficult for me to understand the paper when the important concepts are not properly defined. I suggest the authors to clearly define all notations and concepts the first time they are introduced in the paper. 

The significance of the proposed algorithms is not clear, i.e., why the results are important theoretically and practically?  It would be good if the authors could clearly explain the significance of the proposed method using a running example, e.g., given an input graph, what does the algorith output and show that the output is important.

The experiments were conducted on synthetic graphs only with k = 2. It would be more convincing to show the results on representative real graphs and large values of k. Another question is that k is actually unknown in practice, how do the authors address this problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730650705542

thread_type:
official_review

<thread_object>
creator: reviewer_58yn

<content>
summary:
The authors propose a sparsification algorithm for dense clusters that approximately preserves the clustering the sparse representation of the underlying graph.

strengths:
The authors study an interesting and well-studied problem.

weaknesses:
1. A good fraction of the paper is rehashing well-known definitions.
2. This is a well-studied problem.  There are a lot of missing references including papers that compare different sparsification techniques (e.g., see https://arxiv.org/pdf/2311.12314 and references within).  Related references include : 
        1) D.A. Spielman and N. Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6), pp.1913-1926. 2011.
        2) http://cs-www.cs.yale.edu/homes/spielman/PAPERS/CACMsparse.pdf
        3) https://www.cs.ubc.ca/~nickhar/papers/Sparsifier/Sparsifier-Long.pdf. and references within.
        4) https://www.cis.upenn.edu/~sanjeev/papers/focs22_weighted_sparsification.pdf

questions:
1. The papers I referred to above address the questions of the sparse graph satisfying some properties including community detection. Please differentiate how the proposed work differs from the earlier work.

Update:  The authors have sufficiently addressed my concerns.  I have raised my score. Even as the authors claim their approach works well for the directed case as well, they have not conclusively demonstrated the effectiveness of their approach practically. I am not able to strongly back the paper as the work still seems lacking sufficiently new ideas for a well-studied problem.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730682133749

thread_type:
official_review

<thread_object>
creator: reviewer_a7rn

<content>
summary:
The paper introduced sparsification algorithms and the corresponding theoretical analysis that preserve the structure of densely connected vertex sets in both undirected and directed scenario. The experiments on synthesis dataset indicates the efficiency of the proposed sparsification and the effectiveness for clustering.

strengths:
1. The algorithm description is straightforward and easy to follow. For undirected graph, local sampling and reweighing the edges are the necessary steps for sparsification; for directed graph, the process to convert to undirected graph and converted back are the extra steps.
2. The theoretical analysis and the probability guarantee makes the methodology promising; the nearly-linear running time makes the algorithm applicable. 
3. The specific challenges in directed graph case are discussed in detail.

weaknesses:
1. Some of the notations could be more clear: 
    i.  The w_G and vol_G in line 37 are not defined.
    ii. Although it mentions C is a universal constant on Lemma 3 and Lemma 4, it is still not clear how to determine the value of C in formula 3.1 for the experiment. 
2. There is no experiment conducted on multiple cluster case or real-world dataset.

questions:
1. Is there a way to adjust the level of sparsification? How will the efficiency and effectively be affected?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732202639803

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Experimental results on real-world datasets

comment:
To respond to the reviewers' request, we conduct additional experiments on the real-word data sets. Specifically, we follow the work of Macgregor and Sun (2021), and evaluate the performance of our algorithm on the US migration dataset. Given this dataset, we construct the digraph as follows: every county in the mainland USA is represented by a vertex; for any vertices $i,j$, the edge weight of $(i,j)$ is given by $|(M_{i,j} − M_{j,i})/(M_{i,j}+M_{j,i})|$, where $M_{i,j}$ is the number of people who migrated from county $i$ to county $j$ between 1995 and 2000; in addition, the direction of $(i,j)$ is set to be from $i$ to $j$ if $M_{i,j} > M_{j,i}$, otherwise the direction is set to be the opposite.

We compare the output of ECD and the output of our sparsification algorithm + ECD. Furthermore, we use the vertices corresponding to different counties as the input of the local algorithm ECD. Our experimental result is as follows:

 |County Name               | Target $\phi$  |  ECD Runtime     |  ECD Flow-Ratio       |   ECD+Our  Runtime |   ECD+Our Flow-Ratio|
 | ----------- | ----------- |----------- |----------- |----------- |----------- |
 |Maricopa County  |0.1| 20.28   | 0.416      | 14.124  | 0.45    | 
  |                 |0.2|20.661|0.414 |13.434 |0.417    
  |Virginia Beach City| 0.1| 14.725  | 0.413      | 11.172  | 0.672|      
|                    |0.2| 15.31 |0.546 | 12.29 | 0.621      |
|Kanawha county        | 0.1           | 10.083 | 0.33       | 8.459   | 0.364 |     
|                  | 0.2| 9.318 | 0.33|8.483 | 0.33  |     

These experimental results clearly demonstrate that with our sparsification algorithm the local algorithm achieves roughly the same flow ratio, and our sparsification clearly speeds up the total running time of the algorithm. Moreover, the runtime speedup is more significant when the local algorithm explores more parts of the input graph (corresponding to a higher value of $\phi$).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732636995217

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear reviewers, with the discussion period ending soon, we’d really value your feedback on our responses - let us know if there’s anything else we should clarify or fix. Thank you again for your time.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents efficient sparsification algorithms for both undirected and directed graphs, designed to preserve the structure of densely connected clusters. The authors provide theoretical analysis demonstrating the efficiency of their algorithms, which have near-linear time complexity. They also present experimental results on synthetic datasets, showing the effectiveness of their approach for clustering tasks.

Reviewers appreciate the simplicity of the proposed algorithms and the clarity of the theoretical analysis. The near-linear time complexity is a desirable property for sparsification methods.

However, reviewers also identify some weaknesses:

- Limited Experimental Evaluation: The experiments are limited to synthetic datasets and do not include real-world data or scenarios with multiple clusters. This makes it difficult to assess the practical applicability of the proposed method.
- Missing Related Work: The paper lacks a comprehensive discussion of related work on graph sparsification and clustering. This limits the context for the contributions of the paper.

Recommendation:

While the paper presents efficient sparsification algorithms with theoretical guarantees, the reviewers agree that it does not meet the bar for acceptance at ICLR in its current form.