Header

UZH-Logo

Maintenance Infos

Efficient Spectral Link Prediction on Graphs -- Approximation of Graph Algorithms via Coarse-Graining


Spicar, Daniel. Efficient Spectral Link Prediction on Graphs -- Approximation of Graph Algorithms via Coarse-Graining. 2019, University of Zurich, Faculty of Economics.

Abstract

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.

Abstract

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.

Statistics

Additional indexing

Item Type:Dissertation (monographical)
Referees:Bernstein Abraham
Communities & Collections:03 Faculty of Economics > Department of Informatics
UZH Dissertations
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Place of Publication:Zürich
Date:2019
Deposited On:31 Jan 2020 10:36
Last Modified:25 Aug 2020 14:44
Number of Pages:193
OA Status:Closed
Other Identification Number:merlin-id:19046

Download

Full text not available from this repository.
Get full-text in a library