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

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

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.