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.
Code (1)
Tasks
ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Spectral Clustering of Signed Graphs via Matrix Power Means
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 mat…
ClusteringStochastic Block ModelSubmodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in clustering applications in which higher-or…
ClusteringSpectral Analysis Of Weighted Laplacians Arising In Data Clustering
Graph Laplacians computed from weighted adjacency matrices are widely used to identify geometric structure in data, and clusters in particular; their spectral properties play a central role in a number of unsupervised an…
ClusteringA Tutorial on Spectral Clustering
In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms t…
ClusteringMaking Laplacians commute
In this paper, we construct multimodal spectral geometry by finding a pair of closest commuting operators (CCO) to a given pair of Laplacians. The CCOs are jointly diagonalizable and hence have the same eigenbasis. Our c…
ClusteringDimensionality Reduction