Reinventing the Theory of Machine Learning on Graphs

Introduction

In many scientific domains, graphs are the objects of choice to represent structured data: from molecules to social networks, power grids, the internet, and so on. The exploitation of graph data represents a major scientific and industrial challenge.

Graph Machine Learning

Graph Machine Learning (GML) is thus a fast-growing field, with so-called Graph Neural Networks (GNN) at the forefront. However, in sharp contrast with traditional ML, the field of GML has somewhat jumped from early methods to deep learning, without the decades-long development of well-established notions to compare, analyze, and improve algorithms.

Limitations of GNNs

As a result, there are significant limitations:

1. GNNs, all based on the so-called message-passing paradigm, have significant limitations both practical and theoretical, and it is not clear how to address them.
2. GNNs do not take into account the specificities of graphs coming from domains as different as biology or the social sciences.

Thus, practical results may vary wildly from one case to the other, with no guidelines on how to design reliable GNNs in each case. Overall, these are the symptoms of an overlooked major issue: GML is hitting a glass ceiling due to its severe lack of a grand, foundational theory.

Project MALAGA

The ambition of project MALAGA is to develop such a theory. Solving the crucial limitations of the current theory is highly challenging for several reasons:

• Current mathematical tools cannot analyze the learning capabilities of GML methods in a unified way.
• Existing statistical graph models do not faithfully represent the many characteristics of modern graph data.
• Computational complexity becomes problematic on large graphs.

MALAGA will develop a radically new understanding of GML problems and of the strengths and limitations of a large panel of algorithms. Our goal is to significantly boost the performance, reliability, and adaptivity of GNNs, with a significant impact on three types of graph data that exhibit very different but representative behaviors: biological networks, social networks, and online recommender systems.