💻 computer science

DISC: Dimension-Informed Clustering with Entropy Metric Warping and Attractor Basins

DISC is a novel graph-based clustering algorithm that leverages local geometric entropy to warp affinity metrics and construct a clean, fragmented graph, which is then partitioned into highly pure attractor basins via a depth-guided flow and merged to achieve state-of-the-art performance across diverse datasets.

Original authors: Qin Xu, Chenggang Xu, Hao Helen Zhang, Tian Xu

Published 2026-10-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Qin Xu, Chenggang Xu, Hao Helen Zhang, Tian Xu

Original paper licensed under CC BY 4.0 (https://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

In the vast landscape of modern data science, researchers often face a problem that feels like trying to organize a chaotic library where the books have no titles and the shelves are invisible. The data they work with—images, voices, sensor readings, or text—exists in a high-dimensional space, a mathematical realm with far more directions than the three dimensions of our physical world. To make sense of this, scientists rely on a concept called the manifold hypothesis, which suggests that even though data points might look scattered in this high-dimensional space, they actually cluster together along lower-dimensional shapes, like threads or sheets, hidden within the chaos. The standard way to find these hidden groups is to build a map of connections, linking each point to its nearest neighbors. If two points are close, they are likely part of the same group. However, this traditional approach treats every neighborhood the same, assuming that the space around a data point looks the same in every direction, much like a flat, uniform floor. In reality, data is rarely so uniform; some areas are stretched out along a single line, while others spread out in many directions at once.

A team of researchers at Xgen AI has developed a new method called DISC, which stands for Dimension-Informed Spectral-entropy Clustering, to solve this problem by letting the local shape of the data dictate how connections are made. Instead of treating every neighborhood as a flat, uniform space, DISC measures how many directions the data spreads out in a specific local area. They call this measurement local spectral entropy. If the data in a small neighborhood is tightly packed along a single line, the entropy is low; if it spreads out in many directions, the entropy is high. The researchers use this measurement to warp the distances between points. When the data is spread out in many directions, the method effectively shortens the distances, making neighbors feel closer. When the data is confined to a narrow path, the method lengthens the distances, pushing points apart. This creates a more accurate map of the data's true structure, where connections are only trusted if both points strongly agree that they belong together.

The process begins by calculating these warped distances and then applying a strict filter called a reciprocity gate. This gate acts like a double-check system: a connection between two points is only kept if both points consider each other to be strong neighbors. This step removes a significant amount of "noise" or false connections that usually plague clustering methods, specifically cutting the weight of connections between different groups in half compared to standard methods. However, this strict filtering leaves the map fragmented, broken into many small, isolated islands rather than one continuous network. To solve this, the researchers do not try to force a global solution. Instead, they let each point flow toward a deeper, more stable neighbor, following the strongest available connection. This creates small, highly pure groups called attractor basins, where almost every point inside belongs to the same true category. Finally, these small basins are merged together using a careful averaging process to form the final clusters.

The results of this approach are striking across a wide variety of real-world data. The researchers tested DISC on seventeen different datasets, ranging from images of handwritten digits and faces to speech recordings, sensor data from smartphones, and text documents. In these tests, the new method consistently outperformed established techniques like K-Means, spectral clustering, and density-based methods. On the majority of these datasets, DISC produced clusters that matched the true categories of the data with significantly higher accuracy. For instance, on a dataset of handwritten digits, the method achieved a level of purity where the resulting groups were nearly perfect matches for the actual numbers. Even more impressively, the method performed just as well on eight datasets that were never used during its development, proving that it is not simply memorizing the training data but has learned a general principle for finding structure. The method is also efficient, capable of processing 70,000 data points in just 3.5 seconds, making it fast enough for large-scale applications.

While the method shows great promise, the researchers acknowledge that it is not a perfect solution for every scenario. The process of merging the small, pure basins into final clusters can sometimes introduce errors, particularly in datasets with complex or irregular shapes, where the method occasionally trails behind other advanced techniques. Additionally, the method relies on a fixed setting for the size of the neighborhood it examines, and if this setting is too small, the method can fail to find the correct structure. Despite these limitations, the core innovation—using the local geometry of the data to warp distances and create a cleaner, more reliable map—represents a significant step forward. By allowing the data itself to define the rules of connection rather than imposing a uniform structure, DISC offers a more nuanced and accurate way to uncover the hidden patterns that organize our complex digital world.

Technical Summary: DISC (Dimension-Informed Clustering with Entropy Metric Warping and Attractor Basins)

Problem Statement

Graph-based clustering relies on constructing a neighborhood graph to partition data, operating under the manifold hypothesis that high-dimensional data concentrate near lower-dimensional structures. However, standard constructions often treat all neighborhoods uniformly, failing to account for the varying intrinsic dimensionality and local geometry of real-world data. While some methods adapt to local density, they frequently ignore local shape. Consequently, edges between distinct classes may merge clusters, while missing edges within a class may split them. The challenge lies in building a graph that respects the local geometry—specifically, the number of directions in which data spreads locally—to produce cleaner, more accurate partitions without relying on joint representation learning.

Methodology

The proposed method, DISC (Dimension-Informed Spectral-entropy Clustering), addresses this by letting local geometry dictate edge trustworthiness through a four-stage process:

1. Local Spectral Entropy and Metric Warping

For each point $x_i$ , DISC computes the local covariance matrix of its $k$ nearest neighbors. The eigenvalues of this covariance are normalized to form a probability vector representing the share of local variance along principal directions. The local spectral entropy $H(x_i)$ is calculated as the Shannon entropy of this vector:
$H_i = -\sum_{t=1}^D q_{i,t} \ln q_{i,t}$
where $q_{i,t}$ is the normalized eigenvalue share. The exponential of this entropy, $\exp(H_i)$ , serves as the effective number of directions the data locally occupies.

This entropy defines a conformal metric warping $g_i = H_i^{-2} I$ . Under this metric, distances from low-entropy (nearly low-dimensional) neighborhoods are lengthened, while distances from high-entropy (diffuse) neighborhoods are shortened. Directional affinities $p_{j|i}$ are then computed using a Gaussian kernel normalized over neighbors, utilizing this warped distance.

2. Reciprocity Gate

To reduce cross-class noise, DISC applies a reciprocity gate. An edge between $i$ and $j$ is retained only if both endpoints strongly endorse it. Specifically, the edge weight is non-zero only if the minimum of the two directional affinities exceeds the median of all such minimums among mutual neighbor pairs. This process effectively halves the cross-class edge weight compared to a standard $k$ -NN graph but results in a sparse, fragmented graph.

3. Attractor Basin Partitioning

Because the gated graph is too sparse for global spectral partitioning, DISC performs a local partitioning:

Depth: Each point's depth is defined as its gated degree divided by its local spectral entropy.
Flow: Each point follows its strongest gated edge toward a neighbor with greater depth. This process repeats until an attractor (a point with no deeper gated neighbors) is reached.
Basins: The data is partitioned into attractor basins, where each basin is a tree rooted at an attractor. These basins are observed to be highly class-pure.
Isolated Points: Points with no gated edges are assigned to the basin of their nearest connected neighbor.

4. Basin Merging

The final clusters are formed by merging the attractor basins using average linkage. The affinity between basins is computed based on symmetrized directional affinities (including pairs removed by the gate). The algorithm iteratively merges the pair of clusters with the highest average affinity until the desired number of clusters $c$ is reached. If no positive affinity remains, clusters are merged based on centroid proximity.

Key Contributions

Local Spectral Entropy: Introduces a metric where the exponential of entropy represents the effective number of local directions, used to warp the distance metric conformally.
Reciprocity Gate: A mechanism that produces a graph with significantly reduced cross-class edge weight (approximately half that of a standard $k$ -NN graph) by retaining only mutually endorsed edges.
Attractor-Basin Partitioning: A clustering strategy that avoids eigenvectors and modularity optimization, instead using a hill-climbing flow on the gated graph to form pure local basins, which are subsequently merged.
Comprehensive Evaluation: A rigorous evaluation across 17 datasets (9 benchmark, 8 held-out) covering images, text, speech, and sensor data, demonstrating robustness without overfitting to development data.

Results

DISC was evaluated against K-Means, Ward linkage, Spectral Clustering, DBSCAN, HDBSCAN, and Leiden community detection on 17 datasets.

Performance: DISC outperformed K-Means on 14 datasets in Adjusted Rand Index (ARI) and 13 datasets in Accuracy. It outperformed Ward linkage and Spectral Clustering on 15 datasets for both metrics. It outperformed DBSCAN and HDBSCAN on all 17 datasets with statistically significant gains ( $p \le 10^{-10}$ ).
Generalization: The performance gains were consistent on the 8 held-out datasets (never used during development), indicating the method is not overfit.
Comparison with Leiden: DISC is statistically on par with Leiden community detection, sharing the best mean ARI rank. DISC excels on datasets with small classes (e.g., Olivetti) and specific held-out sets, while Leiden performs better on deep image features (CIFAR-10) and Satimage.
Scalability: DISC scales efficiently, processing 70,000 MNIST points in 3.5 seconds with a runtime scaling exponent of approximately 1.5, comparable to Leiden and significantly faster than spectral clustering.
Internal Metrics: While DISC achieves high external accuracy, it yields lower Silhouette coefficients than density-based methods (DBSCAN/HDBSCAN). The authors note this is because Silhouette rewards compact, convex shapes, whereas DISC captures curved or elongated class structures.

Significance and Claims

The paper claims that DISC offers a robust, geometry-aware alternative to traditional graph-based clustering. By utilizing local spectral entropy to warp metrics and employing a reciprocity gate, DISC constructs a "clean" graph that minimizes cross-class connections. The subsequent attractor-basin approach allows for effective clustering without the computational cost of global eigendecomposition or the need for learned representations.

The authors emphasize that DISC is designed for fixed data representations (e.g., ResNet features) rather than joint representation learning. The method's ability to generalize to unseen datasets and its statistical parity with Leiden suggest it is a strong general-purpose clustering tool that effectively leverages local dimensionality to improve cluster purity and separation. The primary limitation noted is that the final merging step (average linkage) may introduce errors on specific datasets, suggesting that improved merging criteria could be a future avenue for enhancement.