A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
Authors: Ranran Shen
Pan Peng
Venue: NeurIPS 2023 poster (2023)
Keywords: Sublinear-time algorithms
Spectral Clustering
Graph Clustering
Random Walks

Abstract: We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain $k$ latent clusters, each characterized by a large inner conductance (at least $\varphi$) and a small outer conductance (at most $\varepsilon$). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consistent with a $k$-partition that is close to the ground-truth clustering. Previous oracles have relied on either a $\textrm{poly}(k)\log n$ gap between inner and outer conductances or exponential (in $k/\varepsilon$) preprocessing time. Our algorithm relaxes these assumptions, albeit at the cost of a slightly higher misclassification ratio. We also show that our clustering oracle is robust against a few random edge deletions. To validate our theoretical bounds, we conducted experiments on synthetic networks.

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
Ranran Shen"
Pan Peng" ppengoustc. edu cn
ranranshen@mail, ustc. ustc.edu. cn
Abstract
We address the problem of designing sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain & latent clusters, each characterized by large inner conductance (at least (p) and small outer conductance (at most E). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consistent with a k-partition that is close the ground-truth clustering. Previous oracles have relied on either a poly(k) log gap between inner and outer conduc- tances or exponential (in k/=) preprocessing time. Our algorithm relaxes these assumptions, albeit at the cost of slightly higher misclassification ratio. We also show that our clustering oracle is robust against a few random edge deletions. To validate our theoretical bounds, we conducted experiments on synthetic networks.
1 Introduction
Graph clustering fundamental task in the field of graph analysis. Given a graph G EV and an integer k; the objective of graph clustering is to partition the vertex set V into k disjoint clusters : .i....: Ck- Each cluster should exhibit tight connections within the cluster while maintaining loose connections with the other clusters. This task finds applications in various domains, including image segmentation [ and bio-informatics 22
community detection [32 12..
modularity maxi- mization (26), density-based clustering [0], can be computationally expensive, especially for large datasets. For instance, spectral clustering is significant algorithm for solving the graph clustering k-dimensional
However, global graph clustering algorithms, such as spectral clustering 277
problem, which involves two steps. The first step is to map all the vertices Euclidean space using the Laplacian matrix of the graph. The second step is to cluster all the points in this k-dimensional Euclidean space, often employing the k-means algorithm. The time complexity of spectral clustering, as well other global clustering algorithms, is poly(n), where = [ denotes the size of the graph. As the graph size increases, the computational demands of these global clustering algorithms become impractical.
Addressing this challenge, an effective approach lies in the utilization of local algorithms that operate within sublinear time. In this paper, our primary focus is on a particular category of such algorithms designed for graph clustering, known as sublinear-time spectral clustering oracles [30 [4] These algorithms consist of two phases: the preprocessing phase and the query phase, both of which can be executed in sublinear time. During the preprocessing phase, these algorithms sample subset of vertices from V, enabling them to locally explore a small portion of the graph and gain insights into its cluster structure. In the query phase, these algorithms utilize the cluster structure learned during the preprocessing phase to respond to WHICHCLUSTERIC... queries. The resulting partition
School Computer Science and Technology, University of Science and Technology China, Hefei, China. Corresponding author: Pan Peng.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

defined by the output of WHICHCLUSTER .) should be consistent with a k-partition that is close to the ground-trutt trutth clustering.
We study such oracles for graphs that exhibit strong clusterability, which are graphs that contain k latent clusters, each characterized by large inner conductance (at least yp and small outer
conductance (at most E). Let us assume > 0 is some constant. In (30) (see also [ (8), robust clustering oracle was designed with preprocessing time approximately O(yn- poly( Alog )), query
time approximately Olvni poly( <log))) )), misclassification error (i.e., the number of vertices that misclassified with respect to ground-truth clustering) approximately OkknVE). The oracle relied on a poly(k) (t) log n. gap between inner and outer conductance. In [14], a clustering oracle was designed with preprocessing time approximately 2 p poly(log n.) - n2/2++0(e), query time approximately poly( k l n /2+0(e), misclassification error Olog k- =)|Cal for each cluster C,, i [A]] and it takes approximately O(poly(*) ()- n /2+0(() poly n)) space. This oracle relied on a log l gap between inner and outer conductance.
One of our key contributions in this research is a new sublinear- time spectral clustering oracle that offers enhanced preprocessing efficiency. Specifically, we introduce an oracle that significantly reduces both the preprocessing and query time, performing in poly(k (k log n2) - 12+))(((s) time and reduces the space complexity, taking O(poly(k) (oooly(k)n//++000 1/2+0((e), 11//2+00)--ool((logggg n)) space. This approach relies on poly(A) gap between the inner and outer conductances, while maintaining a misclassification error of (ppol((k)) - /3)3 for each cluster C, i E [k]. Moreover, our oracle offers practical implementation feasibility, making it well-suited for real-world applications. In contrast, the clustering oracle proposed in [44 presents challenges in terms of implementation (mainly due to the exponential dependency on k/E)-
We also investigate the sensitivity of our clustering oracle to edge perturbations. This analysis holds significance various practical scenarios where the input graph may be unreliable due to factors such as privacy concerns, adversarial attacks, or random noises [31]. We demonstrate the robustness of our clustering oracle by showing that can accurately identify the underlying clusters in the resulting
graph even after the random deletion of one or few edges from a well-clusterable graph.
Basic definitions. Graph clustering problems often rely conductance as metric to assess the quality of a cluster. Several recent studies (8 9 30 14 (2)) have employed conductance in their investigations. Hence, in this paper, we adopt the same definition to characterize the cluster quality. We state our results for d-regular graphs for some constant d 2 3, though they can be easily generalized to graphs with maximum degree at most d (see Appendix (B).
Definition 1.1 (Inner and outer conductance). Let G = (V, E) be a d-regular nevertex graph. For set S S C S V. we let E(S, C\S) denote the set of edges with one endpoint in S and the other endpoint in C\S. The outer conductance of a set C is defined to be @our((, V) = min The inner conductance of a set C' is defined to be dinn (C) scc,o<ssss 19)
(EC))V)) d[l]
Dour (8, C)
((S.CVS) if | > 1 and one otherwise. Specially, the conductance of graph G is ds$
min scC,0<[s|s
le1
defined to be ((G)=
min CCV.D<
Pout (C, V).
Note that based on the above definition, for cluster C, the smaller the Pout (C, V) is, the more loosely connected with the other clusters and the bigger the (C') is, the more tightly connected within C. For high quality cluster C, we have doue (C, V) < Di (C)(C) 1.
Detinition 1.2 (k-partition).. Let G = (V,E) be a graph. A k-partition of V is a collection of disjoint subsets Cı..... .....,,C Cs such that U C. = V.
Based on the above, we have the following definition of clusterable graphs
Definition 1.3 ((k, sp, -clsttrrtt,) Let G = (V, E) be a d-regular graph. A (k, sp, cluusttrnng of Gs a k-partition of V. denoted by C1,..., , Ck. such that for all E [k), omn 2 4p, Dout (C, V) S e and for all i E [k] one has (k, sp, -ccussetni of G.
[Cal [C, E 0(1. called (k, sp, clucststeee graph if there exists a

---

Main results. Our main contribution is a sublinear settineerrtmmeeeeee spectral clustering oracle with improved preprocessing time for d-regular (k, -.cluttabbee graphs. We assume query access the adja- cency list of graph G, that is, one can query the i-th neighbor of any vertex in constant time.
Theorem Let k 2 2 be an integer. yp & (0, 1). Let G = (V, E) be a d-regular n-vertex graph that admits (k, sp, (...))-custerinng CI...., कe <
k2 -lgu and for all i E [K], S |Ca] T where Y is a constant that is in (0.001, 1]. There exists an algorithm that has query access to the adjacency (llgg))) preprocessing time list of G and constructs a clustering oracle in O(n 0(n2/240(e//"') -polyy 7p
and takes O( 0/-000=-()/ poly( 7 (oly)))oz))) following hold:
klog))) space. Furthermore, with probability at least 0.95, the
1. Using the oracle, the algorithm can answer any WHICHCLUSTER query in O(n
poly( & log ")) time and a WHICHCLUSTER query takes (n 1221/2e0)) poly( k log "og")) 7 ")) space.
74P
Let U, == {x EVE WHICHCLUSTER(G: x) = i).i E [be] be the clusters recovered by the algorithm. There exists permutation [k] + [k] such that for all i E [k), (U=(1) ACil s
0 (/)
Specifically, for every graph G (V, F) that admits k-partition Cı,..., C& with constant in- ner conductance yp and outer conductance < O( (aay( ). our oracle has preprocessing time x n//240((s poly(A: (k: (Ilog n), query time x 1//2+((s) poly(koogg) n), space v 0(n1/200(s//²)
poly(A n)) and misclassification error z (pooy((k) - |C/ for each cluster C,, E [b]] In comparison [30], our oracle relies on a smaller gap between inner and outer conductance (specif- ically (poly(kk logn)). n)). In comparison to [14), our oracle has a smaller preprocessing time and a smaller space at the expense of a slightly higher misclassification error of (poly(kk) eC/ instead of (log l- Ca and slightly worse conductance gap of < O(4² /poly (k)) instead of e < (1p² /log(k)) It's worth highlighting that our space complexity significantly outperforms that of [14] (i.c., ((2//=00()/=') poly( & llog n))) particularly in cases where l: is fixed and takes
exceptionally small values, such as "E for sufficiently small constant term in our space complexity does not depend on e in comparison to the one in [14].
0, since the second
Another contribution of our work is the verification of the robustness of our oracle against the deletion of one or few random edges. The main idea underlying the proof is that a well-clusterable graph is still ollsttusteeabbc (with slightly worse clustering quality) after removing few random edges, which in turn is built upon the intuition that after removing a few random edges, an expander graph remains an expander. For the complete statement and proof of this claim, we refer to Appendix E
Theorem 2 (Informal; Robust against random edge deletions). Let e > 0 be a constant. Let Go be a Let G be graph obtained from Go by randomly deleting edges. Then there exists a clustering oracle for with the same guarantees as presented in Theorem
graph satisfying the similar conditions stated in Theorem [
1.1 Related work
Sublinear-time algorithms for graph clustering have been extensively researched. Czumaj et al. [ proposed a property testing algorithm capable of determining whether a graph is k-clusterable or significantly far from being k-clusterable in sublinear time. This algorithm, which can be adapted to a sublinear time clustering oracle, was later extended by Peng [30] to handle graphs with noisy partial information through a robust clustering oracle. Subsequent improvements both the testing algorithm and the oracle were introduced by Chiplunkar et al. (6) and Gluchowski et al. [14]. Recently, Kapralov et al. [16] [7 presented a hierarchical clustering oracle specifically designed for graphs exhibiting a pronounced hierarchical structure. This oracle offers query access to a high- quality hierarchical clustering at a cost of poly 1/2+0())) per query. However, it is important to note that their algorithm does not provide oracle for flat k-clustering, considered in work, with the same query complexity. Sublinear time time clustering oracles for signed graphs have also been studied recently (25).
The field of local graph clustering framework, the objective is to identify a cluster starting from given vertex within a running time
33
is also closely related to our research. this
3

---

that is bounded by the size of the output set, with weak dependence on n. Zhu et al. 34 proposed local clustering algorithm that produces set with low conductance when both inner and outer conductance are used as measures of cluster quality. It is worth noting that the running times of these algorithms are sublinear only if the target set's size (or volume) is small, for example, at most o(n). In contrast, in our setting, the clusters of interest have a minimum size that is ()(n/k).
Extensive research has been conducted on fully or partially recovering clusters in the presence of noise within the "global algorithm regimes". Examples include recovering the planted partition in the stochastic block model with modeling errors or noise 4
21], correlation clustering on 20 and graph partitioning in the average-cass model [18 20 is important to note that all these algorithms require least linear time to run.
15 24
different ground ground-truth graphs in the semi-random model [2 S
2 Preliminaries
Let G = (V, E') denote a d-regular undirected and unweighted graph, where V := {l.... n Throughout the paper, we use [n] denote
S n. For any two vectors x, R" let (x, = x" x²y y denote the dot product of x and y. For graph G, we let A E gnx* denote the adjacency matrix of G and let D R=x* denote diagonal matrix with D i) = deg(i), where (ig(i) is the degree of vertex i, E [n]. We denote with L the normalized Laplacian of G where
L = D D - A)D 1/2 = - A. For L. we use 0 S \ S S An < 2 7 to denote its eigenvalues and we use u1..... ....... Un
d' R" denote the corresponding eigenvectors. Note that the corresponding eigenvectors are not unique, in this paper, we let ui...... Uh, be an orthonormal basis of eigenvectors of For any two sets S1 and S2, we let S, denote the symmetric difference between S1 and S2.
Due to space constraints, we present only the key preliminaries here; the complete preliminaries will be presented in Appendix A
Our algorithms in this paper based on the properties of the dot product of spectral embeddings, so we also need the following definition.
Definition 2.1 (Spectral embedding). For a graph G (V, F)) with n [V] and an integer 2 & S n, we use L denote the normalized Laplacian of G. Let UN E Ra denote the matrix of the bottom & eigenvectors of L. Then for every x E V, the spectral embedding of x. denoted by fz E R.A is the z-row of U[J which means fz( u,(x). i [k].
Definition 2.2 (Cluster centers), Let G = (V, E) be d-regular graph that admits a (k, e) clustering Ci...., Ck. The cluster center μr of C is defined to be μ4 지.. Exec, Sa, i [k].
The following informal lemma shows that the dot product of two spectral embeddings can be approximated in O(n
pk)) time.
Lemma 2.1 (Informal; Theorem 2, [14). Let G = (V,E) be d-regular graph that admits a (k) CI...., Cs, E
To.. Then for every pair of vertices 2, E V. SPECTRALDOTPRODDCTICC x, 1/2, D) computes an output value Syass in 0(11/240l///") poly(k)) time such that with high probability: (fer (ulapx - (fas fa) <
3²
For the completeness of this paper, we will show the formal Lemma 2.1 and algorithm SPECTRALDDOPRRDUCCTT.OC 1/2, D) in Appendix
3 Spectral clustering oracle
3.1 Our techniques
We begin by outlining the main concepts of the spectral clustering oracle presented in 14 Firstly, the authors introduce sublinear time oracle that provides dot product access the spectral embedding of graph G by estimating distributions of short random walks originating from vertices in G (as
described in Lemma 2. Subsequently, they demonstrate that (1) the set of points corresponding to the spectral embeddings of all vertices exhibits well-concentrated clustering around the cluster center
μls (refer to Definition 2.2). and (2) all the cluster centers are approximately orthogonal to each other.
The clustering oracle in [4 operates follows: it initially guesses the & cluster centers from a set of

---

Figure 1:
The angle between embeddings of vertices in the same cluster is small and the angle between embeddings of vertices in different clusters is close to orthogonal (k =3.
poly(k/s) sampled vertices, which requires time complexity of 220l Subsequently, iteratively employs the dot product oracle to estimate (Sz: 14)). If the value of (Jaz (4.) is significant, it allows them to infer that vertex r likely belongs to cluster C₁.
Now we present our algorithm, which builds upon the dot product oracle in [1. Our main insight is to avoid relying directly on cluster centers in our algorithm. By doing so, we can eliminate the need to guess cluster centers and consequently remove the exponential time required in the preprocessing phase described in [14]. The underlying intuition is as follows: if two vertices, and y. belong to the same cluster C., their corresponding spectral embeddings f. and fy will be close to the cluster center Ms As result, the angle between fa and fy will be small, and the dot product (fa, fy) will be large (roughly the order of O(²)). Conversely, if z and y belong different clusters, their embeddings fa and fy will tend to be orthogonal, resulting in a small dot product (fz, fu) (close to 0). We prove that this desirable property holds for the majority of vertices in d-regular (k, -ccusttrlla graphs (see Figure [ for an illustrative example). Slightly more formally, we introduce the definitions of good and bad vertices (refer to Definition 3.1) such that the set of good vertices corresponds to the core part of clusters and each pair of good vertices satisfies the aforementioned property: the rest vertices the bad vertices. Leveraging this property, we can directly utilize the dot product of spectral embeddings to construct a sublinear clustering oracle.
Based on the desirable property discussed earlier, which holds for d-regular (k:, (p, sp.gscclusterable graphs, we can devise a sublinear spectral clustering oracle. Let G = (V, E)) be a d-regular (k, =)- clusterable graph that possesses (k, ş2, -cluusteri Ci...., C2. In the preprocessing phase, we sample a set 5 vertices from V and construct a similarity graph, denoted as H, on S. For each pair of vertices x, y S, we utilize the dot product oracle from [14] to estimate (fz, fg). If and y belong to the same cluster C₁ yielding a large (fz. fy), we add an edge (I, y) to H. Conversely, and belong to different clusters, resulting in a (fa. fu) close to O,
make modifications to H. Consequently, only vertices within the same cluster Ci(i E [k:) can be connected by edges. We can also establish that, by appropriately selecting 8, the sampling set S will, with high probability, contain at least one vertex from each Ci,... Cs- Thus, the similarity graph H will have & connected components, with each component corresponding to cluster in the ground-truth. We utilize these k connected components, denoted as Si....,
......,,, Sp. to represent CI....,
During the query phase, we determine whether the queried vertex belongs to connected component in H. Specifically, we estimate (fz: fy) for all y E S. If there exists a unique index E [k] for which (fe.Ju) is significant (approximately O )) for all u E S,, we conclude that æ belongs to cluster Ci, associated with S. If such unique index is found, we assign random index i, where i [k)..
3.2
The clustering oracle
Next, we present our algorithms for constructing a spectral clustering oracle and handling the WHICH- CLUSTER queries. In the preprocessing phase, the algorithm CONSTRUCTORACLEGG. k, s,e,, learns the cluster structure representation of G. This involves constructing similarity graph H on a sampled vertex set S and assigning membership labels E to all vertices in S. During the query phase, the algorithm WHICHCLUSTEER(C. x) determines the clustering membership index to which vertex x belongs. More specifically, WHICHCLUSTER(G: 2) utilizes the function SEARCHI l)
5

---

Algorithm 1: CONSTRUCTORACLEG p,
Let 5 1000 and let lo.
2 Let = 0.96(1 - ) d (5)
Sample set S of vertices independently and uniformly at random from V
Generate similarity graph // (5,0)
Let D INTIIALIZEORACLENN
1/2,
for any u. E do = SEECRAALDOTRRODUCTRRACCEEEE 1/22,,,,
Let (fus fe)apx 2 then
Add an edge (u, v) to the similarity graph H
if H has exactly & connected components then
11
Label the connected components with 1,2..... & (we write them as Si,..., , Ss)
Label S with if E S Return and the vertex labeling
13
14
else
15
return fail
to check whether the queried vertex belongs to unique connected component in H. If it does, SEARCHINDEX(H)) f, x) will return the index of the unique connected component in H.
The algorithm in preprocessing phase is given in Algorithm | CONSTRUCTOOAACIEGG.. k, &9,
See Appendix for algorithm INITIALIZEORACLE and SPECTRALDOOPRRODCCTOOAACEE invoked by CONSTRUCTORACLEDS k, p, ?)),
Our algorithms used in the query phase are described in Algorithm SEARCCINNDEX(HI,..2 and Algorithm WHICHCLuSTER(G..r) 2))
Algorithm 2: SEARCHINDEX(HI, (,
for any veriex E S do
Let (Su, fz) = SPFECRALDDOTRODDCCORR.... u, x. 1/2,5,
there exists a unique index S S such that (Sus Sa)apx 2 0 for all S then return index
5 else
return outlier
Algorithm 3: WHICHCLUSTER(C...
preprocessing fhils then return fail
3 SEARCHINDEX(H! H, f) return outlier then return random indexe [k]
else
return SEARCHINDEX(H,E.5
3.3 Analysis of the oracle
We now prove the following property: for most vertex pairs x, y, if xr, y are in the same cluster, then (fz. f,y) rough O () (Lemma 3.4); and if æ, are the different clusters, then (fa. fy.) is close to (Lemma 3.5). We make of the following three lemmas. Due to the limited space, all the
missing proofs will be given in Appendix D
The following lemma shows that for most vertices x, the norm [| is small.

---

Lemma 3.1. Let a E 10. Let k 2 2 be an integer. ip E (0, 1), and & E (0, 1). Let G = (V, be d-regular (k,4,,)) clusserrll graph with [V] n. There exists subset V C V with [ (1-a) such that for all V, holds that llfall2 5 -
We then show that for most vertices x, fa. is close to its center of the cluster containing x.
Lemma 3.2. Let B E (0, 1). Let k 2 2 be an integer, up E (0,1), and E (0, Ler = EV be a d-regular graph that admits a (k. 9, c.lssteriig CI..... Ck with [V] = n. There exists subset
V C V with VV 2 (1 (11-3)(V [V] such that for all x E V, it holds that IIʃ - 12ll2 -
4ks 36"
The next lemma shows that for most vertices x in a cluster C,, the inner product (far p4) is large. Lemma 3.3. Let k 2 be an integer, up (0, 1), and 5-x be smaller than a sufficiently small constant. Let = (V, E) be d-regular graph that admits a (ki, q, --clustiing C1,... Ci...., Ck- Let C2 denote the cluster corresponding to the center po i E [b.]. Then for every Cs i E [k]. there exists subset C. S C, with |C,| 2 (1 & (Cs) such that for all x E Co it holds that (far 2 0.96||p:l12.
For the sake of description, we introduce the following definition.
Definition 3.1 (Good and bad vertices). Let & 2 2 be an integer, o E (0, and for be smaller than a sufficiently small constant. Let G (V, E) be d-regular n-vertex graph that admits (k, (.,).) -llusteingg Ci...., Ck. We call a vertex x E V a good vertex with respect to E (0, 1) and B (0, 1) if E (V n n ( (()), where V is the set defined in Lemma
3.1
V the set as
defined in Lemma 3.2 and C (i E [k)) is the set as defined in Lemma 3.3 We call a vertex x E V a bad vertex with respect to (0, and 3 E (0, 1) if it's not good vertex with respect to a and [3.
Note that for a good vertex x with respect to a E (0,1) and 3 E (0, 1). the following hold: (I)
ll la S V 1 4; (2) lIfe - Pxll2 S
4ke Bdt
I. (3) (fe, Mw) 2 0.96|| 12. For a bad vertex æ with
respect to a E (0, 1) and 3 E (0, 1), it does not satisfy at least one of the above three conditions.
The following lemma shows that if vertex x and vertex are in the same cluster and both of them are good vertices with respect to a and / (a and |3 should be chosen appropriately), then the spectral dot product (Jn, fu) is roughly 0.96- T.TI
Lemma 3.4. Let 2 2, & E 10 and +.x be smaller than a sufficiently small constant. Let G = (V, E) be d-regular n-vertex graph that admits a (k, q, el-cssrte C1,..., Cs. Suppose that x. y V are in the same cluster C, E [k] and both of them are good vertices with respect to
-2vk ( M/3 and 3 2 (1)
(5) Then (fe, fu) 0.96 (1 1VE
Vk
1/6
The following lemma shows that if vertex æ and vertex y are in different clusters and both of them good vertices with respect dot product (fz: fu) is close to O.
and 33 (a and B should be chosen appropriately), then the spectral
Lemma 3.5. Let k 2 2, & E (0,1) and fo be smaller than a sufficiently small constant. Let G = (V, E) be a d-regular n-vertex graph that admits a (k, y, cclusttring C1...., Cy. Suppose that C, y E C₁ (i,j E [k], + j) and both of them are good vertices with respect to Tv (3) and 3 = 2v.. (5) the following holds:
Vk fo <
1/6
2244/4
1/3
V(
AVE 1
SVE.
1
n
2
6
Cjl
Proof of Theorem 1. Now we prove our main result Theorem
Proof. Let s 10k log be the size of sampling set a
(5/2 Recall that we where V. V.V. C. E [M] are 3.2 3.3 respectively. We use B to denote the set of all bad vertices. Then
call vertex bad vertex, if (V) V) u (V) (V UV
defined in Lemma 3.1
we have [B| < (a + 10
(vk-- (5) 1/3
10's
We let S 4vh. (5) + 10
7

---

be the fraction of B in V. Since
72
we have A S 4vK
1/3
10ts 4
S
49-109-
log"
10 log & +
43.105. log² S
72
10 ing =
2y
50.
Therefore, by union bound, with probability at least 1 - K- in S are good (we fixed a 3 = 2/k (15) so we will omit "with respect to a and 8r in the following). In the following, we will assume all the vertices S are good.
= 1-
50 all the vertices
50s
Recall that for i E [k], |C|| 2 x so with probability at least 1 1 (1- 1
$ log
1- A
50k there exists at least one vertex in S that is from C. Then with probability at least 1- 50. for all 1: clusters Ci,..., Ck. there exists least one vertex in S that is from C..
Let = V7 By Lemma 2.1 STW.RAA..DDOPODUUTOO.....EEEEEEE
we know that with probability at least 1 - no0, for any pair of x. E V.
1
y, ç, D) computes an output value (faz fn) apo such noo for all D) computes an output value
that fy)a fu) S 5. So, with probability at least 1o00
8-8
2
pairs y.y S, (fz, fyxapx such that (fer fulapx (fz: S &. In the following, we will assume the above inequality holds for any x,y y E S.
By Lemma 3.4 we know that if x. are in the same cluster and both of them are good vertices, then we VE
have (fzz fu)
0.96(1- 4vE C. n
( (3:) )1/ 2 0.96(1 & 1x=) _ yk
n (55) since |C, S 7
By Lemma 3.5
we know that if xr y are in the different clusters and both of them are good vertices, Lk
then we have (fz. fu) S
(
/6 2241/4
(5) V(+ AVE
+ BYE
Vilio, S
v/
VI
1/6
2 3/4
4vE
- 1/3 + BVE_ l since in 1/3
|C,| for all illis [k]]
x
Recall that 7
<
and 7 E (0.001, 1.. Let 0.96(1 452 nk
( E n
13.109 3 k
then we have > V (0.96.7k 10 log 2 2-103/2. k
0.48
> 0.034 vT
TO00
Let S satisfies that all the vertices in S are good, and S contains at least one vertex from C2 for all i == I,...,k h. For any x, y E S, then:
1. If x. y belong to the same cluster, by above analysis, we know that (fz. 2 0.96(1
4= 11/6 Then it holds that (Sas Suipax 2 (s), & vI (5)
4VE nk vk
Φ )
x 2 0.96(1 - -AVE 1h
f 0. Thus, an edge (z,,z) will be added to H (at lines 8 and 9 of Alg
2. If N.y belong to two different clusters, by above analysis, we know that (Ja, S V
(5) 2//2 + 3/4
Ave
1/3 +
By
& Then it holds that (fer fo) S
(fzz fu) + & +
Vk 1/6
13/4
AVE
(5)
SVE 4
+ $ vT.
< 0.027 5 < B, since
2-109/2.
log 17 2-10 Ing
10 .5/1 "
1/g
1000
5 43. 10 & log" &
and {
vt
Thus, an edge (u, v) will not added to H.
G
1000
Therefore, with probability at least 1 50 50 2o 2 0.95, the similarity graph H has following properties: (1) all vertices in ((H) (i.e., 5) are good; (2) all vertices in S that belongs to the same cluster C, form connected components, denoted by S;; (3) there is no edge between S; and Sj. i * ji (4) there are exactly connected components in H, each corresponding to a cluster.
Now we are ready to consider query WHICHCLUSTER(G. x).
Assume x is good. We use CD to denote the cluster that belongs to. Since all the vertices in are good, let y E C2 S,S, so with probability at least नमक 2 1 n by above analysis, we have (Jz,
2 (Jn, fu) at least 8 2 1 n by above analysis, we have fy) S (fa, + < 0. Thus, 100
> 0. On the other hand, for any y E S,. with probability
WIICHCCLUSTER(C... .r) will output the label of y E C2 S as w's label (at line of Alg
8

---

Therefore, with probability at least 1 tices will be correctly recovered. So the misclassified vertices come from B. We know that 1/3
1
no 2 0.95, all the good ver-
12
50
50
|B|| - a + 3 10²²)
Avk
10ts
Since |C||
T we have [C,.
So, |B| S (AV7 (5) + (9tE)
1/3)))) This implies that there exists a permutation : [k] [t] such that for all i [R], (U & O (5))118111
マ// ||Ca| S O
Running time. By Lemma we know that INITIALIZEORACIEGG 1/2, computes in time ($) n21/240(e/p)) (log n)) き a sublinear space data structure D and for every pair of L/2, computes an output value
vertices H, V. (fe. fp) in ( ( 1 (logn)² 1 time.
In preprocessing phase, for algorithm CONSTRUCTORACI k, it invokes INITIALIZEORACLE one time to construct a data structure DD and SPiCTTAAtDOTPROOOCCOAAA times construct similarity graph HI So the preprocessing time of our oracle is ($) ( n1/2240(//0²) (logn)3
100A log l (5)0()) n1/2+0(e/v0)) (logn)² 4 =
0(n1/2+0(e/v") polyy A-log
In query phase, to answer the cluster index that x belongs to, algorithm WHICHCLUSTER ..) invokes SPECTRALDDTPRODUCTORR.CC s times. So the query time of our oracle is log ($)00), . n (logn)² = 0((212200e//0)) poly( A=log
Space. By the proof of Lemma and
we know that overall both algorithm INITIALIZEORACLE
take (t) n21/2+0(e/4") poly(log n) space. There-
fore, overall preprocessing phase takes ()) n n poly(log (logg) = ((n122+0ie//")
poly( 7 (Algg)) space (at lines and 7 of Alg In query phase, WHICHCLUSTER query takes
(2) (110).1//+0(e////// poly(logn) = O 1/0001200000 (tt/pp/)))))))))e)) polly( kloga) (oly(*logm)
space (at line 2 of Alg 2). 0
4 Experiments
To evaluate the performance of our oracle, we conducted experiments on the random graph generated by the Stochastic Block Model (SBM). In this model, we are given parameters p, q and n, k. where n, & denote the number of vertices and the number of clusters respectively; denotes the probability that any pair of vertices within each cluster is connected by an edge, and g denotes the probability that any pair of vertices from different clusters is connected by an edge. Setting > for some big enough constant we can get well-clusterable graph. All experiments were implemented in Python 3.9 and the experiments were performed using an Intel(R) Core(TM) i7- 1270FF CPU @ 1010GHz processor, with 32 GB RAM. Due to the limited space, practical changes to our oracle will be shown in Appendix F
Misclassification error. To evaluate the misclassification error oracle, we conducted this experiment. In this experiment, we set & = 3, = 3000, q = 0.002, p E [0.02, 0.07] in the SBM, where each cluster has 1000 vertices. For each graph G = (V, E), we run WHICHCLUSTER(CG, x) for all x E V and get k-partition U1,... Us of V. In experiments, the misclassification error of our oracle is defined to be 1-1 max, Σ i=! Un(1) n C. where π [k] +
[k] is a permutation and
Ci..... Cs are the ground-truth clusters of
Moreover, we implemented the oracle in 8 to compare with our oracle The oracle in 8 can be
a non-robust version of oracle in 30 Note that primary advancement over (also 30
is evident in the significantly reduced conductance gap we achieve.
We remark that the oracle is implicit in 8 (see also 30 Instead of using the inner product of spectral embeddings of vertex pairs, the authors of 8 used the pairwise ég-distance between the distributions of two random walks starting from the two corresponding vertices.

---

We did not compare with the oracle in [14] since implementing the oracle in [14] poses challenges. As described in section the oracle in [4 imitially approximates the k cluster centers by sampling around O(1/e. k' log k) vertices, and subsequently undertakes the enumeration of approximately 2001/e-k* log" k) potential k-partitions (Algorithm 10 in (14). This enumeration process is extremely time-intensive and becomes impractical even for modest values of k.
According to the result of experiment (Table D. the misclassification error of our oracle is reported to be quite small when 2 0.025, and even decreases to 0 when p 2 0.035. The outcomes of our experimentation distinctly demonstrate that our oracle's 's misclassification error remains notably minimal in instances where the input graph showcases an underlying latent cluster structure. In addition, Table also shows that oracle handle graphs with smaller conductance gap than the oracle in g which is consistent with the theoretical results. This empirical validation reinforces the practical utility and efficacy of our oracle beyond theoretical conjecture.
Table 1: The misclassification error of the oracle in g and oracle
p
0.02
0.025
0.03
0.035
0.04
0.05
0.06
0.07
min-error's (8)
0.5570
0.1677
0.0363
0.0173
0.0010
0
0
max-error'ss (error((]]] (18)
0.6607
0.6610
0.6533
0,4510
0.0773
0.0227
0,0013
average-error
8
0.6208
0.4970
0.1996
0.0829
0.0168
0.0030
0.0003
error (our)
0.2273
0.0113
0.0003
0
0
0
0
the experiment, we found that the misclassification error of oracle in fluctuated greatly, so for the oracle in [ for each value of p. we conducted 30 independent experiments and recorded the minimum crror,
maximum error and average error of oracle in S
Robustness experiment. The base graph Go EV) is generated from SBM with 3000, k 3, = 0.05,q q = 0.002. Note that randomly deleting some edges in each cluster is equivalent to reducing p and randomly deleting some edges between different clusters is equivalent to reducing So we consider the worst case. We randomly choose one vertex from each cluster; for each selected vertex I3, randomly delete delNum edges connected to 2; in cluster Cz. If x; has fewer than delNum neighbors within C, then we delete all the edges incident to I; in C.. We run WHiCHCLUSTER queries for all vertices in V on the resulting graph. We repeated this process for five times for each parameter delNum and recorded the average misclassification error (Table The results show that our oracle robust against a few number of random edge deletions.
Table 2: The average misclassification error with respect to delNum random edge deletions
delNum 25
32
40
45
50
55
60
65
error
0.00007 0.00007
0.00013
0.00047
0.00080
0.00080
0.00080
0.00087
We also conducted experiments to report the query complexity and running time of our oracle. See Appendix F for more details.
5 Conclusion
We have devised a new spectral clustering oracle with sublinear preprocessing and query time, In comparison the approach presented in [14, our oracle exhibits improved preprocessing efficiency, albeit with slightly higher misclassification error rate. Furthermore, our oracle can be readily implemented in practical settings, while the clustering oracle proposed in [4] poses challenges in terms of implementation feasibility. To obtain our oracle, we have established a property regarding the spectral embeddings of the vertices in for a d'-bounded n-vertex graph G = (V, F)) that exhibits (ki yp, e)-clustering Ci...., Ct. Specifically, if a and y belong to the same cluster, the dot product of their spectral embeddings (denoted as (fz, fy)) is approximately x()). Conversely, if z and are from different clusters, (fz. fy) is close to O. We also show that our clustering oracle is robust against few random edge deletions and conducted experiments on synthetic networks to validate our theoretical results.
10

---

Acknowledgments and Disclosure of Funding
The work is supported in part by the Huawei-USTC Joint Innovation Project on Fundamental System Software, NSFC grant 62272431 and "the Fundamental Research Funds for the Central Universities".
References
[1] Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 06), pages 475 486. IEEE, 2006.
[2] Reid Andersen, Shayan Oveis Gharan, Yuval Peres, and Luca Trevisan. Almost optimal local graph clustering using evolving sets. Journal of the ACM (JACM), 63(2):1-31, 2016.
[3] Reid Andersen and Yuval Peres. Finding sparse cuts locally using evolving sets, Proceedings of the forty-first annual ACM symposium Theory of computing, pages 235-244, 2009.
[4] Tony Cai and Xiaodong Li. Robust and computationally feasible community detection the presence of arbitrary outlier nodes. The Annals of Statistics, 43(3)::027-1055) 2015.
[5] Yudong Chen, Ali Jalali, Sujay Sanghavi, and Huan Xu. Clustering partially observed graphs via convex optimization. The Journal of Machine Learning Research, 15(1):2213 (1::)122222333 2014.
[6] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Test- ing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Annual Symposium on Foundations Computer Science (FOCS), pages 497-508 IEEE, 2018
[7] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[8] Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure of graphs. In Proceed- ings of the forty-seventh annual ACM symposium on Theory of Computing, pages 723-732, 2015.
[9] Tamal K Dey, Pan Peng, Alfred Rossi, and Anastasios Sidiropoulos. Spectral concentration and greedy k-clustering. Computational Geometry, 76:19-30 2019.
[10] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, al. A density-basee algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pages 226-231, 1996.
[11) Pedro F Felzenszwalb and Daniel P Huttenlocher. Efficient graph- image segmentation. International journal of computer vision, 59:167-181, 2004.
[12] Santo Fortunato. Community detection in graphs. Physics reports, 486(3-5);55-174, 2010.
[13] Amir Globerson, Tim Roughgarden, David Sontag, and Cafer Yildirim. Tight error bounds for structured prediction. arXiv preprint arXiv: 1409.55409 2014.
[14] Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Christian Sohler. Spectral clustering oracles sublinear time. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1598-1617. SIAM, 2021.
[15] Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck's 's inequality. Probability Theory and Related Fields, 1655--)):1055-049, 2016.
[16] Michael Kapralov, Akash Kumar, Silvio Lattanzi, and Aida Mousavifar. Learning hierarchical structure of clusterable graphs. CoRR, htss/207700251.. 2022.
[17] Michael Kapralov, Akash Kumar, Silvio Lattanzi, and Aida Mousavifar. Learning hierarchical cluster structure of graphs in sublinear time. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 925-939. SIAM, 2023.

---

[18] Konstantin Makarychev. Yury Makarychev, and Aravindan Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 367-384. ACM, 2012.
[19] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Constant factor approximation for balanced cut in the pie model. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 41-49, ACM, 2014.
[20] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Correlation cluster- ing with noisy partial information. In Proceedings The pages 1321-1342, 2015.
The 28th Conference on Learning Theory,
[21] Konstantin Makarychev. Yury Makarychev, and Aravindan Vijayaraghavan. Learning com- munities in the presence of errors. In Conference Learning Theory, pages 1258-1291. 2016.
[22] Bogdan-Ad Addiinn Manghiuc and He Sun. Hierarchical clustering: apppooaiooinnitooonn for well- clustered graphs. Advances in Neural Information Processing Systems, 34:9278-9222 -9879, 2021.
[23] Claire Mathicu and Warren Schudy. Correlation clustering with noisy input. In Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pages 712-728. Society for Industrial and Applied Mathematics, 2010.
[24] Ankur Moitra, William Perry, and Alexander S Wein. How robust are reconstruction thresholds for community detection? In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 828-841 841. ACM, 2016.
[25] Stefan Neumann and Pan Peng. Sublinear-time clustering oracle for signed graphs. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 16496- 16528. PMLR, 2022.
[26] Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 13, 2004.
[27] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances neural information processing systems, 14, 2001.
[28] Lorenzo Orecchia and Zeyuan Allen Zhu. Flow-based algorithms for local graph clustering. In Proceedings of the twenty-fith annual ACM-SIAM symposium on Discrete algorithms, pages 1 1267-1286. SIAM, 2014.
[29] Alberto Paccanaro, James A Casbon, and Mansoor AS Saqi. Spectral clustering of protein sequences. Nucleic acids research, 34(5):1571-1550, 2006.
[30] Pan Peng. Robust clustering oracle and local reconstructor of cluster structure of graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 2953-2972..0 SIAM, 2020.
[31] Pan Peng and Yuichi Yoshida. Average sensitivity of spectral clustering. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27,
2020, pages 1132-1140, ACM, 2020.
[32] Mason A Porter, Jukka-Pekka Onnela, Peter J Mucha, et al. Communities in networks. Notices of the AMS, 1689):008- 2009.
[33] Daniel A Spiclman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, 42(1):1-26, 2013.
[34] Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well- connected clusters. In International Conference on Machine Learning, pages 396-404. PMIR, 2013.
12

---

Appendix
A Complete preliminaries
Let G = (V, denote a d-regular undirected and unweighted graph, where V := {L..... n). Throughout the paper, we use E [n] to denote S S n and all the vectors will be column vectors unless otherwise specified or transposed to row vectors. For vertex z E V, let 1, E IR" denote the indicator of z, which means (i) = 1 if i 2 and 0 otherwise. For vector x, we let ||x||2 V Ei x(i)² denote its & norm. For matrix E R we use ||] to denote the spectral norm of A, and we use | to denote the Frobenius norm of A. For any two vectors x, y E IR", we let (x,y) y) x" y denote the dot product of x and y. For matrix RR*x, we use An E Rnxi to denote the first i columns of A, 1 S. S
Let A _=** denote the adjacency matrix of G and let D R denote diagonal matrix. For the if (i E E and 0 otherwise, u, E [n]. For the diagonal matrix D, D(i, deg(t), where deg is the degree of vertex i, e [n]. We denote with L the normalized Laplacian of where L D 1/2 A)D 1/2
adjacency matrix A, A(i,j) )) =
For L, we 0 S À S S An S R" to denote the corresponding eigenvectors. Note that the corresponding eigenvectors are not unique, in this paper, we let #1,.... Un be an orthonormal basis of eigenvectors of L. Let U E R be matrix whose i-th column is u4 E [n]. then for every vertex V. fa UT 1z. For any two sets S₁ and S2, we let S,4.Sp denote the symmetric difference between S and S2.
7 to denote its cigenvalues and we use ......,
B d-bounded graphs to d-regular graphs
For a d-bounded graph G' = (V, E). we can get d-regular graph G' from G' by adding d d deg(2) self-loops with weight 1/2 each vertex x E V. Note that the lazy random walk G is equivalent to the random walk on G", with the random walk satisfying that if we are at vertex I, then we jump to random neighbor with probability 1 and stay at with probability 1 1 deg(z) 24
We use
W (a) (d deg(z)) 2/2 to denote the the weight of all self-loops of x E V.
C Formal statement of Lemma 2.1 and description of dot-product algorithms in [14]
Lemma C.1 (Lemma 2.1 Formal; Theorem 2, [14). Lere, (0,1) with I & Let G (V,E) be d-regular graph that admits a (k, ccuusttring CI...., Ck. Let At E < 1. Then INTIALLIZORAACLEG; 1/2, E) computes in time ( ())(1)) ) 12/20(((/=" (logn)3. 1 sublinear
space data structure D of size ( .n1/2+0(e//²) (logn)3 such that with probubility at least
1 100 the following property is satisfied:
For every pair of vertices E V, SPECTRAL.OTPRODUCCTN x 1/2, D) computes an oulput value (Sz, Jypapx such that with probability least n 100
n100
- < S
(fx: fyd
The running time "SSECCRAALDOTRROUUCCCC.E.....L (2200///000 (log
Algorithm 4: RUNRANDOMWALKSCC
R, R,t,))
Run R random walks of length starting from x
Let (v) be the fraction of random walks that ends
3 return mzg
13

---

Algorithm 5: EBSIDANTETANNSTTIOMMRTTIGGG R,
for each sample & E Is do
my --UNRANNOM R,
end
Let Q be the matrix whose columns are my for x E Is
return Q
Algorithm 6: ESSTMATTCCOLLLLOPPPRRAAALLLLILCL
for i Ollog n.) do
Q: -ESTMAATTETRRANSSTOONAAAAAA Is, R,t) P. ESSTIATTERRANNTTINMATTKKK Is, R,
9 == 1/4 Q. + P.)
end
Let G be matrix obtained by taking the entrywise median of G/s
return G
Algorithm 7: INITIALIZEORACLEEG.. 6,5)
Need:e/p S
20-log
t ==
2 Rimit == 0 1.7 /52)
On log n h.a /=/E²)
4 Let 1s be the multiset of indices chosen independently and uniformly at random from {1....,m] n)
5 for i = to O(log n) do
Q -SSIINNETRRANNTTIONAAAAACC
Rinit, t)
7 end
9 -BBTTAATECOLLLSOOPOOOAABLLLLLLLE Is, Riuit;
9 Let G = WEWT be the eigendecomposition of =
1--1 exists then
11
= - Wik [
WT [4]
return D = -V, Qi.... (0()
12
13
end
Algorithm 8: SVECTRALLDOPPOODCCTOOACC.. ,, Need:e/ x² s 10
Rquery On 19 /E2)
2 for i 1 to Ologgn) n) do
m -UUNRNNDOMWALKSSG Raquer t, x)
m, --RUNRANDDMMWLLKSC.. Rquery, t, y)
end
Let Og be vector obtained by taking the entrywise median of (Q.)T(m) over all runs
Let Bt be vector obtained by taking the entrywise median of (Q.) (m,)) over all runs 8 return (fz. Jy)apx = of Way
D Deferred proofs
Let a E (), Letk > 2 be an integer, yp E (0, 1), and E E (0, 1). Let G = (V, E) be a d-regular (k, sp, cllcsttrlle graph with [V] = n. There exists
Lemma D.1 (Restatement of Lemma 3.1
subset V CV with | 2 (1 a)]V[ such that for all x E V, it holds that [| S . k
14

---

Proof. Recall that ui...... uy are an orthonormal basis of eigenvectors of L, so ||u1122 = 1 for all i E [k). So Σx ||u, = Σ Il5 k. Let X be random variable such that X fl 11 with probability 1. n.
π Ei= fz. 11 n Using Markov's inequality, we have Pr[X 2 3/4 E[X]] = Pr[x 2 _/- - < a. This gives us that Pr[X - + # Z
for each E [n]] Then we have [ 1
1 - a, which means that at least (1 at) fraction of vertices in V satisfies fl < 1 A.
We define
n
V = {a V: 1lf - 2 a }). then we have [7] 2 (1 V) This ends the proof.
Lemma D.2 (Restatement of Lemma 3.2 Let 3 E (0, Let k 2 2 be an integer, up E (0, 1), and e E 1), Let G = (V, E) be a d-regular graph that admits a (k, 4, --clusteringg Ct...., Ck with
[V] = n. There exists a subset V - V with
[V] 2 (1 B)[ such that for all x E V, it holds that
Ilfe Mall2 S
4k
The following result will be used in our proof:
Lemma D.3 (Lemma 6, [14). Let k 2 2 be an integer, &p E 1), and & E (0, 1). Let G = (V, be a d- d-regular graph that admits a (k, sp, cclusterig Ci...., Ck. Then for all a E R with ||a||2 = 1 we have
4 x2²
Σ
Σ rc
(fe Mi a)) s
Proof of Lemma 3.2
By summing over a in an orthonormal basis of R we can get
4s 4kg 2
E 12-1
ZEV
where My is the cluster center of the cluster that x belongs to. Define V = for E V: 115e 12213
4ke
1. Then,
Di
4kg
4ke 1
4Kg 1 3i22 n
I1
Mar 11
Σ 1s 1x
|V
82
3ip n
aEV
DEV-
So, we can get IV* S 3n. We define V = -
= fx V
II - ux
H. Therefore,
D
we have [V| 2 (1 - 3)n (1 /. This ends the proof.
Lemma D.4 (Restatement of Lemma 3.3 Let l 2 be an integer, &p 1), and fo be smaller than a sufficiently small constant. Lei G = (V, be a d-regular graph that admits a (k, e) clustering Ci,.... Cs. Let Ci denote the cluster corresponding to the center pe, i E [k]. Then for every C2, i E [k),, there exists subset C, S C. with |C|| 2 (1 it holds that (fn. 2 0.96 |1
10'=)[[s) such that for all x E C..
4²
The following result will be used in our proof:
Lemma D.5 (Lemma 31, [14). Let k: 2 2, y 1), and &o be smaller than a sufficiently small constant. Let G = (V, F) be a d-regular graph that admits (k,, sp, -.llssuutg Cr...., Ck- If 14, are cluster means then the following conditions hold. Let (M1.....,,13) Let II denote the orthogonal projection matrix on to the span(S)) Let μa {PI...., V.S. Let C denote the cluster corresponding to the center μ. Let
Ō f== (TI Mp) 2 0.96]
then we have:
10's 6² [C|.
10 <
Proof of Lemma 3.3 We apply S 0 in Lemma D.5 so that II is identity matrix and we will have 10
IC,)Cal s x²
Ctl. where C, = {ar E V : (Sa, mz) 2 0.96 1++1) 3)+ i [R.]. So
10te
[ 2 1
[C,).
15

---

We define C. C, E [k]. Therefore, for every C, E [k], there exists subset C S C with 10's |[Cb] such that for all Ci it holds that (far 2 0.96||
[C|| 2
Lemma D.6 (Restatement Lemma 3.4 Let 2 2 ( and 3. be smaller than a sufficiently small constant. Let G = (V, E) be a d-regular n-vertex graph that admits a (ki, 4. e)ccstrteinng C1,...,; Ck- Suppose that z,, y V are in the same cluster C., i E [Bc] and both of them are good vertex with respect
2 (g)) and 3 2v (5x) )2/3, the following holds:
4VE
Vk
1/6
(fa. fu) 2 0.96
1
10
[c||
n
62
The following result will be used in our proof:
Lemma D.7 (Lemma 7, [14). Let k 2 2 be an integer, E (0,1), and E (0, 1). Let G = (V, be a d-regular graph that admits a (k, ( Cr, Ck. Then we have
1. for all i E [k]. |1
|c.1|
- 4vE 1
e IC
2. for all i i E [b]. K/4, n1)) x SvC
Vicill
Proof of Lemma 3.4 According to the distributive law of dot product, we have
(fa, fu) (Sz. fu 44 + m4) = (far fo - (4) + (fz: Mz)-
By using Cauchy-Schward Inequality, we have ((fz, fy --)) S llfal12 Ilfy p 22. Since and y are both good vertices with respect to a = 2 ( (550 )133 and 3 = 2 To
( (55a) ) 1/3, we have
1 k
4ke 1
Vi
1/6
[0 fu -4)1 S 11 115y mill2 S
3
which gives us that (Sa, fu - pa) 2 vi (5x )2/6. (fz, p4) 2 0. Hence, it holds that
Recall that x is a good vertex, we have
(Ja, (Sa, Jn ui) + (Sa, ps)
Vk
1/6
2 0.96|114.11
n
4ve 1-
VT
1/6
2 0.96
y
π
The last inequality is according to item in Lemma
D.7
Lemma D.8 (Restatement Lemma 3.5 Let 2. E (0, 1) and fo be smaller than a sufficiently small constant. Let G = (V, E) be a d-regular n-vertex graph that admits a (k, y, el-cstrteiing CI...., C₁- Suppose that C, y E Cj (i.j [k), i + j) and both of them are good vertex with respect to a 2/TT (15 and 3 2 15), the following holds:
Vi
1/6
1/4
1/3
4VE 8
SVE 4
(fe.fa) <
+
Va
E
C
VCA.
Proof. According to the distributive law of dot product, we have
(F.. = (Sar - μú + m1) (Sz, Ju 11)) + (fz.1z)
(Sa; - -nj) + (Sz - p4 + pis (1))
fo -11) + (fa (..Hg) + (Hin Hy).
16

---

By Schwarz Inequality, we have
Kf fy - -ay) S Ilfzlle Ilfu -2ll2
and
1(f= ui, wلمl - ||m 115e Mill2.
Since r and y are both good vertices with respect to a = 2//: (ur))// and / = 2vk (52) 1/3 we have
1 k
4kg 1
Vk
e
1/6
50 -1511 s 11 115x Myll2 S V a
|
Bip
n
x²
and
4ks
1
V22k2/4
1/3
1ls= (Ja-Mi, Mis Mes S 11,ll22 115- - msll2 s ||55112 V
|151122
BGp
n
vn
So we have
(f fu)
(fer fg (1)) + (fr Ms: p.. pb) + (Mi pe)
S || 2
[|5 - M1ll2 ||lill2 [m uil
2|2 (11, M4)
Vk
1/6
2211/1
1/3
<
+
||اد (1is 15)
n
622
vn
6
Vk
1/6
1/
E
1/3
4ve [+
1
8VE
+
6
6
Cy
/Ca . C21
The last inequality is according to item I and item 2 in Lemma D.7
E Formal statement of Theorem 2 and proof
Theorem 2 (Formal: Robust against random edge deletions). Let 2 be an integer, yp E (0, 1). Let Go (V, Eo) be d-regular n-vertex graph that admits ()) Cl...., Ck.
and all E [k]. S |C| Aogl k
S a where 7y is a constant that in (0.001, 1].
Let G be a graph obtained from Go by deleting at most e edges in each cluster, where c is a de² then there exists an algorithm that has query access to the adjacency constant. If0 S S 2/10'
list of G and constructs clustering oracle in ((n-/2+0le/4")) ppll( sslog )) preprocessing time and takes (2+00()))))) poly( klogg) space. Furthermore, with probability least 0.95, the following hold:
1). Using the oracle, the algorithm can answer any WHICHCL.USTER query in ((n1/2+0(e//2) poly( klogg)
)) time and WHICHCLLUSTER query takes (22424+0()//") pplyy (klogz) )) space.
7/ 2). Let U, fi E V WHICHCLUSTER (G. x) i). E [k] be the clusters recovered by the algorithm. There exists permutation π [k] + [k] such that for all E [k].
|U 00 (5))
2. Let G be graph obtained from Go by randomly deleting at most O( (og k+d edges in Go. With probability least ę.. then there exists an algorithu that has query access to the adjacency list of G and constructs clustering oracle in O( 02+00(/0)) pooly( bloon)) preprocessing time and takes /2+00ee())) poly( klog )) space. Furthermore, with probability least 0.95, the following hold: 1). Using the oracle, the algorithm can answer any WIICHCLUSTER query in O(n (22//240()//)) poly( & klogg )) time and WHICHCLUSTER query takes ( .plly( & log )) space.
kdf
7
7/
7.
17

---

2). Let U, : fx V WHICHCLUSTER x)) =i. E [k] be the clusters recovered
by the algorithm. There exists permutation π : [k] +
[k] such that for all [k]
AU & 0 ( (C)
To proof Theorem we need the following lemmas.
Lemma E.1 (Cheeger's Inequality). In holds for any graph that
A x(G) 222 2
Lemma E.2 (Weyl's Inequality), Let A, B E R= be symmetric matrices. Let 0i,..., An and be the eigenvalues of A and B respectively. Then for any i E [ni], have
Br B1....,
la; 8:1 S |l Bl|,
where ||A - B|| is the spectral norm of A B.
Proof of Theorem Proof of item For any d-bounded graph G' (V, E), we can get d-regular EV, graph G from G" by adding d - deg(xr) self-loops with weight 1/2 to each vertex æ E V. Then according to 77. the normalized Laplacian of G (denoted as I.) satisfies
(adr(())
if x=
L(x
x x and (z,8) EE otherwise
d
0
Let Go Eo) be d-regular graph that admits (k, sp -clusttrnn Cı...., Chy...,Ca, Cp. Now o consider cluster C,, E [k]. Let C. be a d-regular graph obtained by adding - deg. (z) self-loops to each vertex x C. where deg, (z) is the degree of vertex in the subgraph C₁ i E [k]. Let Ci be a graph obtained from C by: (1) randomly deleting edge (u, v) E(C ) where EECC-L) ") a set of edges that have both endpoints in Ci (2) turning the result subgraph in (I) be a d-regular graph, E [ E [c]. Let L be the normalized Laplacian of C. E [k).j = 0, 1, Let HI = L3 L3 E [K], E [c]. Then if + v. we have
if x == or U, u
H
z2
z=y=u or otherwise
if
and if u v, Hi is all-zero matrix. Consider the fact that for a symmetric matrix, the spectral norm
is less than equal to its Frobenius norm, we will have / < || v2 - 2
5
vi for all E [k], [c]. Let = Σ n - we have |||H||| S 2d
vIO
2d c [k]
V 2
Let (D and d2 (Iā) be the second smallest eigenvalue of LQ and L respectively. By Lemma E.2
we have (A2(L A2(74) < |
vi which gives us A2( 2 A2( 8² v/0
vTo 2d c, i E [k]
2d
By Lemma E.1 and the precondition that S T010'
do²
we have (2 2 2
2
c. Therefore,
V10
X2(L,) 2 22(1))
2d
V10
= 2 Xe(L + )
c
2
2d
2 >22(1))) + V10
V10
2d
2d
2 (Z
Again by Lemma F. for graph C2 we have oin (CT) = (bC)) 2 {22((T9) 2 (22(T.)) > L e [k). Note that we sligtlly abuse the notion Cj for of (C,)), treat Cj d-regular graph, and
18

---

for ΦIn (C we treat C as a cluster obtained by deleting edges from E(C,). So, for (k, p,
clusterable graph Go - (V, Eo), we delete at most c S 2 edges each cluster, then the resulting graph G is (k: g e) clusteraale.. Since & <
dg²
we have 1 logg k The statement of item 1 in this theorem follows from the same augments as those in the proof of Theorem with parameter s $1²² in G.
log" &
Proof of item 2: Let c
de- 2V10"
Since |C,|| - n for all [b], have |E(C)) 2 4.
7k
where E(C;) is a set of edges that have both endpoints in C.. So |E(C |Eul
I 7t
1
E
[k].
7
4
Since |C:] 2 on and Pout (C,, V) S E, we have E(C,) 2 ad (7 +). So [E(C
2
21
(1-3)
2E
( ) E [b.] Combining the above two results, we have (7 5 S |E(C, Bol
S
1
T
In the following, we use X; to denote the number of edges that are deleted from E(C,). If ko ko"x(=-=s)
we randomly delete
-= Flg k+ ojc O
ke 2= Toggg k+d edges from Go. then we have k(7 - 5)
(1og
9 llg k+2((2--5 B(X,)
1
9 b eyc which gives
7h
(72 - z)²
c
S <(())) <
9 log k + 2(7² s)c
glgg 2(77 =)c
Chernoff-Hoeffinn implies that Pr[X; > (1+6). Se -2 then we have
We 8 9log k- - (72-6)e
Pr > > Pr X; (1+5) 2072
9log + 2(7² E)C
< Pr X > (1 + 8) -B(x))
21, +)² 8² blogg+2(y" -eae
$
blog (8--)(
26P-n)²
3
Using union bound, with probability at least 13 k 12, we have that if we randomly delete
-=)=()) = kd ) edges from Go, there is no cluster that is deleted more than c edges. log a
glog k k-2((==2()))) Therefore, according to item of Theorem 2 with probability at least 1- - E k == 1 - р.. G is
(k,, ( -lclsetteee graph. The statement of item in this theorem also follows from the same augments as those in the proof of Theorem with parameter yp g2² in G.
F Experiment Details
Practical changes to our oracle. In order to implement our oracle, we need make some modifications to the theoretical algorithms. To adapt the dot product oracle parameters (see Algorithm ann Algorithm in in Appendix Cp. i.e., (random walk length), s (sampling set size), and Rynit- Rquery (number of random walks), we exploit the theoretical gap between intra-cluster and inter- cluster dot products in clusterable graphs. Given clusterable graph G, by constructing the dot product oracle with various parameter settings and calculating some intra-cluster and inter-cluster dot products, we generate density graphs. The setting with the most prominent gap in the density graph is selected (see Figure 2 for an illustrative example).
7
19

---

1220
Inte- cluster
iiraa dissier
6000
interrusterr
entre shole
7000
1030
6000
200
3000
Deeeks
6000
2000
2000
200
1000
0.001
0w1008800000000000
000750000000000000 0012000000000000001177777
Figure 2: For random graph G generated by SBM with 3000, k 3. 0.03, q 0.002, we build the dot product oracle for several different parameters for t, 8, Rinits R Ryuery and plot the density graph. The setting with the most prominent gap in the density graph, i.e., the one on the right, selected. We can further set = 0.0005 for G' according to the right graph.
Determining the appropriate threshold (at lines 2. 8, 9 of Alg and line 3 of Alg is the next step. By observing the density graph linked to the chosen dot product oracle parameters, we identify the fitting (see Figure 2 for an illustrative example).
Determining the appropriate sampling set size s (at line 3 of Alg T of our oracle is the final step. Given a graph
(V, E) generated by SBM. for all vertices in V. we know their ground -tuth clusters. We can built our clustering oracle for several parameters for s. For each parameter setting, we run WHiCHCLuUterRG. æ)) for some V and check x was classified correctly. We pick the parameter setting with the most correct answers.
Query complexity. We conducted an experiment on SBM graph with k: 3, n 15000, q 0.002, 0.2. We calculate the fraction of edges that have been accessed given number of invocations of WHICHCL.USTER(G, 2:) (Table3). (Note that there is trade-off between computational cost and clustering quality. Therefore, it is necessary to point out that the parameters of this experiment are set reasonably and the misclassification error is 0.) Table 3 shows that as long as the number of WHICHCLUSTER queries is not too large, our algorithm only reads small portion of the input graph.
The above experiment shows that for a small target misclassification error, our algorithms only require sublinear amount of data, which is often critical when analyzing large social networks, since one typically does not have access to the entire network.
Table 3: The fraction of accessed edges of queries
# queries 0
50
100
200
400
800
1600
3200
fraction
0.1277
0.2539
0.3637
0.5377
0.7517
0.9273
0.9929
0.9999
Running time. To evaluate the running time of our oracle, conducted this experiment some random graphs generated by SBM with n 3000, = 3, g = 0.002 and p E [0.02, 0.06]. Note that there is trade-off between running time and clustering quality. In this experiment, we set the experimental parameters the same as those in the misclassification error experiment, which can ensure small error. We recorded the rumning time of constructing similarity graph H construct-time. For each p. we query all the vertices in the input graph and recorded the average time of the n = 3000 queries as query-time (Table
Table 4: The average query time of our oracle
0.02
0.025
0.03
0.035
0.04
0.05
0.06
construct-time (s)
11.6533
12.4221
11.8358
11.6097
12.2473
12.2124
12.5851
query-time (s)
0.3504
0.4468
0.4446
0.4638
0.4650
0.4751
0.4874
20


Reviews:
[{"review_id": "ZMM6qvnVtM", "reviewer": "Reviewer_xqth", "summary": "This paper proposes a spectral clustering oracle with sublinear pre-processing time and query time. The query is in the form of $(G, x)$ where $G$ is a graph with underlying clusters and $x \\in V$ is a vertex. The goal is to (1) construct the oracle efficiently, (2) report which cluster vertex $x$ belongs to efficiently.\n\nComparing to the previous work, the main contribution is improvement on the pre-processing time, which reduces exponential to polynomial on $O(k/\\varepsilon)$, but blows up the misclassification error from $\\log k$ to $\\text{poly}(k)$, also slightly relaxing an assumption on the gap between inner and outer conductance.  The query time is asym-same. \n\nThe main technique is to replace the exhaustive search for each sampled vertex to decide a vertex $x$ belongs to a cluster with center $\\mu$, with estimating the inner product of their spectral embeddings. It is proved the magnitude of the inner product roughly shows if two vertices belong to the same cluster.", "questions": "For the oracle results, there is another measure-of interest on the space. It would be good to report and compare with previous ones on this. \n\nJust some curiosity on the lower bound. Is there any result stating something like: to obtain a small error, at least some space / time is needed?\n\nAnother suggestion is to give some conceptual description of good and bad vertices before the definition, maybe in the main technique part.", "limitations": "See above.\n\nMy reason to give the current assessment is mainly on the technical novelty limit.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written and well organized.\n- The result is neat, the proposed algorithms are more easy to implement comparing to previous ones.\n- I think for a theory paper, having experiments is always a plus. However, there is a mentality that either do it well or just don't do it. The experiments can be improved or at least clarified better.", "weaknesses": "- The major concern is that the contribution of the main result is quite limited. Yes, $O(k/\\varepsilon)$ is an important factor, but it still in the $\\tilde{\\Omega}(\\sqrt{n})$ regime, not to mention compromise on others. I actually like the robustness result better.\n- On the experiments, if the authors want to keep and improve the section, I would suggest:\n  - (1) Clarify the evaluation. I believe the theoretical result on the error is the number of query instances? Then the current report does not look like so, is it the fraction?\n  - (2) The issue of query complexity is not mentioned before. It is out of blue. Explain why you do it.\n  - (3) Add the robustness experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking your time to review our paper. We are happy to know that you like our robustness result. We address your concerns in the following.\n\n**The major concern is that the contribution of the main result is quite limited. Yes, polynomial on k/eps is an important factor, but it still in the Omega(\\sqrt{n}) regime, not to mention compromise on others.** \n\nSince the running time of the spectral clustering oracle is $f(k) \\Omega(\\sqrt{n})$ regime, it seems that improving the f(k) factor from exp(k/eps) to poly(k/eps) is a modest improvement. We wish to highlight that achieving this improvement was not straightforward, besides that our algorithm is more practical and conceptually simpler. Our improvement necessitated the intricate application of spectral embeddings and the acquisition of certain insights, which appear deceptively simple *in hindsight*. Remarkably, during a presentation in the Bangalore Theory Seminars, one of the authors, M. Kapralov of [14],  raised an open question (refer to the segment commencing at 54:44 of the YouTube video): \"if one can get polynomial dependency on $k$ or avoid enumerating over the candidate cluster centers...\" and \"get sublinear time for all $k=o(n)$\". \n\nOur result made progress towards solving this question, and our algorithm does not enumerate over the candidate cluster centers and has sublinear running time for a much broader range of $k$ (with a slightly worse conductance gap than [14]). \n\n**Clarify the evaluation. I believe the theoretical result on the error is the number of query instances? Then the current report does not look like so, is it the fraction?**\n\nThanks, we will clarify this in the upcoming version. In the context of our study, the misclassified error pertains to the **fraction** of inaccurately categorized vertices within each cluster. In Theorem 1, we employ the assertion $|U_{\\pi(i)}\\triangle C_i|\\le O({\\rm poly}(k\\cdot\\varepsilon))|C_i|$ as a metric for quantifying this error. This can also be equivalently expressed as the fraction of misclassified vertices being $O({\\rm poly}(k\\cdot \\varepsilon))$ within each individual cluster $C_i$. In our experiments, we directly utilize this error fraction within our report, as exemplified in Table 1 in our submitted manuscript.\n\n**The issue of query complexity is not mentioned before. It is out of blue. Explain why you do it.**\n\nWe note that there is a tradeoff between computational cost and clustering quality. The main reason that we are adding the experiment on the query complexity is to show that for a small target misclassification error, our algorithms only require a **sublinear amount** of data, which is often critical when analyzing large social networks, since one typically does not have access to the entire network. \n\n**Add the robustness experiments.**\n\nPlease see the attached PDF file (Table 2) within our rebuttal for our additional experiments on the robustness of our spectral clustering oracle.\n \nFor example, we evaluate our robust algorithm on an SBM graph after deleting delNum edges in each cluster (chosen randomly), where delNum is a parameter. We found that as long as delNum is not too large, our oracle has a small misclassification error, e.g. for 50 edge deletions in each cluster, the error is only $0.8\\textperthousand$.\n\n**For the oracle results, there is another measure-of interest on the space. It would be good to report and compare with previous ones on this.**\n\nThanks for the suggestion. Upon further consideration, we find that our data structure uses much smaller space than the one in [14] for some interesting regime of parameters. We will add the following clarification in the next version of our manuscript.\n\nThe space complexity of our data structure is $O\\left({\\rm poly}(k)\\cdot n^{1/2+O(\\varepsilon/\\varphi^2)}\\cdot {\\rm poly}(\\log n)\\right)$, while the oracle in [14] needs $O\\left({\\rm poly}(k/\\varepsilon)\\cdot n^{1/2+O(\\varepsilon/\\varphi^2)}\\cdot {\\rm poly}(\\log n)\\right)$. That is, the first term in our space complexity does **not** depend on $\\varepsilon$ in comparison to the one in [14]. The primary factor behind this enhancement lies in our ability to approximate the dot product of spectral embeddings with only an additive error of $1/{\\rm poly}(k)$, whereas [14] necessitates achieving an additive error of ${\\rm poly}(\\varepsilon/\\varphi)$.\n\nIt's worth highlighting that our space complexity significantly outperforms that of [14], particularly in cases where $k$ is fixed and $\\varepsilon$ takes on exceptionally small values, such as $\\varepsilon=1/n^{c}$, for sufficiently small constant $c>0$. \n\n**Is there any result stating something like: to obtain a small error, at least some space/time is needed?**\n\nThanks for the question. We will add the following clarification in the next version of our manuscript.\n\nWe note that there is no clustering oracle that allows both $o(\\sqrt{n})$ preprocessing time and $o(\\sqrt{n})$ query time. The reason is as follows: in [GR97], the authors show that one needs $\\Omega(\\sqrt{n})$ queries to distinguish an expander with $n$ vertices from a graph that is a union of two disjoint expanders each with $n/2$ vertices. Note that if there exists an oracle with both $o(\\sqrt{n})$ preprocessing time and $o(\\sqrt{n})$ query time, then one can use this oracle to distinguish the above two graphs, by checking if the corresponding similarity graphs have one or two connected components. This  will be a contradiction to the $\\Omega(\\sqrt{n})$ lower bound [GR97].\n\nReference: [GR97] O. Goldreich, D. Ron. Property testing in bounded degree graphs. STOC 1997.\n\n**Another suggestion is to give some conceptual description of good and bad vertices before the definition, maybe in the main technique part.**\n\nThanks, we will give a brief informal description of good and bad vertices in Section 3.1 (our techniques) as you suggested. "}, {"review_id": "IZaGC02Zlp", "reviewer": "Reviewer_2P47", "summary": "This paper studies oracles for spectral graph clustering, i.e., local algorithms that answer membership queries for single nodes in a spectral clustering of a graph. There is a line of research on testing cluster structure in degree-bounded graphs, and recently, the learning version of the problem studied in this paper has become popular. Besides a result for robust clustering oracles by Peng, this works is closely related to a paper by Gluch et al. Compared to the work of Gluch et al., this submission improves the preprocessing time to $O(n^{1/2 + O(\\epsilon / \\phi^2)})$, which is better by a factor of approximately $2^{poly(k/e)}$ at the expsense of requiring a conductance gap of approximately $\\Omega(1/poly(k))$, which is worse by approximately a $poly(k)/\\log(k)$ factor, and a misclassification error of $O(poly(k) \\epsilon)$, which is worse by approximately a $k / \\log(k)$ factor. The misclassification error is the fraction of vertices that are assigned to the wrong cluster (compared to the ground truth clustering). The query time of the two algorithms is roughly the same. In a nutshell, the result in this submission trades an additional polynomial dependency in conductance gap and misclassification error against the removal of an exponential dependency in preprocessing time. The authors experimentally confirm the misclassification error and query complexity proven in their theorems.\n\nThis work builds up on the dot product oracle introduced by Gluch et al. The algorithm in the latter work estimates the means of the clusters (in an embedding space) and uses the dot product oracle to estimate the closest cluster center (mean) for a query node. The exponential preprocessing time arises from the former part. In the present submission, the authors propose an algorithm that doesn't estimate the cluster means, but compares the dot product between node embedding directly. Intuitively, if two nodes belong to the same cluster, they have a large dot product with their cluster mean, and so they should also have a large dot product with each other. This modification also results in the aforementioned trade off, i.e., the increased misclassification error and the stronger requirement on cluster separation.\n\nThe question answered by this paper arises naturally from the work of Gluch et al.: Do we need to compute the cluster means explicitly? While the answer may not be surprising (no, but there is a trade off), it requires some work to actually prove this, as the formal argument is not simple and obvious. The intention of the experiments is not clear to me, as there is no comparison with other algorithms, or insights how the theoretical algorithm needs to be modified and tuned for applications.\n\nRebuttal: Rating changed from weak accept to accept due to authors' rebuttal responses.", "questions": "Note: It seems to me that a comparison of the conductance gap of your result and [14] is missing.", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The question explored in this paper is natural.\n* The paper confirms an intuitive concept of spectral embeddings for clustering.", "weaknesses": "* The result in this paper is not very surprising or better than one would expect. It seems more like a reasonable trade off.\n* The experiments seem currently not very useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for taking the time to review our paper.  We address your concerns in the following.\n\n**Summary: The intention of the experiments is not clear to me, as there is no comparison with other algorithms or insights on how the theoretical algorithm needs to be modified and tuned for applications.**\n\n**S1: The intention of our experiments.**\n\n(1) We aim to elevate our oracle beyond its theoretical framework. The outcomes of our experimentation, presented in Table 1 within our manuscript, distinctly demonstrate that our oracle's misclassification error remains notably minimal in instances where the input graph showcases an underlying latent cluster structure. This empirical validation reinforces the practical utility and efficacy of our oracle beyond theoretical conjecture.\n\n(2) We note that there is a tradeoff between computational cost and clustering quality. The main reason that we are adding the experiment on the query complexity, presented in Table 2 within our manuscript, is to show that for a small target misclassification error, our algorithms only require a **sublinear amount** of data, which is often critical when analyzing large social networks, since one typically does not have access to the entire network.\n\n**S2: Why there is no comparison with other algorithms?**\n\nWe briefly comment on the implementation of the two most relevant sublinear-time clustering oracles given in [14] and [30].\n\n(1) Implementing the algorithm from [14] poses challenges. As highlighted in our paper, the algorithm in [14] initially approximates the $k$ cluster centers by sampling around $O(1/\\varepsilon\\cdot k^4\\log k)$ vertices, and subsequently undertakes the enumeration of approximately $2^{O(1/\\varepsilon\\cdot k^4\\log^2 k)}$ potential $k$-partitions (Algorithm 10 in [14]). This enumeration process is extremely time-intensive and becomes impractical even for modest values of $k$. We will explicitly state this factor in Section 4 to provide a clear rationale for our approach.\n\n(2) Regarding the algorithm introduced in [30], it appears that its implementation is likely viable. However, our primary advancement over [30] is evident in the significantly reduced conductance gap we achieve. To thoroughly explore the comparative performance of our algorithm against [30], we aim to conduct new experiments. These experiments will focus on determining the specific graph ranges within which our algorithm outperforms [30]. In the upcoming version of our work, we are committed to implementing the algorithm from [30] and conducting the suggested experiments to provide a more comprehensive understanding of the algorithms' respective capabilities.\n\n**S3: How the theoretical algorithm needs to be modified and tuned for applications?**\n\nIn the upcoming version, we'll provide the following detailed steps to translate the theoretical algorithm into a practical one.\n\nTo adapt the dot product oracle parameters, such as $t$ (random walk length), $s$ (sampling set size), and $R$ (number of random walks), we exploit the theoretical gap between intra-cluster and inter-cluster dot products in clusterable graphs. By constructing the oracle with various parameter settings and calculating intra-cluster and inter-cluster dot products, we generate density graphs. The setting with the most prominent gap in the density graph is selected (see Figure 1 in the attached PDF file within our rebuttal). Our misclassification error experiments adopt $t=25$, $s=20$, and $R=200$.\n\nDetermining the appropriate threshold $\\theta$ (lines 2, 8, 9 of Algorithm 1, and line 3 of Algorithm 2) is the next step. By observing the density graph linked to the chosen dot product oracle parameters, we identify the fitting $\\theta$. In our misclassification error experiments, $\\theta$ is set at $0.0006$ and $0.00053$ for $p=0.02$ and $0.0225$, respectively. For all other $p$ values in the range $[0.025, 0.06]$, $\\theta$ is fixed at $0.0005$.\n\nFurthermore, for a WhichCluster($G,x$) query, the theoretical algorithm randomly selects an index if vertex $x$ belongs to multiple components of similarity graph $H$ (Algorithm 2). In practice, we return the index of the first component to which $x$ belongs. This adjustment enhances the algorithm's practical usability.\n\n**Weakness: The experiments seem currently not very useful.**\n\nThanks for pointing out this. We are pleased to share that we have generated new experimental results that enrich our evaluation efforts. We kindly request your review of the attached PDF file within our rebuttal, where these results are detailed. Notably, these additions encompass experiments focusing on the algorithm's running time and its robustness, providing a more comprehensive assessment of its performance. Your consideration of these findings is greatly appreciated.\n\n* [Running time experiments] Please see Table 1 in the PDF file. The experimental results show that the running time of a single query is between 0.5-0.7 seconds, and the pre-processing time of our oracle is between 15.9-18.2 seconds.\n\n* [Robustness experiments] Please see Table 2 in the PDF file. We evaluate our robust algorithm on an SBM graph after deleting delNum edges in each cluster (chosen randomly), where delNum is a parameter. We found that as long as delNum is not too large, our oracle has a small misclassification error, e.g. for 50 edge deletions in each cluster, the error is only $0.8\\textperthousand$. \n\n**Question: It seems to me that a comparison of the conductance gap of your result and [14] is missing.**\n\nThanks for pointing out the missing comparison. We will fix this in our manuscript. We also provide the comparison of the conductance gap between the two results in the following.\n\nIn [14], the conductance gap is $\\varepsilon\\ll O(\\varphi^3/{\\rm log}(k))$, and our conductance gap is $\\varepsilon \\ll O(\\varphi^2/{\\rm poly}(k))$."}, {"review_id": "mvgBRWWNnY", "reviewer": "Reviewer_Wy1e", "summary": "This paper studies the problem of constructing a spectral clustering oracle with sublinear pre-processing and query time complexity. The paper introduces a new algorithm which improves on previous methods with respect to the running time at the expense of a slightly worse approximation guarantee. In contrast with previous methods, the new algorithm is more practical as demonstrated by experiments on synthetic data.", "questions": "What is the purpose of $\\xi$ in Theorem 1? As far as I can see from the Theorem statement, it only appears in the running times, and always in the denominator - why not always set it to $1$?\n\nIs it possible to experimentally compare the algorithm with [30] and [14]? \n\n### Typos\n* Line 133 - space missing after '.'\n* Line 144 - space missing after reference [7]\n* Line 145 - Noted -> Note\n* Line 246 - dose -> does\n* Line 262 - space missing after 'Theorem'", "limitations": "Limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "On the theoretical side, this paper introduces a new sublinear-time clustering oracle with guarantees which improve on the previous state of the art in terms of running time. The new proof techniques are introduced in quite a natural way and the intuition is clearly explained. An important contribution of this paper is that the proposed algorithm is practical and admits an implementation.", "weaknesses": "The theoretical improvements over the previous algorithms are quite small (in particular, the improvement over [30]), however I don't view this as a major weakness given that the new algorithm is more practical.\n\nThe statement of Theorem 1 is quite difficult to follow. For example, the parameter $\\xi$ doesn't seem to be introduced or explained intuitively.\n\nThe experimental evaluation is quite limited - it does not include comparison with any other method, and does not report the running time of the algorithm. If the algorithm cannot be compared with that of [30] or [14], consider stating why this is the case in section 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the careful reading and the helpful comments. We fixed the typos in the updated manuscript. We slightly summarized your questions and provided detailed answers below.\n\n**Question 1: The statement of Theorem 1 is quite difficult to follow. What is the purpose of $\\xi$ in Theorem 1? It only appears in the running times, and always in the denominator - why not always set it to $1$?**\n\n(1) The primary intention behind the incorporation of $\\xi$ into Theorem 1 was to more effectively illustrate the tradeoff between preprocessing/query time and the precision of the approximation for the dot product of spectral embeddings. This approximation forms a pivotal component of our clustering oracle. However, upon further consideration, we acknowledge that including $\\xi$ in Theorem 1 is not essential (see below).\n\n(2) There is a typo for the upper bound of $\\xi$ in the statement of Theorem 1, that is, the correct range of $\\xi$ is $(\\frac{1}{n^5},\\frac{\\gamma k}{5}]$ (instead of $\\xi\\in (\\frac{1}{n^5},1)$). This range can be seen from the proof of Theorem 1 on page 8. \n\n(3) We concur that incorporating $\\xi$ into Theorem 1 is not essential. Instead, it is sufficient to substitute $\\xi$ with the upper bound $\\frac{\\gamma k}{5}$ and subsequently adjust the associated running times accordingly. In the next version of our work, we intend to implement this modification by directly replacing $\\xi$ in Theorem 1 with the aforementioned upper bound. \n\n**Question 2: Is it possible to experimentally compare with the algorithm in [30] and [14]? If it cannot be compared with that of [30] or [14], consider stating why this is the case in section 4.**\n\nThe algorithm in [14] is hard to implement.  As highlighted in our paper, the algorithm in [14] initially approximates the $k$ cluster centers by sampling around $O(1/\\varepsilon\\cdot k^4\\log k)$ vertices, and subsequently undertakes the enumeration of approximately $2^{O(1/\\varepsilon\\cdot k^4\\log^2 k)}$ potential $k$-partitions (Algorithm 10 in [14]). This enumeration process is extremely time-intensive and becomes impractical even for modest values of $k$. As suggested, we will explicitly state this factor in Section 4 to provide a clear rationale for our approach.\n\nRegarding the algorithm introduced in [30], it appears that its implementation is likely viable. However, our primary advancement over [30] is evident in the significantly reduced conductance gap we achieve. To thoroughly explore the comparative performance of our algorithm against [30], we aim to conduct new experiments. These experiments will focus on determining the specific graph ranges within which our algorithm outperforms [30]. In the upcoming version of our work, we are committed to implementing the algorithm from [30] and conducting the suggested experiments to provide a more comprehensive understanding of the algorithms' respective capabilities.\n\n**Question 3: The experimental evaluation is quite limited - it does not include comparison with any other method, and does not report the running time of the algorithm.**\n\nWe are pleased to share that we have generated new experimental results that enrich our evaluation efforts. We kindly request your review of the attached PDF file within our rebuttal, where these results are detailed. Notably, these additions encompass experiments focusing on the algorithm's running time and its robustness, providing a more comprehensive assessment of its performance. Your consideration of these findings is greatly appreciated.\n\n* [Running time experiments] Please see Table 1 in the PDF file. The experimental results show that the running time of a single query is between 0.5-0.7 seconds, and the pre-processing time of our oracle is between 15.9-18.2 seconds.\n\n* [Robustness experiments] Please see Table 2 in the PDF file. We evaluate our robust algorithm on an SBM graph after deleting delNum edges in each cluster (chosen randomly), where delNum is a parameter. We found that as long as delNum is not too large, our oracle has a small misclassification error, e.g. for 50 edge deletions in each cluster, the error is only $0.8\\textperthousand$. \n \n"}]

Author rebuttal:
In response to the review comments, we have incorporated two additional experimental outcomes and included a figure outlining the parameter tuning process for the theoretical algorithm. We invite you to refer to the attached PDF file for both the experimental results and the figure explanation. Your review of the attached PDF file is greatly appreciated. Thank you.

Meta-review: The paper received universally positive reviews -- it answers an interesting theoretical question -- improving the runtime of prior work on sublinear time spectral clustering oracles from exponential in the number of clusters and error parameter to polynomial, at the cost of requiring an exponentially larger (log k -> poly(k)) gap between the clusters.

While the paper is largely theoretical, one major concern was the experimental section. The authors have given expanded results during the rebuttal, which we hope will be included in the final version of the paper. We encourage the authors to address additional gaps, notably the lack of comparison to any other approaches. Or, at least to clearly mention the limitations of the experiments in the paper.
Decision: Accept (poster)