On affinity matrix normalization for graph cuts and spectral clustering

• A relationship with invariant property about cluster's data assignment is established for graph partitioning problems.
• The relationship holds for normalized affinity matrix having constant row/column-sum.
• Consequently, the solution of numerous spectral clustering algorithms can be obtained using graph ratio-cut objective.
• Clustering experiments on 7 such normalization schemes and 17 benchmark datasets are presented.

Graph-based spectral clustering algorithms involve the analysis of an affinity matrix. The latter defines the pairwise similarity relations among data points. Popular graph partitioning algorithms typically involve a normalization step that reflects itself onto an affinity matrix normalization step in spectral clustering algorithms. In this paper, we show that affinity matrix normalization with constant row/column sum guarantees the invariance of the size-weighted sum of the between- and within-cluster graph association; a property conceptually equivalent to the data variance decomposition exploited by the standard k-means algorithm. From this observation, we demonstrate that the solution of numerous spectral clustering methods can be obtained using the standard graph ratio cut objective function. We have identified in the literature 7 such affinity matrix normalization schemes relevant to spectral clustering. Clustering experiments performed with these 7 normalization schemes on 17 benchmark datasets are presented. As a general rule, it is observed that the appropriate normalization method depends on the dataset. A geometric interpretation in the feature space (FS) of such a normalization scheme for k-way spectral clustering is also presented.