Further Information
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 a classic problem in data analysis and machine learning, of establishing a statistical ranking of a set of items given a set of inconsistent and incomplete pairwise comparisons. 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, and consider an application to detecting leaders and laggers in financial multivariate time series data. An instance of the group synchronization problem over Z_2 with anchor information is broadly applicable to settings where one has available a sparse signal such as positive or negative news sentiment for a subset of nodes, and would like to understand how the available measurements propagate to the remaining nodes of the network. We also present a simple spectral approach to the well-studied constrained clustering problem, which captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. This line of work extends to the setting of clustering signed networks and correlation clustering, where the edge weights between the nodes of the graph may take either positive or negative values, for which we provide theoretical guarantees in the setting of a signed stochastic block model and numerical experiments for financial correlation matrices. Finally, we discuss a spectral clustering algorithm for directed graphs based on a complex-valued representation of the adjacency matrix, motivated by the application of extracting cluster-based lead-lag relationships in time series data.