Graph Machine Learning

Wednesday Papers Something you might be interested in while waiting for the LOG reviews (unless you are writing emergency reviews, hehe) - Expander Graphs Are Globally Synchronising by Pedro Abdalla, Afonso S. Bandeira, Martin Kassabov, Victor Souza, Steven H. Strogatz, Alex Townsend. In the previous posts, we covered interesting properties of Expander Graphs (Cayley graphs). This new work on the theory side employs expander graphs to demonstrate that random Erdos-Renyi graphs G(n,p) are connected if p ≥ (1 + eps)(log n)/n👏 - On Classification Thresholds for Graph Attention with Edge Features by Kimon Fountoulakis, Dake He, Silvio Lattanzi, Bryan Perozzi, Anton Tsitsulin, Shenghao Yang - Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation by Zhiqiang Zhong, Sergei Ivanov, Jun Pang - Graphein - a Python Library for Geometric Deep Learning and Network Analysis on Protein Structures and Interaction Networks by Arian R. Jamasb, Ramon Viñas, Eric J. Ma, Charlie Harris, Kexin Huang, Dominic Hall, Pietro Lió, Tom L. Blundell - Annotation of spatially resolved single-cell data with STELLAR by Maria Brbić, Kaidi Cao, John W. Hickey, Yuqi Tan, Michael P. Snyder, Garry P. Nolan & Jure Leskovec

GraphMLNews Today (Oct 21st) MIT hosts the first Molecular ML Conference (MoML 2022). OpenBioML backed by StabilityAI (creators of Stable Diffusion) launches an open-source initiative to improve protein structure prediction. The base implementation will be OpenFold — powered by the cluster behind Stable Diffusion, we could expect full reproduction of AlphaFold experiments, ablations, and, of course, better interfaces thanks to the open-source community! OpenMM, one of the most popular Python frameworks for molecular modeling, released a new version 8.0. The workshop on Geometric Deep Learning in Medical Image Analysis (GeoMediA), to be held on Nov 18th in Amsterdam, published the list of accepted papers and a program including keynotes by Emma Robinson and Michael Bronstein.

Blog Posts of the Week A few fresh blog posts to add to your weekend reading list. Graph Neural Networks as gradient flows by Michael Bronstein, Francesco Di Giovanni, James Rowbottom, Ben Chamberlain, and Thomas Markovich. The blog summarizes recent efforts in understanding GNNs from the physics perspective. Particularly, the post describes how GNNs can be seen as gradient flows that help in heterophilic graphs. Essentially, the approach implies having one symmetric weight matrix W shared among all GNN layers, residual connections, and non-linearities can be dropped. Under this sauce, classic GCNs by Kipf & Welling strike back! Graph-based nearest neighbor search by Liudmila Prokhorenkova and Dmitry Baranchuk. The post gives a nice intro to the graph-based technology (eg, HNSW) behind many vector search engines and reviews recent efforts in improving scalability and recall. Particularly, the authors show that non-Euclidean hyperbolic space might have a few cool benefits unattainable by classic Euclidean-only algorithms. Long Range Graph Benchmark by Vijay Dwivedi. Covered in one the previous posts in this channel, the post introduces a new suite of tasks designed for capturing long-range interactions in graphs. Foundation Models are Entering their Data-Centric Era by Chris Ré and Simran Arora. The article is very relevant to any large-scale model pre-training in any domain, be it NLP, Vision, or Graph ML. The authors observe that in the era of foundation models we have to rethink how we train such big models, and data diversity becomes the single most important factor of inference capabilities of those models. Two lessons learned by the authors: “Once a technology stabilizes the pendulum for value swings back to the data” and “We can (and need to) handle noise”.

Graph Papers of the Week Expander Graph Propagation by Andreea Deac, Marc Lackenby, Petar Veličković. A clever approach to bypass bottlenecks without fully-connected graph transformers. Turns out that sparse but well-connected 4-regular Cayley graphs (expander graphs) can be a helpful template for message propagation. Cayley graphs of a desired size can be pre-computed w/o looking at the original graph. Practically, you can add a GNN layer propagating along a Cayley graph after each normal GNN layer over the original graph. The anonymous ICLR 2023 submission Exphormer: Scaling Graph Transformers with Expander Graphs applies the same idea of expander graphs as a sparse attention in Graph Transformers allowing them to scale to ogb-arxiv (170k nodes) Rethinking Knowledge Graph Evaluation Under the Open-World Assumption by Haotong Yang, Zhouchen Lin, Muhan Zhang. When evaluating KG link prediction tasks, there is no guarantee that the test set contains really all missing triples. The authors show that if there is an additional set of true triples (not labeled as true in the test), as small as 10% of the test set, MRR on the original test set only log-correlates with the MRR on the true test set. It means that if your model shows 40% MRR on the test set and you think it’s incomplete, chances are the true MRR can be much higher, you should inspect the top predictions as possibly new unlabeled true triples. Pre-training via Denoising for Molecular Property Prediction by Sheheryar Zaidi, Michael Schaarschmidt, and DeepMind team. The paper takes the NoisyNodes SSL objective to the next level (aka NoisyNodes on steroids). NoisyNodes takes a molecular graph with 3D coordinates, adds Gaussian noise to those 3D features, and asks to predict this noise as a loss term. NoisyNodes, as an auxiliary objective, was used in many OGB Large-Scale Challenge winning approaches, but now the authors study NoisyNodes as the sole pre-training SSL objective. Theory-wise, the authors find a link between denoising and score-matching (commonly used in generative diffusion models) and find that denoising helps to learn force fields. MPNN pre-trained on PCQM4Mv2 with this objective transfers well to QM9 and OC20 datasets and often outperforms fancier models like DimeNet++ and E(n)-GNN.

📏Long Range Graph Benchmark Vijay Dwivedi (NTU, Singapore) published a new blogpost on long-range graph benchmarks introducing 5 new challenging tasks in node classification, link prediction, graph classification, and graph regression. “Many of the existing graphlearningbenchmarks consist of prediction tasks that primarily rely on local structural information rather than distant information propagation to compute a target label or metric. This can be observed in datasets such as ZINC, ogbg-molhiv and ogbg-molpcba where models that rely significantly on encoding local (or, near-local) structural information continue to be among leaderboard toppers.” LRGB, a new collection of datasets, aims at evaluating long-range capabilities of MPNNs and graph transformers. Particularly, the node classification tasks were derived from image-based Pascal-VOC and COCO, the link prediction task is derived from PCQM4M asking about links between atoms distant in the 2D space (5+ hops away) but close in the 3D space where only 2D features are given, and the graph-level tasks focus on predicting structures and functions of small proteins (peptides). Message passing nets (MPNNs) are known to suffer from the bottleneck effects and oversquashing and, hence, underperform in long-range tasks. First LRGB experiments confirm that showing that fully-connected graph transformers quite significantly outperform MPNNs. A big room for improving MPNNs! Paper, Code, Leaderboard

Hot New Graph ML Submissions from ICLR 🧬 Diffusion remains the top trend in AI/ML venues this year, including the graph domain. Ben Blaiszik compiled a Twitter thread of interesting papers in AI 4 Science domain including material discovery, catalyst discovery, and crystallography. Particularly cool works: - Protein structure generation via folding diffusion by the collab between Stanford and MSR - Kevin E. Wu, Kevin K. Yang, Rianne van den Berg, James Y. Zou, Alex X. Lu, Ava P. Amini - why do you need AlphaFold and MSAs if you can just train a diffusion model to predict all the structure? 😉 - Dynamic-Backbone Protein-Ligand Structure Prediction with Multiscale Generative Diffusion Models by NVIDIA and Caltech - Zhuoran Qiao, Weili Nie, Arash Vahdat, Thomas F. Miller III, Anima Anandkumar - DiffDock: Diffusion Steps, Twists, and Turns for Molecular Docking by MIT - Gabriele Corso, Hannes Stärk, Bowen Jing, Regina Barzilay, Tommi Jaakkola - the next version of the famous EquiDock and EquiBind combined with the recent Torsional Diffusion. - We’d include here a novel benchmark work Tartarus: A Benchmarking Platform for Realistic And Practical Inverse Molecular Design by Stanford and University of Toronto - AkshatKumar Nigam, Robert Pollice, Gary Tom, Kjell Jorner, Luca A. Thiede, Anshul Kundaje, Alan Aspuru-Guzik 📚 In a more general context, Yilun Xu shared a Google Sheet with ICLR submissions on diffusion papers and score-based generative modeling including trendy text-to-video models announced by FAIR and Google. 🤖 Derek Lim compiled a Twitter thread on 10+ ICLR submissions on Graph Transformers - the field looks a bit saturated at the moment, let’s see what reviewers say. 🪓 Michael Bronstein’s lab at Twitter announced two cool papers: - Gradient Gating for Deep Multi-Rate Learning on Graphs by the collab between ETH Zurich, Oxford, and Berkley - T. Konstantin Rusch, Benjamin P. Chamberlain, Michael W. Mahoney, Michael M. Bronstein, Siddhartha Mishra. A clever trick improving a standard residual connection to allow nodes to get updated ad different speeds. A blast from the past - GraphSAGE from 2017 with gradient gating becomes a unanimous leader by a large margin in heterophilic graphs 👀 - Graph Neural Networks for Link Prediction with Subgraph Sketching by Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M. Bronstein, Max Hansmire. A neat usage of sketching to encode subgraphs in ELPH and its more scalable buddy BUDDY for solving link prediction in large graphs.

DGL: Billion-Scale Graphs and Sparse Matrix API In a new release 0.9.1 DGL accelerated the pipeline of working with very large graphs (5B edges). Before it was taking 10 hours and 4TB of RAM and now 3 hours and 500GB of RAM, which also reduces the cost by 4x. Also, if you use or would like to use sparse API for your GNNs, you can provide the feedback and use cases to the DGL team (feel free to reach out to @ivanovserg990 to connect). They are looking for the following profiles: * Researchers/students who are familiar with sparse matrix notations or linear algebra. * May have math or geometry backgrounds. * Work majorly on innovating GNN architecture; less on domain applications. * May have PyG/DGL experience.

ICLR 2023 Submissions The list of submissions to the top AI venue is available on OpenReview (with full-text PDFs). There are 6000+ submissions this year (3x growth from 2000+ last year), we will be keeping an eye on cool Graph ML submissions and prepare an overview. Enjoy the weekend reading and checking if someone has scooped a project you’ve been working on last months/years 😉

​​GraphML News: PyG + NVIDIA, Breakthrough Prize 🚀 PyG announced the release of pyg-lib, the result of collaboration with NVIDIA on speeding up most important PyG operations. It is a low-level GNN library that integrates cuGraph, cuDF, and CUTLASS that improve the speed of matrix multiplications and graph sampling (a common bottleneck when working on large graphs). The reported speedups are pretty astounding - up to x150 when sampling on a GPU. There will be more exciting news about PyG at the upcoming Stanford Graph Learning Workshop! 👏 Breakthrough Prize (renowned as the “Oscars of Science”) announced the winners in life sciences, maths, and physics - graph and geometry areas are well represented there! - John Jumper (DeepMind) and Demis Hassabis (DeepMind) received the Life Sciences prize for AlphaFold - Daniel A. Spielman (Yale University) received the Math prize for contributions to spectral graph theory, the Kadison-Singer problem, optimization, and coding theory - Ronen Eldan (Weizmann Institute of Science and Microsoft Research) received the New Horizons in Mathematics Prize for advancing high-dimensional geometry and probability including the KLS conjecture - Vera Traub (Uni Bonn PhD 2020) received the Maryam Mirzakhani New Frontiers Prize for advances in approximation results in classical combinatorial optimization problems, including the traveling salesman problem and network design.

TorchProtein & PEER Protein Sequence Benchmark Release MilaGraph released TorchProtein, a new version of TorchDrug powered with a suite of tools for protein sequence understanding. Quoting the authors: “ TorchProtein encapsulates many complicated yet repetitive subroutines into functional modules, including widely-used datasets, flexible data processing operations, advanced encoding models, and diverse protein tasks. With TorchProtein, we can rapidly prototype machine learning solutions to various protein applications within 20 lines of codes, and conduct ablation studies by substituting different parts of the solution with off-the-shelf modules. Furthermore, we can easily adapt these modules to our own needs, and make systematic analyses by comparing the new results to a benchmark provided in the library.” Simultaneously, the authors present PEER: A Comprehensive and Multi-Task Benchmark for Protein Sequence Understanding, a new benchmark of 17 protein understanding tasks grouped into 5 categories (Function Prediction, Localization Prediction, Structure Prediction, Protein-Protein Interaction Prediction, Protein-Ligand Interaction Prediction) already available in TorchProtein. ProtBert and ESM-1b have been probed on PEER (and ESM-2 is expected to arrive as well).

📚Weekend Reading This week brought quite a few interesting papers and resources - we encourage you to invest there some time: Geometric multimodal representation learning by Yasha Ektefaie, George Dasoulas, Ayush Noori, Maha Farhat, and Marinka Zitnik. A survey of 100+ papers on graphs combined with other modalities and a framework of multi-modal approaches for natural sciences like physical interaction, molecular reasoning, and protein modeling. Clifford Neural Layers for PDE Modeling by Johannes Brandstetter, Rianne van den Berg, Max Welling, Jayesh K. Gupta. If you thought you know all the basics from the Geometric Deep Learning Course - here is something more challenging. The authors introduce the ideas from Geometric Algebra into ML tasks, namely, Clifford Algebras that unify numbers, vectors, complex numbers, quaternions, and have additional primitives to incorporate plane and volume segments. The paper gives a great primer on the math and applications. You can also watch a very visual YouTube lecture on Geometric Algebras. Categories for AI (Cats4AI) - an upcoming open course on Category Theory created by Andrew Dudzik, Bruno Gavranović, João Guilherme Araújo, Petar Veličković, and Pim de Haan. “This course is aimed towards machine learning researchers, but approachable to anyone with a basic understanding of linear algebra and differential calculus. The material is self-contained and all the necessary background will be introduced along the way.” Don’t forget your veggies 🥦

Upcoming NeurIPS’22 Workshops & Submission Deadlines As NeurIPS’22 decisions are out, you might want to submit your work to some cool upcoming domain-specific graph workshops: 1. Temporal Graph Learning Workshop @ NeurIPS’22 organized by researchers from Mila and Oxford - deadline September 19th 2. New Frontiers in Graph Learning @ NeurIPS’22 organized by researchers from Stanford, Harvard, Yale, UCLA, Google Brain, and MIT - deadline September 22nd 3. Symmetry and Geometry in Neural Representations @ NeurIPS’22 - organized by researchers from UC Berkley, Institut Pasteur, ENS, UC Santa Barbara - deadline September 22nd 4. Workshop on Graph Learning for Industrial Applications @ NeurIPS’22 organized by JP Morgan, Capital One, Bank of America, Schonfeld, Mila, IBM, Pfizer, Oxford, and FINRA - deadline September 22nd 5. Critical Assessment of Molecular ML (NeurIPS’22 side-event) organized by ELLIS units in Cambridge and Linz - deadline October 18th If you are at MICCAI in Singapore those days, don’t forget to attend the 4th Workshop on Graphs in biomedical Image Analysis (GRAIL) on September 18th organized by NVIDIA, TU Munich, and Oxford. There will be talks by Marinka Zitnik, Islem Rekik, Mark O’Donoghue, and Xavier Bresson.