Source-linked AI summary
Nuclear norm minimization for the planted clique and biclique problems
Brendan Ames, Stephen Vavasis
TL;DR
The paper asks how to recover maximum cliques and maximum-edge bicliques, both NP-hard, from graphs containing a planted structure obscured by diversionary edges. It formulates the problems as matrix-rank minimization and applies nuclear-norm convex optimization, establishing exact recovery in adversarial and random-edge settings.
Problem
How can maximum cliques and maximum-edge bicliques, both NP-hard problems, be recovered when diversionary edges obscure a planted structure?
Source: §1 · p. 2Method
The paper expresses the graph problems as matrix-rank minimization and relaxes them to convex optimization using the nuclear norm.
Source: §1 · p. 2Results
The analyses establish exact recovery for planted clique and biclique instances; with random edges, a planted clique of at least O(N^1/2) nodes is recoverable, matching Alon et al. and Feige and Krauthgamer.
Source: §1 · p. 2Takeaways & Limitations
The paper shows that nuclear-norm minimization can solve these graph problems in polynomial time when the input consists of a single clique or biclique plus diversionary edges.
Source: §5 · p. 19In the adversarial setting, recovery tolerates O(n^2) diversionary edges only if each non-clique vertex is adjacent to at most O(n) clique vertices; the authors say these bounds are best possible up to constants.
Source: §1 · p. 2, §3.2 · p. 13
Abstract
from arXiv · showhide
We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special cases that the input graph has a planted clique or biclique (i.e., a single large clique or biclique plus diversionary edges), our algorithm successfully provides an exact solution to the original instance. For each problem, we provide two analyses of when our algorithm succeeds. In the first analysis, the diversionary edges are placed by an adversary. In the second, they are placed at random. In the case of random edges for the planted clique problem, we obtain the same bound as Alon, Krivelevich and Sudakov as well as Feige and Krauthgamer, but we use different techniques.
1 Introduction
The paper studies maximum clique and maximum-edge biclique, both NP-hard problems, as applications of nuclear-norm relaxation for matrix-rank minimization. It analyzes exact recovery when diversionary edges are adversarial or random.
1 Introduction
- Nuclear-norm minimization relaxes matrix-rank minimization, whose rank objective counts nonzero singular values in correspondence with vector sparsity in compressive sensing.The paper notes applications of clique and biclique models in data mining.Source: §1 · pp. 1–3
- The problems are maximum clique in an undirected graph and maximum-edge biclique in a bipartite graph, and both are NP-hard.The biclique objective is to maximize the product of the two sides’ sizes.Source: §1 · p. 2
- For adversarial diversionary edges, recovery tolerates O(n^2) edges if no non-clique vertex is adjacent to more than O(n) clique vertices; analogous biclique results are established.The authors state both bounds are best possible up to constant factors.Source: §1 · p. 2
- With independently random non-clique edges, the clique result matches Alon et al. and Feige and Krauthgamer: a clique of at least O(N^1/2) nodes is recoverable.The convex optimization also certifies that the maximum clique has been found through a uniqueness result.Source: §1 · p. 2
2 Results on norms of random matrices
This section develops random-matrix results used in the paper’s analyses, including a spectral-norm probability bound for symmetric matrices and an entry adjustment that makes column sums zero.
2 Results on norms of random matrices
- The random entries take value 1 with probability p and -p/(1-p) otherwise, giving mean zero and variance p/(1-p).The entries are described as independently and identically distributed.Source: §2 · p. 3
- For the symmetric-matrix theorem, the stated probability is at least 1-exp(-c n^1/6), for some c>0 depending on σ.The paper defines the spectral norm as the maximum singular value.Source: §2 · p. 3
- Mean zero is crucial to the symmetric-matrix theorem; a distribution with nonzero mean would give spectral norm O(n).A related theorem for unsymmetric matrices is attributed to Geman.Source: §2 · p. 3
- The adjusted matrix replaces non-one entries in each column so its column sum is deterministically zero, unlike the random column sums of the original matrix.The proof bounds each f_j by 2/3 after choosing parameters so both terms in (7) are at most 1/3.Source: §2 · pp. 4, 6
3 Maximum Clique
This section formulates maximum clique as a rank-minimization problem and relaxes it using the nuclear norm. It gives conditions for exact recovery and uniqueness under adversarial or randomized diversionary edges.
3 Maximum Clique
- A clique’s adjacency matrix with loops is rank one, motivating a nuclear-norm relaxation of the NP-hard rank-minimization formulation; the constraint Xij≤1 is omitted as superfluous and unhelpful.The relaxation uses the nuclear norm, the sum of singular values, as a surrogate for rank.Source: §3 · p. 7
3.1 Optimality Conditions
- Sufficient certificate conditions make the planted rank-one matrix optimal; when ∥W∥<1 and µ>0, it is unique, and in the graph specialization the clique is uniquely maximum.The graph theorem also states that the planted matrix is optimal under the certificate conditions.Source: §3.1 · pp. 8, 11
3.2 The Adversarial Case
- With a planted clique of size n, the adversarial analysis shows that up to O(n^2) added edges can preserve its status as the unique maximum clique under certain conditions.The analysis considers graphs with at most r extra edges and limits each outside vertex to at most δn neighbors in the planted clique.Source: §3.2 · pp. 12–13
- With adversarial edges, the planted clique remains the unique maximum clique even with O(n^2) edges outside it.The bounds are best possible up to constants: the adversary must be limited to const · n^2 edges for const < 1/2, and each nonclique vertex may be adjacent to at most const · n clique vertices.Source: §3.2 · p. 13
3.3 The Randomized Case
- When n = Ω(N^1/2), the randomized construction yields the planted clique as the unique maximum clique and unique solution of (12) with probability tending exponentially to 1.The proof establishes the certificate condition ∥W∥ < 1 with probability tending exponentially to 1 and also verifies pj < n for vertices outside the planted clique.Source: §3.3 · pp. 14–15
4 Maximum Edge Biclique
The maximum-edge biclique problem is expressed as rank minimization and relaxed with the nuclear norm; KKT conditions certify when the planted biclique is optimal or uniquely optimal. The paper analyzes adversarial and independently random diversionary edges.
4 Maximum Edge Biclique
- The biclique adjacency matrix is rank one, and replacing rank minimization with the nuclear norm yields a convex optimization problem.KKT conditions provide criteria for when the planted adjacency matrix is optimal; strict certificate conditions give uniqueness.Source: §4 · pp. 15–16
4.1 The Adversarial Case
- Under the stated per-vertex adjacency conditions, up to O(mn) adversarial diversionary edges preserve the planted biclique's optimality and uniqueness.The graph has at most r edges outside the biclique; outside vertices have bounded adjacency into each planted side.Source: §4.1 · pp. 17–18
4.2 The Random Case
- With n≥αN, the planted biclique is the unique solution to the convex relaxation with probability tending exponentially to 1 as N→∞.The threshold constant depends on p, y, and z.Source: §4.2 · p. 18
- In the random case, remaining potential edges are added independently with probability p, and the theorem gives exact recovery of the planted biclique.The result applies to the graph construction specified for the random analysis.Source: §4.2 · p. 18
5 Conclusions
Nuclear norm minimization solves the planted maximum clique and maximum-edge biclique problems in polynomial time under the stated graph structure.
5 Conclusions
- For graphs consisting of a single clique or biclique plus diversionary edges, nuclear norm minimization solves the maximum clique and maximum biclique problems in polynomial time.The paper suggests extending this approach to other NP-hard problems.Source: §5 · p. 19