Algorithms with predictions for triangle counting in temporal networks

In recent years, there have been major efforts in refining existing algorithms by considering problem instances that are likely to appear, while maintaining a formal and rigorous methodology as in time and space complexity analysis. This approach exploits Machine Learning to extract additional information from the data received in input and predict useful properties of the considered instances that can be used to improve the algorithm performance. Such an approach is referred to as “Algorithms with Predictions”. This work aims to apply this framework to the Motif Counting Problem in large Temporal Networks, focusing on improving standard sampling algorithms techniques and providing guarantees on the results obtained. In particular, we design and analyze the first algorithm for counting triangles in temporal networks using machine learning predictions. We also perform an in-depth experimental evaluation of the algorithm presented, in order to gather evidence on its practical effectiveness and efficiency.