Efficient Spectral Link Prediction on Graphs Approximation of Graph Algorithms via Coarse Graining
Spectral graph theory studies the properties of graphs in relation to their eigenpairs, that is, the eigenvalues and eigenvectors of associated graph matrices. Successful applications of spectral graph theory include the ranking web search results and link prediction in graphs. The latter is used to predict the evolution of graphs and to discover previously unobserved edges. However, the computation of eigenpairs is computationally very demanding. The eigenvalue eigenvector decomposition of graph matrices has cubic time complexity. As graphs or networks become large, this makes the computation of a full eigendecomposition infeasible. This complexity problem is addressed on one of the most accurate state of the art spectral link prediction methods. The method requires several eigenvalue eigenvector decompositions which limits its applicability to small graphs only. Previous work on similar complexity bottlenecks has approached the problem by computing only a subset of the eigenpairs in order to obtain an approximation of the original method at lower computational cost. This thesis takes the same approach but instead of modifying the original link prediction algorithm, it uses the eigenpair subset to approximate the graph without significant changes to the link prediction algorithm. The graph is approximated by spectral coarse graining, a method that shrinks graphs while preserving their dominant spectral properties. This approach is motivated by the hypothesis that results computed on a coarse grained graph approximate the original link prediction results. The main contribution presented in this dissertation is a new, coarse grained spectral link prediction approach. In a first part, the state of the art link prediction method is combined with spectral coarse graining and the computational cost, complexity and link prediction accuracy is evaluated. Theoretical analysis and experiments show that the coarse grained approach produces accurate approximations of the original method with a significantly reduced time complexity. Thereafter, the spectral coarse graining method is extended to make the complexity reduction more controllable and to avoid the computation of the eigenvalue eigenvector decomposition. This dramatically increases the efficiency of the proposed approach and allows to compute more accurate graph approximations. As a result, the link prediction accuracy can be significantly improved while maintaining the reduced time complexity of the coarse grained approach. Furthermore, the proposed approach produces a valid graph of the same structure and type as the original graph. In principle, it can be used with many other graph applications without the need for major adaptations. Therefore, the approach is a step towards a more general approximation framework for spectral graph algorithms.