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

Julien Ah-Pine

European Journal of Operational Research, 2022, vol. 299, issue 3, 1069-1078

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 n (modulo permutation of rows and columns) on the one hand, and the set of possible partitions of a set of n 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.

Keywords: Machine learning; Graph-based clustering; Doubly stochastic affinity matrix; Idempotent matrix; ADMM (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721010900
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:299:y:2022:i:3:p:1069-1078

DOI: 10.1016/j.ejor.2021.12.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().