A convergence theorem for graph shift-type algorithms. Issue 8 (August 2015)

• Record Type: Journal Article
• Authors: Fan, Xuhui; Cao, Longbing
• Is Part Of: Pattern recognition. Volume 48:Issue 8(2015:Aug.)
• Page Start: 2751
• Page End: 2760
• Publication Date: 2015-08
• Subjects: Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2015.02.013
• Languages: English
• ISSNs: 0031-3203

Abstract

<abstract abstract-type="author" id="ab0005"> <title id="sect0005">Abstract</title> <sec> <p id="sp0050">The Robust Graph mode seeking by Graph Shift (Liu and Yan, 2010) (RGGS) algorithm represents a recent promising approach for discovering dense subgraphs in noisy data. However, there are no theoretical foundations for proving the convergence of the RGGS algorithm, leaving the question as to whether an algorithm works for solid reasons. In this paper, we propose a generic theoretical framework consisting of three key Graph Shift (GS) components: the simplex of a generated sequence set, the monotonic and continuous objective function and closed mapping. We prove that the GS-type algorithms built on such components can be transformed to fit Zangwill׳s theory, and the sequence set generated by the GS procedures always terminates at a local maximum, or at worst, contains a subsequence which converges to a local maximum of the similarity measure function. The framework is verified by theoretical analysis and experimental results of several typical GS-type algorithms.</p> </sec> </abstract>