Search

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. Index Terms--Canadian traveller problem, disambiguation protocol, probabilistic path planning, random disambiguation path, visibility graph.

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 provea spherical homeomorphism theorem which is valid for all digital images when utilizing the (26,6)-connectivity rule. Index Terms--Digital topology, spherical homeomorphism.

The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describe a comprehensive paradigm for statistical inference on random dot product graphs, a paradigm centered on spectral embeddings of adjacency and Laplacian matrices. We examine the graph-inferential analogues of several canonical tenets of classical Euclidean inference. In particular, we summarize a body of existing results on the consistency and asymptotic normality of the adjacency and Laplacian spectral embeddings, and the role these spectral embeddings can play in the construction of single- and multi-sample hypothesis tests for graph data. We investigate several real-world applications, including community detection and classification in large social networks and the determination of functional and biologically relevant network properties from an exploratory data analysis of the Drosophila connectome. We outline requisite background and current open problems in spectral graph inference. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]

Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance. [ABSTRACT FROM AUTHOR]

Graph matching is an important problem in machine learning and pattern recognition. Herein, we present theoretical and practical results on the consistency of graph matching for estimating a latent alignment function between the vertex sets of two graphs, as well as subsequent algorithmic implications when the latent alignment is partially observed. In the correlated Erdős-Rényi graph setting, we prove that graph matching provides a strongly consistent estimate of the latent alignment in the presence of even modest correlation. We then investigate a tractable, restricted-focus version of graph matching, which is only concerned with adjacency involving vertices in a partial observation of the latent alignment; we prove that a logarithmic number of vertices whose alignment is known is sufficient for this restricted-focus version of graph matching to yield a strongly consistent estimate of the latent alignment of the remaining vertices. We show how Frank-Wolfe methodol- ogy for approximate graph matching, when there is a partially observed latent alignment, inherently incorporates this restricted-focus graph matching. Lastly, we illustrate the rela- tionship between seeded graph matching and restricted-focus graph matching by means of an illuminating example from human connectomics. [ABSTRACT FROM AUTHOR]

For random graphs distributed according to a stochastic block model, we consider the inferential task of partitioning vertices into blocks using spectral techniques. Spectral partitioning using the normalized Laplacian and the adjacency matrix have both been shown to be consistent as the number of vertices tend to infinity. Importantly, both procedures require that the number of blocks and the rank of the communication probability matrix be known, even as the rest of the parameters may be unknown. In this paper, we prove that the (suitably modified) adjacency-spectral partitioning procedure, requiring only an upper bound on the rank of the communication probability matrix, is consistent. Indeed, this result demonstrates a robustness to model mis-specification; an overestimate of the rank may impose a moderate performance penalty, but the procedure is still consistent. Furthermore, we extend this procedure to the setting where adjacencies may have multiple modalities and we allow for either directed or undirected graphs. [ABSTRACT FROM AUTHOR]

Copyright of Naval Research Logistics is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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. [ABSTRACT FROM AUTHOR]

Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)⩽Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound Rk(G)=O(√ of 2rk(G)) and we show that this bound is sharp. [Copyright &y& Elsevier]

In this paper we exhibit, under suitable conditions, a neat relationship between the Moore­Penrose generalized inverse of a sum of two matrices and the Moore­Penrose generalized inverses of the individual terms. We include an application to the parallel sum of matrices. [ABSTRACT FROM AUTHOR]

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 [2] 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. [ABSTRACT FROM AUTHOR]