Ming Li

The relationship between the Bayesian approach and the minimum description length approach is established. We sharpen and clarify the general modeling principles minimum description length (MDL) and minimum message length (MML), abstracted as the ideal MDL principle and defined from Bayes's rule by means of Kolmogorov complexity. The basic condition under which the ideal principle should be applied is encapsulated as the fundamental inequality, which in broad terms states that the principle is valid when the data are random, relative to every contemplated hypothesis and also these hypotheses are random relative to the (universal) prior. The ideal principle states that the prior probability associated with the hypothesis should be given by the algorithmic universal probability, and the sum of the log universal probability of the model plus the log of the probability of the data given the model should be minimized. If we restrict the model class to finite sets then application of the ideal principle turns into Kolmogorov's minimal sufficient statistic. In general, we show that data compression is almost always the best strategy, both in model selection and prediction.

Deep neural networks for graphs (DNNGs) represent an emerging field that studies how the deep learning method can be generalized to graph-structured data. Since graphs are a powerful and flexible tool to represent complex information in the form of patterns and their relationships, ranging from molecules to protein-to-protein interaction networks, to social or transportation networks, or up to knowledge graphs, potentially modeling systems at very different scales, these methods have been exploited for many application domains.

The nature of heterophilous graphs is significantly different from that of homophilous graphs, which causes difficulties in early graph neural network (GNN) models and suggests aggregations beyond the one-hop neighborhood. In this article, we develop a new way to implement multiscale extraction via constructing Haar-type graph framelets with desired properties of permutation equivariance, efficiency, and sparsity, for deep learning tasks on graphs. We further design a graph framelet neural network model permutation equivariant graph framelet augmented network (PEGFAN) based on our constructed graph framelets. The experiments are conducted on a synthetic dataset and nine benchmark datasets to compare the performance with other state-of-the-art models. The result shows that our model can achieve the best performance on certain datasets of heterophilous graphs (including the majority of heterophilous datasets with relatively larger sizes and denser connections) and competitive performance on the remaining.