Query Lower Bounds for Correlation Clustering Under Memory Constraints

Sumegha Garg, Songhua He, Periklis A. Papakonstantinou

TL;DR

This paper introduces the study of memory-query tradeoffs for graph problems, specifically focusing on correlation clustering. The authors establish tight lower bounds on the number of queries required to approximate correlation clustering, even under strict memory constraints, revealing a fundamental interplay between memory and query complexity.

What Problem Does This Paper Address?

Correlation Clustering (CC) is a fundamental problem in machine learning and network analysis. Given a graph where edges represent "similar" items and non-edges represent "dissimilar" items, the goal is to partition the vertices into clusters to minimize disagreements (e.g., similar items in different clusters, dissimilar items in the same cluster). While CC has been extensively studied, this paper tackles a crucial aspect: understanding the trade-offs between the number of queries an algorithm makes to a graph and the amount of memory it uses, especially when aiming for approximate solutions. This is particularly relevant for massive graphs that cannot be fully loaded into memory. The authors investigate how memory limitations impact the query complexity for solving CC, both for finding an approximate clustering and for just estimating its optimal cost.

Methods

The paper employs a variety of sophisticated techniques from theoretical computer science to establish its lower bounds. Key methods include:

  • Adjacency Matrix Query Model: For a direct lower bound on finding an approximate clustering, the authors use a model where algorithms can query any pair of vertices to check for an edge.
  • Random Query Model: To study memory-query tradeoffs, a model is introduced where algorithms receive uniformly random vertex pairs and an indicator of whether they form an edge. This model is crucial for analyzing scenarios with limited memory.
  • Information Theory: Concepts like Fano's inequality and mutual information are central to bounding the information an algorithm can extract from queries, especially when dealing with noisy or approximate answers.
  • Fourier Analysis: Techniques from Fourier analysis are adapted to analyze the distinguishability of graph distributions, particularly in the context of the PD-BHP (Perturbed Distributional Boolean Hidden Partition) problem.
  • Hybrid Arguments: The authors construct complex hybrid distributions by combining different graph models to bridge the gap between theoretical problems and the target graph problem.
  • Adversarial Input Distributions: Carefully constructed graph distributions are used to create challenging instances for algorithms, forcing them to make many queries to gain sufficient information.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and establishes lower bounds based on algorithmic models and input distributions, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Memory and Query Complexity are Fundamentally Intertwined: The paper demonstrates that for graph problems like correlation clustering, reducing memory usage significantly increases the number of queries required, even for approximation tasks. This is a crucial insight for designing efficient algorithms for large-scale graph analysis.
  • Approximating Cost vs. Finding Partition: The authors show that even the seemingly easier task of approximating the optimal clustering cost (without necessarily outputting the partition itself) still requires a substantial number of queries, especially under memory constraints.
  • The Random Query Model is Powerful for Tradeoffs: By analyzing algorithms in the random query model, the paper provides the first non-trivial query-space tradeoffs for graph problems, highlighting how random access patterns interact with memory limitations.
  • General Graph Model is Harder: While tighter bounds are achieved in the adjacency matrix model, the paper also establishes lower bounds in the more general graph model (allowing neighbor and degree queries), showing that these richer query types don't necessarily make the problem easier in terms of query complexity for approximation.

Key Results

  • Tight Ω(n/ε²) Query Lower Bound: For correlation clustering, any algorithm that finds a clustering with an additive error of O(εn²) requires Ω(n/ε²) adjacency-matrix queries. This matches existing upper bounds, settling the query complexity in this model.
  • Memory-Query Tradeoff in Random Query Model: For algorithms with limited memory (y√n bits), the paper establishes a lower bound on queries q that depends on both n, ε, and y. Specifically, q = Ω(n/ε²) if y ≥ 1 and q = Ω(n/ε² * min(1/y², n/ε²)) if y < 1. This is the first such tradeoff for graph problems in this model.
  • Lower Bound in General Graph Model: An Ω(n/ε) query lower bound is proven for correlation clustering in the general graph model, which is weaker than the adjacency matrix bound but established in a more powerful query model.

Limitations and Future Work

  • General Graph Model Bounds Not Tight: The lower bounds for the general graph model are not yet tight, leaving room for further research to improve them.
  • Focus on Additive Error: The results primarily focus on additive error guarantees (εn²). Exploring tradeoffs for multiplicative error or mixed guarantees could be a future direction.
  • Specific Graph Models: While the paper uses carefully constructed distributions, extending these results to more general or natural graph families could be valuable.
  • Broader Graph Primitives: The authors view correlation clustering as a testbed and suggest that this work is a first step towards studying query-space tradeoffs for a wider range of graph primitives.

Summary updated

Abstract

This work initiates the study of memory-query tradeoffs for graph problems, with a focus on correlation clustering. Correlation clustering asks for a partition of the vertices that minimizes disagreements: non-edges inside clusters plus edges across clusters. Our first result is a tight query lower bound: to output a partition whose cost approximates the optimum up to an additive error of $\varepsilon n^2$, any algorithm requires $Ω(n/\varepsilon^2)$ adjacency-matrix queries. Under memory constraints, we show that even for the seemingly easier task of approximating the optimal clustering cost (without producing a partition), any algorithm in the random query model must make $\gg n/\varepsilon^2$ adjacency-matrix queries. Finally, we prove the first general graph model query lower bound for correlation clustering, where algorithms are allowed adjacency-matrix, neighbor, and degree queries. The latter two bounds are not yet tight, leaving room for sharper results.
BibTeX
@inproceedings{garg2026query,
  author = {Sumegha Garg and Songhua He and Periklis A. Papakonstantinou},
  title = {{Query Lower Bounds for Correlation Clustering Under Memory Constraints}},
  booktitle = {Itcs},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.67},
}
Figure