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 stateoftheart 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 variancereducing 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 RaoBlackwellization 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.
Collections
Related items
Showing items related by title, author, creator and subject.

Pattern Recognition on Random Graphs
Chen, Li (Johns Hopkins University, 20150317)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 dissertation focuses on pattern recognition ... 
Interval Digraphs
Reiland, Elizabeth Honda (Johns Hopkins UniversityUSA, 20190204)We say that a simple, undirected graph interval graph if there exists a function mapping the vertices of the graph to intervals such that each pair of vertices is adjacent if and only if the corresponding intervals have a ... 
GRAPH MATCHING AND VERTEX NOMINATION
Patsolic, Heather G; 0000000180055455 (Johns Hopkins UniversityUSA, 20200320)When given a collection of graphs on overlapping, but possibly nonidentical, vertex sets, many inference tasks involve learning the acrossnetwork alignment. Often, this task is difficult due to the enormity of the graphs, ...