We focus on the problem of aligning graphs that have a spatial basis. In such graphs, which we refer to asrigid graphs, nodes have preferred positions relative to their graph neighbors. Rigid graphs can be used to abstract objects in diverse applications such as large biomolecules, where edges corresponding to chemical bonds have preferred lengths, functional connectomes of the human brain, where edges corresponding to co-firing regions of the brain have preferred anatomical distances, and mobile device/ sensor communication logs, where edges corresponding to point-to-point communications across devices have distance constraints. Effective analysis of such graphs must account for edge lengths in addition to topological features. For instance, when identifying conserved patterns through graph alignment, it is important for matched edges to have correlated lengths, in addition to topological similarity. In this paper, we formulate the problem ofrigid graph alignmentand present a method for solving it. Our formulation of rigid graph alignment simultaneously aligns the topology of the input graphs, as well as the geometric structure represented by the edge lengths, which is solved using a block coordinate descent technique. Using detailed experiments on real and synthetic datasets, we demonstrate a number of important desirable features of our method: (i) it significantly outperforms topological and structural aligners on a wide range of problems; (ii) it scales to problems in important real-world applications; and (iii) it has excellent stability properties, in view of noise and missing data in typical applications.

Dynamic graphs are natural abstractions for modeling correlations in brain activity. These correlation graphs are constructed from time-series signals corresponding to neuronal activity in different regions of the brain over suitably selected time windows, by linking correlated regions via edges. An important problem in the context of these dynamic correlation graphs is the discovery of sets of regions of the brain, whose activity level is temporally coherent. These manifest as temporally persistent sub-graphs that are strongly connected, referred to as coherent subgraphs. In this paper, we present a model and method for identifying coherent subgraphs in dynamic correlation graphs. We show that densely connected components in correlation graphs can be effectively modeled as low-rank sub-matrices derived from the time series signals. Specifically, we derive theoretical results showing that quasi cliques in a correlation graph can be inferred from rows of the left singular matrix of its time-series, and can be tracked in time to identify coherent subgraphs. We apply our proposed method to real-world time-series data from functional MRIs. We show that signals corresponding to nodes in coherent subgraphs can accurately predict whether the subject was actively performing a cognitive task, or was at rest. Furthermore, we also show that the same set of nodes can predict task outcomes/ conditions (such as win v/s loss in a gambling task). To the best of our knowledge, our work is the first in theoretically modeling and analyzing dynamic brain networks using spectral decomposition of the windowed time-series.

Advances in imaging technologies, combined with inexpensive storage, have led to an explosion in the volume of publicly available neuroimaging datasets. Effective analyses of these images hold the potential for uncovering mechanisms that govern functioning of the human brain, and understanding various neurological diseases and disorders. The potential significance of these studies notwithstanding, a growing concern relates to the protection of privacy and confidentiality of subjects who participate in these studies. In this paper, we present a de-anonymization attack rooted in the innate uniqueness of the structure and function of the human brain. We show that the attack reveals not only the identity of an individual, but also the efficacy with which they performing cognitive tasks. Our attack relies on novel matrix analyses techniques that are used to extract discriminating features in neuroimages. These features correspond to individual-specific signatures that can be matched across datasets for highly accurate identification. We present data preprocessing, signature extraction, and matching techniques that are computationally inexpensive, and can scale to large datasets. We characterize the efficacy of our de-anonymization attacks on publicly available databases. Finally, we discuss implications of the attack and challenges associated with defending against such attacks.

The problem of characterizing brain functions such as memory, perception, and processing of stimuli has received significant attention in neuroscience literature. These experiments rely on carefully calibrated, albeit complex inputs, to record brain response to signals. A major problem in analyzing brain response to common stimuli such as audio-visual input from videos (e.g., movies) or story narration through audio books, is that observed neuronal responses are due to combinations of ``pure'' factors, many of which may be latent. In this paper, we present a novel methodological framework for deconvolving the brain's response to mixed stimuli into its constituent responses to underlying pure factors. This framework, based on archetypal analysis, is applied to the analysis of imaging data from an adult cohort watching the BBC show, Sherlock. By focusing on visual stimulus, we show strong correlation between our observed deconvolved response and third-party textual video annotations -- demonstrating the significant power of our analyses techniques. Building on these results, we show that our techniques can be used to predict neuronal responses in new subjects (how other individuals react to Sherlock), as well as to new visual content (how individuals react to other videos with known annotations). This paper reports on the first study that relates video features with neuronal responses in a rigorous algorithmic and statistical framework based on deconvolution of observed mixed imaging signals using archetypal analysis.