IJCAI 2016 Tutorial: Pattern Recognition for Random Graphs

A graph is a representation of a collection of interacting objects. The objects are referred to as nodes or vertices, and the interactions are referred to as edges or links. In a neural connectome, the vertices represent neurons, and the edges represent synapses. In a social network, the vertices are people and the edges are their relationships. The field of pattern recognition developed significantly in the 1960s, and the field of random graph inference has enjoyed much recent progress in both theory and application. This tutorial focuses on pattern recognition in the context of a particular family of random graphs, namely the stochastic blockmodels, from the two main perspectives of single graph inference and joint graph inference.


Single graph inference is the performance of statistical inference on one single observed graph. Given a single graph realized from a stochastic blockmodel, we here consider the specific exploitation tasks of vertex classification, clustering, and nomination. The theoretical guarantees of these methods are proved and their effectiveness are demonstrated in simulation as well as real datasets including communication network, online advertising, and neural connectomes. We are also concerned with joint graph inference, which involves the joint space of multiple graphs. Specifically, given two graphs, we consider the tasks of seeded graph matching for large graphs and joint vertex classification. The methodologies are shown to discover signals in the joint geometry of diffusion tensor MRI and the Caenorhabditis elegans neural connectomes.