Mihai Cucuringu, UCLA

Title: Spectral methods for clustering signed/directed networks and heterogeneous group synchronization

Abstract: Graph clustering problems typically arise in settings where there exists a discrepancy in the edge density within different parts of the graph. In this work, we consider problem instances where the underlying cluster structure arises as a consequence of a signal present on the edges or nodes, and is not driven by edge density. We first consider the problem of clustering in two families of networks, signed (with edge weights taking positive or negative values) and directed, both solvable by exploiting the spectrum of certain graph Laplacian matrices. We consider a generalized eigenvalue problem involving graph Laplacians, and provide performance guarantees under the setting of a Signed Stochastic Block Model, along with regularized versions to handle very sparse graphs (below the connectivity threshold), a regime where standard spectral methods are known to underperform. We also propose a spectral clustering algorithm for directed graphs based on a complex-valued representation of the adjacency matrix, which is able to capture the underlying cluster structures, for which the information encoded in the direction of the edges is crucial. We evaluate the proposed algorithm in terms of a cut flow imbalance-based objective function, which, for a pair of given clusters, it captures the propensity of the edges to flow in a given direction. We analyze its theoretical performance on a Directed Stochastic Block Model. Finally, we discuss an extension of the classical angular synchronization problem that aims to recover unknown angles from a collection of noisy pairwise difference measurements. We consider a generalization to the heterogeneous setting where there exist k unknown groups of angles, and the measurement graph has an unknown edge-disjoint decomposition, where the subgraphs of noisy edge measurements correspond to each group. We propose a probabilistic generative model for this problem, along with a spectral algorithm that comes with theoretical guarantees in terms of robustness against sampling sparsity and noise. Time permitting, we discuss extensions to the temporal setting, and approaches based on graph neural networks.