How to create graphs in hardware-constrained environments? Choosing the best creation approach via machine learning-based predictive models

Graphs are increasingly adopted to model and handle complex systems, but their processing is known to be resource-intensive due to the complexity of the algorithms and the size of the graphs. This hindrance limits their usage for those who do not possess sophisticated equipment with “unlimited” memory space. In this paper, a new graph format called compressed edge-centric (CEC) is proposed, aiming to reduce memory usage by compressing graph edges, facilitating more efficient large graph handling. It is then followed up by the implementation of several graph creation approaches, each using a different graph representation and parallelism level. The idea is to use a predictive model to estimate the execution time and used memory, along with a decision-making process that will automatically choose the best approach by selecting the lowest predicted time that does not overload the memory for a given graph and in a certain hardware environment. Experiments on diverse real-world graphs, sourced from the Network Repository, demonstrate that CEC-based creation methods are more efficient than vertex-centric techniques in terms of time (up to 60% decrease) and in many cases in terms of memory consumption (up to 50% decrease). Since this efficiency is not uniformly observed, this work relies on machine learning models to predict the time and memory of each approach for a given context. The results show that linear models are not adequate to thoroughly predict time and memory consumption, while tree-based solutions give considerably better results.