🤖 machine learning

TopoMap: A Feature-based Semantic Discriminator of the Topographical Regions in the Test Input Space

The paper introduces TopoMap, a black-box, model-agnostic framework that constructs a topographical map of the input feature space through dimensionality reduction and clustering to group inputs by shared failure-inducing features, thereby enabling more effective selection of test cases for mutation analysis compared to random selection.

Original authors: Gianmarco De Vita, Nargiz Humbatova, Paolo Tonella

Published 2026-03-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Gianmarco De Vita, Nargiz Humbatova, Paolo Tonella

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 find a specific type of bug in a very complex, self-driving car's brain (a Deep Learning model). You know the car sometimes makes mistakes, like swerving when it shouldn't.

The Problem:
Most testing methods are like throwing darts blindly at a wall. You throw a dart (a test input), and if the car crashes, you celebrate. But you don't really know why it crashed. Was it the rain? The color of the car? A specific type of tree? You just know that it crashed. Existing methods try to tweak the darts slightly to find more crashes, but they often get stuck in one corner of the wall, missing other dangerous spots entirely.

The Solution: TOPOMAP
The authors of this paper created a tool called TOPOMAP. Think of TOPOMAP as a high-tech GPS map for the world of test inputs.

Instead of throwing darts blindly, TOPOMAP draws a map of the entire "landscape" of possible inputs. It groups similar inputs together into "regions" or "neighborhoods."

The Neighborhoods: Imagine a map where one neighborhood is "All rainy days," another is "All sunny days with bright sun glare," and another is "All snowy roads."
The Goal: The goal is to find out which specific neighborhood contains the "bugs" (the inputs that make the car crash).

How It Works (The Magic Trick):
Creating this map is tricky because the data is too complex for humans to understand directly (it's like trying to read a book written in a language with 10,000 letters).

Squishing the Data (Embedding): First, TOPOMAP uses a magic lens to "squish" the complex data down into a simpler shape, like turning a giant, tangled ball of yarn into a neat, flat sheet of paper. This keeps the important features but makes them easier to see.
Grouping the Neighbors (Clustering): It then draws lines on this sheet to group similar items together. It's like sorting a giant pile of mixed Lego bricks into buckets: all red 2x4s here, all blue wheels there.
The Robot Judge (The DNN Evaluator): Here is the clever part. How do we know if the groups are good? Should we ask a human to look at every group? That takes forever.
- Instead, TOPOMAP uses a Robot Judge (a small AI).
- The Robot Judge is asked: "Can you tell the difference between Group A and Group B?"
- If the Robot Judge can easily tell them apart, it means the groups are distinct and meaningful. If the Robot Judge gets confused, the groups are messy and need to be reorganized.
- The system tries millions of different ways to squish and group the data until the Robot Judge is happiest with the result. This creates the final, perfect "Topographical Map."

Why Is This Awesome? (The Results)
The researchers tested this map by trying to "kill" (find bugs in) different versions of the AI.

Random Guessing: If you just pick random test inputs, you might need to test 100 items to find a bug.
Using TOPOMAP: By looking at the map, the researchers could pick just 9 items from the "dangerous neighborhood" and find the bug.
The Score: Their method was 35% better than random guessing for bugs that could be found, and a massive 61% better for the really tricky bugs that are hard to find.

The Human Touch:
The researchers also asked real humans to look at the groups the map created. They found that when the images were clear (like handwritten numbers), humans agreed with the map almost perfectly. The map had successfully grouped things in a way that made sense to human intuition.

In a Nutshell:
TOPOMAP is like a detective who doesn't just look for clues randomly. Instead, it draws a detailed map of the crime scene, identifies specific "hot zones" where the bad guys hang out, and helps you focus your search there. It saves time, finds more bugs, and does it all automatically without needing a human to manually define what a "bug" looks like.

1. Problem Statement

Testing Deep Learning (DL) systems is a significant challenge. While it is relatively easy to find inputs that cause a model to fail, existing testing approaches often suffer from two main limitations:

Lack of Systematic Exploration: Many methods rely on small perturbations of specific inputs, focusing on isolated regions of the input space while neglecting other regions where different types of failures might occur.
Manual Feature Engineering: Approaches like DeepHyperion attempt to map the input space but require substantial human effort to define and quantify domain-specific features (e.g., luminosity for images, lane distance for self-driving cars). This limits scalability and generalizability.
Black-Box Requirement: Many existing techniques require access to internal model states (e.g., neuron activations, softmax outputs), making them unsuitable for black-box testing scenarios.

The core problem is the need for a fully automated, black-box, and model-agnostic method to partition the high-dimensional input space into meaningful, discriminative regions (a "topographical map") that can effectively expose DL faults without human intervention.

2. Methodology: TOPOMAP

TOPOMAP constructs a topographical map of the input space by grouping inputs based on shared features. The process is divided into four main stages (illustrated in Figure 2 of the paper):

A. Dimensionality Reduction (Embedding)

Since DL inputs are high-dimensional (e.g., images, audio), the first step is to transform raw inputs into lower-dimensional embeddings that retain key semantic features. The authors evaluated various techniques:

Linear: PCA, SVD, LDA.
Non-linear: UMAP, t-SNE, Isomap.
Deep Learning: Autoencoders (AE), Word2vec (for text).
Selection: The approach does not assume a single best method; instead, it treats the choice of embedding as a hyperparameter to be optimized.

B. Input Clustering

The reduced embeddings are clustered using unsupervised learning algorithms to group similar inputs. Evaluated algorithms include:

Parametric: K-means, BIRCH (require a predefined number of clusters, $k$ ).
Non-parametric: HDBSCAN, Affinity Propagation (determine $k$ internally).

C. Automated Configuration Selection (The Core Innovation)

Since different datasets require different embedding/clustering combinations, TOPOMAP uses a DNN-based evaluator to automatically select the optimal configuration.

The Logic: A human evaluator would judge two clusters as "good" if they are easily distinguishable based on their features. TOPOMAP simulates this by training a Deep Neural Network (DNN) to classify inputs based on the pseudo-labels (cluster IDs) generated by a specific clustering configuration.
Metric: The quality of a map is measured by the Weighted Pairwise Accuracy of the DNN. This metric calculates the DNN's ability to distinguish between every pair of clusters, focusing on the worst-case pair (minimum accuracy). A high minimum pairwise accuracy indicates that the clusters are distinct and meaningful.
Optimization: The system iterates through embedding/clustering configurations and selects the one that maximizes this worst-case DNN accuracy.

D. Automated Selection of Cluster Count ( $k$ )

For algorithms requiring a specific number of clusters ( $k$ ), TOPOMAP employs an ad-hoc algorithm (Algorithm 1). It incrementally increases $k$ and monitors the accuracy of the clustering-as-classification task. The process stops when the accuracy gain plateaus (derivative < 0.001), indicating that further splitting yields no new discriminative features.

3. Key Contributions

TOPOMAP Framework: A novel, fully automated, black-box approach to generate topographical maps of DL input spaces without requiring internal model access or manual feature engineering.
DNN-Based Configuration Selector: A method to automatically select the best embedding and clustering configuration by mimicking human discrimination capabilities via a DNN classifier trained on cluster pseudo-labels.
Weighted Pairwise Accuracy Metric: A robust metric for evaluating clustering quality that accounts for class imbalance and focuses on the most difficult-to-distinguish cluster pairs.
Empirical Validation: Extensive evaluation across six diverse datasets (MNIST, CIFAR-10, Speaker Recognition, Reuters, Udacity Steering, Unity Eyes) covering both classification and regression tasks.

4. Experimental Results

The authors evaluated TOPOMAP using mutation analysis (via the DeepCrime tool) and human studies.

A. Fault Detection Effectiveness (RQ3)

Killable Mutants: TOPOMAP identified small aggregations of clusters (averaging 9% of the total test set) that killed mutants with 100% probability.
Comparison to Random: Compared to random selection of the same number of inputs, TOPOMAP improved the killing probability by 35% on average for killable mutants and 61% for non-killable mutants.
Density: The "killing aggregations" contained a high density of fault-revealing inputs (contributors), often exceeding 50% of the cluster size.

B. Comparison with DeepHyperion (RQ4)

Complementarity: The maps generated by TOPOMAP and DeepHyperion showed low similarity (Gini Similarity ~0.6), indicating they capture different structural representations of the input space.
Performance: TOPOMAP outperformed DeepHyperion in terms of contributor density (8% higher for killable mutants) and required fewer inputs to achieve statistical significance in killing mutants.
Automation: Unlike DeepHyperion, TOPOMAP requires no manual feature definition.

C. Human Study (RQ2)

A user study with Amazon Mechanical Turk participants showed a strong correlation between human ability to distinguish clusters and the DNN's weighted pairwise accuracy (especially on MNIST).
This validates that the "discriminative" regions found by TOPOMAP align with human-perceivable features.

D. Killing Propagation (RQ5)

Specific clusters were found to be consistently effective at killing different mutation operators (fault types), suggesting that the topographical map identifies robust "failure regions" rather than artifacts of a specific fault configuration.

5. Significance

Scalability and Automation: TOPOMAP removes the bottleneck of manual feature engineering, making it applicable to any DL system (image, text, audio, regression) without domain-specific tuning.
Black-Box Testing: It enables rigorous testing of proprietary or closed-source DL models where internal states are inaccessible.
Efficient Test Generation: By identifying dense regions of fault-revealing inputs, developers can generate highly effective test suites with significantly fewer test cases than random sampling.
Interpretability: The resulting topographical maps provide a visual and semantic understanding of where a model is likely to fail, aiding in debugging and model improvement.

In conclusion, TOPOMAP represents a significant step forward in automated DL testing, shifting the paradigm from random or perturbation-based testing to a structured, feature-based exploration of the input space that is both effective and interpretable.