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 |