Joint Embedding of Graphs

Applying Joint Graph Embedding to Study Alzheimer's Neurodegeneration Patterns in Volumetric Data

Neurodegeneration measured through volumetry in MRI is recognized as a potential Alzheimer's Disease (AD) biomarker, but its utility is limited by lack of specificity. Quantifying spatial patterns of neurodegeneration on a whole brain scale rather than locally may help address this. In this work, we turn to network based analyses and extend a graph embedding algorithm to study morphometric connectivity from volume-change correlations measured with structural MRI on the timescale of years. We model our data with the multiple random eigengraphs framework, as well as modify and implement a multigraph embedding algorithm proposed earlier to estimate a low dimensional embedding of the networks. Our version of the algorithm guarantees meaningful finite-sample results and estimates maximum likelihood edge probabilities from population-specific network modes and subject-specific loadings. Furthermore, we propose and implement a novel statistical testing procedure to analyze group differences after accounting for confounders and locate significant structures during AD neurodegeneration. Family-wise error rate is controlled at 5% using permutation testing on the maximum statistic. We show that results from our analysis reveal networks dominated by known structures associated to AD neurodegeneration, indicating the framework has promise for studying AD. Furthermore, we find network-structure tuples that are not found with traditional methods in the field.

A Novel Temporal Network-Embedding Algorithm for Link Prediction in Dynamic Networks

Understanding the evolutionary patterns of real-world complex systems such as human interactions, biological interactions, transport networks, and computer networks is important for our daily lives. Predicting future links among the nodes in these dynamic networks has many practical implications. This research aims to enhance our understanding of the evolution of networks by formulating and solving the link-prediction problem for temporal networks using graph representation learning as an advanced machine learning approach. Learning useful representations of nodes in these networks provides greater predictive power with less computational complexity and facilitates the use of machine learning methods. Considering that existing models fail to consider the temporal dimensions of the networks, this research proposes a novel temporal network-embedding algorithm for graph representation learning. This algorithm generates low-dimensional features from large, high-dimensional networks to predict temporal patterns in dynamic networks. The proposed algorithm includes a new dynamic node-embedding algorithm that exploits the evolving nature of the networks by considering a simple three-layer graph neural network at each time step and extracting node orientation by using Given's angle method. Our proposed temporal network-embedding algorithm, TempNodeEmb, is validated by comparing it to seven state-of-the-art benchmark network-embedding models. These models are applied to eight dynamic protein-protein interaction networks and three other real-world networks, including dynamic email networks, online college text message networks, and human real contact datasets. To improve our model, we have considered time encoding and proposed another extension to our model, TempNodeEmb++. The results show that our proposed models outperform the state-of-the-art models in most cases based on two evaluation metrics.

Neural excursions from manifold structure explain patterns of learning during human sensorimotor adaptation

Humans vary greatly in their motor learning abilities, yet little is known about the neural mechanisms that underlie this variability. Recent neuroimaging and electrophysiological studies demonstrate that large-scale neural dynamics inhabit a low-dimensional subspace or manifold, and that learning is constrained by this intrinsic manifold architecture. Here, we asked, using functional MRI, whether subject-level differences in neural excursion from manifold structure can explain differences in learning across participants. We had subjects perform a sensorimotor adaptation task in the MRI scanner on 2 consecutive days, allowing us to assess their learning performance across days, as well as continuously measure brain activity. We find that the overall neural excursion from manifold activity in both cognitive and sensorimotor brain networks is associated with differences in subjects' patterns of learning and relearning across days. These findings suggest that off-manifold activity provides an index of the relative engagement of different neural systems during learning, and that subject differences in patterns of learning and relearning are related to reconfiguration processes occurring in cognitive and sensorimotor networks.

Netpro2vec: A Graph Embedding Framework for Biomedical Applications

The ever-increasing importance of structured data in different applications, especially in the biomedical field, has driven the need for reducing its complexity through projections into a more manageable space. The latest methods for learning features on graphs focus mainly on the neighborhood of nodes and edges. Methods capable of providing a representation that looks beyond the single node neighborhood are kernel graphs. However, they produce handcrafted features unaccustomed with a generalized model. To reduce this gap, in this work we propose a neural embedding framework, based on probability distribution representations of graphs, named Netpro2vec. The goal is to look at basic node descriptions other than the degree, such as those induced by the Transition Matrix and Node Distance Distribution. Netpro2vec provides embeddings completely independent from the task and nature of the data. The framework is evaluated on synthetic and various real biomedical network datasets through a comprehensive experimental classification phase and is compared to well-known competitors.

Clustering of heterogeneous populations of networks

Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we describe a Bayesian analysis framework for such data that allows for the fact that network measurements may be reflective of multiple possible structures. We define a finite mixture model of the measurement process and derive a Gibbs sampling procedure that samples exactly from the full posterior distribution of model parameters. The end result is a clustering of the measured networks into groups with similar structure. We demonstrate the method on both real and synthetic network populations.

Latent space models for multiplex networks with shared structure

Latent space models are frequently used for modelling single-layer networks and include many popular special cases, such as the stochastic block model and the random dot product graph. However, they are not well-developed for more complex network structures, which are becoming increasingly common in practice. Here we propose a new latent space model for multiplex networks: multiple, heterogeneous networks observed on a shared node set. Multiplex networks can represent a network sample with shared node labels, a network evolving over time, or a network with multiple types of edges. The key feature of our model is that it learns from data how much of the network structure is shared between layers and pools information across layers as appropriate. We establish identifiability, develop a fitting procedure using convex optimization in combination with a nuclear norm penalty, and prove a guarantee of recovery for the latent positions as long as there is sufficient separation between the shared and the individual latent subspaces. We compare the model to competing methods in the literature on simulated networks and on a multiplex network describing the worldwide trade of agricultural products.

Link prediction in dynamic networks using random dot product graphs

The problem of predicting links in large networks is an important task in a variety of practical applications, including social sciences, biology and computer security. In this paper, statistical techniques for link prediction based on the popular random dot product graph model are carefully presented, analysed and extended to dynamic settings. Motivated by a practical application in cyber-security, this paper demonstrates that random dot product graphs not only represent a powerful tool for inferring differences between multiple networks, but are also efficient for prediction purposes and for understanding the temporal evolution of the network. The probabilities of links are obtained by fusing information at two stages: spectral methods provide estimates of latent positions for each node, and time series models are used to capture temporal dynamics. In this way, traditional link prediction methods, usually based on decompositions of the entire network adjacency matrix, are extended using temporal information. The methods presented in this article are applied to a number of simulated and real-world graphs, showing promising results.

Optimal Bayesian estimation for random dot product graphs

We propose and prove the optimality of a Bayesian approach for estimating the latent positions in random dot product graphs, which we call posterior spectral embedding. Unlike classical spectral-based adjacency, or Laplacian spectral embedding, posterior spectral embedding is a fully likelihood-based graph estimation method that takes advantage of the Bernoulli likelihood information of the observed adjacency matrix. We develop a minimax lower bound for estimating the latent positions, and show that posterior spectral embedding achieves this lower bound in the following two senses: it both results in a minimax-optimal posterior contraction rate and yields a point estimator achieving the minimax risk asymptotically. The convergence results are subsequently applied to clustering in stochastic block models with positive semidefinite block probability matrices, strengthening an existing result concerning the number of misclustered vertices. We also study a spectral-based Gaussian spectral embedding as a natural Bayesian analogue of adjacency spectral embedding, but the resulting posterior contraction rate is suboptimal by an extra logarithmic factor. The practical performance of the proposed methodology is illustrated through extensive synthetic examples and the analysis of Wikipedia graph data.

Joint embedding: A scalable alignment to compare individuals in a connectivity space

A common coordinate space enabling comparison across individuals is vital to understanding human brain organization and individual differences. By leveraging dimensionality reduction algorithms, high-dimensional fMRI data can be represented in a low-dimensional space to characterize individual features. Such a representative space encodes the functional architecture of individuals and enables the observation of functional changes across time. However, determining comparable functional features across individuals in resting-state fMRI in a way that simultaneously preserves individual-specific connectivity structure can be challenging. In this work we propose scalable joint embedding to simultaneously embed multiple individual brain connectomes within a common space that allows individual representations across datasets to be aligned. Using Human Connectome Project data, we evaluated the joint embedding approach by comparing it to the previously established orthonormal alignment model. Alignment using joint embedding substantially increased the similarity of functional representations across individuals while simultaneously capturing their distinct profiles, allowing individuals to be more discriminable from each other. Additionally, we demonstrated that the common space established using resting-state fMRI provides a better overlap of task-activation across participants. Finally, in a more challenging scenario - alignment across a lifespan cohort aged from 6 to 85 - joint embedding provided a better prediction of age (r2 = 0.65) than the prior alignment model. It facilitated the characterization of functional trajectories across lifespan. Overall, these analyses establish that joint embedding can simultaneously capture individual neural representations in a common connectivity space aligning functional data across participants and populations and preserve individual specificity.

Query-Specific Deep Embedding of Content-Rich Network

In this paper, we propose to embed a content-rich network for the purpose of similarity searching for a query node. In this network, besides the information of the nodes and edges, we also have the content of each node. We use the convolutional neural network (CNN) to represent the content of each node and then use the graph convolutional network (GCN) to further represent the node by merging the representations of its neighboring nodes. The GCN output is further fed to a deep encoder-decoder model to convert each node to a Gaussian distribution and then convert back to its node identity. The dissimilarity between the two nodes is measured by the Wasserstein distance between their Gaussian distributions. We define the nodes of the network to be positives if they are relevant to the query node and negative if they are irrelevant. The labeling of the positives/negatives is based on an upper bound and a lower bound of the Wasserstein distances between the candidate nodes and the query nodes. We learn the parameters of CNN, GCN, encoder-decoder model, Gaussian distributions, and the upper bound and lower bounds jointly. The learning problem is modeled as a minimization problem to minimize the losses of node identification, network structure preservation, positive/negative query-specific relevance-guild distance, and model complexity. An iterative algorithm is developed to solve the minimization problem. We conducted experiments over benchmark networks, especially innovation networks, to verify the effectiveness of the proposed method and showed its advantage over the state-of-the-art methods.