Scalable Multi-View Graph Clustering With Cross-View Corresponding Anchor Alignment

Multi-view graph clustering (MVGC) explores pairwise correlations of entire instances and comprehensively aggregates diverse source information with optimal graph structure. One major issue of practical MVGC is the high time and space complexities prohibiting being applied on large-scale applications. As a promising solution of addressing large-scale problems, anchor-based strategy identifies small portion and key landmarks to serve as replacements for the entire dataset. Despite of its efficiency, anchors chosen across views may be semantically unaligned contrasting to naturally-aligned full sample setting, which may lead to the latter inappropriate graph fusion. Limited attention has been focused on the mentioned Multi-View Anchor-Unaligned Problem (MV-AUP) in the existing literature. In this paper, we first revisit existing multi-view anchor graph clustering frameworks and present the MV-AUP phenomenon. Then, we propose a novel <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</u>ulti-view <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</u>orresponding <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u>nchor <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</u>raph <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u>lignment <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</u>usion framework (MV-CAGAF), which elegantly solves MV-AUP with structural representation matching in multi-dimensional spaces. Further, we theoretically prove our proposed structural matching approach can be regarded as minimizing the EMD distance of the two relative anchor distributions. Based on this, we design the innovative multi-view anchor graph fusion paradigm with correspondence alignment, which inherits the linear sample complexity for scalable cross-view clustering. Our proposed MV-CAGAF achieves significant improvements with the help of the novel fusion framework on comprehensive benchmark datasets. Most importantly, the experimental results on both of the simulated and real-world datasets significantly prove the importance of cross-view alignment for large-scale multi-view clustering.