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

Abstract:Many algorithms are designed to work well on average over inputs. But when such an algorithm is run on an arbitrary input, the question arises: Can we trust the algorithm on this input? This question is especially relevant in network science, where algorithms for theoretical random graph models are often applied to individual real-world networks. We identify a new class of algorithmic problems addressing this, which we call "Quality Control Problems." These problems are specified by a "quality function" $\rho$ and a distribution $D$ such that, with high probability, a sample drawn from $D$ is "high quality," meaning its $\rho$-value is near $1$. The goal is to accept most inputs $x \sim D$ and reject potentially adversarially generated inputs $x$ with $\rho(x)$ far from $1$. In this work, we consider the sublinear version of the quality control problem, where $D \in \Delta(\{0,1\}^N)$ and the goal is to solve the $(D,\rho)$-quality problem with $o(N)$ queries and time. As a case study, we consider random graphs, i.e., $D = G_{n,p}$ (and $N = \binom{n}2$), and the $k$-clique count function $\rho_k := C_k(G)/\mathbb{E}_{G' \sim G_{n,p}}[C_k(G')]$, where $C_k(G)$ is the number of $k$-cliques in $G$. In suitable parameter ranges, worst-case approximate $k$-clique counting requires $p^{-\Omega(k^2)}$ queries. In contrast, we show that the quality control problem for $G_{n,p}$ (with $n\geq p^{-ck}$ for some constant $c$) with respect to $\rho_k$ can be tested with $p^{-O(k)}$ queries and time, showing quality control is provably superpolynomially more efficient in this setting. More generally, for a motif $H$ of maximum degree $\Delta(H)$, we show that the corresponding quality control problem can be solved with $p^{-O(\Delta(H))}$ queries and running time.

84 pages. FOCS 2026

Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Combinatorics (math.CO); Probability (math.PR)

arXiv:2508.16531 [cs.DS]

(or arXiv:2508.16531v3 [cs.DS] for this version)

https://doi.org/10.48550/arXiv.2508.16531 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.