Source-linked AI summary
Clustering Partially Observed Graphs via Convex Optimization
Yudong Chen, Ali Jalali, Sujay Sanghavi, Huan Xu
TL;DR
The paper addresses clustering partially observed graphs when many node pairs have unknown connectivity. It minimizes observed disagreements through convex low-rank-plus-sparse matrix decomposition and evaluates the method under the planted partition model. The analysis characterizes tradeoffs among observation probability, density gap, and cluster size, while experiments report recovery with fewer observations than spectral baselines.
Problem
The paper asks how to cluster partially observed graphs into internally dense and externally sparse groups when many node pairs are unknown.
Method
The method minimizes disagreements using convex optimization that splits the partially observed adjacency matrix into low-rank cluster structure and sparse disagreements.
Results
The method recovers underlying clusters with fewer observations than the considered spectral imputation baselines and exhibits the predicted observation–disagreement tradeoffs.
Takeaways & Limitations
The results provide sufficient recovery conditions that explicitly relate observation probability, density gap, and minimum cluster size.
Takeaways & Limitations
The tightness of the conditions on observation probability and its tradeoff with τ remains unclear in the stated regime.
Abstract
from arXiv · showhide
This paper considers the problem of clustering a partially observed unweighted graph---i.e., one where for some node pairs we know there is an edge between them, for some others we know there is no edge, and for the remaining we do not know whether or not there is an edge. We want to organize the nodes into disjoint clusters so that there is relatively dense (observed) connectivity within clusters, and sparse across clusters. We take a novel yet natural approach to this problem, by focusing on finding the clustering that minimizes the number of "disagreements"---i.e., the sum of the number of (observed) missing edges within clusters, and (observed) present edges across clusters. Our algorithm uses convex optimization; its basis is a reduction of disagreement minimization to the problem of recovering an (unknown) low-rank matrix and an (unknown) sparse matrix from their partially observed sum. We evaluate the performance of our algorithm on the classical Planted Partition/Stochastic Block Model. Our main theorem provides sufficient conditions for the success of our algorithm as a function of the minimum cluster size, edge density and observation probability; in particular, the results characterize the tradeoff between the observation probability and the edge density gap. When there are a constant number of clusters of equal size, our results are optimal up to logarithmic factors.
1. Introduction
The paper studies clustering when graph observations are incomplete, using disagreement minimization and convex optimization to recover clusters without pre-specifying their number. It situates the approach in planted-partition models and prior work, emphasizing tradeoffs among observation probability, cluster size, and density gap.
- Problem setting: Partial observation records edges, non-edges, and unknown node pairs, with most pairs often unobserved in applications.The paper motivates this setting through social networks and other domains where similarity data are expensive to obtain.
- Problem setting: The clustering objective minimizes disagreements: observed cross-cluster edges plus observed within-cluster missing edges.The formulation does not require specifying the number of clusters and reduces fully observed graphs to correlation clustering.
- Our approach: The proposed method uses convex matrix splitting to recover a low-rank ideal-cluster matrix and a sparse disagreement matrix.The algorithm either returns a disagreement-minimizing clustering or reports failure, rather than returning a sub-optimal clustering.
- Theoretical setting: The planted partition model assumes in-cluster edge probability p exceeds inter-cluster probability q and provides the main theoretical benchmark.The results are compared with prior exact-recovery requirements for minimum cluster size and density difference.
- Relation to prior work: Unlike prior approaches that impute missing observations, the paper directly handles partial observations and characterizes tradeoffs among p0, τ, and Kmin.Earlier imputation-based methods can require more observations, while the proposed analysis applies to smaller clusters in the cited comparison.
- Relation to prior work: The paper also distinguishes its entrywise partial-observation setting from work sampling rows or columns, features, or actively selected similarities.These prior studies address different observation schemes or clustering structures.
2. Main Results
The paper formulates partially observed graph clustering as observed-disagreement minimization and solves it by recovering low-rank cluster structure plus sparse disagreements through convex optimization. Under the planted partition model, the method has high-probability recovery guarantees whose tradeoffs depend on minimum cluster size, density gap, and observation probability, with matching lower bounds up to logarithmic factors in the constant-cluster regime.
- Problem formulation: The task is to find the clustering minimizing observed disagreements, consisting of present cross-cluster edges and missing within-cluster edges.The input adjacency matrix records observed edges, observed nonedges, and unknown pairs; only observed pairs contribute to the objective.
- Algorithm: The algorithm decomposes the partially observed adjacency matrix into a low-rank ideal-cluster matrix and a sparse disagreement matrix using convex optimization.For ideally clustered fully observed graphs, adding the identity produces a block-diagonal all-ones matrix whose rank equals the number of clusters.
- Performance analysis: Under the planted partition model, the original clustering is the unique optimum with probability at least 1 − cn^-10 when the theorem’s conditions on Kmin, 1−2τ, and p0 hold.Here 1−2τ lower-bounds the density gap p−q, while p0 is the observation probability.
- Performance analysis: The sufficient conditions require Kmin = ˜Ω(√n), allow vanishing observation probability when the density gap is constant, and expose a quadratic density-gap versus observation tradeoff.When 1−2τ = Θ(1), larger minimum clusters permit smaller p0; four times as many observations can support a 50% smaller density gap.
- Lower bounds: For Kmin = Θ(n), a lower bound shows that the requirements on density gap and observation probability are optimal up to logarithmic factors for any algorithm.The paper notes that tightness remains unresolved for the p0–τ tradeoff in other cluster-size regimes, although the density-gap condition is conjectured to be nearly tight.
3. Proofs
The proof shows that the convex program recovers the true clustering by certifying a unique optimum through an equivalent observation model, optimality conditions, and a constructed dual certificate.
- Proof of Theorem 2: If the convex program returns a valid clustering matrix, that solution is the disagreement-minimizing clustering.Validity means the low-rank matrix corresponds to disjoint cliques; the proof reduces the relaxed program to disagreement minimization when its solution is valid.
- Proof of Theorem 4: Theorem 4 proves recovery by showing that the true pair (B*, K*) is the unique optimum of the convex program with high probability.The proof establishes uniqueness through three steps involving an equivalent model, first-order conditions, and a dual certificate.
- Step 1: Equivalent model: Step 1 replaces the observation and disagreement process with an equivalent model that is easier to analyze when observation probability and density gap are small.The equivalent model makes the relevant random sets independent and uses random signed entries, facilitating dual-certificate construction.
- Steps 2–3: Dual certificate: Step 2 derives sub-gradient optimality conditions requiring a dual certificate W, while Step 3 constructs W to satisfy those conditions under the true-clustering assumptions.The constructed certificate certifies (B*, K*) as the unique optimum; this step extends prior matrix-splitting analyses to vanishing observation probabilities and density gaps.
- Step 3: Dual certificate: The proof constructs W recursively through a golfing-scheme variant and verifies its required inequality conditions with high probability.The certificate is initialized at W0 = 0 and updated across k0 stages, with the analysis using technical lemmas and projection operators.
4. Experimental Results
Simulations examine the algorithm across observation probability, graph size, cluster size, and disagreement probability, finding phase transitions and curve alignments consistent with the theory. A comparison also shows better performance than spectral clustering under the tested partial-observation setting.
- Observation probability and graph size: Larger p0 and n improve performance, with a success-probability phase transition predicted by Theorem 4.With τ = 0.2 and Kmin = n/4, the experiments vary p0 and n across generated planted-partition graphs.
- Observation probability and graph size: Plotting success probability against the rescaled control parameter makes curves align, matching the predicted p0–n scaling up to an extra log factor.The right pane of Figure 2 uses p0n log n as the control parameter and shows the predicted alignment.
- Other parameter settings: Across experiments varying (p0, Kmin), (τ, n), and (τ, Kmin), curves roughly align under control parameters derived from Theorem 4.Figures 3, 4, and 5 use fixed settings for n, p0, or τ while varying the remaining parameters.
- Comparison with spectral clustering: The method outperforms spectral clustering with zero or random 1/0 imputation and requires fewer observations in the tested setting.The comparison uses n = 2000, Kmin = 200, and τ = 0.1 while varying p0.
5. Conclusion
The paper presents a convex optimization method for partially observed graph clustering and establishes conditions under which it finds the disagreement-minimizing clustering. Simulations validate its effectiveness and show recovery with fewer observations than spectral clustering, while future work targets alternative sampling and sparse graphs.
- 5. Conclusion: The method reduces partially observed graph clustering to decomposing low-rank and sparse matrices via convex optimization.Under a wide range of planted-partition parameters, it is guaranteed to find the optimal disagreement-minimizing clustering.
- 5. Conclusion: Our method outperforms spectral clustering and requires fewer observations under the compared observation probabilities.The comparison uses zero and random imputation schemes for spectral clustering.
- 5. Conclusion: Simulation studies validate the method’s effectiveness and the scaling of its theoretical results.
- 5. Conclusion: Future work includes active sampling schemes and methods for sparse graphs with very few connections.
Appendix A. Technical Lemmas
The appendix develops probabilistic matrix-norm bounds used in the proof, relying on Bernstein inequalities and related estimates for sampled symmetric matrices and random operators.
- Appendix A. Technical Lemmas: The proofs repeatedly apply non-commutative or standard Bernstein inequalities to obtain high-probability bounds.
- Appendix A. Technical Lemmas: The bounds exploit the structure of the low-rank cluster matrix and control projected sampling operators on the relevant tangent space.
- Appendix A. Technical Lemmas: The technical lemmas bound operator, spectral, and infinity norms of random sampled symmetric matrices and operators.
- Appendix A. Technical Lemmas: Sampling sets are modeled with Bernoulli entries, while auxiliary random matrices may have symmetric ±1 entries.
- Appendix A. Technical Lemmas: Union bounds and sufficiently large constants complete the high-probability estimates required by the main theorem.
Appendix B. Proof of Theorem 5
The proof uses an information-theoretic argument over equal-size partitions to derive a necessary condition for recovering the planted clustering from partial observations.
- Appendix B. Proof of Theorem 5: The proof considers all partitions of n nodes into equal-size clusters and counts their number using Stirling’s approximation.
- Appendix B. Proof of Theorem 5: Fano’s inequality and mutual-information convexity relate the probability of recovering the clustering to divergences between observation distributions.
- Appendix B. Proof of Theorem 5: The KL divergence is decomposed across independent node pairs and vanishes for pairs whose latent cluster relations agree.
- Appendix B. Proof of Theorem 5: For the left-hand side of (8) to be less than 1/4, the necessary condition is p0(1 −2τ)^2 ≥ C 1.