AAAI Publications, Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
A Theoretical Framework of the Graph Shift Algorithm
Xuhui Fan, Longbing Cao

Last modified: 2012-07-14


Since no theoretical foundations for proving the convergence of Graph Shift Algorithm have been reported, we provide a generic framework consisting of three key GS components to fit the Zangwill’s convergence theorem. We show that 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. What is more, a theoretical framework is proposed to apply our proof to a more general case.


Convergence; Graph Shift; Zangwill

Full Text: PDF