Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916947821592576 |
|---|---|
| author | Sevi, Harry Debaussart-Joniec, Gwendal Hacini, Malik Jonckheere, Matthieu Kalogeratos, Argyris |
| author_facet | Sevi, Harry Debaussart-Joniec, Gwendal Hacini, Malik Jonckheere, Matthieu Kalogeratos, Argyris |
| contents | Clustering in directed graphs remains a fundamental challenge due to the asymmetry in edge connectivity, which limits the applicability of classical spectral methods originally designed for undirected graphs. A common workaround is to symmetrize the adjacency matrix, but this often leads to losing critical directional information. In this work, we introduce the generalized Dirichlet energy (GDE), a novel energy functional that extends the classical Dirichlet energy to handle arbitrary positive vertex measures and Markov transition matrices. GDE provides a unified framework applicable to both directed and undirected graphs, and is closely tied to the diffusion dynamics of random walks. Building on this framework, we propose the generalized spectral clustering (GSC) method that enables the principled clustering of weakly connected digraphs without resorting to the introduction of teleportation to the random walk transition matrix. A key component of our approach is the utilization of a parametrized vertex measure encoding graph directionality and density. Experiments on real-world point-cloud datasets demonstrate that GSC consistently outperforms existing spectral clustering approaches in terms of clustering accuracy and robustness, offering a powerful new tool for graph-based data analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_03221 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs Sevi, Harry Debaussart-Joniec, Gwendal Hacini, Malik Jonckheere, Matthieu Kalogeratos, Argyris Machine Learning Clustering in directed graphs remains a fundamental challenge due to the asymmetry in edge connectivity, which limits the applicability of classical spectral methods originally designed for undirected graphs. A common workaround is to symmetrize the adjacency matrix, but this often leads to losing critical directional information. In this work, we introduce the generalized Dirichlet energy (GDE), a novel energy functional that extends the classical Dirichlet energy to handle arbitrary positive vertex measures and Markov transition matrices. GDE provides a unified framework applicable to both directed and undirected graphs, and is closely tied to the diffusion dynamics of random walks. Building on this framework, we propose the generalized spectral clustering (GSC) method that enables the principled clustering of weakly connected digraphs without resorting to the introduction of teleportation to the random walk transition matrix. A key component of our approach is the utilization of a parametrized vertex measure encoding graph directionality and density. Experiments on real-world point-cloud datasets demonstrate that GSC consistently outperforms existing spectral clustering approaches in terms of clustering accuracy and robustness, offering a powerful new tool for graph-based data analysis. |
| title | Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2203.03221 |