Accelerating Matrix Computations for Mining Large Dynamic Complex Networks

加速矩阵计算以挖掘大型动态复杂网络

• 批准号: 425481309
• 负责人: Professor Dr. Henning Meyerhenke
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/425481309?language=en
• 关键词: Accelerating; Matrix; Computations; Mining; Large

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.

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