Deep clustering

Overview

Deep clustering partitions unlabelled items into K groups while a neural network learns the item representation. The core loop is: embed the items, compare each embedding with K cluster centres, turn those comparisons into a target, and pull the network toward that target. The two cards differ in where the target comes from.

• DFCN builds its target from soft assignments of the fused embedding to K learned centres, and refreshes it during training. The paper refreshes it every T iterations, with T not stated 2012.09600 alg. 1. The centres start from K-means on the embeddings 2012.09600 alg. 1.
• PiCIE re-clusters all pixel features once per epoch with k-means, labels each pixel by its nearest centroid, and trains the network against those labels for that epoch 2103.17070 §3.1 2103.17070 §3.3.

For attributed graphs (items with their own features and links between items), the design question is which view feeds the target. DFCN fuses a feature-only encoder with a graph encoder and builds the target from both 2012.09600 §Triplet Self-supervised Strategy. For images, the design question is which invariances the clusters must respect. PiCIE asks the clusters to agree across colour changes and to follow geometric transforms 2103.17070 §3.3.

This page covers two papers, from two domains. The variants below are the ones these papers vary, not a survey of the field. All numbers are author-reported.

Variants

Fusion of feature and graph encoders (DFCN)

DFCN trains an autoencoder (AE) and an improved graph autoencoder (IGAE) together. A learned fusion module (SAIF) mixes their embeddings and smooths them over the graph. A Student-t kernel gives soft assignments of the fused embedding to K centres, and a sharpened target is built from them. A triplet KL loss pulls the assignments of all three embeddings toward that target 2012.09600 eq. 6–12. Card: Deep Fusion Clustering Network.

The fusion uses a linear mix with weight alpha, one graph-smoothing step, a softmax over inner products between nodes, and a skip connection with weight beta 2012.09600 eq. 6–9. The paper initialises beta at zero, following DANet 2012.09600 §Structure and Attribute Information Fusion.

Per-pixel prototype clustering with invariance and equivariance (PiCIE)

PiCIE clusters the pixels of an image into groups for unsupervised semantic segmentation 2103.17070 §1. It starts from a DeepCluster-style pixel baseline and changes three things 2103.17070 §3.1:

• Prototype classifier. The learned pixel classifier is removed. Each pixel is scored against the current centroids 2103.17070 §3.2.
• Photometric invariance. Each image gets two colour-changed views. Each view is clustered on its own, and a cross-view loss trains each view against the other view's labels. The paper says this term makes the clustering itself invariant, not only the features 2103.17070 §3.3.1 eq. 11.
• Geometric equivariance. One crop and flip per image links the two views at feature level 2103.17070 §3.3.2 eq. 12–13.

Card: PiCIE.

The ablation shows each term's contribution on COCO-All. The prototype classifier alone gives 39.25 Acc and 9.82 mIoU, against 34.35 and 9.88 for the baseline without it 2103.17070 tab. 5. Adding the geometric term to the prototype classifier gives 46.97 and 12.04; adding the photometric term gives 42.55 and 9.84 2103.17070 tab. 5. Adding auxiliary over-clustering ("+H") gives 49.99 and 14.36, against 48.09 and 13.84 without it 2103.17070 tab. 1.

Single-source target variants (DFCN ablation)

DFCN builds the target from one embedding at a time, the AE alone or the IGAE alone, and compares these with the triplet target 2012.09600 tab. 4. The ablation shows that the triplet target is better on most rows, but not on all of them (see Contradictions).

Graph built from features (DFCN)

For datasets without a given graph, the paper builds an affinity matrix with a heat kernel, following SDCN, and uses five nearest neighbours 2012.09600 §Parameters Setting 2012.09600 §Benchmark Datasets. The bandwidth is not stated in the text 2012.09600 §Benchmark Datasets.

Baselines in the same papers

DFCN compares with K-means, AE, DEC, IDEC, GAE, VGAE, ARGA, DAEGC and SDCN, with SDCN_Q as a second SDCN variant [arxiv:2012.09600 §Comparison with the State-of-the-art Methods] 2012.09600 tab. 3. Most baseline numbers are copied from the SDCN paper; ARGA was re-run by the authors 2012.09600 §Parameters Setting.

PiCIE compares with a no-training baseline, a modified DeepCluster, IIC and IIC-res12 2103.17070 tab. 1. The modified DeepCluster is the closest pixel-level baseline to PiCIE's pipeline.

When to use which

The DFCN paper reports no runtime or memory measurements. The memory point is an inference from the dense softmax and adjacency matrices 2012.09600 eq. 8 2012.09600 §Benchmark Datasets.

Implementation sketch

Language-agnostic core of one training step for DFCN. Equation numbers refer to the card; the code differs in several places (see the card's Paper vs code).

# One DFCN training step  [arxiv:2012.09600 alg. 1]
# Inputs: features X (N, d), normalised adjacency A_norm (N, N), K centres

def dfcn_step(X, A_norm, centres, P, lam):
    # Encode with the feature-only and the graph encoders  [eq. 1]
    z_ae = ae_encoder(X)                      # (N, d')
    z_gae = igae_encoder(X, A_norm)           # (N, d')
    # Mix the two embeddings with a learned weight  [eq. 6]
    z_i = alpha * z_ae + (1 - alpha) * z_gae
    # One smoothing step over the graph  [eq. 7]
    z_l = A_norm @ z_i
    # Dense attention between nodes, then a skip connection  [eq. 8, 9]
    s = softmax(z_l @ z_l.T, axis=1)          # (N, N)
    z_fused = beta * (s @ z_l) + z_l
    # Soft assignments of the three embeddings  [eq. 10]
    q = student_t(z_fused, centres)
    q_gae = student_t(z_gae, centres)
    q_ae = student_t(z_ae, centres)
    # Reconstruction losses from the fused embedding  [eq. 2 to 5]
    loss_rec = recon_loss(z_fused, X, A_norm)
    # Triplet KL to the target P, weighted by lam  [eq. 12, 13]
    loss_kl = kl(P, (q + q_gae + q_ae) / 3)
    update(loss_rec + loss_kl * lam)
    return q

The target P is recomputed from the soft assignments eq. 11. The paper does not state how often; the algorithm uses an interval T that is not given 2012.09600 alg. 1.

For PiCIE, one epoch alternates a clustering pass and a training pass. The sketch leaves out the per-batch details; see the card for the full loss.

# One PiCIE epoch  [arxiv:2103.17070 §3.1-3.3] [eq. 1-14]
# Inputs: images (N, 3, H, W), feature network f, K clusters

def picie_epoch(images, f, K):
    # One photometric pair and one geometric transform per image,
    # fixed for the whole epoch  [§3.3]
    transforms = sample_transforms(images)
    # Pixel features for each view, L2-normalised  [eq. 12-13]
    feats_1 = view_features(images, transforms, f, view=1)
    feats_2 = view_features(images, transforms, f, view=2)
    # Cluster each view on its own with k-means  [eq. 8-9]
    centroids_1 = kmeans(feats_1, K)
    centroids_2 = kmeans(feats_2, K)
    # Pixel label: nearest centroid, per view  [§3.3]
    labels_1 = nearest_centroid(feats_1, centroids_1)
    labels_2 = nearest_centroid(feats_2, centroids_2)
    # Train f; labels and centroids stay fixed for the epoch  [§3.2]
    for batch in epoch_batches(images, transforms):
        # Within-view and cross-view terms  [eq. 10] [eq. 11]
        # The paper sums them [eq. 14]; the release averages them
        loss = within_view_loss(batch, labels_1, labels_2, centroids_1,
                                centroids_2)
        loss = loss + cross_view_loss(batch, labels_1, labels_2,
                                      centroids_1, centroids_2)
        f = adam_step(f, loss)
    return f

Contradictions

• Overall claim versus REUT (DFCN). The paper says DFCN consistently outperforms the baselines [arxiv:2012.09600 §Comparison with the State-of-the-art Methods]. On REUT, DFCN's ACC is 77.7 and SDCN_Q's is 79.3 2012.09600 tab. 3.
• Both sources needed versus the ablation (DFCN). The paper argues that both sources are needed [arxiv:2012.09600 §Influence of Exploiting Both-source Information]. Table 4 shows the AE-only target with a higher NMI on HHAR (82.8 against 82.2) and a higher F1 on CITE (64.4 against 64.3) 2012.09600 tab. 4.
• Stop rule (DFCN). The paper stops when a validation loss plateaus 2012.09600 §Parameters Setting. The released code reports, for each dataset, the epoch with the best ground-truth ACC and the other metrics from that epoch 2012.09600 §Paper vs code. Numbers from the two rules are not expected to match, and the size of the gap is not measured in the paper.
• Repeats (DFCN). The paper reports 10 runs with mean and standard deviation 2012.09600 §Training Procedure. The released code runs one seed by default 2012.09600 §Paper vs code.
• Balancing direction (PiCIE). The paper's ablation says balancing the clusters helps: 48.09 Acc and 13.84 mIoU with it, 40.56 and 11.46 without 2103.17070 tab. 6. The paper's wording does not settle which way the weight runs. The released code weights each cluster by its share of pixels, which favours large clusters. See the card's Paper vs code for the code reference: PiCIE.
• Learning rate (PiCIE). The supplement gives 1e-3 for PiCIE and for modified DeepCluster 2103.17070 supp. S1. The released launch script and logs use 1e-4 (see the card's Paper vs code).
• "+H" numbers (PiCIE). The auxiliary over-clustering rows are the paper's best COCO-All rows 2103.17070 tab. 1. The released code has a single clustering level, so these rows cannot be reproduced from that release (see the card's Paper vs code).
• Stuff claim (PiCIE). The paper says PiCIE keeps better or compatible stuff performance 2103.17070 §4.4. On the stuff-only partition, PiCIE + H has lower mIoU than modified DeepCluster (17.32 against 22.24) 2103.17070 tab. 2.

Papers

• Deep Fusion Clustering Network: fuses an AE and an improved graph AE with a learned module and trains them with a triplet KL target; author-reported gains over SDCN on six attributed datasets.
• PiCIE: Unsupervised Semantic Segmentation using Invariance and Equivariance in Clustering: clusters pixels with a non-parametric prototype classifier and photometric and geometric invariance losses; author-reported gains over modified DeepCluster on COCO-Stuff and Cityscapes.