PaperlayerView exact revision on arXiv

Source-linked AI summary

Align then Fusion: Generalized Large-scale Multi-view Clustering with Anchor Matching Correspondences

Siwei Wang, Xinwang Liu, Suyuan Liu, Jiaqi Jin, Wenxuan Tu, Xinzhong Zhu, En Zhu

arXiv:2205.15075v2cs.LG

TL;DR

Separately selected anchors across views may lack correct correspondences, and different feature dimensions make matching difficult. FMVACC uses flexible anchors and feature and structure information to align correspondences before fusion. Experiments report strong benchmark performance and improvements when the alignment module is applied to existing methods.

  • Problem

    Multi-view anchor sets may not correspond across views, and different feature dimensions make direct anchor-distance matching difficult.

    Source: §1 · p. 1, §3.2 · p. 4

  • Method

    FMVACC flexibly selects anchors, uses feature and structure information to establish correspondences, and then fuses aligned anchor graphs column-wise.

    Source: §1 · p. 2

  • Results

    Across three small and four large datasets, FMVACC outperforms competitors on most metrics; its ACC progress over AMGL is 39.53% on 3-Sources.

    Source: §4.2 · p. 9

  • Takeaways & Limitations

    Applying the alignment module to existing multi-view anchor graph approaches significantly improves clustering performance, indicating the importance of anchor alignment.

    Source: §1 · p. 2

Abstract

from arXiv · show

Multi-view anchor graph clustering selects representative anchors to avoid full pair-wise similarities and therefore reduce the complexity of graph methods. Although widely applied in large-scale applications, existing approaches do not pay sufficient attention to establishing correct correspondences between the anchor sets across views. To be specific, anchor graphs obtained from different views are not aligned column-wisely. Such an \textbf{A}nchor-\textbf{U}naligned \textbf{P}roblem (AUP) would cause inaccurate graph fusion and degrade the clustering performance. Under multi-view scenarios, generating correct correspondences could be extremely difficult since anchors are not consistent in feature dimensions. To solve this challenging issue, we propose the first study of the generalized and flexible anchor graph fusion framework termed \textbf{F}ast \textbf{M}ulti-\textbf{V}iew \textbf{A}nchor-\textbf{C}orrespondence \textbf{C}lustering (FMVACC). Specifically, we show how to find anchor correspondence with both feature and structure information, after which anchor graph fusion is performed column-wisely. Moreover, we theoretically show the connection between FMVACC and existing multi-view late fusion \cite{liu2018late} and partial view-aligned clustering \cite{huang2020partially}, which further demonstrates our generality. Extensive experiments on seven benchmark datasets demonstrate the effectiveness and efficiency of our proposed method. Moreover, the proposed alignment module also shows significant performance improvement applying to existing multi-view anchor graph competitors indicating the importance of anchor alignment. Our code is available at \url{https://github.com/wangsiwei2010/NeurIPS22-FMVACC}.

1 Introduction

Multi-view anchor graphs can scale graph clustering, but independently selected anchors may not correspond across views, making fusion inaccurate. FMVACC aligns flexible anchors using feature and structure information before column-wise fusion; experiments report effectiveness, efficiency, and gains from alignment.

1 Introduction

  • Existing multi-view graph clustering methods often have quadratic or cubic complexity in the number of instances, limiting their use on large datasets.Anchor graph methods reduce complexity by representing instances with selected anchors.Source: §1 · pp. 1–2
  • The Anchor-Unaligned Problem arises because anchors selected separately across views may not correspond, making graph columns misaligned and fusion inaccurate.Selecting samples at the same indexes, as in SFMC, can avoid mismatches but may destroy anchor flexibility; different feature dimensions also make direct anchor-distance computation difficult.Source: §1 · p. 2
  • FMVACC uses flexible anchors and feature and structure information to establish correspondences, then fuses anchor graphs column-wise; late fusion and PVC are special variants.The paper presents this as a generalized framework for flexible anchor correspondence fusion.Source: §1 · p. 2
  • Experiments report FMVACC’s effectiveness and efficiency, and significant improvement when its alignment module is applied to existing approaches.The introduction identifies alignment’s importance as a key implication of those improvements.Source: §1 · p. 2

2 Related Work

Related work describes multi-view graph clustering as constructing view-specific graphs and fusing them, then presents anchor graphs as a way to reduce the cost for large datasets. Anchor methods construct per-view graphs and combine them into a fused graph for clustering.

2.1 Multi-view Graph Clustering

  • MVGC builds single-view graphs and fuses them; approaches differ in pairwise-relationship construction and consensus optimization.Full pair-wise graph settings do not have the AUP because their anchors are instances and are naturally aligned.Source: §2.1 · p. 3

2.2 Multi-view Anchor Graph Clustering

  • Majority graph approaches require O(vn2) space and O(n3) time, motivating anchor graphs that use m selected anchors instead of all instances.The cited complexity is quadratic and cubic, respectively, in the number of instances.Source: §2.2 · p. 3
  • Anchor graph construction builds a graph for each view with fixed anchor matrix A_i; each sample’s similarities to anchors in Z_i sum to one.Common anchor-selection strategies include per-view k-means and random sampling.Source: §2.2 · p. 3
  • Fusion combines view-specific anchor graphs using view weights α, then applies k-means to the fused graph’s left singular vector; complexity is O(vnm) space and O(nm2) time.The weights and fused graph are alternatively optimized; cited alternatives include equal view weights and a rank constraint.Source: §2.2 · p. 3

3 Anchor-Unaligned Clustering for Large-scale Multi-view Data

FMVACC addresses unaligned anchor sets across views by learning flexible anchors and matching them using feature and structure information before graph fusion. Its framework also connects to existing multi-view clustering settings and is analyzed as linear in sample count for space and time.

3 Anchor-Unaligned Clustering for Large-scale Multi-view Data

  • FMVACC first learns flexible anchors for individual views, then establishes correspondences before performing column-wise graph fusion.The framework is presented as a generalized approach to flexible anchor correspondence fusion.Source: §3 · p. 3, §3.1 · p. 4

3.1 Flexible Anchor Generation

  • Orthogonality constraints make learned anchors more discriminative and diverse, while truncated SVD provides an analytical update when m ≤ d_i.When m > d_i, the orthogonal constraints are removed for unconstrained optimization.Source: §3.1 · p. 4

3 Anchor-Unaligned Clustering for Large-scale Multi-view Data

  • The Anchor-Unaligned Problem arises when independently selected anchor sets mismatch across views, leaving their graph columns unaligned for fusion.The paper states that this can lead to inaccurate fusion and degraded clustering performance.Source: §3 · p. 3, §3.2 · p. 5

3.2 Generalized Multi-view Anchor Matching Framework

  • FMVACC represents each anchor by its anchor-graph column as an n-dimensional feature, making anchors measurable across views for matching.The matching retains first-order feature and second-order structure information.Source: §3.2 · pp. 5–6
  • The correspondence objective combines feature similarity with second-order graph-structure agreement, then relaxes the quadratic assignment problem to a doubly stochastic domain.The relaxed objective is solved with a Projected Fixed-Point Algorithm.Source: §3.2 · pp. 5–6

3.3 Complexity Analysis

  • FMVACC has O(n) space and time complexity when m ≪ n and d ≪ n, including its post-processing.The optimization time is O(nmd + nm2 + m2d + m3), and SVD plus k-means post-processing costs O(nm2).Source: §3.3 · p. 7

3.4 Theoretical Analysis

  • Late fusion is a special case of FMVACC with k clustering-center anchors and discrete partition graphs, while PVC is a special case using structure loss and known correspondences.The paper presents these connections as evidence of FMVACC’s generality.Source: §3.4 · p. 7

4 Experiments

Experiments assess FMVACC on a simulated dataset and real-world multi-view benchmarks, including the alignment module’s effects on clustering and runtime. The reported results favor FMVACC on most clustering metrics and show gains from alignment.

4 Experiments

  • The evaluation includes a simulated dual-view dataset with four clusters of 50 two-dimensional instances each, plus real-world datasets spanning 169 to 63,896 instances.Source: §4 · p. 7, §4.1 · p. 7, §4.2 · p. 8

4.1 Simulated Multi-view Dataset

  • On the simulated dataset, alignment improves LMVSC by 15.94% (ACC), 17.82% (NMI), and 20.31% (Fscore), while flexible selection provides 33.00% (ACC) and 21.71% (Fscore) for SFMC.Source: Table 1 · p. 8, §4.1 · p. 8, Figure 3 · p. 8

4.2 Real-world Multi-view Datasets

  • FMVACC outperforms seven algorithms on most metrics across three small datasets, with ACC gains over AMGL of 39.53% (3-Sources), 7.21% (UCI-Digit), and 23.46% (BDGP).On the last four large-scale datasets, it outperforms RMKM, BMVC, LMVSC, FMCNOF, and MSGL on most metrics.Source: Table 2 · p. 9, §4.2 · p. 9
  • On UCI-Digit, LMVSCAligned raises ACC from 66.78% to 82.97%, and aligned fused graphs for LMVSC and FMVACC have clearer structures.Source: §4.2 · p. 9, Figure 4 · p. 9
  • On MNIST’s 60,000 samples, FMVACC runs in 571.10 seconds, second only to BMVC; RMKM takes 1468.30 seconds and LMVSC 604.68 seconds.Source: Table 3 · p. 10, §4.2 · p. 10
  • On all seven benchmarks, adding the alignment module improves clustering performance for both LMVSC and FMVACC.Source: Table 4 · p. 10, §4.2 · p. 10

5 Conclusion

The paper introduces FMVACC as a flexible multi-view anchor-graph fusion framework that establishes anchor correspondences using feature and structure information. It reports experimental effectiveness and connects the framework theoretically to existing multi-view strategies.

5 Conclusion

  • FMVACC is presented as the first study of the multi-view anchor-unaligned problem.The paper identifies future work on improving anchor representations with deep learning.Source: §5 · p. 10
  • FMVACC constructs flexible anchors and captures correspondences using both feature and structure information.The paper also provides theoretical analysis connecting FMVACC with existing multi-view strategies.Source: §5 · p. 10
  • Experiments are reported to demonstrate the effectiveness of anchor alignment and FMVACC.Source: §5 · p. 10
  • The paper identifies deep-learning-based, more-qualified anchors as future work.Source: §5 · p. 10

.1 Details of Algorithms

This appendix specifies the projected fixed-point alignment procedure and its convergence result, then reports alignment, parameter-sensitivity, and orthogonality experiments.

.1 Details of Algorithms

  • Equation (12) is called the multi-view anchor correspondence framework, and P is updated with a projected fixed-point algorithm using a double-stochastic projection; α is set to 0.5.Source: .1 Details of Algorithms · p. 13

.2 Convergence Rate Proof

.3 Experimental setting

.4 More Experimental Results

  • 14.46% (UCI-Digit) and 8.70% (BDGP) NMI gains are reported for LMVSC-Aligned over LMVSC, while FMVACC-Aligned gains 8.52% (BDGP) and 6.80% (YTF-10) Fscore over FMVACC without alignment.The comparison covers seven benchmarks.Source: Table 5 · p. 14, .4 More Experimental Results · p. 14

.5.1 Effect of Orthogonal Constraints on Anchor Matrices

.5 Parameter sensitivity

  • As structural-correspondence effect decreases, clustering performance rises; m=2k performs best on MNIST and YTF-10.The sensitivity experiments use six datasets and vary λ and the number of anchors.Source: .5 Parameter sensitivity · p. 14, Figure 5 · p. 15
Loading 2205.15075v2…