We consider a generalization of graph Laplacian which acts on the space of functions which assign to each vertex a point in $d$-dimensional space. The eigenvalues of such connection Laplacian are useful for examining vibrational spectra of molecules as well as vector diffusion maps for analyzing high dimensional data. We will discuss algebraic, probabilistic and algorithmic methods in the study of the connection spectra. For example, if the graph is highly symmetric and the connection Laplacian is invariant under the symmetry of the graph, then its eigenvalues can be deduced by using irreducible representations. In addition, by using matrix concentration inequalities, the eigenvalues of random connection Laplacians can be approximated by the eigenvalues of the expected matrices under appropriate conditions. Furthermore, graph sparsification algorithms can be generalized to approximate and extract the global structure of information networks arising in signal and data processing.