Sublinear Spectral Clustering Oracle with Little Memory
Authors: Ranran Shen
Xiaoyi Zhu
Pan Peng
Zengfeng Huang
Venue: ICLR 2026 Poster (2026)
Keywords: Spectral Clustering
Sublinear Algorithms
Memory-Efficient Algorithms
Space-Time Trade-offs
Random Walks
Primary area: learning theory

Abstract: We study the problem of designing *sublinear spectral clustering oracles* for well-clusterable graphs. Such an oracle is an algorithm that, given query access to the adjacency list of a graph $G$, first constructs a compact data structure $\mathcal{D}$ that captures the clustering structure of $G$. Once built, $\mathcal{D}$ enables sublinear time responses to \textsc{WhichCluster}$(G,x)$ queries for any vertex $x$. A major limitation of existing oracles is that constructing $\mathcal{D}$ requires $\Omega(\sqrt{n})$ memory, which becomes a bottleneck for massive graphs and memory-limited settings. In this paper, we break this barrier and establish a memory-time trade-off for sublinear spectral clustering oracles. Specifically, for well-clusterable graphs, we present oracles that construct $\mathcal{D}$ using much smaller than $O(\sqrt{n})$ memory (e.g., $O(n^{0.01})$) while still answering membership queries in sublinear time. We also characterize the trade-off frontier between memory usage $S$ and query time $T$, showing, for example, that $S\cdot T=\widetilde{O}(n)$ for clusterable graphs with a logarithmic conductance gap, and we show that this trade-off is nearly optimal (up to logarithmic factors) for a natural class of approaches. Finally, to complement our theory, we validate the performance of our oracles through experiments on synthetic networks.

Published as a conference paper at ICLR 2026
SUBLINEAR SPECTRAL CLUSTERING ORACLE WITH LITTLE MEMORY
Ranran Shen' Xiaoyi Zhu?, Pan Peng'. Zengfeng Huang
"ccoool of Computer Science and Technology, University of Science and Technology of China, Hefei, China "School of Data Science, Fudan University, Shanghai, China
Shanghai Innovation Institute, Shanghai, China
ranranshen@mail wus.....de.. en, 2huxy 22 @m. fudan. edu. cn, ppengeustc. edu. cn, huangz fudan edu..eduu... cn
ABSTRACT
We study the problem designing sublinear spectral clustering oracles for well- clusterable graphs Such an oracle is algorithm that, given query access the adjacency list of graph G, first constructs a compact data structure 'D that captures the clustering structure of G. Once built. D enables sublinear time responses to WHiCHCLUSTER (,, x) queries for any vertex A major limitation of existing oracles is that constructing D requires ( memory, which becomes a bottleneck for massive graphs and memory-limited settings. In this paper, we break this barrier and establish memory-time trade-off for sublinear spectral clustering oracles. Specifically, for well-clusterable graphs, present oracles that construct D using much smaller than (vv)) memory (e.g., O.000))) )) while still answering membership queries in sublinear time. We also characterize the trade- off frontier between memory usage S and query time T, showing, for example, that S T = (n) for clusterable graphs with a logarithmic conductance gap, and show that this trade-off is nearly optimal (up to logarithmie factors) for a natural class of approaches. Finally, to complement our theory, we validate the performance our oracles through experiments on synthetic networks.
INTRODUCTION
central task in graph analysis to uncover communities, which are groups of vertices that are more densely connected internally than externally. This problem. known as graph clustering. has long been a cornerstone graph theory and algorithms (Hagen & Kahng 1992 Chan et al. 1993 Ng et al. 2001 Czumaj et al. 2015; Peng 2020). Beyond its theoretical significance, graph clustering underlies diverse applications, ranging from community detection in networks (Van Gennip et al.
2013 Bedi & Sharmal 2016 Li ct al. 2024) to bioinformatics (Paccanaro al. (0066 and image
segmentation (Shi & Malik 2000) Felzenszwalb & Huttenlocher 2004).
Despite their importance, most graph clustering algorithms impractical for large graphs, they require reading the entire input, spending 2(()) time, and/or building data structures of size 9(n). where n is the number of vertices. Even when only few cluster memberships are needed, these methods still carry out full global computations, making them unsuitable for massive graphs where both time and memory (or space) matter but memory is the primary bottleneck.
From a systems perspective, this memory bottleneck is especially pressing. Many realistic environ- ments severely restrict available working memory: streaming models limit algorithms to a single pass with sublinear space; cloud-based platforms often impose high storage and data-transfer costs, making it infeasible to materialize the entire graph; and GPUs and TPUs offer massive compute but only modest on-chip memory relative to dataset size. In all these settings, the primary challenge is to fit a compact representation of the clustering structure into limited fast memory. Thus, developing memory-efficient clustering algorithms is not only theoretical pursuit but also practical necessity for analyzing trillion-edge graphs in modern computing environments.
"Corresponding authors.

---

Published as a conference paper at ICLR 2026
These considerations have motivated the study of local clustering oracles that run in sublinear time and space. Our focus is on sublinear spectral clustering oracles (Pengl 2020 Gluch et al.) 2021] Shen & Peng 2023), which construct compact data structure D from query access to the adjacency list of the graph. Once built, 'D enables efficient evaluation of W WHICHCL.USTER (G, x)) queries, that is, determining the cluster assignment of any vertex x without incurring the global ((n) costs. Importantly, these oracles return consistent assignments (with a fixed random seed) and closely approximate the ground-truth trruhh clustering, thereby making local access to clustering information both theoretically sound and practically useful.
Several recent works (Peng 2020, Gluch et al., 2021: Shen & Peng 2023) demonstrate that such oracles are possible under planted clustering assumptions, supporting cluster membership queries in both sublinear time and sublinear space. However, all existing sublinear spectral clustering oracles
require at least ((vz) space. In particular, Peng (Peng 2020) constructs an oracle using O m1)
space, while both Gluch et al. (Gluch et al.) (021] ) and Shen et al. (Shen & Peng 2023) require ((n2-5) space for any 8 S 2. which is again at least vn. We refer to Table and Section 1.3 for more details. For truly massive graphs, this requirement is prohibitive, as limited working memory and frequent main memory access quickly dominate the overall cost. This raises the central question:
Is it possible to design a spectral clustering oracle that breaks the ()( space barrier- - can we use substantially less memory while still achieving sublinear query time? If so, what kinds of trade-offs between space and query efficiency can be realized?
To the best of our knowledge, the question of establishing space-time trade-off for sublinear spectral clustering oracle has not been explicitly studied in the prior literature. This challenge is reminiscent of recent work
space-time trade-offs in learning, beginning with |aaz (2017)'s result on parity learning and later extended to tasks such as linear regression (Sharan et al. (019)) and noisy parity (Garg et al.
2021). In the area of distribution testing, series of works (Diakonikolas et al.. 2019
Berg et al.) 2022 Roy & Vasudev 2023] Canonne & Yang 2024) have established sharp space-time trade-offs for fundamental problems such as uniformity testing and closeness testing. Much like in these learning problems and in recent advances on distribution testing, the central question for sublinear spectral clustering is how far memory usage can be reduced without making query times impractically large.
In this paper, we give the first sublinear spectral clustering oracles with little memory (i.e., much less than (Vnr)) and a trade-off between memory usage and query time T satisfying S se Ö(n) (for a class of well clusterable graphs). We show that this trade-off is nearly optimal (up to logarithmic factors) for a natural class of approaches. In the following, we first present some basic definitions.
Basic definitions We measure cluster connectivity using conductance, a widely studied metric (e.g., (Chiplunkar et al.) 2018 Dey et al. 2019, Manghiuc & Sun 2021 [Shen & Peng] 2023 )) Let G (V, E) be an undirected graph. For any vertex v E V, let d, denote the degree in G. For any subset C' C V, let CC) = Enec d, denote the volume of C. For any two subsets S, C.V. let E(S, C) denote the set of edges between S and C.
Definition 1.1 (Outer and inner conductance). For any non-empty subset C C V, the outer conduc- tance and inner conductance of C is defined to be
Dout (C, V) EE(C, /ooo)),
min oin(C) sgC,
(S (S,C))
Specially, the conductance of graph G is defined to be (GG) =
min CCV:Dvwl(C)ss))())) Dont (C, V).
Intuitively, inner (resp. outer) conductance captures the internal (resp. external) connectivity of a cluster. A "good" cluster exhibits both large inner conductance and small outer conductance. Based on the definition of conductance, we give the formal definition of the input graph which is assumed to have planted clustering structure (see Definition 1.3)
Definition 1.2 (k-partition). Let G EV,E) be a graph. A k-partition of V is a collection of k disjoint subsets Cl...., Cs such that U._1 =V Definition 1.3 ((k, sp, el-uustteree graph). Let A 2 2 be an integer and let şo E (0, 1) and E E [0, 1). Let G (V,E) be graph. If there exists k- k-partition of V, denoted by C1 ... Cg. such that for C1....,
all i E [4], (C,) 2 s, Donl (C, V) S E and for all i,j E [b). one has |Cal |e, E (1), then we call G
is (be sp, -cllusteerabl graph.
2

---

Published as a conference paper at ICLR 2026
We work in the adjacency list model, where the algorithm query any neighbor of a specified vertex in constant time.
1.1 MAIN RESULTS
Sublinear spectral clustering oracle A key contribution of this work is spectral clustering oracle that operates with very little memory and provides an explicit trade-off between memory and query time. Given (k, ip, -clustebbee graph, the goal of clustering oracle is to build data structure D in sublinear time such that, for any vertex æ, the oracle can answer WIICHCLUSTER (G, (G,z) x) in sublinear time. Moreover, the clustering induced by answering WHICHCLUSTER x) for all should have a small misclassification error, that is, only a small fraction of vertices are assigned to the wrong clusters compared the ground truth.
In what follows, we state our main theorem in the simplified setting where ş = 2(1) and d, k: = 0(1). While state results for d-regular graphs, they naturally extend to d-bounded graphs, i.e., graphs in which every vertex has degree at most d (see Appendix Dj.
Theorem 1.1 (Informal main result; full statement Theorem 3.1, Suppose v 2(1), d,k 0()), and ε S h(d, k. 4) for some function h. Let G = (V, EV) be a d-regular (k, -clusttrlle graph with clusters Cl....,Cr Ck. Let nt (ee)) < M < 5 (n(2/22-0()) be a trade-off parameter. Then there
exists a sublinear spectral clustering oracle that:
constructs a data structure using Ō (nO M) bits of space,
answers any WHICHCL.SSTER query in Ô (n2+Ole) /M) time,
misclassifies at most (cs2/S)CC) vertices in each cluster C₁ i [k)].
Note that the space used to build and the query time T satisfy the trade-off T (0)
The oracle is built upon new subroutine ESTCOLLIPROB (Alg. D for estimating the collision probability of two random walk distributions with asymptotically space-time trade-off. In particular, when E < 1/ log n, this simplifies to S T = (()). The theorem establishes a trade-off: larger space yields faster queries, while smaller S slows them down. Unlike prior oracles that require at least S?( ()) space, our method operates with substantially less space, often far below yn, thereby breaking the /n space barrier.
We provide more detailed comparison between our main algorithmic result (Theorem 3.1 and prior work in Table [ Note that there are two types of results, one with (log is C)| misclassification error at the cost of larger space usage and query time (e.g., Gluch et al. (2021) and the other with (poly(kk) ) [ misclassification error and slightly smaller space usage and query time (e.g..
Shen & Peng 2023)
Table 1:
Comparison of our results (Theorem 3.1 with previous work terms of space usage, query time and misclassification error. We use O₂ to suppress dependence on o and Ö to hide all poly(log n)) factors. Here 8 E (0, ] is constant and n =/pp" < M S O O("'/2 1//--ote/v") parameter.
is a trade-off
k
work
space usage
query time
misclassification error
Peng 2000
Ōolyā poly())) (n--0ote) p))
ÖplVā- poly(
((kn/E) Ollog k e)JCC
Gluch et al.
1
(n poly($))
(Item]
(n M poly( (n pk))(k))
ò (n p)ly(?))
(n .poly(k))
Shen & Pene
2023
our (Item
(p((n))) M (ol)(k))
δ (000) poly(k))
(ppoy((k) [C]
for each cluster C,, E [k].
Previous oracles require at least 2( (n)) space usage while our oracle operates within much less space. Moreover, we stress that, our new clustering algorithms (Item) I and Item (2, although they introduce space constraint, affect only the space usage and query time; all other guarantees (e.g.. the conductance gap and the misclassification error) remain unchanged.
Distinguishing 1-cluster vs. 2-cluster As a corollary of our main result, we obtain a sublinear algorithm for distinguishing between single-cluster expander and graph consisting of two disjoint
3

---

Published as a conference paper at ICLR 2026
clusters. Formally, let yp (2(1 and d O(). Consider the following promise problem: the input a d-regular graph G (V, E) that is guaranteed to be in one of two cases: (i) G is a y--expanerr (ii) G is the disjoint union of two identical y-expanderss each on n/2 vertices (i.e.. (2, sp 0))clusterabbl). The goal of the 1-cluster vs. 2-cluster problem is to determine which case holds.
on vertices (i.e., 42, cluutterabb,,,,
We address this problem with an ESTCOLLIPROB-bae algorithm, yielding the following result.
Theorem 1.2 (Upper bound). For any trade-off parameter S M I O(yn), there exists an algorithm (Alg. 5 that, with probability at least 2n 1000 2n solves the 1-cluster vs. 2-cluster problem. Moreover, the algorithm:
uses (M) bits of space,
* rums in O (33 time.
We complement this with lower bound for distinguishing between the two cases when the graph can only be accessed through random walk queries.
Definition 1.4 (Random walk queries). For any specified starting vertex x, random walk query returns the endpoint of an Ollog -ttep random walk starting from T.
Theorem 1.3 (Lower bound). Any algorithm that correctly solves the 1-cluster vs. 2-cluster problem with error at most 1/3 using only random walk oracles must satisfy - (n)),, where and T denote the space complexity and time complexity of the al algorithm, respectively.
Note that a random walk query can be simulated with Ollog n) adjacency-list queries, so our upper bound matches the lower bound up to poly(log n) factors. Since the ESSTCOLLIPROB-baSS approach solves the 1-cluster vs. 2-cluster problem, our lower bound indicates that its trade-off off is nearly tight. This, in turn, suggests that the space-time trade-off of our clustering oracle is essentially tight, least for approaches based on collision probability estimation.
1.2 TECHNICAL OVERVIEW
Sublinear spectral clustering oracle To obtain sublinear spectral clustering oracles that rely on a log(k) or poly(k) conductance gap, a key primitive the estimation of the dot product (fz. fu), where fa is the spectral embedding of x E V (see Definition 1. Suppose there exists an algorithm that estimates such dot products using S space and time. can then design a clustering oracle based on this primitive, which uses (pooyy(k) 5) space to construct a data structure 'D and answers W WHICHCL.USTER queries in (poly(A) T) time (see Section 3.2 Thus, the central task is to understand the space-time trade-off for dot product estimation, as it directly determines the efficiency of the resulting clustering oracle.
Indeed, the previous Q ()) space bottleneck in constructing D arises precisely from this dot product estimation step. rather than from the clustering procedure itself. This observation motivates our technical improvements. In particular, the dot product estimation algorithm of GGuuh et al. (2021) does not directly compute (fz, fy) for arbitrary vertex pairs. Instead, it applies sequence of transformations and shows that estimating (fz, fy) can be reduced to computing the collision probability (M'1,) (M'1,)) = (M'1, 12, M'1.). where M is the random walk transition matrix of G and 1, is the indicator vector of vertex s.
Previous dot product oracle estimates (M'1,, M' by performing walks of length t O (logg)) from each vertex and y, respectively. The endpoints of these walks are stored to construct empirical distributions, whose dot product is then computed. This approach requires (R) words of space and O(Ri) time, tightly coupling space usage with computation time. In particular, to ensure sufficient accuracy, R. must be at least 9 ((vn), which implies that the space usage cannot be reduced below (v))).
vn independent random
To reduce the memory requirement below O(Vi)) and achieve a more flexible trade-off' between space and time, we propose a batch- estimation strategy. The idea behind this approach is inspired by Canonne & Yangl (2024), where similar batching technique is used to design memory-efficienn algorithms for uniformity testing under memory constraints. While the underlying technique is inspired by prior work, are the first to apply this idea in the graph setting to rigorously analyze
4

---

Published as a conference paper at ICLR 2026
random walks. Specifically, we partition the total of R random walks into B R/M batches. In each batch, M walks of length are performed from each vertex, and only the endpoints within the batch are stored to construct empirical distributions. The batch-level dot product is computed, and the final estimate is obtained by averaging over all batches. This approach reduces the space requirement to (MM) words while keeping the total number of walks. By choosing M smaller than ((yn), can achieve space-time trade-off satisfies M R 2 n. This allows for efficient estimation of the dot product even under memory constraints.
Distinguishing 1-cluster vs. 2-cluster The core idea of our algorithm (Alg. for distinguishing the I-cluster vs. 2-cluster is reduce the task detecting a spectral gap in the random walk operator. Specifically, we set t = Ollog rn/p²) so that in the 1-cluster case, the second largest eigenvalue of M becomes negligibly small, while in the 2-cluster case remains exactly To capture this behavior within bounded space, we avoid storing M' explicitly and instead construct a compact surrogate matrix 9 using the batch-based strategy described above. This surrogate preserves the essential spectral information of M', so that the separation between the two cases is faithfully reflected in the spectrum of g. Consequently, analyzing G suffices to distinguish between the 1-cluster and 2-cluster cases using only (M) space.
To prove the lower bound, we note that analyzing the distribution of random walks of the two cases reveals fundamental discrepancy: in the 1-cluster case, this distribution converges uniformity over the entire set of points; whereas in the 2-cluster case, it decomposes into two separate uniform distributions, each concentrated over half of the points. Under sublinear space constraint, the algorithm cannot store enough indices to reliably identify which cluster a given sample belongs to. We formalize this via the information--heorrttie framework for distribution-testinn lower bounds of Diakonikolas et al. (2019), showing that each observation provides only limited distinguishing information. Consequently, any algorithm requires a sufficient number of observations achieve statistical confidence, implying the stated space-time trade-off lower bound.
key novelty of our approach is a new reduction that connects random-walk-- walk-based graph clustering distribution testing. We construct paired hard instances and show how any random-wale algorithm for distinguishing 1-cluster vs. 2-cluster instances can be simulated in the distribution-testiie setting. The key technical contribution is an inductive coupling argument ensuring that the random-wale histories remain indistinguishable in total-variation distance. This reduction new and is what enables space-time lower bound.
with
1.3 RELATED WORK
Peng (2020) (see also (Czumaj et al. (015)) provided a robust sublinear spectral clustering oracle that constructs a data structure using (Vvi+ poly( & log )) bits of space and answers any WHICH- CLUSTER x) in OVV poly( & &oog log )) time. This oracle relies on a poly(k) log conductance gap between inner and outer conductance and misclassifies at most O(kny/) vertices. Gluch et al. [2021) (resp. Shen & Pengl 2023 Pp gave sublinear spectral clustering oracle that constructs a data structure poly( log )) (resp. O(n! O(n1- (6400)) poly (A: log n))) bits of space and answers any WHICHCLUSTER x) in (((8+0(c) poly( & <log))) ))) (resp. (1z poly(k ()) time, where 5 g) These two oracles have different conductance gap and misclassification error.
using 1n11-000
Recently, Neumann & Peng 2022) studied designing sublinear spectral clustering oracles for signed Secently,/Neumann
graph. Kapralov et al. (2023) studied designing sublinear hicrarchical clustering oracle for graphs exhibiting hicrarchical structure. We defer other related works to Appendix B due to page constraint. Moreover, all omitted proofs are provided in the appendix.
2 PRELIMINARIES
Let G = (V. E) denote an unweighted, undirected d-regular graph with n vertices, where V {1, 11. n3. Let E [n] denote S S n. For a graph (V, E), let e Raxa denote the
Although the paper does not explicitly state the space complexity, it can be directly inferred from the al algorithm description.
Shhen & Pengle 2003) stated their result for 5 1/2. Since their algorithm relies on the dot product oracle in
Gluch al. 2021 the guarantce extends naturally to any 8 E (0, }
5

---

Published as a conference paper at ICLR 2026
adjacency matrix of G, where A(i.)) 1f (i.)) E E, and A(i.j) =0 otherwise, i,j [n]] Let D IR" denote a diagonal matrix, where ti,, = d, E [n]. Let L = D (D A)
I- denote the normalized Laplacian matrix of G. where I E R= is the identity matrix. For L. we use 0 A I I An I to denote its eigenvalues and Ui...., Un R to denote the corresponding eigenvectors. Without loss of generality, we assume {uI.... un forms an orthonormal basis of IR.. Let U (u1.... AuI..... U..)) R Based on U. give the definition of spectral embedding (see Definition 2.1 Moreover, let M = ) + A) I 2/2 denote the transition matrix of lazy random walk on G. That is, if the walker is currently at a vertex x E V, then in the next step it stays with probability 2.2 moves to each neighbor of with probability 2d."
Let R" denote column vector (unless otherwise stated). For any two vectors a, b E R", (a, b) = a to denote the dot product of a and b. For any x E V, let 1g E R" denote the indicator vector of x, where (i) 1 if i x and 0 otherwise. For any symmetric matrix B E Rax", use uy (B) to denote the i-th largest eigenvalues of B.
Definition 2.1 (spectral embedding). Let G EV, be graph. For any vertex V. fz E R to denote the spectral embedding of z, where fz = U 1 = (ui (z).......... uz(x))²
Definition 2.2 (o-expander). Let G = (V, E) be graph. Let o E (0, Let @GG) denote the conductance of G (see Definition 1.1. If (G) 2 ş. then we call G -p-expander.
The supplementary preliminaries are deferred to Appendix C
SPECTRAL CLUSTERING ORACLES WITH LITTLE MEMORY
In this section, present and prove main algorithmic result, stated in the theorem below. We emphasize that the resulting algorithms exhibit different trade-offs between the conductance gap (p vs. <), the misclassification ratio, and the corresponding space-time bounds, depending on the clustering algorithms employed, either that offhh et al. (2021) or [Shen & Pengl (2023).
Theorem 3.1. Let k > 2 be an integer. P, E (0, 1) and hı (k, sp), h2(k, and ha e) be three functions. Let & < (k: v). Let G = (V. E) be a d-regular and (ki, 4,, -l-ussterralll graph with Ci....,Cu, Let n////² < M < O( 0(""/2-00e10" k enough constant. There exists sublinear spectral clustering oracle that, with probability at least 0.9:
be a trade-off parameter, where e is a large
constructs a data structure D using (b2 o(e//))) M) bits of space,
answers any WHICHCLUSTER query using D in Ō (h2(k) n (1+0(s/0)), 3)) time, has O (ha(k, ep) [Cs] misclassification error for each i [k]]
where we use O2p to suppress dependence on yp and Ô to hide all poly(log n) factors and:
1 if hy (k: = Tugk: then h2(k, 8) = (()0(1) and ha(k, e) + log k; if h1 (ki,
=² then fug(k) (4) and ha(k, s,.) (5) k3, where
13 log"
7 E (0.001, 1] is a constant such that for all i E [R]. 7E < |C,| S 7k-
This section is organized as follows. In Section 3.1 we present our dot product oracle with little memory and the corresponding algorithms. In Section 3.2 we provide the proof of Item 2 of Theorem 3.1
The proof of the remaining case, Item deferred to Appendix
3.1 DOT PRODUCT ORACLE WITH LITTLE MEMORY
Our objective in this section is to design a dot product oracle that approximates ff) while achieving a favorable space-time trade-off and ensuring small approximation error. The following theorem states the performance guarantees of our oracle. Proof is deferred to Appendix
Recall that fa denotes the spectral embedding of vertex (see Definition 2.1
Theorem 3.2. Let k > be an integer. Let x 10, with +
I
I. TOr. Let G = (V,E) be
<E< L. Let 1 < M Manary S 00 0/222/2-20//22 d-regular and (k, 9, clusstrbbeee graph. Let 1 n5 Then, with probability at least 1- 2n
-2n-100 100 INITORACLE(G, k. K, Mia) (Alg. 3 computes a sublinear space matrix Ve of size n O(el4") log" (+) (1)),,, such that the following property is satisfied:

---

Published as a conference paper at ICLR 2026
for every pair of vertices x, V, QUERYDOT(GGRR V. V, Mquery) (Alg. computes output value (fzz Sylaps such that with probability at least 1 6n. -n.-10;
Kf fylaps (fa: fu)
Moreover, let Sinit, Timi be the space and time costs of INTTORACLE(G.A k: &. Maai) 3 and let Squery T query be those of single QUERYDOT v, M, V, Mquery) query (Alg(4). Then we have
SSn (1)) n O(E/4") Mini log n, Tim = (+)(()) n1+0(e/44)
log
Mun
S query
)0() ((sl1)) Mquery log n, Tquery" = ($) nl+0(e//")
log
Magar
Note that ensure that INTTORACLE(G, Miin) (Alg. and QUERY (Alg. run sublinear time, is required that Mina Mquery 2 n where e is a constant that larger than the constant hidden in O(-) O--)-term of (1+0(e//") in both Tin and T query.
M,
Mquer)
For initializing the dot product oracle, the previous dot product oracle in Gluch et al. (2021) requires at least 92 (z)) bits of space, whereas our proposed oracle can perform accurate estimation using at most (vvn) bits of space, thus breaking the vn barrier.
The algorithm Algorithm ] estimates the collision probability (i.c., (M'1, M'1,) of the random walk distributions from two given vertices within bounded space Ö(M). This bounded- space guarantee achieved through our batch technique, and we are the first to apply this idea the graph setting for analyzing random walks. Algorithm Seporithm@copppn computes an estimate of the Gram matrix corresponding to the random walk distributions from a set of vertices, where S E 1 99 is a matrix whose i-th column is an indicator vector Hg for v S, while operating within bounded space Ö(M (S)P). The formal guarantees of these two procedures are stated respectively.
in Lemma 3.1 and Lemma E.5
Lemma 3.1. Let k 2 2 be integer and 9, E 10,1). Ler (V, E) be a d-regular and (ks, up, elcctssterable graph. Let M be the random walk transition matrix of G. Let be the output of ESTRWDoT(G, R, t, M, x, y) (Alg. [ Let Our > O. Let 1 be large enough constant. For
any 20 20log and any x, y V, if R 2ik 400/002 and 1 S M O 200/02
then with
8²
probability least 0.99, we have
Z - (M'M, M'1,)| oor.
Jer.
Moreover, ESTRWDOT R,4, M, y) runs in ORR)) time and uses O(M -logn) bits of space.
Algorithm 1: ESTRWDOT
Algorithm 2: ESTCOLLIPROB
(G, M, x. v)
(G. R, t, M, Is)
Z = 0, = & B: number of batch
R
s == [s| = (81,...,
M
2 for to B do
for ( = to Ologgn do
3 Run M independent random walks of length & starting from x (resp. from 3))
for iori= 10 s do
for i to do
Gr(j = Gi(i.j) f)= ESTRWDOT(G, R2, 8,8)))
Define (1) (resp. (i)) as the fraction of randoms walks from æ (resp. from y) that end at
5
Z4 = Py),
7v
Let G be matrix obtained by taking the entrywise median of Gi's
6
7 return
return G
Algorithm initializes the dot product oracle by constructing a compact matrix within approx- imately bounded space Ö(M). Then Algorithm 4 leverages to estimate (fz; Sy) while still operating under the same bounded space. The formal guarantees of these two procedures are stated in Theorem 3.2
7

---

Published as a conference paper at ICLR 2026
Algorithm 3: INITORACLE
Algorithm 4: QUERYDOT
(G, ki, C, Mint)
(G, x. y, E.V, Mquery)
:= 20
t == 20
2 Rinit = =0(" 20 202200/0
k1 g
Rquery = O 2 144006/02
Mun
Manerry
3 8 == O(n250-=//
log n 1 4 Let 15 {81, 9 Sy) be the multiset of indices chosen i.u.r. from
/-2)
a for to Olog n) do
for i =1 to do
(1) = ESTTRW ESTRWDOT(C. DOT Rquery. t, Mquery, I., 8t)
V -L.....,
5 G =
ESTCOLLIPROB G. Riit t, Main, Is)
(1 = ESTRES DOWWDDT((O G. Rquery- L, M querys y/ 81)
Let - G = WWWT be the eigendecomposition of !h
7 Let a (resp. ayy) be a vector obtained by taking entrywise median of an 's (resp. y1 ')) Oxz, Cit E RR
7 if 1- exists then
8 = -. Wi 5-2WT
D V E Rox*
return [k] (
8 return (fz, Su)apx = a Yay
3.2 CLUSTERING ORACLE: ITEM 2 OF THEOREM 3.1
We now present the proof of Item 2 Theorem 3.1 and give a clustering oracle with the corresponding space-time trade-off. Item 2 which addresses a sublinear spectral clustering oracle under poly(k) conductance gap. Our sublinear spectral clustering oracle closely follows the construction in [hhen & Peng 2023), except that we substitute our dot product oracle from Section 3.1 in place of theirs.
High-level idea of the algorithm Now we briefly outline the main idea of the oracle. Shen & Peng (203) showed that for most vertices in (kt, cluuttrrbbe graph, æ;, y E belong the n. otherwise, (fz. fu) ss O. Leveraging this property, we can design k log vertices to form a set S, and for each pair
same cluster, then (fz. fu)
} = &,
clustering oracle as follows: it first samples
u, S, it computes the dot product (fw, fu)apx using new dot product oracle. If the value is large, an edge (u, u) is added to the initially empty similarity graph H = (S, 0). At query time, the oracle uses H and its connected components to determine the cluster assignment of vertices. We provide full description of the clustering oracle in Appendix G Now we present the proof of Item 2 in Theorem 3.1 follows.
Proof of Item in Theorem 3. Space and runtime. In the preprocessing phase, CONSTRUCTOR-
ACLE(G, k, 8, Y, M) (Alg. invokes INITORACLEEG, k. M) (Alg. one time to get
matrix V/ (see line 5 of Alg. 12 then CONSTRUCTORACLE k, (p, 6, 7, M) invokes our QUERY-
DOT(G, u, E, Vr, M) O log k)/+²) times (see lines 6 ~ 9 of Alg.
12 to get a similarity
graph H. Therefore, CONSTRUCTORACLECC k. E, M) uses Snir + O log k)/ Squery bits of space. Using Theorem 3.2 we get that CONSTRUCTÖRACLE/ G, k, p,e, Y, M) uses (le/vo) M poly( & logn )) bits of space to get matrix V and a similarity graph H.
In the query phase, WHICHCLUSTER G, M) (Alg. 14 invokes SEARCH H, E, x. M) (Alg. 13 one time. SEARCH f, x. M) invokes our QUERYDOT(G; u, x. E. V, M) O(k log k)/r) times (see lines 1 ~ 2 of Alg. 13). Therefore, in O((k log k)>)) quary time. Using Theorem 3.2 we get that WHICHCL.USEERCG x, M) uses O(n M poly(" logg)) bits of space and runs in O( 1 poly( &log Tp time.
13 and relies on the similarity graph H (see lines 3 ~ 6 of Alg. M) uses O(kk log k)/7) Squery bits of space and runs
Thus, the oracle constructs a data structure (ineluding V, similarity graph H etc) using O(n Ole M poly( (logn) )) bits of space. Using D, any WHICHCLUSTER(G..t x) query can be answered by Alg. 14 in O( (+0es/p") 1
poly( klog time.
M
Correctness. Since the correctness guarantees (i.e., conductance gap and misclassification error) of the clustering oracle rely the properties of the dot product oracle, and our dot product oracle satisfies
8

---

Published as a conference paper at ICLR 2026
the same correctness guarantees with the previous one, the correctness of the overall clustering oracle follows directly from the correctness of the clustering oracle in Shen & Peng (2023).
4 DISTINGUISHING I-CLUSTER VS. 2-CLUSTER
The algorithm and sketch of its analysis Now we present Alg. 5 for solving the 1-cluster vs. cluster problem, which is based estimating the second largest eigenvalue of M using subroutine
ESTCOLLIPROB (Alg. 2 from Section 3.1
Algorithm 5: DISTINGUISIIC,,
t:= 20 R O M Ol
Let === :....... 82) be the multiset of s indices chosen independently and uniformly at random from V = (1......)
-ESTCOLLIPROD G, R2 M,)s)
Let (2(" be the second largest eigenvalue of matrix g
[22 ()))) < 0.6 then
return "1-cluster"
return "2-cluster"
The formal guarantee of this algorithm is given in Theorem 1.2 whose proof is deferred to Appendix Here, we provide a proof sketch.
Consider the when the input graph G is ---expander. By Cheeger's ' inequality (Lemma H.1p
we get that the second smallest eigenvalue of L satisfies A 2 w²/ 02. Equivalently, the lazy random walk matrix M
L/2 has its second largest eigenvalue (2(M) < 1 -s² -2//4. In contrast, if G consists of two disjoint ge-expanders of equal size, then X2 = 0 and hence U2
U2 (M) 1. Setting t O(log n/ )²",, we obtain that in the 1-cluster case, the contribution of (2(M)
10 while in the 2-cluster case, U2 M) remains exactly 1. Thus, M exhibits a clear spectral gap between the two cases. Alg. 5 constructs an approximation G se (M' (M'' E IR O n) x)xO(log x) within bounded space, where each column of M' 5 corresponds the t-step lazy random walk distribution starting from vertex in the sampled set Is. The second largest eigenvalue of G closely reflects that of M thereby preserving the above separation (see Lemma H.4 for the formal statement). Moreover, since G is small matrix, we can afford to perform an eigen-decompositiin Consequently, examining the spectrum of & suffices to distinguish between the 1-cluster and 2-cluster cases using (MM bits of space and O(n/M) time.
it directly.
The lower bound The lower bound for distingushing 1-cluster vs. 2-cluster is summarized in Theorem I.3 The main proof of Theorem 1.3 is presented in Appendix Mand comprises two parts. First, we establish lower bound for distinguishing between uniform distribution over all vertices and two separate uniform distributions each over half of the vertex set. We demonstrate that under a space constraint of S, the information regarding the underlying case can only increase by ((S/n) per observation. Consequently, the total number of observations T must satisfy T ((S(())) R(1), which directly implies the space-time trade-off lower bound S T ((n) (see Theorem I.2p
Second, by analyzing the random walk distributions in the 1-cluster and 2-cluster cases, we observe that these distributions closely approximate the two aforementioned reference distributions. To finalize the reduction, it is necessary to demonstrate that deviations from uniformity do not significantly alter the final memory state distribution. The key challenge lies the cumulative effect sampling distribution discrepancies at each step, which collectively influence the memory state. To quantify this discrepancy, we adopt the total variation distance as a metric and employ a mathematical induction argument. This approach shows that the discrepancy in the memory state distribution does not substantially amplify after each sampling step. Specifically, the incremental increase in discrepancy is proportional to the difference between the sample distributions and remains controllable. Consequently, the overall discrepancy is bounded by the sum of these incremental increases and remains negligible throughout the process.

---

Published as a conference paper at ICLR 2026
5 EXPERIMENTS
To evaluate the space-time trade-off of our sublinear spectral clustering oracles, we conducted experiments in Python on graphs generated from the stochastic block model (SBM) with parameters (num of vertices), k (num of clusters), and edge probabilities p (within-cluster) and (between- cluster). Experiments were run on a server with Intel(R) Xeon(R) Platinum 8562Y processor (2.80 GHz) and 768 GB RAM. Each reported data is the average over five independent runs.
We implemented two variants of the poly -oonuucttnee from Shenn& & Peng (2023), and our memory- memory-effciiet variant that operates within a smaller space. For each, we recorded the number of words stored in each component of the data structure as proxy for space S, evaluated accuracy (the fraction of vertices correctly classified), the success rate (i.c., the fraction of successful runs among runs Both variants used the same number of sampled vertices, random walk length, and median -tickktrkkkkkk repetitions; differences arose only in space-time-related parameters. We instantiated this setup on an SBM graph with n = 3000, & = 3, p 0.07, and g = 0.002, yielding clusters of 1000 vertices each. Additional implementation details are provided in Appendix
clustering oracle the original oracle
Space efficiency Prior sublinear spectral clustering oracles require at least D n1) space to construct data structure D. In contrast, our clustering oracle allows constructing D using substantially less space, well below vn. In this section, we provide experimental evidence validate this improvement.
Table 2: Comparison of space usage for clustering oracles, with 10400 words used as the baseline.
clustering oracle
ours
previous
space (# of words)
9900
10100
10400
34840
43888
44383
61223
space (x baseline)
0.95x
0.97x
1x
3.35x
4.22x
4.27x
5.89x
success rate for constructing D
1
1
1
0
0.6
1
1
accuracy
0.9833
0.9900
0.9907
0
0.9860
0.9997
1.0000
Table demonntrate that our clustering oracle achieves high accuracy using substantially less space (10400 words as 1x). In contrast, the previous clustering oracle requires 4.27 times of the baseline space achieve comparable accuracy, and even when given 3.35 times the baseline space, it fails to construct D successfully (i.e., success rate is 0). These results confirm that our approach significantly improves space efficiency without compromising accuracy.
Space-time trade-off As established in Theorem 3.1 there is a trade-off between the space S required to construct ID and the query time T, satisfying S T = Ö(n +0()), where e is the small constant corresponding to the outer conductance.
10400
Space vs. Time
To validate this experimentally, we also mea- sured S as the total number of words stored to construct D. We use the total number of random walks per WIICCHCLUSEE query as a proxy for time T, since this dominates the query cost. Across all tested parameter settings, the oracle maintains high accuracy (0.9833 1), confirm- ing the practical validity of the configurations used.
10300
30200
space
10000
9900
Figure Plots 5 (y-axis) versus T (x-axis), il- lustrating the space-time trade-off:: memory us- age decreases as query time increases, and vice versa, consistent with the theoretical bound.
0.6
0.8
1.0
1.2
14
query time (+ of random walks)
le6
Figure Space-time trade-off of the sublinear spectral clustering oracle, showing S, T are in- versely proportional.
'We did not experiment with the concku)acoonct gap oracle due to its impractical runtime of 2
n 1+-0(s) 1 for constructing D.
3f
'If the available space is too limited, the construction of the similarity graph H7 may yield either too many few connected components, in which case the construction of D fails.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Ranran Shen and Pan Peng are supported in part by NSFC Grant 62272431 and Quantum Science and Technology National Science and Technology Major Project (Grant No. 2021ZD0302901, Xiaoyi Zhu and Zengfeng Huang are supported in part by National Natural Science Foundation of China No. 62276066.
ETHICS STATEMENT
This work is purely theoretical and algorithmic in nature. Our experimental evaluation is conducted solely synthetic datasets generated from the stochastic block model (SBM). The research does not involve human subjects, personal data, or other sensitive information. We do not anticipate any immediate ethical, societal, or environmental risks arising from our methods or results.
REPRODUCIBILITY STATEMENT
We have taken several steps to ensure the reproducibility of our work. All theoretical results are stated formally in the main text and accompanied by complete proofs in the appendix. The assumptions underlying our results are explicitly described. For the experimental evaluation, we used standard stochastic block model (SBM) graphs to ensure reproducibility. Implementation details and parameter settings are included in Appendix
REFERENCES
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 (66), pp. 475-486. IEEE, 2006.
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.
Sepehr Assadi, Xiaorui Sun, and Omri Weinstein. Massively parallel algorithms for finding well- connected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on principles of distributed computing, pp. 461-470, 2019.
Sepehr Assadi, Christian Konrad, Kheeran K Naidu, and Janani Sundaresan. O (log log n) passes is optimal for semi-streaming maximal independent set. In Proceedings of the 56th Annual ACM
Symposium on Theory of Computing, pp. 847-858, 2024.
Punam Bedi and Chhavi Sharma. Community detection in social networks. Wiley interdisciplinary reviews: Data mining and knowledge discovery, 633::155-135 2016.
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghh Ha- jiaghayi, Richard M Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 481-490, 2019.
Tomer Berg, Or Ordentlich, and Ofer Shayevitz. On the memory complexity of uniformity testing. In Conference on Learning Theory, pp. 3506-3523, PMLR, 2022.
Clément L Canonne and Joy Qiping Yang. Simpler distribution testing with little memory. In 2024 Symposium Simplicity in Algorithms (SOSA), pp. 406-416. SIAM, 2024.
Pak K Chan, Martine DF Schlag, and Jason Y Zien. Spectral k-way ratio-cut partitioning and clustering. Proceedings of the 30th international Design Automation Conference, pp. 749-754, 1993.
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 497-508. IEEE, 2018.
Artur Czumaj, Pan Peng, and Christian Sohler. Testing cluster structure graphs. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pp. 723-732, 2015.
11

---

Published as a conference paper at ICLR 2026
Tamal K Dey, Pan Peng, Alfred Rossi, and Anastasios Sidiropoulos. Spectral concentration and greedy k-clustering. Computational Geometry, 76:19-32, 12,99-222220 2019.
Ilias Diakonikolas, Themis Gouleakis, Daniel M Kane, and Sankeerth Rao. Communication and memory efficient testing of discrete distributions. In Conference on Learning Theory, pp. 1070- 1106. PMLR. 2019.
Pedro F Felzenszwalb and Daniel P Huttenlocher. Efficient graph-based image segmentation. Inter- national journal of computer vision, 59:167-181, 2004.
Sumegha Garg, Pravesh K Kothari, Pengda Liu, and Ran Raz. Memory-sample lower bounds for learning parity with noise. arXiv preprint arXiv:2107.02320, 2021.
Mohsen Ghaffari and Krzysztof Nowicki. Massively parallel algorithms for minimum cut. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 119-128, 2020.
Shayan Oveis Gharan and Luca Trevisan. Partitioning into expanders. In Proceedings of the twenty-fifth anmual ACM-SIAM symposium on Discrete algorithms, pp. 1256-1266. SIAM, 2014.
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Christian Sohler. Spectral clustering oracles in sublinear time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1598-1617. SIAM, 2021.
Lars Hagen and Andrew B Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE transactions on computer-aided design of integrated circuits and systems, 1109):0774-085, 1992.
Michael Kapralov. Better bounds for matchings in the streaming model. In Proceedings of the twenty-oorrhh annual ACM- symposium on Discrete algorithms, pp. 1679-1697. SIAM, 2013.
Michael Kapralov, Akash Kumar, Silvio Lattanzi, and Aida Mousavifar, Learning hierarchical cluster structure of graphs in sublinear time. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithmms (SODA), pp. 925-939. SIAM, 2023.
Jakub Lącki. Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Walking randomly, massively, and efficiently. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 364-377, 2020.
Jiakang Li, Songning Lai, Zhihao Shuai, Yuan Tan, Yifan Jia, Mianyang Yu, Zichen Song, Xiaokang Peng, Ziyang Xu, Yongxin Ni, et al. A comprehensive review of community detection in graphs. Neurocomputing, 600: 1281122119 2024.
Adrian Manghiue and He Sun. Hierarchical clustering: approxxiioinn for well-clustered graphs. Advances in Neural Information Processing Systems, 34:9278-999 99879, 2021.
Stefan Neumann and Pan Peng. Sublinear-time clustering oracle for signed graphs. In International
Conference on Machine Learning, pp. 16496-16528. PMLR, 2022.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
Krzysztof Nowicki and Krzysztof Onak. Dynamic graph algorithms with batch updates in the massively parallel computation model. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2939-2995 SIAM, 2021.
Alberto Paccanaro, James A Casbon, and Mansoor AS Saqi. Spectral clustering of protein sequences. Nucleic acids research, 34 2006.
Pan Peng. Robust clustering oracle and local reconstructor of cluster structure of graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2953- 2972. SIAM, 2020.
Ran Raz. A time-space lower bound for a large class of learning problems. 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pp. 732-742. IEEE, 2017.
12

---

Published as a conference paper at ICLR 2026
Sampriti Roy and Yadu Vasudev. Testing properties of distributions in the streaming model. arXiv preprint arXiv:2309.0322 09244, 2023.
Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoff's for linear regression with small error. In Proceedings of the 51st Annual ACM SIGACT Symposium Theory of Computing, pp. 890-901, 2019.
Ranran Shen and Pan Peng. A sublinear-time spectral clustering oracle with improved preprocessing time. Advances in Neural Information Processing Systems, 36, 2023.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-99) 905, 2000.
Daniel A Spielman and Shang-Hua Teng. local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning, SIAM Journal on computing. 42(1):1-26, 2013.
Yves Van Gennip, Blake Hunter, Raymond Ahn, Peter Elliott, Kyle Luh, Megan Halvorson, Shannon Reid, Matthew Valasik, James Wo, George E Tita, et al. Community detection using spectral clustering on sparse geosocial data. SIAM Journal on Applied Mathematics, 73(1):67-83, 2013.
Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well-connected clusters. In International Conference Machine Learning, pp. 396-404. PMLR, 2013.
13

---

Published as a conference paper at ICLR 2026
Appendix
The appendix is organized as follows.
Appendix
A provides statement
use of L.MSs for English writing assistance. provides additional related works omitted from the main text.
Appendix
Appendix
presents supplementary preliminaries.
Appendix shows that how our results for d-regular graphs can be extended to d-bounded
graphs.
Appendix presents the proofs of Theorem 3.2 which concerns our dot product oracle that
operates under limited memory.
Appendix F provides the proof of Item i our main result (Theorem 3.1
Appendix G
describes the sublinear spectral clustering oracle related Item i our main
result (Theorem 3.1).
Appendix presents the proof of Theorem 1.2.
which gives the upper bound for distinguish-
ing 1-cluster vs. 2-cluster problem.
Appendix prressenss the proof of Theorem 1.3 which gives the lower bound for distinguish-
ing 1-cluster vs. 2-cluster problem.
Appendix proovides details on the experimental setup and parameter choices.
A
THE USE OF LARGE LANGUAGE MODELS (LLMS)
During the preparation of this manuscript, mainly used ChatGPT to assist with English writing. Specifically, the model was employed to improve the fluency of sentences, check grammar, and seggeststylisttce suggest stylistic refinements. We emphasize that all theoretical contributions, proofs, and experimental results (including code implementation, simulations, and results collection) were developed and verified solely by the authors without the involvement of LLMs. The of LLMs did not influence the research process, methodology, or the originality of the results presented in this paper.
B OTHER RELATED WORK
Property testing Besides the above most directly related work sublinear spectral clustering oracles, several other research directions are also relevant to our study. One line of work is property testing (i.e., testing graph clusterability), where the goal is quickly distinguish whether graph can be partitioned into k clusters with high inner conductance, or whether it is far from having such clustering. For example, Czumaj al. (2015) studied testing whether graph admits a good cluster structure in the adjacency list query model, providing algorithms with sublinear query time, This direction was later advanced by Chiplunkar et al. (2018). While property testing algorithms do not provide explicit cluster assignments, they capture the fcasibility of clustering in sublinear resources and thus serve as an important precursor to oracle-hased approaches like ours. For example,Cxumaj Czumaj et al. (2055) implicitly yields sublinear spectral clustering oracle under a log conductance gap. This was later extended by Peng (2020), who developed a robust oracle capable of handling noise.
Local graph clustering Another line of related work is local graph clustering (Andersen al. & Teng 2013, Zhu et al. 2013) Gharan & Trevisan 2014] Andersen et al. 2016). The goal of this category is to identify a cluster associated with a given vertex. In this setting, the algorithm outputs set of vertices related to the input vertex, and its running time and memory usage are bounded by the size of the output cluster, up to a weak dependence on n. In particular, when the graph contains & clusters and vertices, the complexity can be large as ((n/k))
Grapah problems under limited memory Recently, there has been surge of work on understand- ing learning under limited memory. Graph problems inherently require substantial space and time to compute, and have attracted increasing attention. One line of research focuses on the semi-streaming model where the algorithm is permitted O(n pooy n)) space. Both upper bound algorithms and lower bound results are proposed for various graph problems, including Maximal Independent Set (Assadi et al. 2024) and Matching (Kapralov) (2013). There is also significant work on the Massively Parallel Computation model, where machines have sublinear memory solve the graph problems
14

---

Published as a conference paper at ICLR 2026
(Behnezhad et al. 2019 Lacki et al. 2020 Nowicki & Onak 2021 Assadi al. 2019 Ghaffar & Nowicki 2020).
C SUPPLEMENTARY PRELIMINARIES
For a vector (a(1)..... ((()), the p-norm (p 2 1) of a is defined to beilallp
(E==1((1)) For any matrix B E R we use |B] F Ej (i( de- note the Frobenius norm of B, |B maX and Big to denote the first i columns of B, S S n.
Bar la denote the spectral norm of B
Definition C.1 (TV distance). For two probability distributions p. over [n], the total variance distance (i.e., TV distance) of p, q is defined to be
dp q) 2 Ip a111-
Fact C.1. For any vector p E R", we have |pll S |pl|
Proof. Let |/pll00 max p())). Then, we have
|pli
p (1) S
pi)
|pll
/ P
(1)
i=1
Σ (1)
Σ p2(1)
1p1.2
D FROM d-BOUNDED GRAPHS TO d-REGULAR GRAPHS
Although we state our results for d-regular graphs, they extend naturally to d-bounded graphs, i.e., graphs in which every vertex has degree at most d. The extension is straightforward: for d-bounded graph G' = (V, E"), ), for every d-regular graph G (V, E). Note that the lazy random walk on G is equivalent to the random walk on G', with the random walk satisfying that if the walker is currently at E V, then in the next step it stays at & with probability 2
V, we can add d - de self-loops with weight 1 to to get
di
or moves to each neighbor of x with probability 2d_
E PROOF OF THEOREM 3.2
Theorem E.1 (Restate of Theorem 3.2p. Letk 2 be an integer. Let e, yp E (0, with &or S -h.. Let
G = EV be a d-regular and (k, pp, (.)..cccustteablll graph. Let + < & < 1. Let 1 S Minis Mqqary
O o ). Then, with probability at least 1 2n 100, INITORACLE(G, k. E, Muau (Alg- computes sublinear space matrix Va of size Ole/ log" n (1), such that the following property is satisfied:
for every pair of vertices x, E V. QUERYDOT(C. x, E. V. Mggorr) (Alg. computes an output value (fzz fylaps such that with probability at least 1 6n-100;
kffz fulaps
(fa. felff)
15

---

Published as a conference paper at ICLR 2026
Moreover, let miit: Smit be the time and space costs of INITORACLE(G,, k. Mma) (Alg 3. and let
T Tquay. Squary be those of a single QUERYDOT(G, z, y, &, V, Mquery) query (Alg4). Then we have
min (0)) n=100(//6)).
los' n
Mun
S (())0)) . ole/4") Mint log"
querry = (4) nn 1+((t//))
log m
Moxas
Squery
(()) n n(=/p")) Mquery
log" n.
To prove Theorem 3.2
we begin by analyzing Za defined in Alg. [ The following lemma shows that Zo is an unbiased estimator of (M'1,, M and quantifies its variance.
Lemma E.1. Ler = (V, E) be a graph. Let R. M be integers, where 1 S M < R. Letz.yEV
be two vertices. Let M be the random walk transition matrix of G. Let 74 (1 < bb & be the
random variable defined in ESTRWDOT(G, R, t, M, x, v,y) y) (see line 6 of Alg. 7 Then, we have
BiZy| (M' M'1.),
Var[Zz]
M M 1M
|M'1,l2 M (IMM 1|M || 1| l2)
Proof. Run M random walks of length from (resp. from y). Let (i) (resp. ci)) denote number of random walks from (resp. from y) that end at vertex i. It's clear that we have (1) c=(i)
M and (i) = (,(t) Mr (see lines ~~ of Alg. 1. Let Ps = M'1, (resp. Py = 1)) be the probability distribution of length random walk starting from r (resp. from y). Note that (t) ~ Binomial(MM) M, Pa (i)) and (2) ~ Binomial (M,, Py (t)). According to line 6 of Alg. [ we
have Zn = Px. Py) Therefore, about Zr), we have
E Zn]
(Dn, Puy)
E
Pa (1)
(1)
M
n
c/ (1) ( (c)
M²
1
Mp.
M
Σ
(1()))y()
1=1
(Da, P.y) (M' 1,, M'1,).
About Varl [Z), since Var(Zp] = F[ZE]
(E| [b,) suffices to calculate R[ZZ] to get Var [z).
B[Z E [ p
27
E
Σ (.P
E
Pa 2.000,0000000000
16

---

Published as a conference paper at ICLR 2026
(1000,
M
72
B c2 (1) (1) (lc,00,,,())
M
==
E
[c
Bl,x(()c, Blc(00)
M
For convenience, J
A1 to denote Mr Σ E [c) E [c] and A2 to denote E Ej=1j B (1)es (1)(())()))))
M' Ei=
Since C, (i) ~ Binomial(M, p= (i)), we have E[cx(1) = (1. and El = Var(ea (i) +
(Elc,, (i)))² (pz(1) Pa (i) (1) (i) + (M 1)p (i). Therefore, have
1
A =
E [c](0]] B (c)
M
i=1
1
M (pr + (M (M-))) M [P,(1) + (M- 1)p]
M
Σ
(1))))p()) + (M - 1) ppp0p +M - (1p)())))
M
M 1
((.. py) py)) + (M - 1)2
M Pz. Po)
(p p?))
M
M
where with a slight abuse of notation, we use (pz, p2) to denote 1 (1) and we use (ph.p))
to denote P (t)
To calculate A2, we need to calculate (i) where i + j. We define x as follows:
1,
The a-th random walk from x ends at
x
00 otherwise
So we have ((c,())c,,()) E. ΣM D. = M En X[X: For all and
i * j. we have X = 0], since for single random walk, it cannot ends at and j the same time. For all a * b and i * j. have E|X; Pa (i)..)....) So
get (1), M(M - ()px( (1)p=()) (j). By the same augment, we get that for all i # j. (lc,(tcc,, = M (i), Therefore.
A2
1
Σ
Σ
B(c,(()c,,)) (lc00))
M
i= j=lj
n Σ
M4 Σ
M(M 1)p- M(M (1p,())
/=1,111
(M 1)2 m
n
(1()),,()) P.(Pps
M2
1=1,141
M-1)2
Pa (1)(() p.Ppp - Σ Ep(003(
M
1=1
(M - 1)² 2
Σ Pz (1) Σ pp(0)py() - -6p2. p3))
M2
17

---

Published as a conference paper at ICLR 2026
(M - 1)2 - M
( pp))
Put them together, we get
E|2,] = A1 + A2
1
11
(Pa:.Py) 2) + (P):P.))) + (M
(M-1) - 1)2
M2 (Pn. Pu) +
(P Pe)
M
M
(M - 1)?
((Po) pu)
(p))Pa))
M
1
--1
((Po: piy + (p.. + (M - 1)2
2 (Px: (po:Py) +
(Px. Pu)?
M
M
Therefore, we have
Var[Zo] B[2 (I(22))2
M- 1
((Pa: Py) + (P. Py)) + (M - 1)2
M Py) +
(Pa. Py!
-(p.. Py)
M
M²
M
1 -2
M Pp) +
(Pp.. Pg) + (p. py))
+
(px, Py)?
M
M2
S
M (Pr.Pu)) +
(1Dms Py)
(p Pn))
M
Σ
Pa (1) + M
Σ Pa (1(p) + Σ 10000))))
M
i=1
1
$ M
||eell
llPull + (l/p=l12 ||p + ||p 13 ||
M
1
1
1pzl22
||llla + (llpal12
11p,122 Ip_ 12 ||pyl12)
M2
M
where the second-to-last inequality uses the Kauchy-Schwarr inequality and the last follows from Fact C.I
Building on Lemma E.I we now consider the estimator obtained by averaging B R/M independent copies of Za- The following lemma shows that Z remains an unbiased estimator with variance reduced by factor of R/M.
Lemma E.2. Let G (V, E) be a graph. Let R,t, M be integers, where < M < Let y E V be two vertices. Let M be the random walk transition matrix of G. Let Z be the outpur of ESTRWDOT(G, R, t, M, x, y) (Alg. 7). Then, we have
E| (M'1,, M'11),
VarlZ] < R M |M'all - ||M', (IIM'a I|M' [MML113 || la)
113
Proof. According to Alg.
we know that 1
13 - Zz where D [[Z,] (M',, M' and
R. M. Therefore, us-
ing Lemma E.
we have E
1
Var 7
Var %
B
b=1
Var 2b,
B
M
Var [2b
R
18

---

Published as a conference paper at ICLR 2026
M M 1' 1,M22, + M (IIM'1.ll2 , 1| 11
R M
M | + (I || |
||
= R
Lemma 3.1 shows that, with suitable input parameters, ESTRWDOT(G, R, M, x. y) (Alg. approximates the dot product of the random walk distributions from any two vertices E V within an error of der-
Lemma E.3 (Restatement of Lemma 3.1 Let k > be integer and e, E (0,1). Ler (V, E)
be d-regular and (k, cllusterrb graph. Let M be the random walk transition matrix of
G. Let Z be the output of ESTRWDoT(G, R,t, M, x, y) (Alg. 7. Let der > Let > =1 be
20 and any I, E if mk -1440/022 0 M
a large enough constant. For any 2
and
1 S M S 10(0 <0(
12-000000/
k then with probability least 0.99, we have
Z (M'1 M' S Oer.
Moreover, ESTRWDOT(G: R, M, x, y) runs in (RR) time and uses O(M 1o bits of space. Remark E.1. The success probability of Lemma 3.1 can be boosted up to n 100 using median trick, i.e., by taking the median O(log n.) independent runs.
To prove Lemma 3.1 we need the following lemma in Gluch et al. 2021
Lemma E.4 (Lemma 22 in Gluch et al. (202T)). Let 2 2 be an integer and &,, E (0, 1). Let G (V, E) be d-regular and (k, yp, E) cluusterrable graph. Let M be the random walk transition matrix of For any 20 log and any
we have
| < O(k -1/2+(200/42))
Now we are ready to prove Lemma 3.1
Proof of Lemma 3.1
Correctness. By Lemma E.2 and Lemma E.4 we can get that
1 1 S
Var Var[Z]]
M' lll2 1|M' 1,12 + (II' 1 2ll2 |MML 2112 + || 1M111 -IIMI v1ll))
R
M
O(k2 -+000//4)
1
O(k3........ -n...nn33/60/// 3/2+000//0/) 0(630n50//2000/633)
R
M
Using Chebyshev's inequality, have
Pr|]z (M'1,, M "'1,, Genl = Pr|l - |[ 2 dem]
Var [Z]
1
O(k2 n 1+40e/02
+ +O -33/2+000/00)
0
R
M
1
1:2 -1+0Ue//"
02
R
M
1
100'
19

---

Published as a conference paper at ICLR 2026
where the second-to-last incquality holds by M < 0 22/22-20//22 our choice of
And the last inequality holds by
c. n -+400//00
R
02 M
where is large enough constant that cancels the constant hidden in O 1 1 11-01040 402/c2
Runtime and space. Algorithm ESTRWDOT(C, R, 1, M, y) (Alg. performs B af bathches (i.e., B = R iterations of the for-loop). each batch, runs M random walks of length t, which requires (MM)) time and O(M) words of space to store the ((M) endpoints of the walks. Computing the dot product of two probability distributions takes O(M) ) time, since each distribution has most M nonzero entries. Therefore, the runtime and space per batch are O(Mt+ M) (Mt) time and (M) words, respectively. Moreover, the space used within each batch can be reused across batches, Consequently, the overall runtime and space complexity of ESTRWDOT(C.. R, I, M, y) (Alg- 1 are B ((M)) Ht O(Mt) O (Rt)) and ((M) words (i.e., O(M log n) bits of space, since each endpoint can be stored in log n bits), respectively.
M
states that, under appropriate input parameters, the output G of our algorithm EST- COLLIPROB (G, R, M, Is) (Alg. 2 is close to (M' () in spectral norm, where (M'S) is the Gram matrix of the random walk distributions from vertices in the sam- ple set.
Lemma E.5
(M'S)* (M'S)
Lemma E.5. Let k 2 2 be an integer and p, E (0, 1). Let = (V. E) be a d-regular and (ke e) clusterable graph. Let M be the random walk transition matrix of G. Let Lg (.,,..., S,3 be a multiset of s indices chosen from {l,..., n). Let S E Raxx be the matrix whose i-th column equals Ls Let G E gaxs be the output of ESTCOLLIPROB (G, (G,Rt,, 1s) (Alg. D.. Let aer
Let c > be a large enough constant. For any 2 20logn R Z
e -1
and 1 S M S
a
O n 2/2-200/00) then with probability at least n - 100 we have b
|| - (M'') S aem-
Moreover. ESTCOLLIPROB (G, R, t, M,)) runs in O s²) time and uses (M -log n2)²)
bits of space.
Proof. Correctness. Note that in line 5 of Alg. (Alg.
we get Gi( BSSTRWOOT R, M, 81, 8j)
Since t > 20 logn, R 2 c
22 and 1 I M < o
1/2-200/02
then
M
k
by Lemma 3.1 with probability at least 0.99, for all i, E [s), we have
(i. - 1M',., M' = (i,)) (M'1, (M'
T(M') s,)1
Jen-
Note that in line 6 of Alg. 2 define G as matrix obtained by taking the entrywises median of Gi's over (log n)) runs. Thus with probability at least 1 n -100 (see Remark E. for all j E [s]. we have
((( - 1M'...) S dem.
which implies
|| - (M'') Ger-
Moreover, have
l|g -
|| (M''S' s. den-
Runtime and space. In Alg. Alg. ((Rt) and ((M log n) bits, respectively, the runtime and space of Alg. 2 are O Rt log and O(M log² n s2) bits, respectively.
1 is called log n 2² times. Since the runtime and space of Alg.
20

---

Published as a conference paper at ICLR 2026
Recall that fy)- Lemma E.6 states that under appropriate parameters, Alg.
(M'S)"
to estimate
3 outputs matrix
v = WWA Me
l PM [M] The [k] proof of Lemma E.6 is analogous that of Lemma 24 in Gluch al. (2021) Nevertheless, for completeness, we provide a concise proof here.
which, with high probability, is spectrally close to W
Lemma E.6. Let k 2 2 be an integer and p, E (0, Let G (V, E) be a d-regular and (k, y, e) clusterable graph. Let M be the random walk transition matrix of G. Let Is {81 ( 8a) be a multiset of s indices chosen independently and uniformly at random form V = {1...., nR. Let S E 1=xx be the matrix whose i-th column equals a1. Let g R be the output of
ESTCOLLIPROB (G, R, t, M, 1s) (Alg. 2 Let / M'S = ÜEWT be an SVD of V M'S where Ú _xxn Σ pax", W _2*xn Let 2. G WEWT be an eigendecomposition of = G.
Let 1 n < <1 Let C1 > and C2 > be two large enough constants. For any / 2
20 if
S N... 2 61 n2 22000/4" log n k., R cz 10000/002 and 1 S 00
1/22 200/0²
then k
M.
with probability at least 1 2- matrices E and 5-4 exist and we have [M
W WIn
WTlle <.
[
Equipped with Lemma E.5 to prove Lemma E.6 we also need the following lemmas.
Lemma E.7 (Lemma 18 Gluch et al. 2021 ). Let A, A E R be symmetric matrices with
eigendecomposition A YrYT and A YTVT. Let the eigenvalues of be 2 71 2 ...
In 2 O. Suppose that A All2 S
7t and M++1 < 7. Then we have
100
16| Alla + 478+1
Vr [M]
PI
[K]
Lemma E.8 (Lemma 28 in Gluch et al. (022)). Let k 2 2 be an integer and (p, E (0, 1). Let G= GV.VE E) be d-regular and (k, 5, clusteraable graph. Let M be the random walk transition matrix of G. Let Is = {81,.... 8s) be multiset of indices chosen independently and uniformly at random form V
..). Let nx be the matrix whose i-th column equals sx Let e. >
be a large enough constant. For any 2
20 n if & S 10 4"
and 2 c. nn 210e/pp
-logn K2, then
with probability at least 1 -100 we have
Uk (7 (M'S (M')) Uk (7 (M' (M'S)) Uk+1 (= (M'S) () S
80./22
Lemma E.9 (Weyl's Inequality). Let A, B E 1R be symmetric matrices. Let oi,..., On and Bn B1....,
be the eigenvalues of A and B respectively. Then for any i [ni], have
los 3. S ||A Bll2-
Now we are ready to prove Lemma E.6
S.n 31000///
Proof of Lemma E.6 Let C3 > 1 be a large enough constant and let dur
Let be
constant from Lemma E.5 By the assumption of the lemma for large enough constant 02 > 1, have
C2 R.6
2/700//22
c-k2 1-kk--1+40///
R
M g2
02
Thus we can apply Lemma E.5 Hence, with probability at least 1 - n 100 we have
|| - (M' (M'' 5) S s. Ten-
Let Ā 3 (M'S) W and À = G. Thus, we have A
( (M' () WEAT and 1 ( -- WT To use Lemma E.7
21

---

Published as a conference paper at ICLR 2026
have bound 1 1 (#) (M - Using the triangle inequality and sub-multipliaatiiity of spectral norm and the above || (M' S der bound, we can get that
(((M''))'''') 9 S (s Ten)² (e)) + Jen SM'
Note that [[ < [(MM')) ((M
v VEi Ej= (M
by Cauchy Schwarz inequality and Lemma E.4 we can get that (M'S)((M' (M'S) S)ll2 S O(s .
-1+-00/444) Put them together and by the choice of Cem 8.
1 2000/02
we have that
nn-3200/pp" 33000/p2
8.n
1 A
50
Moreover, let ej be the constant from Lemma E.8 since 2 c1 . 240 with probability at least n 1n-1000 we have
-log n. k., by Lemma E.8
n-8U///0 2
uk A2 = Uk ((MSTT)))
160e/$²
and
Uk+1 (x²) uk+1 (0 (MT')
= -18 (n-
By Weyl's inequality, we have that v/ (A²) 2 2n -
1100//02 -0( (0:E:n -320//4
O, $-2 exists. Moreover, since A _ are symmetric matrices, 11 - 1-222222 -
(A
and
100
(A²) < 4 by Lemma E.7 we have that
16|1
A 40x+1 (A2)
W و. WT
W W
2% (A2)2
nn 320
+ 4m
3200/
16
+ 64n
C3
1
5
Moreover, both Lemma E.5 and Lemma E.8 fail with probability at most 100 can get that the above inequality holds with probability at least 2n 100
by union bound, we
The following lemma shows that the output value (fr, of Alg. is close to ( [ W WAS -- WT (M' The proof follows from the proof of Lemma 29 in Gluch et al. (202T). Nevertheless, for completeness, we provide concise proof here.
[R] [k]
Lemma E.10. Let k > 2 be an integer and v, E (0, Lei G = (V, E) be d-regular and (k, q, cl-cstttee graph. Let M be the random walk transition matrix of G. Let Is = {S1...., Sz) be multiset of indices chosen independently and uniformly at random form V {1. {1...., n)..
Let S IRaxs be the matrix whose i-th column equals 1.;-- Let V M = UEWI an
SVD of V -M'S where Ü E guxn E E Inxn W E gaxn, Let + < and 5
(21/2-200/62) ) Let 2 20lonn
Minic < 0 k
Let c > 1 be a large enough constant. Let 2
22

---

Published as a conference paper at ICLR 2026
n 240e/4
-logn. k... Let W denote the matrix constructed by INITORACLE (G, &, Mmit) (Alg.
3
Let 2 V. Let (f fulapx E R. denote the value returned by QUERYDOT (G, 2, U.C, V, Mquery)
then with probability at (Alg. 41 1f & I 10c. Alg. succeeds and 1 S Mquery S SO 2//2/200/2²
k
least
1 - 5n 100 matrix
exists and we have
(fa: fudapx (M' (M (
F.-WiN Win SA (M'S) S
Proof. Note that in line of Alg. 4 (fa: Ful is defined a Vay, where in line 8 of Alg. 3 E Rx is defined to be
Win [[] WT and ar Bty E R are vectors obtained by taking entriwise median over all Olog n)) runs (see lines 3 ~ 7 of Alg. 4
For any vertex a E V, we use Pr to denote Pa M' We then define
a₂ P (M' S). A= n
Win
5- WTT
WTk [k) ag = (M'S)" Ps.
e, a az.
E= A,
Cy axy ag.
Then by triangle inequality, have
Th - W(k) S af Va,, - p. (M's)
5--Wi [4]
S) P.
(a, + (A+ (a c.y) a. Aayl
||2/|22|| 2|22 e + ||a ||2 Fb lepll
+ | |a>|l2| E a, + | || | + |alll
In the following, we bound || a. |a,||2, ||a F 2, ||
| and ||e.||2-
Let d' > be a constant and let 6' = c' c' /u
Thus for large enough constant c, we have
2 C1 2100/0² llog n 1d and Pinit = O(" +0200/
14 5
27000//1 as in line 2 of Alg.
Mar
Mun
hence, by Lemma E.6 applied with g' we have that with probability at least 2n 1300, 100 5-2 and
[K]
exist and we have
E = || I
n
WT
Win S W <
-''=
f.n
(I)
e¹ k4 n p2
Moreover, according to the proof of Lemma 29 in Gluch et al. 2022 least 1 n 100
we have that, with probability
4 n 1600////
|AAl|2 5
(2)
And with probability 1, we have
||ar||2 50(V8. 10(v..>> 122 n -1440=/0/)
(3)
and
layl2 S0(V8 Cat///sk..-----0000 -1120///
Now we need to bound e. and ey. Recall that e, = x pe (M'S), where E R is obtained by taking entrywise median over all ax's ss. Note that in line of Alg. ( is the output of
ESTRWDOT (G, Rquery t, Mquay, x, s.) (Alg. D. Let c3 be constant infront of R in Lemma 3.1
Let Jer c' 4200 Thus by our choice of Rquerr- O n2 Maner
14400//02
in line 2 of Alg.
the prerequisites of Lemma 3.1 are satisfied:
(
(n²' 4/000///p² 66
C3 22 40epppp
Rquery θ
M Mquery
-2
22 M Mqnery
23

---

Published as a conference paper at ICLR 2026
Thus apply Lemma 3.1 Hence, for any S $ with probability at least 0.99, we have
(1) P Ps. I der-
Since we are running (log n) rounds to compute æ and Or obtained by taking entrywise median, we can get that with probability at least 1 n- 10010 for all E Is (see Remark E.1b. we have
[a=(2) - p. Ps Fer-
Therefore, with probability least
-n-100 we can get
Vs.E
| = ||a - ph (M' S V8. Jen d' 12 n 222000e/p
(5)
Using the same analysis, with probability at least 1 - n -1000 100
get that
V E | 112 |aa (M' Pulla S v der d 122 n 2202000//0
(6)
Putting
2 3
(
together and for large enough n, we can get
a T Vay P [M's) S)
( Wh To Wh)
(M's)" Pv
$ || elllz + || A22 / +
| 112
+ ||a 112121//122//o.111 + ||a.||||| E12 |,1l2 |1 A 2
$
0 c'.'
5
The last inequality holds by setting be a large enough constant to cancel the hidden constant of
0 5
Using union bound, if Alg.
3
succeeds, then the above inequality holds with probability at least
1 2n 100
n 100
2n
100
5n 100
Having Lemma 3.1 and Lemma E.10 to prove Theorem 3.2 we also need the following lemma.
(2211). Let k 2 2 be an integer and 4, E (0, 1). Let Lemma E.11 (Lemmaa 19 in Gluch et al.
G -V E) be d-regular and (k, yp e) (. -llusterrbbee graph. Let M be the random walk transition matrix of G. Let Is {si,.... {.} be a multiset of indices chosen independently and uniformly at random form V = (1...., n}. Let S E Raxs be the matrix whose i-th column equals 1 Let
/ M'S = UEWT be SVD of / M'S where U E Ruxn E E RR W E Bax., Let
n < E <1 1 and 2 n0 If
Let c. > be a large enough constant. Let s 2 c-n 180e .log n 18 1E/
s²
c S T then with probability at least 1 - n n1000 matrix STT exists and we have -
1 (MM (=
- (M1
W11 WT WTT) (1)
(M'S)
< E
Now we are ready to prove Theorem 3.2
Correctness. Equipped with Lemma E.10 based on the correctness proof of Theorem in Gluch et al. 2021). we can directly obtain the correctness.
Poof of Theorem 3.2
Note that in line 3 of Alg. 3 we set On 480e/p² -log n n k* /g²), and in line of Alg, 3 we sample
indices independently and uniformly random form V {l,.... .....,,, n. to get Is (si.......
Recall that M is the random walk transition matrix of G. Let S E maxx be the matrix whose i-th column is s..- Let / M'S USWT be an SVD of V M' where U E Ruxn E
Raxn W E R
24

---

Published as a conference paper at ICLR 2026
Recall that for any vertex E V, define fx Unj (see Definition 2.1 thus we have (z).f)) = fo fu = (U L [8] ly = U (T) un- For convenience, let us denote B =
(M'L))"(M')) (a ( 1 Se (Tk)
(M By trangle inequality, we have
1(fa, Folaps (fa: fy) = 1Kfz Fytapx
B + B (fa; fz)l
- 1(fz, Fulapx
B + B (fr:
= Kfzz Jujapx
B
+ B
(1 U(h 1))
Let 5¹ 5. Let c' be constant in front of form Lemma E.10 Since (n0 log
ka/ 1$2) 2 d' 200ee/44 log n k4, then by Lemma E.10 with probability at least 5n 5n- 100 we have 1ffrr (f) apx B
2m
Let с be constant in front of s form Lemma E.11 Since =
484000//4 log k*/²2) >
48000//0" llognn Ka/e /E/ and 2 105 then by Lemma E.11
with probability at least n 100
have B 2 [M] [1) wl
2m
Therefore, by union bound, with probability at least 5n 100 (f), (fz, fu)l S 2n
100 = 1 - 6n -100 we have n
2rc
Runtime and space of INITORACLE. A Algorithm INITORACLE(G, k E, Maa) (Alg. calls EST- COLLIPROB(G) G, Rinit i, Minit 1s) (Alg. 2 to get & (see line 5 of Alg. 3 According to Lemma E.5 ESTCOLLIPROB GG Rini,h, L, Mini, Is) runs in O(Pimi L- log n- time and uses ((Miir log" n- bits of space. Then line of INITORACLE, and it uses s² log bits of space to store & E Raxn Thus overall INITORACLE runs in O t logn- s² + 88) time and uses O log n 52 +2 -lggn bits of space. By the choice of & = 20 Rinit = O(T 1 11200//
computes the SVD of matrix G in 5 time
and s == O(n 280--/0/ logn k*/E²) as in INITORACLE, we get that INITORACLE runs in Time (2) nz +0(e/p))) 1 -log n d2 time
8²
Mik
Ma
and uses Smn ((1))1))) (le//")) Miit log" n bits of space.
Runtime and space of QUERYDOT. In QUERYDOT (Alg. 4. in lines 3 ~ 6, it calls ESTRW- DOT(G, Rquery. f,, Mquery F, (Alg. D for Ollogn n- s) times. According to Lemma 3.1 ESTRW- DoT(G, Rquery, t, Mquery, I, 8;) runs (Rquery t) time and uses (MMquery log n) bits of space. Moreover, in line 9 of QUERY DOT, it returns (Sa, fu)apx
a Var, which can be computed in compute a² v in s² time and then compute ad, in s² time. Thus overall QUERY DoT runs in Olog
O(s²) time, since
Rquery t + s2) time and Olog? n s Mquary) bits of space. Rquery- = O 10000/00
By the choice of in QUERYDOT, we get that QUERYDOT runs in Tauay= = ( k (()) +00(c/0²) Mass log n
20 log rd
1 and s = 480-00/// logg 1. /E?) as
Many
time and uses Squery = ( (()) (lElv)) Mquery log" bits of space.
F PROOF OF ITEM IN THEOREM 3.1
In this section, we first present an algorithm for computing the spectral dot product in a subspace, which will serve building block for the sublinear spectral clustering oracle that relies log(k) conductance gap. Next, we introduce the sublinear spectral clustering oracle, originally proposed in Gluch et al. (2021), corresponding Item in Theorem 3.1 Finally, we provide the proof of Item ]
in Theorem 3.1
F.1
DOT PRODUCT ORACLE ON SUBSPACE
Note that the clustering oracle in Gluch et al. (2021) relies on cluster centers:
25

---

Published as a conference paper at ICLR 2026
Definition F.1 (Cluster center). For a vertex set C V. the cluster center of C' is defined to be
Ea. FEC
PC = |01
They proved that if x: E C2 then fæ is close to JC;, which means (fa. 2 | where c is a constant. Therefore, the key idea behind the clustering oracle in Gluch et al. (202)) subset of vertices and enumerate possible k-partition in order obtain good approximation Ti..... Fig to the true cluster centers pl,.... 14, (see lines 6 ~ 11 of Alg. 7 When answering an arbitrary W HIcHCLLUSTER (G, x) query, the oracle assigns the to fz while other cluster centers are not close to fa (see line 5 of Alg. IT)
1) is to sample
the cluster whose center is close
In fact, their clustering algorithm uses hyperplane partitioning, which requires computing dot products in the subspace (i.e., (fz: IT))). Therefore, we first present the algorithm that computes the dot products in the subspace based on our improved version. We highlight that this (i.e., Alg. 6 is not our contribution.
Algorithm DOrPHOOUCCOOAACCHOOSSSSISAAAAAA
V, M, B Bi.... B,)
Let X 12 be E ER, 28,,h by R"
Let 5 = O n -800//2 00
for i.j [r] do
L X(i,)) == B.ll EnEB, EIJEB, 24 2,,,',, M)
for E [r] do
1. Σx.e,, QUERYDOT(G, 2, V) (t) [..
(i)
[A,] EZEB, QUERYDOT(G, V.C. V, M)
return (fz. (pp QUERYDOT V. M) h X-
In the following, we will give some informal theorem and corollaries about Alg. Note that the only modification
make to Alg. i is to replace SPECTRALDOTPRODUC with improved version. Since our dot product oracle provides the same correctness guarantees as the original one, the correctness of the theorem and corollaries concerning Alg. 6 follows immediately from the proof of Theorem in Gluch et al. (2021). Therefore, we focus on analyzing the time and space complexities.
Theorem F.1 (Informal). Let l 2 be an integer, i, # < < and áa be smaller than a positive absolute constant. Let G (V, E) be d-regular and (k, (..)..)))))) (.c))-cuutterbble graph with C1....,C,
Let E [K]. Let BI...., B, denote multisets of vertices. Let b max4e[1] [Ba). Let P4 1 Bil
EOEB, B, fz. Ler II is defined as orthogonal projection onto the span (1P1.... ,r pr, 1 Then
for all x, y E V. we have
(fa, N - (Sa. (fa, ff) S S. where (fz, Ty) is the output of Alg. 6
-Sa,
Alg. 6 runs in 62 (4))0) ++00(e/0"). + log" n + time,
Alg. uses b² (2.(()) (1)0 (le//")))))) ole/o M- log" bits of space.
Proof. In lines 3 ~ 4 of Alg. 6 compute X, Alg. Callss QUERY for r.. 22. times. In lines 5 ~ 7 of Alg. 6. to compute ha, h, Alg. G]calls QUERYDOT for r b k- times. To compute -1 it takes 3 < 3 time. Therefore, Alg. r in 62 Tquery + k- b-uauryy + 13 time and uses 12. Squery + k--b-qquery +²2 bits of space. Note that T query ( 001) (0(1)_n1+00 1+0(e/0²)) 37 log n +
and Squay ( 0(1) O(e/o") . M -loo n, where Og 80s/4² 122 k0). Therefore, get that Alg. 6 runs in b² ( 10) +00s//0?) M -log time and uses b². ( 0(1) 0le/42) log
bits of space.
Corollary F.1. There exists algorithm that
I returns a value (fz. M7) mpx such that (fz, M.0 (Sa, N7p)
<
26

---

Published as a conference paper at ICLR 2026
runs in 6 (2)00) (0(000))) MM log" n. ~ time. uses b² (2))()) 0le//) M log" bits of space.
Proof. One can compute (J M7x apx | EyeB DOTPROOCCTORACIIONSSSSSIIICCC ys
V, M, .I..... B,) (Alg. 60. Therefore, the algorithm that computes (fz. lTp) calls Alg. times, which ends the proof.
Corollary F.2. There exists an algorithm that
returns a value ||[iiillaps such that || || s &
runs in b (2)(0) (er0)nn++0000 nl+0(e/v") log" n s time,
3 uses 15 (2)00) ol6// M log n bits of space.
Proof. One compute ||للا upp (Пa)* ň ii / Ii B
(ū. lip)
EnEB (fa, apx) Therefore, the algorithm that computes || calls the algorithm in Corollary E.I b times, which ends the proof.
F.2 SUBLINER SPECTRAL CLUSTERING ORACLE
Now present the sublinear spectral clustering oracle with log(k) gap between inner and outer conductance, originally proposed in Gluch et al. (202T), and adapt it by incorporating our dot product oracle, which operates with very little memory.
Algorithm 7 finds some cluster centers that reflects the clustering structure of the input graph.
Algorithm 7: FINDEENTERSG)
INTTORACLEGG,K,100 10-6 v., M)
= 40 log l: log(1 /n) 82 = 4 (0 1o loog(1
for t E (og do
Random samples of vertices of of size 0( x* log
for (P1, Ps. ... P&) EPARTITION (S) do
for i = to do
7. = P. Ee
Cr,C) COMPUTRRORDDEEDDARTTTOOC (fi,...,,Tá)) 82, M)
if TRUE then
return C
Algorithm 8: COMPUTTORRDSEEPPRRTIINNGGG (fi,..., 1Kk) 82, M)
S = [ū1,. .......,,l .
for i 1 to llog do
T. : 0
for f E do do
=O (T.,...TTT1))55 llg k) then
é < 0
T T7:771 fm
it then
10
return (TRUE, (TI....,T:) T:))
return (FALSE, L)
27

---

Published as a conference paper at ICLR 2026
Algorithm 9: OUTERCOONUCCAANEEG, (T,..... To), S,,,,1111 81, 82, M)
cnt == 0
for t to 31 do
~UUNIFOM(11 n if ISINSIDE(2; .. then cnt = cnt +
if min /pl/22 then
L return
e = 0,a ==
for (
82 do
10
Y ~ UNIFORM w E N (u))
11
if ISINSIDE( R. (T),
S, then
13
a = a a+++ if IT-ISNNSIDEY,PR (T1, S, then c
15
return
Algorithm 10: ISINSIDE(r, fi, (T....., To), M)
for i b do
Let 1l be the projection onto the span (U)+(T))+
Let S; - (U}z,T)) US
for f4 E T3 do
i E Capx
0.93. UprEs.((A.)
Che C17 0.93 then
return FALSE
Let IT be the projection onto the span (U)
if x E Caps TTj.0.99 UpresMaa Caps TTjr,..93 then
return TRUE
return FALSE
Algorithm [1 corresponds the query phase of the clustering oracle where it is used to assign vertices to clusters based on cluster centers.
Algorithm 11: IYYERPLLNIIAATTTTOONNNN,,, (Ti,..., To), M)
for i b do
Let II be the projection onto the span (Uj+(T))+
Let S, = (L)z/T))
for çi T: do
apx if x E 112.0.93 UprEMM) CHe ..a.. 0.93 then return f
F.3 DEFERRED PROOF
Theorem F22 (Restate of Item Theorem 3.1 Let k 2 be an integer, P.E (0. 1) and
h (k, (2) and hylk, E) be three functions. Let & h (k, Φ). Let G = (V,E) be
d-regular and (ks, s,, cllusteeraa gruph with Ci...., Cr. Let ne/// S SMO O (1/32000/12)
be trade-off parameter, where e large enough constant. There exists sublinear spectral clustering oracle that:
constructs a data structure D using O (ba(k) ole M) bits of space.
28

---

Published as a conference paper at ICLR 2026
answers any WHICHCLUSTER query using D in Og (h2(k)) ( =0(00//))) *t) time, has O (ha(k, yp v,E)) [C:] misclassification error for each [k].
where we use Oip to suppress dependence on ip and Ô to hide all poly(log n.) factors and:
if (k: = &² lo then l22k,, 8) - (4) and ha (2,5) = So log k.
Proof. Space and runtime. In the preprocessing phase, as line 1 of FINDCENTERS (Alg. it invokes INITORACLE E, M) one time to get matrix V, which takes Sin bits of space according
to Theorem 3.2 Then it samples
x² k log k vertices and tests all the possible k-partitions of the
sample set. For each partition, it invokes Alg. one time. Each run of Alg. g invokes Alg.
9 k: log
times. Each run of Alg. invokes Alg. 10
(81 + 82) times. Each run of Alg. 10 computes
ups
0.93
about k0(1)) times, where Capx 117,0.93
x V, m
(ff.. 2 0.93). According to Corollary
F. and
Corollary F22 computing (f2 takes s² ((2))(()) .n ((/44") M Mqqery -log n bits of space, where
||
we set { = 10-6, VE Therefore, Alg. uses Sini + k log k- (81 82) st ((t((te)) (ee)
Mquery" log" n bits of space. By setting $1 == - 1 log h log (1/1)) 82 = = ( 5 log((1)))
77 Ollg n.) and Mquarr M, get that Alg. 7 uses (Bee ( n o(=/'") M (oly(log bits of space to get a matrix V and a collection of vertex sets C' that represents the cluster centers.
In the query phase, HYPERPLANEPARTTIOONN
(Alg. computes Tip.0.93 about k0(1) times.
1177.0.93 = for E V, (f...1i) 2 0.93). According to Corollary F.1 and Corollary R.2 where Capx
computing (f... takes st (Ee)om ((e/0") M log n bits of space and s4 ( ||
1+0(t/pp) log" n + time, where we set & 10-6 y that Alg. 11 takes (Le)orl). ((e/o")) M poly(logn) n)
By setting = g k4 lool k. we get
bits of space and (22) +++0(=/=")
M poly(log n) time.
Thus, the clustering oracle constructs a data structure D (including matrix V cluster centers C and other information used by the query phase) using ( ( (01) (((//))) M poly(log n) bits of space.
Using D, any WHICHCLUSTER query can be answered by Alg. 11 in ke ( ++0(pppp") M poly(log n) time.
Correctness. We highlight that the sublinear spectral clustering oracle is not our contribution. Note that the only modification we make to the clustering oracle is replace the dot product oracle used in the original work (Gluch et al. 2021) with our improved oracle. Since the correctness guarantees (i.e., conductance gap and misclassification error) of the clustering oracle rely on the properties of the dot product oracle, and our dot product oracle satisfies the same correctness guarantees with the previous one, the correctness of the overall clustering oracle follows directly from the correctness of the clustering oracle in Gluch et al. (021
G SUBLINEAR CLUSTERING ORACLE RELATED TO ITEM 2 IN THEOREM 3.
In this section, we present the sublincar spectral clustering oracle with a poly gap between inner and outer conductance, originally proposed in Shen & Peng 2023). and adapt it by incorporating our dot product oracle, which operates with very little memory.
Algorithm 12 first initializes dot product oracle to get matrix V (see line 5). It then leverages our dot product oracle to estimate (fz. fy) for all pairs of vertices æ, y in the sample set S, which are subsequently used to construct similarity graph H (see lines 6 9).
29

---

Published as a conference paper at ICLR 2026
Algorithm 12: CONSTRUCTORACIIGG.........
Let 5 TO00 and let 10-k log
Let 0 = 0.96(1
Av2 )
L 9 (5)
Sample set S of vertices independently and uniformly at random from V Generate similarity graph H (5,0)
Let v/ INITORACLE(G, K,
for any u do
Let J. if (fu. apx 2 0 then
QUERYDOT(G, u, M, M)
L Add an edge (u, v) to the similarity graph
10 H has exactly & connected components then Label the connected components with 1,2, k (we write them as , with if S
12
Label
Return H and the vertex labeling
else
15
return fail
Algorithm 13: SEARCHINDEX(H, é,
for any vertex ti E do
L Let (fus fa) QUERYDOT(G, u, E, V, M)
if' there exists a unique index 1 S S. le such that (f fa) 2 1 for all u E St then return index
else
return outlier
Algorithm 14 corresponds the query phase of the sublinear spectral clustering oracle, where answers any WHICHCLUSTER query using matrix V and similarity graph H.
Algorithm 14: WHICHCLUSTER
preprocessing phase fails then return fail
SEARCHINDEX(EF H, x. M) return outlier then return random indexe [k]]
else
return SFARCHINDEEX
H PROOF OF THEOREM 1.2
Theorem H.1 (Restate Theorem 1.2 For any trade-off parameter < M < O(VR), there exists
an algorithm (Alg. 5 that, with probability at least 2n. -100 solves the 1-cluster vs. 2-cluster problem. Moreover, the algorithm:
uses Ö(M) bits of space,
runs in Ö n N
time.
To prove Theorem 1.2
need the following lemmas.
Lemma H.1 (Cheeger's inequality). In holds for any graph that
A < ((G S V2x2-
2
30

---

Published as a conference paper at ICLR 2026
Lemma H.2 bounds the lz-norm of the t-step random walk distribution starting from any vertex in a d-regular graph, distinguishing between the case where the graph is a single e-expander and the case where it consists of two disjoint y-expanders.
Lemma H.2 (Expander related version of Lemma E.4). Let 4 E (0, 1). Let G be a d-regular gruph. Let M be the random walk transition matrix of G. For any t 20 = and any V, x
1 if G is i--xppnderr of size n, then | S V 2
2 if G is the disjoint union of two identical y-expanders of size n/2, then [M' 212 1 V
Proof. Item 1 Let L be the normalized Laplacian matrix of G. Recall that we use 0 = \1 < S Xn S 2 denote the eigenvalues of and we use U1....y Un to denote the corresponding eigenvectors, where ui...., Un form an orthonormal basis of I2 and u1 (I) = vn for any r V.
Au 2 0, d 2 ..... 2 1- 2 Note that M = I - 2 Hence, the cigenvalues of M are given by 1 = 1 - 2 and the corresponding cigenvectors are still u1..... ..... Un For convenience, we relabel the eigenvalues of M as 1 ii (M)
4 (M) (1 Aa) 2 2 (M(M)
(1 -/) > 0.
Moreover, we can write that 1 Ex= U, Note that uj 1,11 Ei= auu u, = aj. Therefore. aj corresponds to u²,11 11, = (z). Now, we have
M'1, = M Σ
Σ MaM'u =
Σ ==1
as (vx(M)) u,
a3 =
1=1
Thus, we have
| (M'),) (M'1,) = Σ af (M))
= (M) 20
a (v) 2
i=2
x2
+ (12(M)) 21
$ n2
1=2
< + (v2(M)) (n 1).
Since G is e-expander, according to Cheeger's inequality (Lemma H.l Therefore, for any t 2 rd
we get that Ae 2 8² 2
1o
we have
2/ (2) = (1 1
A2 21
(1
2²²
10 logn
S
2
4
n 10
Combine above results together, get that
||M
10 (n - 1)
+ n
n
Item 2] We use C1 C2 to denote the two e-expanders in G. Since C and C2 are disconnected, the normalized Laplacian matrix L of G can be written in block-diagonal form as
Le,
L
where Lc, E R and Lc, x are the normalized Laplacian matrix of C1 and Cz. respectively. For Lc,, we use 0 x .... 202 < denote the eigenvalues of Lc, and
use uf ...., n/2 x to denote the corresponding cigenvectors, where uf: ...., ..... u C, n/2
31

---

Published as a conference paper at ICLR 2026
from an orthonormal basis of IR x and u (2) = V for any a E V. Therefore, the eigenvalues
of are given by 0 X1 I I An/ I 2, each of which has multiplicity two, where X 1, = >,3 For Ao we use 1 U2i E R" to denote the corresponding cigenvectors, where M2:-1 ((ug)) (T)T ............ 0)2 and u2 = (0, ..... 0, (u: ) Note that M = 2
I Hence, the
7 2 ... 2 An/2 2 O, each of which has multiplicity two, and the corresponding eigenvectors are still U1..... Un For convenience, we relabel the eigenvalues
eigenvalues of M are given by = 1- - 1
2
of M as 01 (M) 02 (M) (1 - ) 03 (M) e (M) (1 2
Un- (M)
Un (M) (1 An/2 2 0.
Similar to the proof of item 1, we get
| 112 (M'1)) (M'', = Σ
a (us (M))²
i=1
= + +02
o (v;(M))
1=3
$ + (vs(M))
Σ
of
n
i=3
2 + (vn(M)) 2 (n 2).
Since C1 and C2 both are g-expander, according to Cheeger's inequality (Lemma H.1 20 log we have
we get that
NC: 2 2 T. Therefore, for any
xp
(vs(M)) (1 A2
2 2
2r
20
(1
202
10 log
2
4
7
Combine above results together, get that
2
1 n2
1 n2
| 1
(n
2)
+
n
The following lemma shows that, under appropriate parameters, Alg. [ can estimate the dot product of the random walk distributions from any two vertices up to den, whether the graph is a single sp-expander consists of two disjoint sp-expanders.
Let E (0, Let G (V, E) be either a d-regular sp-expander with size n or the disjoint union of two identical d-regular ip- expander of size n/2. Let M be the random walk transition matrix of G. Let Z be the output of ESTRWDOT(GG R, t, M, x, y) (Alg. [). Let Oer > Let > be large enough constant. For am M
Lemma H.3 (Expander related version of Lemma 3.1
any L > 20 and any I, E V. if R Z
and 1 S M S //n then with probubility at
4*
least 0.99, we have
1 - (M'1, M' 1 S der-
Moreover, ESTRWDOT(G, R,t, M, x, y) runs in O(Rt) time and uses O log n) bits of space.
Proof. Runtime and space. See the proof of Lemma 3.1
Correctness.
By Lemma E.2land and Lemma H.2 can get that
1 1 S
Var [
M I
,ll + (II'I
12l2
|MM1,
1,13 + ||M' 1 || v112))
R
M
32

---

Published as a conference paper at ICLR 2026
1 /0(n-1) = R M
+ +O -0())1/))
Using Chebyshev's inequality, we have
Pr|1Z - (M'1.. M' 2 Gen)
Pr[1Z - -E|Z]| > dem
VarlZ
0
1
[0(nn)
+ 0( 0((-311))
en
R
M
1
nn-
M 0 (n222)
0
2
R
M
100
The last inequality holds by our choice of R as follows, where e is large enough constant that cancels the constant hidden in O
n
R N 0 a M
Lemma H.4 asserts that, under suitable parameters, the output 9 ESTCOLLIPROB (Alg. approximates (M'S)" (M'S) in spectral norm, where the latter is the Gram matrix of the random walk distributions from sampled vertices, and this holds whether the graph a single --eexander or two disjoint e-expanders.
Lemma H.4 (Expander related version of Lemma E.5 Let E (0.1). Ler = (V, E) be either d reregal (p-expander with size or the disjoint union of two identical d-regular y-expanner of size n/2. Let M be the random walk transition matrix of G. Let Is [ --.......8 88) ) be multiset of indices chosen from (1,.... n). Let S E TR be the matrix whose i-th column equals 11 s. Let G x2xx be the output of ESTCOLLIPROB (G, R,t, M, Is) (Alg. 2 Let dar > 0. Let >> be
a large enough constant. For any 2
20 log
if R
o and M S (1212). then weith
4
probability 1-n -100, 100 have
|| - (M'S) S Gen-
Moreover. ESTCOLLIPROB (G, R, t, M, runs in O(Rt-oo Rtt-log n n.) time and uses ( logg n s2) bity of space.
Proof. Note that we have established Lemma H.3 which is an analogue of Lemma 3.1 for graph that
either a ip-expander of size the disjoint union of identical (e-expanders size n/2. Since
the proof of Lemma E.5 relies only on Lemma 3.1 the same augment immediately yields Lemma H.4
corresponding analogue of Lemma E.5
Lemma H.5 demonstrates that (M's) has clear spectral gap between the 1-cluster and 2-cluster cases.
Lemma H.5 (Expander related version of Lemma E.8 Let & E (0, Let G be a d-regular graph.
Let M be the random walk transition matrix of G. Let Is = ..1....,3 8,} be multiset of indices chosen independently and uniformly at random form = nI......... Let S E gaxx be the matrix
whose i-th column equals I For any >
loga with probability at least n -100 we have x²
if G is se-expander size and 2 then va (
~n-
33

---

Published as a conference paper at ICLR 2026
2 if G is the disjoint union of two identical (-expanderss of size n/2 and log where
c <> is a large enough constant, then (2) (M)))) 2 0.99.
To prove Lemma H.5 we need the following lemma.
Lemma H.6 (Lemma 21 in Gluch et al. (2021). Let A E Raxa be a matrix. Let b = 10n"t"'ogn, 40n²t² logn, Let Is {s1....,8y 8,}
maxte(1 (I....)) (((A)))AA)))ll Ler O < Let 8 2 be multiset of indices chosen independently and uniformly at random form V {1, (I,...,() m). Let S E TRaxs be the matrix whose i-th column equals s. Then we have
&
12 Pr -
(AS)
2 10-
Proof of Lemma H.. Item The proof follows directly from the proof of item 2 of Lemma 28 in
Gluch et (2021).
Let A = (M') = 2 we get (2) = 22(M) Since G is the disjoint union of two identical ye-xxpanders, G has two connected components. Therefore, the normalized Laplacian matrix L of G has two smallest eigenvalues equal to 0. Consequently, since M = 2
Item 2.
L the two
largest eigenvalues of M are - 1. Thus, (2) 1.
Let Ā _ (M' S) (M' By Item in Lemma H.2 we have b = [
S
|| 1 12 S n. Let { = 100 Therefore, for a large enough constant c > 1, we have = c log n 2
40n 62 log
Thus, according to Lemma H.6 we get that with probability at least - n 100
100 ]a
|| Ālle S
100
By Weyl's inequality (Lemma E.9 we get that v2(A) 2 22(A) ||A||| 2
0.99.
100
The proof of Lemma H.7 follows directly from the proof of Lemma 24 in Gluch et al. 2022 Nevertheless, for the sake of completeness, we provide a concise proof here.
Lemma H.7 (Expander related version of Lemma E.6). Let yp E (0, Ler G (V, F) be a d- regular graph. Let Is {s1...., } be a multiset of s indices chosen independently and uniformly at random V = (I.....,)) n). Let G E Rxx= be the output of ESTCOLLIPROB (G, R, t, M, 1s) (Alg.
2. Let c > be a large enough constant. For any t 2
Ing
if
Sy and 1 S M < 0 12). M
then with probability least 1 ... 100 1000
1 if G is a i--xxpandr of size n and 2 1, then ((-9) (12)))) < 0.001,
(12() if is the disjoint union of two identical e--expanders of size n/2 and 2 02 log where
02 > 1 a large enough constant, then U/ (=9))) = (v2(" 0.95.
Proof. Let M be the random walk transition matrix G. Let S R be the matrix whose i-th column equals 1s., Let v T M'S = UEWT be an SVD of V M'S where E Ruxn E E
Raxn W E R xx
Let n G = W T be an eigendccomposition of G.
Item
Let den 0.0001 Let c be the constant from Lemma have
H.4
By the assumption of the lemma,
R Ci n
10
C- 12-2
M
o2 22, M
Thus we can apply Lemma H.4 Hence, with probability at least - n 100 we have
||g - (MM'S)((M''' S)ll2
(M' S s Jen-
Let Ā 3 - (M'S) WE'WT and Ā .. G. Thus, we have Ae
( () WEAT and X2 (a 9) W.WWT. Moreover, we have
34

---

Published as a conference paper at ICLR 2026
|| - 1212 (2) (((M 12 Using the triangle inequality and sub-
multiplicativity of spectral norm and the above ||g (M' (M'))l S s den bound, we can get that
.. (M(')) - -9 - (s ren)² + oea (M
Note that [( < II(M'S - VELLE (MM',, ,,))) by Cauchy Schwarz. inequality and Item of Lemma H.2 we can get that (MM')))(M')) l2 S Put them together and by the choice of dur 0.0001 have that
|| A
n2
0000 ee + s.
2 11
n2 -n²o2 + 4no S 0.00005.
Oer
Moreover, since
1. by Item of Lemma H.5
with probability at least n n100 we have
U/ A² U2 (M' (M'))M
S (n 9)2
By Weyl's inequality, we have that
U2 (A*) S (2 + ||A2 -A2 S n 18 0.0005 S 0.001.
Item 2
By the same augment of the proof of Item I and Item 2 of Lemma H.2 we can get that (I 5) ( (M'S))l2 S s- 3. Thus, by the choice of der 0.0001 we have that
n
|| - A )=)²²
(s2 (8002 + Fer
3
n o 6n S 0.0007.
Morcover, since 2 C2 llg n, by Item of Lemma H.5 with probability at least 1 100
we have
A² 02 (1 (M') > (0.99)² > 0.98.
By Weyl's inequality, we have that
(A 2 v²( - || - -A 2 0.98 0.0007 > 0.95.
Now we are ready to prove Theorem
Proof of Theorem T.2 Correctness. By the promise in the theorem statement, the input d-regular graph G = (V, E) is guaranteed to be either l-expander the disjoint union of two identical sp-expanders, each of size n//2. We run algorithm DISTINGUISH M) (Alg. 5) to distinguish the above two cases. Note that the choices of I,, 8, and R made so that all the assumptions required by Lemma are satisfied. Therefore, by Lemma H.7 we get that in case (i) (when G is p-expander), with probability at least 1 2n
(e2( ()) 0.001 0.6; in case (ii), with probability at least 2n 100, (1)(")))² 0.95 0.6. Therefore, we get that, with probability at
least 100 algorithm DISTINGUISH correctly distinguishes which case holds.
Space and runtime. According to Lemma H.4 getting matrix & requires O(R t loo s2) time and O(M log² n s²) bits of space. Computing ( g)² requires 0(s3) time and O(s2 log n) bits of space. Therefore, the overall runtime and space complexity are O(R R f log s2 + $3) and (MM log" s² 2 log n) bits, respectively. By setting t we get that DISTINGUISH(G. .) runs in n M polly(oo n) za time and uses M poly n) bits of space.
20 log R O a and O n). p²
35

---

Published as a conference paper at ICLR 2026
1 PROOF OF THEOREM 1.3
Theorem I.1 (Restate of Theorem 1.3 Any algorithm that correctly solves the 1-cluster vs. 2-cluster
problem with error at most 1/3 using only random walk oracles must satisfy T S 2 M()), where T and S denote the time complexity and space complexity of the algorithm, respectively.
Before we start the proof of Theorem information theory.
1.3
we would first introduce some basic definitions in
1.1 BASIC DEFINITIONS
Definition I.1 (Entropy). Given a random variable X taking values in the set X' and distributed according to p: X' [0, 1), the entropy of X is defined
(XX)= =- Σ p(x) logp(z).
In the special case where X has only two possible outcoms, the entropy is given by
(2() = - pplog (1 log(1 pp).
The entropy of random variable quantifies the average level of uncertainty or information associated with the random variable. Note that for the special case of H2, have the following property: Lemma I.1.
H2 ( + +a)
1(21 - = (a²).
(2a) 21
2ln
Given the outcome of another random variable Y, we can also quantify this randomness using conditional entropy.
Definition 1.2 (Conditional entropy). Given random variables and taking values sets and ), respectively, with joint distribution p: X' y j0, 1]. the conditional entropy of X given Y is defined as
p(r,z) p(y)
HX IY) (XX,Y) HYY)
Σ p(z, v) log
xEX,EEy
Furthermore, the amount of information that is shared between two random variables is called mutual information.
Definition I.3 (Mutual Information). Given random variables X and Y taking values in A' and V respectively, the mutual information between X and Y is defined as
I(X;Y) H(X) H(X Y) H(Y) H(Y X).
Similarly, given random variable Z taking values in Z, the conditional mutual information of X and Y given defined as
1(;Y 2) = H(X Z) HX Y,
Our proof will also use the following key properties of mutual information.
Lemma L.2 (Data Processing Inequality). Given random variables X, Y and Z taking values in sets X.y and Z, respectively, such that X 1 Z Y. Then
2) < I(X;Y).
Lemma 1.3 (Chain Rule), Given random variables X, Y and Z taking values in sets X. y and Z, respectively, we have
(X;Y,2) T(X; T(X;Y (2)
36

---

Published as a conference paper at ICLR 2026
1.2 HARD INSTANCE
To prove Theorem T.3 we first consider the following Hard Instance, inspired by Diakonikolas et al. (2019) and commonly used in uniformity testing. Note that in construction, at each time the player is allowed to pick a W, E [nn]. The proof of Theorem 1.2 then follows from the proof of Theorem 23 in Diakonikolas et 2019).
Definition 1.4 (Hard Instance 1). Let X be uniformly random bit. Based on X, the adversary chooses the distribution on [2n] bins as follows:
X = 0: Pick p U2n- where U2n is the uniform distribution [2m].
= 1 We construct two sets as follows: Pair the bins as {1, 2). {3, 4).......... ... {2n - 1, 2n) Now on each pair {2i
24} pick random Y, (+1). If Y; 1. we put bin 2i to
set I and bin 2I to set 2: otherwise, we put bin 2i to set and bin 2i to set 2. Each time, the player picks W, e [2n]. If W, belongs The distribution is then
1, we have Ze 1: otherwise, Z, -1.
1 YiZ
1
YiZ
(p2-1.P2.)
2n
2n.
We have the space-time tradeoff of this instance to be
Theorem I.2. Let A be an algorithum that detects the Hard Instance I with error most 1/3. The algorithm can access the samples in single-pass streaming fashion using M bits of space and T samples. Furthermore, each step, the algorithm may choose which set sample by specifying W.. We then have T M = Q (n).
Remark I.1. In Theorem 1.2 we use M to denote the space complexity because S is already used in the proof to refer sampling-related quantity. For consistency with the rest of the paper, we will denote the space of the algorithm by S in subsequent discussions.
Proof of Theorem 1.2 In either case, we can think of the output of p as being pair (C, V), where C is an element of [n] is chosen uniformly, and V E {0, 1 is fair coin if X = 0 and has bias Yc Ze if =
Let $1...., be the observed samples from p. Let M, denote the bits stored in the memory after the algorithm sees the t-th sample st.
Since the algorithm A learns X with probability at least 2/3 after viewing T samples, we know that [X;; My) > 12(1). On the other hand, M, computed from (M,-1, 8t) without using any information about X. More formally, X 1. Mr (M,-1.8) st) and therefore we can use the data processing inequality (Lemmal) [.2] and chain rule (Lemma to get:
(X; S (I I ( Mc-1).
Since irrespective of X, uniform over the pairs of bins, we note that C is independent of even when conditioned on the memory M. Moreover, player's choice of W, is computed only from M,-1- Thus.
I 1(388
= 7 C.; = I M,-CC,) = I(;; [
Let 1 = M,-1 M,-.C.W,] and thus Pr = 0 M.- [,W, = ar-1-
We have that
37

---

Published as a conference paper at ICLR 2026
Pr V = 0 X = 0, C,,
2'
Pr [V; = 0 X = 1, 2, = 1+ E L,Y. Mo-1,
2
1+ E (,,Y.
M Wi]
Pr [V, = 0 M,-1, Ci]
= (1 - at-1) +
+
a1-1
2
2
1
0r
M Wi]
2
2
We can calculate
V4 M, C.W, H (V; | M,-ICW,, H (V:l M--CWW,)
-H2 (Pr [V, = 0 C,,
-(Pr [X= | MM,1I H2 (Pr [ = X M,, Wil)
+ PPr[X= = M.WI H2 (Pr [V 0 X 1,, Wi)))
1
a (Y, (2,V,, M-11, Wi)
(1
B[Z,yc, | MM-1, Wi]
-H2
+
- H2
2
2
2
2
(1
(1
at H2
2
11
E |Z,Y, MM-1,, Wil
0 11-1E1 EZyY,
M Wi]
=1:-
H₂
H2
2
2
2
2
E
(ZYY,
M
Wi] Mr-1,Wal)
O4-- [ieYc,
M Wi]
=0(1)
0t-1
2
2
=0(1)at-1 (1 a1-1) E (Z, Mc-1, M,
[O,Y) M,-1, W
Since C₁ is uniformly random, we have that
I (x;V/ Mc - 1 Σ O(1EIZZY Mr-1, W.J2
Now to bound this part, note that first have (M,11, W.) M that I (Z,Y.... 21 Wi) < M. At the same time, notice that Ze is just flipping the value of Vi.... .i...., Yn and thus (Z,Y, ...,.)))) H (YI... .....))) n. Thus have
(Z,Y, ... Z,Y, M,-1, Wt) = H (Z,Y, ... ZYY,) 1(2 ... M- Wi) 2 nn M.
On the other hand, we have that
Σ H (Z.Y Mc-1, W)) 2 (ZY ... ZY, M,11, 2 n M.
Thus.
M >
Σ I - H (ZY,
M,1, [2, =
Σ
Z,, Mc-1. wi?
1=1
where the equality comes from the fact that if Pr [4Y; = M, ,, W.] ] + 8, then
38

---

Published as a conference paper at ICLR 2026
E [2,Y, M--1 Wi] Pr [2,Y 1 M
+ -1
= (2+
1 2
23.
We finally have that
2(1) S (M7; X) x)=
(M++1; (M
I (M, So+1; (M;;
I (S (M)
Σ
T (V4+1; Mss C++1, W4+1)
0(1) T.M
We conclude that T M 2 2(m)-
1.3 HARD INSTANCE II
For the graph problems, we would consider the following Hard Instance.
Definition 1,5 (Hard Instance II). Let X be uniformly random bit. Let yp E (0, 1) with 2211),
and let d ((). Based on X, the adversary chooses d-regular graph on 2n vertices as follows:
X = 0 Pick the graph to be op-expander on 2n vertices.
= 1 We construct two sets as follows: Puir bins the as {1,2), (3, (3.4)..... {2n 1, 2n
Now on each pair {2i 1, 21) pick random Y, E {+1). IfY; = we pul vertex 2: to
set and vertex 2i to set 2; otherwise, we put vertex 2i to set and vertex 2i 1 to set
The graph is then composed of two identical sp-expanders over set and set 2.
We would assume that the algorithm has access the graph only via the random walk queries.
Definition L.6 (Random walk queries). For any specified starting vertex x, random walk query returns the endpoint of an O(log step random walk starting from T.
We have the properties of a random walk for a y--expander as follows:
Lemma L.4. Assume G (V, E) is a d-regular ip-expander on n vertices. Let M be the lazy random walk transition matrix of G. Let '11, 1 be the probability distribution of a random walk with length
O (Logm) p) starting from vertex E V. Let _L_ 1 E TR. be the uniform distribution over
.....,,
vertices. We have that drv (M'1 11 π) <
0.01 n2
To prove Lemma I.4 we first introduce the definition of mixing time.
Definition I.7 (Mixing time). Let = (V, E) be a d-regular graph on n vertices. Let M be the lazy random walk transition matrix of G. Let m, M M'mo, where my is a distribution over [n)] Let ा (,, L be the stationary distribution G. Then the mixing time T. (M) is defined to be the smallest such that for any ma, dmy, T) S e.
Proof of Lemma 1.4 Note that = - 1 r E Rn is the stationary distribution of G. Accord-
ing to spectral graph theory, have T, (M) O ( log(?)) 2)) Let 0.01 n² Note that G
39

---

Published as a conference paper at ICLR 2026
is yp-expander, we have that o(G) yp (see Definition 1.1 Therefore, according to the defi- 0
nition of mixing time, we get that for & (M( 0 log d I 0.01 n²
have that log
With the above results, we would show the space-time trade-off of identifying Hard Instance II.
Theorem 1.3 (Variant of Theorem 1.3). Let A be an algorithm which detects the Hard Instance II with error probability at most 1/3. The algorithm can perform T random walk queries using M bits of space. We have M T = 92 (n).
Remark 1.2. In Theorem 1.3 use M denote the space complexity because S is already used in the proof to refer to a sampling-relan reelling-relted quantity. For consistency with the rest of the paper, we will denote the space of the algorithm by S in subsequent discussions.
Proof of Theorem 1.3 We would reduce this problem the Hard Instance I. Assume we have an algorithm A that solves the Hard Instance II. We would show how it can be used to solve Hard Instance I. At each time, the algorithm would choose make random walk query starting from vertex i. We would then set W, to the Hard Instance I and get the feedback sample 8t. We would feed 9t the algorithm A and then to the next round. Finally, after rounds, we would output the results of A.
To prove the correctness, we need to show that the total variation distance O(1) between the history generated by Hard Instance I: (#1, (81, M....... 8T, mr) and the history generated by Hard Instance II: ( mi....,,y. m'y)) We would prove by math induction.
Now for dTv((m,, st), (m,', s()), we consider any fixed x E [2n], m [M] that
1p(m- = m, = x)- p(m) = m, s¹c = x)]
Σ
p(m+ m, St = 2 m = m, S = T). (m--1 =m, $1-1 = T))
(m,
Σ
p(m) = m, 5/ = x/m6/11 = m, 1/ = T) pmmm-11 = m, 14.1/-1 = F)
m).5)
Σ (m)
p(m-- = m, 81 = 2 1 = m, 81-1 = F)
(p(m (p(m--1 m. St-1 = ②)) -mmmm-111111 m, S/-1 = x))
p(ml_1 = m. 6 =x)
- (p(m: m. St x1/4-11 m, St-1 = -) p(mm m.
s m.
2/m1-1 m, s x))
Now for the first part, we have
Σ
Σ
p(m+ -1, x/ma-1 M, 8:-1 7)
(m,z) (m.))
(p(m--1
m. 81-1 = T) -pmmm_1 m, 86 = x))
(p(m= m, x/m4-11 m, 8:-1 =))
(m,x) (M.
|p(me-1 = st-1 = F) - -p(m'_1 = m 8 = x)))
Σ (lo(me-1= = m, 8 = 3) p(mn'_1 -,, 8/11 = T)
40

---

Published as a conference paper at ICLR 2026
p(me = 8t = = (m,z)
Σ
1 = m, Sc-1 = =z)
p((m-1 m, 8t-1 x) - p(mmm1 m, 8/-1 x)
(m,2)
2drv ( (m (, 81-1)).
For the second part, notice that
p(m = m, S₁ 2 = m, St-1 = z) p(mmm = m, s x x/14-1 = -m, 8 = T)
-p(m, m|s: = I, 11 = m, 81-1 3) p(s: = x/m=-1 = m, 81- 3)
- -pmm = m| = x. m/, = m, 8 = T) p(ss; = =x|m/_1 = m, 8/-11111111 = .).
Note that since we are using the same algorithm, when fixing m4-1 and 8t, the update of my and ml the same, and thus
p(m- m, x|m=-11 m, 8t-1 .) p(mm m, 5/ x x//m/11 m, 8/ 3)
p(m m/st z, m4-1 = m. (p(s: 21|m-11 = m) p( = x m = m))
Moreover, by the property of lazy random walk (Lemmal I.4) we should have that for any m,
Σ p(( = x| m) - p( = x/m/_1 m)l - n
0.01
2
Summing over all (m, we have the second part is bounded by
Σ
Σ
p(m4-1 m, 8/-11 = p(mm = m 8t = x. mh-1 = m)
(m,
(p(s: - m) - p((' m =m))
<
p(ml_1 m, 8/ .) -m(m+ m|s: Iz 1--1 m)
m..
|p(st
x 1 m) p(s/ z 2/mL-1 m|
Σ
p(m/-1 m, 1/11 = I) |p(s = x 22/m=11 = m) - -p(s'- = 2/m1 = m)
=
(x,m,
Σ p(m+ m|s: = x, m = m)
Σ
p(m(-1 m, 1/- = -z) (pppp(( =
x/m=-1 x m) - p(s = x/m1-1 = m))
(2.m,))
Σ p(m/_1 = M, 5/21 = =t) Σ |p(s = f/ - p(ss 2/m1 = =mi)
(m,))
0.01
< 2 x n2
pmmi11 = M, 8 2)
(m.))
0.01 2 n
Combining the results, we have
1 Σ
drv((m,, 8t), (me', ,
pp(m= m, =x) - p(mm, = m, 8 = x:)
2 (m.r)
41

---

Published as a conference paper at ICLR 2026
0.01
dTv(((m (m/ s(-1))
n²
Moreover, for the initial points, we have that
0.01
drv s1) - n²
Since mi mi are merely function of 81, 81, we have that
0.01
dTv(m1, m²) s n²
Therefore
0.02
(1)) (mi', s1)) s + drv(m,, S n²²
drv((m,, 8t); (mi', x)) S 0101(1+1)
n2
This means that
0.01 +
drv(mr, m/r) S drv((me,, ST), (mT', <
< 0.01,
n²
where we use the fact that T Σ O(n²) since otherwise we can get the output using constant space.
Now note that the output result is only the function of my. Since the total variation distance of my is bounded, the correctness can still be guaranteed using the uniform distribution rather than the random walk distribution.
J EXPERIMENTAL DETAILS
Accuracy Let Ci,..., C2 be the ground-truth clustering and let Či..... C2 be the clusters pro- duced by the oracle, where C, = fx E V//HICHCC.USSER (G, = i). The accuracy defined as 1. max, Ex= IC, n Cz((g)l. where : [k]] + [k] is a permutation.
Implementation details In our experiments, we implemented three main components: (i) the new dot product oracle proposed in this paper (Alg- 3 and Alg. [4). (ii) the original dot product oracle in Gluch et al. (2021). and (iii) the spectral clustering oracle relies on a poly(k) conductance gap itself. The clustering oracle relies on accurate dot product estimates to function correctly; hence, we first needed to identify parameters that ensure reliable dot product estimation performance. These parameters include (i) Sdot, the number of sampled vertices in dot product oracle, (ii) t, the random walk length and (iii) I, the number of repetitions in the median trick, and set of space-time-relate parameters.
R. 21:40.8 qu t-200 201--201--00
R,0000, t- 200-201--20
128
363
Dowty
3300
352
(a) unsuitable parameter values: Rint
Repeery =
40
(b) suitable parameter values:
Rusc Rquay 80
Figure 2: Effect of parameter settings the original dot product oracle. (a): unsuitable configura- tion where the estimated spectral dot products for intra-cluster and inter-cluster pairs overlap. (b): a suitable configuration where clear gap emerges between the two distributions.
42

---

Published as a conference paper at ICLR 2026
For the original dot product oracle in Gluch al. (202I), Raitt Rquery are the space-time-related parameters. We set Riit and Rquery according to the theoretical guarantee, which states that the oracle works when Rini Rquery O() Following the implementation details in Shen & Peng 2023 we explored multiple parameter configurations for Sdot. f, L, Rinit Rquery. For each configuration, we initialized the dot product oracle with the corresponding parameters, sampled subset of vertex pairs, computed their estimated spectral dot products, and plotted the density graphs (see Figure 2) The presence of a clear gap (see Figure 2b) in the density graph was used as the criterion for selecting suitable parameter values. In fact, for graph with parameters
3, 0.07, and 0.002, we found that Shat = 20, I = 20, 1 = 20, and Rinit Rquery 2 80 provided reliable estimates. And we make 80 x 80 a concrete instantiation of O(vn) X (V = (n)..
3000,
For the new dot product oracle, we set ddot 20, t 20 and 20 like above. The space-time- related parameters Mun = Mquery serve as inputs, corresponding to Rini = Qquery Mat
80x80
6400
Milt
(see line 2 of Alg. 3 and Alg, 4). In our experiments, we varied Mini = Mquery in the range [30, 80].
Finally, for the clustering oracle itself, we determined the number of sampled vertices (see line 3 of Alg. 12) through extensive testing of multiple candidate values, and selected = 21 for all experiments. Additionally, we set threshold (see line of Alg. 12) construct similarity graph; based on the density plots of estimated dot products (see Figure 2b we chose = 0.0005.
43


Reviews:
[{"review_id": "7xEUqS5ynn", "reviewer": "Reviewer_hd45", "summary": "This paper considered the problem of designing sublinear spectral clustering oracles for well-clustered graphs. The authors assume query access to the adjacency list of the graph. They have given a space-time tradeoff for this problem, and also showed this tradeoff is tight for approaches using only random walk oracles. One of the interesting feature of this work is that their algorithm has space complexity of $o(\\sqrt{n})$, in contrast to previous algorithms which require $\\Omega(\\sqrt{n})$ space.", "questions": "1. The authors should highlight the new ideas in their technique compared to previous works. \n\n2. What is the main bottleneck to extending the lower bound to adjacency oracle query access?\n\n3. Was the tradeoff an explicit open problem in the prior literature?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Strengths:\n\n1. They have given a space-time tradeoff for designing sublinear spectral clustering oracles. \n\n2. They have shown that this tradeoff is tight for approaches that use only random walk oracles", "weaknesses": "1. (Upper bound) The main technical contribution of this work is the construction of an efficient inner-product oracle (Theorem 3.2) for spectrally embedded vertex vectors. However, the details of this construction are not presented in the main text. The authors only sketch those proofs that primarily follow the approach of Shen & Peng (2023).\n\n2. (Lower bound) While the proof of the space–time tradeoff lower bound is nice, it would have been much more interesting if the lower bound had been established under adjacency list query access, which is the more natural and standard setting.\n\n3. I suggest moving the experimental section to the appendix and instead including a more detailed proof outline for Theorem 3.2 in the main text.\n\n4. Although the tradeoff result is nice, it is unclear whether the resolved question was explicitly open in the prior literature. Clarification on this point would be helpful.\n\n5. The authors did not adequately highlight the novel ideas distinguishing their techniques from previous works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ppVUwwgPZk", "reviewer": "Reviewer_64dM", "summary": "The paper studied the construction of spectral clustering oracles on well-clustered graphs with limited memory. The problem has recently attracted a flurry of work due to its applications in sublinear clustering algorithms. Here, we are given a graph that could be partitioned into $k$ clusters where the conductance between the clusters are high and the conductance inside the clusters are low. As such, we could label the vertices to generate a ‘ground truth’ clustering. The goal for the algorithm is to compute a data structure such that upon querying a vertex $x$, the algorithm can answer the cluster label of $x$ with high efficiency. The metrics for good algorithms in this application include:\n- Pre-processing time: the time to construct the data structure\n- Querying time: the time complexity needed to return the answer for each cluster\n- Accuracy: The answer for most of the vertex queries should be correct\n- Memory efficiency: the memory used by the data structure should be small\n\nThe last aspect was the main contribution of this paper. The paper discussed that all previous algorithms require $\\Omega(\\sqrt{n})$ space for such applications; in contrast, this algorithm is able to design an algorithm with only $n^{O(\\varepsilon/\\phi^2)}$ space, where $\\varepsilon$ and $\\phi$ are parameters that characterize the clusterability of the graph. The query time will be affected, which is now $n^{1+O(\\varepsilon/\\phi^2)}$ time. In fact, the trade-off could be made general with $n^{O(\\varepsilon/\\phi^2)}M$ space and $n^{1+O(\\varepsilon/\\phi^2)}/M$ time.\n\n**Main techniques.** The main techniques of the paper follow from the construction in Shen and Peng [NeurIPS’23]. In a nutshell, this line of techniques reduces the algorithm for the spectral clustering oracle to the approximation of the dot products of vertex embeddings. The previous space lower bound is due to the computation of the approximation dot product using random walks, and this paper adopted the simple idea to conduct the walk in batches to trade time efficiency for space efficiency.", "questions": "Most of the questions are embedded in the weakness comments. Some additional questions and comments:\n\nLine 150: The notion of ‘random walk queries’ is not defined. Also, what does Theorem 1.3 mean? The lower bound works only against algorithms that rely exclusively on random walk queries, and cannot make, e.g., degree or neighborhood queries, on adjacency lists? This family of algorithms seems to be extremely restrictive. \n\nLine 262-263: We use $O_\\phi$ *to suppress*; similarly, $\\tilde{O}$ *to hide*.\n\nThe leading constants in $n^O(\\varepsilon)$ appear to be crazily large for any interesting applications. In your experiment, did you conduct some type of algorithm engineering to bring down the actual time and space?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I’m generally supportive of the paper. The spectral clustering oracle problem has attracted quite some attention over the past few years, and it is great that the space aspect is taken into consideration in this paper. I did not get the time to verify the correctness of the results, but the technique overview provided some good justifications for first-time readers to believe the correctness. Some experiments are also provided besides the theoretical results.", "weaknesses": "On the flip side, I think the paper could do a better job in terms of the comparison between their results and existing algorithms.\n\nJudging from the presentation of the main results, it is not entirely clear whether certain restrictions (e.g., $d$-bounded graph) are also used in previous results, and how the misclustering error would compare with oracles with no space limits. \n\nFurthermore, it is not always clear which part of the algorithm follows from existing work, and which part is the contribution of this paper. The techniques are not thoroughly compared with similar papers. Since I do not know the techniques in those papers, it is harder for me to evaluate the technical novelty.\n\nOverall, I think it’s a solid paper with a good set of results. However, the writing issues and the fact that I’m not very familiar with related techniques make it hard for me to champion for it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "X7AyAq78Em", "reviewer": "Reviewer_S7oN", "summary": "This paper considers the task of community detection in well-clusterable graphs with sublinear space. The goal is to design a data structure D that fits in sublinear memory, and that enables one to query the cluster assignment for each node in sublinear time. Previous approaches all require $\\Omega(\\sqrt{n})$ space for such a datastructure D, but this paper overcomes that. In particular, it is able to design a data structure with a much smaller memory requirement that still allow for sublinear time which-cluster queries. The paper also provides new insights into the time-space tradeoff for this problem, by designing oracles there memory usage S and query time $T$ satisfy $S\\cdot T \\approx \\tilde{O}(n)$. Again, this holds for a class of graphs with good clustering structure. The paper also proves that this is optimal up to logarithmic factors for a certain class of techniques.\n\nThe notion of well-clusterable graphs corresponds (roughly) to graphs that have a k partition where clusters are roughly balanced in size and have small conductance (and large inner conductance, which measures internal connectivity of clusters).\n\nThe paper also proves new results (sublinear algorithms and lower bounds) for the 1-cluster/2-cluster problem, which seeks to tell the difference between graphs that are expenders on n nodes or that are disjoint unions of two identical expanders on n/2 nodes. \n\nFor the clustering results, the key technical advance is to provide a new way to estimate the dot product between the spectral embedding of two nodes in sublinear space and time (the spectral embedding for a node comes from the node's entries in the first few eigenvectors of the normalized Laplacian). This primitive is combined with a previously observation that if two nodes are from the same cluster (under the well-clusterability assumptions), then the dot product of their embeddings with be large, and otherwise the dot product will be zero.", "questions": "Is there hope for something like this to be practical for real world graph clustering? What would it take to make that happen?\n\nHow long did it take to construct $\\mathcal{D}$ in practice for your numerical experiments?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* This paper provides good motivation and justification for sublinear time and space algorithms, and tackles and interesting problem in graph analysis. \n* The main theoretical result is interesting and represents a substantial improvement over previous techniques for sublinear space clustering oracles. In particular, it breaks the $\\Omega(\\sqrt{n})$ space barrier limiting previous approaches. The results on algorithms and the lower bound for the 1-cluster/2-cluster problem are a nice bonus addition to the paper. The theoretical results are highly non-trivial. \n* The structure and writing of the paper are excellent; about as good as one could hope for a paper whose core contribution is so dense and complicated. The paper did a very good job motivating the problem, explaining the key contributions and their significance, and communicating the main technical components that made them work. I learned a lot by reading this paper, despite how theoretically dense it is. The presentation is very, very good. \n* I really appreciate that the authors have even provided an implementation of the algorithm and accompanied their theory with numerical experiments. Even if it's only on synthetic data, it is impressive to have an implementation of any kind for an algorithm that is so detailed and complicated.", "weaknesses": "The main downsides of this paper, when considering it for publication at ICLR specifically are: (1) the algorithm is extremely complicated and detailed, and (2) the algorithm is very impractical for real-world clustering problems. I don't this at all disqualifies the article from being accepted and published somewhere. The contribution here seems very impressive. I do wonder though whether ICLR is the right venue for this work, and instead of a core theory conference. For example, the main work this improves upon (Peng 2020; Gluche et al 2021) are both SODA papers.\n\nExpounding more on the two weaknesses above:\n\n(1) Although the writing does an impressive job making the pieces of the algorithm make sense at a high level, there is still no way around how intricate the statements of the results are. Many many different functions and parameters need to be defined---all with complicated dependencies on each other---even just to present the statement of the results, without even considering what it takes to prove the results. \n\n(2) The theory assumes d-regular graphs with a very specific clustering structure that is not going to be satisfied by pretty much any real world graph. Expanding this to d-bounded graphs doesn't make it much more practical. Even if a graph does satisfy the well-clusterability assumptions for certain choices of $k, \\varepsilon, \\varphi$, we wouldn't know these a priori, and the algorithm make strong assumptions about these parameter (just one among many examples: the specific need in Theorem 3.1 for $\\varepsilon /\\varphi \\leq 1/10^5$). \n\nThis makes it all the more impressive that the paper includes an experimental result of any kind, but in order for this to work (even in a very carefully controlled synthetic setting), one needs to try out many different parameters for the algorithms. \n\nI'm still overall in favor of seeing this paper accepted, given the significance of its core technical contribution and its many other strengths. Graph clustering in general seems well within scope at the conference, and the fact that there are at least some numerical experiments is a plus.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)