Dynamic Inexact High-Performance Algorithms for Network Centralities and Graph Embeddings

网络(即图)是各种现实世界应用中普遍存在的建模工具。图挖掘是从网络中提取知识的任务。这些网络通常由数亿到数十亿个顶点组成。在这种规模的图上，通常需要运行时间为(接近)线性的并行算法才能在合理的时间内得到结果。不幸的是，许多有趣的图挖掘问题本质上是困难的，不允许这样的算法。为此，这些问题的解决方案越来越依赖于产生近似答案或放松问题约束的不精确方法。现实世界的网络往往会随着时间的推移而变化，这一事实带来了更多的挑战。在这种情况下，可以使用动态算法来避免频繁的从头开始重新计算。事实上，已经为顺序和共享内存模型设计了动态不精确算法。然而，尽管存在备受瞩目的应用程序，但对分布式内存中的动态图形的操作还没有得到很好的理解。在这个方案中，我们想要开发新的动态不精确图挖掘算法，适用于高性能集群和超级计算机上的现实应用。我们的目标是两个重要的应用，即网络中心性和图嵌入。与最先进的解决方案相比，这一提议将实现三个新功能：(I)我们将设计高性能计算(HPC)算法来解决动态图挖掘问题，其速度将大大快于当前可能的速度；(Ii)我们将能够获得比目前可行的更高精度的(不精确的)结果；以及(Iii)由于我们将支持分布式内存中的图，因此可以应用我们的算法来分析单个计算节点的内存无法容纳的动态图。

Networks (i.e., graphs) are a ubiquitous modelling tool in various real-world applications. Graph mining is the task of extracting knowledge from networks. Those networks often consist of hundreds of millions to several billions of vertices. On graphs of this size, parallel algorithms with (nearly-)linear running time are usually required to obtain results within reasonable time. Unfortunately, many interesting graph mining problems are inherently difficult and do not admit such algorithms. To this end, solutions to these problems increasingly rely on inexact methods that yield approximate answers or relax the constraints of the problem. The fact that real-world networks often change over time poses further challenges. In this context, dynamic algorithms can be employed to avoid frequent recomputation from scratch. Indeed, dynamic inexact algorithms have already been designed for sequential and shared-memory models. Manipulating dynamic graphs in distributed memory, however, is not well-understood yet -- despite the fact that high-profile applications exist. In this proposal, we want to develop new dynamic inexact graph mining algorithms suitable for real-world applications on high-performance clusters and supercomputers. We target two important applications, namely network centralities and graph embeddings. Compared to state-of-the-art solutions, this proposal will enable three new capabilities: (i) we will design high-performance computing (HPC) algorithms to solve dynamic graph mining problems significantly faster than currently possible, (ii) we will be able to obtain (inexact) results of better accuracy than what is currently feasible and (iii) since we will support graphs in distributed memory, it will be possible to apply our algorithms to analyze dynamic graphs that are too large to fit into the memory of a single compute node.