GRAPH MATCHING AND CORRELATION FOR GRAPHS

Abstract

The graph matching problem is, given two graphs, to find the bijection between the vertex sets that best preserves the adjacency structure. It has been applied in many areas such as pattern recognition, object detection, and neuroscience, to name a few. Our first group of contributions: We modify the state-of-the-art approximate graph matching algorithm ``FAQ'' to approximately solve the graph matching problem when part of the bijection is fixed, adapt its applicability to include graphs with different sized vertex sets, and extend it so as to provide a nomination list of likely matches for each vertex. We also develop an algorithm to approximately solve the induced subgraph matching problem, and prove a consistency result. Our second group of contributions: When two graphs have a correlated Bernoulli distribution, we prove that the alignment strength of their natural bijection strongly converges to a novel measure of graph correlation ρT that neatly combines intergraph with intragraph distribution parameters. Within broad families of the random graph parameter settings, we illustrate that exact graph matching runtime and matchability are both functions of ρT. We then present the Phantom Alignment Strength Conjecture, which provides a principled and practical means of using alignment strength to assess if the graph matching solution is a good estimate of the true bijection. We provide empirical evidence for the conjecture and explore its consequences. Our third group of contributions: In the context of a correlated Bernoulli graph model, we introduce a new variance-reducing technique, called balancing, that can refine estimators for model parameters. Specifically, we construct a disagreement statistic and show that it is complete and sufficient; balancing can be interpreted as Rao-Blackwellization with this disagreement statistic. We show that for unbiased estimators of functions of model parameters, balancing generates uniformly minimum variance unbiased estimators (UMVUEs). However, even when unbiased estimators for model parameters do not exist—which, as we prove, is the case with the heterogeneity correlation and the total correlation parameters—balancing can still lower mean squared error. In particular, we demonstrate how balancing can improve the efficiency of the alignment strength estimator for the total correlation.