Clustering Signed Networks with the Geometric Mean of Laplacians
Signed networks allow to model positive and negative relationships. We analyze existing extensions of spectral clustering to signed networks. It turns out that existing approaches do not recover the ground truth clustering in several situations where either the positive or the negative network structures contain no noise. Our analysis shows that these problems arise as existing approaches take some form of arithmetic mean of the Laplacians of the positive and negative part. As a solution we propose to use the geometric mean of the Laplacians of positive and negative part and show that it outperforms the existing approaches. While the geometric mean of matrices is computationally expensive, we show that eigenvectors of the geometric mean can be computed efficiently, leading to a numerical scheme for sparse matrices which is of independent interest.
This paper presents an argument for using the geometric mean of the normalized Laplacian matrix for each of the positive and negative normalized laplacian matrices  associated with a signed graph. The authors present some evidence for this idea in terms of a stochastic  block model.  This is a small but nice observation. They show that the eigenvectors of simple block-models (e.g. matrices (pI + q*ones) and variations for  the signed matrices). ) So the analysis is very simple for the highly idealized case. (There is no study of the empirical convergence to this distribution as  found in Abbe et al.; https://arxiv.org/pdf/1405.3267.pdf)  When this is used for spectral clustering, we need the eigenvectors of the geometric metean.  They also show how the eigenvectors of the geometric mean might be computed more rapidly than forming the geometric mean and computing it's eigenvectors. This is based on a particular application of the extended Krylov subspace method that can rapidly compute various functions of matrices. This contribution is less clear (see below) due to some existing work on the area whose relationship the authors should clarify.   The empirical results for real world datasets are fairly standard finding of "my new method is better". There  are various parameters (e.g. # of classes) that could  be varied (e.g. # of classes) and little sensitivity study, but this is not uncommon. The only troubling finding is on the Wikipedia signed network. The authors claim to have clustering structure based on a highly misleading plot, the dreaded "dot plot" which is arguably the weakest  evidence possible. This section needs far more evidence to support its supposed conclusions.    Questions for authors ---------------------  1. Could you clarify the relationship with other work on computing the geometric mean * a vector, e.g.  * Krylov iterative methods for the geometric mean of two matrices times a vector Jacopo Castellini (too new to have been included as a ref.)  * Computing the weighted geometric mean of two large-scale matrices and its inverse times a vector. http://eprints.ma.man.ac.uk/2474/01/covered/MIMS_ep2016_29.pdf  (It seems this is related to [8], which you already cite.)  In particular, what is the contribution of the Krylov algorithm in this paper vs. [8].  2. Is there additional evidence for clustering in the  wiki-sign network? Figs. 4(a) and 4(b) are not at all convincing. (Especially in light of multiple  negative findings in [15] an and [4].)  Suggestions for future work ---------------------------  Given the results on the stochastic block model are largely expressed with the same subspaces (e.g. the eigenvectors are the same for the pos. and neg, it might be nice to study a more straightforward quantity such as A*B or B*A (or their sum) as a baseline measure to quantify the significance of your approach. This would also suggest a simple extension to your theorem about the blockmodel case for a broader class of matrix functions.   Presentation remarks -------------------- * Harmless typos throughout that do not impede understanding * Theorems 1 and 2 are fairly simple and don't seem like they need to be highlighted. (And can probably be cited from existing work.)
 This is a small but nice contribution. It seems like much of the theory could be generalized to a broader class of matrix functions (e.g. many things with the product of the Laplacians would seem to meet many of the criteria, so there is nothing special about the geometric mean). This could enable and allow better computational methods that are far more straightforward.