🔢 mathematics

RTD-Lite: Scalable Topological Analysis for Comparing Weighted Graphs in Learning Tasks

The paper introduces RTD-Lite, a scalable algorithm that efficiently compares the topological connectivity structures of weighted graphs with $O(n^2)$ complexity, enabling its effective application in dimensionality reduction and neural network training to preserve topological features.

Original authors: Eduard Tulchinskii, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, Serguei Barannikov

Published 2026-06-05

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Eduard Tulchinskii, Daria Voronkova, Ilya Trofimov, Evgeny Burnaev, Serguei Barannikov

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 two massive, complex maps of a city. One map shows the roads as they are today, and the other shows a slightly different version of the city—maybe some new bridges were built, or some old streets were closed. Your goal is to figure out exactly how different these two maps are, not just by looking at individual streets, but by understanding the big picture: how neighborhoods connect, how traffic flows, and how the city's "shape" changes.

This is the problem the paper "RTD-Lite" tries to solve, but for data instead of cities.

The Problem: The "Heavy" Calculator

In the world of machine learning, data is often represented as graphs (dots connected by lines). To compare two graphs, scientists use a powerful tool called Topological Data Analysis (TDA). Think of TDA as a super-advanced scanner that doesn't just count the dots; it looks at the "holes," "clusters," and "loops" in the data.

However, the existing method for doing this (called RTD) is like trying to solve a massive jigsaw puzzle by hand, piece by piece, while wearing heavy lead boots. It is incredibly accurate, but it is so slow and computationally expensive that it crashes computers when the data gets too big (like trying to analyze a whole city instead of a single neighborhood).

The Solution: RTD-Lite (The "Light" Version)

The authors introduce RTD-Lite, a new, streamlined method. If the original RTD is a heavy-duty excavator, RTD-Lite is a nimble, high-speed drone.

Here is how it works, using a simple analogy:

The "Minimum Spanning Tree" (The Skeleton):
Imagine you want to connect all the houses in a neighborhood with the least amount of fencing possible. You would build a "skeleton" of the neighborhood using only the most essential roads. In math, this is called a Minimum Spanning Tree (MST).
- RTD-Lite builds this "skeleton" for both of your maps.
- It then compares the skeletons. If the skeletons look different, it means the underlying structure of the data has changed.
The "Barcode" Shortcut:
The old method tries to calculate a "barcode" for every single possible scale of the city (from a single house to the whole metropolis). This takes forever.
RTD-Lite is clever: it realizes that for many learning tasks, you don't need every tiny detail. It calculates a simplified barcode that focuses on the most important changes: how clusters of data merge or split.
- Analogy: Instead of counting every single brick in a wall to see if it's different, RTD-Lite just checks if the wall is still standing or if it has collapsed into a pile of rubble. It captures the "shape" of the change without getting bogged down in the dust.

Why It Matters (The Results)

The paper claims that RTD-Lite is a game-changer for three main reasons:

It's Blazing Fast: The old method gets slower and slower as data grows, eventually becoming impossible to use. RTD-Lite stays fast and efficient, scaling up to handle huge datasets (like 50,000 points) that would crash the old method. In tests, it was 10 times faster than other popular methods and could run on data that the original method couldn't even fit into memory.
It's Still Accurate: Even though it's a "light" version, it doesn't lose its eyesight. The paper shows that RTD-Lite can still spot the exact same topological differences as the heavy method. It correctly identifies when a group of data points splits into separate clusters or when they merge together.
It Helps AI Learn Better: The authors showed that you can use RTD-Lite as a "teacher" for Artificial Intelligence. By adding RTD-Lite to the training process of a neural network (the "brain" of the AI), the AI learns to organize data in a way that preserves its natural shape.
- Analogy: If you are teaching a student to draw a cat, the old method might say, "Draw every single whisker perfectly, or you fail," which takes forever. RTD-Lite says, "Make sure the cat has ears, a tail, and a body," and lets the student learn much faster while still getting the shape right.

Summary

RTD-Lite is a new, super-fast tool for comparing the "shape" of complex data. It uses a clever shortcut involving "skeletons" of the data to skip the slow, heavy calculations of the past. This allows scientists to analyze massive datasets quickly and helps train better, more efficient AI models without losing the ability to see the big picture.

The authors have made their code public, so anyone can try this "light" version of topological analysis on their own data.

Technical Summary: RTD-Lite

Problem Statement

The comparison of weighted graphs is a fundamental task in machine learning, network science, and computational biology. While Topological Data Analysis (TDA) offers robust tools like persistence barcodes to capture multi-scale topological features, existing methods for comparing weighted graphs often suffer from computational inefficiency. Specifically, the Representation Topology Divergence (RTD) metric, which quantifies topological dissimilarity based on comparative cross-barcodes, becomes computationally prohibitive for large-scale datasets. The high complexity of computing full persistent homology limits the applicability of rigorous topological comparison in real-world learning tasks, such as neural network training and dimensionality reduction, where scalability is critical.

Methodology

The authors introduce RTD-Lite, a scalable algorithm designed to efficiently compare the topological features of two weighted graphs, $A$ and $B$ , which share a one-to-one correspondence between their vertex sets. The method focuses on capturing discrepancies in connectivity and cluster structures (zero-dimensional homology) across arbitrary scales without computing full persistence barcodes.

Core Mechanism

The algorithm operates on an auxiliary graph $C$ constructed from the input graphs $A$ and $B$ :

Graph Construction: An auxiliary graph $C$ is formed with the same vertex set as $A$ and $B$ . The weight of an edge $e$ in $C$ is defined as $c_e = \min(a_e, b_e)$ , where $a_e$ and $b_e$ are the weights of the corresponding edges in $A$ and $B$ (with absent edges treated as having infinite weight).
MST Utilization: The method leverages Minimal Spanning Trees (MSTs). It computes the MST of graph $C$ and the MST of graph $A$ .
Interval Calculation: For each edge $e$ in the MST of $C$ (with weight $c_e$ ), the algorithm identifies the minimal level $t(e)$ at which the two clusters connected by $e$ in $C$ merge into a single cluster in $A$ . This is achieved by iteratively adding edges from the MST of $A$ until a path connects the endpoints of $e$ .
Barcode Generation: The result is a set of intervals $[c_e, t(e)]$ , termed the RTD-Lite barcode. The sum of the lengths of these intervals, $\sum (t(e) - c_e)$ , constitutes the RTD-Lite metric value, denoted as $RTDL(A, B)$.

Algorithms

The paper proposes two algorithms:

Algorithm 1 (Direct): Computes the full set of intervals (the barcode). It involves sorting edges, constructing MSTs, and using a Disjoint Set Union (DSU) structure with temporary copies to track connectivity.
Algorithm 2 (Simplified): Computes only the sum of interval lengths ($RTDL(A, B)$) without reconstructing individual intervals. It calculates the sum of edge weights in the MST of $A$ ( $s_A$ ) and the MST of $C$ ( $s_C$ ), returning $s_A - s_C$ . This approach is mathematically proven to yield the same total sum as the direct method.

Complexity

Both algorithms achieve a time and memory complexity of $O(n^2)$ , where $n$ is the number of vertices. This is a significant improvement over standard RTD, which involves persistence barcode computation that can be cubic or worse depending on the number of simplices. The $O(n^2)$ complexity is derived from Prim's algorithm for MST construction and the linear operations required for DSU management.

Differentiability

The endpoints of the RTD-Lite intervals are determined by edge weights or minimums of edge weights, making them (sub-)differentiable. This property allows the metric to be integrated into neural network training as a differentiable loss function component, enabling gradient-based optimization to preserve topological structures.

Key Contributions

Efficient Metric Proposal: The introduction of RTD-Lite as a computationally efficient method to compute a large subset of RTD features, specifically focusing on zero-dimensional homology (connected components).
Complexity Analysis: A detailed demonstration that RTD-Lite scales quadratically ( $O(n^2)$ ) in both time and memory, making it feasible for large datasets where standard RTD fails.
Integration into Learning: A framework for incorporating RTD-Lite into neural network training as a loss function component to promote the preservation of topological structures in learned representations.
Empirical Validation: Extensive experiments on synthetic and real-world datasets showing that RTD-Lite effectively identifies topological differences while significantly reducing computation time compared to existing methods.

Experimental Results

The authors evaluated RTD-Lite across several scenarios:

Synthetic Data (Clusters and Rings): In experiments involving point clouds with varying numbers of clusters or rings, RTD-Lite demonstrated a monotonic response to increasing topological discrepancy. In contrast, the Centered Kernel Alignment (CKA) metric exhibited chaotic behavior, failing to consistently reflect topological changes.
UMAP Representations: When comparing 2D representations of the MNIST dataset generated by UMAP with varying neighbor counts, RTD-Lite and RTD showed monotonic increasing dissimilarity as the topological structure changed. CKA again failed to show a consistent pattern.
Neural Network Representations:
- CNNs: On CIFAR-10, RTD-Lite accurately identified that layers from networks trained with different initializations were most similar to their corresponding layers in other networks. It achieved 98% classification accuracy in matching corresponding layers, comparable to RTD (98%) and CKA (96%), but with a computation time approximately 6 times faster than RTD.
- GNNs: On the Amazon Computers dataset, RTD-Lite scores were lowest for corresponding layers across various GNN architectures (GCN, GraphSAGE, GAT, ClusterGCN), aligning well with standard RTD scores.
Scalability: For a dataset of 50,000 vertices (full CIFAR-10 training set), RTD-Lite completed the comparison in 3.75 minutes. Standard RTD failed due to GPU memory constraints, and CKA took 36 minutes.
Dimensionality Reduction (Autoencoders): When used as a loss function in autoencoders for dimensionality reduction (on "Spheres", F-MNIST, and COIL-20 datasets), RTD-Lite achieved performance comparable to RTD-AE and TopoAE in preserving global manifold structure. Crucially, training with RTD-Lite was significantly faster and did not require the two-stage training procedure (reconstruction loss followed by topological loss) often needed for RTD-based losses.

Significance and Claims

The paper claims that RTD-Lite addresses the critical computational bottleneck associated with topological graph comparison. By reducing complexity to $O(n^2)$ , it enables the application of rigorous topological analysis in large-scale learning tasks where it was previously infeasible. The authors assert that RTD-Lite serves as a practical tool for:

Comparing neural representations in CNNs and GNNs.
Enhancing dimensionality reduction by preserving topological structures without the overhead of full persistence barcode calculations.
Providing a scalable alternative to existing graph comparison methods that either lack multi-scale topological sensitivity or do not scale to large data.

The work positions RTD-Lite not as a replacement for full TDA in all contexts, but as a highly efficient approximation that captures essential topological discrepancies (specifically cluster structures) suitable for integration into modern machine learning pipelines.