Unsupervised and universal data reduction and network sparsification methods by minimal algorithmic information loss

​We introduce a family of unsupervised domain-free and (asymptotically) model-independent algorithms based on algorithmic information theory designed to minimize the loss of any (enumerable computable) property contributing to the object's algorithmic content and thus important to preserve in the process of data dimension reduction when forcing the algorithm to delete the least important features. Being independent of any particular criterion and of general purpose, they are universal in a fundamental mathematical sense. Using suboptimal approximations of efficient (polynomial) estimations we demonstrate how to preserve network properties outperforming other (leading) algorithms for network dimension reduction. Our method preserves all graph-theoretic indices measured, ranging from degree distribution, clustering coefficient, edge betweenness, and degree and eigenvector centralities. We conclude and demonstrate numerically that our unsupervised, Minimal Information Loss Sparsification (MILS) method is robust, has the potential to maximize the preservation of all recursively enumerable features in data and networks, and achieves equal to significantly better results than other data reduction and network sparsification methods.

Unsupervised and universal data reduction and network sparsification methods.pdf