Given a large data matrix $A\\in\\mathbb{R}^{n\\times n}$, we consider the\nproblem of determining whether its entries are i.i.d. with some known marginal\ndistribution $A_{ij}\\sim P_0$, or instead $A$ contains a principal submatrix\n$A_{{\\sf Q},{\\sf Q}}$ whose entries have marginal distribution $A_{ij}\\sim\nP_1\\neq P_0$. As a special case, the hidden (or planted) clique problem\nrequires to find a planted clique in an otherwise uniformly random graph.\n Assuming unbounded computational resources, this hypothesis testing problem\nis statistically solvable provided $|{\\sf Q}|\\ge C \\log n$ for a suitable\nconstant $C$. However, despite substantial effort, no polynomial time algorithm\nis known that succeeds with high probability when $|{\\sf Q}| = o(\\sqrt{n})$.\nRecently Meka and Wigderson \\cite{meka2013association}, proposed a method to\nestablish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy.\n Here we consider the degree-$4$ SOS relaxation, and study the construction of\n\\cite{meka2013association} to prove that SOS fails unless $k\\ge C\\,\nn^{1/3}/\\log n$. An argument presented by Barak implies that this lower bound\ncannot be substantially improved unless the witness construction is changed in\nthe proof. Our proof uses the moments method to bound the spectrum of a certain\nrandom association scheme, i.e. a symmetric random matrix whose rows and\ncolumns are indexed by the edges of an Erd\\"os-Renyi random graph.\n