Agglomerative clustering via maximum incremental path integral

• A novel graph-structural agglomerative clustering algorithm.
• A structural descriptor, Incremental Path Integral, to define affinity of clusters.
• Treat a cluster as a dynamic system and its samples as states.
• Path Integral measures the stability of a dynamic system.
• Considerably outperform the state-of-the-art clustering algorithms.

Agglomerative clustering, which iteratively merges small clusters, is commonly used for clustering because it is conceptually simple and produces a hierarchy of clusters. In this paper, we propose a novel graph-structural agglomerative clustering algorithm, where the graph encodes local structures of data. The idea is to define a structural descriptor of clusters on the graph and to assume that two clusters have large affinity if their structural descriptors undergo substantial change when merging them into one cluster. A key insight of this paper to treat a cluster as a dynamical system and its samples as states. Based on that, Path Integral, which has been introduced in statistical mechanics and quantum mechanics, is utilized to measure the stability of a dynamical system. It is proposed as the structural descriptor, and the affinity between two clusters is defined as Incremental Path Integral, which can be computed in a closed-form exact solution, with linear time complexity with respect to the maximum size of clusters. A probabilistic justification of the algorithm based on absorbing random walk is provided. Experimental comparison on toy data and imagery data shows that it achieves considerable improvement over the state-of-the-art clustering algorithms.