Understanding Machine Learning on Graphs: From Node Classification to Algorithmic Reasoning.

Machine learning on graphs is currently one of the most prominent topics in artificial intelligence. The reason behind this trend is that many applications, such as recommendation systems, malicious behavior detection, drug discovery and reasoning tasks require the combination of relational and attribute information. The attributes capture information about the entities of interest, i.e., nodes in the graph, while edges in the graph capture relations among the entities.

The most popular models for such multi-modal data are graph neural networks. In this talk, I will provide a comprehensive understanding of the fundamental limitations and strengths of graph neural networks for node classification and algorithmic reasoning. I will start by presenting results on the performance of vanilla graph convolutional and attentional neural networks for the task of node classification. Then, I will define a notion of Bayes optimality for graph neural network architectures and I will present novel optimal architectures for
node classification.

Finally, I will talk about a new topic of research known as “Neural Algorithmic Reasoning”. I will present results on the ability of looped graph neural networks to execute classical algorithms such as breadth-first search, depth-first search, and Dijkstra’s shortest path algorithm for any input size up to a limit
determined by precision.