Graph Machine Learning research groups: Johan Ugander

I do a series of posts on the groups in graph research, previous post is here. The 30th is Johan Ugander, a professor at Stanford, who was a post-doc at Microsoft Research Redmond 2014-2015 and held an affiliation with the Facebook Data Science team 2010-2014.

Johan Ugander (~1986)
- Affiliation: Stanford
- Education: Ph.D. at Cornell in 2014 (advisors: Jon Kleinberg)
- h-index 17
- Interests: social network analysis, algorithms on graphs, clustering
- Awards: Young Investigator Award, best paper awards (WebSci, WSDM, AAAI)

Compositional Tokenization for Knowledge Graphs

This is a guest post by Michael Galkin about their new paper of reducing the memory issues of existing approaches.

Pretty much all KG embedding algorithms are, in fact, shallow embedding algorithms. It means that each node is mapped to a unique vector - and as a basis for all downstream tasks you need to store the whole embedding matrix in memory. Already at the OGB scale (2.5-5M nodes) you’d need 2-10 GB VRAM on the embeddings only, not counting forward passes and backprop. The more nodes you have - the bigger the matrix, the more expensive GPU you need.

Looking back to 2015, it resembles word2vec and GloVe a lot - huge shallow word vocabularies of 0.5-3M words, every other word is OOV (out of vocab). Then, subword units arrived (as Byte-Pair Encoding or WordPiece) and dramatically reduced vocab sizes allowing building infinite combinations from a rather small tokens vocab (30-50K in BERT & GPT-2/3 ). Saved params are now better invested into a flurry of Transformer encoders.

If we treat nodes in a graph like “words”, what would be their “sub-word” units? Can we have a similar approach that would allow to bootstrap a representation of both seen and unseen nodes using the same vocab? We tackle those questions in our new work where we design NodePiece (pun intended), a compositional tokenization scheme for KGs where tokens are anchor nodes and relation types. Going from shallow to compositional encoding, we reduce embedding matrices 10-1000x times and still observe a competitive performance. Interestingly, sometimes you don’t even need trainable node embeddings to perform well on node classification and relation prediction, i.e, relations around the node are enough!

We encourage you to find even more details in the pre-print, Medum blog, and try out the code in Github repo.

Graph Neural Networks as Neural Diffusion PDEs

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

Fresh picks from ArXiv
This week on ArXiv: life science package of DGL, efficient models for knowledge graphs, and explanation insights from tabular data 🤓

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

Software
* DGL-LifeSci: An Open-Source Toolkit for Deep Learning on Graphs in Life Science

Embeddings
* Simple Truncated SVD based Model for Node Classification on Heterophilic Graphs
* Exploring the Representational Power of Graph Autoencoder
* NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs with Mikhail Galkin and William L. Hamilton
* A Deep Latent Space Model for Graph Representation Learning

Explanation
* Towards Automated Evaluation of Explanations in Graph Neural Networks
* Reimagining GNN Explanations with ideas from Tabular Data

Survey
* Graph and hypergraph colouring via nibble methods: A survey

Speech recognition and Graph Transformer Networks

A lecture by Awni Hannun talks about low-resource speech recognition, beam search decoding, finite-state automate, and graph transformer networks.

Recordings: Graph Neural Networks at CAIMS

Recordings of a session at CAIMS are now available. The topics are the cutting-edge research in the GNN world and is interesting if you want to see what researchers are currently working on in this space.

From local structures to size generalization in graph neural networks by Haggai Maron (NVIDIA)

On the generalization of graph neural networks and their applications to probabilistic inference by Renjie Liao (Google)

Graph convolution for semi-supervised classification: improved linear separability and out-of-distribution generalization by Kimon Fountoulakis (University of Waterloo)

Persistent message passing by Petar Veličković (DeepMind)

On "On Graph Neural Networks versus Graph-Augmented MLPs"

There is a cool ICLR'21 paper "On Graph Neural Networks versus Graph-Augmented MLPs" by Lei Chen, Zhengdao Chen, and Joan Bruna, which studies a question I had in mind for some time: can we replace a graph with some statistics of graph, which we will later use with standard MLP, and not lose in quality?

The answer is that for graph-level task, such as graph isomorphism, we can indeed capture much of what's needed from the graph to solve graph isomorphism problem at the same level as WL test. However, for node-level tasks, there are provably less functions on nodes that graph-augmented MLPs can identify than GNNs.

Roughly, the reason is that GNNs process graph topology and node features at the same time, while graph-augmented MLPs first treat the graph topology and then process node features with MLP. So theoretically we lose expressive power when we use MLPs instead of GNNs on graph-structured data.

GNN Applications

An overview presentation by Xavier Bresson about applications of GNNs, which include chip design, protein folding, autonomous driving, energy physics, and more.

Connecting the Dots: Harness the Power of Graphs & ML

A new short book on graph ML that describes various algorithms on graphs and future challenges.

Fresh picks from ArXiv
This week on ArXiv: WL to solve planar graphs, efficient molecule generation, and compressing graphs 🤐

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

Math
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

GNNs
Curvature Graph Neural Network
Relational VAE: A Continuous Latent Variable Model for Graph Structured Data
GraphPiece: Efficiently Generating High-Quality Molecular Graph with Substructures
Privacy-Preserving Representation Learning on Graphs: A Mutual Information Perspective KDD 2021
Partition and Code: learning how to compress graphs with Andreas Loukas and Michael M. Bronstein
Evolving-Graph Gaussian Processes ICML Workshop 2021

How to build E(n) Equivariant Normalizing Flows, for points with features?

A nice post that discusses how one can use normalizing flows and equivariant GNNs to generate realistic molecules.

Graph Machine Learning research groups: Andreas Krause

I do a series of posts on the groups in graph research, previous post is here. The 31st is Andreas Krause, a professor at ETH Zurich and an advisor for Stefanie Jegelka.

Andreas Krause (~1982)
- Affiliation: ETH Zurich
- Education: Ph.D. at CMU in 2008 (advisor: Carlos Guestrin)
- h-index 81
- Interests: social network analysis, community detection, graphical models.
- Awards: Rossler Prize, best papers (AISTATS, AAAI, KDD, ICML)

Fresh picks from ArXiv
This week on ArXiv: explanations of GNNs, generalization of GAE and generating natural proofs 👴

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

GNN
* Automated Graph Learning via Population Based Self-Tuning GCN
* Quantitative Evaluation of Explainable Graph Neural Networks for Molecular Property Prediction
* Robust Counterfactual Explanations on Graph Neural Networks
* Probabilistic Graph Reasoning for Natural Proof Generation
* On Generalization of Graph Autoencoders with Adversarial Training
* Private Graph Data Release: A Survey

GNN User Group Meeting videos (June)

Video from the June meeting of GNN user group that includes talks about binary GNNs and dynamic graph models by Mahdi Saleh and
and about simplifying large-scale visual analysis of tricky data & models with GPUs, graphs, and ML by Leo Meyerovich.

Speeding Up the Webcola Graph Viz Library with Rust + WebAssembly

A captivating story about optimizing visualization of graphs in the browser. The code can be found here. Here is a performance comparison of different browser visualization libraries. And here is another efficient library for plotting graphs in a browser.

LOGML Videos

LOGML is an exciting summer school with projects and talks about graph ML happening this week. 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.

Effortless Distributed Training of Ultra-Wide GCNs

A great post about distributed training of GNNs on large graphs. The architecture splits the GNN into several submodules where each is trained independently on separate GPUs, providing the flexibility to increase significantly the hidden dimension of embeddings. As such this approach is GCN model agnostic, compatible with existing sampling methods, and performs the best in very large graphs.

Fresh picks from ArXiv
This week on ArXiv: QA in images, graph matching, and learning robot dynamics 🤖

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

GNNs
* Train on Small, Play the Large: Scaling Up Board Games with AlphaZero and GNN
* Reasoning-Modulated Representations with Petar Veličković and Thomas Kipf
* SENSORIMOTOR GRAPH: Action-Conditioned Graph Neural Network for Learning Robotic Soft Hand Dynamics
* Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More with Stephan Günnemann
* Graphhopper: Multi-Hop Scene Graph Reasoning for Visual Question Answering with Stephan Günnemann
* Elastic Graph Neural Networks

Survey
* A Survey of Knowledge Graph Embedding and Their Applications

Graph Papers at ICML 2021

ICML 2021 is happening this week and here is a list of all relevant graph papers that you can encounter there. There are papers on improving expressiveness, explainability, robustness, normalization and theory.

Awesome Explainable Graph Reasoning

An awesome collection of research papers and software related to explainability in graph machine learning, provided by AstraZeneca. It covers papers on explainable predictions and reasoning, libraries, and survey papers.