Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this article, we modify the state-of-the-art approximate graph matching algorithm “FAQ” of Vogelstein et al. (2015) to make it a fast approximate seeded graph matching algorithm, adapt its applicability to include graphs with differently sized vertex sets, and extend the algorithm so as to provide, for each individual vertex, a nomination list of likely matches. We demonstrate the effectiveness of our algorithm via simulation and real data experiments; indeed, knowledge of even a few seeds can be extremely effective when our seeded graph matching algorithm is used to recover a naturally existing alignment that is only partially observed.

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 also matchability are both functions of ϱT, with thresholding behavior starkly illustrated in matchability.

Given a graph in which a few vertices are deemed interesting a priori, the vertex nomination task is to order the remaining vertices into a nomination list such that there is a concentration of interesting vertices at the top of the list. Previous work has yielded several approaches to this problem, with theoretical results in the setting where the graph is drawn from a stochastic block model (SBM), including a vertex nomination analogue of the Bayes optimal classifier. In this paper, we prove that maximum likelihood (ML)-based vertex nomination is consistent, in the sense that the performance of the ML-based scheme asymptotically matches that of the Bayes optimal scheme. We prove theorems of this form both when model parameters are known and unknown. Additionally, we introduce and prove consistency of a related, more scalable restricted-focus ML vertex nomination scheme. Finally, we incorporate vertex and edge features into ML-based vertex nomination and briefly explore the empirical effectiveness of this approach.

Graph matching-aligning a pair of graphs to minimize their edge disagreements-has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational difficulty. Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance. A common technique is to relax the discrete problem to a continuous problem, therefore enabling practitioners to bring gradient-descent-type algorithms to bear. We prove that an indefinite relaxation (when solved exactly) almost always discovers the optimal permutation, while a common convex relaxation almost always fails to discover the optimal permutation. These theoretical results suggest that initializing the indefinite algorithm with the convex optimum might yield improved practical performance. Indeed, experimental results illuminate and corroborate these theoretical findings, demonstrating that excellent results are achieved in both benchmark and real data problems by amalgamating the two approaches.

Suppose there is a need to swiftly navigate through a spatial arrangement of possibly forbidden regions, with each region marked with the probability that it is, indeed, forbidden. In close proximity to any of these regions, you have the dynamic capability of disambiguating the region and learning for certain whether or not the region is forbidden - only in the latter case may you proceed through that region. The central issue is how to most effectively exploit this disambiguation capability to minimize the expected length of the traversal. Regions are never entered while they are possibly forbidden, and thus, no risk is ever actually incurred. Nonetheless, for the sole purpose of deciding where to disambiguate, it may be advantageous to simulate risk, temporarily pretending that possibly forbidden regions are riskily traversable, and each potential traversal is weighted with its level of undesirability, which is a function of its traversal length and traversal risk. In this paper, the simulated risk disambiguation protocol is introduced, which has you follow along a shortest traversal - in this undesirability sense - until an ambiguous region is about to be entered; at that location, a disambiguation is performed on this ambiguous region. (The process is then repeated from the current location, until the destination is reached.) We introduce the tangent arc graph as a means of simplifying the implementation of simulated risk disambiguation protocols, and we show how to efficiently implement the simulated risk disambiguation protocols that are based on linear undesirability functions. The effectiveness of these disambiguation protocols is illustrated with examples, including an example that involves mine countermeasures path planning.

Shattuck and Leahy [IEEE Trans. Med. Imag., 20 (2001), pp. 1167--1177] conjectured---and Abrams, Fishkind, and Priebe [IEEE Trans. Med. Imag., 21 (2002), pp. 1564--1566], [IEEE Trans. Med. Imag., 23 (2004), pp. 655--657] proved---that the boundary of a digital image is topologically equivalent to a sphere if and only if certain related foreground and background graphs are both trees. In this article we extend this result by proving upper and lower bounds on digital image boundary genus in terms of the foreground and background graphs, and we show that these bounds are best possible. Our results have current application to topology correction in medical imaging.

The spherical homeomorphism conjecture, proposed by Shattuck and Leahy in 2001, serves as the backbone of their algorithm to correct the topology of magnetic resonance images of the human cerebral cortex. Using a canonical image-thickening technique and the authors' previously proven "spherical homeomorphism theorem for surfaces," we formulate and prove a spherical homeomorphism theorem which is valid for all digital images when utilizing the (26,6)-connectivity rule.

The human cerebral cortex is topologically equivalent to a sphere when it is viewed as closed at the brain stem. Due to noise and/or resolution issues, magnetic resonance imaging may see "handles" that need to be eliminated to reflect the true spherical topology. Shattuck and Leahy present an algorithm to correct such an image. The basis for their correction strategy is a conjecture, which they call the spherical homeomorphism conjecture, stating that the boundary between the foreground region and the background region is topologically spherical if certain associated foreground and background multigraphs are both graph-theoretic trees. In this paper, we prove the conjecture, and its converse, under the assumption that the foreground/background boundary is a surface.