Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
Spectral methods are popular in detecting global structures in the given data that can be represented as a matrix. However when the data matrix is sparse or noisy, classic spectral methods usually fail to work, due to localization of eigenvectors (or singular vectors) induced by the sparsity or noise. In this work, we propose a general method to solve the localization problem by learning a regularization matrix from the localized eigenvectors. Using matrix perturbation analysis, we demonstrate that the learned regularizations suppress down the eigenvalues associated with localized eigenvectors and enable us to recover the informative eigenvectors representing the global structure. We show applications of our method in several inference problems: community detection in networks, clustering from pairwise similarities, rank estimation and matrix completion problems. Using extensive experiments, we illustrate that our method solves the localization problem and works down to the theoretical detectability limits in different kinds of synthetic data. This is in contrast with existing spectral algorithms based on data matrix, non-backtracking matrix, Laplacians and those with rank-one regularizations, which perform poorly in the sparse case with noise.
This paper proposes, in spectral detection of global structures in data matrix, a means to resolve the localization problem, which is known to cause several spectral detection methods to fail in sparse and/or noisy cases. The proposal is based on learning a proper regularizer on the basis of localized eigenvectors of the data matrix, where the algorithm is such that one iteratively updates the regularizer so that the regularized matrix has no significant eigenvalues, with the associated eigenvectors being localized in terms of the inverse participation ratio (IPR). 
Although the use of IPR in quantifying localization would work well in practice, as demonstrated in the section on numerical evaluations, it seems heuristic, since there would be several different quantities which would have qualitatively the same property as the IPR. Why it is a good quantifier compared with other possibilities in terms of detection of global structures should be discussed.     The author claims that the approach of trimming throws away part of the information, but one can see in the algorithm proposed in [12] that while trimming is used in the first stage the whole dataset is used in the final stage.     I was not convinced by the argument in page 3, which claims that spectral algorithms using the non-backtracking matrix can also be interpreted as an example of equation (1). In the interpretation the regularizer is dependent on the eigenvalue, which obscures the interpretation of these spectral algorithms as instances of the regularized spectral method (equation (1)). Specifically, I do not see any description of the claimed direct relation between the vector v appearing in Line 90 and the eigenvectors of the non-backtracking matrix.     Minor points:     - Line 32: Weigner's -> Wigner's     - Line 35: the wigner's -> Wigner's     - Line 37: which (is -> are) roughly     - Line 68: by learn(ing) a proper     - Line 75: that correlate(d)     - Line 103: that (are) specific     - Line 108: have (a large eigenvalue -> large eigenvalues) / which represent(s)     - Line 110: one who reveal -> ones which reveal     - Line 127: semi-cycle -> semi-circle (But in this case the bulk of the spectrum is not exactly a semi-circle.)     - Line 129: The spectra(l) density     - Line 130: the continu(es -> ous) part     - Line 152: the inverse participat(e -> ion) ratio     - Lines 179, 293: state-of-art -> state-of-the-art     - Line 220: between (duplicate)     - Line 227: assign items a hidden clusters -> assigns to items hidden clusters     - Line 228: then generate(s) similarity between (a) randomly sampled pairs of items     - Line 236: Here the term overlap is briefly explained, but it has already appeared several times before. The brief explanation should be given at its first appearance.     - Line 246: each selected node(s)     - Line 249: fail(s) to work     - Line 255: that (is) closely related     - Line 276: where (one) can see     - Line 286: a(n) accurate completion