Adaptive-order proximity learning for graph-based clustering. (June 2022)

• Record Type: Journal Article
• Authors: Wu, Danyang; Chang, Wei; Lu, Jitao; Nie, Feiping; Wang, Rong; Li, Xuelong
• Is Part Of: Pattern recognition. Volume 126(2022)
• Publication Date: 2022-06
• Subjects: Graph-based clustering -- Structured proximity matrix learning -- High-order proximity -- Adaptive learning; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.108550
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: This work firstly points out the mismatched problem between the first-order proximity matrix and the groundtruth. This work introduce the high-order proximity to structured proximity matrix learning. This work adaptively uses the proximity matrices of appropriate orders. This work proposes an efficient algorithm to solve the models. This work is extensible and can generate many models. Abstract: 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.