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

arXiv:2508.16531 · cs.DS, cs.LG, math.CO, math.PR · Submitted 2025-08-22 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Quality control in sublinear time".

Jane: Detailed Research Summary: Quality Control Problems in Sublinear Time (Case Study:

Tom: First, who's behind it and why it matters.

Paper summary: Tom: Hey Jane, so we're looking at this paper today called "Quality control in sublinear time: a case study via random graphs." It seems to be about how to trust an algorithm when it's dealing with inputs that aren't perfectly random, which is a big deal for real-world networks.

Jane: Yeah, the core idea here is defining these "Quality Control Problems," which involve a quality function rho and a distribution D where most samples drawn from D are high quality, meaning their rho value is near one. The goal is to build an algorithm that accepts inputs from D but rejects inputs where the rho value is far from one.

Tom: So, the specific version they tackle here is the sublinear version of this problem with o(N) queries and time for N being the size of a set, which they use as n squared. They use random graphs G n,p as their main example.

Lu: The paper focuses on how motif counting functions, like the k-clique count rho k, can be tested efficiently in this setting. They show that for certain parameter ranges, worst-case approximate k-clique counting needs p to the power of omega of k squared queries.

Meng: That sounds bad for a real system, because if p is small, that query complexity gets really high fast when you need to be sure about the quality of an input. But what they claim is that for random graphs G n,p where n is big enough relative to p and k, they can test this with just p to the power of O of k queries and time.

Jane: That means quality control is provably superpolynomially more efficient in this setting compared to traditional worst-case counting methods. And they generalize that idea for any motif H with maximum degree Delta(H).

Tom: So, we've got the idea that you can get a much better estimate of something by just doing a few queries, which is what the paper "Quality control in sublinear time: a case study via random graphs" is showing us. It’s about moving away from just hoping an algorithm works on average to actually being able to check if it's reliable on any given input.

Lu: The framework they use involves probability theory, quasirandomness, and a technique where you transform the quality control problem for one parameter into another on the same distribution. This suggests that these quality control algorithms provide provably superpolynomially more efficient solutions than traditional worst-case algorithms for estimating these parameters in this random graph setting.

Paper summary: Meng: From a production standpoint, if we can test this with p to the power of O of Delta(H) queries, that's much better than what I'd expect when dealing with noisy data or adversarial inputs where the input distribution isn't perfectly known. But how sure are they about these concentration results holding up for real traffic?

Lalam: Based on my internal literature review, the results for k-clique counts and cycle counts show that they take one/p queries, or rather one/p(k) queries for the clique count <ref:2508.16531#pg1>. This is what the paper claims under certain conditions.

Jane: So if we think about a listener who just wants to know if a piece of data they received from an AI is likely accurate, this paper suggests there's a way to check that without having to check everything. It moves beyond just testing the input distribution D itself and focuses on checking the quality function rho.

Tom: The specific result they highlight for triangle counting shows it can be solved in O(one/p) queries and time if you have access to adjacency list, adjacency matrix, and vertex degree queries <ref:2508.16531#pg1>. That’s a very efficient bound when it comes to simple structures like triangles.

Meng: one/p is fast, but that depends on being able to query the graph structure directly in that way <ref:2508.16531#pg1>. What if we're working on a massive graph where we can't even afford those direct structural queries easily? That’s where I get nervous about deployment.

Lu: The paper does address this by showing a general quality control algorithm for any motif H on k vertices, which is solvable in O(p - c one (H)) adjacency matrix queries and running time when p is large enough, specifically when p = n - one/m H <ref:2508.16531#pg1>.

Jane: That means the complexity scales with the maximum degree of the motif you are interested in. If you're looking at a very sparse structure, Delta(H) is small, and it gets faster. If it’s dense, that query count goes up a bit.

Tom: So what this paper really changes for us is that we can prove efficiency guarantees for these quality control problems on random graphs when the input isn't guaranteed to be perfectly drawn from D, but just likely to be close to it. It gives us a concrete way to verify the trustworthiness of an algorithm under uncertainty.

Paper summary: Meng: For me, the practical implication is that if we are deploying a model and we can estimate its internal structure using these quality control checks, we might reduce the computational cost of verification significantly compared to running full exhaustive checks.

Lalam: My literature suggests that this quality control approach connects to average-case complexity results. Specifically, Theorem C.two states that the average-case complexity over G n,p for counting motifs in a graph with high probability is approximately one/p(H) <ref:2508.16531#pg1>.

Jane: So it seems like the authors are tying this quality control work directly into average-case performance bounds for motif counting in random graphs. It’s connecting the trust mechanism to the overall efficiency of the estimation task.

Tom: So, to wrap up on this paper "Quality control in sublinear time: a case study via random graphs," it formalizes a way to check if an algorithm is reliable when inputs are not perfectly distributed according to D. It shows that for random graphs, we can do this with sublinear queries relative to N, and the scaling depends on the motif's maximum degree.

Lu: The work also extends beyond just Erdős–Rényi graphs, showing a universal quality control algorithm for any motif H on k vertices as long as the distribution D satisfies specific concentration properties regarding labeled induced copies of subgraphs within H.

Meng: I still worry about the practical cost of running that universal quality control algorithm if we have a very complex motif, because even with the best bound it's not constant time; it’s still dependent on p.

Lalam: My literature suggests that the authors are quite confident in their bounds for k-clique counts and cycle counts, showing they take one/p(k) queries <ref:2508.16531#pg1>.

Jane: So for a listener who just wants to know if the AI is trustworthy, this paper gives them a mathematical proof that we can verify it efficiently without having to check every single possibility.

Tom: That's the essence of it: moving from average case performance on random data to provable reliability checks under adversarial conditions. We saw how these quality control problems can be solved with p to the power of O of Delta(H) queries and time in this context, which is a clear win for efficiency over traditional methods.

Conclusion: Tom: So, we’ve been talking about these Quality Control Problems in sublinear time for random graphs and what they mean for how we trust algorithms when inputs aren't perfect samples from a known distribution.

Jane: That’s right, so the authors are looking at this new way to check if an algorithm is reliable on any input, not just on average.

Tom: They call it the Quality Control Problem, defined by a quality function rho and a distribution D where most things drawn from D are high quality. The main takeaway is they can test this with sublinear queries, meaning fewer queries than you’d expect for traditional methods.

Jane: Sublinear queries relative to N squared, which is basically like testing something without having to look at the whole dataset every single time. That’s a big deal for scalability, especially in network science where we deal with massive graphs.

Lu: The authors show this applies specifically to things like counting cliques in random graphs G n,p, where they find that the quality control problem is provably superpolynomially more efficient than just doing the standard worst-case counting.

Meng: Superpolynomially more efficient means the query complexity scales much better with n. If this holds up for real traffic at scale, it could cut down verification costs significantly in production environments.

Lalam: I’ve seen the literature on motif counting, and this paper connects directly to that by showing how a quality control algorithm can be set up to filter out bad inputs based on structural properties of the motif itself.

Jane: So if you only listen to this show, think about it like a security check for an AI model. Instead of running every possible test, you use these quality control checks to verify if the input is likely good enough before trusting the output.

Tom: The paper’s title, "Quality control in sublinear time," really captures that idea of getting high-confidence results with very few queries. The authors are focusing on proving this efficiency for specific graph structures like cliques and general motifs.

Jane: They’re showing that you don't need to check everything to be sure about the quality of an input coming from a random process, which is a kind of mathematical guarantee.

Tom: It’s moving the goalpost from just counting things accurately to proving that we can verify accuracy very cheaply under uncertainty. This suggests a new way to think about model validation in complex systems.

Jane: And this leads us into what the authors are doing next, specifically how they generalize these results beyond just random graphs and simple clique counts.

School of Engineering and Applied Sciences, Harvard University · Computer Science and Artificial Intelligence Laboratory, MIT

cs.DS, cs.LG, math.CO, math.PR

Submitted: 2025-08-22

Updated: 2026-10-15

Comments: 84 pages. FOCS 2026

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

The gist: Detailed Research Summary: Quality Control Problems in Sublinear Time (Case Study: Random Graphs) This research focuses on formalizing and solving a new class of algorithmic problems termed "Quality

Key concepts

Quality Control Problems: These are algorithmic challenges where the goal is to distinguish inputs drawn from a known good distribution (like random graphs) from potentially bad inputs. The problem is defined by a 'quality function' $\rho$, aiming to accept most inputs while rejecting those with poor quality, i.e., $\rho(x)$ far from 1.
Sublinear Version: This refers to solving the quality control problem using only $o(N)$ queries and time, where $N$ is related to the size of the graph (e.g., $\binom{n}{2}$ for random graphs). The goal is to find a solution that scales much better than linear or polynomial time relative to the input size.
Motif Quality Function ($ ho_k$): This function measures how close a specific graph's count of a subgraph (motif) is to its expected count in the random graph model. A high $\rho_k$ value near 1 indicates that the actual number of $k$-cliques in the given graph is very close to what you would expect from a purely random graph with the same parameters.
Query Complexity Bounds: These are mathematical limits on how many times an algorithm must ask for information (queries) to solve a problem. The paper shows that for counting cliques or general motifs $H$, these bounds are significantly better than previous worst-case estimates, often scaling as $p^{-O(k)}$ or $p^{-O(\Delta(H))}$.

Summary

Detailed Research Summary: Quality Control Problems in Sublinear Time (Case Study: Random Graphs)

This research focuses on formalizing and solving a new class of algorithmic problems termed Quality Control Problems. These problems are designed to bridge the gap between algorithms optimized for inputs drawn from a known distribution D (e.g., random graphs) and those designed to handle potentially adversarial inputs. A quality control problem is defined by a distribution D and a quality function rho, where the objective is to devise an algorithm that accepts inputs x about D with high probability, while effectively rejecting inputs whose quality measure, rho(x), deviates significantly from 1.

The core investigation centers on the sublinear version of this problem: solving the (D, rho) -quality problem using only o(N) queries and time. The paper utilizes Erdős–Rényi graphs, denoted G n,p, as a primary case study. The quality function rho k(G) is specifically tied to counting subgraphs (motifs), exemplified by the ** k-clique count**. Let mu k(n, p) be the expected number of k-cliques in G n,p. The quality parameter rho k(G) is defined as the ratio of the actual number of k-cliques in G to this expectation: rho k(G) = (number of k-cliques in G) / mu k(n, p). The fundamental insight is that for sufficiently large n relative to p and k, the actual count concentrates around the expectation, meaning rho k(G) is close to 1.

Key Theoretical Framework and Techniques

The paper establishes a powerful methodology by leveraging three synergistic components:

Probability Theory: Utilizing concentration of sampled values to bound deviations from expected counts.
Quasirandomness: Employing concepts like jumbledness to ensure the input distribution behaves predictably under sampling.
The Quality Control Insight: A crucial technique is demonstrating that a quality control algorithm A for a specific parameter (D, rho) can be transformed into an algorithm A' for an unrelated parameter tau on the same distribution D, where A' filters out instances rejected by A.

This framework implies that quality control algorithms provide provably superpolynomially more efficient solutions than traditional worst-case algorithms for estimating these parameters in this random graph setting. Furthermore, the framework suggests that quality control implies strong average-case complexity results.

Main Results and Complexity Bounds

The paper presents several concrete results detailing the query complexity and runtime for various motif counting problems:

** k-Clique Counting:** For a fixed constant k and sufficiently large n (specifically when p at least omega n - 2/(k-1)), the quality control problem (G n,p, rho k) is solvable in O(p - c 1 k) adjacency matrix queries and time. A related result specifies that under an additional condition (p = ((n)/n) 1/(4k-1)), the problem is solvable in O(p - c 3 k) time.
Triangle Counting: For triangles (a specific case of motif counting), the quality control problem (G n,p, rho) can be solved remarkably efficiently in O(1/p) queries and time, provided access to the adjacency list, adjacency matrix, and vertex degree queries is available.
General Motifs (H): For a general motif H on k vertices, the quality control problem (G n,p, rho H) is solvable in O(p - c 7 (H)) adjacency matrix queries and running time.

Specific Theorem Summaries:

Theorem 1.2: Formalizes the solvability of (G n,p, rho k) with the stated query complexity bounds.
Theorem 4.1 (and Theorem 1.5): Addresses general motifs H, showing solvability in O(p - c 1 (H)) queries when p = n - 1/m H.
Corollary 4.2: Provides tight bounds for specific structures: cycle counts take 1/p(1) queries, and k-clique counts take 1/p(k) queries.
Theorem 4.8 (Lower Bound): Establishes a lower bound on the query complexity for (G n,p, rho H) -quality control algorithms, showing that any such algorithm must have a query complexity of at least c times p - (H)/2.

Extensions and Connections to Broader Complexity Theory

The research extends beyond Erdős–Rényi graphs:

General Distributions: Theorem 5.2 establishes a universal quality control algorithm for any motif H on k vertices, provided the underlying distribution D n satisfies specific concentration properties regarding labeled induced copies of subgraphs within H. The complexity here is O(r k(H) - 2) queries, where r k(H) relates to the structure of the motif.
Stochastic Block Models (SBMs): Section D provides concentration results for subgraph counts in SBMs, showing that motif counts are well-concentrated around their expectations with high probability (e.g., at least 9/10).
Average-Case Complexity: The framework connects to average-case complexity via Theorem C.2, stating that the average-case complexity over G n,p for counting motifs in a graph with high probability is approximately 1/p(H).
General Graph Parameters: Theorem B.2 generalizes the result to any graph parameter F computable by a P-NC0 circuit with fan-in k and depth d. The query complexity for (G n,p, rho F) is 1/p poly(k d), where k d relates to the circuit structure.

Algorithm Detail: Triangle Quality Control

The paper details a specific implementation, Algorithm Triangle-Quality, which synthesizes several subroutines (A through D) to achieve the quality control goal for triangle counts in G n,p. This algorithm involves sequential steps utilizing Lemma A.2, Corollary A.5, and Lemmas A.7/A.8 to perform filtering based on expected bounds (t) and rejection criteria (delta). The overall complexity is dominated by the initial step (Lemma A.3), resulting in a query complexity and runtime of O(1/p).

**In conclusion, this paper provides a rigorous, theoretically grounded framework for analyzing the estimation of subgraph counts in random graphs under adversarial conditions. It demonstrates that quality control algorithms offer significant computational advantages by achieving sublinear query complexities relative to N, with bounds scaling inversely with powers of p and structural properties ((H)) of the motif being counted.

Improvements for AI systems

Improved Sublinear Quality Control for Clique Counts: The Algorithm Clique-Quality-Efficient algorithm can test if a graph is drawn from Erdős–Rényi graphs with respect to k-clique counts using only 1/pO(k) adjacency matrix queries and a runtime of 1/pO(k) · exp(poly(k/ε)).
Improved Motif Counting for General Motifs: The quality control problem for general motifs H in Erdős–Rényi graphs can be solved with O(p − c1∆(H)) adjacency matrix queries and runtime, where ∆(H) is the maximum vertex degree of H.
Enhanced Distinguishing Power: Quality control algorithms can distinguish between a graph drawn from Gn,p and an adversarially generated structure contributing at least εµH labeled induced copies of a constant-sized subgraph H by querying the adjacency matrix within that subgraph.