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.

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.

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.

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.

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.

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. AVAILABILITY AND IMPLEMENTATION: The scSGL code and analysis scripts are available on https://github.com/Single-Cell-Graph-Learning/scSGL. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.