Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We provide a thorough analysis of the proposed approach in the setting of a general Stochastic Block Model that includes models such as the Labeled Stochastic Block Model and the Censored Block Model. We show that in expectation the signed power mean Laplacian captures the ground truth clusters under reasonable settings where state-of-the-art approaches fail. Moreover, we prove that the eigenvalues and eigenvector of the signed power mean Laplacian concentrate around their expectation under reasonable conditions in the general Stochastic Block Model. Extensive experiments on random graphs and real world datasets confirm the theoretically predicted behaviour of the signed power mean Laplacian and show that it compares favourably with state-of-the-art methods.
where @math is the average node degree @math . The Bethe Hessian @math need not be positive definite. In fact, eigenvectors with negative eigenvalues bring information of clustering structure @cite_34 .
@cite_34
2152361742
Many graphs arising in various information networks exhibit the "power law" behavior — the number of vertices of degree k is proportional to k −β for some positive β. We show that if β > 2.5, the largest eigenvalue of a random power law graph is almost surely (1+ o(1)) √ m where m is the maximum degree. Moreover, the k largest eigenvalues of a random power law graph with exponent β have power law distribution with exponent 2β − 1 if the maximum degree is sufficiently large, where k is a function depending on β, m and d, the average degree. When 2< β < 2.5, the largest eigenvalue is heavily concentrated at cm 3−β for some constant c depending on β and the average degree. This result follows from a more general theorem which shows that the largest eigenvalue of a random graph with a given expected degree sequence is determined by m, the maximum degree, and ˜ d, the weighted average of the squares of the expected degrees. We show that the k-th largest eigenvalue is almost surely (1+ o(1)) √ m k where mk is the k-th largest expected degree provided mk is large enough. These results have implications on the usage of spectral techniques in many areas related to pattern detection and information retrieval.