GRAPH MATCHING AND VERTEX NOMINATION

Abstract

When given a collection of graphs on over-lapping, but possibly non-identical, vertex sets, many inference tasks involve learning the across-network alignment. Often, this task is difficult due to the enormity of the graphs, as network alignment (that is, graph matching) is NP-hard in its most general form. That being said, often a partial alignment is known a priori. We leverage the knowledge of this partial alignment (seeds) to assist the graph matching task. We further present principled methods of handling non-identical vertex sets and multiple-node alignment for both the tasks of graph matching and vertex nomination. We demonstrate the applicability of our methodologies via synthetic and real-data experiments. In particular, we show a real-time example of network alignment of the left- and right-hemispheres for the Drosophila larvae connectome and demonstrate that our structure-based algorithm improves their currently used techniques. Further, inspired by the nuances inherent in this data, and in particular the presence of neural type-based correlation, we present a network model which is robust enough to handle this type of data while still being practical in the sense that statistical theory is still relevant. We compare this model to other network models and present relevant existing theory.