# Scalable Mutual Information Estimation using Dependence Graphs

arXiv: https://arxiv.org/abs/1801.09125 · HTML: https://mlsanity.com/paper/1801.09125/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2018.

## Built on by (most cited first, 22 of 22)

- [To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review](https://mlsanity.com/paper/2304.09355/) (2023)
- [Bridging Information-Theoretic and Geometric Compression in Language Models](https://mlsanity.com/paper/2310.13620/) (2023)
- [Information Bottleneck Analysis of Deep Neural Networks via Lossy Compression](https://mlsanity.com/paper/2305.08013/) (2023)
- [Towards Tracing Trustworthiness Dynamics: Revisiting Pre-training Period of Large Language Models](https://mlsanity.com/paper/2402.19465/) (2024)
- [Information Bottleneck: Exact Analysis of (Quantized) Neural Networks](https://mlsanity.com/paper/2106.12912/) (2021)
- [A Quantitative Metric for Privacy Leakage in Federated Learning](https://mlsanity.com/paper/2102.13472/) (2021)
- [Diffeomorphic Information Neural Estimation](https://mlsanity.com/paper/2211.10856/) (2022)
- [HRel: Filter Pruning based on High Relevance between Activation Maps and Class Labels](https://mlsanity.com/paper/2202.10716/) (2022)
- [High-Dimensional Smoothed Entropy Estimation via Dimensionality Reduction](https://mlsanity.com/paper/2305.04712/) (2023)
- [MIND: Inductive Mutual Information Estimation, A Convex Maximum-Entropy Copula Approach](https://mlsanity.com/paper/2102.13182/) (2021)
- [Real-World Graph Convolution Networks (RW-GCNs) for Action Recognition in Smart Video Surveillance](https://mlsanity.com/paper/2201.05739/) (2022)
- [Consistency regularization-based Deep Polynomial Chaos Neural Network Method for Reliability Analysis](https://mlsanity.com/paper/2203.15655/) (2022)
- [Data Encoding For Healthcare Data Democratisation and Information Leakage Prevention](https://mlsanity.com/paper/2305.03710/) (2023)
- [Entropy-Based Non-Invasive Reliability Monitoring of Convolutional Neural Networks](https://mlsanity.com/paper/2508.21715/) (2025)
- [Towards Theoretical Analysis of Transformation Complexity of ReLU DNNs](https://mlsanity.com/paper/2205.01940/) (2022)
- [Phase transitions reveal hierarchical structure in deep neural networks](https://mlsanity.com/paper/2512.11866/) (2025)
- [Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures](https://mlsanity.com/paper/2305.07138/) (2023)
- [Understanding the role of autoencoders for stiff dynamical systems using information theory](https://mlsanity.com/paper/2503.06325/) (2025)
- [A Theoretical Perspective on Subnetwork Contributions to Adversarial Robustness](https://mlsanity.com/paper/2307.03803/) (2023)
- [Modeling Systemic Risk: A Time-Varying Nonparametric Causal Inference Framework](https://mlsanity.com/paper/2312.16707/) (2023)
- [Concept Probing: Where to Find Human-Defined Concepts (Extended Version)](https://mlsanity.com/paper/2507.18681/) (2025)
- [Information-Theoretic Greedy Layer-wise Training for Traffic Sign Recognition](https://mlsanity.com/paper/2510.27651/) (2025)

## Abstract (arXiv)

The Mutual Information (MI) is an often used measure of dependency between two random variables utilized in information theory, statistics and machine learning. Recently several MI estimators have been proposed that can achieve parametric MSE convergence rate. However, most of the previously proposed estimators have the high computational complexity of at least O(N2). We propose a unified method for empirical non-parametric estimation of general MI function between random vectors in ℝd based on N i.i.d. samples. The reduced complexity MI estimator, called the ensemble dependency graph estimator (EDGE), combines randomized locality sensitive hashing (LSH), dependency graphs, and ensemble bias-reduction methods. We prove that EDGE achieves optimal computational complexity O(N), and can achieve the optimal parametric MSE rate of O(1/N) if the density is d times differentiable. To the best of our knowledge EDGE is the first non-parametric MI estimator that can achieve parametric MSE rates with linear time complexity. We illustrate the utility of EDGE for the analysis of the information plane (IP) in deep learning. Using EDGE we shed light on a controversy on whether or not the compression property of information bottleneck (IB) in fact holds for ReLu and other rectification functions in deep neural networks (DNN).