Adaptive-order proximity learning for graph-based clustering

Recently, structured proximity matrix learning, which aims to learn a structured proximity matrix with explicit clustering structures from the first-order proximity matrix, has become the mainstream of graph-based clustering. However, the first-order proximity matrix always lacks several must-links compared to the groundtruth in real-world data, which results in a mismatched problem and affects the clustering performance. To alleviate this problem, this work introduces the high-order proximity to structured proximity matrix learning, and explores a novel framework named Adaptive-Order Proximity Learning (AOPL) to learn a consensus structured proximity matrix from the proximities of multiple orders. To be specific, AOPL selects the appropriate orders first, then assigns weights to these selected orders adaptively. In this way, a consensus structured proximity matrix is learned from the proximity matrices of appropriate orders. Based on AOPL framework, two practical models with different properties are derived, namely AOPL-Root and AOPL-Log. Besides, AOPL and the derived models are regarded as the same optimization problem subjected to some slightly different constraints. An efficient algorithm is proposed to solve them and the corresponding theoretical analyses are provided. Extensive experiments on several real-world datasets demonstrate superb performance of our model.