I’m happy to cheer you again after the summer 🌞 Hopefully, you enjoyed the sun and rested well for the next academic season as it promises quite a packed agenda to explore. In today’s episode, we will look back at the recent talks, latest trends, and upcoming events. Let’s go!

Videos 👀

Geometric Deep Learning @ML Street Talk

Michael Bronstein, Petar Veličković, Taco Cohen and Joan Bruna are special guests in the new 3.5 hours episode of ML Street Talk talking Geometric DL and explaining the concepts covered in their recent book and pretty much all the current state of the art in the field.

Graph Learning Workshop

A workshop organized by Stanford on the latest advances in Graph Neural Networks. The program includes applications, frameworks, and industry panels on the challenges of graph-based machine learning models.

GDL Course

A course on Geometric Deep Learning, which closely follows the contents of the GDL proto-book. It contains 12 lectures, 2 tutorials, and 4 seminars coverings topics such as graphs, grids, geodesics, and more.

GNN User Group Videos

July’s video from a regular meeting of the GNN user group includes a discussion of the new features of DGL library and two research talks on storing node feature for large graphs and locally private GNNs.

Interpretable Deep Learning for New Physics Discovery

In this video, Miles Cranmer discusses a novel method for converting a neural network into an analytic equation using a particular set of inductive biases. With it, they discover gravity along with planetary masses from data; they learn a technique for doing cosmology with cosmic voids and dark matter halos; and they show how to extract the Euler equation from a graph neural network trained on turbulence data.

LOGML Videos

LOGML is an exciting summer school with projects and talks about graph ML. A collection of videos that includes presentations of the cutting-edge research as well as industrial applications from leading companies are available now for everyone.

ICML 2021 Videos

One of the main important conferences in ML, ICML, features about 50 papers on graphs, for which recordings are now available. For the list of relevant graph papers, check out this repo.

Software 💻

PyG 2.0 Release

A major new release of Pytorch Geometric -- a collaboration between Stanford and TU Dortmund. In addition to a constantly growing number of supported GNN architectures, the 2.0 version features heterogeneous graph support, GraphGym - a whole platform for designing and experimenting with GNNs, pre-defined models, half-precision support, and other smaller improvements to make your GNN journey easier.

DGL 0.7 Release

DGL v0.7 brings improvements on the low-level system infrastructure as well as on the high-level user-facing utilities. Among improvements are GPU-based neighbor sampling that removes the need to move samples from CPU to GPU, improved CPU message-passing kernel, DGL Kubernetes Operator, and search over existing models and applications.

TorchDrug: a powerful and flexible machine learning platform for drug discovery

Jian Tang and co-workers from MILA open-sourced a new library TorchDrug on drug modeling with machine learning. It includes an easy interface for property prediction, pretrained molecular representations, de-novo molecule design & optimization, knowledge graph reasoning, and more.

Posts 📚

Graph Neural Networks as Neural Diffusion PDEs

A post by Michael Bronstein about the connection of GNNs and differential equations that govern diffusion on graphs. This gives a new mathematical framework for studying different architectures on graphs as well as a blueprint for developing new ones.

Review: Deep Learning on Sets

A new blog post by Fabian Fuchs and others about recent approaches to applying deep learning on sets. It digests several paradigms such as permuting & averaging, sorting, approximating invariance and learning on graphs as a way to overcome permutation invariance of machine learning algorithms.

GNN Tutorial & Graph Convolution Intuition @ Distill

As the last bow of Distill.pub, the authors prepared two very cool articles breaking down message passing and graph convolutions: A Gentle Introduction to Graph Neural Networks and Understanding Convolutions on Graphs.

Knowledge Graphs in Natural Language Processing @ ACL 2021

Already a regular update from Michael Galkin on the SOTA applications of KG in the world of words. This year’s focus is on neural databases & retrieval, KG-augmented language models, KG embeddings & link prediction, entity alignment, KG construction, entity linking, relation extraction, KGQA: temporal, conversational, and AMR.

Future events 🔮

The Learning on Graphs and Geometry Reading Group

A graph and geometry reading group organized by Hannes Stärk with supervision from Pietro Liò at Cambridge. It includes many interesting fresh papers on graphs.

Graph ML in Industry Workshop

Complementary to the Stanford’s event above, we organize a mini-workhop that would gather industry researchers to talk about their experience of applying graph models in production. Our motivation was an apparent shortage of industry applications for GNNs and graph embeddings in the real-world and desire to share success stories and pain points of those who go from research to production. Please, join us at the Zoom and YouTube on 23rd September, 17-00 Paris time (should be more or less time-friendly for most of the time zones).

That’s all for today 👋 If you like the post 👍, make sure to subscribe to my twitter 🐦and graph ML telegram channel 📝 Until next time!

Sergey

This is an Express version ⚡ of the newsletter that highlights recent events in graph machine learning. As ICLR just took place 💻, ICML released their accepted papers 📝, and NeurIPS started reviewing process ⚖, it’s good time to look back at what has happened in the world of graphs 🌐

Conferences

ICLR 2021

This year's International Conference on Learning Representations (ICLR) was supposed to be in Vienna, but the second year for obvious reasons it happened online. I personally liked more 2020 version of ICLR, maybe because back then online conferences just started and I was not exhausted by the zoom meetings. But on the positive side, there were gather.town poster sessions which remind real connections between attendees.

The compilation of keynotes was amazing: Michael Bronstein’s talk about geometric deep learning, Timnit Gebru’s talk on fairness in AI, Alexei Efros’s talk on various forms of self-supervised learning, among others. Top content 👏 Besides, you can browse the short videos for more than 800 ICLR papers, many of which are on graph neural networks and graph embeddings.

ICML 2021

ICML 2021 is coming this July and the paper titles are now available. ICML 2021 has a slight increase in submissions and accepted papers compared to 2020 and retains the same acceptance rate. Many stats about ICML 2021 can be found in this tweet:

There are about 60 graph papers, on topics such as oversmoothing, explainability, expressivity, robustness, and so on (categorization is offered here). Top authors at ICML 2021 who publish graph papers are displayed below:

WebConf 2021

WebConf 2021 accepted 357 papers and about 30% of all papers are on graphs. Videos are available here and the topics span many applications in security, search, recommendations, and more.

NAACL 2021

North American ACL conference accepted 477 papers that are centered around NLP applications. There are about 30 papers that apply graphs to text summarization, dialogue systems, translation, and more. Additionally, there is an interesting tutorial “Deep Learning on Graphs for Natural Language Processing”, which is based on Graph4NLP library.

MLSys 2021

MLSys is one of the conferences that look at the intersection between ML and industrial systems and this year there was a spectacular workshop on Graph Neural Networks and Systems (GNNSys'21). The talks are available online and include topics such as GNNs on graphcore's IPU, chip placement optimization, particle reconstruction at the large hadron collider and more.

Videos

CS224W Lectures

A legendary Stanford CS224W course on graph ML now releases videos on YouTube. There are 20 video lectures and slides available online. Topics include PageRank, GNNs, knowledge graphs, generative models, community detection, and applications.

GNN User Group

GNN user group organized by AWS and Nvidia continues to host monthly talks on the latest research in the GNN world. Recent talks are about graph transformers, GBDTs for heterogeneous graphs, and GNNs in therapeutics. Check them out here.

Pytorch Geometric tutorials

A nice channel that goes over the implementation of GNN models in PyTorch-Geometric. It also features talks and presentations from researchers working in the field. There are more than 15 tutorials available.

Blog posts, competitions, and books

Knowledge Graphs @ ICLR 2021

One and only Michael Galkin does it again with a superior digest of knowledge graph research at ICLR 2021. Topics include reasoning, temporal logics, and complex question-answering in KGs: a lot of novel ideas and less SOTA-chasing work!

Graphs at ICLR 2021

Another take on graph works at ICLR by Daniele Paliotta. He highlights some papers that solve overmoothing, over-squashing, heterophily, and attention problems in GNNs.

Graph Neural Networking Challenge 2021

If you still have energy after OGB-LSC challenge, there is a new competition, organized by Technical University of Catalonia (UPC) and ITU, about building GNNs to predict source-destination routing time. The goal is to test the generalization abilities of GNNs: training on small graphs and testing on much larger graphs.

Geometric Deep Learning Book

A new book by graph ML experts Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković on geometric deep learning is released. 156 pages on exploring symmetries that unify different ML neural network architectures. An accompanying post nicely introduces the history of geometry and its impact on physics. It's exciting to see a categorization of many ML approaches from the perspective of the group theory.

That’s all for today 👋 If you like the post 👍, make sure to subscribe to my twitter 🐦and graph ML telegram channel 📝 You can support these emails by subscribing to this newsletter 📧 Until next time!

Sergey

Hello and welcome to the graph ML newsletter!

This in-depth post is about self-supervised learning (SSL) and its applications to graphs. Disclaimer: this post is long and can be clipped in gmail, in which case you can go to the web version now.

There are hundreds of works, with many surveys (e.g. one, two, three, four) and blog posts written (e.g. this and that), so it was quite overwhelming to digest, but eventually I categorized these works into three distinct groups, based on the training procedure each group has. But before going into details, let’s first define what it is.

What is self-supervised learning and how is it different from unsupervised learning?

Before ~2016, unsupervised learning (UL) and SSL were used interchangeably. Circa 2016 Yann LeCun and other researchers started using the term SSL to highlight that we have large volumes of data which we feed to neural networks to learn representations.

So now we use the term SSL when we want to say that we learn representations in unsupervised manner, while UL solves the task directly, without learning useful representations. For example, in the context of graphs there is a rich line of works on graph kernels, where graphs are represented as a histogram of some statistics (e.g. degree values) and these histograms are not learned but rather computed via an algorithm in an unsupervised manner.

Then, why self-supervised learning is such an active area of research now?

One obvious reason is that labeling the data is expensive and if we can achieve the same performance with SSL as with supervised learning by leveraging big corpuses of data it would enable all sorts of applications. But maybe more importantly, SSL would allow us to reduce the role of humans in the design choices of ML pipeline, as was outlined by Alexei Efros in his ICLR’21 keynote talk.

Specifically, SSL would allow us (a) to let the neural network cluster the objects based on the similarity of the contexts they appear instead of the human-designed label (think of the word “chair”, which is rather defined by the action “sit” and not by how it visually appears); (b) to learn on the data similarly how humans learn by always seeing a new image and (c) to omit the explicit single reward that humans design for neural networks to optimize and instead let neural networks to decide what they want to optimize next, based on the data they deal with at the moment.

Now that we understand what SSL and why do we want it, let’s look at the three forms of self-supervised learning. 🔽

SSL as property prediction

This is probably the easiest and the most explanatory type of self-supervised learning because we know exactly what our representation model predicts. Such models define a target label for each node based on the topological structure around it and the loss is cross-entropy for classification or MSE for regression between the defined target labels and the predictions of the model.

For example, S2GRL defines the target label as the hop-count between two nodes, GROVER predicts the number of node-edge types for molecules as well as if a particular motif exists in the graph. Hwang et al. show that one can boost the performance of any GNN by creating an additional SSL task of predicting a link between two nodes. Jin et al. compare regression-based tasks such as predicting the degree of a node or the distance to the cluster center.

As you can see the difference between these approaches lies only in the form of what statistics we want to predict. This approach is useful if you know what the downstream task would be. For instance, if the downstream labels correlate with the degrees of nodes then it makes sense to create an SSL task that predicts the degrees correctly. However, what to do if you don’t know where the learned representations would be used? In that case, you can resort to the second type of SSL. ⏬

SSL as contrastive learning

Contrastive learning hinges on the distinction between positive and negative views of the object. The view is defined as some perturbation of the object such as addition or removal of node or edges, subgraph sampling, or feature masking.

Most of the contrastive learning is based on the maximization of the mutual information between two random variables X and Y, where X is the target and Y is the context. In the context of graphs, X is the true or given graph G, while Y is a view of some graph (not necessarily of G).

Mutual information (MI) is the KL divergence between the joint distribution P(X, Y) which represents the distribution of positive pairs (target-positive context), and the product of the marginal distributions P(X)P(Y), which represents the distribution of negative pairs (target-negative context).

KL divergence, in turn, measures the expected number of extra information necessary to identify X and Y if they are modeled via marginal distributions instead of the joint one. If KL divergence is zero, it means that X and Y are independent, and knowing Y tells you nothing about X. So when you maximize mutual information, you want your model to distinguish well between positive pair and negative pair.

To measure mutual information one has to take the expectation of the joint P(X, Y) and marginal distributions P(X) and P(Y) and unless they are known in advance it’s impossible to compute mutual information exactly from the finite data. Instead, one approximates the true value of mutual information by maximizing some empirical lower bound of MI which could be easily computed on positive and negative pairs. The idea is that if the lower bound is close to the true value of MI, then maximizing lower bound will maximize MI too.

One of the earliest bounds is the Donsker-Varadhan (DV) lower bound, which could be estimated empirically as follows:

This bound provides the loss value for the encoder f, which is used to measure the similarity scores of positive and negative pairs. For example, graph model MVGRL compares this DV estimator to several other lower bounds discussed below.

Another popular bound is Jensen-Shannon (JS) estimator which is defined as follows:

For example, Deep Graph Infomax and InfoGraph use Jensen-Shannon on corrupted positive and negative views of the same graph. When f is sigmoid function, JS estimator is a logistic regression loss that tries to distinguish between positive and negative pairs. When K negative samples are used for each positive pair this loss is also known as negative sampling loss. Negative sampling loss has been popularized by word2vec model, which inspired several graph models such as DeepWalk, LINE, and node2vec.

Another popular lower bound is the noise contrastive estimation (NCE):

NCE bound is very similar to DV bound with the difference that NCE draws K samples per each positive and has logarithm inside the expectation in the negative part. A particular instance of NCE is called NT-Xent, which computes the similarity f(x) as a normalized temperature-scaled dot product of target and context representations. Grace and GraphCL are examples of graph models that utilize NCE loss on generated views of the same graph.

If K=1 NCE loss can be seen as a triplet loss, which was used in Subg-Con that contrasts sampled subgraphs for a given node.

Tighter bound to NCE was derived by Nguyen, Wainwright, and Jordan (NWJ):

Other contrastive losses include BPR loss, popular in the context of ranking optimization, that optimizes a sigmoid of a difference between a positive and a negative pair.

Recently Grill et al. proposed a contrastive loss BYOL which does not require generating negative samples, but works on two positive views. One may think that such loss would lead to the collapsed constant representation, however, as was shown later this loss vitally depends on the batch norm that acts as implicit contrastive learning with an average view. BYOL loss was used by BGRL algorithm on node classification task.

These losses are summarized below.

This number of choices is overwhelming so rightfully one can ask what loss function to choose in contrastive learning? Theoretically, there is a proof by McAllester and Stratos that any distribution-free lower bound (including those discussed above) on mutual information cannot be larger than O(logN) so if the true mutual information is high, then it’s infeasible to estimate it correctly with lower bounds. So from this perspective none of the bounds is good enough.

Moreover, Tschannen et al. showed that looser lower bounds can lead to better representations in downstream tasks and the success of these methods could be explained through the view of triplet-based metric learning. Given these results, it seems that the choice for particular objective should be based on the ease of computation and the downstream results that the learned representations achieve.

SSL as generative modeling

The third type of self-supervised learning tries to generate the instances of the graphs that would resemble or coincide with the ones presented in the dataset. Autoregressive generative models attempt to generate the next element given all previously generated ones in iterative fashion.

GraphRNN is one of the first autoregressive models that adds nodes one by one with an RNN encoder that adds connections for a newly added node. MolecularRNN subsequently improved this model for molecule generation by additionally considering physical properties of realistic molecules. GPT-GNN masks node attributes and edges and iteratively builds the graph by encoding each node with two GNNs for attributes and edges, respectively.

Auto-encoding generative models aim to reconstruct the entire input in one shot by passing it through an encoder-decoder pipeline. Variational auto-encoders (VAE) are an important example of this that optimizes the following loss:

VGAE was among the first to use this idea on graphs. The encoder is a simple GCN model, while the decoder generates an adjacency matrix as a dot product between latent node representations. DVNE uses Wasserstein auto-encoder that minimizes Wasserstein distance between the data distribution and the encoded training distribution.

The goal of adversarial generative models is to train two networks, one that generates objects (generator) and one that discriminates between the true objects and the generated ones (discriminator). Note that generator does not have to produce entire graphs, but can output graph-related statistics such as connectivity, random walks, or subgraphs.

GraphGAN is one example of adversarial graph model where generator predicts connectivity of every node, which is subsequently discriminated against the true ones. Next, NetGAN has a generator that produces random walks from a latent variable which are then compared against the random walks from the true graph. MolGAN takes this idea further and generates entire graphs of pre-defined size at once by MLP, which are compared against true molecules.

As you can see there are plenty of methods for obtaining self-supervised representations so it’s natural to ask:

Which self-supervised model should I pick for my task?

And as you may guess there is no silver bullet for all downstream tasks but rather an entire toolbox you can use to approach your problem. However, some general strategies exist to narrow down the search.

As said above, property prediction SSL excels at tasks where the auxiliary label correlates with the target label of the downstream task. For example, in the context of recommendation one may predict the number of views of each product as a proxy for the more precise and rarely available label such as the number of purchases of a product.

Contrastive SSL is a very active area of research right now and is considered to be state-of-the-art for many tasks in computer vision. Recent breakthroughs in this area, including such models as SwAV, MoCo, and SimCLR achieved classification accuracy on ImageNet close to the supervised methods, even though they don’t use true labels.

Finally, generative SSL is able to learn the underlying distribution of the data without assumptions of the downstream tasks and as such achieves phenomenal results in natural language modeling in models such as GPT-3 and BERT. Hence, if your learned representations are going to be used in the generation of new objects (texts, audios, or graphs), then generative SSL should be a default choice.

That’s all for today 👋 If you like the post 👍, make sure to subscribe to my twitter 🐦and graph ML telegram channel 📝 You can support these emails by subscribing to this newsletter 📧 Until next time!

Sergey

This post is the first one that I made for paying subscribers only for a few reasons. I generally try to be open about my ideas but thought I make a subscriber-only post for a few reasons.

First, I greatly appreciate your support in my writings, it motivates me to learn more about the subjects and then share this knowledge with every…

Read more

For some time I was struggling with the format of this newsletter: whether to write about news and blog posts or about my recent insights in some specific topics. So I decided to separate between these formats and call all my emails that gather recent news in the field as GML Express and my emails that dive into very specific topics as GML In-Depth. Today, I will do my first issue of GML Express, which will cover announcements, videos, courses and tutorials, and blog posts.

Announcements

Graph machine learning challenges at KDD Cup 2021

There are two graph-related challenges at KDD Cup this year: OGB-LSC and City Brain.

The first one asks you to build graph models for link prediction, graph regression, and node classification tasks on graphs of unprecedented scale (the largest has ~250M nodes). Dates: 15th March - June 8th. The winners will be honored at the KDD 2021 opening ceremony.

The second challenge asks you to build a model to predict and optimize traffic at a city-scale road network — the task where GNNs work well. Dates: 1st April - 1st July. The top-10 winners will take home 10K USD.

Release of PyG-Temporal

PyG-Temporal is an extension of a popular PyTorch library PyG for temporal graphs. It now includes more than 10 GNN models and several datasets. With world being dynamic I see more and more applications when standard GNN wouldn't work and one needs to resort to dynamic GNNs.

Blog posts

Graph Transformer: A Generalization of Transformers to Graphs

A blog post by Vijay Prakash Dwivedi about their paper with Xavier Bresson at 2021 AAAI Workshop. It is a generalization of GAT network with batch norm and positional encodings, which aggregates via local neighborhoods. After studying heterophily I expect to see more works that go beyond local neighborhoods, for example by learning the nodes to attend to across the whole graph. One recent instance of such architecture is a paper Language-Agnostic Representation Learning of Source Code from Structure and Context ICLR 2021 that combines structure of AST graph with the context of each word for attention model in the code summarization task.

Top-10 Research Papers in AI

My recent blog post about the top-10 most cited papers in AI for the last 5 years. I looked at major AI conferences (ICML, NeurIPS, ICLR, etc.) and journals (Nature) (excluding CV and NLP conferences). One of the most cited papers is the seminal work by Kipf and Welling introducing Graph Convolutional Network (GCN) that spawned a lot of research in graph ML. It was quite a refreshing experience to realize that many of what we use today by default (Adam, Batch Norm, adversarial attacks, etc.) have been discovered only within the last few years.

Graph Neural Networks by Jonathan Hui

Two blog posts about GNNs by a popular ML writer Jonathan Hui (known for his RL, CV, and DL blog posts). In the first one he describes the basics of GNNs (MP, pooling, etc) as well as some popular models (ChebNet, MoNet, GAT, etc.). The second one covers recurrent GNNs, graph auto-encoders, spatio-temporal models, and applications.

The Easiest Unsolved Problem in Graph Theory

This is our blog post about reconstruction conjecture, a well-known graph theory problem with 80 years of results but no final proof yet. It’s one of the grand challenges of graph theory and it has seen some progress recently, so hopefully it will be resolved in my lifetime. In the meantime, we considered graph families for which reconstruction conjecture is known to be true and tried to come up with the easiest family of graphs that is still not resolved and have very few vertices. The resulted family is a type of bidegreed graphs (close to regular) on 20 vertices, which is probably possible to verify by brute-force computer computations (though it would take a year or so).

Learning materials

Deep Learning and Combinatorial Optimization IPAM Workshop

This is a great workshop on the intersection of ML, RL, GNNs, and combinatorial optimization. This is a very hot topic of how you can solve hard combinatorial problems with machine learning tools and facilitate existing off-the-shelf solvers. Presentations are by the top experts in this field and discuss applications of ML to chip design, TSP, physics, integer programming, among others.

A Complete Beginner's Guide to G-Invariant Neural Networks

A tutorial by S. Chandra Mouli and Bruno Ribeiro about G-invariant neural networks, eigenvectors, invariant subspaces, transformation groups, Reynolds operator, and more. Soon, there should be more tutorials on the topic of invariance and linear algebra.

CS224W: Machine Learning with Graphs 2021

CS224W is one of the most popular graph courses by Jure Leskovec at Stanford. This year includes extra topics such as label propagation, scalability of GNNs, and graph nets for science and biology.

Paper Notes in Notion

Vitaly Kurin discovered a great format to track notes for the papers he reads. These are short and clean digestions of papers in the intersection of GNNs and RL and I would definitely recommend to look it up if you are studying the same papers.

Videos

Theoretical Foundations of Graph Neural Networks

Video presentation by Petar Veličković who covers design, history, and applications of GNNs. A lot of interesting concepts such as permutation invariance and equivariance discussed. Slides can be found here.

A Tale of Three Implicit Planners and the XLVIN agent

Another presentation by Petar Veličković about implicit planners, which could be seen as a middle-ground between model-based and model-free approaches for RL planning problems. The talk covers three popular implicit planners: VIN, ATreeC and XLVIN. All three focus on the recently popularised idea of algorithmically aligning to a planning algorithm, but with different realisations.

Video and slides of GNN User Group meeting

The first meeting of GNN user group talks about the usage and next release of DGL and featuring Le Song with combinatorial optimization talk. On the second meeting there is a discussion of new release of DGL, graph analytics on GPU, as well as new approaches for training GNNs, including those on disassortative graphs. Slides can be found in their slack channel.

Geometric deep learning, from Euclid to drug design

Michael Bronstein talks about the history of geometry, how it is now applied within deep learning for various applications for drug design, recepie creation, and image reconstruction.

That’s all for today. If you like the post, make sure to subscribe to my twitter and graph ML channel. If you want to support these newsletters there is a way to do this. See you next time.

Sergey

In this email, I will look into recent research that focuses on the performance of GNNs in two opposing settings, homophily and heterophily, and its connection to oversmoothing.

The term homophily in network science means that nodes of the same group or label tend to cluster together. The group here is defined informally and depending on its definition homophily may or may not arise in your network. So, for example, in a social network people that graduated from the same university tend to be connected together and the network is homophilous with respect to the university label.

Opposing homophily is the term heterophily when nodes of different groups tend to be connected, while the connectivity within the groups is sparse. For example, fraudsters in transaction networks are more likely to be connected to accomplices than to other fraudsters. In this case, fraudsters form heterophilic connections with the nodes of accomplices.

One of the popular ways to define homophily in a network is as a fraction of edges that connect nodes with the same label. This ratio h will be 0 when there is heterophily and 1 when there is homophily. In most real applications, graphs have this number somewhere in between, but broadly speaking the graphs with h < 0.5 are called disassortative graphs and with h > 0.5 are assortative graphs.

Why is it interesting? In my opinion, there is a mini paradigm shift in the GNN community that happened over the last year. This shift is associated with increasing evidence that popular message-passing networks such as GCN or GAT that aggregate messages locally do not work well with the disassortative graphs and new insights and architectures have been discovered to make it work. Let’s look at what happened.

How it all started

When we think of graph neural nets, arguably the most generic architecture we imagine is the message-passing neural net. This model takes a graph with node and edge features and then synchronously updates these node and edge features using neighborhoods of each node.

This architecture leaves us with many design choices that we have to make before applying it to real graphs. In particular, we need to decide how exactly the model updates the node and edge features, i.e. what functions do we need to apply to the input, how do we define the neighborhood for each node, and how do we aggregate the neighbors.

These choices led to hundreds of architectures, each claiming its SOTA on Cora datasets. For example, one of the first models of this kind, GCN, takes the sum of 1-hop neighbors’ embeddings multiplied by a learnable weight and normalized by the degree.

You can see that the neighborhood is just 1-hop neighbors, the aggregation function is the summation, and the transformation functions are linear projections into latent space.

And these models indeed show improvement on some datasets. For example, if you compare GCN with node2vec or MLP on Cora dataset you will get 10-30% increase in accuracy metric. That was a huge deal and sparked a lot of interest in studying graph neural nets. There were just two issues with that.

Back to the modern days

The first issue is a rather reputational one. With all the hype that deep learning has graph researchers also want to brag that we have deep graph neural nets that solve important real-world problems. But if you start increasing the number of layers in GCN, then surprisingly performance starts going down. Shortly after introducing GCN, Li et al. 2018 explained that vanilla message-passing nets essentially perform a Laplacian smoothing that may mix features of vertices from different clusters and make them indistinguishable. This problem was called oversmoothing and received hundreds of papers that tackle it.

The second problem is a practical one. In parallel, with new SOTAs on Cora datasets, there were other datasets where message-passing GNNs do not outperform simple baselines that sometimes ignore graph structure altogether. More recently Huang et al. 2021 showed that in high-homophily regimes label propagation with 0 parameters is capable to attain the same or better performance than complex GNNs with millions of parameters. What’s going on? 

My bet is that we still have not figured out the whole palette of applicability for GNNs, but there are recent results that show that those datasets where traditional message-passing networks do not work well are disassortative graphs, while Cora and co. are all assortative graphs. Moreover, it turned out that oversmoothing and heterophily are deeply linked and it’s possible to design GNNs that are both deep and perform well on the homophily and heterophily settings. Let’s see what happened.

Fixing the problems

A background idea of heterophily is that neighboring nodes can be of different classes and it’s not good for GNN to treat nodes in the neighborhood equally. Some models like GAT have an additional learnable weight per edge, but this weight is positive and rather plays a role of a balance that decides how much of a neighbor we need to put in the aggregation function. Instead, we need to redefine the whole notion of a neighborhood for a GNN, and here is how new architectures do it.

One way was proposed by Pei et al. 2020, where Geom-GCN architecture first embeds nodes in the latent space and then builds a new graph between embedded points. As such the neighborhoods are parameterized and redefined at each step. FAGCN of Bo et al. 2021 in turn takes the approach of GAT to learn the weight on each edge; however, they allow the weight to be negative as well. This can be seen as splitting the neighborhood into two: the positive and negative parts. One limitation of this is that the approach is tailor-made to the input graph and as such the model is transductive.

To fix this, Yan et al. 2021 proposed an inductive setting for GNNs that define + and - for each message in a differentiable style in their GGCN model. Moreover, they back up their model design by some theoretical explanation on how oversmoothing and homophily are related. In particular, they show that nodes with high heterophily or nodes with low heterophily and low degree cause oversmoothing problem by moving to the mean embedding of the opposite class. You can see from the image below how the performance of their model does not degrade, going up to 64 layers.

Finally, in addition to redefining the neighborhood per se, some hacks were proposed to change the way models aggregate the nodes. Zhu et al. 2020 offered 3 tricks in the H2GCN model: a concatenation of ego embedding with neighborhood one, using 2-hop neighborhoods, and combining all hidden layers into final representation. Another approach was inspired by ResNet by Chen et al. 2020 who proposed GCNII model that includes two more tricks: using residual connections to the initial representations and adding identity matrix to the weight matrix at each layer. These tricks were known before and could be applied to a wide range of message-passing networks but the authors prove their relevance to solving oversmoothing in disassortative graphs.

These new architectures were evaluated in a wide range of graphs, showing their applicability in heterophily settings. The problem of oversmoothing seems to be solved as well unless there are some other datasets where the proposed architectures degrade performance with more layers. Nonetheless, the global question of when to apply GNNs vs other (non)-graph models remains open.

That’s all for today. If you like the post, make sure to subscribe to my twitter and graph ML channel. If you want to support these newsletters there is a way to do this. See you next time.

Sergey

In this email, I will look into a particular line of research related to the question: can we say something about the performance of GNN on the test data?

There are two possibilities: the test data is close to the training set (interpolation or in-distribution generalization) or it is far outside of the training set (extrapolation or out-distribution generalization). In the context of graphs, to explain interpolation you can imagine that test graphs have a little bit different structure from the training set but the number of nodes and vertices is approximately the same. On the other hand, in the extrapolation test graphs can vary a lot from the training distribution, for example by having much larger sizes. So the question is for a given neural network can we say something about its generalization abilities?

Interpolation

To analyze the generalization of ML model, we assume that there is data distribution D and that our training set S is drawn from D. We can also define two errors: empirical error and generalization error. Empirical error for model f is the error that f makes on the training set S. On the other hand, generalization error is the expectation of the model’s error on points that are generated from D. The key difference between empirical and generalizations errors is that generalization error considers expected possible test set that can be generated from D, while empirical error considers only one, i.e. S.

Interpolation can be seen as an easy case of generalization because it implies that the data in the train set and test set do not differ much (i.e. support of their data generating distributions is identical). In this case, one can bound interpolation error as a sum of empirical error and some additive term. This additive term is what researchers are constantly trying to estimate and refine for a given family of models and data distributions.

One of the recent works by Liao et al. (ICLR 2021) proposes to use PAC-Bayesian analysis to derive a generalization bound for GCNs and message-passing GNNs. Their bounds (quite scary formulas) depend on the maximum degree of the graphs, the dimension of the hidden layer, and the norm of the learned weights. The smaller these quantities are, the smaller the generalization error is. This result is a tighter bound than of Garg et al. (ICML 2020) and Scarselli et al. (2018) which use Rademacher complexity and VC dimension of the GNNs.

A couple of results exist for particular types of GNNs. Verma & Zhang (KDD 2019) studies the question of how generalization bound of a single-layer GNN depends on the randomness of SGD algorithm. The result, however, is a very loose bound as it monotonically increases as the number of SGD iterations grows. Next, Du et al. (NeurIPS 2019) derives a data-dependent generalizaton bound for graph neural tangent kernel (GNTK), a particular type of GNN. This is in turn used to show that GNTK can learn certain input functions with polynomial number of samples.

Extrapolation

Extrapolation is generalization outside of the training distribution and so it’s naturally harder than interpolation. For example, Joshi et al. (2020) show that existing GNN architectures poorly generalize in combinatorial optimization problems such as TSP and it requires additional inductive biases. However, there has been some evidence that GNNs extrapolate well on some particular tasks such as learning dynamic programming algorithms (Veličković et al. (ICLR 2020), Xu et al. (ICLR 2020)), complex particle dynamics (Sanchez-Gonzalez et al. (ICML 2020)), and branching heuristics (Kurin et al. (NeurIPS 2020)). In all cases trained GNN could retain good performance for either bigger graphs, or longer time scales, or similar but different problems.

Some works attempted to study this phenomenon in a controlled environment. For example, Knyazev et al. (NeurIPS 2019) scrutinize generalization of attention-based GNNs through ad-hoc datasets and provide recipes for more powerful architectures. Wu et al. (ICLR 2021) propose a data generation process for theorem proving that tests GNN’s generalization from 6 different angles (with different number of axioms, short or longer proofs, etc.). This work shows that GNN-based solution can have smaller out-of-distribution generalization gap than transformer-based models.

Finally, a work by Xu et al. (ICLR 2021) theoretically studies extrapolation of MLP and GNNs. First, they show that MLPs with ReLU activation function extrapolate well only if the target function is linear and training data is “diverse” enough. Other activation functions such as tanh or cos extrapolate well when target function is similar to the activation one. This suggests that incorporating non-linearity to the activation function of GNNs (aggregation and readout) can learn a function with such non-linearity. For example, if you know that target function is some form of the maximum operator, using max aggregator helps in extrapolation. While for a general task target function can be unknown, for dynamic programming algorithms, for example, min/max operators are all over the place, so it’s worth making an architecture to align with that.

That’s all for today. If you like the post, make sure to subscribe to my twitter and graph ML channel. If you want to support these newsletters there is a way to do this. Until next time!

Sergey

First of all, Happy New Year 🧨With all the knowledge that we accumulated over 2020, let this year be more productive and predictable for you. Second, I moved the newsletter from revue to substack platform. There are several reasons for it: (a) it’s free for me to send these emails, which was not true before, becoming a noticeable financial burden; (b) it has more features (for example, I can do podcasts or engage with readers via threads); and (c) you can now support me with monthly payments if you wish.

As you probably know writing about graph ML (through the blog posts, telegram, and newsletter) has been my much-loved hobby, which I have been doing pro bono and now there is a way to support all of it via substack. In return, I offer additional perks such as promotions of your work or personal chats (more on this here), but as this format is new to me, I would be happy to hear more feedback on what you would like to see in the offer. It would also motivate me to write more frequently and advertise graph ML broader in AI community. All in all, I hope that if anything changes for the reader, it will be only for the better.

Subscribe now

Now about this issue. As we are entering 2021, there is much hype associated with GNNs. Legends of ML now speak loudly that it’s a very promising direction.

That’s exciting times for us, graph researchers, as we are getting the green light from our managers and colleagues to try these things out in the real world. It’s also bigger responsibility for us: so far we had comparatively fewer applications of GML than for example CV or NLP and in the end, the impact of our work will be measured by how much value it brings to society. So to start I outlined the top applications of GNNs in 2021, which I will elaborate on in this email. Furthermore, we will discuss the predictions of many researchers in this field of what will come out in the next years. And as always there are some special links, which could be relevant to you.

Interesting links

Blog post: Geometric ML becomes real in fundamental sciences Michael Bronstein nicely summarizes three papers that use graph ML for drug design and bioinformatics.

Course: Machine Learning for Graphs and Sequential Data (MLGS) Stephan Günnemann covers in-depth generative models, robustness, sequential data, clustering, label propagation, GNNs, and more.

Podcasts: TWIML with Taco Cohen and Michael Bronstein 1-hour discussions with two researchers on equivariance and state of graph ML field.

Book: The Atlas for the Aspiring Network Scientist More network science than ML book by Michele Coscia, covering hitting time matrix, Kronecker graph model, network measurement error, graph embedding techniques, and more.

Book: Probabilistic Machine Learning: An Introduction a general ML book by Kevin Patrick Murphy that has a chapter on graph embeddings co-authored with Bryan Perozzi.

Video: How to Predict Which Candidate COVID-19 mRNA Vaccines Are Stable with AI Kaggle grandmasters discuss how they use GNNs to win in the OpenVaccine Kaggle competition.

Video: Graph Neural Nets series Aleksa Gordić digests architectures of popular GNN models (GCN, GAT, GraphSage, etc.)

What 2021 holds for Graph ML?

In a new format, Michael Bronstein did mini-interviews with diverse researchers in this field about their predictions of where we are going. I was fortunate to participate and to express my feeling that GNNs will search for new ways to get through production infrastructure to make a real-world impact (more on this below).

One of the common themes raised by Will Hamilton is going beyond message-passing neural nets (MPNN) that has been dominating the field. Right now, most of the works assume static graphs that are given to us or as Thomas Kipf put it “the nodes and edges of the dataset are taken as the gold standard for the computation structure“.

There are indeed many assumptions we make when we claim SOTA results of GNNs. As Emanuele Rossi mentions, dynamic graphs, where nodes and edges are added and removed, have been largely understudied; or, graphs with homophily, which are very well suited for label propagation techniques than GNNs and we don’t have a good understanding why (mentioned by Petar Veličković and Matthias Fey); or, at the other extreme, when we don’t have graphs per se, how do we account for the relational structure (by Thomas Kipf).

Another frequent point is the use of graph ML to make a difference in the world. Sure, numbers in node classification benchmarks are important, but the underlying task is what we really care about. Novel approaches for protein modeling, new particle discoveries in physics, and medical imaging are among the current great candidates for such important tasks but discovering even more new forms that could be efficiently learned with the help of graphs (such as in AlphaFold 2) is what we hope to get in the nearest future.

Top Applications of Graph Neural Networks 2021

GNNs are a very popular topic right. I mean there are approximately ~300 new graph papers each month in ArXiv, of which about a third is related to GNNs. ICML/NeurIPS/ICLR have about 7% of all their papers related to graphs, data mining conferences such as KDD has ~30% graph papers. So it’s pretty big numbers in academia, but is it reflected in the industrial applications? In this post, I gathered the most noticeable recent GNN applications in small and big companies.

This includes the use of GNNs to embed users and products for recommendation and personalized search. I must add that large-scale recommender systems combine signals from different sources, including text, images, and sequential data, and GNNs are probably not enough. But if there is a strong relational signal for recommender systems GNNs are in the best position to capture it.

Another increasingly popular application is combinatorial optimization problems that are ubiquitous in manufacturing or logistics. This has been explored from two orthogonal perspectives: integrating it within existing solvers (e.g. Gasse-et al., 2019, Nair et al. 2020, the library Ecole) or doing end-to-end optimization from scratch (e.g. multiple surveys, Google’s presentation on chip manufacturing, a blog post by Chaitanya Joshi).

Next, if I bet for the most promising application of GNN I would say it’s going to be drug development and bioinformatics in general. There are already startups calling for graph ML researchers and developing GNN platforms, and this industry arguably perfectly fits in the world of graphs.

There is more in the post, but in the end, I hope that my list is not an ultimate one and in a year we will see many more valuable applications of GNNs; at least we need to strive to influence the world with our research work. After all, the world is connected and there is always a place for some graph.

That’s all for today folks, I hope you enjoyed it. As always if you have some feedback or have some topics to share, feel free to reply to this email. Subscribe to me on Twitter or Telegram. And more than anything else take care.

Peace!

Sergey

“Knowledge is like money: To be of value it must circulate, and in circulating it can increase in quantity and, hopefully, in value.”

Welcome!

NeurIPS 2020 is over 👏, ICLR 2021 finished the rebuttal 👓, and Christmas ⛄ is around the corner, what a great time to relax and look back at the achievements of this year. Today, we will look back at what we achieved during 2020 and compare it against the predictions I made in January. We will also look at the graph works at NeurIPS 2020 and ICLR 2021. And as always share a few links that can be worth to you, aficionado of graphs 💣.

Trends of 2020

One of the first posts I made this year was on the trends of GML. I spent a couple of months reading graph submissions to ICLR 2020 and it kind of paid off: more than 7.5K people read it. Here are the four trends I outlined in the beginning of this year.

1. More solid theoretical understanding of GNN;

2. New cool applications of GNN;

3. Knowledge graphs become more popular;

4. New frameworks for graph embeddings.

Let’s deep dive at each of those. Theoretical understanding of GNNs was indeed a huge topic this year 📈. There are works on universal approximation, equivariant networks, expressive power, generalization, convergence, oversmoothing, and many other aspects. Are we done? I’m pretty sure there will be much more works on the theory of GNNs. The topic is growing and we still have many open questions remaining (for example, studying the power of non-message-passing networks on graphs).

I have a mixed feeling about the trend of new cool applications of GNN 👩‍🔬. People indeed published a lot of papers about how graph networks can be applied to various problems. The molecular design drew a lot of attention with several recent surveys, competitions, and datasets. There are numerous works for writing better software, traffic forecasting, computer vision. I personally liked the application of GNNs to structural design by AutoDesk. However, there is little adoption of GNNs in the industry, at least to my knowledge. Those companies that I know usually have graphs as some small subsystem for their production (although it could have some serious impact) and what’s lacking, in my opinion, is the availability of industry-level datasets (scale and nature) as well as frameworks to put GNNs into production. I hope that’s something we will see in the near future.

Research on knowledge graphs also pleased us with significant milestones. Query2box, a technique for answering logical queries, inspired more a big wave 🌊 of research on logical reasoning without ontologies such as BetaE and EmQL. Several challenging KG datasets have been released, where traditional models such as transformers and MPNN achieve very low accuracy. Google’s researchers presented a large and realistic natural language question-answering dataset CFQ, where a question should be correctly transformed into a complex logical query. Then GraphLog is a multi-purpose, multi-relational graph dataset built using rules grounded in first-order logic. Moreover, Open Graph Benchmark includes two KGs which would inspire more tasks and submissions in this area. Finally, KGs have become a must-have part for language models, now enriched with entities from wikidata and showing superior results in several NLP problems. Clearly KGs constitute a significant part of obtaining knowledge about this world so they won’t go away any time soon.

Finally, 2020 proposed some new approaches for embedding a graph. LouvainNE and InstantEmbedding are two competing approaches to get node embeddings extremely fast 🏎, which were evaluated in graphs with billions of edges. GraphZoom is a general framework that can incorporate any unsupervised embedding model and improve accuracy through a multi-scale approach. Personally, I think the field of unsupervised embedding is slowly moving from research to production settings, which is a great indication that graph methods are useful. So in the future, I would rather expect more research on supervised embedding methods.

NeurIPS 2020

How did you feel about NeurIPS? I think gather town 🏙 really saved communication in this conference, poster sessions felt real (except for occasional bugs), no more zoom connections for every single poster. As expected with about ~2K papers it was a bit overwhelming to search for the right material: just scrolling down the papers for a poster session already felt like a laborious task, not to say 3️⃣-hour tutorial sessions. Luckily, if you are interested in graphs, there is just the right amount of research to consume for everybody.

1. If you want to learn how graphs are used at Google, look no further, there is a great tutorial by Bryan Perozzi and the gang. To see a complete schedule with the links to the video, check out this page.

2. If you want to learn novel ideas, that’s what workshops are for and there are several related to graphs. Topological Data Analysis and Beyond, Differential Geometry meets Deep Learning, Learning Meets Combinatorial Algorithms (LMCA), Machine Learning for Molecules is all you need to see where the field is going.

3. And of course, there are more than 120 full papers related to graphs. Around 6.5% of all accepted papers – that’s huge! If you want to have a sneak peek at some of them check out this curated list.

ICLR 2021

ICLR is one of the top conferences in ML 🧠, gaining more popularity each year due to the novel review process when anyone can see the reviews for any of the submitted paper. This allows one to analyze all sorts of statistics about the quality of papers and the reviews. So I open-sourced the list of all submissions together with their final scores and calculated a few stats about this year. So what do we have?

1. There are more than 2600 submissions this year, which is approximately the same as last year. With the acceptance rate of 25% there would be 650+ accepted papers. There are about 210 graph-related papers, which again makes it a very hot topic.

2. Here is a list of graph-related papers, 59 of which have an average score >= 6️⃣. What’s cool is the top-1 submission across all submissions is the one related to the generalization abilities of GNNs.

3. You may wonder how your rebuttal affects your scores? Do reviewers tend to change their scores? If yes, by how much? So the definite answer is that about 50% of the papers get at least one of the score changes. There are some rare exceptions when all 4 scores changed after the rebuttal. On average, average score jumped by 0.25 after rebuttal for all papers. The majority of the score changes are +1 or +2, but there are again some exceptions when the scores changed by -5 or +5. So overall it seems that it’s worth being engaged in the discussion with the reviewers as it is very likely to change your scores.

Videos

Geometric Deep Learning: Successes, Challenges, Next Steps by Michael Bronstein. Michael is talking about deriving convolution from the first principles, first GNN models, the expressivity of GNNs, and the future applications of the field. Very inspiring.

Recent Developments of Graph Network Architectures by Xavier Bresson. A must-watch presentation that nicely summarizes exciting topics such as graph isomorphism, WL tests, equivariance, universal approximations, positional encodings, and more.

Graph Neural Networks Channel by Zak Jost, covering some aspects of GNNs, including an interview with DeepMind authors for using GNNs for physics.

Blog posts

Erdős goes neural: unsupervised learning of combinatorial algorithms with neural networks by Andreas Loukas. He talks about their NeurIPS work that proposes a differentiable way to solve CO problems with unsupervised GNNs.

Knowledge Graphs @ EMNLP'20 and NeurIPS'20 by Michael Galkin. Michael continues his journey to the fascinating world of facts represented by graphs and how can we extract value out of it.

Undergraduate Math Student Pushes Frontier of Graph Theory by QuantaMagazine about a 21-year-old who improved results of Erdős and Szekeres on the upper bound for two-color Ramsey numbers.

That’s all folks 👦. As always share a word 🗣 among your friends and colleagues if you liked this issue. Also, if you have something to share 📤 with the community such as blog posts or videos, please reply to this issue! Happy Christmas 🎄 and New Year’s Eve 🤶! Peace!

Welcome to the 4th issue of GML newsletter!

This issue I decided to devote to the upcoming NeurIPS 2020 (6-12 December), covering what authors and organizations publish the most at the conference and some of the popular topics among graph papers.

🥁🥁🥁

Part1. Who publishes at NeurIPS?

Before diving into graph papers let’s first take a look at NeurIPS 2020 analysis I made about authors, affiliations, countries, and collaborations.

Number of papers. This year the exponential trend of the number of submissions and accepted papers continued for the 6th year in a row and reviewers got almost 9.5K papers (40% increase over the last year). If this trend continues there will be 50K submissions in 2025 🤪 Sounds absurd, but hey, I bet you could not believe the 10K number 5 years ago.

One of the complaints people discussed is that the acceptance rate remains suspiciously constant as if the quality of papers haven’t changed over time. While I agree it would be great to merit papers primarily based on their quality rather than a predefined number, I’m not sure how to cope with the increasing load of the papers one conference can maintain.

Top affiliations. Nothing surprising here, Google champions the ranking with a significant lead over Stanford (2nd) and MIT (3rd). This trio preserved its place from ICML 2020, showing consistent research efforts at top venues. What’s more interesting is the first time China’s affiliation made to the top-10 list, with Tsinghua University in 7th place. We have heard many times that China steps on the heels of the UK and it’s just one of the illustrations of it (more next).

Top authors. For some reason, NeurIPS also has many more authors with many publications than at ICML or other venues. There are 28 authors with 7+ papers at NeurIPS (vs 9 at ICML). Traditionally Sergey Levine (UC Berkeley) leads with 12 papers.

I don’t have a good answer why people write more papers for NeurIPS rather than ICML, but this year it’s incredible how many papers top authors published: the first 10 authors published 83 papers in total. There are discussions that we should not encourage scientists and the whole research ecosystem to publish that many papers, favoring quality over quantity. While I agree with the last statement, based on the number of submissions I believe that the quality of papers increased on average over time and it’s rather a problem of searching the gems in a large space of publications.

Top countries. The USA is just far ahead of other countries, no questions about it. China for the first time overtakes 2nd place of the UK, with several industrial companies (Tencent, Alibaba, Huawei) contributing significantly to the country’s performance. Some small countries such as Israel, South Korea, and Singapore published more than such behemoths as Russia, India, and Australia. A single university in Saudi Arabia, KAUST, published all 10 papers of the country.

Collaboration. Some companies collaborate more than others (and as far as I’m concerned there are internal policies to encourage people to collaborate inside the affiliation rather than with external people). For example, Google tends not to publish their papers with other industrial companies (except DeepMind), while MIT has collaborations with both industry and academia across the world.

Part 1 conclusion. My conclusion is that NeurIPS is not slowing down in terms of the number of papers and I’m looking forward to seeing the length of the queue to a registration desk when people get back to real conferences in a year or two (hopefully). Top authors now publish even more: if it’s the rich get richer phenomenon or they just accumulated their rejected papers from the previous years, I don’t know – but again I would not be surprised to see someone to publish 25 papers at a single conference in 5 years from now (what now accounts for all publications of India).

Part 2. Graph topics at NeurIPS 2020.

About 7% of all papers at NeurIPS 2020 are using graph machine learning in one part or another. Proceedings with all papers are available here and graph papers are available here. Scientists use graphs for many purposes and hence the papers are covering a broad spectrum of topics, from theoretical machine learning to practical improvements of a particular GNN model. Next is just a glimpse of some topics.

Theory. Several works study the limitations of existing GNNs in terms of their ability to distinguish non-isomorphic graphs. Chen et al. show that many GNNs are not capable of learning induced subgraphs such as triangles. Andreas Loukas introduces a measure of communication capacity and shows that it needs to grow quadratically with the number of nodes in order to distinguish non-isomorphic connected graphs. Morris et al. propose a scalable version of WL algorithm and show that it’s strictly more powerful than the original WL.

Oversmoothing. For those who don’t know oversmoothing is the problem that GNN with many layers tend to have similar embeddings across all nodes which leads to poor performance and as we work in the paradigm of deep learning we want to tackle this problem by all means. As such Zhou et al. proposes to use community structure and Min et al. to use scattering transforms when designing aggregation schemes for GNN. Oono and Suzuki further analyze the problem through the lens of gradient boosting.

Adversarial attacks. Similar to adversarial settings in computer vision, this topic covers the mechanisms of attack and defense of node prediction models. Ma et al. describes a new type of node attack, when the attacker only has access to a small subgraph, while Zhang and Zitnik propose GNNGuard – a model-agnostic way that defends against adversaries by increasing the weights on similar nodes and decreasing it on unrelated nodes during the aggregation.

Faster GNN. This year improved a bit in terms of the sizes of graph datasets that we have access to, which reflects the scale of industrial applications and several methods were proposed to improve the efficiency of standard GNN models. Chen et al. GNN model has a sublinear time complexity for preprocessing and training and can scale to billions of edges. Ramezani et al. propose a generic augmentation of sampling techniques when sampling is performed rarely and reused for next iterations.

Explainability. Explaining the predictions of neural network models on graphs should include the explanation at the feature level (which features are important) and at the topology level (which links are important). Unlike previous approaches that usually offer a single explanation of predictions for each node, Luo et al. train a NN to provide multi-instance explanations in an inductive manner. Orthogonally, Vu and Thai use a graphical model to show the dependencies of explained features in form of conditional probabilities.

Computer Vision. Using graphs to represent objects in an image, video, or 3D point clouds is one of the popular applications for GML. Bear et al. propose to build a hierarchical graph of objects in an image and show that it can better segment an image into a scene than past approaches. Zhou et al. leverage the graph structure of the low-resolution image to recover detailed textures of the image and retrieve a super-resolution image.

Novel applications. Predicting the properties of molecules has been one of the most promising applications of GNNs in the real world. Rong et al. pretrain a GNN model with 100M parameters trained on a huge unlabeled molecular dataset achieving significant improvement over past approaches. Several works apply GNNs for software programs. Zhou et al. use GNN as an encoder of the program for a deep RL algorithm that optimizes the computational graph of the program. In another work, Huang et al. exploit inductive biases of GNN for assembling parts of the furniture by predicting translation and rotation for each input part.

Physics. More and more works now use GNN models to predict how elementary particles interact with each other. Cranmer et al. demonstrate exciting results of discovering unknown equations that govern the concentration of dark matter. For this, GNN’s messages on edges and node outputs are provided to an additional genetic algorithm that iteratively searches for an underlying equation that explains data well. Schoenholz and Cubuk present JAX MD for performing molecular dynamics in JAX, a NumPy-like package with autograd, purely in python. The models are accelerated on GPU with end-to-end training and can be suitable for graphs with up to hundreds of thousands of particles.

Part 2 conclusion. I just scratched the surface and there are many other interesting and impactful papers and you should check out the whole list of papers if you want to deep dive into graph research. There is still 1 month before the conference takes place 😊

That’s all for today. Thanks for reading!

Feedback 💬 As always if you have something to say, feel free to reply to this email. Likewise, contribute 💪to the future newsletter by sending me relevant content. Subscribe to my telegram channel about graph machine learning, Medium and twitter. And spread the word among your friends by emailing this letter or by tweeting about it 🐦

Welcome to the 3rd issue of GML newsletter!

I hope your papers got accepted to NeurIPS and submitted to ICLR, so that you can take a cup of coffee ☕ and enjoy the latest updates in the field of GML.

In today’s email, you will see the next big bets for GNNs and learn how you can create a graph with neural networks. You will also find new ongoing courses that study GNNs or watch a couple of videos about many applications of graphs and prepare for the next graph ML events 🌟.

Let’s go!

Blog posts

Going Big in Particle Discovery

The CMS detector at the Large Hadron Collider takes billions of images of high-energy collisions every second to search for evidence of new particles. Graph neural networks expeditiously decide which of these data to keep for further analysis. Photo: CERN

We have already seen GNNs being applied to complex physics, autonomous driving, and drug design, but the US-based physics lab Fermilab in a new blog post discusses probably the biggest application of GNNs: to discover new particles in the data from the Large Hadron Collider (LHC) 💥. The goal is to analyze relationships between pixels in a large number of images in order to decide whether to keep an image for processing later. They hope to have GNNs functional by the time the third run of the LHC in 2021.

Manifold Learning 2.0

Previous approach of first embedding a graph and then applying ML model is now replaced with end-to-end GNN training.

One of the hot topics this year is the construction of a graph from unstructured data (e.g. 3d points or images). In a new post, Michael Bronstein asks how can we meaningfully create a graph from unstructured data (e.g. 3d points or images 📷) and suggests that using GNNs both to learn the structure of the graph and to solve the downstream tasks (e.g. in DGM) can be a better alternative than a de-coupled approach (e.g. DGCNN).

GNNs are on the Maps

Researchers at DeepMind have partnered with the Google Maps team to improve the accuracy of real time ETAs by using GNNs.

DeepMind for Google released a blog post on how you can apply GNNs to predict traffic for Google Maps 🗺. While there are not many exact details about the models they used, a few interesting can be found such as (i) using sampling strategies for training, (ii) using RL to select which subgraph should go to each batch, and (iii) using parametric learning rate for training.

What’s in the menu today?

Food preparation as a computational graph with cooking transformations modeled as edges, and optimize it by choosing such operations that preserve in the best way the anti-cancer molecular composition.

Michael Bronstein, Kirill Veselkov, and Gabriella Sbordone present an idea of hyperfood 🥗 – the food that contains thousands of bioactive molecules, some of which are similar to anti-cancer drugs. In their journal paper at Nature Scientific Reports they apply a learnable diffusion process to hunt for anti-cancer molecules in food using protein-protein and drug-protein interaction graphs. Soon they hope to apply graph ML to generate recipes that strike the optimal balance between health, taste, and maybe even aesthetics.

Videos

Graph ML at Data Fest 2020

Videos of Graph ML from Data Fest 2020, a data science conference, are open now 🔑. This year speakers from the industry and academy talked about kNN search on graphs, graphical models, unsupervised embeddings, knowledge graphs, graph visualization, and many other exciting directions of graphs.

3DGV Seminar

3DGV Seminar is a weekly lecture on 3D Geometry 💠and Vision. One of the seminars was presented by Michael Bronstein who was talking about inductive biases on graphs, the history of GNN architectures, and several successful applications.

Can you trust your GNN?

Stephan Günnemann as a keynote at ECML-PKDD gave a presentation about robustness for SOTA graph-based learning techniques, highlighting the unique challenges and opportunities 💸 that come along with the graph setting.

Courses

GNN course at UPenn

In addition to cs224w at Stanford and COMP 766 at McGill (both should happen next semester), there is an ongoing course on Graph Neural Networks at the University of Pennsylvania 🦔 by Alejandro Ribeiro, who worked on graph ML and graph signal processing. The course covered so far permutation equivariance, graph convolutional filters, empirical risk minimization, and graph neural networks.

NYC Deep Learning course

Deep Learning course at NYC 🗽 instructed by Yann LeCun and Alfredo Canziani have two final lectures on graph convolutional networks (by Xavier Bresson) and deep learning for structured predictions. It covers spectral convolutions, energy-based factor graphs, and graph transformer networks. In addition to lectures, there are also practical sessions and exercises.

Events

CIKM 2020

A conference on information and knowledge management (CIKM) will happen 19-23 October online with a number of research and applied papers, tutorials and workshops about graph neural networks, knowledge graphs, and general algorithms 🔢.

That’s all for today. Thanks for reading!

Feedback 💬 As always if you have something to say about this issue, feel free to reply to this email. Likewise, contribute 💪to the future newsletter by sending me relevant content. Subscribe to my telegram channel about GML, Medium and twitter. And spread the word among your friends by emailing this letter or by tweeting about it 🐦

Welcome to the 2nd issue of GML newsletter!

The summer is over 🌄 and it’s time to get back to school 🏫 (or to self-study with this newsletter).

In today’s email you will gain some intuition of graph Laplacians and learn about new ways to scale your graph neural networks. You can also watch videos by top researchers from summer schools or read the digests of the past conferences and different workshops. And finally, you can register for cool upcoming events that will be valuable for graph researchers.

Let’s go!

Blog posts

A seemingly simple question “What does a graph Laplacian represent❓” was recently raised in mathoverflow, leading to a pool of good explanations and blog posts, including László Lovász’s link to random walks, Muni Pydi’s step-by-step procedure to derive graph Laplacian, as well as David Childers’s interpretation of the graph Laplacian from the perspectives of functional analysis, probability, statistics, differential equations, and topology.

A graph function over the vertices of the Peterson graph.

Michael Bronstein continues a marathon 🏃‍♀️ of great blog posts on GML. In a new post, he describes their recent work on scaling GNNs to large networks, with introduction to sampling-based methods (e.g. SAGE, GraphSAINT, ClusterGCN), which smartly sample a subgraph for each batch of the training. Then, he describes that it can be beneficial to precompute r-hop matrices, A^r X, and use MLP on these features. The algorithm is already available in pytorch-geometric.

SIGN architecture. The key to its efficiency is the pre-computation of the diffused features (marked in red).

Pennylane, a python library for a quantum machine developed at Xanadu, now has an example of quantum graph recurrent neural networks (QGRNN), which are the quantum analogue 👩‍🔬 of a classical graph recurrent neural network, and a subclass of the more general quantum graph neural network (QGNN). Both the QGNN and QGRNN were introduced in the paper (2019) by Google X.

A visual representation of one execution of the QGRNN for one piece of quantum data.

Last but not the least, Bastian Rieck made a post on topological data analysis papers at ICML 2020 that includes graph filtration techniques, topological autoencoders, and normalizing flows.

Videos

With the target to bring the best ML/AI environments closer to Indonesia 🌏, Machine Learning Summer School - Indonesia gathered top researchers to talk about latest advancements in ML. Among others Daniel Worrall spoke about equivariance and inductive biases (slides are here), diving into group theory and convolutions, while Max Welling touched on graphical models and graph neural networks, describing difficulties of applying convolutions in manifolds and curved spaces. Check out the full schedule here.

Petar Veličković also made a presentation about their recent work Principal Neighbourhood Aggregation for Graph Nets that extend theoretical framework (initiated by the GIN paper) to continuous features that appear frequently in the real world 🌐. One of the messages is that we may need to go beyond just sum aggregators of neighborhoods, to min/max and normalized moments aggregations.

Aggregations that are injective (black) and non-injective (orange) for top-bottom graph pairs.

Events

August was rich 💰 in the events that are relevant to our community. In addition to MLSS-Indo described above, there were KDD conference, many graph-related workshops, and JuliaCon. Let’s have a sneak peek at those.

• Papers related to graphs made around 30% of all accepted papers at KDD 2020. Among those, the most frequent theme is the development of new graph neural network models for various practical applications (e.g. molecule prediction 🧪 or recommender systems). Another topic that occurred several times is how to tackle the computational complexity of GNN models (e.g. via PageRank, minimal variance sampling, big, small, and redundancy-free models). And other papers solve various topics in graph mining such as clustering, drawing, summarization. For more highlights of KDD 2020, you can check my recent post.

Graphs and recommendations are traditionally two big topics at KDD.

• Of particular importance to GML community are the workshops that are usually the best place to meet like-minded colleagues 🎓 to discuss the latest problems that they are working on. MLG workshop had a great line-up of speakers talking about applications of GNNs to algorithmic reasoning, cybersecurity, healthcare and other important topics (videos can be found here). Mining Knowledge Graph workshop and Knowledge Graphs and E-commerce workshop in turn had a number of keynotes speaking of applications of KG to medical, biological, and consumer domains.

• Israeli Geometric Deep Learning workshop gathered many great researchers who spoke about recent works on deep learning on non-Euclidean domains such as sets, graphs, point clouds, surfaces and their applications to computer vision 👀, graphics, 3D modeling, etc. The video of the workshop is available online.

• While Python 🐍 is a default language for analyzing graphs, there are numerous other languages that provide packages for dealing with graphs. In the recent JuliaCon, devoted to a programming language Julia, many talks were about new graph packages with applications to transportation networks, dynamical systems, geometric deep learning, knowledge graphs, and others.

Books

With the difference of one day 2 (!) books 📚 were announced.

• Graph Representation Learning book by Will Hamilton, which so far has 3 main chapters on node embeddings, GNNs, and generative models.

• Deep Learning on Graphs book by Yao Ma and Jiliang Tang. This should be available this month and should focus on the foundations of GNNs as well as applications.

Upcoming events

Make sure to register for those in advance.

• The 28th International Symposium on Graph Drawing and Network Visualization will be held online from Sep. 16 to 18, free of charge. This venue will have many insightful talks about new techniques for visualizing graphs 🎨.

• Data Fest by Open Data Science is a recurring data science conference, organized by Russian-speaking community. This year (19-20 Sep.) the conference will be global, free of charge, and fully-online. Unlike other academic conferences, Data Fest has a mix of researchers, practitioners, and industry leaders 👨‍🏫. I organize a section on Graph ML and we have 10 great speakers who will talk about embeddings, knowledge graphs, nearest neighbors search, and many other exciting areas. So feel free to register and tune in.

That’s all for today. Thanks for reading!

Feedback 💬 As always if you have something to say about this issue, feel free to reply to this email. Likewise, contribute 💪to the future newsletter by sending me relevant content. Subscribe to my telegram channel about GML, Medium and twitter. And spread the word among your friends by emailing this letter or by tweeting about it 🐦

Welcome!

Three years ago Sebastian Ruder started his NLP newsletter with the words that “NLP is seeing increasing interest recently”. Today NLP is at the peak 🗻 of its popularity, featured across all major media sources.

I hope that Graph Machine Learning (which I abbreviate as GML) is in the same state as NLP was three years ago. Indeed, the number of GML papers posted on ArXiv CS section is more 300 each month (!) and all major conferences have a decent portion of papers in the intersection of graphs and machine learning.

The goal for this newsletter is quite simple: I want people to know more about recent breakthroughs, current trends, and future events in GML. I already post daily in telegram about GML and this newsletter can be considered as a less frequent, more condensed version of what I run there. Besides, I make blog posts on Medium and tweet on twitter (feel free to follow).

This email is about how can we design theoretically better GNN models and what stands in the way of deep GNN. You can also find digests of recent conferences that were rich on graph-related topics and many releases and updates of GML libraries that will make your life easier🧙‍♂️.

Let’s go!

Blog posts

In a series of blog posts, Michael Bronstein touches several important points regarding the developments of new Graph Neural Networks (GNN). One is the fact that most of the current approaches to study the expressive power of GNN was on the comparison of GNN against its algorithmic counterpart, Weisfeiler-Lehman (WL) algorithm. However, this is not necessarily the most useful comparison as it ignores the case when the two graphs are similar but not isomorphic.

Instead of asking GNN to distinguish graphs by isomorphism testing, a more general way to compare expressive power of GNNs is by probably approximate isometry: 𝖯( c⁻¹ d(G,G′)−ε ≤ |f(G)−f(G′)| ≤ c d(G,G′) )>1−δ

Another question that he raises is why deep GNNs are not the thing for GML to the same extent as deep CNNs are for CV. There is a profound reason for that, termed over-smoothing, that makes node embeddings indistinguishable from each other with the growth of the number of layers. There are ways to overcome it by different means such as regularization; yet, it still does not show any significant improvement in real-world settings. As outlined, we may just miss proper data sets where the target labels strongly depend on higher-order graph structures.

While there are ways to "fix" performance of typical GNNs with more layers, the overall deep GNN models do not bring significant advantage yet.

You can find more interesting posts by Michael Bronstein on this page.

Finally, if you are a little bit rusty or just started studying graphs check out this quick and intuitive post on centrality measures by Anas Ait Aomar.

Podcasts

In a recent TWIML podcast 🎧 Michael Bronstein compared his views on the field 2 years ago vs today: fast evolution with the appearance of software/hardware/datasets; the difference between academic and industrial research; his recent papers as well as his vision of the field for the next 5 years.

Conferences

Several big events recently took place that presented the latest advancements of the field from different perspectives.

• One of the top 🔝 conferences ICML has a variety of GML papers ranging from structural design 👷‍♂️ to linear solvers to particle dynamics. Besides the main track at ICML there were two relevant graph workshops, GRL+ (more on it below) and Bridge Between Perception and Reasoning (videos are here), each featuring novel perspectives on how graphs capture different aspects of reality.

• Graph Representation Learning and Beyond (GRL➕) workshop at ICML is a venue for researchers to discuss cutting-edge ideas and perspectives of GML. Current trends in GML include topics such as emerging work on performance/scalability, stronger KG embeddings, a proposal of many datasets/benchmarks/libraries, and applications to computational chemistry and algorithmic reasoning. Besides, Petar Veličković (one of the organizers) mentions explicit consideration of structure for GNN as the main standout, not only in the papers but also in most of the invited talks. Videos are here.

• Another top conference ACL in NLP ✍ also had a solid record of papers with a graph in its title (in total around 50 papers (8% of total)). Knowledge graphs play a big role in several applications such as chatbots and as Michael Galkin put it in a blog post the main theme of this year was discovering that knowledge graphs demonstrate better capabilities to reveal higher-order interdependencies in otherwise unstructured data.

• Automated Knowledge Base Construction (AKBC) conference had its second edition (previously held as part of bigger conferences). In total 29 papers present research on extracting entities and relationships in various sources of data (text, images, video, etc.) and then using it to deliver insights to the users 🙌. You can find the videos on YouTube as well as highlights of AKBC 2020 from Daniel Daza, which features papers on embedding complex queries, inductive representation learning in KGs, and KGs for information extraction.

In August there will be another big conference KDD with a line-up of great papers and 4 (!) workshops (1, 2, 3, 4) on GML. I encourage someone to spend some time digesting and writing a blog post about GML works at KDD (which I will feature in the next email) 🙏.

Software

There are some major updates on software libraries 👩‍💻. PyTorch-Geometric released version 1.6.0 with several improvements for scalability such as support for mini-batch training, memory-efficient graph storage SparseTensor, and conversion to TorchScript programs. For more check out this video by Matthias Fey.

Another popular library DGL aims to provide software that offers flexibility for different real-world domains such as knowledge graphs, chemistry and biology, CV and NLP, as well as prod-ready distributed training. More details can be found in this video by Zheng Zhang.

Besides these big 2️⃣, there were numerous new libraries that serve specific needs of using graph models. Geo2DR is GPU-ready library for unsupervised learning on graph embeddings through substructure decomposition. Spektral is a library for graph deep learning, based on the Keras API and TensorFlow 2. Graphein is a library for constructing graph and surface-mesh representations of protein structures for computational analysis. Geoopt is a PyTorch add-on that allows you to perform Riemannian optimization for neural network models. PyKEEN is a python package designed to train and evaluate knowledge graph embedding models. Additionally, several graph data sets have been updated and formalized: Wiki-CS, OGB, TUDataset.

That’s it folks for today.

Feedback 💬 If you have some opinion how to improve this issue, feel free to reply to this email. Likewise, contribute 💪to the future newsletter if you have content that can be relevant to the community. And please spread the word among your friends by emailing this letter or by tweeting about it 🐦