🤖 machine learning

Non-negative Matrix Factorisation with Topological Regularisation

This paper proposes a novel Non-negative Matrix Factorisation framework that enhances the interpretability of learned bases by incorporating persistent homology as a stable, threshold-free topological regulariser, thereby unifying the modeling of spatially coherent images, periodic time-series, and clique-like graph signals.

Original authors: Matias de Jong van Lier, Shizuo Kaji, Keunsu Kim

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matias de Jong van Lier, Shizuo Kaji, Keunsu Kim

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 have a giant, messy pile of Lego bricks. Your goal is to figure out what the original, simple shapes were that were used to build every single structure in the pile. This is essentially what a computer algorithm called Non-Negative Matrix Factorization (NMF) does. It tries to break down complex data (like images, sound, or graphs) into a set of basic "building blocks" (called bases) that can be mixed together to recreate the original data.

The problem is, standard NMF is a bit like a child playing with Legos: it can find a way to rebuild the structures, but the "building blocks" it invents might be weird, fragmented, or nonsensical. It might create a block that is half a wheel and half a door, just because that mathematically fits the numbers, even though it doesn't make sense in the real world.

This paper introduces a new method called Top-NMF (Topological NMF). Think of this as giving the computer a set of "common sense" rules about what a good building block should look like, based on the shape of the data.

Here is how it works, using simple analogies:

1. The Problem: "Thresholds" are Unreliable

Usually, to check if a shape is "connected" (like one solid piece of clay) or "broken" (like two separate pebbles), you have to draw a line. "If the clay is taller than this line, it counts; if it's shorter, it doesn't."

The Issue: If you move that line up or down just a tiny bit, a single connected piece might suddenly look like two separate pieces, or two separate pieces might look like one. This makes it hard for the computer to learn smoothly because the rules keep changing with tiny adjustments.

2. The Solution: "Persistent Homology" (The "Time-Lapse" Camera)

Instead of drawing a single line, Top-NMF uses a technique called Persistent Homology. Imagine taking a time-lapse video of a sandcastle being built as the tide comes in.

You don't just look at the castle at one specific water level. You watch the whole process.
You see when a tower appears (is born) as the water recedes, and when it disappears (dies) as the water rises.
The Magic: If a tower lasts for a long time before the water washes it away, it's a real, strong structure. If a tiny bump appears and disappears instantly, it's just noise.
Top-NMF uses this "time-lapse" view to measure the "shape" of the data without getting confused by tiny, random fluctuations. It gives the computer a stable, smooth way to say, "This is a solid, connected shape," or "This is a ring," or "This is a loop."

3. How It Changes the Learning (The "Topological Score")

The paper adds a new rule to the computer's learning process. It says: "Don't just try to rebuild the data perfectly; also try to make sure your building blocks have the right shape."

The paper tests this on three different types of data:

Images (The "Connected Blob" Rule):
- Goal: If you are breaking down a picture of a face, you want the building blocks to be connected parts (like a whole nose or a whole eye), not a nose that is split into three tiny, disconnected dots.
- Result: Top-NMF learns to create bases that are solid, connected blobs, whereas the standard method creates fragmented, scattered pieces.
Graphs (The "Social Clique" Rule):
- Goal: Imagine a graph representing friendships. You want to find groups of people who are all friends with each other (a "clique").
- Result: Top-NMF learns to find these tight-knit, dense groups. The standard method might mix people from different groups together. Top-NMF acts like a detective that says, "These people form a perfect circle of friends; let's keep them together."
Time Series (The "Rhythm" Rule):
- Goal: If you are analyzing a heartbeat or a song, you want to separate the steady "beat" (the rhythm) from the "trend" (the song getting louder or quieter).
- Result: Top-NMF can be told, "Find me a block that is perfectly circular (a loop in time, meaning it repeats)." It successfully separates the repeating rhythm from the non-repeating trend, whereas the standard method mixes them up.

4. The Trade-Off

The paper notes that there is a balance to strike.

Standard NMF is like a perfectionist who cares only about the final picture looking exactly right, even if the pieces used to make it are weird.
Top-NMF is like a teacher who says, "The picture can be almost perfect, but the pieces you use must be logical and well-shaped."
Sometimes, the "logical" pieces don't recreate the image quite as perfectly as the "weird" pieces, but the result is much easier for a human to understand.

Summary

In short, this paper teaches computers to look at data not just as a list of numbers, but as shapes. By using a mathematical "time-lapse" camera (Persistent Homology), the computer learns to prefer building blocks that are connected, looped, or clustered in ways that make sense for the specific type of data it is looking at. This makes the results much more interpretable and useful for humans.

Technical Summary: NMF with Topological Regularisation (Top-NMF)

Problem Statement

Non-negative Matrix Factorisation (NMF) is a standard technique for decomposing additive non-negative data into interpretable, part-based representations. However, standard NMF often yields basis vectors that, while achieving low reconstruction error, lack structural coherence. A sparse basis may be fragmented into disconnected components, and a smooth basis may blur semantically distinct regions. Existing regularisation methods (e.g., sparsity, smoothness, or graph-regularised coefficients) fail to directly control the global topological structure of the basis supports. Furthermore, naive attempts to enforce topology via thresholded supports are hindered by discontinuity and threshold dependence, making them unsuitable for continuous optimisation.

The core problem addressed is how to learn NMF basis functions that are not only reconstructive but also possess specific, domain-appropriate topological properties (e.g., connectedness in images, periodicity in time series, or clique-like structures in graphs) in a way that is compatible with gradient-based optimisation.

Methodology

Functional Viewpoint and Topological Regularisation

The authors propose Top-NMF, a framework that treats basis vectors not merely as rows of a matrix but as non-negative functions $v: \Omega \to \mathbb{R}_{\geq 0}$ defined on a structured domain $\Omega$ (e.g., image grids, graphs, or time series). The objective function augments the standard reconstruction loss with a topological penalty:
$\min_{W, V \geq 0} L_{\text{recon}}(X, WV) + \lambda_{\text{top}} L_{\text{top}}(V)$
where $L_{\text{top}}(V) = \sum Q(v_j)$ is a sum of scalar topological scores derived from the basis functions.

Persistent Homology as a Continuous Quantifier

To overcome the instability of threshold-dependent topology, the method employs persistent homology (PH). Instead of analyzing a single thresholded support, Top-NMF constructs a superlevel-set filtration (or a derived filtration for time series) from each basis function. PH tracks the birth and death of topological features (connected components, holes) across all thresholds, providing a stable, threshold-free summary.

The topological score $Q(v)$ is a scalar functional derived from the persistence diagram. The paper utilises total squared persistence (and its weighted variants) as a differentiable proxy for topological properties. Minimising this score encourages specific structural priors:

Connectedness (Images/1D Signals): Penalising finite 0-dimensional persistence bars (which represent disconnected components that merge at lower thresholds) encourages a single, connected support.
Periodicity (Time Series): Using sliding-window embeddings and Vietoris–Rips filtrations, the method targets 1-dimensional persistence (holes) to identify circular structures. A target-based penalty $(Per(v) - a)^2$ allows users to specify desired periodicity levels.
Clique-like Structures (Graphs): For edge-weighted graphs, a novel clique-promoting functional ( $CP_\alpha$ ) is introduced. This score is derived from the persistence of the graph filtration and can be expressed in closed form via a maximum-weight spanning tree. It rewards delayed merging of vertex groups (high 0-persistence) and early cycle formation (high 1-persistence), effectively promoting dense, clique-like subgraphs.

Optimisation

The resulting optimisation problem is non-smooth and non-convex. The authors formulate it within the framework of tame geometry (o-minimal structures). They employ a projected subgradient method (specifically using AdamW in experiments) where the subgradient of the topological term is computed using the chain rule through the persistence diagram or the explicit spanning-tree formulation. Theoretical guarantees (Proposition 6 and Theorem 7) establish that accumulation points of the iterates are Clarke stationary points under standard assumptions.

Key Contributions

Functional Formulation: The paper formulates NMF from a functional viewpoint on structured domains, providing a unified language to define topological priors for images, time series, and graphs.
Differentiable Topological Quantifiers: It demonstrates how persistent homology transforms discrete interpretability criteria into optimisable regularisers, avoiding the threshold-dependence of traditional support analysis.
Domain-Specific Instantiations:
- Development of connectedness and hole-free penalties for image and signal bases.
- Introduction of a periodicity score for time-series bases using sliding-window embeddings.
- Proposal of a clique-promoting regulariser ( $CP_\alpha$ ) for graph signals, which is presented as a novel persistent-homology-based descriptor for edge-weighted graphs with independent utility beyond NMF.
Empirical Validation: The framework is evaluated on synthetic and real-world datasets, showing that Top-NMF recovers structurally coherent bases (e.g., unimodal peaks, connected bars, clique subgraphs, and rhythmic ECG components) that standard NMF fails to isolate, often with competitive reconstruction error.

Experimental Results

The authors evaluate Top-NMF across four domains:

1D Signals: In recovering unimodal Gaussian peaks from mixtures, Top-NMF achieved a significantly higher atom-recovery score (0.997 vs. 0.772 for standard NMF) by penalising secondary local maxima, despite a slight increase in reconstruction RMSE.
Images: On synthetic bar atoms and Hangul glyphs, Top-NMF successfully recovered single connected components (Betti number $\beta_0 = 1.0$ ), whereas standard NMF produced fragmented bases ( $\beta_0 > 1.6$ ).
Graphs: On synthetic clique mixtures and real-world SocioPatterns high school contact data, Top-NMF successfully separated clique-like components. In the real-world setting, Top-NMF bases showed higher intra-class edge mass (0.995 vs. 0.966) compared to standard NMF and network-regularised baselines.
Time Series: In separating periodic signals from trends, Top-NMF successfully isolated distinct periodic components (cosine, triangle wave) and a trend, whereas standard NMF mixed these features. Applied to MIT-BIH ECG data, the method produced rhythm-like bases and residual components; using only the periodic bases for reconstruction yielded a high AUROC (0.955) for detecting premature ventricular contractions (PVCs) as anomalies, outperforming standard NMF (0.105).

Significance and Claims

The paper claims that Top-NMF provides a modular framework for encoding domain-specific structural priors directly into the matrix factorisation objective. Its primary significance lies in shifting the role of persistent homology from a post-hoc feature extractor to an integral, optimisable component of the learning process.

The authors emphasise that the method does not guarantee global optimality or solve the general identifiability problem of NMF; rather, it selects structurally preferable solutions from the set of ambiguous factorisations based on the imposed topological prior. The work suggests that persistent homology serves as a formal modelling language for defining the desired structural characteristics of learned representations, enabling the learning of bases that are both reconstructive and topologically interpretable.

The paper acknowledges limitations, including the computational overhead of calculating persistent homology (though mitigated by efficient spanning-tree formulations for graphs) and the dependence on user-specified domain constructions (e.g., filtration types, embedding dimensions). It positions Top-NMF as a tool for researchers to inject domain knowledge about "good" basis structures into unsupervised learning, rather than an automated discovery procedure.