publications

Edge embeddings have been widely used in graph signal processing, and learning tasks. However, if a graph is changing dynamically, with new edges appearing over time, these embeddings have to be recomputed. This work focuses on edge embeddings derived from the eigendecomposition of the adjacency of the line graph of a graph, and introduces a novel projection-based scheme to update spectral edge embeddings of dynamic graphs. The proposed method can handle graph updates in which either new edges or new vertices are added. The effectiveness of the proposed approach is demonstrated through numerical experiments on real-world graphs.

Graph convolutional filters (GCF) have played an important role in various applications to learn from graph signals by taking the graph structure into account. Most of the current work on GCFs focus on unsigned graphs. Recently, there has been a growing interest in signed graphs which account for both positive and negative interactions, capturing similarity and dissimilarity between entities. Thus, there is a need for development of GCFs for signed graphs to learn latent representations in signed graphs. The primary challenge of extending GCFs to signed graphs is that a node’s local neighborhood can be split into two based on whether balanced or unbalanced paths are used to define it. In this paper, we propose to design signed GCFs while taking this split in nodes’ local neighborhoods into account. Our GCF is modeled as a multivariate polynomial of two graph shift operators (GSO) defined separately for positive and negative edges, which allows us to perform convolution separetely on two local neighborhoods of a node. The utility of the proposed filter is illustrated by evaluating its performance on attributed signed graph clustering problem for both synthetic and real data.

Several graph data mining, signal processing, and machine learning downstream tasks rely on information related to the eigenvectors of the associated adjacency or Laplacian matrix. Classical eigendecomposition methods are powerful when the matrix remains static but cannot be applied to problems where the matrix entries are updated or the number of rows and columns increases frequently. Such scenarios occur routinely in graph analytics when the graph is changing dynamically and either edges and/or nodes are being added and removed. This paper puts forth a new algorithmic framework to update the eigenvectors associated with the leading eigenvalues of an initial adjacency or Laplacian matrix as the graph evolves dynamically. The proposed algorithm is based on Rayleigh-Ritz projections, in which the original eigenvalue problem is projected onto a restricted subspace which ideally encapsulates the invariant subspace associated with the sought eigenvectors. Following ideas from eigenvector perturbation analysis, we present a new methodology to build the projection subspace. The proposed framework features lower computational and memory complexity with respect to competitive alternatives while empirical results show strong qualitative performance, both in terms of eigenvector approximation and accuracy of downstream learning tasks of central node identification and node clustering.

Drug repurposing offers a scalable route to accelerate therapeutic discovery, yet existing approaches based on single-cell RNA sequencing (scRNA-seq) often overlook spatial tissue context, limiting their ability to capture microenvironment-dependent drug responses. Here we present STDrug, a spatially informed computational framework that integrates spatial transcriptomics, graph-based modeling, and multimodal learning to enable patient-specific therapeutic prioritization. STDrug identifies and aligns disease and control spatial domains using graph convolutional networks and coherent point drift, and prioritizes candidate drugs through an integrative scoring scheme combining tumor-reversible gene signatures, perturbation-based reversal scores, and knowledge-guided gene weighting within a machine learning framework. By modeling spatial domain interactions alongside predicted drug efficacy and toxicity, STDrug generates robust patient-level drug scores. Across hepatocellular carcinoma and prostate cancer datasets, STDrug outperforms existing single-cell and spatial transcriptomics–based drug repurposing methods, achieving signficantly improved predictive accuracy (AUCs=0.81-0.82) across patients. Validation using large-scale electronic health records and in vitro assays further supports the translational relevance of top-ranked candidates. Taking together, STDrug establishes a generalizable framework for incorporating spatial omics into therapeutic discovery, advancing spatially informed and personalized drug repurposing.

Graph anomaly detection is an important research problem that aims to identify structures in a graph that deviate significantly from the rest of the graph. Existing work proposed various approaches to detect anomalous nodes, edges or sub-graphs using tools from machine learning and statistical signal processing. Nevertheless, the majority of existing methods are limited to detecting only a single type of anomalous object, that is, they consider detection of node, edge, or subgraph anomalies as separate tasks. Real world graphs can simultaneously include multiple types of anomalous objects, motivating the development of new algorithms that can perform joint detection. This work proposes an algorithm that aims to simultaneously identify node and edge anomalies. In particular, we consider graphs whose topology includes anomalous edges and whose nodal attributes are contaminated with anomalous labels. The proposed approach uses an autoencoder to find node embeddings that are informative for identification of both types of anomalies. A sequential ensemble learning process is also put forth to train the autoencoder to reduce the effect of anomalies on training. Preliminary results showcase the potential of this novel approach.

Over the past two decades, tools from network science have been leveraged to characterize the organization of both structural and functional brain networks. One such tool is hub node identification. Hubs are nodes within a network that link distinct brain units corresponding to specialized functional processes. Conventional methods for identifying hubs utilize different types of centrality measures and participation coefficient to profile various aspects of nodal importance. These methods solely rely on the functional connectivity networks constructed from functional magnetic resonance imaging (fMRI), ignoring the structure-function coupling in the brain. In this paper, we introduce a graph signal processing (GSP) based framework that utilizes both the structural connectivity and the functional activation to identify hubs. The proposed framework models functional activity as graph signals on the structural connectivity. Hub nodes are then detected based on the premise that they are sparse, have higher level of activity compared to their neighbors, and the non-hub nodes’ activity is the output of a low-pass graph filter. Based on these assumptions, an optimization framework, GraFHub, is formulated to learn the coefficients of the optimal graph filter and detect the hub nodes. The proposed framework is evaluated on both simulated data and resting state fMRI (rs-fMRI) data from Human Connectome Project (HCP).

Real-world data is often represented through the relationships between data samples, forming a graph structure. In many applications, it is necessary to learn this graph structure from the observed data. Current graph learning research has primarily focused on unsigned graphs, which consist only of positive edges. However, many biological and social systems are better described by signed graphs that account for both positive and negative interactions, capturing similarity and dissimilarity between samples. In this paper, we develop a method for learning signed graphs from a set of smooth signed graph signals. Specifically, we employ the net Laplacian as a graph shift operator (GSO) to define smooth signed graph signals as the outputs of a low-pass signed graph filter defined by the net Laplacian. The signed graph is then learned by formulating a non-convex optimization problem where the total variation of the observed signals is minimized with respect to the net Laplacian. The proposed problem is solved using alternating direction method of multipliers (ADMM) and a fast algorithm reducing the per-ADMM iteration complexity from quadratic to linear in the number of nodes is introduced. Furthermore, theoretical proofs of convergence for the algorithm and a bound on the estimation error of the learned net Laplacian as a function of sample size, number of nodes, and graph topology are provided. Finally, the proposed method is evaluated on simulated data and gene regulatory network inference problem and compared to existing signed graph learning methods.

Crowdsourcing is becoming increasingly important for contemporary applications in machine learning and artificial intelligence. However, crowdsourcing systems may be susceptible to adversarial attacks where a subset of annotators deliberately provide erroneous responses. This paper introduces a novel algorithm for identifying adversarial attacks in crowdsourcing systems by recasting the problem as dense subgraph detection in bipartite graphs. In particular, we represent crowdsourced data as a weighted bipartite graph between workers and data points which are connected with edges whose weights are computed from annotators’ responses. The constructed bipartite graph is then analyzed with a sequential peeling algorithm to detect the dense subgraph that includes adversarial attacks. Compared to previous methods where only adversaries are detected, our proposed method can simultaneously identify adversarial annotators as well as affected data points. Preliminary results on real datasets showcase the potential of this novel approach.

Graph topology inference is a significant task in many application domains. Existing approaches are mostly limited to learning a single graph assuming that the observed data is homogeneous. This is problematic because many modern datasets are heterogeneous and involve multiple related graphs, i.e., multiview graphs. Prior work in multiview graph learning ensures the similarity of learned view graphs through pairwise regularization, which has several limitations. First, most of the existing work focuses on the Gaussian Graphical Models (GGM) which learns precision matrices rather than the actual graph structures. Second, these methods do not infer the consensus structure across views, which may be useful in certain applications for summarizing the group level connectivity patterns. Finally, the number of pairwise constraints increases quadratically with the number of views. To address these issues, we propose a consensus graph-based multiview graph model, where each view is assumed to be a perturbed version of an underlying consensus graph. The proposed framework assumes that the observed graph data is smooth over the multiview graph and learns the graph Laplacians. A generalized optimization framework to jointly learn the views and the consensus graph is proposed, where different regularization functions can be incorporated into the formulation based on the structure of the underlying consensus graph and the perturbation model. Experiments with simulated data show that the proposed method has better performance than existing GGM-based methods and requires less run time than pairwise regularization-based methods. The proposed framework is also employed to infer the functional brain connectivity networks of multiple subjects from their electroencephalogram (EEG) recordings, revealing both the consensus structure and the individual variation across subjects.

Graphs and graph structured data are ubiquitous in many applications as they readily represent datasets that lie in irregular, yet structured, domains. Due to their popularity, a plethora of methods have been developed to learn from graphstructured data, which have been shown to be effective in many real-world applications including biology, finance, and social sciences, among others. However, these methods generally assume that the observed graph is free of corruption. This assumption does not hold in cases where the graph includes structural contamination, such as anomalous edges, which can degrade learning performance. This paper presents a method to identify anomalous edges that can be employed prior to learning methods to mitigate their effects. The proposed method employs link prediction (LP) to assign likelihood scores to the observed edges. As LP is not anomaly aware, we combine LP with ideas from sampling and consensus algorithms. LP is applied to subgraphs which tend to have fewer anomalies. Edge anomaly scores are then obtained by judiciously combining LP prediction results across subgraphs. Preliminary results indicate the effectiveness of the proposed method.

Drug repurposing is a promising strategy to find new usage for existing drugs outside of their original purpose. We have recently developed a computational framework ASGARD that employs single cell RNA-sequencing (scRNA-seq) to repurpose drugs. However, scRNA-seq lacks the spatial information of the tissue, an important determinant of the heterogeneity within the tissue micro-environment. In this paper, we propose Spatial Transcriptomics to Aid Drug-reposition Recommendation (STADS) framework, a new drug repurposing computational framework that employs Spatial Transcriptomics (ST) datasets with gene expression in situ. STADS reduces the ST gene expression by spatially-aware embedding, integrates multiple healthy and diseased samples, identifies the matched spatial domains between disease and controls, then repurposes drugs by a novel drug score that considers differentially expressed genes between disease and control samples among all matched spatial domains. We apply STADS to a ST dataset of patients with Hepatocellular Carcinoma and demonstrate its superior performance to ASGARD. STADS is a promising personalized drug repurposing prediction method using ST data.

Many real-world data are represented through the relations between data samples, i.e., a graph structure. Although many datasets come with a pre-existing graph, there is still a large number of applications where the graph structure is not readily available. An essential task for such cases is graph learning (GL), which infers the graph structure from a set of graph signals. Existing GL techniques mostly focus on learning a single graph structure; however, samples are usually connected in multiple different ways. Furthermore, existing works can only handle unsigned graphs, while contemporary tasks require inference of signed graphs, which are better at representing similarity and dissimilarity of samples. In this paper, we propose a framework (mvSGL) for joint estimation of multiple related signed graphs. mvSGL optimizes the total variation of graph signals with respect to graphs while ensuring that the graphs are similar to each other through a consensus graph. mvSGL is employed in the inference of multiple gene regulatory networks (GRN) from single cell datasets that include multiple cell types. Performance evaluation using simulated and real datasets demonstrates the effectiveness of mvSGL in the inference of multiple related GRNs.

An important problem in graph signal processing (GSP) is to infer the topology of an unknown graph from a set of observations on the nodes of the graph, i.e. graph signals. Recently, graph learning (GL) approaches have been extended to learn dynamic graphs from temporal graph signals. However, existing work primarily focuses on unsigned graphs and cannot learn signed graphs, which are important data structures that can represent the similarity and dissimilarity of the nodes. In this paper, we propose a dynamic signed GL (dynSGL) method based on the assumptions that (i) at each time point signals are smooth with respect to the signed graph, i.e. signal values at two nodes connected with a positive (negative) edge are similar (dissimilar) and (ii) evolution of the graph structures is smooth across time. The performance of dynSGL is evaluated on simulated data and shown to have higher accuracy compared to static signed and dynamic unsigned GL techniques. Application of the proposed method to a financial dataset gives important insights to the time-varying changes to the interactions between stocks.

Functional connectivity networks of the human brain are commonly studied using tools from complex network theory. Existing methods focus on functional connectivity within a single frequency band. However, it is well-known that higher order brain functions rely on the integration of information across oscillations at different frequencies. Therefore, there is a need to study these cross-frequency interactions. In this paper, we use multilayer networks to model functional connectivity across multiple frequencies, where each layer corresponds to a different frequency band. We then introduce the multilayer modularity metric to develop a multilayer community detection algorithm. The proposed approach is applied to electroencephalogram (EEG) data collected during a study of error monitoring in the human brain. The differences between the community structures within and across different frequency bands for two response types, i.e. error and correct, are studied. The results indicate that following an error response, the brain organizes itself to form communities across frequencies, in particular between theta and gamma bands while a similar cross-frequency community formation is not observed following the correct response.

Background: Characterizing the topology of gene regulatory networks (GRNs) is a fundamental problem in systems biology. The advent of single cell technologies has made it possible to construct GRNs at finer resolutions than bulk and microarray datasets. However, cellular heterogeneity and sparsity of the single cell datasets render void the application of regular Gaussian assumptions for constructing GRNs. Additionally, most GRN reconstruction approaches estimate a single network for the entire data. This could cause potential loss of information when single cell datasets are generated from multiple treatment conditions/disease states. Results: To better characterize single cell GRNs under different but related conditions, we propose the joint estimation of multiple networks using multiple signed graph learning (scMSGL). The proposed method is based on recently developed graph signal processing (GSP) based graph learning, where GRNs and gene expressions are modeled as signed graphs and graph signals, respectively. scMSGL learns multiple GRNs by optimizing the total variation of gene expressions with respect to GRNs while ensuring that the learned GRNs are similar to each other through regularization with respect to a learned signed consensus graph. We further kernelize scMSGL with the kernel selected to suit the structure of single cell data. Conclusions: scMSGL is shown to have superior performance over existing state of the art methods in GRN recovery on simulated datasets. Furthermore, scMSGL successfully identifies well-established regulators in a mouse embryonic stem cell differentiation study and a cancer clinical study of medulloblastoma.

Graph learning (GL) aims to infer the topology of an unknown graph from a set of observations on its nodes, i.e., graph signals. While most of the existing GL approaches focus on homogeneous datasets, in many real world applications, data is heterogeneous, where graph signals are clustered and each cluster is associated with a different graph. In this paper, we address the problem of learning multiple graphs from heterogeneous data by formulating an optimization problem for joint graph signal clustering and graph topology inference. In particular, our approach extends spectral clustering by partitioning the graph signals not only based on their pairwise similarities but also their smoothness with respect to the graphs associated with the clusters. The proposed method also learns the representative graph for each cluster using the smoothness of the graph signals with respect to the graph topology. The resulting optimization problem is solved with an efficient block-coordinate descent algorithm and results on simulated and real data indicate the effectiveness of the proposed method.

In many modern data science problems, data are represented by a graph (network), e.g., social, biological, and communication networks. Over the past decade, numerous signal processing and machine learning (ML) algorithms have been introduced for analyzing graph structured data. With the growth of interest in graphs and graph-based learning tasks in a variety of applications, there is a need to explore explainability in graph data science. In this article, we aim to approach the issue of explainable graph data science, focusing on one of the most fundamental learning tasks, community detection, as it is usually the first step in extracting information from graphs. A community is a dense subnetwork within a larger network that corresponds to a specific function. Despite the success of different community detection methods on synthetic networks with strong modular structure, much remains unknown about the quality and significance of the outputs of these algorithms when applied to real-world networks with unknown modular structure. Inspired by recent advances in explainable artificial intelligence (AI) and ML, in this article, we present methods and metrics from network science to quantify three different aspects of explainability, i.e., interpretability, replicability, and reproducibility, in the context of community detection.

Motivation: Elucidating the topology of gene regulatory networks (GRNs) from large single-cell RNA sequencing datasets, while effectively capturing its inherent cell-cycle heterogeneity and dropouts, is currently one of the most pressing problems in computational systems biology. Recently, graph learning (GL) approaches based on graph signal processing have been developed to infer graph topology from signals defined on graphs. However, existing GL methods are not suitable for learning signed graphs, a characteristic feature of GRNs, which are capable of accounting for both activating and inhibitory relationships in the gene network. They are also incapable of handling high proportion of zero values present in the single cell datasets.
Results: To this end, we propose a novel signed GL approach, scSGL, that learns GRNs based on the assumption of smoothness and non-smoothness of gene expressions over activating and inhibitory edges, respectively. scSGL is then extended with kernels to account for non-linearity of co-expression and for effective handling of highly occurring zero values. The proposed approach is formulated as a non-convex optimization problem and solved using an efficient ADMM framework. Performance assessment using simulated datasets demonstrates the superior performance of kernelized scSGL over existing state of the art methods in GRN recovery. The performance of scSGL is further investigated using human and mouse embryonic datasets.

Learning the graph structure underlying observed graph signals is important in many graph signal processing (GSP) applications. This problem has been extensively addressed as graph Laplacian learning with the constraint that the graph signals have smooth variations on the resulting topology. The current approaches focus primarily on the case that the signals are observed across all nodes and possibly corrupted by additive Gaussian noise. In this paper, we propose a general framework for graph learning where the graph signal is partially observed and corrupted by sparse outliers in addition to Gaussian noise. We present a general optimization framework that addresses this problem and show how this formulation encapsulates a variety of problems in GSP including Laplacian learning and graph regularized low-rank matrix completion. The proposed optimization is solved with ADMM and the resulting algorithms are evaluated on both simulated graphs with different topology and real world graph-based data clustering.

Community detection aims to identify densely connected groups of nodes in complex networks. Although a variety of methods have been proposed for community detection, the relationship between them is not well understood. Recently, researchers have shown the equivalence between modularity optimization and likelihood maximization in stochastic block models (SBMs) for static networks. Showing this equivalence is important for both understanding the different community detection methods and selecting the hyperparameters in the different algorithms in a more principled way. In this paper, we extend this equivalence for dynamic community detection algorithms. In particular, we show the equivalence of evolutionary spectral clustering to a variant of dynamic stochastic blockmodel. For this purpose, we first introduce a novel dynamic SBM where the evolution of communities over time is modeled with pairwise Markov random fields. We then show that the log-posterior of the proposed model is equivalent to the quality function of evolutionary spectral clustering. This equivalence is used to determine the forgetting factor in evolutionary spectral clustering and to develop two new algorithms for dynamic community detection. Compared to original evolutionary spectral clustering, the forgetting factor is time-dependent and derived directly from the parameters of the proposed dynamic SBM. The proposed algorithms are shown to be superior to state-of-the-art dynamic community detection methods for both simulated and real-world dynamic networks.

Networks are useful representations of many systems with interacting entities, such as social, biological and physical systems. Characterizing the meso-scale organization, i.e. the community structure, is an important problem in network science. Community detection aims to partition the network into sets of nodes that are densely connected internally but sparsely connected to other dense sets of nodes. Current work on community detection mostly focuses on static networks. However, many real world networks are dynamic, i.e. their structure and properties change with time, requiring methods for dynamic community detection. In this paper, we propose a new stochastic block model (SBM) for modeling the evolution of community membership. Unlike existing SBMs, the proposed model allows each community to evolve at a different rate. This new model is used to derive a maximum a posteriori estimator for community detection, which can be written as a constrained spectral clustering problem. In particular, the transition probabilities for each community modify the graph adjacency matrix at each time point. This formulation provides a relationship between statistical network inference and spectral clustering for dynamic networks. The proposed method is evaluated on both simulated and real dynamic networks.

Network representations are useful for describing the structure of a variety of complex systems. One of the important problems in the analysis of such complex systems is inferring the network structure from the available data. Community detection has been a common way to infer network topology. In recent years, network representation has been extended to describe multi-relational or multiview data sets resulting in multilayer networks. These types of networks arise in different applications including social, ecological, biological and brain networks. Even though different graph theoretic metrics have been extended to study multilayer networks, approaches for network topology inference, e.g. community detection, have been limited. In this paper, we introduce a multilayer community detection method based on a modified graph cut definition and propose a corresponding algorithm. The proposed multilayer community detection method is evaluated on both simulated network models and a multilayer brain network, where the layers correspond to different frequency bands.

Global brain network parameters suffer from low classification performance and fail to provide an insight into the neurodegenerative diseases. Besides, the variability in connectivity definitions poses a challenge. We propose to represent multi-modal brain networks over a population with a single 4D brain tensor (B) and factorize B to get a lower dimensional representation per case and per modality. We used 7 known functional networks as the canonical network space to get a 7D representation. In a preliminary study over a group of 20 cases, we assessed this representation for classification. We used 6 different connectivity definitions (modalities). Linear discriminant analysis results in 90-95% accuracy in binary classification. The assessment of the canonical coordinates reveals Salience subnetwork to be the most powerful in classification consistently over all connectivity definitions. The method can be extended to include functional networks and further be used to search for discriminating subnetworks.