Hermite expansion improves clustering algorithm accuracy and analysis
Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems
Data Structures and Algorithms
Summary
Clustering is about grouping items so that those in the same group are similar. The authors study a mathematical technique used to decide these groups and improve how well it works, especially when there are multiple groups. They develop a new way using Hermite polynomials to understand and bound the chances that two items end up in the same group, making it easier to prove how good the method is. Their work leads to better algorithms for tasks like grouping data, dividing networks, and maximizing agreements in clustering.
What this means in practice
- •For data engineers: Implement improved clustering algorithms that provide better guarantees and tighter bounds for grouping large datasets using SDP relaxations.
- •For network analysts: Use enhanced Max K-Cut approximation methods to better segment networks for community detection and modularity maximization in social or communication graphs.
Authors
David García-Soriano, Atsushi Miyauchi
Abstract
The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). On the hardness side, we show that the integrality ratio of the standard SDP relaxation is at most $0.802$, and that approximation beyond that is Unique Games-hard. We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$.