Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity

In plain words

Clustering sorts unlabelled items into groups. When every item is described by several feature sets, called views (for example colour and texture features of the same image), the usual methods either merge all views at once, or cluster each view on its own and merge the results afterwards. This paper asks whether merging in several partial rounds can be more accurate and still cheap enough for very large datasets.

The method, FastMICE, works like many small committees formed at random. Each committee looks at a random subset of the views and draws a rough map of how the items relate. It uses a small set of representative points instead of comparing every item with every other item. Each map is cut into groups, which gives one partial answer per committee. A final step combines all the partial answers into one clustering. The randomness makes the partial answers differ from each other, and the authors argue that this makes the combined answer more robust.

The appeal is speed and convenience. The authors report that the cost grows roughly in line with the number of items, and that the method needs no tuning of settings for each dataset. On the largest dataset in their study, the other methods they tried ran out of memory, and FastMICE finished.

TL;DR

• FastMICE is an ensemble clustering method for multi-view data: random groups of views, each turned into an anchor-based bipartite graph and partitioned, then one consensus partition §3.
• It is designed to have almost linear time and space complexity in the number of samples N, and to need no dataset-specific hyperparameter tuning §1 §3.6.
• Author-reported: best average NMI rank on 22 datasets (1.23, next best 4.41), and the only method that completes YTF-400 with 398,191 samples tab. 3 §4.3 tab. 7.
• Before you implement it, read "Paper vs code": the official MATLAB code differs from the text in a scaling factor, a row normalisation, and in the k-means settings, which the paper does not state.

Problem

Multi-view clustering combines information from several views of the same samples. Many such methods build an N-by-N affinity matrix, which takes O(N²d) time and O(N²) space, and then run spectral clustering, which needs an SVD and takes O(N³) time §1. Most methods fuse views in a single stage, either early (all views in one model) or late (cluster each view, then fuse), and few explore multi-stage fusion §1 §2.1. Anchor-based methods scale better, but they either share one anchor set across all views or learn one per view, and many of them need dataset-specific tuning of several hyperparameters §1 §2.1. The stated aim is a method that scales, fuses in more than one stage, and runs without per-dataset tuning §1.

Method

The paper describes four stages §3. Symbols follow the paper: N samples, V views, M random view groups (= base clusterings = ensemble size), p anchors per group, K nearest anchors per sample, k final clusters, k_c = Σ k^(m) clusters over all base clusterings §3.1 tab. 1.

1. Random view groups §3.2. Draw M groups. Group m holds V^(m) view members, with V^(m) chosen at random in [V_min, V_max] = [1, V] §3.2 eq. 1 eq. 2. Early fusion and late fusion are the special cases of one group with all views and of V groups with one view each §3.2.
2. View-sharing bipartite graph per group §3.3. For each member v of group m:
   • Feature-level diversity: keep a random fraction τ of the member's columns, with τ in [τ_min, τ_max] and a ceiling on the count §3.3.
   • Anchor-level diversity: choose p̄ = ⌈p / V^(m)⌉ anchors from the sampled features by hybrid representative selection §3.3, cites huang19_tkde.
   • Neighbourhood-level diversity: link each sample to its K̄ = ⌈K / V^(m)⌉ nearest anchors, with a Gaussian similarity, and set all other entries to zero §3.3 eq. 5.
   • Normalise each row of the member's cross-affinity matrix to unit norm, then concatenate the members column-wise into B^(m) §3.3. The group graph therefore has p̄·V^(m) anchors, which lies in [p, p + V) §3.3.
3. Base clustering §3.4. Draw k^(m) from [k_min, k_max] (experiments use [k, 2k], §4.2). Partition B^(m) with the transfer cut: solve a small eigenproblem on the anchor graph eq. 8 eq. 9, map each eigenvalue to λ with δ = λ(2 − λ) eq. 10, lift the eigenvectors to the samples eq. 11, then run k-means on the sample rows §3.4.
4. Consensus §3.5. Stack the M base clusterings into one N × k_c binary matrix B with exactly M ones per row eq. 14. Apply the same transfer cut with k clusters to get the final labels §3.5.

The paper has no algorithm box. The pseudocode below is our summary of the text, with the code's behaviour noted where it differs FastMICE_EnsembleGeneration.m Tcut_for_bipartite_graph.m.

# FastMICE, from the text (no algorithm box in the paper)  [§3]
# Input:  views: V matrices of shape (N, d_v); k; M, p, K
# Output: labels: (N,) cluster ids in 0..k-1

def fastmice(views, k, M=20, p=1000, K=5):
    # Stage 1: M random view groups, each with 1..V members  [§3.2] [eq. 1]
    groups = [random_view_group(num_views) for m in range(M)]
    base_labels = []
    for group in groups:
        # Anchors and neighbours are shared evenly across members  [§3.3]
        p_bar = ceil(p / len(group))
        K_bar = ceil(K / len(group))
        blocks = []
        for view in group:
            # Feature-level diversity: keep a random fraction of columns  [§3.3]
            ratio = uniform(0.2, 0.8)     # range from experiments [§4.2]
            X = random_columns(views[view], ceil(ratio * dim_of(view)))
            # Anchor-level diversity: p_bar representatives of X  [§3.3]
            anchors = hybrid_representatives(X, p_bar)
            # Neighbourhood-level diversity: K_bar nearest anchors  [§3.3]
            blocks.append(gaussian_affinity(X, anchors, K_bar))
        # Concatenate member graphs; rows of each block have unit norm  [§3.3]
        B_m = hstack(blocks)                            # (N, p_bar * |group|)
        # Base clustering with k_m clusters  [§3.4]
        k_m = random_int(k, 2 * k)
        base_labels.append(transfer_cut(B_m, k_m))
    # Stage 4: unify the base clusterings in one bipartite graph  [§3.5]
    B = one_hot_union(base_labels)          # (N, k_c), M ones per row
    return transfer_cut(B, k)

# Transfer cut on a cross-affinity matrix B of shape (N, q)  [§3.4]
# Output: k cluster labels for the N samples

def transfer_cut(B, k):
    # Degree of each sample: row sums of B  [§3.4]
    sample_degree = B.sum(axis=1)                       # (N,)
    # Reduced graph on the q anchors: E_s = B^T D^-1 B  [§3.4]
    anchor_affinity = B.T @ (B / sample_degree[:, None])    # (q, q)
    # Smallest k eigenpairs (delta_i, u_i) of L_s u = delta D_s u  [eq. 9]
    deltas, u = smallest_generalized_eigenpairs(anchor_affinity, k)
    # Recover lambda from delta = lambda (2 - lambda)  [eq. 10]
    lam = 1 - sqrt(1 - deltas)                          # (k,)
    # Lift to the samples: h = D^-1 B u / (1 - lambda)  [eq. 11]
    embedding = (B / sample_degree[:, None]) @ u / (1 - lam)    # (N, k)
    # Discretise the N sample rows with k-means  [§3.4]
    return kmeans(embedding, k)

Key equations, as written in the paper (symbols as in §3.4):

L^{(m)} y^{(m)} = \lambda^{(m)} D^{(m)} y^{(m)} eq. 8

L_s^{(m)} u^{(m)} = \delta^{(m)} D_s^{(m)} u^{(m)}, \quad E_s^{(m)} = (B^{(m)})^\top (\hat{D}^{(m)})^{-1} B^{(m)} eq. 9 §3.4

\lambda_i (2 - \lambda_i) = \delta_i, \qquad y_i = \begin{bmatrix} h_i \\ u_i \end{bmatrix}, \qquad h_i = (\hat{D})^{-1} B\, u_i \,/\, (1 - \lambda_i) eq. 10 eq. 11

b_{ij} = \begin{cases} Sim(\tilde{x}_i, a_j) & \text{if } a_j \in \mathcal{N}_{\bar K}(\tilde{x}_i) \\ 0 & \text{otherwise} \end{cases} eq. 5

b_{ij} = \begin{cases} 1 & \text{if } x_i \in C_j \\ 0 & \text{otherwise} \end{cases} eq. 14

The paper leaves some details open: the distribution of the random draws, the Gaussian bandwidth, and how the anchors are chosen (cited to huang19_tkde). The Hyperparameters table and Pitfalls say how the code resolves them.

Hyperparameters

The paper has no single hyperparameter table. Values come from §4.2 and the sensitivity sections, plus the code defaults. "Not stated" means the paper does not give the value.

Results

Author-reported. Setup: 22 multi-view datasets, 10 general-scale and 12 large-scale tab. 2 §4.1. Metrics are NMI, ARI, ACC and PUR, each averaged over 20 runs tab. 3 to tab. 6. Hardware: Intel i5-6600 CPU, 16 GB RAM §4. Ten baselines §4.2. Entries marked N/A ran out of memory. Where only four methods are feasible, the paper gives the other seven a shared fifth place §4.3.

Headline numbers:

Scalability, running time in seconds tab. 7 §4.8: on YTF-200 (286,006 samples) FastMICE takes 263.81 s, LMVSC 3,184.79 s, SMVSC 74,063.30 s and FPMVS-CAG 32,974.03 s. On YTF-400 (398,191 samples) FastMICE takes 652.05 s and is the only method that completes. The tuning time of baselines is listed separately in tab. 7.

Sensitivity (described in text; figure values are not stated in the text):

• fig. 3: NMI against ensemble size M, for FastMICE and the three ensemble baselines. FastMICE stays consistently high across M, and larger M is reported as beneficial. The ensemble baselines do not run beyond NH-4660 §4.4.
• fig. 4: NMI against anchors p from 100 to 1400. Performance is consistent, and larger p is reported as beneficial on most datasets, especially YTF-200 and YTF-400 §4.5.
• fig. 5: NMI against K from 1 to 10. A moderate K is reported as beneficial on most datasets; the paper suggests [4, 8] §4.6.
• fig. 6: random view groups against one view per group and against all views in one group. Random groups are reported as better on most datasets; all-view groups are comparable on Yale §4.7.

Dataset details tab. 2:

NMI (%), mean ± standard deviation over 20 runs, best in bold, best overall in [brackets] tab. 3:

ARI (%) tab. 4:

ACC (%) tab. 5:

PUR (%) tab. 6:

Running time in seconds, tuning and running separately tab. 7. "-" means no dataset-specific tuning is needed. The paper prints the M²VEC (km) and M²VEC (spec) columns as one merged cell, so both columns show the same tuning time.

Paper vs code

Official code: https://github.com/huangdonghere/FastMICE at 7feccc0cd035812e16da78265464838b3c2db282. The repository owner name matches the first author, and the README's contact address matches the first author's e-mail in the paper README.md. The repository has no LICENSE file. The code is MATLAB, tested on R2019b under Windows 10 README.md runFastMICE.m. The README cites the published version as IEEE TKDE 2023 (35(11), pp. 11388-11402). This card follows the arXiv v4 text, which the arXiv metadata dates 2023-01-24.

Discrepancies between the text and the code:

1. Scaling of the spectral embedding. Eq. 11 divides h by (1 − λ), and by Eq. 10 this equals √(1 − δ) §3.4 eq. 10 eq. 11. The code computes D⁻¹Bu without this division Tcut_for_bipartite_graph.m.
2. Row normalisation and distance. The text runs "k-means discretization" on the stacked eigenvectors and does not mention row normalisation §3.4. The code normalises each row to unit length and runs k-means with cosine distance Tcut_for_bipartite_graph.m.
3. Similarity for cosine data. The text allows any similarity §3.3. For cosine distance the code uses 1 − distance FastMICE_EnsembleGeneration.m. For Euclidean data it uses a Gaussian with σ equal to the mean of all K̄-NN distances in that view member FastMICE_EnsembleGeneration.m. The paper gives no bandwidth.
4. Anchor search. The text says "approximate K-NN computation", citing huang19_tkde §3.3. The code searches only the candidate set of each sample's nearest representative, with the sizes given in "Hyperparameters" FastMICE_EnsembleGeneration.m.
5. Consensus k-means. The paper gives no iteration count. runFastMICE.m passes 20 iterations and 5 replicates runFastMICE.m. The function's own defaults are 100 and 3 FastMICE_ConsensusFunction.m.
6. Empty clusters. The text defines k_c as the total number of clusters in all base clusterings §3.5. The code removes clusters that no sample belongs to before the consensus step FastMICE_ConsensusFunction.m.
7. Distributions. The text says "randomly chosen" for view members, feature ratios and cluster counts §3.2 §3.3 §3.4. The code draws all three uniformly FastMICE_EnsembleGeneration.m FastMICE_EnsembleGeneration.m FastMICE_EnsembleGeneration.m.
8. Seeding. The code reseeds from the clock before each random step, so runs are not reproducible FastMICE_EnsembleGeneration.m FastMICE_EnsembleGeneration.m. The paper states no seed.
9. Number of runs. The tables average 20 runs tab. 3 to tab. 6. The demo defaults to 5 runs demo_1.m.
10. Demo output. The demo prints the NMI value on the ARI, ACC and PUR lines demo_1.m. The stored scores are in the right order: NMI, ARI, ACC, PUR computeFourClusteringMetrics.m. Only the printed text is wrong.
11. Default arguments. Each default in runFastMICE is guarded by nargin < 3, so calls with 3 to 5 arguments leave some defaults unset and fail runFastMICE.m. Calls with 2 or 6 arguments work.
12. Cluster count in the demo. The demo sets k to the number of ground-truth classes demo_1.m. The text treats k as an input §3.4.
13. Metrics. NMI is normalised by √(H(x)H(y)) computeFourClusteringMetrics.m. ACC uses Hungarian matching computeFourClusteringMetrics.m. The text names the metrics but gives no formulas §4.2.
14. Eigenvalue path. The code uses a dense eigendecomposition of the p × p matrix and keeps the top eigenvectors of the normalised matrix Tcut_for_bipartite_graph.m. This matches the reduced problem in the text eq. 9 up to normalisation.

Pitfalls

• Scaling and normalisation (item 1 and 2 above). Pick one and document it. The text's version and the code's version can give different partitions, because row normalisation depends on the per-column scale. We have not measured the effect.
• Gaussian bandwidth. The text gives no bandwidth. Following the code, σ is the mean K̄-NN distance over the whole view member, with a small eps for safety FastMICE_EnsembleGeneration.m. If distances are all zero, the eps guard is the only protection.
• Anchor and neighbour counts per group. The total anchors per group is p̄·V^(m), which lies in [p, p + V). The total neighbours per sample is K̄·V^(m), which lies in [K, K + V) §3.3. Do not assume exactly p anchors.
• Few columns. If a graph has fewer columns than k, the code pads it with a zero column so that it has k columns Tcut_for_bipartite_graph.m. The paper says nothing about this case. Check the anchor count and log it.
• Hidden cubic costs. The text's overall complexity O(NMp^{1/2}V^{1/2}) assumes k, K, M, V ≪ p ≪ N and drops the M·p³ term from the M eigenproblems and the k_c³ term from the consensus §3.6.1. With p = 1000, each eigenproblem is a dense 1000 × 1000 eigendecomposition in the code Tcut_for_bipartite_graph.m.
• Space. The text gives O(N(K + V + k + M)) §3.6.2. The matrices are sparse with N·K̄·V non-zeros for the anchor graph and N·M for the consensus graph §3.3 §3.5.
• "Tuning-free" has conditions. The method needs k, and the distance must be chosen by the user (cosine for text) §4.2 runFastMICE.m. The values of M, p and K are fixed across datasets §4.2, and the sensitivity curves are described in words only fig. 3 fig. 4 fig. 5.
• Run-to-run variance. Several entries have standard deviations of 5 or more tab. 3 tab. 4 tab. 5. A single run may differ much from the reported mean. Average at least 20 seeds, as the paper does.
• Baseline cells with ± 0.00. The captions say each value is an average over 20 runs, yet many baseline cells show ± 0.00 tab. 3. The paper does not explain this.
• Average ranks. For a dataset where only four methods run, the other seven share fifth place §4.3. The ranks therefore reward being feasible as well as accurate. Read the ranks with the N/A counts in mind.
• Text–table mismatches. The text says the PUR comparison covers "twenty" datasets, and the rank comparison says "twenty datasets" §4.3. There are 22 tab. 2. The dataset is called "Out-Scene" in tab. 2 and tab. 7, and "OutdoorScene" in tab. 3 to tab. 6. This card uses the table names.
• Typo in tab. 7. Citeseer, MVEC, TuneTime is printed as "37,1374.01". We could not verify the intended value.
• Figures. The sensitivity figures fig. 3 to fig. 6 carry the results, but the text does not give their values. Do not read numbers off the figures into implementation settings without checking the source.
• Other data. The code ships data_ALOI.mat and data_OutScene.mat only. The other datasets must be obtained separately; we have not checked their terms.

Lineage

• Builds on: the hybrid representative selection and approximate K-NN of "Ultra-Scalable Spectral Clustering and Ensemble Clustering" §3.3 FastMICE_EnsembleGeneration.m; the transfer cut of Li et al., "Segmentation using superpixels: A bipartite graph partitioning approach" (CVPR 2012) §3.4; and conventional spectral clustering §3.4.
• Compared against §4.2: MVSC (large-scale multi-view spectral clustering via bipartite graph); AMGL; SwMC; MVEC and M²VEC (ensemble-based multi-view clustering, with k-means and spectral final steps); BMVC; LMVSC; SMVSC; and FPMVS-CAG.
• Superseded by: not known from the content in this wiki.