Deep Learning on Graphs: History, Successes, Challenges, and Next Steps

Contributed by Dr. Michael Bronstein, professor at Imperial College London and Head of Graph Learning research at Twitter. This post is based on the article “Geometric Deep Learning: Going beyond Euclidean data” that appeared in the IEEE Signal Processing Magazine, July 2017. It is available in IEEE Xplore® . 

Dr. Bronstein also presented this topic as a 2020 SPS Webinar. You can find the recorded webinar at the SPS Resource Center.

Deep learning on graphs, also known as Geometric deep learning (GDL) [1], Graph representation learning (GRL), or relational inductive biases, has recently become one of the hottest topics in machine learning. While early works on graph learning go back at least a decade [2], if not two [3], it is undoubtedly the past few years’ progress that has taken these methods from a niche into the spotlight of the Machine Learning (ML) community.

Graphs are powerful mathematical abstractions that can describe complex systems of relations and interactions in fields ranging from biology and high-energy physics to social science and economics. Since the amount of graph-structured data produced in some of these fields nowadays is enormous (prominent examples being social networks like Twitter and Facebook), it is very tempting to try to apply deep learning techniques that have been remarkably successful in other data-rich settings.

There are multiple flavors to graph learning problems that are largely application-dependent. One dichotomy is between node-wise and graph-wise problems, wherein the former one tries to predict properties of individual nodes in the graph (e.g., identify malicious users in a social network), while in the latter one tries to predict the entire graph (e.g., predict the solubility of a molecule). Furthermore, as in traditional ML problems, we can distinguish between supervised and unsupervised (or self-supervised) settings, as well as transductive and inductive problems.

Similar to convolutional neural networks used in image analysis and computer vision, the key to efficient learning on graphs is designing local operations with shared weights that do message passing [8] between every node and its neighbors. A major difference compared to classical deep neural networks dealing with grid-structured data is that on graphs such operations are permutation-invariant, i.e., independent of the order of neighbor nodes, as there is no canonical way of ordering them.

Despite their promise and a series of success stories of graph representation learning (among which I can selfishly list the acquisition by Twitter of the graph-based fake news detection startup, Fabula AI, that I founded together with my students), we have not witnessed so far anything close to the smashing success convolutional networks have had in computer vision. In the following, I will outline my views on the possible reasons and how the field could progress in the next few years.

Standardized benchmarks like ImageNet were surely one of the key success factors of deep learning in computer vision, with some [4] even arguing that data was more important than algorithms for the deep learning revolution. We have nothing similar to ImageNet in scale and complexity in the graph learning community yet. The Open Graph Benchmark launched earlier this year is perhaps the first attempt toward this goal.

Scalability is one of the key factors limiting industrial applications that often need to deal with very large graphs (think of Twitter social network with hundreds of millions of nodes and billions of edges) and low latency constraints. The academic research community has until recently almost ignored this aspect, with many models described in the literature completely inadequate for large-scale settings. Furthermore, graphics hardware (GPU), whose happy marriage with classical deep learning architectures was one of the primary forces driving their mutual success, is not necessarily the best for graphs. We need specialized hardware for graphs.

Dynamic graphs are another aspect that is scarcely addressed in the literature. While graphs are a common way of modeling complex systems, such an abstraction is often too simplistic as real-world systems are dynamic and evolve in time. Sometimes it is the temporal behavior that provides crucial insights about the system. Despite some recent progress, designing graph neural network models capable of efficiently dealing with continuous-time graphs represented as a stream of node- or edge-wise events is still an open research question.

Higher order structures such as motifs, graphlets, or simplicial complexes are known to be of importance in complex networks, e.g., describing protein-protein interactions in biological applications. Yet, the majority of graph neural networks are limited to nodes and edges only. Incorporating such structures into the message passing mechanism could bring more expressive power to graph-based models.

The theoretical understanding of the expressivity of graph neural networks is rather limited. It is common to see both dramatic boosts in performance coming from the use of graph neural networks in some settings along with almost no difference in others. It is not clear yet when and why graph neural networks work well. The problem is difficult because one has to consider both the structure of the underlying graph as well as the data on it. For graph classification problems, recent works showed that graph neural networks are equivalent to Weisfeiler-Lehman graph isomorphism test [5], a heuristic for solving a classical problem in graph theory. This formalism sheds light on why, for example, graph neural networks fail on instances of non-isomorphic graphs that cannot be distinguished by this simple test. Going beyond the Weisfeiler-Lehman hierarchy of tests while keeping the low linear complexity that makes graph neural networks so attractive is an open research question.

Applications are perhaps the most gratifying part of the field. Having worked on graph learning for many years now, I have made friends with particle physicists [9], biologists, clinicians [10], and chemists [5] - people I would unlikely meet otherwise had we not worked on applications in their respective fields. If I were to bet on just one field where graph deep learning could make the biggest impact in the next few years, I would indicate structural biology and chemistry. In these fields, graph-based models can be used both as low-level models for molecules [8], as well as high-level models of interactions between them [10], [11]. Combining these might be the key to getting to a level that would be useful for the pharmaceutical industry - and we see initial signs of this, with graph neural networks used to discover a new class antibiotics [4] earlier this year or to predict interactions between proteins [5]. If graph deep learning delivers on its promise, the traditionally very long and astoundingly expensive process of discovering, developing, and testing new drugs may never look the same.

References:

[1] M. Bronstein et al., Geometric deep learning: going beyond Euclidean data, IEEE Signal Processing Magazine 34(4):18-42, 2017, DOI: 10.1109/MSP.2017.2693418.

[2] F. Scarselli et al., The graph neural network model, IEEE Transactions on Neural Networks 20(1):61-80, 2008, DOI: 10.1109/TNN.2008.2005605.

[3] A. Küchler and C. Goller, Inductive learning in symbolic domains using structure-driven recurrent neural networks, Proc. Künstliche Intelligenz, 1996.

[4] A. Wissner-Gross, Datasets over algorithms, 2016.

[5] K. Xu et al., How powerful are graph neural networks? ICLR 2019.

[6] J. Stokes et al., A deep learning approach to antibiotic discovery. Cell, 180(4), 2020.

[7] P. Gainza et al., Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning, Nature Methods, vol. 17:184–192, 2020.

[8] J. Gilmer et al., Neural message passing for quantum chemistry, ICML 2017.

[9] N. Choma et al., Graph neural networks for IceCube signal classification, ICMLA 2018.

[10] K. Veselkov et al., HyperFoods: Machine intelligent mapping of cancer-beating molecules in foods, Nature Scientific Reports, 9:9237, 2019.

[11] M. Zitnik et al., Modeling polypharmacy side effects with graph convolutional networks, Bioinformatics 34(13):457-466, 2018.