Presentation
P40 - Spectral Methods for the Clustering of Cyclic and Acyclic Graphs
Presenter
DescriptionTraditional spectral clustering methods are designed for undirected graphs and fail to capture the directionality of the edges and of the connections between the clusters. The aim of our work is centered around developing novel spectral methods for the spectral clustering of directed graphs with block-cyclic and block-acyclic structures. Block-cyclic instances are obtained from phenomena with recurrent patterns, while block-acyclic ones capture hierarchical relationships, and usually appear in real-world scenarios such as task scheduling between processors and trophic networks. We extend previously introduced spectral methods for the clustering of block-cyclic and block-acyclic graphs to novel algorithms, employing nonlinear graph Laplacians, that provide sharper approximations for the directed graph cuts, resulting in higher clustering accuracy. Additionally, we leverage diffusion principles in the transition matrices under question, to effectively minimize the normalized cut between the partitions. The effectiveness of the introduced algorithms is validated through a series of experiments on synthetic and real-world graphs. The performance of the algorithms is measured both with metrics based on the quality of the graph-cut, and with metrics based on the accuracy of labels retrieval.
TimeTuesday, June 1710:30 - 11:00 CEST
LocationCampussaal - Plenary Room
Session Chair
Event Type
PASC Poster
