Nonparametric small random networks for graph-structured pattern recognition

Taking inspiration from the probabilistic principles underlying the topological regularities observed in random networks, the paper presents a simple and efficient Bayesian framework for the classification of (small) labeled random networks. The proposed “graphical model” relies on a Parzen window estimate of the pairwise vertex-vertex probability distribution under an implicit Markov assumption. Experiments show that, in spite of its simplicity, the approach is at least as accurate as the state-of-the-art machines. The highest average recognition accuracies to date were obtained on the friendly + unfriendly Mutagenesis classification task.