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.
@cite_61: It is well known that the smallest eigenvalue of the adjacency matrix of a connected d-regular graph is at least − d and is strictly greater than − d if the graph is not bipartite. More generally, for any connected graph G = (V, E), consider the matrix Q = D + A where D is the diagonal matrix of degrees in the graph G and A is the adjacency matrix of G. Then Q is positive semidefinite, and the smallest eigenvalue of Q is 0 if and only if G is bipartite. We will study the separation of this eigenvalue from 0 in terms of the following measure of nonbipartiteness of G. For any S ⊆ V, we denote by emin(S) the minimum number of edges that need to be removed from the induced subgraph on S to make it bipartite. Also, we denote by cut(S) the set of edges with one end in S and the other in V − S. We define the parameter Ψ as ***image*** The parameter Ψ is a measure of the nonbipartiteness of the graph G. We will show that the smallest eigenvalue of Q is bounded above and below by functions of Ψ. For d-regular graphs, this characterizes the separation of the smallest eigenvalue of the adjacency matrix from −d. These results can be easily extended to weighted graphs. © 1994 Wiley Periodicals, Inc.
Both Laplacians are positive semi-definite, and the smallest eigenvalue is zero if and only if the graph has a bipartite component @cite_61 .