Quality control in sublinear time: a case study via random graphs

Cassandra Marcussen, Ronitt Rubinfeld, Madhu SudanarXiv 2025 · DOI · arXiv

Abstract

This paper introduces "Quality Control," a novel algorithmic framework for sublinear-time property estimation. By allowing algorithms to reject inputs that deviate significantly from "typical" behavior, the authors achieve superpolynomial speedups in motif counting—specifically $k$-cliques—reducing query complexity from $p^{-\Omega(k^2)}$ to $p^{-O(k)}$ in random graph models.

Introduction: The Trust Gap in Sublinear Algorithms

In computer science, a fundamental tension exists between average-case and worst-case analysis. Many algorithms perform exceptionally well on "average" or random inputs but fail catastrophically when faced with adversarial, worst-case examples. For practitioners, this creates a dilemma: if you are handed a specific input, how do you know if you can trust an average-case algorithm?

Statistically, it is impossible to determine if a single sample was drawn from a specific random distribution. Conversely, running a full "worst-case" check to verify an input's properties is often computationally prohibitive, sometimes even NP-hard. This paper bridges the gap by defining Quality Control (QC) Problems, a framework that allows for sublinear-time algorithms that are guaranteed to work on typical inputs while safely rejecting those that are "bad."

The Quality Control Framework

The goal of a Quality Control algorithm is twofold:

  1. Acceptance: It must accept inputs that are "high quality" (i.e., typical of a target distribution $\mathcal{D}$).
  2. Rejection: It must reject inputs where a specific "quality function" $\rho$ (such as a clique count) is far from the expected value.

This objective is intentionally weaker than full property testing or estimation. By allowing the algorithm to reject "weird" inputs—even if they might technically be valid—the framework enables massive efficiency gains that are impossible in traditional worst-case analysis.

Technical Innovations

The authors demonstrate the power of this framework through the problem of counting motifs (small subgraphs like cliques or cycles) in random graphs. Their approach relies on three key technical pillars:

1. Exponentially Robust Quasirandomness

The authors define a new property for graphs where the count of small subgraphs in a random sample is highly concentrated around the global mean. This is a relaxation of standard quasirandomness specifically designed to be testable in sublinear time. It ensures that a tiny, randomly sampled subgraph can reliably certify the global properties of a massive graph.

2. The Inductive Filtering Lemma

To verify if a graph contains the expected number of $k$-cliques, the algorithm employs a hierarchical approach. Rather than jumping directly to $k$, it iteratively checks for $(k-1)$-cliques, $(k-2)$-cliques, and so on. If the graph fails to meet the expected density at any level, it is rejected. This "filtering" ensures that by the time the algorithm reaches the $k$-clique check, the graph is sufficiently "well-behaved" for a small sample to be accurate.

3. Jumbledness Testing

To optimize runtime, the algorithm utilizes "jumbledness," a measure of how evenly edges are distributed across the graph. The authors show that if a sampled subgraph is sufficiently jumbled, they can employ efficient approximate counting algorithms that are significantly faster than brute-force enumeration.

Key Results and Speedups

The paper evaluates these methods against several mathematical models, including Erdős–Rényi graphs ($G_{n,p}$), Stochastic Block Models, and $d$-regular graphs. The results demonstrate a significant reduction in query complexity:

  • $k$-Clique Speedup: In the worst-case sublinear setting, estimating $k$-cliques requires roughly $p^{-\Omega(k^2)}$ queries. The Quality Control algorithm requires only $p^{-O(k)}$ queries. For large $k$, this represents a superpolynomial improvement.
  • Triangle Counting: For the specific case of triangles ($k=3$), the authors identify the exact complexity as $\Theta(1/p)$ queries. This provides a quadratic speedup over the worst-case requirement of $\Theta(p^{-3})$.
  • Structural Complexity: A major insight of the paper is that for a general motif $H$, the difficulty of the QC problem is driven not by the number of vertices in $H$, but by its maximum degree $\Delta(H)$. This provides a clean, structural explanation for algorithmic complexity in this space.

Conclusion and Future Directions

The Quality Control framework suggests that we don't need to know if a graph is random; we only need to know if it acts random enough for our specific property of interest. While the paper establishes the $p^{-O(k)}$ and $p^{-O(\Delta(H))}$ scaling, the exact constants in the exponents remain an open question.

Future work may explore the "sparse regime," where the number of vertices $n$ is not large relative to $1/p$. Furthermore, the authors suggest that the Quality Control framework could be applied to other domains, such as high-dimensional geometry or property testing of distributions, potentially revolutionizing how we handle complex data structures in sublinear time.

Summary updated

BibTeX
@misc{marcussen2025quality,
  author = {Cassandra Marcussen and Ronitt Rubinfeld and Madhu Sudan},
  title = {{Quality control in sublinear time: a case study via random graphs}},
  year = {2025},
  eprint = {2508.16531},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.16531},
}
Figure