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

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" ρ and a distribution D such that, with high probability, a sample drawn from D is "high quality," meaning its ρ-value is near 1. The goal is to accept most inputs x ~ D and reject potentially adversarially generated inputs x with ρ(x) far from 1. In this work, we consider the sublinear version of the quality control problem, where D ∈ Delta(0,1N) and the goal is to solve the (D,ρ)-quality problem with o(N) queries and time. As a case study, we consider random graphs, i.e., D = Gn,p (and N = binomn2), and the k-clique count function ρk := Ck(G)/mathbbE_G' ~ Gn,p[Ck(G')], where Ck(G) is the number of k-cliques in G. In suitable parameter ranges, worst-case approximate k-clique counting requires p-Omega(k2) queries. In contrast, we show that the quality control problem for Gn,p (with n≥ p-ck for some constant c) with respect to ρ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.