Deep learning on graphs: successes, challenges, and next steps

Deep learning on graphs: successes, challenges, and next steps

TL;DR This is the first in a series of posts where I will discuss the evolution and future trends in the field of deep learning on graphs.

Deep learning on graphs, also known as Geometric deep learning (GDL) [1], Graph representation learning (GRL), or relational inductive biases [2], has recently become one of the hottest topics in machine learning. While early works on graph learning go back at least a decade [3] 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 ML community and even to the popular science press (with Quanta Magazine running a series of excellent articles on geometric deep learning for the study of manifolds , drug discovery , and protein science ).

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 flavours to graph learning problems that are largely application-dependent. One dichotomy is between node-wise and graph-wise problems, where in 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 make a prediction about the entire graph (e.g. predict solubility of a molecule). Furthermore, like in traditional ML problems, we can distinguish between supervised and unsupervised (or self-supervised ) settings, as well as transductive and inductive problems.

Similarly 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 [5] between every node and its neighbours. 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 neighbour 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 I have 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 try to outline my views on the possible reasons and how the field could progress in the next few years.

Standardised benchmarkslike ImageNet were surely one of the key success factors of deep learning in computer vision, with some [6] 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 in 2019 is perhaps the first attempt toward this goal trying to introduce challenging graph learning tasks on interesting real-world graph-structured datasets. One of the hurdles is that tech companies producing diverse and rich graphs from their users’ activity are reluctant to share these data due to concerns over privacy laws such as GDPR. A notable exception is Twitter that made a dataset of 160 million tweets with corresponding user engagement graphs available to the research community under certain privacy-preserving restrictions as part of the RecSys Challenge . I hope that many companies will follow suit in the future.

Software librariesavailable in the public domain played a paramount role in “democratising” deep learning and making it a popular tool. If until recently, graph learning implementations were primarily a collection of poorly written and scarcely tested code, nowadays there are libraries such as PyTorch Geometric or Deep Graph Library (DGL) that are professionally written and maintained with the help of industry sponsorship. It is not uncommon to see an implementation of a new graph deep learning architecture weeks after it appears on arxiv.

Scalabilityis 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 fit for graph-structured data. In the long run, we might need specialised hardware for graphs [7].

Dynamic graphsare another aspect that is scarcely addressed in the literature. While graphs are a common way of modelling complex systems, such an abstraction is often too simplistic as real-world systems are dynamic and evolve in time. Sometimes it is the temporal behaviour 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 structuressuch 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.

Theoretical understandingof 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 completely clear yet when and why graph neural networks work well or fail. 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 concerned with the graph connectivity only, recent works showed that graph neural networks are equivalent to the Weisfelier-Lehman graph isomorphism test [8] (a heuristic for solving a classical problem in graph theory of determining if two graphs are identical up to the permutation of their nodes). 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.

Robustness and guaranteed performanceof graph neural networks in the presence of noisy data or when subjected to adversarial attacks [9] is another interesting and largely virgin research field.

Applicationsare perhaps the most gratifying part of the field. Having worked on graph learning for many years now, I have made friends with particle physicists [10], clinicians [11], biologists and chemists [12] — 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 [5], as well as high-level models of interactions between them [13,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 of antibiotics [14] earlier this year or to predict interactions between proteins [12]. 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.

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

[2] P. Battaglia et al., Relational inductive biases, deep learning, and graph networks , arXiv:1806.01261, 2018.

[3] F. Scarselli et al. The graph neural network model, IEEE Transactions on Neural Networks 20(1):61–80, 2008.

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

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

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

[7] C.-Y. Gui et al.. A survey on Graph Processing accelerators: Challenges and Opportunities , arXiv:1902.10130, 2019.

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

[9] D. Zügner et al., Adversarial attacks on neural networks for graph data , Proc. KDD 2018.

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

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

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

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

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