Online Sparsification of  Bipartite-Like Clusters in Graphs
Authors: Joyentanuj Das
Suranjan De
He Sun
Venue: ICML 2025 poster (2025)
Keywords: bipartite-like components
sparsification
online algorithms
Primary area: general_machine_learning->clustering
TL;DR: 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.

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, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study bipartite-like clusters and present efficient and  online 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.

Online Sparsification of Bipartite-Like Clusters in Graphs
Joyentanuj Das
Suranjan De He Sun
Abstract
Our Results. We first study bipartite-like clusters in undirected graphs, and present an algorithm that sparsi- fies 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. For- mally speaking, for an undirected G (V, E) and pair of
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-wor worldworld 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 algorithms significantly speedup the running time of existing clustering algorithms while preserving their effectiveness.
disjoint and non-empty subsets A, B C V. we define
2wo 2wc(A, (A, B)
(A,
vola (AUB)
where
WG Wo (A, B) A
Σ
w(u, v)
{u,v)EE hEA,eEB
is the eut value between and and vola U B) the volume of A U B defined by
vola = Σ wa(u, v).
(u.)EE DEAJB
1. Introduction
Graph clustering a fundamental technique in data anal- ysis 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 de- fined by alternative objective functions, tailored to the spe- cific 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 bipartite-like graph. For example, when represent- ing 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 al., 2022), and the significance of bipartite- like clusters further highlighted when studying many other real-world datasets (Bennett al., 2022: Concas et al., 2022).
Notice that high value of (a implies that most edges adjacent to the vertices in A U B are between A and B, and A and B form bipartite-like cluster. Generalis- ing this to multiple clusters, for every k E N we define the k k-way dual Cheeger constant by
(k( A
max min B.)...)....AAA. (As B2) Isick
(A, (1.1)
where the maximum is taken over all the possible pairs of subsets (A1, Bi), (Ag, Bx) satisfying A; Aj 6, B, B, 0, A, B, 0 for different i,j [k], and A, U B, * 0 for different i,j e [k]. Notice that high value of (a( implies that G contains A bipartite- like clusters, in each of which the vertex sets A; and B, are densely connected to each other. We prove that, when G presents a clear structure of bipartite-like clusters, this structure can be represented by sparse subgraph G" of G with (n)) edges, and G be constructed online in nearly-linear time!. Our result is as follows:
School of Informatics, University of Edinburgh, Ed- inburgh, United Kingdom. Correspondence to: He Sun <h.sun ed.ac.u>>.
'ee say that graph algorithm runs in nearly-linear time if the algorithm's running time is O(m poly logn), where m and n are the number of edges and vertices of the input graph. For simplicity, we use Ō(-) to hide a logyrtoga factor
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Theorem (Result for undirected graphs). Let G (Va, EG, we) be an undirected and weighted graph of m edges, and assume that G contains k bipartite-like clusters By) corresponding to PG(k). Then, there is an algorithm that runs in ((m) time and com- putes sparsifier G (Va, F C Ea, W), such that these k bipartite-like like clusters are preserved in G* with high probability. That is, it holds with high probability that Pa- (k) = 2 (p)(k)), and G contains only k bipartite- like clusters.
these directed bipartite-like clusters of G are preserved in G with high probability. That is, it holds with high prob- ability that Piz2 (k) 5t ( and G² only contains k directed bipartite-like clusters.
(A1,
Now we examine the significance of Theorems 1 and 2. We first highlight that our algorithms preserve the cut values w(A, B,) between the pairs of vertex sets A, and B; for sii S 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 V.S. Secondly, our algo- rithms preserve bipartite-like clusters, and the value of in the output graph is the same as the input graph. Thirdly, our second result works for directed graphs; this result very interesting on its own since most sparsification algo- rithms 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.
Secondly, we study the bipartite-like clusters in directed graphs. Let T = (Vg. Egg (g) be digraph with weight function w6: E + Rzo- For any vertex u E VVa. we use degomn (w) _ E(w,)EE ua(u,, v) and degin (u) & Eiu,ue (V, u) to express the sum of weights of di- rected edges with u as the tail or the head, respectively. For any S C VVg. we define volour _ Eues degoal (u) and volm(S) & Enes degin( (u). For any two disjoint subsets A, B C Vig we define (A, by
The design of our algorithms is based on several new re- ductions 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 underly- ing 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 demon- strate this, we conduct experimental studies and show that our algorithms can be directly applied to significantly speed up the running time of the the ones presented in (Macgre- gor & Sun, 2021a), while preserving similar output results on both the synthetic and real-world datasets.
2 (A, B) volour (A) + volin (B))
0 B)
(1.2)
where
w " B)
Σ w(u,e) v)
(u,))E uEA.EB
is the sum of the weights of the edges from A to B. For every &e e N. the w-way directed dual Cheeger constant is defined by
(k)) 2
max min (A,, B.), (1.3)
BA.........AA A B&) Isigk
Related Work. Bipartite-like clusters are widely studied in both theoretical computer science and machine learn- ing communities. In theoretical computer science, Trevisan (2009) developed a spectral algorithm that finds a bipartite- like cluster in an undirected graph, and used this to design an approximation algorithm for the max-cut problem. This result is improved by Soto (2015). Liu (2015) studied the relationship between the k-way dual Cheeger constant and the eigenvalues of the normalised graph Laplacians, and developed Cheer-type inequality.
where the maximum is taken over all the possible k pairs of subsets (A1, BI)....... (As. BR) satisfying A, n A, = 9, B, A Bj = A, n B, = 0 for different i,j E [k]] A Bi + for any E [A]. By definition, a high
value of pa (k) implies that T contains k bipartite-like clusters (A1, B.)..., (Ap. B&) such that most edges with their tails in A; have their head in B, and conversely most edges with their head in B; have their tail in A,. We prove that, when & presents a structure of k bipartite-like clus- ters with respect to (A)), this structure can be represented by a sparse graph G+ with Ö() edges, and &H can be con- structed online in nearly-linear time:
In the machine learning community, bipartite-like clusters are employed to model highly-correlate data items of dif- ferent types, and algorithms finding these clusters are stud- ied in different settings. Andersen (2010), Li & Peng (2013) and Macgregor & Sun (2021a) presented local al- gorithms that find bipartite- like clusters, and Macgregor & Sun (2021b) presented an algorithm that finds bipar- tite components in hypergraphs. Cucuringu et al. (2020) proved that densely connected clusters in a directed graph can be uncovered through spectral clustering on a complex- valued Hermitian matrix representation of directed graphs.
Theorem 2 (Result for directed graphs). Let ? (Vg,Lig, wx) be a directed and weighted graph of m edges, and assume that & contains is directly bipartite-like clusters (A1, B1)...., (Ak, Bk) with respect to Pra Then, there is an algorithm that runs in ((m) time and computes a sparsifier G² = (Vz, F C &rrg. i) such that
2

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Neumann & Peng (2022) designed sublinear-time ora- cle which, under a certain condition, correctly classified the membership of most vertices in set of hidden planted ground- truth clusters in signed graphs.
For any symmetric matrix A R let (1 S X²(A) s... A (A) be the eigenvalues of A. For ease of presentation, we always use 0 = Àι S X2 S .... S An S 2 to express the eigenvalues of LG. with the corresponding orthonormal eigenvectors f1, ... ; With slight abuse of notation, we use LG for the pseudo-inverse Lg. i.c.
;
Our work relates to finding clusters in disassortative net- works (Moore et al., 2011; Pei et al., 2019; Zhu et al., 2020), although most existing techniques are based on semi-supervised and global methods. Our work is also related to designing graph sparsification algorithms, e.g.. (Spielman & Teng, 2011; Batson et al., 2012; Cohen et al., 2017; Lee & Sun, 2017; 2018). We highlight that, while a spectral sparsifier preserves the cut value w(S, V S) be- tween any vertex set S and its complement V S.S. our algo- rithms' output preserves the cut value (A; B,) for pairs of vertex sets A; and B;. Moreover, our algorithms are much easier to implement, and work for directed graphs.
n
T.T..
Note that when G is connected, it holds that X2 > 0 and the matrix LG well defined. We sometimes drop the subscript when is clear from the context.
For any R define ||=]|| - M R we define
VE x and for any
|Mx
| = max ZER")(O)
|||||
2. Preliminaries
Graph expansion and Cheeger inequality. For any undirected graph G, the expansion (or conductance) of any non-empty subset S V in G is defined
In this section we list the notation and preliminary results used in the analysis.
Matrix Representation of Graphs. We always use G (V, E, w) represent an undirected and weighted graph with vertices and weight function E - Rz0- The de- gree of any vertex is defined as (u) = Enne w(u, v), represents that u and v are adja- cent, i.e., {u, v} E EGG). The normalised indicator vector of any C V is defined by
(G A WG(S,
vola(S)
where $ is the complement of S. We call subsets of vertices
S1, S2, ... .A k-way partition of G if S: * 0 for all 1 S i S k. S; n = 0 for i + j and U S. = V. For any &o E N, the k-way expansion constant is defined as
where the notation
dc((s), (c(k) S1.82 St 1sick
min
do(v)
xs(u)= V vS)
where the minimum is taken over all possible k-way parti- tions of G. Lee et al. (2014) proves the following higher- order Cheeger inequality:
v E S, and (s( = otherwise. Let Ag be the adjacency matrix of G defined by (Ag)u, w(u, e) if (u,u) E E(G), and (Ag)u,
Lemma (Higher-order Cheeger Inequality, (Lee et al., 2014)). It holds for any undirected graph G of vertices and integer 1 < k S n that
otherwise. The degree matrix De of G is diagonal matrix defined by (De)u, da(u), and the normalised Laplacian of G is defined by
Ax/2 S PG (k) S CK2 V
T-= DD Ag AG
where C is universal constant.
We can also write the normalised Laplacian matrix with re- spect to the indicator vectors of the vertices: for each vertex v, we define an indicator vector Xv E R" by (u)
Generalising this, Liu (2015) proves the following higher- order dual-Cheeger inequality:
1 va, if = and (u) = 0 otherwise. We further define be = Xa - Xv for each edge e = {u, v), where the orienta- tion of is chosen arbitrarily. Then, we have
Lemma 4 (Higher-order dual-Cheeger Inequality, (Liu, 2015)). It holds for any undirected graph G of n vertices and integer 1 S k S n that
(2- 22-An-441/22
pa(k)) & Ck3 /2- An-
La =
Σ == (u.lEE
w(u, u) b.
where C' is universal constant.
The higher-order dual Cheeger inequality can be viewed as quantitative version of the fact that An-k+1 = 2 if and only has at least bipartite connected components.
We also define
To A 1 D 1/2 De 1/2
3

---

Online Sparsification of Bipartite-Like Clusters in Graphs
3. Proof of Theorem 1
Let ((A,, B,);== be the optimal clusters corresponding
p(k). Then, we have for every S i S k that
In this section we present a nearly-linear time sparsification algorithm such that every bipartite-iiz like cluster in an undi- rected graph G is approximately preserved in the sparsifed graph G", and sketch the proof. Our result is as follows:
pa(k) S S0 (i) = 2wo B,) vola (A; U B,)
which implies
Theorem 5 (Formal Statement of Theorem I), There exists a nearly-linear time algorithm that, given an input graph G = (V, E, w) with (k) 2 log for constant some k, = (V, F C E, w) with [F] = =0 2-log" n edges such that the fol- 2-
(k(kk) volc(A,
Σ wc(u,e) v). (=(u,o) HEAL.EB
1
with high probability computes sparsifier G²=
Applying the Chebyshev's inequality, we have for any con- stant E R that
lowing hold: (1) PG- = (pac(k)): (2) >x+1(TG-)= (J)))
E
P PIX E[X]| 20 -.C]
S 2 E[X]²
The first statement of Theorem 5 shows that the & bipartite-
like clusters of G is approximately preserved in G", and together with Lemma 4 the second statement shows that the number of bipartite-like clusters in G and G is the same.
2 (2-2-
2. C. log""g n [k)3
max c=lu,0] (da (u) + do(u)) MEA,,EB
Algorithm. Our algorithm is similar with (Sun & Zanetti, 2019) at high level, and is based on sampling edges in G with carefully defined probabilities. Formally, for an in- put undirected graph G = (V, E, wc). the algorithm starts with G (V, 0, ū)) and samples every edge u ~ v in G with probability pe - pu(u)) + (u) (a(u)-Pell where
walu, v).
vola(A, U.)²
(u,0)
Mc VEB
Since volc(A, ='NE,, da(u)+ da(v) and da(u) = Euvo we ww u), we have
max (do(u) + do(()) e=(u,0
Pa(v)
uc A.
C. log" e min { (wolu,)) da(u)- (2 Xn- .) (3.1)
S Σ dolu) + dolv) = volo(A. <ol(u))ool((AUBB)
ueA.
vEB,
for some constant C. For every sampled edge e = {u, v). the algorithm adds e graph G", and sets (a-(e) (e) wc(e)/Pe- Notice that, the choice of C' only changes the sampling probability by constant factor, and doesn't 't in- fluence the asymptotic order of the sampled edges. More- over, in practice we usually treat C-log"p a as Olog' n) for 2-An-x a constant c, and this only influences the total number of sampled edges and the algorithm's 's running time by a poly- logarithmic factor.
and Σ (u.,) wa(u, & volc(A, U B,). Applying uc UE these gives us that
P E[X] 2 E[X]]
2(2 xn
1
S c² C2.C.log's p(k))2
log
Hence, by the union bound, we have that WH (A, B.) Ω (wa(A,, B,)) for all < i i k. The proof of the sec- ond statement of Theorem can be found in the appendix. Finally, the total number of edges in H follows by the def- inition of sampling probability and the Markov inequality. This completes the proof of Theorem 5.
Proof Sketch of Theorem 5. We first prove that the cut values between A, and B, in G is preserved in H for any 1 15i i k. For any edge variable Y. by Y. wc(u, v)/pe with probability Pe. and Y. = 0 otherwise. By defining X = WH (A,, B,), we prove that [ wa(A, B,) and
{u, v). we define the random
4. Proof of Theorem 2
In this section we present a nearly-linear time sparsification algorithm such that every directed bipartite like cluster in directed graph is approximately preserved in the output sparsifier, and prove Theorem 2. Specifically, for digraph & that contains exactly l pairs of (A1, BI)..., (Aş, B₁) with high values of कH (A,, B,) for every 1 S S h, our
E x
2 - An-k
w(u, ( (dc(u) + +do(v))
Σ
C. log" n
o= (u.0)
uE
4

---

Online Sparsification of Bipartite-Like Clusters in Graphs
objective is to construct a sparse digraph & such that (i) the values of T B,) are high for every S à S k and
Constructing H from G. Notice that, to preserve O B.), the cut values w(A,, B,) between A, and B, need to be approximately preserved in sparsified directed graph; this objective is different from the most graph spar- sification one, which only preserves the cut value between any set S and its complement. To overcome this, we con- struct an undirected graph H such that every bipartite-like cluster defined by B.) in G corresponds to low- conductance set in H. Specifically, for weighted digraph F
(ii) the number of such pairs in G is the same as G. Our
result as follows:
Theorem 6 (Formal Statement of Theorem 2). There is a nearly-linear time algorithm that, given a directed and weighted graph G (Vz. Ez w²) :...)) with n vertices and k directed bipartite-like clusters satisfying م. (k) -1- o1/kk) as input, with high probability computes sparsifier G = (Vz, F C. F such that Pega (k) 2t (Pa (+))- Moreover, the total number of edges in the output graph is nearty-linear in n.
wz), we construct its semi-double cover H (VH, EH, wH) as follows: (1) every vertex has two corresponding vertices U1, E VHH (2) for every edge (u, v) E Eg. we add the edge {ui, 12) in Eg. See Figure 2 for illustration.
Va
Before sketching technique, recall that, for undi- rected graphs, the value of k is proven to be identical for G and G by analysing the eigenvalues of JG and To- and applying the higher-order dual-Cheeger inequal- ity (Lemma 4). However, natural matrix representation for directed graphs could result in complex-vai valued eigen- values, and there is analogue of Lemma 4 for directed graphs. To overcome this, our developed algorithm is based on a novel reduction from a directed graph to an undirected one, and its reverse operation. Specifically, our designed algorithm consists of the following three steps:
b2
d
Figure 2: Illustration of the semi-double cover construc- tion. A directed graph of n vertices (left) corresponds to an undirected and bipartite graph of 2n vertices (right).
Next we analyse the properties of the reduced graph. Let G be directed graph with semi-double cover H. For any S C Vaa, define S1 C VH and S2 C VH by S1 â (uilo E S} and S2 & {v2le E S). A subset S of Vμ is called simple if Kv, [2) n S| z 1 holds for all v E Vzz. The following lemma develops a relationship between flow ratio from B defined by
1. for any input digraph G. the algorithm constructs an undirected graph H such that every directed bipartite- like cluster defined by (A,, B;) in & corresponds low-conductance set in H;
2. the algorithm constructs sparsifier H* of H, such that H and H* have the same structure of clusters;
(A, & (A
(4.1)
3. the algorithm applies the sparsified undirected graph H construct directed graph &² of & that satisfies ن. (k) Ω (P)()))
and (Ai U B2), for any A, B.
Lemma 7. Let & be directed graph with semi-double cover H. Then, it holds for any A,B c Vz that (A, (Ai U B2). Similarly, for any simple set S VH, let A = {u E S} and B = {u u2 E S}. Then, it holds that f (A, B) = QH
See Figure I for illustration.
G (()))(
semi-double cover
(H, (n.pn())
Lemma 7 proves a one-to-one correspondence between any bipartite-like cluster in & and vertex set in H. Building this, we prove that this one-to-one correspondence can be generalised between any l bipartite-like clusters in d and l disjoint vertex sets in H. Moreover, the structure of h bipartite-like clusters a is preserved by a collection of k disjoint vertex sets of low conductance H.
graph sparsification
graph sparsification
())
semi-double cover (H*, (k))
reverse
Figure 1: A commutative diagram of our construction. To construct "² from ,, we construct graphs H and H" and prove the close relationships between G. H, H", and G
Lemma 8. For any directed and weighted graph π (V Eg wa)) and k E N, it holds that
(k((k)
min max Φu (Ct), Ci....C 1Sisk
(4.2)
5

---

Online Sparsification of Bipartite-Like Clusters in Graphs
where the minimum is laken over k disjoint simple subsets of Vn defined by C. = Ai, U Big for 1 sisk.
Hence, there are very few edges between S₁ and S2 for any S C Vn. Without loss of generality, we assume that
20 (S,,
Sparsification of H. Next we construct a sparse repre- sentation of H. denoted by H" such that the k vertex sets low conductance is preserved in H To achieve this, we apply the following result to construct cluster-preserving sparsifier.
WH (S1, S1) + wH S2)
S
for some constant < 1. Simplifying the inequality above we get
WH (1,, + Hy (S2, S2) 2w (S1, S2) 2 (1-d) [m (S1, S1) + wH www. 52)
Lemma 9 ((Sun & Zanetti, 2019)). There exists a nearly- linear time algorithm that, given graph G = (V, E,, w) with l clusters input, with probability at least 9/10, computes sparsifier H = FV. C E,w) with [F] 0((1/>++1) (0-41)-0 -n log n) edges such that the following holds:
Thus, for any not necessarily simple vertex set S Vn we have
ΦH(()= = WH (S
(1) it holds for any S i I k that Φn = O(k
vol(S)
(S.),.) where Si, ",,...,,,, Sy are the optimal clusters in G that achieves p(k); (2) AR+1 (Cn) 120x=+ (Ca)).
wHr( Si) + wH (S2, (S1,
vol(S)) + vol(S2)
wH Si) WH( S2) vol(Si)
Constructing T² from :: Finally, we construct a di- rected graph G from H* such that the original & directed bipartite-like like clusters in T is preserved in G To achieve this, introduce the following reverse semi-double cover:
2 (1-c) min
vol(S2)
c) min (0 (S1), (S2)),
where the last inequality follows by the median inequality. Thus, for every S C VH, there is a simple set I' C VH such that ΦH (S) 2 (1-c).0u (T). Moreover, for any collection of disijooint sets S1, S2. ... Sk. where S. C VH we have collection of k-disjoint simple sets T1, T2, Tk. where T; C VH. such that
Definition 10 (reverse semi-double cover). Given any dou- ble cover graph H = [ Eu-; WH-) as input, the re- verse semi-double cover of H* is a directed graph G² = (V 1it (+)) constructed as follows:
max ÓH 2 (1 c)
max ÓH (Ti). isis
every pair of vertices u1 and u2 in VH corresponds to a vertex u E Viti
ISISK
Taking minimum over all such collection of k-disjoint sub- sets of Vn gives us that
we add an edge v, to Eg if there is edge [2, E En,, and set (u, = wn- (ur, v2).
min
max (S.)
S S2.S2.- Se 1sisk
= (k( 2 (1
min max (H
One might think that the reverse double cover plays an exact opposite role of the double cover, however is not the case. In particular, while our constructed sub- sets CI,..., Ck in the first step are always simple in H (cf. Lemma 8), the k subsets corresponding pn (k)
T2.72. Th 1SiSk
where in the second half of the inequality the minimum taken over collection of k-disjoint simple subsets of VH. On one hand, rearranging the above inequality we have
are not necessarily simple. As result,
PH 2
min max (T.)).). (4.3)
TI.II.--..I Isick
and on the other hand, since the collection of k-disjoint simple subsets of Vn is a sub-collection of the collection of k-disjoint subsets of VH, we have
min max on = pP C......C Cs 15isk
doesn't hold in general, and there no direct corre- spondence between Cr...., C in H and the directed bipartite-like clusters in G that correspond to (z=
min max 6H (T;) 2 (k()). T. Th .h 1gigk
(4.4)
Thus, combining (4.3) and (4.4), we have
To analyse P (kt), for any set S C Vn we partition the set into two subsets S₁ and S2 defined by S₁ (A,, )B;,) and S2 SS(AA, U B,, ). For example, following Figure 2, if A, = {a, c) and B, = {b, d} and the set S c V4 is
1-c Pm (k) >
min max on (T.) 2 pm
T.. Tr 1sisk
(4.5)
Further, combining (4.2) and (4.5) we have
s = {a,, b, b2, C1, c2). then we have S = {a, c1)
1
and S2 = (2). As A, and B, are densely connected in
1-c (k)(k) S (k( S (H()).
(4.6)
H, there are few edges within A, and B, for < 1 < k.
6

---

Online Sparsification of Bipartite-Like Clusters in Graphs
NS-Oat
Mi+ M5
-0-
M5
Ran Timee (Secodd)
0.375
Biparthennes Ratto
2,
0.393
0.4
0.000
0.25
0.39
300
750
1000
:233
1505
1150
2000
3250
2500
02-
330
750
1000
1250
1500
3720
3003
1250
2592
(a) Runtime comparison
(b) Bipartiteness Ratio comparison
Figure 3: Runtime and bipartiteness comparison between MS and our algorithm by fixing 0.3, 0.1p and varying the number of vertices between 500 and 2, 500 in each partition.
Proof of Theorem 2. Now we are ready to prove The- orem 2. Since T is directed graph with & bipartite- like clusters, the value of (a(
All experiments were performed on HP ZBook Stu- dio with 11th Gen Intel(R) Core(TM) 17-11800H @ 2.30GHz processor and 32 GB of RAM. Our code can be downloaded from http::/github..com// http://hhhh...oo//uuuaon//////ee
(k) is high; together with (4.6), this implies that Ptr(k) = o1). By Lemma 9, we know that there exists a sparsifier H' of H, such that Pa- (k) Olk (k)). Thus, we can conclude that pn- (k) = o(1) Hence, applying (4.6) for G and H*
5.1. Results for Undirected Graphs
we have
Synthetic Dataset. We compare the performance of algorithm with the LOCBIPARTDC algorithm presented in (Macgregor & Sun, 2021a), which we refer to as MS, on synthetic graphs generated from the stochastic block model (SBM). Specifically, we assume that the graph has k = clusters, say C₁, C2, and the number of vertices in each cluster, denoted by nı and n2 respectively, satisfies nı n2. Moreover, any pair of vertices E C, and Cj is connected with probability Pij- We assume that P12
pm- (k) S (k) pH- (4.7)
Finally, using the fact that PH- (k) = o(1), we conclude that P (k:) is close to 1 and hence the structure of & will be preserved in -². Moreover, by the construction of H, and H and & the value of k is preserved.
For the running time, notice that all the intermediate graphs H and H can be constructed locally, and it's sufficient to examine every edge of the input graph & once throughout the execution of the algorithm. This implies the nearly- linear running time of our overall algorithm. Combining everything above above proves Theorem
P21 and P11 1/2 g. where q 0.1p. Throughout the experiments, we leave the parameters and free but maintain the above relations.
Our algorithm sparsifies the underlying graph and simulta- neously applies the MS algorithm. We evaluate the qual- ity of the output (L, R) returned by each algorithm with respect to its bipartiteness ratio defined by B R) 1 TL, R). All our reported results are the average perfor- mance of each algorithm over 10 runs, in which a random vertex from C1 U is chosen as the starting vertex of the algorithm. We generate graphs from the SBM such that q = 0.1p and vary the size of the target set by varying n1 between 500 and 2, 500. In Figure 3, we fix the probability p 0.3 and vary the number of vertices n1 n2 and com- pare both runtime and the bipartiteness ratio between the MS algorithm and our algorithm. One can observe that for a fixed probability p as we increase the number of vertices, our algorithm takes much less time than the MS algorithm and maintains similar bipartiteness ratio with the MS al- gorithm.
5. Experiments
We evaluate the performance of our proposed algorithms on synthetic and real-world datasets. We employ the algorithms presented in (Macgregor & Sun, 2021a) as the baseline algorithms, and examine the speedup of their algorithms when applying our sparsification al- gorithms as subroutines. Notice that, as all the in- volved operations of algorithms can be performed locally, one can run our graph sparsification algorithms online while exploring the underlying graph with a lo- cal algorithm. For ease of presentation. in this sec- tion we call the local algorithm in (Macgregor Sun, 2021a) with our sparsification framework our algorithm.
7

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Table I: Comparison of MS with our algorithm on the Militarised Interstate Disputes Dataset. We use the vertices corre- sponding to the listed countries in the first column as the seed vertex of the local algorithm.
COUNTRY NAME
MS
MS
OUR ALGO.
OUR ALGO.
RUNTIME
BIPARTITENESS
RUNTIME
BIPARTITENESS
USA
0.034
0.292
0,0044
0.285
NETHERLANDS
0.0351
0.307
0,0042
0.281
LITHUANIA
0.0336
0,303
0.0043
0.165
Agar
Alyittin
(Secodai)
Number of Vertices in Each Partioon
Number of Vertiee in Each Partition
(a) Runtime comparison
(b) Flow-ratio comparison
Figure 4: Runtime and flow-ratio comparison between ECD and our algorithm by fixing 1) = 0..7 and varying the number of vertices in each partition from 500 2, 500.
Real-world Dataset. We evaluate the performance of our algorithm on the Dyadic Militarised Interstate Disputes Dataset (v3.1) (Maoz et al., 2019), which records every in- terstate dispute during 1900-1950, including the level of hostility resulting from the dispute and the number of ca- sualties. We construct graph from the dataset as follows: every country represented by vertex; two vertices are connected by an edge with weight 30 if there is war be- tween the corresponding countries, and the two vertices are connected by an edge with weight if the corresponding countries have other dispute which is not part of an inter- state war. We set ? = 0.02 for the MS algorithm, and Ta- ble I compares the performance of the MS algorithm with ours. This shows that our algorithm takes much less time than the MS algorithm and maintains similar bipartite- ness ratio.
the probability of assigning edge is defined by
L
R
9/n1
9
n
R
9/m2
i.e., the probability that there is an edge within the partition is 9/n1 = 9/ n2 and so on. As most of our directed edges are from to R, the value of 7 is high. For our experiments we generate two sets of plots:
We fix the value of γ 0.7 and increase the number of vertices in each partition from 500 2, 500, and compare the runtime of ECD and our algorithm. As reported in Figure 4, our algorithm takes much less time than the ECD algorithm and gives a similar flow- ratio at the same time as we increase the number of vertices.
5.2. Results for Directed Graphs
Synthetic Dataset. We compare the performance of our al- gorithm with the EvOCUTDIRECTED algorithm presented in (Macgregor & Sun, 2021a), which we refer to as ECD, and use the graphs generated from the SBM as the algo- rithms' input. In our algorithm, given a digraph G as input, we sparsify the graph along with generating the volume- biased ESP on G's semildouble cover H. Since the ECD also test our algorithm locally. In this model, look into cluster which is almost bipartite with the bipartition being L and R. We set the number of vertices in L and R to be nı and n2 such that ny = n2 and
We increase the number of vertices in each partition from 500 to 2, 500, increase the value of 1) from 0.7 to 0.9, and compare the runtime of the ECD algorithm and our algorithm. As reported in Figure 5, our al- gorithm runs faster than the ECD algorithm r in- creases.
local algorithm,
Real-world Dataset. Now we evaluate the algorithms' per- formance on the US Migration Dataset (U.S. Census Bu- reau, 2000). We construct the digraph from the dataset as follows: every county in the mainland USA represented
8

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Rued
Eachiatttin
(a) 1 0.7
(b) for 0.8
(c) 1l = 0.9
Figure 5: Runtime comparison between ECD and our algorithm for r7 - 0.7, and 0.9 respectively.
Table 2: Comparison of ECD with our algorithm on real-world datasets. We use the vertices corresponding to the listed
counties in the first column the seed vertex of the local algorithm.
COUNTY NAME
TARGET Ø
ECD
ECD
OUR ALGO.
OUR ALGO. FLOW-RATIO
RUNTIME
FLOW-RATHE
RUNTIME
Maricopa County
0.2
20.661
0.414
13.434
0.417
Virginia Beach City
0.2
15.31
0.546
12.29
0.621
Kanawha county
0.2
9.318
0.33
8.483
0.33
by a vertex; for any vertices j.j. , the edge weight of given by (M,, M2.)/ (MM,) M,,i)l, where Mij is the num- ber of people who migrated from county to county between 1995 and 2000; in addition, the direction of (i,j) is set to be from to if Mrj > Mj otherwise the direction is set to be the opposite. We compare the output ECD and the output of ECD when applying our sparsification algorithm as subroutine. Furthermore, we use the vertices corresponding to different counties the input of the local algorithm ECD. As shown in Table 2, with our developed algorithm the local ECD algorithm achieves roughly the same flow ratio, and our sparsification procedure signifi- cantly 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.
Acknowledgements
The first and third authors of the paper are supported by EPSRC Early Career Fellowship (FP/T00729X/1).
References
Andersen, R. local algorithm for finding dense sub- graphs. ACM Transactions on Algorithms (TALG), 6(4): 1-12, 2010.
Batson, D., Spielman, D. A., and Srivastava, N. Twice- ramanujan sparsifiers. SIAM J. Comput., 41(6):1704 1721, 2012.
Bennett, S., Mihai, C., and Gesine, R. Lead-lag detection and network clustering for multivariate time series with an application to the US equity market. Machine Learn- ing. 111:4497-4538, 2022.
In conclusion, these experimental studies demonstrate that developed algorithms can be directly employed to speed up the running time of existing algorithms that find bipartite-like clusters, and can be widely applied when analysing datasets of various domains. We believe that our developed techniques and algorithms will motivate future and fruitful studies for analysing complex cluster structures of graphs.
Cohen, M. B., Kelner, J. A., Peebles, J., Peng, R., Rao, A. B., Sidford, A., and Vladu, A. Almost-linear-tim algorithms for markov chains and new spectral primi- tives for directed graphs. In Proceedings of the 49th An- nual ACM SIGACT Symposium on Theory of Computing. STOC 2017, pp. 410-419, 2017.
Impact Statement
Concas, A., Fenu, C., Reichel, L., Rodriguez, G., and Yunzi, 7. Chained structure of directed graphs with ap- plications social and transportation networks. Applied Network Science, 7(64), 2022.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences our work, none of which we feel must specifically highlighted here.
Cucuringu, M. Li, H., Sun, H. and Zanetti, L. Hermi- tian matrices for clustering directed graphs: insights and applications. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020.

---

Online Sparsification of Bipartite-Like Clusters in Graphs
He, Y., Reinert, G., and Cucuringu, M. DIGRAC: digraph clustering based on flow imbalance. In Learning Graphs Conference, Proceedings of Machine Learning Research, pp. 21, 2022.
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang. B. Geom-GGN: Geometric Graph Convolutional Networks. In 7th International Conference Learning Represen- tations (ICLR'19), 2019.
Laenen, S. and Sun, H. Higher-order spectral clustering of directed graphs. Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, 2020.
Soto, J. A. Improved analysis of max-cut algorithm based spectral partitioning. SIAM Journal Discrete Mathematics, 29(1):259- 200-28688. 2015.
Spielman, D. A. and Teng, Spectral sparsification of graphs. SIAM J. Comput. 40(():981-1025, 2011.
Lee, J. R., Gharan, S. O., and Trevisan, L. Multiway spec- tral partitioning and higher-order cheeger inequalities. Journal of the ACM, 61(6):1-30, 2014.
Sun, H. and Zanetti, L. Distributed graph clustering and sparsification. ACM Trans. Parallel Comput., 6(3):17:1- 17:23, 2019.
Lee, Y. T. and Sun, H. An sdp-based algorithm for linear- sized spectral sparsification. In 49th Annual ACM Sym- posium on Theory of Computing, pp. 678-687, 2017.
Trevisan, L. Max cut and the smallest eigenvalue. In 41st Annual ACM Symposium on Theory of Computing, pp. 263-272, 2009.
Lee, Y. T. and Sun, H. Constructing linear-sized spectral sparsification in almost-linear time. SIAM J. Comput., 47(6):2315-2333 2018.
U.S. Census Bureau. sus. 20159950000055/ttpp:://ooa census.
United states 2000 cen-
https://web.archive
Li, A. and Peng. P. Detecting and characterizing small dense bipartite-like subgraphs by the bipartiteness ra- tio measure. In 24th International Symposium on Al- gorithms and Compulation (ISAAC' 13), pp. 655-665, 2013.
hww.i////www////// / http:/ec200///////
nov/population
2000. Accessed: January 2021.
Zhu, J., Yan, Y., Zhao, L.., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural net- works: Current limitations and effective designs. In 34th Advances in Neural Information Processing Sys-
Liu, S. Multi-way dual cheeger constants and spectral bounds of graphs. Advances in Mathematics, 268:306- 338, 2015.
tems (NeurIPS 20), 2020.
Macgregor, and Sun, Local algorithms for finding densely connected clusters. 38th International Con- ference Machine Learning, pp. 7268 7278, 2021a.
Macgregor, P. and Sun, H. Finding bipartite components in hypergraphs. In Advances in Neural Information Pro- cessing Systems 34: Annual Conference on Neural In- formation Processing Systems, pp. 7912-7923, 2b.
Maoz, Z., Johnson, L.. Kaplan, J., Ogunkoya, F., and Shreve, A. The dyadic militarized interstate disputes (MIDs) dataset version 3.0: Logic, characteristics, and comparisons to alternative datasets. Journal of Con- flict Resolution, 63(3):811-835, 2019. URL https: //correlateoo fwar. org//
Moore, C., Yan, X., Zhu, Y., Rouquier, J.-B., and Lane, Active learning for node classification in assortative and disassortative networks. In 17th ACM SIGKDD Inter- national Conference Knowledge Discovery and Data Mining (KDD') 11), pp. 841 841-849, 2011.
Neumann, S. and Peng. P. Sublinear time clustering ora- cle for signed graphs. In International Conference on Machine Learning, pp. 16496-16528, 2022.
10

---

Online Sparsification of Bipartite-Like Clusters in Graphs
A. Useful Inequalities
The following inequalities will used in our analysis.
Theorem 11 Sourrat-FFische Theorem), Let A be a n x n symmetric matrix with eigenvalues x S X2 S ... S An-
Then, holds for any < k S that
VT -A..8
A = min
max (ES)(O)
5
y
y A
A
max
min WES)(O) y y
(im(8)=ma k+1
where the maximisation and minimisation are over the subspaces of
Lemma 12 (Bernstein's Inequality). Let X1, X2. ..... Xn be independent random variables such that [X,]] S M for any Isisn Let X Ei=1 Xi, and R Σ E [X]] Then, it holds that
12
P
- - 2 2xxp 2 2RR+ M1
Lemma 13 (Matrix Chernoff Bound), Consider finite sequence } of independent, random, PSD matrices of dimen- sion that satisfy ||x|]| & R. Les Phnin = Amin (E) E; X,)) and Jmmax = Amnax (E X,))- Then, holds that
Amiu
Σx, X2
(1 8)
s.d
(1-5)1
for 8 [0, 1), and
o
Amax
Σx,
2 (1+ +
S dd.
(1+ 872+8
for 8 2 0.
B. Omitted Detail from Section
This section presents all the omitted detail from Section 3, and gives a complete proof of Theorem 5. We first recall that, for every vertex and its adjacent vertex v, the algorithm assigns the edge {u, v} the probability
C. log n (u(v) A min wa(u, u) do(u) (2 An An-k)²
(B.1)
for a large enough constant C' E R>o- The algorithm checks every edge and samples an edge = {u, o} with probability Pe, where
Pe - pu(v) + p.(w) - Pu(v) p.()).
Note that, it is easy to check that satisfies the inequality
(p.( (u)) Sp. S pp) + (u))..
We start with an empty set F and gradually store all the sampled edges in F, which is sampled by the algorithm. Finally, the algorithm returns weighted graph defined by
(V, F, WH), where the weight wH (u, v) of every sampled edge [u,0) E F
wa(u, v)
wH(u,,) v)
Pe
Next, we analyze the size of F. Since
C. log
= 0 log An-
Σ
Σ
wo(u,v) v) do(u) (2 \n-k)
c= [a,v]
11

---

Online Sparsification of Bipartitc-Like Clusters in Graphs
it holds by Markov inequality that with constant probability the number of edges e {u, v) with Pa(v) 2 1 is
n n=log" -----1 - Without loss of generality, assume that these edges are in F, and in the remaining part of the proof we assume it holds for any edge that
C. Cologg n wc(u,v) da(u) (2 xn-k) <1
Then, the expected number of edges in H equals
Σ Pe S
Σ Pu(v) + p2(2)
c [u,u)
e= (u,e}
C log n Σ
w(u,))- (do(u)) + 1
do(o)
(2 An-k) c=(u,0)
0 11 log"
A
and by Markov inequality holds with constant probability that
n log An-k
LF| 0
Now we show that the cut value between A, and B; is preserved for all S S For any edge e {u, we define the random variable Y. by
wG(u,,) v)
with probability Pe.
Ye
Pe
(B.2)
0
otherwise.
Also, we define X =wH(# (Ag, B,), and have that
walu, v)
E[X]=
Σ
E[y.]
Σ
Pe
Pe
fa,e)
c=(ur]
uEA;,
uEA
(B.3)
Σ
wa(u,e) wo(A,, B:).
vEA
Next, we analyse the second moment of the random variable X and have that
w v)
[
Σ
Pe
Pe
(u,uv)
wa(u,v) u)²
Σ
Pe
(=(u.) AENEER
2wo (u, 0)2
Σ
(v) + (u()
(B.4)
(=(u.) HEA.EER
2wo(u, (u, v)²
e=(uv)
(2- An-k)
[Ta(a 2cto)
1
HE AENEB
2 An-
w(u,v) ( (da(u) + do(v))
C. log" n
(u,e) uE PE
12

---

Online Sparsification of Bipartite-Like Clusters in Graphs
where the last step follows by the means inequality. Let ((A,, B= be the optimal cluster where p(k) is attained for graph G. Recall that for every & N, the k-way dual Cheeger constant is defined by
max (k(k) (A1.Ba)o" (A,, 15isk
min (a(A Bt).
Then, we have for every 1 S Kis o that
po(k) I (A, B,) = 2w B³)
vola(A, U
which implies
pk(k) 2
vola(A U B;) -
Σ
v).
(B.5)
e=fu.0]
vEA
Next, by the Chebyshev's inequality we have for any constant E R that
P E 2 E[X]
E[X²]
0² E[X]
2-
Σ (=(u,)) wolu,)) (dalw)tda(e) NEB
G:log"
c² (I e=(mn) wo(u. ) WEA
2-An Gllog"
Σ c=(u,0 wo(u,)) (delw)tdolu) NEA
(B.6)
④. 2. (oolk)
(Pool))
volo U,A,UBB) B.))
Σ e=fu,0 wa(u,, b) (do(u) + do(v))
(2- -)nnk)
HEAL
σ. G. log" PG (k)2
vola (A; U,)2
Σ e=(u,0] wc(u,v) we HEA,
2. (2- -n-
< ② log" (k)2
max e (u.0)
(da(u) + +d(())
WEA..rE.
Since vola (A, = EveA, do(u)) + + EvEB, do(v) and do(u) =E Euvo (u, v), we have
+ + S Σ da(w)= - Σ do(l)
max
e= (u,0)
REA
wEA.
vEB.
= =A,
and
wa(u,v) S vola(A, U B₂).
e= (a AEE
Thus, we have by (B.6) and the assumption of p(k)
lng(nj that
2(2 182-An-1) An-
P||-- - E
E
5 2. C. llog n (kk)22
= 0 log n
13

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Hence, by choosing sufficient large constant e and the union bound, have that
H (A,, B.) 52 (wG(A,, B.)) for all 1 S iisk k.
(B.7)
Next, we show that the degree of every vertex in H is approximately preserved with high probability. Based on the random variable Ye defined in (B.2), we define the random variable Zu by
Z Σ Y
Then, the expected value of Zu is given by
we (w,
E EiZu]
Σ B[Y.] Σ
Pe
Pe
Σ
walu, v) da(u),
and the second moment can be upper bounded by
wor(u, v) Pe wa(u, (u, w)²
2
Σ
E[
Σ Pe
esrmas
We (u, v)²
Pe
Pa(u)
since P. 2 PP()). Now using the value of (v) from (3.1), we have
da(u) - (2 - )n
Σ E EY < Σ w(u, v)²
w(u, v) C. .log" n
du( (2 - An-k)
Σ w)(u,v)
C log 3
de (u) (2 3
xn-
C llog"
n
and for any edge {u, v) we have that
w(u,v) m(u,v)
do(u) (2 - -n-k)
Pe
pu(
C. log
Now, applying Bernstein's 's inequality (Lemma 12), we have
d
P
du (u) - du(u)) 2
2
E [..]
12 -E|Zu]1 >
2
db
exep
(z) a)
dg (2) 4)
C-log"
C-log
C log
2 -xp
B (2 >n-h)
1
m
14

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Hence, it holds by the union bound that, with high probability, the degree of all the vertices in H approximately preserved up to constant factor. This implies that for any subset S V, have
vol (5) θ (volc(S)),
more specifically,
vol U U,) = θ (vola(A, B.)),
(B.8)
sis Thus, combining (B.7) and (B.8) gives us that
H A; B:) = (Aa(Ai, B.))
(B.9)
for all 1 < & k, which implies that
PH (k) 2
min (A, B,) min Ω (A, Siick
isigk
Ω (Da (A:),
where the last equality follows from the fact that {(A,, B:) is the optimal cluster where p(k) is attained for graph G.
Next, we show that the top (n eigennsaaess of Ta are preserved in H. Without loss of generality we assume the graph connected. Since Ic 2T LG by definition, it holds that
A(TG) >nt1-((Ge).
(B.10)
Let
p
(2 ((Co))).ff
and with slight abuse of notation we call P-1/2 as the square root the pseudo-inverse of i.e.
n-k
p-1/2 = Σ (2 X(fc))
Let P be the projection the span of {/1, f2, In-kJ, then
a-k = Σ faf.
if v and Xv(u) otherwise. For each edge {u, v of G we define a vector + X E IR" and a random matrix X. E Ruxa by
Recall that, for each vertex v, the indicator vector X T is defined by Xo(u) vdc(2)
wH((,,) P- P-11 1-12 if (u, v) is sampled by the algorithm, otherwise.
X.
(B.11)
0
Then, it holds that
Σx. Xx
Σ
wn(u,,) p-11/2 g.g. 1p11/2g.077 PP122/2 1/2
cEE
c=(ue]er
-p11/2
Σ
wn(w,, v) gogd p p-1/2
(u
-p-1/2 1/2
15

---

Online Sparsification of Bipartite-Like Clusters in Graphs
where
JH
Σ (H( gege
the signless Laplacian matrix of H normalised with respect to the degree of the vertices the original graph G. We will now prove that, with high probability the top n - h eigenspaces TH and To are approximately the same. We first analyse the expectation of EesE Xe, and have that
E
Σ X
E
Pe wH(u,,) v) PD-1/2 .p-1/2gegtPP P 1/2
LEEE
E=(a,)EB
w
Σ [uM)ER
p-112 -1/2 P p-1122 1/2 go p
Pe
Pe.
= =P-1/2
Σ wc(u,) gege
p-1/2
(F.U)EF
P Jo-1/2J6PP-1 1/2
Σ = i=
Moreover, for any edge e = (u.u} E E sampled by the algorithm, we have
1/29. wa(u,) P ge
|xeell s wn (u, v) 9.p-1//2p hpp-1/2p112gg
Pe
WG v)
2 An-k 11ge|1
Pe 2wa(u, v)
do(u) + da(v)
2 - An-k (1) + (T)
2
C log
where the second inequality follows by the min-max theorem of eigenvalues. Now we apply the matrix Chernoff bound (Lemma 13) to analyze the eigenvalues of Eeer X₂. Following Lemma 13 we set the parameters as follows:
Pmax = Amax
Σ
Xe
= Amax (P) = 1,
LeE F
2
(B.12)
R
and
C logg
3
8
2
Then using the Matrix Chernoff bound (Lemma 13), we have
C-log
P
Amax
Σxe
Xe
n
ea
0
1.52
n
LEE
for some constant C: this implies that
P
Amax
Σ
X Xx
3 = 1 0
(1)
1
(B.13)
n
FEE
the other hand, since E Matrix Chernoff bound (Lemma 13), we get
|EEER X.] P. we have Mmin = 1 and hence keeping R and & the same as above, using the
Co
P
Amin
Σx. Xe
< n
e
=
1
2
0.5+
n3
kEEF
16

---

Online Sparsification of Bipartite-Like Clusters in Graphs
this implies that
P
Amin
Xx Xe 2
0
1
(B.14)
n23
KEE
Combining (B.13), (B.14) and the fact that EeEE non-zero x I2t $1; ... ffn=)) } that
Xe = P 1-111211 J/ p-11111/
1/2 with probability 1 -00 (g:3) it holds for any
rTP 1/2 xTp-1/2 JHP x/2xx p-1/21/x
1 3 22' 2
(B.15)
xx
Let = P-1//2,, x, and we rewrite (B.15) as
The PTP
JT yTy
y yTPy
1 3 2
Since dim f2, ... fn==)) = - k, there exist n k orthogonal vectors whose Rayleigh quotient with respect TH is ((n fG)). Hence, by the Courant-Fischer Theorem (Theorem 11) we have
1 X21 LG) S Ax+1(TH)) S AnI La)
3
(B.16)
2
By the definition of J/r- DG
1/2 1/2 (Dh An) DG 112, we have
Jh D (Dh + An) 1//22 1/2
D
1/2 (Da" In 122 1
Hence, we set y = 12 DH 1/2 x for any x E g" and have that
xT. DD.
1/2 (Dd²
Th 1//2)
D 1/21/2
T JHæ
xT
(B.17)
TT THI y
1
T T
x 2
yT y
where we use the fact that the degree of a vertex differs by constant factor between H and G. Similarly, we also have
IT. IH x
8 JH
(B.18)
xT 2
Let C Ra be (k + dimensiioal subspace of R satisfying
TT In xT
Ax+1(Tn) max ==0,
and T= " Since D 1/2 has full rank, T is also a (k + 1)-dimensional subspace of R".
Hence, by the Courant-Fischer Theorem (Theorem 11) and (B.,7), we have that
yT TTr y
Ac+1 (TH)
min dim(S)k41
VES
yT y
yT Tir
< max vET((0)
(B.19)
TT. y
xT TH
2 max (ET((0) IT
2 >x+I(JH).
17

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Next, using (B.16) and (B.19), have
Ax+1(TG) & )x+1(TH) 2- 22- Ax+I(TH),
which implies that
(x+1((G)) S (TH)
(B.20)
Similarly, let U C I be an (n --) dimensionnll subspace of R" satisfying
IT.JH
Au+ 1 (Jn)
min #00,zEU
x
and Ū = (D' x EUJ. Since D/ DH 1/2 has full rank, U is also (n dimeensoio subspace of TR..
Thus, using the Courant-Fissoe Fischer Theorem (Theorem 11) and (B.18), we have
y I' y
{x+1(TH)=
max 8 dim(S)=n-k
min VE
yT
y TH y
min
(0)
VT
(B.21)
xT (2I LH)
2
min 3 xEU)(O)
xt
dEt1 (Jt).
Next, by (6) and (B.21) we have
2
3 Ax+1(TH) S (4H)((H))) S Ast1(Ja),
3
which implies that
)x+1(TH) S >x+1(Ja).
(B.22)
Thus, combining (B.20) and (B.22) we have
9 4 A++1(Ja) S Ax+1(TH) S A+t1 (JT),
Hence, the the top n eigenspaces of Tg are preserved in Th. This proves the second statement the theorem.
C. Omitted Detail from Section
In this section we list all the proofs omitted from Section 4.
Proof of Lemma 7. The proof follows from (Macgregor & Sun, 2021a), which proves the result for undirected graphs. We include the proof here for completeness. Let S = A₁ U Bg in H, then
(H(A B₂) = (H( = " V (S)
vol
vol 2w
volH (S)
2wH (S,
(C.1)
volH
2w (A, B)
1 volom (A) + volin(B)
= (A,
This proves the first statement the lemma. The second statement of the lemma follows by the similar argument.
18

---

Online Sparsification of Bipartite-Like Clusters in Graphs
Proof of Lemma 8. By definition, have that
-(1,
(C.2)
and this implies that
Pa(kk
max
min & (Ai, Bi)
(1 (A.. B.) 1SiSk
min (1 - & (A,, B.))
max
B........o (Ag. B.) ISisk
min
max ( (A, B.) ISiS
B....
min max OH (C;), Cr....Ca ISiE
where the second line follow by (C.2), and the last one follows by Lemma and C; = A,, Big
19


Reviews:
[{"review_id": "wv0jCz2YiZ", "reviewer": "Reviewer_Mk9R", "summary": "This paper studies the problem of finding bipartite-like clusters in both directed and undirected graphs. The authors propose a novel graph sparsification algorithm that can be implemented online and preserves the structure of bipartite-like clusters.  The main findings are theoretical results proving that their algorithm, which runs in nearly-linear time, produces a sparse subgraph with $\\tilde{O}(n)$ edges that maintains the key bipartite-like cluster properties of the original graph. The main algorithmic idea is to perform a specific type of edge sampling based on the dual Cheeger constant and degrees. For directed graphs, a reduction to an undirected \"semi-double cover\" graph is introduced before sparsification, and a \"reverse semi-double cover\" operation is used to transform the sparsified undirected graph back into a directed one.  The authors also demonstrate empirically that their algorithm significantly speeds up existing local clustering algorithms while preserving the quality of the results.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and such detailed report. Here is our response to the raised questions:\n\n**Response to _Other Comments Or Suggestions:_** \n\n>Consider explicitly mentioning what do you mean by online in the paper.\n\nOnline in our setting is more relevant to online algorithms and, with the degree oracle for the whole graph, our algorithm decides whether to keep every online arriving edge in a sparsifier or not without the global information of the graph. We will make this clearer in the next version of the paper. \n\n>Page 2, line 60: \"since most sparsification algorithms are only applicable for undirected graphs\", did you mean directed graphs?\n\nNo. We do mean \"undirected graphs\" in this specific place, and most sparsification algorithms are indeed only applicable for undirected graphs.\n\n>Explain better how do you use the SBM model to generate bipartite graphs. The way it is described it seems to be generating non-bipartite graphs.\n\nWe explained the SBM model on Lines 354- 388 (left) for undirected graphs, and on Lines 374-383 (right) for directed graphs. The reviewer is right that indeed we use SBM to generate non-bipartite graphs. However, since vertices in the same cluster are connected with much lower probability, our generated graphs are _almost bipartite_. As shown from the experiments, our algorithms are able to find the two partitions of the clusters. Notice that the our task becomes trivial if the underlying input graph is a bipartite graph. In the next version of the paper we'll better explain this part.\n\n>Give some intuition on the bipartiteness ratio and the flow-ratio used in the experiments. \n\nTwo clusters $A$ and $B$ with a low bipartiteness/flow ratio corresponds to the case that most edges leaving vertices in $A$ (resp. $B$) will go to $B$ (resp. $A$), and in comparison there are fewer edges inside $A$ and $B$. The objective for finding bipartite clusters is to approximately find the sets $A$ and $B$. We prove that this task can be achieved with easily implementable sparsification algorithms. Our developed algorithms can be used to speed up the running time of the overall algorithm framework for finding two clusters. \n\n**Response to _Questions For Authors:_** \n\n>Could you elaborate more on the practical implications of the lower bound restriction on the dual Cheeger constant ($\\overline{\\rho}_G(k)\\geq 1/\\log n)$)? Are there specific types of graphs or applications where this condition is likely to be met or not met? How does the algorithm's performance degrade as $\\overline{\\rho}_G(k)$ approaches this lower bound?\n\nA graph with $\\overline{\\rho}_G(k)\\geq 1/\\log n$ implies that $G$ has at least $k$ mutually disjoint $A_i$ and $B_i$ such that \n$$\n\\frac{2w(A_i, B_i)}{\\mathrm{vol}(A_i\\cup B_i)} \\geq \\frac{1}{\\log n};\n$$\nthat is, most edges adjacent to vertices in $A_i\\cup B_i$ are between $A_i$ and $B_i$, and $A_i$ and $B_i$ forms an _almost_ bipartite graph. \n\nIn practice, this condition are usually met when we study $k$ pairs of vertex groups that are densely connected. Our experimental results on the Interstate Disputes Dataset and the Migration Dataset are two good examples. \n\nOur sampled edges are inversely proportional to $\\overline{\\rho}_G(k)$. The smaller the value of $\\overline{\\rho}_G(k)$, the more sampled edges needed in order to achieve the proved guarantee. We'll make it clear in the next version of the paper.\n\n>Could you do the extra effort and add an experiment for graphs with a higher number of clusters in the SBM model? Given that the algorithm by (Macgregor & Sun, 2021a) stops once it finds a good cluster, doesn't this mean it could find subset of a cluster, that I assume you remove from the graph, and it can affect the subsequent clusters that it finds?\n\nIn the next version of the paper, we will add an experiment for graphs with more number of clusters. The algorithm by Macgregor & Sun is a local one. If we want to find $k$ pairs of clusters, several other algorithms can be used to achieve this objective. \n\n>Could you explain why it doesn't make sense to compare to spectral sparsifiers in practice?\n\nIn our point of view, it doesn't make sense to compare our result to spectral sparsifiers for 3 reasons:\n\n1. Our focus is to construct a sparsifier which preserves the cut values $w(A_i, B_i)$ for $k$ pairs of $A_i$ and $B_i$. A spectral sparsifier only preserves the cut values between any vertex set $A$ and _its complement $V\\setminus A$_. Hence, a spectral sparsifier doesn't achieve our target;\n\n2. Our algorithms work for both undirected and directed graphs, but a spectral sparsifier only works for undirected ones.\n\n3. Our work is easy to implement, but most algorithms for constructing spectral sparsifiers are based on Laplacian solvers or complicated expander decomposition schemes making it difficult to implement. \n\nWe have tried to address all of your questions within the word limit. We'll be happy to answer any other questions during the discussion phase.", "claims_and_evidence": "The main claims are well-supported by theoretical evidence (proofs of Theorems 1,2 and 5) and experimental evidence.\n\n* Undirected Graphs:  The sparsified graph G* preserves the k-way dual Cheeger constant (and hence the bipartite-like cluster structure) and has $\\tilde{O}(n)$ edges (Theorem 1/5). The proof is sketched in Section 3, while the remaining details are shown in Appendix B.\n\n* Directed Graphs:  A similar result holds for directed graphs, using the semi-double cover construction (Theorem 2). The proof is sketched in Section 4, with the remaining details in the Appendix.\n\n* Practical Speedup: The authors validate their theoretical findings with an empirical evaluation showcasing that the sparsification algorithm speeds up existing local clustering algorithms in practice.  The evidence is experimental results on both synthetic and real-world datasets.\n\nThe claims seem strong and supported by sound evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate.\n\n* Sparsification: Using graph sparsification to accelerate clustering is a sensible approach.  The specific sampling scheme based on the dual Cheeger constant and node degrees is novel and theoretically sound.\n\n* Semi-Double Cover: The reduction from directed to undirected graphs via the semi-double cover is a clever technique to leverage the undirected sparsification algorithm.  The reverse operation is well-defined.\n\n* Empirical Evaluation: The evaluation uses standard metrics, derived from the definition of the problem, to do their experiments. The results are reported over a number of runs. Both synthetic and real-world datasets are used, similarity to (Macgregor & Sun, 2021a).", "theoretical_claims": "I checked the correctness of the proofs for the main theorems (Theorem 1/5 and Theorem 2) as best as possible. I followed the high-level arguments and checked the key steps in the proofs.\n\nThe proofs appear to be mathematically sound and well-structured, leveraging standard techniques appropriately.", "experimental_designs_or_analyses": "I reviewed the soundness of the experimental designs and analyses. The datasets and evaluation criteria follow that of (Macgregor & Sun, 2021a) and is reasonable.\n\nThe experimental design appears sound and the analyses are clearly presented.", "relation_to_broader_scientific_literature": "The paper is well-situated within the broader scientific literature on graph clustering, graph sparsification, and spectral graph theory.  It cites relevant prior work on: Graph Clustering, Graph Sparsification, Spectral Graph Theory.\n\nThe paper clearly distinguishes its contributions from prior work. It emphasizes the novelty of preserving the inter-connection between vertex sets (bipartite-like clusters) rather than just the cut values between a set and its complement. It further outlines the importance of practical sparsification algorithms that can easily be implemented.", "essential_references_not_discussed": "I do not believe there are essential references that are not discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n* Novelty: The proposed sparsification algorithm for bipartite-like clusters is novel and theoretically well-justified.\n\n* Generality: The algorithm works for both undirected and directed graphs, which is a significant advantage. The reduction to the undirected case for directed graphs is clever.\n\n* Efficiency: The algorithm is nearly-linear time, and can be implemented using a local algorithm, making it suitable for large graphs.\n\n* Practical Impact:  The experimental results demonstrate significant speedups for existing local clustering algorithms.\n\n* Clarity: The paper is well-written and clearly explains the problem, the proposed algorithm, and the theoretical and experimental results.\n\nWeaknesses:\n\n* Some concepts and metrics can be explained better (see questions).", "other_comments_or_suggestions": "Consider explicitly mentioning what do you mean by online in the paper. Online as in dynamic algorithm, or online as in online algorithms (where decisions are irreversible )? The oracle with the degrees of the nodes is with respect to the current graph, or with respect to the graph after all node/edge insertions?\n\nPage 2, line 60: \"since most sparsification algorithms are only applicable for undirected graphs\", did you mean directed graphs?\n\nExplain better how do you use the SBM model to generate bipartite graphs. The way it is described it seems to be generating non-bipartite graphs.\n\nGive some intuition on the bipartiteness ratio and the flow-ratio used in the experiments. If I understand this correctly, one wants to find clusters with lower bipartiteness (and flow-ratio), so this means that with your sparsification does better compared to running an algorithm on the initial graph?", "questions_for_authors": "Could you elaborate more on the practical implications of the lower bound restriction on the dual Cheeger constant ($\\overline{\\rho}_G(k) \\geq 1/ \\log n$)? Are there specific types of graphs or applications where this condition is likely to be met or not met? How does the algorithm's performance degrade as $\\overline{\\rho}_G(k)$ approaches this lower bound?\n\nCould you do the extra effort and add an experiment for graphs with a higher number of clusters in the SBM model? Given that the algorithm by (Macgregor & Sun, 2021a) stops once it finds a good cluster, doesn't this mean it could find subset of a cluster, that I assume you remove from the graph, and it can affect the subsequent clusters that it finds?\n\nCould you explain why it doesn't make sense to compare to spectral sparsifiers in practice?\n\nSee also some questions in the comments/suggestions section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PCvhHs2DxK", "reviewer": "Reviewer_s5UQ", "summary": "The paper propose efficient and online algorithms to detect bipartite-like clusters for both directed and undirected graphs. They both are graph sparsifiers that can sparsify the graph into $\\tilde{O}(n)$ edges while preserving the bipartite clusters with high probability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and detailed comments. Here is our response to the raised questions:\n\n**Response to _Experimental Designs Or Analyses_**:\n\n>The speedup is not obvious in figure 3, and the running time fluctuates around 1750 nodes. Some explanations here could be helpful.\n\nThis is a very interesting and meaningful question. Notice that the sampling probability used in our algorithm is defined in Equation (3.1) of the submission. By the assumption of the $k$-way expansion and the higher-order dual-Cheeger inequality, we always set  $C\\log^3(n)/(2-\\lambda_{n-k})$, the quantity involved in the sampling probability, as a fixed constant in the experiment. On the other hand,  by (3.1) the sampling probability of every edge doesn't change linearly with respect to the linear increase of $n$. We believe this is the reason behind the fluctuation shown in Figure 3. We will add necessary explanation in the next version of the paper.\n\n**Response to _Essential References Not Discussed_**:\n\n>The paper \"Algorithmic Tools for Understanding the Motif Structure of Networks\" in ECML 2022 shows by finding square-dense and triangle-sparse subgraphs can lead to bipartite-like subgraphs, and leveraged this idea to detect anomalies in social networks.\n\nThank you for pointing out this reference. Indeed, this paper is closely related to our submission. In the next version of our paper, we will add necessary discussions of this ECML'22 paper and other related works. \n\n**Response to _Other Strengths And Weaknesses_**:\n\n>The problem of detecting communities as bipartite-like structures in graphs is not well-motivated in the paper.\n\nIn the next version, we will expand our Introduction section, and add the following discussion to better motivate our studied problem:\n\nFirst of all, finding bipartite-like structures in a graph is one of the most important problems in theoretical computer science, and is a natural generalisation of the max cut problem; recall that the max cut problem is closely linked to the unique games conjecture. In particular, Trevisan [1] proved that algorithms for finding bipartite-like clusters can be employed to design an approximation algorithm for the max cut problem, and this approach has remained the only combinatorial one for designing approximation algorithms for the max cut problem.\n\nSecondly, the algorithms and their complexities for finding bipartite-like clusters in a graph relate to understanding the top eigenspace of a graph's normalised Laplacian matrix, and this problem is studied separately in spectral graph theory community [2]. This is another indication for its importance.  \n\nThirdly, the problem of finding bipartite-like structures in a graph has been also actively investigated in the machine learning community. For instance, Macgregor and Sun [3] presented local algorithms for finding bipartite-like clusters. With respect to more applied domain, our problem is closely linked to finding clusters in disassortative networks and has been applied in training neural networks, e.g., learning over networks with heterophily [4].\n\n\n>Authors also should highlight that the proposed conductance is not only find bipartite-like structure within the cluster, but also penalizing the connections from the cluster to outside.\n\nThanks a lot for pointing out this. This is an excellent suggestion, and we will better highlight this point in the next version of our paper.\n\n**Response to _Other Comments Or Suggestions_**:\n\n> What if $A_i$ and $B_i$ are not required to be disjoint? In some directed graph problems the \"sender\" and \"receiver\" can be considered as different roles.\n\nIt is a really interesting question, and it seems that our current technique cannot be easily adjusted to handle this situation. We believe that this could be a meaningful question for future work.\n\nWe would like to thank the reviewer once more for these valuable comments. We will implement these suggestions in the next version of the paper.\n\n**Reference**\n\n1. Trevisan, L. Max cut and the smallest eigenvalue. STOC'09. \n\n2. Liu, S. Multi-way dual Cheeger constants and spectral bounds of graphs. Advances in Mathematics, 2015.\n\n3. Macgregor, P. and Sun, H. Local algorithms for finding densely connected clusters. ICML'21.\n\n4. Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS'20", "claims_and_evidence": "The claims are well supported", "methods_and_evaluation_criteria": "The evaluation methods make sense.", "theoretical_claims": "The claims are well supported", "experimental_designs_or_analyses": "The speedup is not obvious in figure 3, and the running time fluctuates around 1750 nodes. Some explanations here could be helpful.", "relation_to_broader_scientific_literature": "The algorithms proposed is highly related to the cluster-preserved sparsifier work from Sun and Zanetti 2019.", "essential_references_not_discussed": "The paper \"Algorithmic Tools for Understanding the Motif Structure of Networks\" in ECML 2022 shows by finding square-dense and triangle-sparse subgraphs can lead to bipartite-like subgraphs, and leveraged this idea to detect anomalies in social networks.", "other_strengths_and_weaknesses": "The problem of detecting communities as bipartite-like structures in graphs is not well-motivated in the paper. \n\nAuthors also should highlight that the proposed conductance is not only find bipartite-like structure within the cluster, but also penalizing the connections from the cluster to outside.", "other_comments_or_suggestions": "What if $A_i$ and $B_i$ are not required to be disjoint? In some directed graph problems the \"sender\" and \"receiver\" can be considered as different roles.", "questions_for_authors": "N.A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MGmwheNqvS", "reviewer": "Reviewer_26Yv", "summary": "In this paper, the authors study study bipartite-like clusters and present efficient and online algorithms that find such clusters in both undirected graphs and directed ones. Experiments on real and synthetic graphs demonstrates that the proposed algorithm can speedup the existing algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer's work and the report. Here is our response to the raised questions:\n\n**Response to _Claims And Evidence_**:\n\n>The title of the paper is \"Finding Bipartite-like Clusters on the Fly\", however, the proposed techniques seems like sparsifier regarding bipartite-like clustering. A more appropriate title may be better.\n\nWe thank the reviewer for the comment. In the next version of the paper, we will update the title to reflect their suggestion.\n\n**Response to _Experimental Designs Or Analyses_**:\n\n>For the synthetic datasets, it is more convincing if more generation models can be used to generate synthetic datasets.\n\nSince SBMs are commonly used models to generate synthetic graphs for clustering algorithms, it's not very clear to us which other generation models the reviewer refers to. If the reviewer has a specific generation model in mind that is suitable for our problem, we'll be happy to add additional experiments to make our work more convincing.\n\n>The size of the datasets used in the paper is unclear.\n\nThe datasets used in our work are the common ones studying the problem, and are the ones used in the previous work, e.g., [3]. Following the reviewer's comments, we will include the size of the datasets in the next version of the paper.\n\n**Response to _Other Strengths And Weaknesses_:**\n\n>W1. The significance to find the bipartite-like clusters in a graph seems weak. It is more convincing if more direct application scenarios can be provided.\n\nWe respectfully disagree with the reviewer's comment on the _significance_ of finding bipartite-like clusters in a graph due to the following reasons: \n\nFirst of all, finding bipartite-like clusters in a graph is one of the most important problems in theoretical computer science, and is a natural generalisation of the max cut problem; recall that the max cut problem is closely linked to the unique games conjecture. In particular, Trevisan [1] proved that algorithms for finding bipartite-like clusters can be employed to design an approximation algorithm for the max cut problem, and this approach has remained the only combinatorial one for designing approximation algorithms for the max cut problem.\n\nSecondly, the algorithms and their complexities for finding bipartite-like clusters in a graph relate to understanding the top eigenspace of a graph's normalised Laplacian matrix, and this problem is studied separately in spectral graph theory community [2]. This is another indication for its importance.  \n\nThirdly, the problem of finding bipartite-like clusters in a graph has been also actively investigated in the machine learning community. For instance, Macgregor and Sun [3] presented local algorithms for finding bipartite-like clusters; the significance of their work is clearly recognised by an ICML'21 oral presentation. With respect to more applied domains, our problem is closely linked to finding clusters in disassortative networks and has been applied in training neural networks, e.g., learning over networks with heterophily [4].\n\nWe hope that the above-mentioned research fields, in which finding bipartite-like clusters has been studied, could convince the reviewer on the significance of the problem. Building on this sequence of research over the past 15 years, our work presents the first algorithms that sparsify the input instances of both the undirected and directed graphs. Hence, we feel that our work is important from this perspective. In the next version of the paper, we will expand the section of related works to better highlight the significance of the problem.\n\n_Additional Comments_: \n\nWe hope that we have answered all of the reviewer's concerns on our work. Given that the reviewer's overall evaluation is mainly due to its significance (instead of flawed proofs or easily obtained theoretical results), we hope that the reviewer can take our response and other reviewers' reports into account when further evaluating our submission. Many thanks.\n\n**Reference**\n\n1. Trevisan, L. Max cut and the smallest eigenvalue. STOC'09. \n\n2. Liu, S. Multi-way dual Cheeger constants and spectral bounds of graphs. Advances in Mathematics, 2015.\n\n3. Macgregor, P. and Sun, H. Local algorithms for finding densely connected clusters. ICML'21.\n\n4. Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS'20", "claims_and_evidence": "The title of the paper is \"Finding Bipartite-like Clusters on the Fly\", however, the proposed techniques seems like sparsifier regarding bipartite-like clustering.  Amore appropriate title may be better.", "methods_and_evaluation_criteria": "1.  The fields of the datasets used in the experiments is limited. It seems more convincing if more datasets from various areas can be used to evaluate the proposed methods.", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "1. For the synthetic datasets, it is more convincing if more generation models can be used to generate synthetic datasets.\n2. The size of the datasets used in the paper is unclear.", "relation_to_broader_scientific_literature": "The proposed method can be used to speedup finding bipartite-like clusters.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Weakness:\n\nW1. The significance to find the bipartite-like clusters in a graph seems weak. It is more convincing if more direct application scenerios can be provided.", "other_comments_or_suggestions": "No", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W4m0W8eIOf", "reviewer": "Reviewer_7SXC", "summary": "The paper studies graph sparsifiers that preserve bipartite-like communities in undirected and directed graphs. The notion of communities is formalized via the bipartiteness ratio and then generalized to $k$ communities in the standard way through $k$-way partitions.\n\nFor undirected graphs, the novel sparsifier is obtained by subsampling from the original graph using a technique similar to one proposed by Sun and Zanetti (2019).\n\nFor directed graphs, the construction is more involved and first constructs an undirected graph which can be sparsified using a result by Sun and Zanetti, and then the undirected sparsified graph can be made directed again.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and detailed comments. Here is our response to the raised questions:\n\n**Response to _Other Comments Or Suggestions_:**\n\n> In Theorems 1 and 2, there are no bounds on the size of the sparsifier. In some sense, they are implicit in the running time, but I think they should be made explicit.\n\nIn the proof of Theorem 3, we proved on Lines 623 of the appendix that the number of edges in our sparsifier is \n$$\nO\\left(\\frac{n\\log^3n}{2-\\lambda_{n-k}}\\right),\n$$\nand the number of edges in our constructed directed sparsifier is dominated by the term above as well. We'll make it clear in the next version of the paper. \n\n> I would appreciate a more comprehensive experimental evaluation on more and larger real-world datasets.\n\nWe agree that a more comprehensive experimental evaluation on our developed algorithms will make our paper considerably stronger. We'll add more experimental results in the next version of the paper. \n\n> Theorem 5 is missing a statement about the running time for constructing the sparsifier.\n\nThe algorithm behind Theorem 5 runs in nearly-linear time in the number of edges of the input graph. We will make it clear in the next version of the paper. \n\n> Theorem 2 appears to be a bit informal and a more formal version of it (similar to Theorem 5 as formal version of Theorem 1) would be a good addition.\n\nIn the next version, we will add a more formal version of Theorem 2, and add it to Section 4. The role of the more formal theorem and Theorem 2 will be similar with Theorem 5 and Theorem 1. \n\n**Response to _Questions For Authors_:**\n\n> How did you set the sampling probabilities in the experiments? How did you deal with the term $\\lambda_{n-k}$, especially for the local algorithms.\n\nOur sampling probability is defined in Equation (3.1) of the submission. By the assumption of the $k$-way expansion and the higher-order dual-Cheeger inequality, we treat $C\\log^3(n)/(2-\\lambda_{n-k})$ as $O(\\log^c(n))$ for a constant $c$. This will only influence the total number of sampled edges and the algorithm's overall running time by a factor of $\\log^c(n)$. We employed this trick in our experiment, and will state this in detail in the next version of the paper.\n\n> For the Lithuania dataset it seems like the gap in bipartiteness ratio between the two algorithms is relatively large. Do you have a justification for this?\n\nThis is a very interesting observation. We think this dues to the fact that, while we apply different seed vertices as the input of the local algorithm and the algorithm returns the output clusters of potentially very different sizes, we employ the same sampling probability to construct a sparsifier. As such, the bipartiteness ratios returned by our algorithm and the MS algorithm could scale differently. \n\nWe would like to thank the reviewer once more for these insightful comments.  We will implement these suggestions in the next version of the paper.", "claims_and_evidence": "There is good evidence for the theoretical claims, including full proofs in the appendix of the submission.", "methods_and_evaluation_criteria": "Generally they make sense, but I think the experiments could be more comprehensive.", "theoretical_claims": "I did not check the proofs in detail.", "experimental_designs_or_analyses": "- The experiments should contain a detailed discussion how the sampling parameters were set. This seems to be missing at this point. This is particularly important since the theoretical sampling probabilities contain terms like $\\lambda_{n-k}$ and it is not obvious how this will be computed (I guess using power iteration? But then what do you do for local algorithms – see also next point.).\n- I was surprised that for both undirected and directed graphs only a single algorithm was used for the evaluation of the sparsifier. Additionally, I was surprised that only a local algorithm was used when evaluating the sparsifier for undirected graphs.\n- The graphs used in the experiments are relatively small, never containing more than 5000 nodes for the synthetic datasets. For the real-world datasets I am not sure about their exact size, but the running times suggest that they are also rather small.", "relation_to_broader_scientific_literature": "I think the key references are cited.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "The biggest strength of the paper are the theoretical results which are interesting and non-trivial to obtain. The paper could be improved with a better experimental evaluation, though. Overall, I think the positives outweigh the negatives, given that this is mostly a theory paper.", "other_comments_or_suggestions": "- In Theorems 1 and 2, there are no bounds on the size of the sparsifier. In some sense, they are implicit in the running time, but I think they should be made explicit.\n- I would appreciate a more comprehensive experimental evaluation on more and larger real-world datasets.\n- Theorem 5 is missing a statement about the running time for constructing the sparsifier.\n- Theorem 2 appears to be a bit informal and a more formal version of it (similar to Theorem 5 as formal version of Theorem 1) would be a good addition.\n\n**Update after rebuttal:** The authors have given a thorough reply to my comments and I have thus increased my score. I will appreciate when the authors discuss the choice and impact of the sampling probability thoroughly in their experiments.", "questions_for_authors": "- How did you set the sampling probabilities in the experiments? How did you deal with the term $\\lambda_{n-k}$, especially for the local algorithms.\n- For the Lithuania dataset it seems like the gap in bipartiteness ratio between the two algorithms is relatively large. Do you have a justification for this?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of identifying bipartite-like clusters, where two sets of vertices are densely connected, moving beyond traditional conductance-based clustering. The authors present novel, nearly-linear time online sparsification algorithms for both undirected and directed graphs that preserve these bipartite-like cluster structures. Experimental results on synthetic and real-world data demonstrate the effectiveness and significant speedup achieved by incorporating these sparsifiers into existing clustering algorithms.

This paper presents a valuable contribution and would be a good addition to the ICML program. Its core strengths lie in the proposed sparsification algorithm for bipartite-like clusters is novel and theoretically well-justified, addressing an increasingly important aspect of graph clustering. A particularly strong point is that the algorithm works for both undirected and directed graphs, which is a significant advantage, broadening its applicability. Furthermore, the algorithm is nearly-linear time, making it practical for large datasets. A minor weakness is that it would be nice to have additional motivation on studying the problem on bipartite graphs; while examples are given, slightly expanding on the significance and application domains could further enhance the paper's impact.
Decision: Accept (poster)