Source-linked AI summary
Statistics of Similarity Graphs in Node-Arrival Streams
Kaiwen Liu, Qin Zhang
TL;DR
The paper asks how to perform fundamental statistical tasks on implicit similarity graphs presented as node-arrival streams, where pairwise weights are available only through stored items. It develops constant-pass, sublinear-space algorithms for degree moments, diversity, and their samplers, and shows lower bounds that nearly match upper bounds in stream length. One-pass sublinear-space algorithms are ruled out for these tasks.
Problem
The central question is how space-efficiently to compute fundamental statistics on an implicit similarity graph when the stream presents nodes rather than edges or weights.
Source: §1 · p. 1Method
The paper develops constant-pass streaming algorithms for degree moments, diversity index, degree-moment sampling, and diversity sampling using an on-demand similarity function over node-arrival streams.
Source: §1 · pp. 2–3Results
Constant-pass upper and lower bounds nearly match in their dependence on n, while one-pass sublinear-space algorithms are ruled out for all four tasks.
Source: §1 · p. 3Takeaways & Limitations
The results establish near-tight space dependence on stream length for statistical computation and sampling on implicit similarity graphs.
Source: §1 · p. 3The upper and lower bounds still differ with respect to ϵ, and other similarity-graph statistics remain open for study.
Source: §4 · p. 24
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies statistical tasks on implicit similarity graphs in node-arrival streams, where similarities are computed on demand from stored items. It develops constant-pass, sublinear-space algorithms and nearly matching space lower bounds across these tasks.
Motivation
- Similarity graphs generalize frequency-based streaming statistics by letting similar but nonidentical items contribute through pairwise similarities.Their weighted degrees represent similarity-aware frequencies and capture relational structure absent from individual frequencies.Source: §1 · p. 1
Problems
- The paper studies degree moments, diversity index, degree-moment sampling, and diversity sampling on the induced similarity graph.Under equality similarity, these recover classical frequency moments, distinct-element counting, ℓp+1-sampling, and ℓ0-sampling, respectively.Source: §1 · p. 2
Model
- The node-arrival model provides stream items and a similarity function, while edge weights are computed only when both corresponding items are stored.The graph is complete and weighted, with w(i,j)=f(σi,σj) and self-loop weight 1.Source: §1 · pp. 1–2
Upper bounds
- Three passes suffice for (1+ϵ,o(1))-approximation of diversity index and diversity sampling, while two passes suffice for degree moments and degree-moment sampling.The stated algorithms use O(·) words of space, though the supplied result passages contain garbled space expressions.Source: §1 · p. 3
Lower bounds
- One-pass algorithms for all four tasks require Ω(n) bits, while constant-pass lower bounds nearly match the upper bounds in their dependence on n.For diversity sampling, the constant-pass lower bound is Ω(√n) bits; the paper states that the remaining gap is mainly logarithmic factors in n.Source: §1 · p. 3
2 Algorithms
The paper develops constant-pass, sublinear-space algorithms for estimating diversity, sampling inversely by degree, estimating degree moments, and sampling by degree-moment contributions. The main strategy partitions nodes by estimated degree, handling high-degree nodes through witnesses and low-degree nodes through samples with exact degree computation when needed.
Algorithmic setting
- The algorithms assume a known stream length n and use the similarity function to estimate graph statistics over node-arrival streams.The known-n assumption can be removed without an additional pass.Source: §2 · p. 5, §2.1 · p. 5
Diversity index
- High-degree nodes are identified with a witness set, while low-degree nodes are sampled and processed separately.This partition reduces variance because low-degree contributions can be estimated from a sample of size ˜O(√n).Source: §2.1 · p. 5
- Three passes suffice for a (1 + ϵ, o(1))-approximation of DI using sublinear space.The analysis establishes high-probability degree separation and accurate estimates for both groups.Source: §2.1 · pp. 5, 7
LDI-sampling
- Three passes also yield a (1 + ϵ, o(1))-LDI-sampler that samples nodes with probability approximately inversely proportional to degree.Conditioned on the stated event, the failure probability is at most 2/n^3 and each node’s sampling probability is within a (1 ± ϵ) factor of d_j^-1.Source: §2.1 · p. 8, §2.2 · pp. 9–10
Degree-moment estimation
- For degree moments, the paper compresses the approach to two passes and obtains a (1 + ϵ, 0.01)-approximation for every p > 0.Parallel repetition and taking the median boost the success probability to 0.99 with only a constant-factor space increase.Source: §2.3 · pp. 12–13
LMp-sampling
- Two passes also suffice for LMp-sampling, with failure probability O(n^−2p−5) under the stated parameter assumption.The algorithm stores candidates that may attain the minimum and processes every such node.Source: §2.4 · pp. 16, 18
3 Lower Bounds
The lower bounds reduce INDEX and DISJ to streaming tasks on succinctly represented implicit similarity graphs. They show linear one-pass lower bounds and near-linear multi-pass lower bounds for approximation and sampling variants.
Reduction framework
- The lower-bound constructions use reductions from INDEX and DISJ, whose randomized communication complexity is Ω(n) at success probability 0.51.Each hard-instance stream item has an O(log n)-bit representation, allowing direct similarity evaluation.Source: §3 · p. 19
One-pass lower bounds
- Any one-pass (C, 0.49)-approximation algorithm for DI requires Ω(n) bits of space for every constant C ≥ 1.The reduction distinguishes instances with DI(INO) = (1 + 2C^2)k from instances with DI(IYES) < 2k.Source: §3.1 · p. 19
- One-pass (1 + ϵ, 0.49)-samplers for diversity and degree moments require Ω(n) bits of space.The LDI-sampler and LMp-sampler lower bounds use repeated independent copies in INDEX protocols.Source: §3.1 · pp. 20–21
- Any one-pass (C, 0.49)-approximation algorithm for Mp requires Ω(n) bits of space for every p > 0 and constant C ≥ 1.The reduction creates a multiplicative separation between Mp(INO) and Mp(IYES).Source: §3.1 · pp. 20–21
Multi-pass lower bounds
- For O(1) passes, diversity approximation requires Ω(n) space, while degree-moment approximation requires Ω(min(n, ϵ^−1/(p+1)n^(1−1/(p+1)))) space.The multi-pass reductions use DISJ and communicate O(s) bits when the streaming algorithm uses s bits.Source: §3.2 · pp. 22–23
- For O(1) passes, LMp-sampling requires Ω(n^(1−1/(p+1))) bits, and LDI-sampling requires Ω(√n) bits.Both bounds follow from DISJ reductions with communication proportional to the streaming space.Source: §3.2 · pp. 22–24
4 Concluding Remarks
The paper studies several statistical problems on similarity graphs in node-arrival streams, while leaving tight dependence on ϵ and additional graph statistics for future work.
Open questions
- The upper and lower bounds match in their dependence on n but still differ in their dependence on ϵ.The paper explicitly asks whether the bounds can be made tight in ϵ.Source: §4 · p. 24
- The authors also identify studying other statistical problems on similarity graphs in node-arrival streams as an open direction.Source: §4 · p. 24