A Convergence Theorem for the Graph Shift-type Algorithms
This provides theoretical guarantees for GS algorithms used in dense subgraph discovery, which is incremental as it builds on existing methods.
The paper tackles the lack of theoretical foundations for Graph Shift (GS) algorithms by proposing a framework to prove their convergence, showing that GS sequences terminate at or converge to a local maximum.
Graph Shift (GS) algorithms are recently focused as a promising approach for discovering dense subgraphs in noisy data. However, there are no theoretical foundations for proving the convergence of the GS Algorithm. In this paper, we propose a generic theoretical framework consisting of three key GS components: simplex of generated sequence set, monotonic and continuous objective function and closed mapping. We prove that GS algorithms with such components can be transformed to fit the Zangwill's convergence theorem, 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 expanding it to other GS-type algorithms and experimental results.