Fresh Picks from Arxiv
(A quick one as things are very busy lately!)

- Theory of Graph Neural Networks: Representation and Learning ft. Stefanie Jegelka.
- LiftPool: Lifting-based Graph Pooling for Hierarchical Graph Representation Learning
- PyGOD: A Python Library for Graph Outlier Detection
- Reinforced Causal Explainer for Graph Neural Networks
- Graph Neural Network based Agent in Google Research Football
- GUARD: Graph Universal Adversarial Defense
- DropMessage: Unifying Random Dropping for Graph Neural Networks
- Effects of Graph Convolutions in Deep Networks
- LEARNING HEURISTICS FOR A* ft. Petar Velickovic.
- AZ-whiteness test: a test for uncorrelated noise on spatio-temporal graphs

(If I forgot to mention your paper, please shoot me a message and I will update the post.)

Knowledge Graph Conference 2022

The premier venue on industrial applications of KGs starts on Monday to last the whole week of May 2-6th! KGC 2022 collected a stellar line-up of speakers including Jure Leskovec (Stanford), Ora Lassila (AWS), Bryan Perozzi (Google), Yu Liu (Meta) as well as talks from all the big companies who use KGs on a daily basis in their products like LinkedIn, Meta, Microsoft, Netflix, Nvidia, Pinterest, and, of course, the majority of graph database vendors like Stardog, neo4j, Ontotext, TigerGraph, Franz. The conference takes place physically in NYC but you could join remotely in a hybrid fashion either.

​​GNNs + ⚽ = 🏆

The NeurIPS deadline has passed and we are back to posting!

If you thought that sophisticated GNNs for modelling trajectories are only used for molecular dynamics and arcane quantum simulations, fear not! Here is a cool practical application with a very high potential outreach: Graph Imputer by DeepMind and FC Liverpool (YNWA and checkmate, Man City) predicts trajectories of football players (and the ball).

The graph consists of 23 nodes, gets updated with a standard message passing encoder and a special time-dependent LSTM. The dataset is quite novel, too - it consists of 105 English Premier League matches (avg 90 min each), all players and the ball were tracked at 25 fps, and the resulting training trajectory sequences encode about 9.6 seconds of gameplay.

The paper is easy to read and has numerous football illustrations, check it out! Sports tech is actively growing those days, and football analysts now could go even deeper in studying their competitors. Will EPL clubs compete for GNN and Graph ML researchers in the upcoming transfer windows? Time to create our own transfermarkt? 😉

​​Denoising Diffusion Is All You Need

The breakthrough on Denoising Diffusion Probabilistic Models (DDPM) happened about 2 years ago. Since then, we observe dramatic improvement in generation tasks: GLIDE, DALL-E 2, and recent Imagen for images, Diffusion-LM in language modeling, diffusion for video sequences, and even diffusion for reinforcement learning.

Diffusion might be the biggest trend in GraphML in 2022 - particularly when applied to drug discovery, molecules and conformers generation, and quantum chemistry in general. Often, they are paired with the latest advancements in equivariant GNNs. Recent cool works that you’d want to take a look at include:

- Equivariant Diffusion for Molecule Generation in 3D (Hoogeboom et al, ICML 2022)
- Generative Coarse-Graining of Molecular Conformations (Wang et al, ICML 2022)
- GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation (Xu et al, ICLR 2022)
- Torsional Diffusion for Molecular Conformer Generation (Jing and Corso et al, 2022)

Where to learn more about DDPMs and its (quite advanced) mathematics? Luckily, there is a good bunch of new educational blog posts with step-by-step illustrations of the diffusion process and its implementation - try it!

- The Annotated Diffusion Model by Niels Rogge and Kashif Rasul (HuggingFace)
- Improving Diffusion Models as an Alternative To GANs by Arash Vahdat and Karsten Kreis (NVIDIA)
- What are Diffusion Models by Lilian Weng (OpenAI)

Workshop on Mining and Learning with Graphs @ ECML / PKDD 2022

The MLG workshop is co-located with ECML PKDD 2022 and will take place in Grenoble (France) on Sept. 23 (physical venue 🎉). Keynote speakers will be Soledad Villar (Johns Hopkins University) and Nils Kriege (Univesity of Vienna). You can submit pretty much anything related to learning or data mining with and on graphs. Also, previous works (aka "lessons learnt") and early idea papers are very much welcome.

The deadline is June 20th - a perfect case to finish up that project you wanted to submit for NeurIPS but ran a little bit late 😉

A new computational fabric for Graph Neural Networks

“Graph Neural Networks (GNNs) typically align their computation graph with the structure of the input graph. But are graphs the right computational fabric for GNNs? A recent line of papers challenges this assumption by replacing graphs with more general objects coming from the field of algebraic topology, which offer multiple theoretical and computational advantages.”

A new Medium post by Michael Bronstein, Cristian Bodnar, and Fabrizio Frasca

tl;dr: The new Learning on Graphs Conference (LoG) is looking for more reviewers! We have a special emphasis on review quality via high monetary rewards, a more focused conference topic, and low reviewer load (max 3 papers). But for this we need your help! Sign up here: https://forms.gle/QFQmCSRN3zwFw9hz9

-----

LoG will take place virtually from 9 - 12 December 2022 and covers papers broadly related to graphs and geometry, as described in our Call for Papers: https://logconference.org/. Here are a few (tentative) details of the reviewing process:

Reviewer Rewards:
Area chairs rate the quality of each review in terms of “constructivism.” The 20 highest-rated reviewers will receive an expected reward of 1500$ funded by our generous sponsors. The exact number of reviewers that receive an award and the award amount is subject to change and might increase if the sponsor revenue is greater than expected. The top reviewer (who is willing to do so) will be invited to talk about reviewing at the conference.

Review Process:
Submissions will be double-blind, we will use OpenReview to host papers and allow for public discussions; comments that are posted by reviewers will remain anonymous.

Tentative timeline:
- Sep 9th: Abstract submission ~3 months before the conference.
- Sep 9th - 16th: reviewers bid for papers until paper submission deadline.
- Sep 16th: Paper submission deadline.
- Sep 16th - 17th: Paper-reviewer matching based on bids using the Toronto system.
- Sep 17th - Oct 20th: Main review period.
- Oct 20th - Nov 3rd: 2 weeks author and reviewer discussion, and paper revision period on OpenReview.
- Nov 3rd - 10th: 1 week reviewer and area chair discussion.
- Nov 10th - 24th: Easy decisions get accepted/rejected by area chairs. Unclear decisions and ethics concerns get escalated to Program Chairs/Senior Area Chairs.
- Nov 24th: Final decisions released.
- Nov 30th: Camera ready deadline.
- Dec 9th: Conference starts.

If you would like to review for LoG and are qualified, please sign up here. We would be very grateful to have you on board!

GraphGPS: Navigating Graph Transformers
Invited post by Ladislav Rampášek

In 2021, graph transformers (GT) won recent molecular property prediction challenges thanks to alleviating many issues pertaining to vanilla message passing GNNs. Here, we try to organize numerous freshly developed GT models into a single GraphGPS framework to enable general, powerful, and scalable graph transformers with linear complexity for all types of Graph ML tasks.

With GraphGPS, we managed to scale Graph Transformers to much larger graphs and get SOTA in several competitive benchmarks, e.g. 0.07 MAE on ZINC. Positional and structural embeddings are necessary for graph Transformers, encoding “where” a node is and “how” its neighborhood looks like, respectively. Bonus: they even make MPNNs provably more powerful! We organize them into local, global, and relative types.

Key observation: It is better to combine an MPNN and Transformer layer together into one: helps with over-smoothing, and allows for plug & play linear global attention, e.g., Performer. In fact, linear attention enables graph transformers to scale to dramatically larger graphs compared to typical molecules - we confirm it easily works on graphs with 5K nodes without any special batching!

Putting these 3 ingredients together: positional/structural encodings, choice of MPNN and Transformer layer combined into one layer, gives the blueprint for our GraphGPS: General, Powerful, Scalable graph Transformer. Plain numbers:

🚀 400% faster than previous graph transformers;
📈 Scaling to batches of graphs up to 10,000 nodes each thanks to linear attention models;
🛠 The GraphGPS library allows co combine any MPNN with any Transformer and any positional/structural encoding.

Find more details in:
- Medium blog post with a deep-dive into GraphGPS: https://mgalkin.medium.com/graphgps-navigating-graph-transformers-c2cc223a051c
- arxiv preprint: https://arxiv.org/abs/2205.12454
- Github repo: https://github.com/rampasek/GraphGPS

​​2nd Open Catalyst Challenge at NeurIPS 2022

The largest benchmark for equivariant GNNs announced its 2nd edition to be co-located with NeurIPS 2022. From the official announcement:

“This year's challenge focuses on the same task -- Initial Structure to Relaxed Energy (IS2RE) -- as last year. The primary differences are: 1) instead of two tracks, we will have a single track where using the IS2RE data and/or the Structure-to-Energy-Forces (S2EF) 2M training data is allowed. 2) A new test-challenge split will be released in September specifically for this year's challenge.”

Using an additional S2EF data as a training signal leads to consistently better performance, so you can now properly scale up and invest a few thousand GPU / TPU / GraphCore hours! (pun intended, yours truly wrote this message on a basic GPU-free laptop). Well, Open Catalyst is a notorious infrastructure-demanding challenge.

Graph Machine Learning for Visual Computing Tutorial @ CVPR 2022

The biggest CV conference features a dedicated tutorial on using Graph ML in Computer Vision tasks, e.g., video understanding, scene graphs in 3D vision, and more!

💫  The lineup of speakers is stellar: Petar Veličković (DeepMind), Matthias Fey (KumoAI / TU Dortmund), Bernard Ghanem (KAUST), Federico Tombari (Google), Fabian Manhardt (Google), Judith Fan (UCSD), Luca Carlone (MIT), and Rajat Talak (MIT).

Tune in next Monday, June 20th, 1:00pm - 5:30pm Central Daylight Time, there will be an open Zoom link 🖥️

Graph Machine Learning at AirBnB

Devin Soni from the engineering team of AirBnB wrote a Medium post on scaling GNNs to industrial-scale graphs. In summary, they use the framework of SIGN (Scalable Inception Graph Networks) and SGC (Simplified GCNs). SIGN pre-computes powers of the adjacency matrix before optimization whereas SGC collapses different layer weights and non-linearities into a single feature propagation step. Conceptually, the approach should be quite fast and scalable, although there are no experimental numbers in the post. Still, great to see recent advancements in scaling GNNs to industrial use-cases!

​​Graph Neural Networks Are The Next Big Thing

says Swami Sivasubramanian, VP of Data and ML Services at AWS re:MARS 2022. Can’t agree more! Watch the keynote to learn more how AWS accelerates graph learning tasks.

​​Monday Special: Learnable Neural Priority Queues in GNNs

Message passing propagates messages to all nodes in a neighborhood. Messages might be weighted with a fixed normalization constant (like in GCNs), or with a learnable scalar (GAT), or with a composition function over node and edge features (MPNN). Still, you’d send messages to all neighboring nodes. Some neighbor samplers (like the one in classic GraphSAGE) allow to subsample K nodes in a neighborhood to send messages to, but, still, all those K subsampled nodes receive the message.

Is there a way to somehow guide a GNN and send messages only to a fraction of neighbors and retain the same performance? This could also potentially save a lot of computation, e.g., when propagating through hub nodes. How do we select those important neighbors then?

Looking at the classical graph search algorithms like Dijkstra and A*, we employ priority queues that essentially rank edges according to a certain heuristic, then we take the top ranked edge, add it to the path, and continue further. Can we use something similar for GNNs?

Recently, a few fresh mid-2022 works proposed to learn priority queues explicitly or implicitly:

- Learning to Efficiently Propagate for Reasoning on Knowledge Graphs by Zhu et al. propose A*Net and a neural priority function. Essentially, we construct an edge index dynamically at each layer of a GNN starting from the “root” node. The priority function takes representations of a current node and edge feature, and produces a sigmoid distribution over neighboring nodes and edges from which we select top-K, add to the edge index, and then perform message passing. The strategy brings 5-7x reductions in the number of computed messages and 2-5x reductions in the GPU RAM (depending on the graph).

- Learning Adaptive Propagation for Knowledge Graph Reasoning by Zhang et al. propose AdaProp that builds the edge index dynamically as well. At each layer, AdaProp still computes all messages in the neighborhood, and then applies the differentiable Gumbel-TopK trick with the Straight-Through Estimator to select K edges. Those edges are added to the edge index for the next message passing layer. AdaProp does not save as many messages as A*Net but converges somewhat faster. (And should be more difficult to train due to noisy Gumbel-TopK + STE).

- Learning heuristics for A* by Numeroso et al. approach the A* problem from the Neural Algorithmic Reasoning viewpoint with the Encoder-Process-Decoder architecture. Instead of dynamically building the edge index, they attach an additional decoder to predict heuristic values (along with the standard node state predictor), and add a regularization term for possibly unbounded predicted heuristic values. Here, we still compute all messages during training, but can perform inference faster based on the predicted heuristics.

Check the papers for more details - definitely worth the time! Illustration: saved messages in the A*Net.

OpenFold & Open Molecular Software Foundation

News from the sister adjacent where Geometric Deep Learning is the main workhorse: OpenFold is a new, non-profit AI research consortium to foster free and open-source tools for biology and drug discovery. OpenFold is founded by the Lab of Mohammed AlQuraishi at Columbia University, Arzeda, Cyrus Biotechnology, Prescient Design, and Outspace Bio.

The first big release of OpenFold is OpenFold, (citing the authors) “a trainable reproduction” of AlphaFold 2 in PyTorch with the aim to open all the training data and model weights.

The OpenFold consortium is designed to be “OpenAI in drug discovery”, let’s hope they will be a bit more open than OpenAI itself about their models and code 😉

EURO Meets NeurIPS 2022 Vehicle Routing Competition

”The EURO Meets NeurIPS 2022 Vehicle Routing Competition aims to bring together researchers from operations research (OR) and machine learning (ML) to address the vehicle routing problem with time windows (VRPTW) as well as a dynamic VRPTW.”

Recently, we have been observing a surge in applying GNNs for Combinatorial Optimization problems (like Traveling Salesman Problem) - here is the top challenge combining combinatorial optimization and dynamic graphs. Data and problem denoscription are already available.

​​Recap: Fields Medal & Graph Theory, Origins of Geometric Deep Learning

1. Fields Medal is often considered “the Nobel Prize in mathematics”. This year, International Mathematical Union (IMU) announced 4 awardees: brilliant mathematicians Hugo Duminil-Copin (Université de Genève and IHÉS), June Huh (Princeton), James Maynard (Oxford), and Maryna Viazovska (EPFL).

It is heartwarming for channel’s editors that the research of June Huh has direct connections to the graph theory - first, he proved the 40-years-unsolved Read’s conjecture on counting ways to color the graph using chromatic polynomials, studied those polynomials even deeper, and generalized the framework to matroids. Check this wonderful Quanta Magazine’s article dedicated to June and his research.

2. Just in case you had all your browser tabs closed and looked for something new to read - Michael Bronstein comes to help and publishes a new blog on the origins of Geometric Deep Learning. This is going to be a series of articles tracing the history of geometry from Greeks to GNNs.

🔥 New Course: An Introduction to Group Equivariant Deep Learning

Erik Bekkers from University of Amsterdam created a fantastic new course covering the most up-to-date flavor of GNNs, namely, equivariant and group-equivariant GNNs. The course consists of 3 lectures, starts from the introduction to the group theory, gradually comes to equivariance and steerable kernels, covers tensor products and irreducible representations (hello Wigner matrices). After the course, you won’t be afraid of cryptic abbreviation like SO(3) or E(n)!

The course includes a YouTube playlist, slides, lecture notes, and Colab notebooks to play around with the real code.

If you got inspired by this topic, we highly recommend the upcoming course by Joey Bose (Mila and McGill) on Geometry and Generative Models with even deeper study of manifolds (hyperbolic, spherical, product) to normalizing flows, ODEs, and denoising diffusion models.

Graph ML Workshops and Summer Schools 🇬🇧 🇨🇦 🇨🇭🇮🇹

This week is surprisingly well-packed with physical meetings of the GraphML community with top speakers and lecturers. We would expect all the materials to be recorded and available online.

- London Geometry and ML Summer School (🇬🇧)
- Deep Exploration of non-Euclidean Data with Geometric and Topological Representation Learning (🇨🇦)
- Swiss Equivariant Machine Learning Workshop (🇨🇭)

Also, in 2 weeks there is going to be Italian Summer School on Geometric DL (🇮🇹).

TensorFlow GNN

TensorFlow GNN (TF-GNN) is a new scalable library for Graph Neural Networks in TensorFlow. It is designed from the bottom up to support the kinds of rich heterogeneous graph data that occurs in real-life use-cases. Many production models at Google use TF-GNN and it has been recently released as an open source project. Google has released a paper that describe the TF-GNN data model, its Keras modeling API, and relevant capabilities such as graph sampling, distributed training, and accelerator support. A new version was just pushed to GitHub.

ICML 2022 - Graph Workshops

ICML starts today with the full week of tutorials, main talks, and workshops. While we are preparing a blog post about interesting graph papers, you can already check the contents of graph- and related workshops to be held on Friday and Saturday.

- Topology, Algebra, and Geometry in Machine Learning (TAG in ML)
- Knowledge Retrieval and Language Models (KRLM)
- Beyond Bayes: Paths Towards Universal Reasoning Systems
- Machine Learning in Computational Design

Origins of Geometric Deep Learning - Part 2 and 3

A while ago we referenced the first article of the series on the Origins of Geometric DL by Michael Bronstein. Recently, the series got new episodes - Part 2 focuses on the high hopes about the perceptron, the curse of dimensionality, and first AI winters. Part 3 introduces first architectures with baked geometrical priors - the neocognitron (precursor of convnets) and convolutional neural networks.

As always, Michael did a great and meticulous job of finding original references and adding some comments to them - often the references section is as interesting and informative as the main text! 🍿