Template-Based Graph Clustering
This work addresses graph clustering problems where prior knowledge about cluster structure is available, offering an incremental improvement for specific applications.
The authors tackled graph clustering by incorporating prior structural information through template matching, achieving superior performance over classical methods in challenging scenarios.
We propose a novel graph clustering method guided by additional information on the underlying structure of the clusters (or communities). The problem is formulated as the matching of a graph to a template with smaller dimension, hence matching $n$ vertices of the observed graph (to be clustered) to the $k$ vertices of a template graph, using its edges as support information, and relaxed on the set of orthonormal matrices in order to find a $k$ dimensional embedding. With relevant priors that encode the density of the clusters and their relationships, our method outperforms classical methods, especially for challenging cases.