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

arXiv:2508.16531v3 Announce Type: replace-cross 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 = inom{n}2), and the k-clique count function rho_k := C_k(G)/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 ngeq 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.

Source: arXiv cs.LG | 2026-10-16