Community detection and graph learning are two important problems in graph analysis. The former problem deals with topological analysis of graphs to identify their mesoscale organization; while graph learning aims to infer the interactions between nodes of a graph from data when the graph topology is not known a priori. Existing community detection and graph learning methods are mostly limited to single-layer graphs, where nodes are assumed to be connected with a single static edge. However, this assumption ignores the fact that many real-world relational data have multiple dimensions, which can be better represented with multilayer graphs. In this thesis, we propose various community detection and graph learning methods for different types of multilayer graphs.℗ In Chapter 2, we tackle the community detection problem in dynamic networks. Specifically, we focus on evolutionary spectral clustering, which extends spectral clustering to dynamic networks to learn a community structure that changes smoothly over time. 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. The proposed algorithms are applied to both simulated and real-world dynamic networks and their performances are compared to state-of-the-art dynamic community detection methods.Chapter 3 introduces a multilayer community detection method, which is especially tailored to handle multilayer brain networks constructed from electroencephalogram(EEG) data. In particular, we first construct functional multilayer networks from EEG data, where layers correspond to different frequency bands and interlayer edges are allowed between all brain regions. Next, a new multilayer modularity metric is defined based on a multilayer null model that preserves the layer-wise node degrees while randomizing the remaining characteristics of the network. The proposed modularity is parameterized with resolution parameter to handle the resolution limit of modularity, and interlayer scale parameter to control the importance of interlayer edges in community formation. Third, a group community detection method is proposed to find the common community structure for a set of subjects. The proposed multilayer community detection method is employed to identify the group level differences between the two response types during Flanker task, i.e. error and correct.In Chapter 4, we present an algorithm to learn signed graphs, which we represent as a two-layer multiplex network where one layer corresponds to positive edges while the other to negative edges. The algorithm is based on graph learning approaches developed using graph signal processing. Existing graph learning methods rely on smoothness of graph signals over the graph; however, they are only capable of learning unsigned graphs. To this end, we propose a signed graph learning approach, that learns signed graphs based on the assumption of smoothness and non-smoothness of graph signals over positive and negative edges, respectively. The proposed method is further extended using kernels to take the nonlinear relations between nodes into account. From GSP perspective, this extension corresponds to assuming smoothness/non-smoothness of graph signals in a higher dimensional space defined by the kernel. The proposed approach is applied to the problem of gene regulatory network inference from single cell gene expression data. Experiments on simulated and real single cell datasets show that the method compares favorably with other single cell gene regulatory network reconstruction algorithms.Chapter 5 addresses the problem of how to learn multiple signed graphs simultaneously. Existing GSP based GL approaches for this problem are limited to unsigned graph topologies. Therefore, we extend the algorithm developed in Chapter 4 to learn multiple signed graphs. In particular, given multiple datasets each of which includes graph signals associated with a signed graph, we assume smoothness and non-smoothness of graph signals as in Chapter 4. Furthermore, we assume that the signed graphs are similar to each other, which is ensured by regularizing the learned signed graphs through a learned signed consensus graph. The proposed method is employed for the joint inference of multiple gene regulatory networks from single cell gene expression data. Experiments on simulated and real single cell datasets show that the method performs better than methods that can learn a single graph at a time and previous joint gene regulatory network reconstruction algorithms.In Chapter 6, we tackle the problem of learning multiple unsigned graphs from a heterogeneous dataset, which requires clustering graph signals while learning a graph for each cluster. Namely, we present an optimization problem for joint graph signal clustering and graph topology inference. The approach extends graph cut based 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. Results on simulated and real data indicate the effectiveness of the proposed method.
Read
