Accelerating Matrix Computations for Mining Large Dynamic Complex Networks

图挖掘和机器学习中的许多常见技术都是基于线性代数例程的，而这些例程在大数据集上是昂贵的。一个最好的例子是计算许多特征对，甚至是图的拉普拉斯矩阵的全特征分解。在具有数百万或数十亿条边的图上执行此类操作会导致很长的运行时间，甚至可能是不切实际的。此外，线性代数内核的库实现不考虑图形随时间的变化。由于动态图如网络图或社交网络的大量存在，导致了计算资源的浪费。我们的建议旨在为动态图挖掘应用程序的线性代数例程提供更快(但不精确)的算法。我们希望开发算法，通过适当的数据结构随着时间的推移监控图形和算法的状态；这避免了代价高昂的从头开始。此外，我们使用近似来以(仍然足够的)精度来交换运行时间，并利用我们的主要输入类复杂网络的共同结构特征。为此，我们希望将数值线性代数(NLA)、组合科学计算和理论计算机科学的结果和技术结合起来。作为项目的重要组成部分，我们通过动态场景中三个常见的图挖掘任务：聚类、相似度和表示来演示改进。最后，将我们的新算法集成到开源网络分析工具NetworKit中将有助于社区采用，并加快其他基于NLA的图挖掘例程。

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.