Nonparametric Dependency Estimation via Minimal Spanning Trees

16 concepts9 papers1 proposal

Imagine you have two high-dimensional datasets and want to know if they come from the same underlying probability distribution. Or perhaps you want to measure the mutual information between two complex variables to select the best features for a machine learning model. Traditionally, answering these questions requires estimating the probability density functions (PDFs) of the data. However, explicit density estimation suffers from the curse of dimensionality: as the number of dimensions grows, data becomes exponentially sparse, causing classical methods like histograms or kernel density estimation to break down.

To bypass this limitation, a powerful geometric framework has emerged. Instead of estimating what the density looks like everywhere, we can look at the local geometry of the data points using graph-theoretic structures like Minimal Spanning Trees (MSTs). By analyzing how points from different groups connect to one another, we can directly estimate divergence, dependency, and information bounds without ever calculating a single probability density.

The Core Intuition: Intermingling vs. Separation

To understand why this works, consider a simple thought experiment. Suppose you have two sets of points—red and blue—sampled from two distributions, $P$ and $Q$. If you pool these points together into a single dataset and construct a Euclidean Minimum Spanning Tree (an MST, which connects all points such that the total edge length is minimized), what will the edges look like?

  • Scenario 1 ($P = Q$): If the two distributions are identical, the red and blue points will be thoroughly intermingled. Because the points are mixed together uniformly, the closest neighbor to a red point is just as likely to be blue as it is to be red. Consequently, the MST will contain a large number of "cross-group" edges connecting a red node to a blue node.
  • Scenario 2 ($P \neq Q$): If the distributions are distinct, the red points will cluster in one region of the space, and the blue points will cluster in another. When the MST minimizes edge lengths, it will naturally draw edges within the red cluster and within the blue cluster. The only cross-group edges will be the few needed to bridge the gap between the two distinct clusters.

By simply counting the number of cross-group edges, we obtain a direct window into the similarity of the two distributions. A significantly low count of cross-group edges indicates that the samples are drawn from distinct distributions.

Identical Distributions (P = Q)       Distinct Distributions (P ≠ Q)
      Red and Blue mixed                     Red and Blue separated

         O---X---O                              O---O---O
        /     \   \                            /       /
       X       O   X                          O       O
        \     /   /                            .     .  <- Few cross-edges
         O---X---O                              X     X
                                               /       \
                                              X---X---X
   (High cross-group edges)                (Low cross-group edges)

Two-Sample Testing and Divergence Estimation

This edge-counting statistic forms the mathematical backbone for non-parametric hypothesis testing and divergence estimation. In A label-efficient two-sample test, Li et al. leverage MST-based hypothesis testing to evaluate distributional differences under strict label budgets, showing that counting edges bridging different classes provides a highly sensitive test for distinct distributions.

The utility of this approach extends directly to practical engineering problems. For example, in industrial process monitoring, An et al. use an edge-counting statistic on an MST to detect faults in iron-making processes in Graph-Based Method for Fault Detection in the Iron-Making Process. By normalizing the count of cross-group edges into a standardized statistic, the authors successfully differentiate true process anomalies from random noise without requiring expensive labeled data.

Beyond simple testing, the local geometry captured by MSTs can be used to estimate fundamental information-theoretic quantities. As shown by Hero III et al. in Empirical Non-Parametric Estimation of the Fisher Information, graph-based statistics effectively capture distributional changes by analyzing local geometry, allowing for the non-parametric estimation of divergence and the Fisher Information Matrix without global density assumptions. Furthermore, Sekeh et al. demonstrate in Convergence Rates for Empirical Estimation of Binary Classification Bounds that this graph-theoretic approach provides a rigorous foundation for estimating empirical binary classification bounds, offering fast convergence rates in high-dimensional settings.

From Divergence to Mutual Information

How do we transition from measuring the divergence between two distinct datasets to measuring the dependency between variables $X$ and $Y$ within the same dataset? The answer lies in a clever permutation trick.

Recall that $X$ and $Y$ are independent if and only if their joint distribution $P(X, Y)$ equals the product of their marginal distributions $P(X)P(Y)$. To measure dependency, we can create a synthetic dataset representing the product of marginals by randomly shuffling the $Y$ values relative to the $X$ values, breaking any existing relationships.

In Geometric Estimation of Multivariate Dependency, Hero et al. introduce Geometric Mutual Information (GMI) based on this exact principle. By constructing an MST over a combined dataset of the original (joint) samples and the shuffled (marginal) samples, the authors count the edges connecting original points to shuffled points. This graph-theoretic dependency estimation bypasses the computational instability and high costs of explicit density estimation, providing a consistent statistical measurement of multivariate relationships in high-dimensional spaces where traditional kernel methods fail. Crucially, the authors prove that these geometric measures satisfy fundamental information-theoretic properties, such as convexity, the chain rule, and the data processing inequality.

Original Joint Samples (X, Y)          Shuffled Marginal Samples (X, Y_shuffled)
   (Preserves Dependency)                     (Breaks Dependency)
          |                                          |
          +--------------------+---------------------+
                               |
                               v
                     Combined Dataset Graph
                               |
                               v
                 Count Cross-Group Edges (GMI)

Application to Feature Selection and Conditional Dependence

Because geometric dependency estimation is fully non-parametric and scales efficiently, it is uniquely suited for high-dimensional feature selection, even when data arrives in streams or contains multi-labeled targets.

For instance, in Geometric Online Adaptation: Graph-Based OSFS for Streaming Samples, Sekeh et al. utilize MST edge lengths to capture spatial distributions and relative spacing. This allows them to robustly estimate feature relevance in streaming environments where traditional histogram-based mutual information fails due to limited sample sizes.

When dealing with complex multi-class problems, Sekeh et al. extend this framework to estimate Conditional Mutual Information (CMI) in Feature Selection for multi-labeled variables via Dependency Maximization.. By leveraging the Friedman-Rafsky edge-counting statistic on a global MST, the authors maximize dependency between features and multi-labeled targets without explicit density estimation, providing a computationally tractable alternative for feature selection.

Similarly, the concept can be generalized to broader topological spaces. In Kernel Partial Correlation Coefficient - a Measure of Conditional Dependence, Sen et al. introduce a non-parametric measure of conditional dependence that leverages K-nearest neighbor (K-NN) graphs and MSTs. Their approach avoids density estimation entirely and operates with near-linear computational complexity, capturing complex non-linear relationships effortlessly.

Finally, understanding the geometry of these statistical models helps map out the fundamental limits of learning itself. For instance, Han et al. demonstrate in Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints that analyzing the geometric properties of a model's score functions can establish sharp lower bounds for parameter estimation under communication constraints, highlighting how geometry underpins both the estimation algorithms and their theoretical limits.

Key Foundational Work

Empirical non-parametric estimation of the Fisher Information (2015) — contributed 2 concept elements to this direction.
Convergence Rates for Empirical Estimation of Binary Classification Bounds (2018) — contributed 1 concept elements to this direction.
Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geometric_dependency_estimation_f468029f,
  title = {geometric dependency estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-dependency-estimation/rdr_f468029fc7164e328ecdafadb1e3b412},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_geometric_dependency_estimation_f468029f_v1,
  title = {geometric dependency estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-dependency-estimation/rdr_f468029fc7164e328ecdafadb1e3b412/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake