Matchability of heterogeneous networks pairs.

We consider the problem of graph matchability in non-identically distributed networks. In a general class of edge-independent networks, we demonstrate that graph matchability can be lost with high probability when matching the networks directly. We further demonstrate that under mild model assumptions, matchability is almost perfectly recovered by centering the networks using universal singular value thresholding before matching. These theoretical results are then demonstrated in both real and synthetic simulation settings. We also recover analogous core-matchability results in a very general core-junk network model, wherein some vertices do not correspond between the graph pair.

Matched Filters for Noisy Induced Subgraph Detection.

The problem of finding the vertex correspondence between two noisy graphs with different number of vertices where the smaller graph is still large has many applications in social networks, neuroscience, and computer vision. We propose a solution to this problem via a graph matching matched filter: centering and padding the smaller adjacency matrix and applying graph matching methods to align it to the larger network. The centering and padding schemes can be incorporated into any algorithm that matches using adjacency matrices. Under a statistical model for correlated pairs of graphs, which yields a noisy copy of the small graph within the larger graph, the resulting optimization problem can be guaranteed to recover the true vertex correspondence between the networks. However, there are currently no efficient algorithms for solving this problem. To illustrate the possibilities and challenges of such problems, we use an algorithm that can exploit a partially known correspondence and show via varied simulations and applications to Drosophila and human connectomes that this approach can achieve good performance.

Connectome Smoothing via Low-Rank Approximations.

In brain imaging and connectomics, the study of brain networks, estimating the mean of a population of graphs based on a sample is a core problem. Often, this problem is especially difficult because the sample or cohort size is relatively small, sometimes even a single subject, while the number of nodes can be very large with noisy estimates of connectivity. While the element-wise sample mean of the adjacency matrices is a common approach, this method does not exploit the underlying structural properties of the graphs. We propose using a low-rank method that incorporates dimension selection and diagonal augmentation to smooth the estimates and improve performance over the naïve methodology for small sample sizes. Theoretical results for the stochastic block model show that this method offers major improvements when there are many vertices. Similarly, we demonstrate that the low-rank methods outperform the standard sample mean for a variety of independent edge distributions as well as human connectome data derived from the magnetic resonance imaging, especially when the sample sizes are small. Moreover, the low-rank methods yield "eigen-connectomes," which correlate with the lobe-structure of the human brain and superstructures of the mouse brain. These results indicate that the low-rank methods are the important parts of the toolbox for researchers studying populations of graphs in general and statistical connectomics in particular.

Consistent latent position estimation and vertex classification for random dot product graphs.

In this work, we show that using the eigen-decomposition of the adjacency matrix, we can consistently estimate latent positions for random dot product graphs provided the latent positions are i.i.d. from some distribution. If class labels are observed for a number of vertices tending to infinity, then we show that the remaining vertices can be classified with error converging to Bayes optimal using the $(k)$-nearest-neighbors classification rule. We evaluate the proposed methods on simulated data and a graph derived from Wikipedia.

Association between visceral adiposity and colorectal polyps on CT colonography.

OBJECTIVE: The purpose of this article is to determine whether there is an association between visceral adiposity measured on CT colonography (CTC) and colorectal polyps. MATERIALS AND METHODS: Patients who underwent CTC and same-day optical colonoscopy (n = 1186) were analyzed. Visceral adipose tissue volumes and volume percentages relative to total internal body volume were measured on slices in the L2-L3 regions on supine CTC scans with validated fully automated software. Student t test, odds ratio, logistic regression, and receiver operating characteristic analyses were performed. RESULTS: For subjects with (n = 345) and without (n = 841) adenomatous polyps, the mean (± SD) volume percentages were 31.2% ± 10.8% and 28.2% ± 11.3%, respectively (p < 0.0001). For subjects with (n = 244) and without (n = 942) hyperplastic polyps, the volume percentages were 31.8% ± 10.7% and 28.3% ± 11.2%, respectively (p < 0.0001). Comparing the lowest and highest quintiles of volume percentage, the odds ratios for having at least one adenomatous polyp or hyperplastic polyp versus no polyp were 2.06 (95% CI, 1.36-3.13) and 1.71 (95% CI, 1.08-2.71), and the prevalence of having adenomatous polyps or hyperplastic polyps increased by 14% and 8%, respectively. CONCLUSION: Subjects with higher visceral adiposity measurements on CTC have a greater risk for the presence of colonic polyps.