The IT researchers (Physics of Information and Quantum Technologies Group) Bruno Coutinho, Lorenzo Buffoni and João Moutinho, won one of the Special Prizes at Science4Cast, an official competition within the 2021 IEEE BigData Cup Challenges. The team’s approach provided a simple, intuitive and scalable solution to the problem.

“Initially 3 prizes were announced for the 3 methods that showed the best performance, but there were still the Special Prizes, which took into account other criteria such as creativity, etc., and that’s how we won the Special Prize. Despite our method ranked 4th, it was recognised for a more original and simple solution”, says João Moutinho, who is also a Técnico PhD student in Physics.

The competition had 72 submissions from teams all over the world and aimed to reward the best predictions of future connections in a network of scientific concepts, in the fields of machine learning and artificial intelligence.

According to João Moutinho, in this type of competition, “very general models are created with a large number of possible characteristics that, later on, have to be trained to adapt to the problem in question”. Surprisingly, the IT team did not use any machine learning technique. “Instead, we analysed the problem using simple Network Science methods, and we were able to identify two key characteristics of this network: new connections are more likely to be made between popular concepts, which themselves already have many connections, and concepts which share many common neighbors”, explains the PhD student. “In addition, we also used the intuitive idea that the most important links are the oldest, corresponding to pioneering publications, and more recent links, corresponding to popular topics today”, he adds. The model developed by the IT team brought these three points together in an artisanal way and directly applicable to the problem, requiring only a small adaptation of some parameters.

At the IEEE BigData 2021 conference, the IT team was the only winning team that used this network theory, while all the other teams used machine learning techniques. “The advantage of our method is that it allows us to have an intuitive justification of the results, and does not require so many computational resources, thus allowing its application in even larger networks”, highlights the PhD student.

The 1st algorithm “with potential quantum speedup for network problems”

The knowledge acquired by João Moutinho in his PhD project, developed in collaboration with his teammate Bruno Coutinho and professor Yasser Omar (IST Department of Mathematics and Coordinator of the Information Physics Group and Quantum Technologies), was decisive in the team’s success.

The authors of the PhD work titled “Quantum Link Prediction in Complex Networks”, propose a quantum algorithm that predicts new links in complex networks by sampling from a continuous-time quantum walk, allowing a potential quantum speedup in this problem.

Professor Yasser Omar highlights the importance of this “first algorithm”, which is an old idea that took several years to develop and follows earlier works carried out by the group, which demonstrated the potential of quantum computing. “We live surrounded by complex networks, whether natural networks such as protein interaction networks, technological networks such as the internet, or social networks such as Facebook. We often do not have complete knowledge of these networks, and we use algorithms to find existing links between two nodes in the network”, says the Técnico professor.

This new quantum algorithm “whose prediction accuracy competes with the best current classical methods”, as professor Yasser Omar points out, “offers perspectives for quantum acceleration in large networks”. “It opens the door to investigate the potential of quantum computing in the many computational problems of complex network theory, and bring together these two fascinating topics”, concludes the Técnico professor.

João Moutinho is already working on some extensions of this work, such as “reducing the computational resources of the quantum method to improve the possible computational advantage over the classical case, and also an application in signed networks encompassing positive or negative connections”, shares the Técnico student.