In the graph clustering problem with a planted solution, the input is a graph on \(n\) vertices partitioned into \(k\) clusters, and the task is to infer the clusters from graph structure. A standard assumption is that clusters induce well-connected subgraphs (i.e. \(\Omega(1)\)-expanders), and connections between clusters are sparse (i.e. clusters form \(\epsilon\)-sparse cuts). Such a graph defines the clustering uniquely up to \(\approx \epsilon\) misclassification rate, and efficient algorithms for achieving this rate are known. While this vanilla version of graph clustering is extremely well studied, in the practice of graph analysis vertices of the graph are typically equipped with labels, or features, that provide additional information on cluster ids of the vertices. For example, each vertex could be equipped with a cluster label that is corrupted independently with probability \(\delta\). Using either of the two sources of information separately leads to misclassification rate \(\min \{\epsilon, \delta\}\), but can one combine the two to achieve misclassification rate \(\approx \epsilon\delta\)?

This paper studies complete k-Constraint Satisfaction Problems (CSPs), where an n-variable instance has exactly one nontrivial constraint for each subset of k variables, i.e., it has binom(n,k) constraints. A recent work started a systematic study of complete k-CSPs [Anand, Lee, Sharma, SODA'25], and showed a quasi-polynomial time algorithm that decides if there is an assignment satisfying all the constraints of any complete Boolean-alphabet k-CSP, algorithmically separating complete instances from dense instances. The tractability of this decision problem is necessary for any nontrivial (multiplicative) approximation for the minimization version, whose goal is to minimize the number of violated constraints. The same paper raised the question of whether it is possible to obtain nontrivial approximation algorithms for complete Min-k-CSPs with k ≥ 3. In this work, we make progress in this direction and show a quasi-polynomial time polylog(n)-approximation to Min-NAE-3-SAT on complete instances, which asks to minimize the number of 3-clauses where all the three literals equal the same bit. To the best of our knowledge, this is the first known example of a CSP whose decision version is NP-Hard in general (and dense) instances while admitting a polylog(n)-approximation in complete instances. Our algorithm presents a new iterative framework for rounding a solution from the Sherali-Adams hierarchy, where each iteration interleaves the two well-known rounding tools: the conditioning procedure, in order to "almost fix" many variables, and the thresholding procedure, in order to "completely fix" them. Finally, we improve the running time of the decision algorithms of Anand, Lee, and Sharma and show a simple algorithm that decides any complete Boolean-alphabet k-CSP in polynomial time.

In this paper we study the problem of finding (ϵ, ϕ)-expander decompositions of a graph in the streaming model, in particular for dynamic streams of edge insertions and deletions. The goal is to partition the vertex set so that every component induces a ϕ-expander, while the number of inter-cluster edges is only an ϵ fraction of the total volume. It was recently shown that there exists a simple algorithm to construct a (O(ϕlog n), ϕ)-expander decomposition of an n-vertex graph using Oe(n/ϕ2) bits of space [Filtser, Kapralov, Makarov, ITCS’23]. This result calls for understanding the extent to which a dependence in space on the sparsity parameter ϕ is inherent. We move towards answering this question on two fronts. We prove that a (O(ϕlog n), ϕ)-expander decomposition can be found using Oe(n) space, for every ϕ. At the core of our result is the first streaming algorithm for computing boundary-linked expander decompositions, a recently introduced strengthening of the classical notion [Goranci et al., SODA’21]. The key advantage is that a classical sparsifier [Fung et al., STOC’11], with size independent of ϕ, preserves the cuts inside the clusters of a boundary-linked expander decomposition within a multiplicative error. Notable algorithmic applications use sequences of expander decompositions, in particular one often repeatedly computes a decomposition of the subgraph induced by the inter-cluster edges (e.g., the seminal work of Spielman and Teng on spectral sparsifiers [Spielman, Teng, SIAM Journal of Computing 40(4)], or the recent maximum flow breakthrough [Chen et al., FOCS’22], among others). We prove that any streaming algorithm that computes a sequence of (O(ϕlog n), ϕ)-expander decompositions requires Ω(e n/ϕ) bits of space, even in insertion only streams.

In a graph bisection problem, we are given a graph $G$ with two equally-sized unlabeled communities, and the goal is to recover the vertices in these communities. A popular heuristic, known as spectral clustering, is to output an estimated community assignment based on the eigenvector corresponding to the second-smallest eigenvalue of the Laplacian of $G$. Spectral algorithms can be shown to provably recover the cluster structure for graphs generated from probabilistic models, such as the Stochastic Block Model (SBM). However, spectral clustering is known to be non-robust to model mis-specification. Techniques based on semidefinite programming have been shown to be more robust, but they incur significant computational overheads. In this work, we study the robustness of spectral algorithms against semirandom adversaries. Informally, a semirandom adversary is allowed to ``helpfully'' change the specification of the model in a way that is consistent with the ground-truth solution. Our semirandom adversaries in particular are allowed to add edges inside clusters or increase the probability that an edge appears inside a cluster. Semirandom adversaries are a useful tool to determine the extent to which an algorithm has overfit to statistical assumptions on the input. On the positive side, we identify a wide range of semirandom adversaries under which spectral bisection using the _unnormalized_ Laplacian is strongly consistent, i.e., it exactly recovers the planted partitioning. On the negative side, we show that in many of these settings, _normalized_ spectral bisection outputs a partitioning that makes a classification mistake on a constant fraction of the vertices. Finally, we demonstrate numerical experiments that complement our theoretical findings.