Progressive Graph Partitioning Based on Information Diffusion
Authors : Mavridis, Christos and Baras, John S.
Conference : 2021 60th IEEE Conference on Decision and Control (CDC 2021) pp. 37-42 , Austin, TX
Date: December 13 - December 15, 2021
We propose an online deterministic annealing algorithm for progressive graph partitioning based on the spectral information of the underlying graph Laplacian matrix. Online deterministic annealing is a prototype-based unsupervised learning algorithm that progressively adjusts the number of prototypes used with respect to a performance-complexity trade-off. Due to the online nature of the proposed learning algorithm, the structure of the graph need not be known a priori. In this regard, we construct a distributed approximation algorithm to estimate the spectral information of the graph Laplacian, bypassing the exact computation of its eigenvectors. By propagating an impulse through the graph via a diffusion equation, we show that each node can construct a local learning representation which can be used for spectral clustering. As a result, the proposed approach is suitable for large graphs, requires minimal hyper-parameter tuning, and provides online control over the complexity-accuracy trade-off. We illustrate the properties and evaluate the performance of the proposed methodology in graph partition and image segmentation applications.
Download Full Paper