On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Introduction

Consider the following detection problem. One is given a symmetric matrix $\mathbf{X}=\mathbf{X}(n)$ of dimension $n$, such that the ${n\choose 2}+n$ entries $(\mathbf{X}_{i,j})_{i\leq j}$ are mutually independent random variables. Given (a realization of) $\mathbf{X}$ one would like to distinguish between the hypothesis that all random variables $\mathbf{X}_{i,j}$ have the same distribution $F_{0}$ to the hypothesis where there is a set $U\subseteq[n]$ so that all random variables in the submatrix $\mathbf{X}_{U}:=(\mathbf{X}_{s,t}:s,t\in U)$ have a distribution $F_{1}$ which is different from the distribution of all other elements in $\mathbf{X}$ which are still distributed as $F_{0}$.

The same problem was recently studied in and, for the of the asymmetric case (where no symmetry assumption is imposed on the independent entries of $\mathbf{X}$), in . We refer to Section 6 for further discussion of the related literature. An intriguing outcome of these works is that, while the two hypothesis are statistically distinguishable as soon as $L\geq C\log n$ (for $C$ a sufficiently large constant) , practical algorithms require significantly larger $L$. This motivates the study of restricted classes of tests. In this paper we study the class of spectral (or eigenvalue-based) tests detecting the signal. Our proof technique naturally allow to consider two further generalizations of this problem that are of independent interests. We briefly summarize our results below.

The Gaussian hidden clique problem. This is a special case of the above hypothesis testing setting, whereby $F_{0}={\sf N}(0,1)$ and $F_{1}={\sf N}(1,1)$ (entries on the diagonal are defined slightly differently for simplifying calculations). Here and below ${\sf N}(m,\sigma^{2})$ denote the Gaussian distribution of mean $m$ and variance $\sigma^{2}$. Equivalently, let $\mathbf{Z}$ be a random matrix from the Gaussian Orthogonal Ensemble (GOE) i.e. $\mathbf{Z}_{ij}\sim{\sf N}(0,1/n)$ independently for $i<j$, and $\mathbf{Z}_{ii}\sim{\sf N}(0,2/n)$. Then, under hypothesis $H_{1,L}$ we have $\mathbf{X}=n^{-1/2}{\mathbf{1}}_{U}{\mathbf{1}}_{U}^{{\sf T}}+\mathbf{Z}$ (${\mathbf{1}}_{U}$ being the indicator vector on $U$, and $|U|=L$), and under hypothesis $H_{0}$, $\mathbf{X}=\mathbf{Z}$ (the factor $n$ in the normalization is for technical convenience).

We then consider the following restricted hypothesis testing question. Let $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}$ be the ordered eigenvalues of $\mathbf{X}$. Is there a test that depends only on $\lambda_{1},\dots,\lambda_{n}$ and that distinguishes $H_{0}$ from $H_{1,L}$ ‘reliably,’ i.e. with error probability converging to as $n\to\infty$? Notice that the eigenvalues distribution does not depend on $U$ as long as this is independent from the noise $\mathbf{Z}$. We can therefore think of $U$ as fixed for this question.

If $L\geq(1+\varepsilon)\sqrt{n}$ then implies that a simple test checking whether $\lambda_{1}\geq 2+\delta$ for some $\delta=\delta(\varepsilon)>0$ is reliable. We prove that this result is tight, in the sense that no spectral test is reliable for $L\leq(1-\varepsilon)\sqrt{n}$.

Again, this problem (and a closely related asymmetric version ) has been studied in the literature, and it follows from that a reliable test exists for $\beta\geq 1+\varepsilon$. We provide a simple proof (based on the second moment method) that no test is reliable for $\beta<1+\varepsilon$.

Rank-one tensors in Gaussian noise. It turns our that the same proof applies to an even more general problem: detecting a rank-one signal in a noisy tensor. We carry out our analysis in this more general setting for two reasons. First, we think that this clarifies the what aspects of the model are important for our proof technique to apply. Second, the problem estimating tensors from noisy data has attracted significant interest recently within the machine learning community .

Main result for spectral detection

Let $\mathbf{Z}$ be a GOE matrix as defined in the previous section. Equivalently if $\mathbf{G}$ is an (asymmetric) matrix with i.i.d. entries $\mathbf{G}_{i,j}\sim{\sf N}(0,1)$,

For a deterministic sequence of vectors $\mathbf{v}(n)$, $\|\mathbf{v}(n)\|_{2}=1$, we consider the two hypotheses

A special example is provided by the Gaussian hidden clique problem in which case $\beta=L/\sqrt{n}$ and $\mathbf{v}={\mathbf{1}}_{U}/\sqrt{L}$ for some set $U\subseteq[n]$, $|U|=L$,

Observe that the distribution of eigenvalues of $\mathbf{X}$, under either alternative, is invariant to the choice of the vector $\mathbf{v}$ (or subset $U$), as long as the norm of $\mathbf{v}$ is kept fixed. Therefore, any successful spectral algorithm will distinguish between $H_{0}$ and $H_{1,\beta}$ but not give any information on the vector $\mathbf{v}$ (or subset $U$, in the case of $H_{1,L}$).

We let $Q_{0}=Q_{0}(n)$ (respectively, $Q_{1}=Q_{1}(n)$) denote the distribution of the eigenvalues of $\mathbf{X}$ under $H_{0}$ (respectively $H_{1}=H_{1,\beta}$ or $H_{1,L}$).

A spectral statistical test for distinguishing between $H_{0}$ and $H_{1}$ (or simply a spectral test) is a measurable map $T_{n}:(\lambda_{1},\ldots,\lambda_{n})\mapsto\{0,1\}$. To formulate precisely what we mean by the word distinguish, we introduce the following notion.

Note that contiguity is not in general a symmetric relation.

In the context of the spectral statistical tests described above, the sequences $A_{n}$ in Definition 1 (with $P_{n}=Q_{0}(n)$ and $Q_{n}=Q_{1}(n)$) can be put in correspondence with spectral statistical tests $T_{n}$ by taking $A_{n}=\{(\lambda_{1},\ldots,\lambda_{n}):T_{n}(\lambda_{1},\ldots,\lambda_{n})=0\}$. We will thus say that $H_{1}$ is spectrally contiguous with respect to $H_{0}$ if $Q_{n}$ is contiguous with respect to $P_{n}$.

Our main result on the Gaussian hidden clique problem is the following.

For any sequence $L=L(n)$ satisfying $\limsup_{n\to\infty}L(n)/\sqrt{n}<1$, the hypotheses $H_{1,L}$ are spectrally contiguous with respect to $H_{0}$.

Equivalently for any sequence of vectors $\mathbf{v}(n)$, and any $\beta=\beta(n)$ satisfying $\limsup_{n\to\infty}\beta(n)<1$, the hypotheses $H_{1,\beta}$ are spectrally contiguous with respect to $H_{0}$.

Finally Theorem 1 provides an example of two family of distributions $H_{0}$ and $H_{1,L}$ such that the total variation distance between $H_{0}$ and $H_{1,L}$ is $1-o_{n}(1)$ whereas $H_{0}$ and $H_{1,L}$ are spectrally contiguous.

Contiguity is related to a notion of uniform absolute continuity of measures. Recall that a probability measure $\mu$ on a measure space is absolutely continuous with respect to another probability measure $\nu$ if for every measurable set $A$, $\nu(A)=0$ implies that $\mu(A)=0$, in which case there exists a $\nu$-integrable, non-negative function $f\equiv\frac{{\rm d}\mu}{{\rm d}\nu}$ (the Radon-Nikodym derivative of $\mu$ with respect to $\nu$), so that $\mu(A)=\int_{A}f\,{\rm d}\nu$ for every measurable set $A$. We then have the following known useful fact, which will be the basis for proving contiguity, and whose proof is given for completeness.

2 Method and structure of the paper

Consider problem (2). We use the fact that the law of the eigenvalues under both $H_{0}$ and $H_{1,\beta}$ are invariant under conjugations by a orthogonal matrix. Once we conjugate matrices sampled under the hypothesis $H_{1,\beta}$ by an independent orthogonal matrix sampled according to the Haar distribution, we get a matrix distributed as

The structure of the paper is as follows. In the next section, we define formally the detection problem for a symmetric tensor of order $k\geq 2$. We show the existence of a threshold under which detection is not possible (Theorem 3), and show how Theorem 1 follows from this. Section 4 is devoted to the proof of Theorem 3, and concludes with some additional remarks and consequences of Theorem 3. Section 5 treats the case of asymmetric Gaussian tensors. Finally, Section 6 is devoted to a description of the relation between the Gaussian hidden clique problem and hidden clique problem in computer science, and related literature.

A symmetric tensor model and a reduction

Exploiting rotational invariance, we will reduce the spectral detection problem to a detection problem involving a standard detection problem between random matrices. Since the latter generalizes to a tensor setup, we first introduce a general Gaussian hypothesis testing for $k$-tensors, which is of independent interest. We then explain how the spectral detection problem reduces to the special case of $k=2$.

We define the Frobenius (Euclidean) norm of a tensor $\mathbf{X}$ by $\|\mathbf{X}\|_{F}=\sqrt{\langle\mathbf{X},\mathbf{X}\rangle}$, and its operator norm by

For a permutation $\pi\in\mathfrak{S}_{k}$, we will denote by $\mathbf{X}^{\pi}$ the tensor with permuted indices $\mathbf{X}^{\pi}_{i_{1},\cdots,i_{k}}=\mathbf{X}_{\pi(i_{1}),\cdots,\pi(i_{k})}$. We call the tensor $\mathbf{X}$ symmetric if, for any permutation $\pi\in\mathfrak{S}_{k}$, $\mathbf{X}^{\pi}=\mathbf{X}$. It is proved that, for symmetric tensors, for symmetric tensors we have the equivalent representation

2 The symmetric tensor model and main result

Note that the subset of entries with unequal indices form an i.i.d. collection $\{\mathbf{Z}_{i_{1},i_{2},\dots,i_{k}}\}_{i_{1}<\dots<i_{k}}\sim{\sf N}(0,2/(n(k!)))$.

Assume $\beta<\beta^{{\rm 2nd}}_{k}$. Then, for any $k\geq 3$, we have

The notation $\beta^{{\rm 2nd}}_{k}$ refers to the fact that this is the threshold for the second moment method to work.

3 Reduction of spectral detection to the symmetric tensor model, k=2𝑘2k=2, and proof of Theorem 1

Recall that in the setup of Theorem 1, $Q_{0,n}$ is the law of the eigenvalues of $\mathbf{X}$ under $H_{0}$ and $Q_{1,n}$ is the law of the eigenvalues of $\mathbf{X}$ under $H_{1,L}$. Then $Q_{1,n}$ is invariant by conjugation of orthogonal matrices. Therefore, the detection problem is not changed if we replace $\mathbf{X}=n^{-1/2}{\mathbf{1}}_{U}{\mathbf{1}}_{U}^{{\sf T}}+\mathbf{Z}$ by

where $\mathbf{R}\in O(n)$ is an orthogonal matrix sampled according to the Haar measure. A direct calculations yields

where $\mathbf{u}$ is uniform on the $n$ dimensional sphere, $\beta=L/\sqrt{n}$, and $\widetilde{\mathbf{Z}}$ is a GOE matrix (with off-diagonal entries of variance $1/n$). Furthermore, $\mathbf{u}$ and $\widetilde{\mathbf{Z}}$ are independent of one another.

$(a)$ Let $\mathcal{F}$ be the $\sigma$-algebra generated by all rotation-invariant events, and let $\mathcal{G}$ be the $\sigma$-algebra generated by the ordered eigenvalues. Then $\mathcal{F}=\mathcal{G}$.

where $\mathcal{B}$ is the Borel $\sigma$-algebra in $\Sigma^{n}:=\{\lambda_{1}\geq\lambda_{2}\ldots\geq\lambda_{n}\}$. ∎

Remark: The first inequality in (19) (and hence the inequality in point $(b)$ of the statement) is actually an equality, but we will not use this fact.

In view of Lemma 4, Theorem 1 is an immediate consequence of Theorem 3.

Proof of Theorem 3

The proof uses the following large deviations lemma, which follows, for instance, from [13, Proposition 2.3].

where in the first step we used (13) and in the last step, we used rotational invariance.

Using Lemma 5, for any $-1\leq a<b\leq 1$,

It follows from the definition of $\beta^{{\rm 2nd}}_{k}$ that $\max_{|q|\geq\varepsilon}F_{\beta}(q)<0$ for any $\varepsilon>0$. Hence

for some $c(\varepsilon)>0$ and all $n$ large enough. Next notice that, under $\mu_{n}$, $\langle\mathbf{v},{\mathbf{e}}_{1}\rangle\stackrel{{\scriptstyle{\rm d}}}{{=}}G/(G^{2}+Z_{n-1})^{1/2}$ where $G\sim{\sf N}(0,1)$ and $Z_{n-1}$ is a $\chi^{2}$ with $n-1$ degrees of freedom independent of $G$. Then, letting $Z_{n}\equiv G^{2}+Z_{n-1}$ (a $\chi^{2}$ with $n$ degrees of freedom)

For $k=2$, the argument is independent of $n$ and can be integrated immediately, yielding (after taking the limit $\delta\to 0$)

(Indeed, the above calculation implies that the limit exists and is given by the right-hand side.)

The proof is completed by invoking Lemma 2. ∎

Threshold values. In the table below we report the numerical values of $\beta^{{\rm 2nd}}_{k}$ for a few values of $k$. The exact value $\beta^{{\rm 2nd}}_{k}=1$ for the matrix case $k=2$ follows from $\log(1-q^{2})\leq-q^{2}$.

Also, it is not difficult to derive the asymptotics $\beta^{{\rm 2nd}}_{k}=\sqrt{\log(k/2)}+o_{k}(1)$ for large $k$.

(Here $\Phi(x)=\int_{-\infty}^{x}e^{-z^{2}/2}{\rm d}z/\sqrt{2\pi}$ is the Gaussian distribution function.) The same phenomenon for rectangular matrices ($k=2$) is discussed in detail in .

Asymmetric tensor model

In particular, all entries are i.i.d. $\mathbf{Z}_{i_{1},\dots,i_{k}}\sim{\sf N}(0,1/n)$. With this normalization, we have of course

For $k\geq 2$, let $\lambda^{{\rm 2nd}}_{k}\equiv(k/2)^{1/2}\beta^{{\rm 2nd}}_{k}$, i.e.

Assume $\lambda<\lambda^{{\rm 2nd}}_{k}$. Then, for any $k\geq 3$, we have

Here we introduced the notation $\mu^{\otimes k}_{n}({\rm d}\mathbf{v})=\mu_{n}({\rm d}\mathbf{v}_{1})\cdots\mu_{n}({\rm d}\mathbf{v}_{k})$ Proceeding as in the proof of Eq. (22), we get

Invoking again Lemma 5, we obtain that for any open set $J\in^{k}$

The key observation is that, for $\lambda<\lambda^{{\rm 2nd}}_{k}$, we have $\max_{{\mathbf{q}}\in^{k}}G_{\lambda}({\mathbf{q}})=0$, with the maximum being uniquely achieved at ${\mathbf{q}}=0$. Once this claim is proved, we can restrict the integral (39) to a neighborhood of $(\langle\mathbf{v}_{1},{\mathbf{e}}_{1}\rangle,\cdots,\langle\mathbf{v}_{k},{\mathbf{e}}_{1}\rangle)=0$ and obtain by an argument completely analogous to the symmetric case

To prove the above claim, and hence complete the proof, note that: ${\mathbf{q}}=0$ is a local maximum of $G_{\lambda}({\mathbf{q}})$; $G_{\lambda}(|q_{1}|,\dots,|q_{k}|)\geq G_{\lambda}(q_{1},\dots,q_{k})$; $G_{\lambda}({\mathbf{q}})\to-\infty$ if $\|{\mathbf{q}}\|_{\infty}\to 1$. It is therefore sufficient to prove that any other local maximum ${\mathbf{q}}_{*}\in[0,1)^{k}\setminus\{0\}$ has $G_{\lambda}({\mathbf{q}}_{*})<0$. The stationarity condition of $G_{\lambda}$ reads

since $x\mapsto x^{2}/(1-x^{2})$ is strictly monotone increasing on $(0,1]$, we deduce that $q_{1}=q_{2}=\dots=q_{k}$. It is therefore sufficient to check $G_{\lambda}(q,q,\dots,q)<0$ for all $q\in(0,1)$. This is guaranteed by $\lambda<\lambda^{{\rm 2nd}}_{k}$. ∎

Related work

Detection problems with similar flavor to the Gaussian hidden clique problem have been studied over the years in several fields including computer science, physics and statistics. Typically, in such problems there is “planted” object with special properties along with random noise which makes the detection of the planted object a nontrivial task. In the classical $G(n,1/2)$ planted clique problem, the computational problem is to find the planted clique (of cardinality $k$) efficiently (e.g., in polynomial time) where we assume the location of the planted clique is hidden and is not part of the input. There are several algorithms that recover the planted clique in polynomial time when $k=C\sqrt{n}$ where $C>0$ is a constant independent of $n$ . In it is proven that a planted clique can be recovered in time $O(n^{2}\log(n))$, whenever $C=e^{-1/2}+\epsilon$. The work of demonstrates that it is possible to find a planted clique of size $c\sqrt{n}$ in time $n^{O(\log(1/c))}$. Despite significant effort, no polynomial time algorithm for this problem is known when $k=o(\sqrt{n}).$ In the decision version of the planted clique problem, one seeks an efficient algorithm that distinguishes between a random graph distributed as $G(n,1/2)$ or a random graph containing a planted clique of size $k\geq(2+\delta)\log n$ (for $\delta>0$; the natural threshold for the problem is the size of the largest clique in a random sample of $G(n,1/2)$, which is asymptotic to $2\log n$ ). No polynomial time algorithm is known for this decision problem if $k=o(\sqrt{n})$. There are several hardness results for computational problems in game theory (see also ) and statistics which are based on the alleged hardness of the the problem of distinguishing between a random graph distributed as $G(n,1/2)$ to a random graph with a planted clique of size $k(n)$ (with $(2+\delta)\log n<k(n)\ll\sqrt{n}$).

As another example, consider the following setting introduced by (see also ): one is given a realization of a $n$-dimensional Gaussian vector $\mathbf{x}:=(\mathbf{x}_{1},..,\mathbf{x}_{n})$ with i.i.d. entries. The goal is to distinguish between the following two hypotheses. Under the first hypothesis, all entries in $\mathbf{x}$ are i.i.d. standard normals. Under the second hypothesis, one is given a family of subsets $C:=\{S_{1},...,S_{m}\}$ such that for every $1\leq k\leq m,S_{k}\subseteq\{1,...,n\}$ and there exists an $i\in\{1,\ldots,m\}$ such that, for any $\alpha\in S_{i}$, $\mathbf{x}_{\alpha}$ is a Gaussian random variable with mean $\mu>0$ and unit variance whereas for every $\alpha\notin S_{i}$, $\mathbf{x}_{\alpha}$ is standard normal. (The second hypothesis does not specify the index $i$, only its existence). The main question is how large $\mu$ must be such that one can reliably distinguish between these two hypotheses. In , one considers two situations. In the first, $\alpha$ are vertices in a two dimensional grid of side length $n$ and the family $C$ is the set of all directed (i.e., with north or east steps only) paths of length $l$, starting from the bottom-left corner. In the second situation treated in , the $\alpha$s correspond to the vertices of a binary tree, and again the family $C$ consists of loopless paths starting at the root. In , both the min-max and Bayesian (with uniform choice of $i$ in $C$) setups are considered. Other choices of $C$ are considered in : the family of all subsets of size $k$, the set of all perfect matching in a given graph and other examples. These detection problems have practical applications-see for details.

The Gaussian hidden clique problem is related to various applications in statistics and computational biology . That detection is statistically possible when $L\gg\log n$ was established in (the authors consider the case where all diagonal elements are zero, but since the detection algorithm can simply ignore the diagonal elements, their results apply to our setting as well). Similar results for the asymmetric case were obtained by . In terms of polynomial time detection, show that detection is possible when $L=\Theta(\sqrt{n})$ for the symmetric cases. As noted, no polynomial time algorithm is known for the Gaussian hidden clique problem when $k=o(\sqrt{n})$. In it was hypothesized that the Gaussian hidden clique problem should be difficult when $L\ll\sqrt{n}$. More specifically [1, Pg. 16, second paragraph] comment that “it seems likely that designing an efficient test in the normal setting will prove as difficult as it proved for planted cliques”. Supporting evidence for this assertion was provided in , who proved that distinguishing between a planted model similar to the Gaussian planted clique model studied in our work and the random case (with entries being independent standard Gaussians) is at least as hard as distinguishing between a graph containing a planted clique and a graph distributed the random graph $G(n,1/2)$.

There is a large body of work in RMT that addresses the effect of low rank perturbations on various properties the spectrum and eigenvectors of Wigner matrices (e.g., ), mostly in studying the almost sure limits and limit distributions of extremal eigenvalues and eigenvectors.

Conclusion

In this work we considered detection problems for GOE matrices perturbed by a deterministic rank $1$ matrix, including the Gaussian hidden clique problem. We have established that spectral methods stop being effective when the norm of the perturbation drops below a threshold, which translates in the Gaussian hidden clique problem to the size of the planted submatrix being smaller than $(1-\epsilon)\sqrt{n}$. In identifying this threshold we have also addressed detectability issues in rank-one perturbations of matrices and tensors which might be of independent interest.

There are several open problems that arise from the current work. First, in the context of the Gaussian hidden clique problem, it would be interesting to provide an efficient algorithm for finding a planted submatrix when $L=o(\sqrt{n})$ or rule out certain algorithmic (non spectral) approaches for this problem. One direction is to study optimization methods such as semidefinite programming and various types of hierarchies (e.g., Lasserre, Sherali-Adams) in dealing with the hidden clique problem for $L=o(\sqrt{n})$.

A natural question is whether one can use the spectrum in order to distinguish between a graph distributed as $G(n,1/2)$ and a random graph with a planted clique of size $L<(1-\epsilon)\sqrt{n}$. Proving that one can or cannot distinguish between these cases using eigenvalues is a challenging open problem.

Finally, it might be interesting to study the limitations of spectral techniques for other problems such as coloring and satisfiability .

Acknowledgments

We thank Iain Johnstone for bringing to our attention.

References