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_55: - Preface to 'Means and their Inequalities'. Preface to the Handbook. Basic References. - Notations. 1. Referencing. 2. Bibliographic References. 3. Symbols for some Important Inequalities. 4. Numbers, Sets and Set Functions. 5. Intervals. 6. n-tuples. 7. Matrices. 8. Functions. 9. Various. A List of Symbols. An Introductory Survey. - I: Introduction. 1. Properties of Polynomials. 2. Elementary Inequalities. 3. Properties of Sequences. 4. Convex Functions. - II: The Arithmetic, Geometric and Harmonic Means. 1. Definitions and Simple Properties. 2. The Geometric Mean-Arithmetic Mean Inequality. 3. Refinements of the Geometric Mean-Arithmetic Mean Inequality. 4. Converse Inequalities. 5. Some Miscellaneous Results. - III: The Power Means. 1. Definitions and Simple Properties. 2. Sums of Powers. 3. Inequalities between the Power Means. 4. Converse Inequalities. 5. Other Means Defined Using Powers. 6. Some Other Results. - IV: Quasi-Arithmetic Means. 1. Definitions and Basic Properties. 2. Comparable Means and Functions. 3. Results of Rado Popoviciu Type. 4. Further Inequalities. 5. Generalizations of the Holder and Minkowski Inequalities. 6. Converse Inequalities. 7. Generalizations of the Quasi-arithmetic Means. - V: Symmetric Polynomial Means. 1. Elementary Symmetric Polynomials and Their Means. 2. The Fundamental Inequalities. 3.Extensions of S(r s) of Rado Popoviciu Type. 4. The Inequalities of Marcus and Lopes. 5. Complete Symmetric Polynomial Means: Whiteley Means. 6. The Muirhead Means. 7. Further Generalizations. - VI: Other Topics. 1. Integral Means and Their Inequalities. 2. Two Variable Means. 3. Compounding of Means. 4. Some General Approaches to Means. 5. Mean Inequalities for Matrices. 6. Axiomatization of Means. Bibliography. Name Index. Index.
@cite_14: This book represents the first synthesis of the considerable body of new research into positive definite matrices. These matrices play the same role in noncommutative analysis as positive real numbers do in classical analysis. They have theoretical and computational uses across a broad spectrum of disciplines, including calculus, electrical engineering, statistics, physics, numerical analysis, quantum information theory, and geometry. Through detailed explanations and an authoritative and inspiring writing style, Rajendra Bhatia carefully develops general techniques that have wide applications in the study of such matrices. Bhatia introduces several key topics in functional analysis, operator theory, harmonic analysis, and differential geometry--all built around the central theme of positive definite matrices. He discusses positive and completely positive linear maps, and presents major theorems with simple and direct proofs. He examines matrix means and their applications, and shows how to use positive definite functions to derive operator inequalities that he and others proved in recent years. He guides the reader through the differential geometry of the manifold of positive definite matrices, and explains recent work on the geometric mean of several matrices. Positive Definite Matrices is an informative and useful reference book for mathematicians and other researchers and practitioners. The numerous exercises and notes at the end of each chapter also make it the ideal textbook for graduate-level courses.
@cite_21: 
The scalar power mean of two non-negative scalars @math is a one-parameter family of means defined for @math as @math . Particular cases are the arithmetic, geometric and harmonic means, as shown in Table . Moreover, the scalar power mean is monotone in the parameter @math , i.e. @math when @math (see @cite_55 , Ch. 3, Thm. 1), which yields the well known arithmetic-geometric-harmonic mean inequality @math . As matrices do not commute, several matrix extensions of the scalar power mean have been introduced, which typically agree if the matrices commute, see e.g. Chapter 4 in @cite_14 . We consider the following matrix extension of the scalar power mean: where @math is the unique positive definite solution of the matrix equation @math . Please note that this definition can be extended to positive semidefinite matrices @cite_21 for @math , as @math exists, whereas for @math a diagonal shift is necessary to ensure that the matrices @math are positive definite. 5pt