HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering

Abstract : In graph-based clustering, a relevant affinity matrix is crucial for good results. Double stochasticity of the affinity matrix has been shown to be an important condition, both in theory and in practice. In this paper, we emphasize idempotency as another key condition. In fact, a theorem from Sinkhorn, R. (1968) allows us to exhibit the bijective relationship between the set of doubly stochastic and idempotent matrices of order (modulo permutation of rows and columns) on the one hand, and the set of possible partitions of a set of objects on the other hand. Thereby, both properties are necessary and sufficient conditions for properly modeling the clustering or graph partitioning tasks using matrices. Yet, this leads to a NP-hard discrete optimization problem. In this context, our main contribution is the introduction of a new relaxed model that efficiently learns a double stochastic and nearly idempotent affinity matrix for graph-based clustering. Our approach leverages existing properties between doubly stochastic and idempotent matrices on the one hand, and their associated Laplacian matrices on the other hand. The resulting optimization problem is bi-convex and can be addressed by an Alternating Direction Method of Multipliers scheme. Furthermore, our model requires less parameters to set in contrast to most of recent works. The experimental results we obtained using several real-world benchmarks, exhibit the interest of our method and the importance of taking into account idempotency in graph-based clustering.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03539972
Contributor : Julien Ah-Pine Connect in order to contact the contributor
Submitted on : Friday, January 28, 2022 - 2:51:14 PM
Last modification on : Friday, April 1, 2022 - 3:57:38 AM
Long-term archiving on: : Friday, April 29, 2022 - 9:26:56 PM

File

paper-dsni-rev_1.pdf
Files produced by the author(s)

Identifiers

Citation

Julien Ah-Pine. Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering. European Journal of Operational Research, Elsevier, 2021, ⟨10.1016/j.ejor.2021.12.034⟩. ⟨hal-03539972⟩

Share

Metrics

Record views

90

Files downloads

58