CS Paper Radar

Optimal Passes and Perfect Sampling for Similarity Graph Statistics

Qin Zhang

cs.DS ·submitted 2026-09-17 22:41 UTC · v1
hot direction

Abstract

We study statistical estimation on implicit weighted similarity graphs presented as node-arrival streams. Previous work~\cite{LZ26b} obtained constant-pass, sublinear-space algorithms for several basic statistics of such graphs, including the diversity index $\mathsf{DI}=\sum_i d_i^{-1}$ and the degree moments $M_p=\sum_i d_i^p$ for $p>0$, together with their associated sampling problems $L_{\mathsf{DI}}$ and $L_{M_p}$. We settle three questions left unresolved by the previous work. First, we show that any two-pass streaming algorithm that $1.1$-approximates $\mathsf{DI}$ requires $Ω(n)$ bits of space; combined with the three-pass $\tilde{O}(\sqrt n)$-space algorithm of~\cite{LZ26b}, this establishes a sharp transition between two and three passes for $\mathsf{DI}$. Second and third, for every fixed $c>0$ we give a three-pass $n^{-c}$-perfect $L_{\mathsf{DI}}$-sampler using $O_c(\sqrt n\log n)$ words and a two-pass $n^{-c}$-perfect $L_{M_p}$-sampler using $O_{p,c}(n^{1-1/(p+1)}\log n)$ words. Matching lower bounds up to polylogarithmic factors show that both the number of passes and the polynomial dependence on $n$ are optimal.

Comment
32 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Statistics of Similarity Graphs in Node-Arrival Streams

cs.DS ·2026-09-03 ·Kaiwen Liu, Qin Zhang
highly cited similarity 0.79
Abstract · 27 pages

In this paper, we study several statistical problems on similarity graphs in the node-arrival streaming model, including degree moments, diversity index, degree-moment sampling, and diversity sampling. We develop constant-pass, sublinear-space streaming algorithms for these problems and establish space lower bounds that nearly match the upper bounds in their dependence on the stream length.

0.53

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.68
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.12

Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

cs.DS ·2026-09-16 ·Adithya Diddapur
theory similarity 0.66
Abstract · 25 pages, 1 figure

We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We make progress towards this gap with a strong lower bound for a restricted range of $β$: whenever $β\leq \sqrt{n}/36\log n$, any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

0.30

Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes

cs.DS ·2026-11-03 ·Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
theory similarity 0.65
Abstract

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $Ω(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).

0.20

Matching in Random-Order Streams via Historical Deletion Bounds

cs.DS ·2026-11-12 ·Alireza Farhadi, Mohammadtaghi Hajiaghayi, Mohammad Mahdavi
theory similarity 0.65
Abstract · 38 pages, including appendices

We study maximum matching when the edges of a fixed graph arrive in a uniformly random order. For any fixed $\varepsilon>0$, we give a one-pass algorithm that achieves, with high probability over the arrival order, approximation ratios of $0.71295$ for unweighted graphs and $0.71295-\varepsilon$ for weighted graphs, using near-linear space with an explicit charge for weight precision. Both approximation ratios hold for bipartite and general graphs. The algorithm does not require the stream length or the weight range in advance. The main structural ingredient is a historical deletion inequality for weighted matchings. The deletion price of a vertex set is the decrease in maximum matching weight when that set is removed. We bound the sum of these prices for pairwise disjoint vertex sets, even when each price is evaluated at a different stage as edges are added to the graph. Applied to the usual unfolding of integer weights, it transfers a bipartite cardinality certificate to an original weighted matching, even when the original graph is not bipartite. This transfer preserves the approximation coefficient. We combine this transfer with a refined analysis of fractional matchings in the two auxiliary graphs arising in the transfer theorem. An exact rational linear-programming certificate proves the stated constant for every feasible graph profile. The approximation guarantees and the new structural results are formally verified in Lean.

0.41

Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

cs.LG stat.ML ·2026-09-27 ·Soham Dan
theory similarity 0.64
Abstract

Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.

0.18

Sampling Matchings in Near-linear Time

cs.DS ·2026-09-18 ·Tianshun Miao, Yitong Yin
theory similarity 0.64
Abstract

For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

0.38

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.63
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26