Seminar Details
2019-05-07 (14:00) : Spectral methods for certain inverse problems on graphs
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Mihai Cucuringu (University of Oxford)
Abstract :
We study problems that share an important common feature: they can all be solved by exploiting the spectrum of their corresponding graph Laplacian. We first consider the classic problem of establishing a statistical ranking of a set of items given a set of inconsistent and incomplete pairwise comparisons between such items. Instantiations of this problem occur in numerous applications in data analysis (e.g., ranking teams in sports data), computer vision, and machine learning. We formulate the above problem of ranking with incomplete noisy information as an instance of the group synchronization problem over the group SO(2) of planar rotations, whose least squares solution can be approximated by either a spectral or a semidefinite programming relaxation. We also present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The proposed algorithm works in nearly-linear time, and consistently outperforms existing spectral approaches both in speed and quality. Furthermore, we propose an algorithm for clustering signed networks, where the edge weights between the nodes of the graph may take either positive or negative edges, and analyze it under a signed stochastic block model. Time permitting, we discuss recent work on clustering directed graphs, and applications of ranking to extracting leaders and laggers in multivariate time series data.