🤖 machine learning

T-REGS: Minimum Spanning Tree Regularization for Self-Supervised Learning

This paper introduces T-REGS, a self-supervised learning framework that utilizes Minimum Spanning Tree length as a regularization term to theoretically and empirically prevent dimensional collapse while promoting distribution uniformity on learned representations.

Original authors: Julie Mordacq, David Loiseaux, Vicky Kalogeiton, Steve Oudot

Published 2026-02-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Julie Mordacq, David Loiseaux, Vicky Kalogeiton, Steve Oudot

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a computer to understand pictures without showing it any labels (like "cat" or "dog"). This is called Self-Supervised Learning. The computer learns by looking at two different versions of the same photo (maybe one is blurry, one is cropped) and trying to figure out that they are the same thing.

However, there's a big problem: the computer often gets lazy. Instead of learning rich, detailed features, it might just output the exact same boring answer for every single picture. This is called "collapse." It's like a student who, instead of studying the whole textbook, just memorizes the first sentence of every chapter and gives that same answer to every test question.

The authors of this paper, Julie Mordacq and her team, have invented a new tool called T-REGS to stop the computer from getting lazy. Here is how it works, explained simply:

The Problem: The "Crowded Room" vs. The "Empty Room"

When a computer learns, it turns every picture into a list of numbers (a point in a multi-dimensional space).

Dimensional Collapse: Imagine all these points clumping together in a tiny corner of the room. The computer has forgotten most of the room's dimensions. It's not using its full brainpower.
Lack of Uniformity: Even if they aren't clumped, they might all be standing in a tight circle. They aren't spread out evenly across the whole space.

The goal is to get the computer to spread these points out as far as possible, filling up the entire "room" evenly, so it can distinguish between every single picture clearly.

The Solution: The "Minimum Spanning Tree" (MST)

The authors use a concept from math called a Minimum Spanning Tree.

The Analogy: Imagine you have a group of people standing in a field. You want to connect everyone with a single rope network so that everyone is connected, but you want to use the shortest total length of rope possible. That shortest network is the "Minimum Spanning Tree."
The Trick: Usually, if you want to minimize rope, you pull people close together. But T-REGS does the opposite: it tries to maximize the length of that rope.

By forcing the computer to make the "rope" connecting all the data points as long as possible, the computer is forced to push the points apart. It can't clump them together anymore, or the rope would be too short.

The Safety Net: The "Sphere"

There's a catch. If you just tell the computer to "maximize the rope length" without any rules, the points will just fly off to infinity, stretching the rope forever. That's not helpful.

So, T-REGS adds a second rule: The points must stay on the surface of a giant, invisible ball (a sphere).

Now, the computer has to push the points as far apart as possible, but they are trapped on the surface of this ball.
The only way to make the rope as long as possible while staying on the ball is to spread the points out evenly, like the vertices of a perfect geometric shape (a simplex) covering the whole surface.

What They Found

The paper shows that this simple idea works really well:

It stops the collapse: The computer is forced to use all its dimensions; it can't hide in a corner.
It creates uniformity: The data points spread out evenly, like guests at a party who are told to stand as far apart from each other as possible while staying in the room.
It works on real data: They tested this on standard image datasets (like CIFAR and ImageNet). When they added T-REGS to existing learning methods, the computers got better at recognizing images.
It works on text and images: They even tested it on a system that matches photos with text (like CLIP). It helped the system understand both images and words better by keeping the "mental space" for both evenly filled.

In a Nutshell

Think of T-REGS as a strict teacher who tells the computer: "You cannot bunch your answers together, and you cannot fly off the page. You must spread your answers out as far as possible across the entire page, filling every corner evenly."

This forces the computer to learn a much richer, more detailed, and more useful way of seeing the world, without needing any human labels to tell it what to do.

Technical Summary: T-REGS (Minimum Spanning Tree Regularization for Self-Supervised Learning)

Problem Statement

Self-supervised learning (SSL) has become a dominant paradigm for learning data representations without labeled data, particularly in visual domains. However, a critical challenge in Joint-Embedding Self-Supervised Learning (JE-SSL) is representation collapse, where networks output identical or non-informative vectors regardless of input. Recent research has identified a more subtle form of failure known as dimensional collapse, where learned features occupy only a low-dimensional subspace, leading to high feature correlations and reduced diversity. Additionally, effective representations require uniformity, ensuring embeddings are evenly distributed across the representation space to preserve maximum information and aid downstream generalization.

Existing solutions face limitations:

Contrastive methods (e.g., SimCLR, MoCo) require large batch sizes and numerous negative samples, which are computationally expensive.
Redundancy reduction methods (e.g., Barlow Twins, VICReg) enforce covariance matrices close to the identity but rely only on second-order moments, potentially missing density concentration points that prevent convergence to uniform distributions.
Asymmetric methods (e.g., BYOL) lack theoretical grounding regarding how they prevent collapse.
Optimal Transport-based approaches (e.g., Fang et al.) satisfy necessary theoretical properties but are computationally costly and can suffer from numerical instabilities due to SVD computations.

Methodology: T-REG and T-REGS

The authors propose T-REG (Minimum Spanning Tree Regularization), a framework designed to simultaneously mitigate dimensional collapse and promote distribution uniformity.

Core Concept: MST Length Maximization

The central idea is to maximize the length of the Minimum Spanning Tree (MST) of the learned embeddings. Theoretical analysis connects MST length to statistical dimension estimation and entropy maximization.

MST Length ( $E(G)$ ): Defined as the sum of Euclidean distances between connected nodes in the tree: $E(G) = \sum_{(z,z') \in E} \|z - z'\|^2$ .
Repulsive Force: During optimization, pairs of points forming edges in the MST exert a repulsive force on each other, naturally pushing points apart to increase the total tree length.

The T-REG Loss Function

To prevent the trivial solution where points diverge to infinity (since maximizing MST length alone encourages dilation), T-REG constrains embeddings to a compact manifold, specifically a hypersphere. The total loss consists of two terms:

MST Length Maximization ( $L_E$ ): $L_E(Z) = -\frac{1}{n} E(\text{MST}(Z))$ . This term encourages spreading.
Soft Sphere Constraint ( $L_S$ ): $L_S(Z) = \frac{1}{n} \sum_i (\|z_i\|^2 - 1)^2$ . This penalizes deviations from the unit sphere.

The combined loss is:
$L_{\text{T-REG}}(Z) = \gamma L_E(Z) + \lambda L_S(Z)$
where $\gamma$ and $\lambda$ are hyperparameters balancing the trade-off between spreading and maintaining the sphere constraint.

Extension to T-REGS

T-REGS applies this regularization to JE-SSL frameworks. Given two augmented views $X$ and $X'$ , the model produces embeddings $Z$ and $Z'$ . T-REGS acts as a regularization term applied independently to each branch:
$L_{\text{T-REGS}}(Z, Z') = L_{\text{T-REG}}(Z) + L_{\text{T-REGS}}(Z')$
It can be used in two ways:

Standalone: Combined directly with a view-invariance term (e.g., Mean Squared Error).
Auxiliary: Added to existing SSL objectives (e.g., BYOL, Barlow Twins) to enhance their performance.

Theoretical Analysis

The paper provides rigorous theoretical guarantees for T-REG:

Small Samples ( $n \le d+1$ ): Theorem 4.1 proves that under the sphere constraint, maximizing MST length forces points to lie on the vertices of a regular simplex. This configuration maximizes pairwise distances, effectively preventing dimensional collapse by utilizing the full representation dimension.
Large Samples ( $n \to \infty$ ): The analysis connects MST length to the intrinsic Rényi entropy. Theorem 4.4 and Corollary 4.6 demonstrate that maximizing MST length asymptotically drives the embedding distribution toward the uniform distribution on the compact Riemannian manifold (the sphere).
Principled Properties: T-REG naturally satisfies the four properties proposed by Fang et al. [23] (instance permutation, instance cloning, feature cloning, and feature baby constraints), which are necessary to prevent dimensional collapse and ensure uniformity.

Experimental Results

The authors evaluated T-REGS on synthetic data and standard SSL benchmarks.

Synthetic Data Validation

Dimensional Collapse: On a 1024-dimensional Gaussian dataset with controlled collapse levels, T-REG's loss sensitivity matched that of the W2 metric (from Fang et al.), confirming its ability to penalize collapse.
Uniformity: Optimization of point clouds showed that T-REG successfully transformed degenerate or clustered data into uniformly distributed points on a sphere. In high dimensions (256-d), the cosine similarity distribution converged to a Dirac delta near 0, indicating a regular simplex configuration.

Benchmark Performance

CIFAR-10/100: T-REGS achieved competitive results, matching or slightly exceeding W2-regularized methods. When used as an auxiliary loss for BYOL and Barlow Twins, it consistently improved Top-1 accuracy over baselines and variants using other regularizers (e.g., Lu, W2).
ImageNet-100/1k: T-REGS demonstrated scalability. As an auxiliary loss for BYOL and Barlow Twins, it improved performance on both datasets. Standalone T-REGS (combined with LMSE) achieved 68.8% Top-1 accuracy on ImageNet-1k, competitive with state-of-the-art methods like INTL.
Multi-modal Application (Image-Text Retrieval): Applied to fine-tuning CLIP, T-REGS improved retrieval performance (R@1 and R@5) on Flickr30k and MS-COCO. This suggests T-REGS helps mitigate the "modality gap" by enforcing uniformity in both image and text branches.

Computational Efficiency

Complexity: The MST computation uses Kruskal's algorithm with a worst-case complexity of $O(B^2(D \cdot \log B))$ , where $B$ is batch size and $D$ is dimension.
Runtime: Despite the theoretical complexity, GPU-parallelized implementations (using torchph) allow T-REGS to match the wall-clock time per step of SimCLR and VICReg in practice.

Significance and Claims

The paper claims that T-REGS offers a conceptually simple, easy-to-implement, and computationally efficient alternative to existing regularization strategies. Its primary significance lies in:

Theoretical Soundness: It provides provable guarantees against dimensional collapse and for promoting uniformity on compact manifolds, grounded in topological data analysis and entropy maximization.
Practical Effectiveness: It improves representation quality across diverse architectures (contrastive and non-contrastive) and modalities (single and multi-modal) without requiring large negative batches or complex numerical operations like SVD.
Versatility: It functions effectively both as a standalone objective and as a modular auxiliary loss, making it adaptable to various SSL pipelines.

The authors conclude that T-REGS successfully bridges the gap between theoretical requirements for good SSL representations and practical, scalable implementation.