Accelerating Matrix Computations for Mining Large Dynamic Complex Networks

点击翻译按钮获取中文摘要

Many common techniques in graph mining and machine learning are based on linear algebra routines that are expensive on large data sets. A prime example is the computation of many eigenpairs or even the full eigendecomposition of a graph's Laplacian matrix. Executing such operations on graphs with millions or billions of edges results in high running times or may even be impractical. Moreover, library implementations of linear algebraic kernels do not takegraph changes over time into account. Since dynamic graphs such as the web graph or social interaction networks are abundant these days, this omission leads to a waste of computing resources.Our proposal aims at significantly faster (yet inexact) algorithms for linear algebra routines for dynamic graph mining applications. We want to develop algorithms that monitor the graph's and the algorithm's state over time with appropriate data structures; this avoids costly restarts from scratch. Moreover, we use approximation in order to trade running time with (a still sufficient) accuracy and exploit common structural features of complex networks, our main input class. To this end, we want to combine results and techniques from numerical linear algebra (NLA), combinatorial scientific computing and theoretical computer science. As a significant part of the project, we demonstrate the improvement by means of three common graph mining tasks in dynamic scenarios: clustering, similarity and representation. Finally, the integration of our new algorithms into the open-source network analysis tool NetworKit will help community adoption and also speeds up other NLA-based graph mining routines.