论文标题
定向和无向图的广义光谱聚类
Generalized Spectral Clustering for Directed and Undirected Graphs
论文作者
论文摘要
光谱群集是一种流行的方法，用于群集无向图，但是将其扩展到有向图（Digraphs）更具挑战性。典型的解决方法是天真地对称有向图的邻接矩阵，但是，这可能导致丢弃边缘方向性携带的有价值的信息。在本文中，我们提出了一个广义的光谱聚类框架，该框架可以解决有向图和无方向的图。我们的方法基于新功能的光谱松弛，我们将其作为图形函数的广义dirichlet能量引入，相对于图形边缘的任意正规化度量。我们还提出了从图表上自然随机行走的迭代力构建的正规化度量的实际参数化。我们提出理论论点，以解释框架在不平衡阶级的挑战性环境中的效率。使用来自真实数据集构建的定向K-NN图的实验表明，在所有情况下，我们的图形分区方法在所有情况下都表现良好，而在大多数情况下的表现都超过了现有方法。
Spectral clustering is a popular approach for clustering undirected graphs, but its extension to directed graphs (digraphs) is much more challenging. A typical workaround is to naively symmetrize the adjacency matrix of the directed graph, which can however lead to discarding valuable information carried by edge directionality. In this paper, we present a generalized spectral clustering framework that can address both directed and undirected graphs. Our approach is based on the spectral relaxation of a new functional that we introduce as the generalized Dirichlet energy of a graph function, with respect to an arbitrary positive regularizing measure on the graph edges. We also propose a practical parametrization of the regularizing measure constructed from the iterated powers of the natural random walk on the graph. We present theoretical arguments to explain the efficiency of our framework in the challenging setting of unbalanced classes. Experiments using directed K-NN graphs constructed from real datasets show that our graph partitioning method performs consistently well in all cases, while outperforming existing approaches in most of them.
