Online Sparsification of Bipartite-Like Clusters in Graphs
Joyentanuj Das, Suranjan De, He Sun · 2025
Read Online Sparsification of Bipartite-Like Clusters in Graphs by Joyentanuj Das, Suranjan De, He Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05437.txt.
Introduction
Joyentanuj Das, Suranjan De, and He Sun present, in a 2025 computer science paper, fast online methods to thin out graphs while keeping clusters that look like two-sided webs. Clustering huge graphs is a core data tool, yet most methods chase single dense groups. Recent work shows the links between groups matter as much for real data.
Their sparsification keeps the two-sided clusters while dropping many edges, which speeds up later clustering runs. The methods work on both plain and directed graphs, and they update as data arrive. Tests on fake and real graphs showed large time savings with clustering quality kept intact. The work targets data sets too big for slower exact tools.
Catalog record
| CREATOR | Joyentanuj Das, Suranjan De, He Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05437
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Online Sparsification of Bipartite-Like Clusters in Graphs Joyentanuj Das, Suranjan De, He Sun Abstract Graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most graph clustering algorithms is to find a vertex set of low conductance, a sequence of recent studies highlights the importance of the inter-connection between vertex sets when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and online sparsification algorithms that find such clusters in both undirected graphs and directed ones. We conduct experimental studies on both synthetic and real-world datasets, and show that our algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness. 1 Introduction Graph clustering is a fundamental technique in data analysis with wide-ranging applications in machine learning and data science. A classical graph clustering problem involves partitioning the vertices of a graph into sets of highly connected vertices to minimize the normalised cut value. However, many real-world clustering tasks are defined by alternative objective functions, tailored to the specific needs and constraints of the problem at hand. One such example involves uncovering the vertex sets that are densely connected to each other, and these two vertex sets form a bipartite-like graph. For example, when representing the migration or trade datasets with a graph, a bipartite-like cluster captures a typical pattern of regional migration or trade ( Cucuringu et al. 2020 ; Laenen & Sun 2020 ; He et al. 2022 ) , and the significance of bipartite-like clusters is further highlighted when studying many other real-world datasets ( Bennett et al. 2022 ; Concas et al. 2022 ) . Our Results. We first study bipartite-like clusters in undirected graphs, and present an algorithm that sparsifies an undirected graph while preserving its structure of bipartite-like clusters. Our algorithm can be implemented online, and directly applied to speed up the running time of existing algorithms that find bipartite-like clusters. Formally speaking, for an undirected G=(V,E) and a pair of disjoint and non-empty subsets A,B\subset V , we define \overline{\phi}_{G}(A,B)\triangleq\frac{2w_{G}(A,B)}{\textup{vol}_{G}(A\cup B)}, where w_{G}(A,B)\triangleq\sum_{\begin{subarray}{c}\{u,v\}\in E\\ u\in A,v\in B\end{subarray}}w(u,v) is the cut value between A and B and \textup{vol}_{G}(A\cup B) is the volume of A\cup B defined by \textup{vol}_{G}(A\cup B)=\sum_{\begin{subarray}{c}\{u,v\}\in E\\ u\in A\cup B\end{subarray}}w_{G}(u,v). Notice that a high value of \overline{\phi}_{G}(A,B) implies that most edges adjacent to the vertices in A\cup B are between A and B , and A and B form a bipartite-like cluster. Generalising this to multiple clusters, for every k\in\mathbb{N} we define the k -way dual Cheeger constant by \bar{\rho}_{G}(k)\triangleq\max_{(A_{1},B_{1}),\ldots,(A_{k},B_{k})}\min_{1\leq i\leq k}\overline{\phi}_{G}(A_{i},B_{i}), (1.1) where the maximum is taken over all the possible k pairs of subsets (A_{1},B_{1}),\ldots,(A_{k},B_{k}) satisfying A_{i}\cap A_{j}=\emptyset,B_{i}\cap B_{j}=\emptyset,A_{i}\cap B_{j}=\emptyset for different i,j\in[k] , and A_{i}\cup B_{i}\neq\emptyset for different i,j\in[k] . Notice that a high value of \bar{\rho}_{G}(k) implies that G contains k bipartite-like clusters, in each of which the vertex sets A_{i} and B_{i} are densely connected to each other. We prove that, when G presents a clear structure of k bipartite-like clusters, this structure can be represented by a sparse subgraph G^{*} of G with \widetilde{O}(n) edges, and G^{*} can be constructed online in nearly-linear time 1 1 1 We say that a graph algorithm runs in nearly-linear time if the algorithm’s running time is O(m\cdot\mathrm{poly}\log n) , where m and n are the number of edges and vertices of the input graph. For simplicity, we use \widetilde{O}(\cdot) to hide a poly-logarithmic factor of n . . Our result is as follows: Theorem 1 (Result for undirected graphs) . Let G=(V_{G},E_{G},w_{G}) be an undirected and weighted graph of m edges, and assume that G contains k bipartite-like clusters (A_{1},B_{1}),\ldots,(A_{k},B_{k}) corresponding to \bar{\rho}_{G}(k) . Then, there is an algorithm that runs in \widetilde{O}(m) time and computes a sparsifier G^{*}=(V_{G},F\subset E_{G},\widetilde{w}) , such that these k bipartite-like clusters are preserved in G^{*} with high probability. That is, it holds with high probability that \bar{\rho}_{G^{*}}(k)=\Omega\left(\bar{\rho}_{G}(k)\right) , and G^{*} contains only k bipartite-like clusters. Secondly, we study the bipartite-like clusters in directed graphs. Let \overrightarrow{G}=(V_{\overrightarrow{G}},E_{\overrightarrow{G}},w_{\overrightarrow{G}}) be a digraph with weight function w_{\overrightarrow{G}}:E_{\overrightarrow{G}}\rightarrow\mathbb{R}_{\geq 0} . For any vertex u\in V_{\overrightarrow{G}} , we use \deg_{\textup{out}}(u)\triangleq\sum_{(u,v)\in E}w_{G}(u,v) and \deg_{\textup{in}}(u)\triangleq\sum_{(v,u)\in E}w_{G}(v,u) to express the sum of weights of directed edges with u as the tail or the head, respectively. For any S\subset V_{\overrightarrow{G}} , we define \textup{vol}_{\textup{out}}(S)\triangleq\sum_{u\in S}\deg_{\textup{out}}(u) and \textup{vol}_{\textup{in}}(S)\triangleq\sum_{u\in S}\deg_{\textup{in}}(u) . For any two disjoint subsets A,B\subset V_{\overrightarrow{G}} , we define \overline{\phi}_{\overrightarrow{G}}(A,B) by \overline{\phi}_{\overrightarrow{G}}(A,B)\triangleq\frac{2{w}_{\overrightarrow{G}}(A,B)}{\textup{vol}_{\textup{out}}(A)+\textup{vol}_{\textup{in}}(B)}, (1.2) where {w}_{\overrightarrow{G}}(A,B)\triangleq\sum_{\begin{subarray}{c}(u,v)\in E\\ u\in A,v\in B\end{subarray}}w(u,v) is the sum of the weights of the edges from A to B . For every k\in\mathbb{N} , the k -way directed dual Cheeger constant is defined by \bar{\rho}_{\overrightarrow{G}}(k)\triangleq\max_{(A_{1},B_{1}),\ldots,(A_{k},B_{k})}\min_{1\leq i\leq k}\overline{\phi}_{\overrightarrow{G}}(A_{i},B_{i}), (1.3) where the maximum is taken over all the possible k pairs of subsets (A_{1},B_{1}),\ldots,(A_{k},B_{k}) satisfying A_{i}\cap A_{j}=\emptyset,B_{i}\cap B_{j}=\emptyset,A_{i}\cap B_{j}=\emptyset for different i,j\in[k] , A_{i}\cup B_{i}\neq\emptyset for any i\in[k] . By definition, a high value of \bar{\rho}_{\overrightarrow{G}}(k) implies that \overrightarrow{G} contains k bipartite-like clusters (A_{1},B_{1}),\ldots,(A_{k},B_{k}) such that most edges with their tails in A_{i} have their head in B_{i} and conversely most edges with their head in B_{i} have their tail in A_{i} . We prove that, when \overrightarrow{G} presents a structure of k bipartite-like clusters with respect to \bar{\rho}_{\overrightarrow{G}}(k) , this structure can be represented by a sparse graph \overrightarrow{G^{*}} with \widetilde{O}(n) edges, and \overrightarrow{G^{*}} can be constructed online in nearly-linear time: Theorem 2 (Result for directed graphs) . Let \overrightarrow{G}=(V_{\overrightarrow{G}},E_{\overrightarrow{G}},w_{\overrightarrow{G}}) be a directed and weighted graph of m edges, and assume that \overrightarrow{G} contains k directly bipartite-like clusters (A_{1},B_{1}),\ldots,(A_{k},B_{k}) with respect to \bar{\rho}_{\overrightarrow{G}}(k) . Then, there is an algorithm that runs in \widetilde{O}(m) time and computes a sparsifier \overrightarrow{G^{*}}=(V_{\overrightarrow{G}},F\subset E_{\overrightarrow{G}},\widetilde{w}) , such that these k directed bipartite-like clusters of \overrightarrow{G} are preserved in \overrightarrow{G^{*}} with high probability. That is, it holds with high probability that \bar{\rho}_{\overrightarrow{G^{*}}}(k)=\Omega\left(\bar{\rho}_{\overrightarrow{G}}(k)\right) , and \overrightarrow{G^{*}} only contains k directed bipartite-like clusters. Now we examine the significance of Theorems 1 and 2 . We first highlight that our algorithms preserve the cut values w(A_{i},B_{i}) between the pairs of vertex sets A_{i} and B_{i} for 1\leq i\leq k ; this objective is different from the one for most graph sparsification problems, which only preserve the cut values between vertex set S and V\setminus S . Secondly, our algorithms preserve k bipartite-like clusters, and the value of k in the output graph is the same as the input graph. Thirdly, our second result works for directed graphs ; this result is very interesting on its own since most sparsification algorithms are only applicable for undirected graphs. Finally, while the design of most graph sparsification algorithms are based on Laplacian solvers making it unpractical, our designed algorithms only use random sampling. The design of our algorithms is based on several new reductions and sampling routines, and our algorithms can be implemented online with the degree oracles. As such one can run our algorithms online while exploring the underlying graph with existing local algorithms (e.g., ( Andersen 2010 ; Li & Peng 2013 ) ), resulting in direct improvement on the running time of the existing algorithms. To demonstrate this, we conduct experimental studies and show that our algorithms can be