Source-linked AI summary
A simple SVD algorithm for finding hidden partitions
Van Vu
TL;DR
Recovering hidden partitions in random graphs encompasses problems such as hidden clique, coloring, and bipartition, and McSherry’s work left open a simpler algorithm. This paper proposes an SVD-based approach and reports recovery guarantees for the general setting and these subproblems under stated conditions.
Problem
The paper seeks a simpler algorithm for recovering clusters in a random graph generated with cluster-dependent edge probabilities, a problem that includes hidden clique, coloring, and bipartition.
Source: §1 · pp. 1–2Method
The approach projects adjacency-matrix columns onto the subspace spanned by the first k left singular vectors, then clusters the projected points.
Source: §1 · p. 2Results
SVD II correctly clusters Y2 with probability 1−o(n−1) under one of Theorem 2’s stated conditions and has corollaries for hidden clique, coloring, and bipartition.
Source: §1 · pp. 3–4Takeaways & Limitations
The paper answers McSherry’s request for a simpler hidden-partition algorithm with an SVD-based alternative.
Source: §1 · p. 2The stated variance lower bound σ² ≥ C log n/n is optimal up to C; below log n/n, many isolated vertices may be assigned to any cluster.
Source: §1 · p. 4
Abstract
from arXiv · showhide
Finding a hidden partition in a random environment is a general and important problem, which contains as subproblems many famous questions, such as finding a hidden clique, finding a hidden coloring, finding a hidden bipartition etc. In this paper, we provide a simple SVD algorithm for this purpose, answering a question of McSherry. This algorithm is very easy to implement and works for sparse graphs with optimal density.
1. The problem and a new algorithm
The paper addresses McSherry’s request for a simpler algorithm for recovering hidden clusters in random graphs. It proposes projecting graph columns onto leading singular-vector subspaces and clustering the projected points.
1. The problem and a new algorithm
- The hidden partition problem asks for recovery of vertex clusters from a random graph whose edge probabilities depend on the clusters.It includes hidden clique, hidden bisection, hidden coloring, and clustering as special cases [11] [12].Source: §1 · p. 1
- The proposed SVD approach projects the input adjacency-matrix columns onto the subspace spanned by the first k left singular vectors, then clusters the projected points.The paper identifies this as a natural choice of subspace for a geometric representation.Source: §1 · pp. 2–3
- SVD II adds random partitions to reduce correlation, and its guarantee directly recovers a partition of Y2 rather than all of X.The paper describes repeating the procedure on random subsets and merging clusters that intersect as one way to extend recovery to X.Source: §1 · p. 3
- SVD II’s main projection step is a routine SVD operation available in standard mathematical packages..Source: §1 · p. 3
- SVD II correctly clusters Y2 with probability 1−o(n−1) when one of Theorem 2’s two stated conditions holds.The theorem also states assumptions on σ², the minimum cluster size s, and k.Source: §1 · p. 3
- The stated lower bound σ² ≥ C log n/n is optimal up to the constant C; below log n/n, many isolated vertices can be assigned to any cluster..Source: §1 · p. 4
- The corollaries report recovery results for hidden clique, hidden k-coloring, and hidden bipartition under their stated parameter conditions.The coloring guarantee has probability 1−O(n−1), while the bipartition guarantee has probability 1−o(n−1).Source: §1 · pp. 4–5
- The paper notes that an approximate algorithm can replace p^1/4 in a denominator with the better term p^1/2.The cited improvement is in Corollary 11.Source: §1 · p. 5
2. Technical lemmas
The technical lemmas bound random projections and matrix perturbations used in the analysis. Together, they provide tools for controlling the SVD-based method under stated variance and singular-value conditions.
Lemma 7: Projection of a Random Vector.
- Lemma 7 bounds the projection length of a mean-zero random vector onto a subspace, with an additional condition involving the subspace basis vectors’ infinity norms.The vector coordinates are independent and have variance at most σ^2 ≤ 1.Source: §2 · p. 5
Lemma 8: Norm of a Random Matrix.
- Lemma 8 gives a norm bound for a symmetric random matrix with independent centered upper-diagonal entries when σ^2 ≥ C0 log n/n.The entries are Bernoulli deviations from probabilities p_ij.Source: §2 · p. 5
Lemma 9: Perturbation Bound.
- Lemma 9 supplies a perturbation bound for matrices when the gap between their kth and next singular values is positive.The passage identifies this result as the Davis-Kahan-Wedin theorem [5, 10, 28, 17].Source: §2 · p. 5
3. Proof of Theorems 2
The proof controls how random sampling and graph noise affect the SVD projection, then uses these bounds to establish recovery under the theorem’s conditions. It also compares the relevant singular values of the full and sampled matrices.
Proof of Theorem 2
- A direct perturbation bound is too crude in the general case, so the proof uses it alongside bounds on the random perturbation and projected vectors.The sampled matrix is written as  = A + E, with independent centered entries in E.Source: §3 · p. 6
- The proof targets projection error below Δ/12, using cluster separation of at least Δ/3 when each cluster has at least C log n vertices.The argument decomposes the error into noise and projection terms; the random partition gives the stated cluster-size condition with high probability.Source: §3 · p. 6
- The algorithm succeeds with probability at least 1 − o(n^-1), establishing the theorem’s first part concerning Condition 1.Source: §3 · p. 7
- The proof compares the kth singular values of P, its sampled versions, and A, obtaining λ_k(P) ≤ 2λ_k(Ṕ).The comparison proceeds through intermediate matrices, with a factor-of-two loss at each stage.Source: §3 · pp. 7–8
4. Variants
The variants address unknown dimension or density information and allow approximate recovery. For hidden bipartition, a degree-based correction turns the approximation algorithm into a full-recovery guarantee under Corollary 11’s conditions.
4.1. Dimension and Density.
- When rank A = l < k, projecting onto Â_l instead of Â_k leaves the rest of the algorithm and analysis unchanged.If k and l are unknown, SVD II can use the essential rank: the largest index whose singular value is at least C3σ√n.Source: §4.1 · p. 8
- When σ is unknown, O(log n) trials with successively doubled σ estimates can be checked using inter-cluster degree densities.The passage says σ is the only information needed when using essential dimension.Source: §4.1 · p. 8
4.2. An approximate Solution.
- If σ^2 ≥ C log n, the SVD II projection produces an (1−ε)-perfect representation with probability 1−o(n^-1.An ε-perfect representation has at least (1−ε)|X_i| points from each cluster within distance r of its representative, with representatives at least 4r apart.Source: §4.2 · p. 9
- Under Corollary 11’s conditions, the approximation algorithm with correction recovers the hidden bipartition with probability 1−o(n^-1).The correction selects the n/2 vertices with the largest degrees.Source: §4.2 · p. 9
Appendix A. Proof of Lemma 7
Appendix A bounds the mean of the projected random vector using concentration, with the key estimate μ ≤ σd^1/2 + O(1). It also derives a tail bound for a weighted sum of independent mean-zero variables under coefficient and moment constraints.
Appendix A. Proof of Lemma 7
- For a 1-Lipschitz convex Π_H(X), the proof applies Talagrand’s inequality and then uses Markov’s inequality.The subsequent optimization sets T = 4α log n and t = α^-1, giving an exponent at most −3 log n.Source: Appendix A · pp. 10–11
- μ ≤ σd^1/2 + O(1) bounds the mean of Π_H(X), using a concentration inequality and an upper bound on μ.The proof notes that μ is unknown, then combines the concentration inequality to obtain the stated bound.Source: Appendix A · p. 10
- Claim 12 considers a weighted sum of independent mean-zero variables with coefficients bounded by α and moments E|ξ_i|^k ≤ σ^2 for k ≥ 2.Its proof takes 0 < t ≤ α^-1 and uses the coefficient and moment bounds.Source: Appendix A · p. 10