Servicenavigation

Project Details

Back

Projekt Print View

Accelerating Matrix Computations for Mining Large Dynamic Complex Networks

Subject Area Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics
Term from 2019 to 2024
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 425481309
 
Final Report Year 2023

Final Report Abstract

Graph mining and machine learning methods often apply linear algebra routines on big data sets. Such routines can be computationally expensive and may exceed available resources. In addition, dynamic changes over time in such data sets are rarely addressed in stateof-the-art software libraries. It was our motivation to overcome several of these aspects with AL-MACOM, specifically to accelerate algebraic algorithms for large-scale and dynamic data sets. To facilitate dynamic graph operations, we published Dynamic Hashed Blocks (DHB), a graph data structure that outperforms state-of-the-art competitors when executing common static and dynamic operations. DHB served as a foundation for several contributions that followed. To improve basic algebraic kernels, we proposed a new MPI-based dynamic sparse matrix multiplication (SpGEMM) algorithm in case of edge updates. This could then be extended to an MPI-based algorithm for dynamic closeness centrality. Using mostly combinatorial techniques, we proposed a new algorithm for approximating the diagonal of the Laplacian pseudoinverse of graphs. This resulted in a more accurate, faster, and more memory-efficient approximation compared to the state of the art. Moreover, we adapted the algorithm to the related problem of approximating the diagonal of the so-called forest matrix. Also this adapted algorithm has the favorable properties mentioned above. The performance of graph analytics kernels also depend on their cache efficiency, which can be optimised by graph reordering. One of our efforts resulted in a multilevel algorithm for mapping graph applications onto hierarchical architectures – it shows a better quality to speed trade-off compared to the competition and can be extended easily to reordering. In addition, we proposed a static and dynamic algorithm for computing a vertex ranking according to Katz centrality. The algorithm improves lower and upper bounds on the centrality values iteratively. This way, it can give (approximate) guarantees on the ranking quality – as opposed to previous methods. Additionally, we proposed a dynamic version of the Suitor approximation algorithm for weighted matchings in graphs. As one further application of our work on approximating (pseudo)inverse matrices, we investigated graph robustness, resulting in algebraic and combinatorial techniques to speed up an established greedy algorithm.

Publications

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung