Skip to main content
Back to timeline
arXivSource publication:

Entropy alone prefers shredded graphs: DEFI prices volume normalization and recovers the true partition in 97.2% of 243 conditions

Synopsis

When choosing a partition on a graph, minimizing entropy alone favors shredding the graph, because deleting edges changes both spectral concentration and graph-volume normalization. DEFI combines a spectral entropy difference, a partition entropy, an information-bottleneck stability anchor and penalties on dimensionality, imbalance and fragmentation into one criterion computed from the Laplacian spectrum of an affinity graph, without inverse-covariance estimation. Across a 243-condition factor-recovery benchmark, DEFI reached an exact recovery rate of 97.2%, versus 75.0% for EGA-TMFG and 45.8% for TEFI on von Neumann entropy.

Interpretation

Candidate partitions can now be scored by one criterion that weighs spectral concentration, representation complexity and structural regularity together, rather than relying on entropy reduction alone. Unregularized entropic criteria improve monotonically under partition refinement and favor degenerate singletons or splinter clusters; network-based entropy criteria rely on inverse-covariance estimators that become ill-conditioned under factor collinearity or disconnected graphs. Across a 243-condition factor-recovery benchmark spanning factor correlations, loading strengths and measurement types, DEFI achieved an overall exact recovery rate of 97.2%, versus 75.0% for EGA-TMFG and 45.8% for TEFI on von Neumann entropy.

The criterion splits the spectral entropy change caused by cutting edges into two terms, one rewarding spectral concentration and one moving oppositely as graph volume shrinks, and the latter is the source of the degenerate-cut preference. At Rényi order 2 the spectral entropy difference is exactly a trace-concentration term minus a graph-volume normalization term, so the structural penalties are a mathematical guard against this failure mode rather than a heuristic patch. In controlled local candidate batteries that distinguish the true model from adjacent and factor-split alternatives, DEFI identified the correct partition in 99.2% of replications; over complete partition lattices for 6 to 12 items, up to 700,074 structures were enumerated.

The same criterion is solved over mixture, hierarchical and subspace candidate classes by continuous relaxation and CMA-ES, turning the discrete cluster-count decision into a continuous search. Cluster count is a discrete variable and direct search stalls at integer boundaries; DEFI relaxes it to a real coordinate with a piecewise linear homotopy between adjacent integers and applies an infeasibility penalty to splinter clusters below the minimum size. Across ten clustering benchmarks, DEFI-guided Gaussian mixtures reached a mean ARI of 0.929, above HDBSCAN at 0.809, Ward clustering at 0.700 and conventional GMM criteria at 0.501 to 0.580; on 26 high-dimensional datasets, DEFI-DR recovered the reference dimension on 25 of 26.

Perspective

These results target offline exploratory analyses that must resolve model order or latent dimensionality under adverse structural conditions such as severe collinearity, weak indicator separation and non-convex manifold geometries; the evaluation covers a 243-condition factor-recovery benchmark, complete partition lattices of up to 700,074 structures, ten clustering benchmarks and 26 high-dimensional datasets. DEFI selects only within the evaluated candidate class and cannot repair a misspecified generator; on geometries such as WingNut, narrow bridge connections and non-convex curves elude elliptical Gaussian components without prior manifold unfolding.

The unsupervised stability anchor is fixed a priori by Gaussian jitter, and sensitivity to alternative perturbation schemes remains an open question; where supervised labels or downstream predictive losses are directly accessible, cross-validation against the supervised objective is preferable to optimizing an unsupervised information-bottleneck anchor. Theoretical selection consistency holds only over finite, margin-separated candidate classes, and uniform convergence over a continuous parameter space is not established; if the same graph is used both to select a partition and to estimate its entropy, selection effects invalidate the fixed-partition variance statements.