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

In plain words

Data about the same things often arrives from several sources, such as an image described by texture, colour and shape features. Clustering that data means grouping the items so that similar ones share a group. The usual graph-based methods connect every item to every other item, which becomes too slow for large datasets. They also usually split the work into two stages: build a graph, then run a separate step such as k-means to read off the groups.

This paper works with a small set of landmark points called anchors. Each item is linked only to these anchors, which gives a much smaller item-to-anchor graph. The method learns one such graph per source, then merges them into one shared graph in which each source gets a learned weight. The shared graph is pushed to split into exactly as many separate pieces as there are clusters, so the pieces themselves are the answer. All of these steps are optimised together, and the authors report that the cost grows linearly with the number of items.

TL;DR

• UDBGL is a graph-based multi-view clustering method that learns per-view anchor graphs and a consensus graph jointly §3.4.
• A Laplacian rank constraint makes the consensus graph have exactly c connected components, so the clusters are read directly from the graph and no k-means step is needed §3.3.
• The optimisation is alternating over three blocks (consensus graph, per-view graphs, view weights), with closed-form or QP sub-steps §4.
• Author-reported: best average NMI, ACC and PUR over ten datasets, the largest of which has 60,000 samples §5.3, tab. 3–5.
• The official MATLAB code exists but has several deviations from the paper; read "Paper vs code" before reimplementing.

Problem

Graph-based multi-view clustering builds an n×n graph, which costs O(n²) time to construct and may cost O(n³) to partition by spectral methods §1. Methods that learn graphs per view and then fuse them either pre-build the view graphs, or learn them and concatenate them heuristically, so the view-specific and consensus graphs are not learned jointly §1, §4. Many bipartite-graph methods still run k-means on the spectral embedding afterwards, which can make the result unstable §2. The paper targets large data where all three problems must be solved together §1.

Method

Notation: n samples, c clusters, V views, m anchors, d^(v) features in view v; X^(v) is d^(v)×n, Z^(v) is n×m, P is n×m, A^(v) is d^(v)×m, δ is a view-weight vector on the simplex tab. 1.

Step 1: anchors and per-view graphs §3.2. Each view is first normalised alg. 1. Anchors are obtained by k-means on the concatenated features, and the resulting centres are split by view §3.2, alg. 1. The sample-to-anchor self-representation of view v is Z^(v), which is non-negative with unit row sums; each row is a bipartite graph row §3.2, eq. 3. The per-view objective is a squared reconstruction error plus a Frobenius penalty on Z^(v) eq. 3.

Step 2: fusion with a rank constraint §3.3. The view graphs are fused as a weighted sum with weights δ on the simplex, and the consensus graph P is pulled toward that sum eq. 4. P is row-stochastic eq. 4. The bipartite graph is turned into a symmetric (n+m)×(n+m) graph S with P in the off-diagonal block eq. 7. By Lemma 1 (a standard spectral fact, cited from von Luxburg and SFMC), the multiplicity of the zero eigenvalue of the normalised Laplacian of S equals its number of connected components §3.3, lemma 1. The paper therefore imposes rank(L̃_S) = n+m−c, which makes P have c connected components §3.3, eq. 9. Clusters are then read off the connected components of P §3.3.

Step 3: unified objective §3.4. The per-view objectives eq. 3 and the fusion term are summed with weight β. The final problem is eq. 10:

• minimise, over Z^(v), P and δ, the sum over views of ||X^(v) − A^(v)(Z^(v))ᵀ||²_F + α||Z^(v)||²_F, plus β||Σ_v δ^(v) Z^(v) − P||²_F;
• subject to Z^(v) ≥ 0 with unit row sums, δ on the simplex, P row-stochastic and non-negative, and rank(L̃_S) = n+m−c eq. 10.

α > 0 and β > 0 are hyper-parameters §3.1, §3.4.

Step 4: alternating optimisation §4, alg. 1. Each iteration updates P, then every Z^(v), then δ, each with the others fixed §4.

P update §4.1. The rank constraint is handled through an auxiliary indicator F with orthonormal columns, and the subproblem becomes eq. 12 with a weight γ on a Laplacian trace term eq. 11–12. F and P are alternated. F has a closed form: with the degree-normalised B = Σ_v δ^(v) Z^(v), take the c largest left and right singular vectors of D_n^(−1/2) P D_m^(−1/2), scale them by √2/2, and stack them §4.1, text after eq. 13. Given F, each entry gets a squared distance q_ij between the scaled sample and anchor embeddings eq. 17, and each row of P is the Euclidean projection onto the simplex of (b_i − (γ/2) q_i), where b_ij are the entries of B eq. 17–18. The paper says the simplex projection has a closed form and cites an external source for it §4.1. γ is doubled when P has too few zero-eigenvalue components and halved when it has too many, starting from 0.1 alg. 1.

Z update §4.2. Each row of each Z^(v) is solved independently as a quadratic programme on the simplex eq. 21. The Hessian is H̄ = (A^(v))ᵀA^(v) + (α + β(δ^(v))²)I and the linear term is f̄ = −2(A^(v))ᵀx_j + 2βδ^(v)(Σ_{i≠v} δ^(i) z^(i)_j − p_j) eq. 22. The paper solves it with an augmented Lagrangian method §4.2.

δ update §4.3. Each Z^(v) is vectorised column by column into a vector of length nm and the vectors are stacked into a matrix Ẑ, so that Σ_v δ^(v)Z^(v) becomes Ẑδ eq. 24. The δ subproblem is then a convex QP on the simplex with H = ẐᵀẐ and f = 2Ẑᵀp̂ eq. 25. It is solved with an augmented Lagrangian: a split variable ρ, multiplier η and penalty μ that doubles each inner iteration eq. 26–30, alg. 1.

Algorithm 1 alg. 1. Normalise the views; k-means on the concatenated features gives the anchors; δ = 1/V; each Z^(v) starts as a K-nearest-neighbour bipartite graph. Repeat: update P (with inner loop on γ until P has c components), update all Z^(v), update δ, until convergence or a maximum iteration count. The final clustering comes directly from P alg. 1.

# UDBGL outer loop  [alg. 1]
# Input:  views X[v] of shape (n, d_v); c clusters; m >= c anchors;
#         alpha > 0, beta > 0
# Output: labels read from the c-component bipartite graph P
def udbgl(views, c, m, alpha, beta):
    # Normalise each view, then k-means on the concatenated features
    # gives m anchors, split back by view  [alg. 1] [§3.2]
    anchors = split_by_view(kmeans(concat(views), m))
    # Start with equal view weights and K-NN bipartite graphs  [alg. 1]
    delta = ones(V) / V
    Z = [knn_bipartite(views[v], anchors[v]) for v in range(V)]
    # Repeat until convergence or a maximum iteration count  [alg. 1]
    while not converged:
        # Fuse the weighted view graphs and update P  [§4.1] [eq. 11]
        B = sum(delta[v] * Z[v] for v in range(V))   # (n, m)
        P = update_P(B, c)
        # Update each view's Z row by row  [§4.2] [eq. 21]
        for v in range(V):
            Z[v] = update_Z(views[v], anchors[v], Z, delta, P, v,
                            alpha, beta)
        # Update the view weights on the simplex  [§4.3] [eq. 25]
        delta = update_delta(Z, P)
    return P

# Update P so that its bipartite graph has c connected components  [§4.1]
# B: (n, m) weighted sum of the view graphs
def update_P(B, c):
    # Start gamma at 0.1 and seed P with B  [alg. 1]
    gamma = 0.1
    P = B
    # Repeat until P has c connected components  [alg. 1] [§4.1]
    while not has_c_components(P, c):
        # Recompute F from the degree-normalised P  [§4.1, eq. 13]
        F_n, F_m = top_c_singular_vectors(P, c) * sqrt(2) / 2
        # Scale sample and anchor embeddings by their degrees  [eq. 17]
        samples = F_n / sqrt(P.sum(axis=1))[:, None]     # (n, c)
        anchors = F_m / sqrt(P.sum(axis=0))[:, None]     # (m, c)
        # Squared distance between each sample and anchor  [eq. 17]
        q = squared_distance(samples, anchors)           # (n, m)
        # Row-wise projection onto the simplex  [eq. 18] [§4.1]
        P = project_rows_to_simplex(B - gamma * q / 2)
        # Double gamma if too few components, halve if too many  [alg. 1]
        gamma = adjust_gamma(gamma, P, c)
    return P

# Update one view's Z, one row per sample  [§4.2] [eq. 21] [eq. 22]
# x: (n, d) samples; A: (d, m) anchors; Z: list of (n, m) per view
def update_Z(x, A, Z, delta, P, v, alpha, beta):
    # Hessian from the anchors and the two regularisers  [eq. 22]
    H = A.T @ A + (alpha + beta * delta[v] ** 2) * I    # (m, m)
    # Coupling to the other views' graphs  [eq. 22]
    others = sum(delta[i] * Z[i] for i in range(V) if i != v)
    for j in range(n):
        # Linear term: pull toward x_j through A, and toward P  [eq. 22]
        f = -2 * A.T @ x[j] + 2 * beta * delta[v] * (others[j] - P[j])
        # Solve min z H z' + z f with z >= 0 and sum(z) = 1  [eq. 21]
        Z[v][j] = solve_simplex_qp(H, f)
    return Z[v]

# Update the view weights on the simplex  [§4.3] [eq. 24] [eq. 25]
# Z: list of (n, m) per view; P: (n, m) consensus graph
def update_delta(Z, P):
    # Stack each view's Z column by column into one vector  [eq. 24]
    Z_hat = stack([vec_colwise(Z[v]) for v in range(V)], axis=1)  # (nm, V)
    p_hat = vec_colwise(P)                                        # (nm,)
    # Quadratic form and linear term of the view-weight QP  [eq. 25]
    H = Z_hat.T @ Z_hat                                           # (V, V)
    g = -2 * Z_hat.T @ p_hat                                      # (V,)
    # Solve min d H d' + d g with d >= 0 and sum(d) = 1  [eq. 25]
    return solve_simplex_qp(H, g)

Key equations: the unified objective eq. 10; the Z-row QP eq. 21–22; the δ QP eq. 25.

Complexity §4.4. The paper states costs per step: k-means O(ndmt₁), P update O(nmct₂ + nm²t₂ + m³t₂), Z updates O(nm²d) in total, and δ update O(V²nm), where t₁ and t₂ are iteration counts. With n ≫ m and c, V, t₂ treated as constants, the total is linear in n §4.4.

Convergence §4.5. The Z-row QP and the δ QP are convex and solved to optimality. The P sub-problem is not guaranteed to be monotone, because γ is adjusted to reach a c-component graph §4.5. The authors report objective curves that decrease fast and generally converge within about twenty iterations on the benchmark datasets §5.5, fig. 4.

Hyperparameters

Demo values in the official repository for Out-Scene: m = c, α = 10⁻³, β = 10⁻⁵ demo_UDBGL.m. These are not paper-reported per-dataset values, and β lies outside the tuning grid of §5.2.

Results

Author-reported. Setup: ten real-world multi-view datasets with between 187 and 60,000 samples and 2 to 4 views tab. 2, §5.1; eleven baselines, of which seven are bipartite-graph methods §5.2; metrics NMI, ACC and PUR, each averaged over 20 runs §5.2. Out-of-memory baselines are marked N/A tab. 3–5.

Dataset details tab. 2:

NMI in percent, mean ± std over 20 runs, best in bold tab. 3:

ACC in percent tab. 4:

PUR in percent tab. 5:

Headline (author-reported): UDBGL has the highest average NMI, ACC and PUR (43.60, 50.71, 54.74), against 36.20, 46.73 and 50.33 for the second-best method, SMVSC. Its average ranks are 1.10, 1.50 and 1.40 §5.3, tab. 3–5. On NMI it is best on nine of ten datasets; FPMVS-CAG is higher on Out-Scene (53.04 vs 52.45) §5.3, tab. 3. Ablation (two-phase variants and a variant without view-specific learning) is reported only as a figure, which the authors say is less stable across datasets §5.6, fig. 5. Execution time is shown as a figure only, with the claim that UDBGL is comparable to MSGL, SMVSC and FPMVS-CAG on most datasets §5.7, fig. 6. Parameter sensitivity over α and β fig. 2 and over the number of anchors fig. 3 is also figure-only.

Paper vs code

Repository: https://github.com/huangdonghere/UDBGL, linked in the abstract, with an owner name matching the handle of an author's e-mail in the front matter. The clone is at commit 93c1de0513bb7adcba132393940d1dd78346b34b. It has no LICENSE file, so the code licence is not stated, and no code is quoted in this card. The repository has MATLAB files UDBGL.m, demo_UDBGL.m and NMImax.m, plus one data file, data_OutScene.mat. The other nine datasets are not included.

Checked and matching: the Z-row QP's Hessian and linear term UDBGL.m equal eq. 22, up to the ½ convention of the QP solver, which gives the same argmin; the δ objective UDBGL.m equals eq. 25; the update order P → Z → δ and the initial δ = 1/V UDBGL.m follow alg. 1.

Discrepancies:

• Anchors. Paper: k-means on the concatenated features alg. 1. Code: when n > 10,000, k-means runs on a random 10,000-row subset, with a fixed seed UDBGL.m.
• Z and δ solvers. Paper: augmented Lagrangian for both §4.2, §4.3. Code: exact QP per row for Z, with parfor UDBGL.m, and quadprog for δ UDBGL.m.
• P sub-problem. Paper: row-wise simplex projection over all m entries of each row eq. 18. Code: projects rows and columns of B separately over the support of B only, so entries that are zero in B stay zero coclustering_bipartite_fast1. The returned P is the average (S + Sᵀ_m)/2 coclustering_bipartite_fast1, which does not in general have unit row sums, unlike the constraint P1 = 1 eq. 10. The code's own degree normalisation is applied only to the spectral step after this.
• γ update and stopping. Paper: double γ if P has fewer than c zero-eigenvalue components, halve if more, stop at exactly c alg. 1. Code: uses the sum of the top-c eigenvalues of the normalised bipartite affinity, doubles γ if that sum is below c, and otherwise halves it coclustering_bipartite_fast1. At exactly c components that sum equals c, so the code halves γ rather than stopping. The else break at line 1109 is reached only if the sum is NaN. In practice the P step runs its full 50 iterations UDBGL.m.
• Revert on γ halving. The code restores U and V from U_old, but U_old is set after U has been recomputed at line 1076 and line 1099, so the restore has no effect coclustering_bipartite_fast1.
• Component check. Paper: the output has c connected components alg. 1. Code: the labels are the connected components of the final graph, and the check against c is commented out coclustering_bipartite_fast1. The number of clusters can differ from c without warning.
• Initial K-NN graph. Paper: K not stated. Code: K = 5 and Gaussian weights exp(−d²/(2σ²)) with σ equal to the mean squared distance, normalised per row UDBGL.m.
• Constants not in the paper. Initial column scaling D₂ = 10 for the first P iteration coclustering_bipartite_fast1; NMI normalised by max(H(x), H(y)) NMImax.m. The paper does not give the NMI formula.
• Outer loop. The code's maximum is 20 outer iterations, with a stopping tolerance of 10⁻⁵ on the objective or on δ UDBGL.m.
• Anchor count. The paper requires m ≥ c alg. 1; the code does not check it UDBGL.m.
• Evaluation. Paper: 20 runs per dataset §5.2. Code: one fixed seed (5489) in each call UDBGL.m. No script for the 20-run protocol is included.
• Demo values. The Out-Scene demo uses β = 10⁻⁵, which lies outside the grid in §5.2 demo_UDBGL.m.
• Software. Tested in MATLAB R2019b on Windows 10 UDBGL.m. The code calls quadprog (Optimization Toolbox) and graphconncomp, which is not in the repository. The README does not list the toolboxes.

Pitfalls

• Unstated constants. K for the initial graph, the k-means settings for anchors, the outer and inner iteration limits, the convergence tolerance and the normalisation formula are all missing from the paper. The code's values are listed in Hyperparameters, and a reimplementation should choose and report its own.
• Component count is not guaranteed. The method's central promise is that P has exactly c connected components. Given the γ logic described above, check the count after running and report it; do not assume it.
• P is not row-stochastic in the code. If you reimplement from the official code, the P passed to the Z and δ updates is not row-normalised. Decide which behaviour you want and state it.
• Cost is dominated by dense n×m matrices and per-row QPs. The code builds dense n×m matrices in the P step coclustering_bipartite_fast1 and solves one QP per sample per view in each outer iteration UDBGL.m. The linear-time claim §4.4 assumes n ≫ m and fixed c, V and t₂; the code's fixed 50 inner iterations make t₂ larger than a converged run would need.
• Data normalisation. Min–max scaling per feature sets NaN results to 1, which matters for constant features UDBGL.m.
• Results. All numbers are author-reported with one run protocol and no released harness. The official repository contains only Out-Scene, so the other nine rows cannot be checked from the repository. N/A entries mean out-of-memory for that baseline on that dataset, not for UDBGL.
• Numbering. Tables and figures are numbered in order of appearance in the source: notations is tab. 1, datasets tab. 2, NMI tab. 3, ACC tab. 4, PUR tab. 5; framework fig. 1, α/β sensitivity fig. 2, anchor count fig. 3, convergence fig. 4, ablation fig. 5, time fig. 6. The journal typesetting may print these differently.

Lineage

• Builds on: the anchor-based subspace model of Kang et al. (LMVSC) §1, §3.2; the bipartite fusion with a rank constraint of Li et al. (SFMC), from which Lemma 1 and the F update come §3.3, §4.1; and the bipartite co-clustering work of Nie et al. §4.1.
• Compared against: MVSC, AMGL, MLAN, SwMC, MVCTM, SFMC, LMVSC, MSGL, SMVSC, FPMVS-CAG and EOMSC-CA §5.2.
• Superseded by: not known from content in this wiki.