Generalized Spectral Clustering for Directed and Undirected Graphs

2022-03-07 · Harry Sevi, Matthieu Jonckheere, Argyris Kalogeratos

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.

📄 PDF Abstract BibTeX arXiv:2203.03221

Code (0)

등록된 구현이 없습니다.

Tasks

Clusteringgraph partitioning

Methods 이 논문이 사용한 방법론

k-NN $k$-Nearest Neighbors is a clustering-based algorithm for classification and regression. It is a a type of instance-based learning as it does not attempt to construct a…

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Clustering for directed graphs using parametrized random walk diffusion kernels

2022-10-01 · Harry Sevi, Matthieu Jonckheere, Argyris Kalogeratos

Clustering based on the random walk operator has been proven effective for undirected graphs, but its generalization to directed graphs (digraphs) is much more challenging. Although the random walk operator is well-defin…

Clustering

Transfer operators on graphs: Spectral clustering and beyond

2023-05-19 · Stefan Klus, Maia Trower

Graphs and networks play an important role in modeling and analyzing complex interconnected systems such as transportation networks, integrated circuits, power grids, citation graphs, and biological and artificial neural…

Clustering Graph Clustering

Koopman-based spectral clustering of directed and time-evolving graphs

2022-04-06 · Stefan Klus, Natasa Djurdjevac Conrad

While spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems ranging from image segmentation and genome sequencing to signal…

Clustering Image Segmentation Semantic Segmentation

Hermitian matrices for clustering directed graphs: insights and applications

2019-08-06 · Mihai Cucuringu, Huan Li, He Sun, Luca Zanetti

Graph clustering is a basic technique in machine learning, and has widespread applications in different domains. While spectral techniques have been successfully applied for clustering undirected graphs, the performance …

Clustering Graph Clustering Stochastic Block Model

Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models

2024-03-28 · Ning Zhang, Xiaowen Dong, Mihai Cucuringu

Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization co…