PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph Learning

Si-Guo Fang, Dong Huang, Xiao-Sha Cai, Chang-Dong Wang, Chaobo He, Yong Tang

arXiv:2209.04187v2cs.LGcs.AI

TL;DR

UDBGL targets the high cost, incomplete joint learning, and separate discretization of existing multi-view clustering methods. It jointly learns view-specific and consensus bipartite graphs with adaptive weights and discrete structure in one objective, using a linear-time optimization algorithm. Across benchmark datasets, it reports robust and efficient clustering, including average NMI, ACC, and PUR scores of 43.60, 50.71, and 54.74, respectively.

  • Problem

    Existing multi-view clustering methods face high computational complexity, limited joint learning of view-specific and consensus graphs, and reliance on k-means for discretization.

  • Method

    UDBGL uses anchor-based subspace learning, adaptive bipartite graph fusion, and a Laplacian rank constraint within a unified objective to learn discrete clustering directly.

  • Results

    43.60 average NMI(%), 50.71 average ACC(%), and 54.74 average PUR(%) are reported across benchmark datasets, with UDBGL substantially outperforming compared MVC methods.

  • Takeaways & Limitations

    UDBGL provides a robust and scalable multi-view clustering approach with linear computational complexity and no additional partitioning step.

Abstract

from arXiv · show

Although previous graph-based multi-view clustering algorithms have gained significant progress, most of them are still faced with three limitations. First, they often suffer from high computational complexity, which restricts their applications in large-scale scenarios. Second, they usually perform graph learning either at the single-view level or at the view-consensus level, but often neglect the possibility of the joint learning of single-view and consensus graphs. Third, many of them rely on the k-means for discretization of the spectral embeddings, which lack the ability to directly learn the graph with discrete cluster structure. In light of this, this paper presents an efficient multi-view clustering approach via unified and discrete bipartite graph learning (UDBGL). Specifically, the anchor-based subspace learning is incorporated to learn the view-specific bipartite graphs from multiple views, upon which the bipartite graph fusion is leveraged to learn a view-consensus bipartite graph with adaptive weight learning. Further, the Laplacian rank constraint is imposed to ensure that the fused bipartite graph has discrete cluster structures (with a specific number of connected components). By simultaneously formulating the view-specific bipartite graph learning, the view-consensus bipartite graph learning, and the discrete cluster structure learning into a unified objective function, an efficient minimization algorithm is then designed to tackle this optimization problem and directly achieve a discrete clustering solution without requiring additional partitioning, which notably has linear time complexity in data size. Experiments on a variety of multi-view datasets demonstrate the robustness and efficiency of our UDBGL approach. The code is available at https://github.com/huangdonghere/UDBGL.

I. INTRODUCTION

UDBGL addresses scalability, incomplete joint learning, and separate discretization in graph-based multi-view clustering by jointly learning view-specific and consensus bipartite graphs with discrete structure. Its unified formulation and linear-time optimization produce direct clustering, with experiments reporting robustness and scalability over state-of-the-art methods.

  • Graph-based multi-view clustering commonly learns sample-wise relationships in n × n graphs before partitioning them into clusters.
  • Bipartite graph methods reduce computational cost by representing data with an n × m graph, where m is the number of anchors and m ≪ n.
  • Prior methods often either learn only a unified graph, concatenate view-specific graphs heuristically, or pre-construct them without jointly refining view-specific and consensus structure.
  • UDBGL jointly learns view-specific bipartite graphs, a view-consensus bipartite graph with adaptive weights, and a discrete cluster structure through a unified objective.
  • A Laplacian rank constraint directly yields the desired connected components, avoiding additional spectral partitioning, while the optimization algorithm has linear computational complexity in data size.
  • Experiments on ten real-world multi-view datasets report robustness, scalability, and superiority over state-of-the-art multi-view clustering methods.

A. Notations

The method models each view through self-representation and extends this formulation to anchor-based bipartite graphs, reducing the cost of learning relationships across large datasets.

  • View-specific subspace learning: Self-representation reconstructs each sample from other samples while minimizing reconstruction error and enforcing zero self-representation.
  • View-specific subspace learning: Nonnegative, row-normalized coefficients make each representation matrix interpretable as a similarity graph.The row constraint ensures every sample has at least one nonzero coefficient.
  • View-specific subspace learning: Multi-view subspace learning jointly regularizes view-specific representation matrices to encourage cross-view consistency.
  • Anchor-based formulation: Learning multiple n × n graphs requires at least O(n^2) time, motivating smaller anchor-based dictionaries for large-scale data.
  • Anchor-based formulation: Replacing each data matrix with an anchor matrix yields Z(v) ∈ R^n×m, a bipartite graph connecting samples to anchors.

C. Rank-constrained Bipartite Graph Fusion

The fusion stage combines view-specific bipartite graphs into a weighted consensus graph and imposes a Laplacian rank constraint so its connected components directly encode clusters.

  • Graph fusion: Bipartite graph fusion combines multiple view graphs into a unified graph using adaptively learned view weights.
  • Graph fusion: The consensus graph is constrained to be nonnegative and row-normalized, while its weights remain normalized across views.
  • Rank-constrained fusion: The conventional route constructs an n × n similarity graph from the bipartite graph and then applies spectral clustering, requiring at least O(n^2c) time.
  • Rank-constrained fusion: The Laplacian rank constraint rank(eLS) = n + m − c enforces exactly c connected components in the learned graph.
  • Rank-constrained fusion: Samples in the same connected component of the rank-constrained bipartite graph are directly treated as one cluster without additional partitioning.
  • Rank-constrained fusion: Unlike ordinary graphs, bipartite connectivity between samples is mediated by one or more anchors.

D. Multi-view Clustering via Unified and Discrete Bipartite Graph Learning

UDBGL jointly learns view-specific graphs, a consensus bipartite graph, and discrete cluster structure in one objective, followed by an alternating optimization procedure that directly yields clustering.

  • Unified learning model: Existing methods commonly pre-construct view-specific bipartite graphs or simply concatenate them, limiting adaptive refinement of the unified graph.
  • Unified learning model: UDBGL jointly formulates view-specific graph learning, consensus graph learning, and discrete cluster structure learning.
  • Unified learning model: The unified objective constrains each view graph and the consensus graph to be nonnegative and row-normalized, with normalized nonnegative view coefficients.
  • Optimization: The algorithm is designed to mutually promote view-specific and consensus graphs and directly produce the final clustering without additional graph partitioning.
  • Optimization: The optimization alternates updates of P, Z(v), and δ while fixing the other variables.
  • Update P: The P-subproblem preserves row normalization, nonnegativity, and the Laplacian rank constraint while optimizing the consensus graph.

B. Update Z(v)

With other variables fixed, the view-specific graph subproblem is solved row by row and formulated as a quadratic program, then handled with an augmented Lagrangian multiplier method.

  • Update Z(v): The subproblem involving Z(v) is isolated by fixing all other variables.
  • Update Z(v): Because rows of Z(v) are independent, the algorithm optimizes the matrix row by row.
  • Update Z(v): Each row optimization is formulated as a quadratic programming problem.
  • Update Z(v): The resulting problem is solved using the augmented Lagrangian multiplier method.

C. Update δ

The algorithm updates the view weights δ through an augmented-Lagrangian formulation while alternating updates of auxiliary variables and graph-related quantities. It iterates these updates until convergence and directly obtains the final clustering from P.

  • Initialization and alternating optimization: UDBGL initializes anchors, view-specific bipartite graphs, and optimization variables before alternating updates of F, P, Z^(v), and δ.Anchors are obtained by k-means on concatenated features, while Z^(v) is initialized with K-nearest-neighbor bipartite graphs.
  • Discrete graph construction: The overall procedure repeatedly adjusts γ until P has c connected components, then updates every view-specific graph and outputs the final clustering directly from P.The parameter γ is doubled or halved according to the multiplicity of the zero eigenvalue of the normalized Laplacian.
  • Updating δ: The δ subproblem is reformulated by vectorizing each view-specific graph Z^(v) and the fused graph B, yielding b̂ = Ẑδ.The stacked matrix Ẑ contains vectorized graphs from all V views, and δ represents their adaptive weights.
  • Updating δ: The δ optimization is a convex quadratic program with a positive-semidefinite quadratic matrix and is solved using an augmented-Lagrangian formulation.The augmented-Lagrangian method introduces ρ and η, with a penalty term enforcing δ = ρ.
  • Updating δ: The auxiliary variables δ and ρ are optimized alternately, while the multiplier is updated as η ← η + µ(δ − ρ) and µ is increased iteratively.The algorithm updates ρ, solves the δ problem, then updates η and µ until δ converges.

D. Computational Complexity Analysis

UDBGL has linear time complexity in the number of samples because it operates on an n × m bipartite graph with n ≫ m and treats c, V, and update iterations as small constants.

  • Complexity components: The preparation cost includes O(nd) normalization and O(ndmt1) k-means time, where d is the summed feature dimension and t1 is the k-means iteration count.These costs arise before the main optimization begins.
  • Complexity components: Updating P costs O(nmct2 + nm^2t2 + m^3t2), while updating all Z^(v) costs O(nm^2d).Here t2 denotes the number of P-update iterations.
  • Complexity components: Updating the view weights δ costs O(V^2nm).This term reflects the adaptive weighting step across V views.
  • Overall complexity: Because n ≫ m and c, V, and t2 are small constants, UDBGL has linear time complexity in n.The bipartite representation avoids the quadratic cost of constructing an n × n graph.

E. Convergence analysis

The optimization has solvable convex subproblems for the graph variables and δ, while dynamically adjusting γ enforces the desired number of connected components but may disrupt monotonic objective decrease.

  • Discrete-structure constraint: The parameter γ is dynamically adjusted to obtain a bipartite graph with a specific number of connected components and discrete cluster structure.This adjustment can undermine monotonicity of the objective function for the associated subproblem.
  • Convergence characterization: Except for γ's dynamic adjustment, the other subproblems admit optimal solutions, and empirical convergence is evaluated experimentally.The convergence discussion distinguishes analytical solvability from the non-monotonic γ adjustment.
  • Convex subproblems: The Z^(v) update is a convex quadratic program because its quadratic form is positive semidefinite and its constraints are affine.The same analysis establishes convexity for the δ update.

V. EXPERIMENTS

UDBGL is evaluated on ten real-world multi-view datasets using NMI, ACC, and PUR against eleven baseline methods. It generally achieves the strongest clustering performance while remaining computationally feasible for large datasets.

  • Baseline methods and settings: UDBGL is compared with eleven baseline multi-view clustering methods, including both general graph-learning and bipartite graph-based approaches.The experiments repeat each method 20 times and report average scores and standard deviations.
  • Comparison with other MVC methods: UDBGL outperforms all baselines in NMI on nine of ten datasets, although FPMVS-CAG scores higher on Out-Scene.The paper reports that bipartite graph methods generally handle large datasets more efficiently than general graph-based methods.
  • Comparison with other MVC methods: 43.60, 50.71, and 54.74 are UDBGL's average NMI(%), ACC(%), and PUR(%) scores across the benchmark datasets.The corresponding second-best averages are 36.20, 46.73, and 50.33, respectively.
  • Comparison with other MVC methods: 1.10, 1.50, and 1.40 are UDBGL's average ranks for NMI, ACC, and PUR, compared with second-best ranks of 3.70, 3.50, and 3.80.These rankings summarize performance across the benchmark datasets.

D. Parameter Analysis

UDBGL is evaluated under varying regularization, fusion, and anchor-count settings. Moderate α and β values generally help, while setting the anchor number to the cluster count is robust on most datasets.

  • Experimental setup: The parameter analysis varies α, β, and the number of anchors m to assess their influence on UDBGL.The anchor-count experiments use values ranging from c to 200 where applicable.
  • Hyper-parameters: Moderate α and β values generally benefit clustering performance across various datasets.α and β negotiate the regularization and graph-fusion terms.
  • Number of anchors: Setting the anchor number equal to the cluster number c produces quite robust clustering results on most datasets.The tested anchor counts are drawn from {c, 50, 100, 200}, subject to being at least c.

E. Empirical Convergence Analysis

UDBGL generally converges quickly and remains computationally practical on large datasets. Its unified formulation couples view-specific and consensus graph learning with discrete cluster-structure learning, while experiments assess convergence, ablation, and execution time.

  • Convergence: The objective value decreases very fast and generally converges within twenty iterations across various datasets.This indicates the reported good convergence property of UDBGL.
  • Ablation analysis: The ablation study compares UDBGL's single-phase formulation with variants that remove view-specific graph learning or split the model into two phases.The study also considers pre-constructed K-nearest-neighbor graphs followed by graph fusion.
  • Execution time: UDBGL is computationally feasible on the eight larger datasets, with time cost comparable to MSGL, SMVSC, and FP.Several competing methods are infeasible on four datasets containing over 30,000 samples, while seven bipartite graph methods remain feasible.
  • Unified formulation: UDBGL jointly learns view-specific and view-consensus bipartite graphs, couples them with a Laplacian low-rank constraint, and directly obtains discrete cluster structure.Its alternating minimization algorithm has computational complexity linear to the data size.
Loading 2209.04187v2…