Gradient Boosting Meets Graph Neural Networks for Heterogeneous Data

We have two short paper submissions this year to GRL workshop this year. One of them is about application of gradient boosting decision trees (GBDT) to graphs. We know that Xgboost, LightGBM, and CatBoost perform extremely well on tabular data and are preferred methods for competitions like Kaggle. But how do you generalize it to graph-structured data?

A naïve approach is to train first GBDT on node features only, ignoring graph topology and then use predictions as additional features to your model. But that misses graph information, possibly leading to inaccurate predictions. Instead, we propose to train GBDT and GNN end-to-end such that each tree of GBDT approximates mistakes made by GNN in the forward passes. We call the model Boosted Graph Neural Network and show that it can lead to significant uplift in performance in node regression task, while being very efficient.

Are Hyperbolic Representations in Graphs Created Equal?

The second submission to GRL workshop was on hyperbolic embeddings for graphs. We first make a good introduction to the distances and dot products in k-Stereographic model (a Riemannian manifold with constant curvature) and fix the issue with taking gradients at zero curvature, by taking a Taylor series expansion around the origin. This allows seamless gradient descent optimization in non-Euclidean space.

Then we make experiments on node and graph classification, link prediction, and graph embedding task (i.e. preserving distances in the latent space) and show that for link prediction and graph embedding there is an uplift in using hyperbolic manifolds, while for node and graph classification Euclidean models work better.

ICML 2020 collaboration graph

As a preview to my future post (next week) about ICML 2020, I want to share a collaboration graph between different organizations. Final graph has 429 nodes (organizations) and 1206 edges (collaborations). Each edge has a weight: the number of papers the organizations collaborated with. As the final graph is too big to display nicely, you can also look at the subgraph between organizations that collaborated the most (at least 30 collaborations). I will release a colab notebook so that you can play with it.

Covid Knowledge Graph

A knowledge graph on COVID-19 that integrates various public datasets. This includes relevant publications, case statistics, genes and functions, molecular data and much more. It's implemented in Neo4j and can be accessed via browser.

The ‘Useless’ Perspective That Transformed Mathematics

Matrix algebra is well understood, while group theory, which is used in many proofs of graph theory and other fields, is much more complicated to study. Representation theory creates a bridge between group theory and linear algebra by assigning a matrix to each element in a group, according to certain rules. This nice article introduces to the world of representation theory.

Fresh picks from ArXiv
This week people share their works they submitted to NeurIPS, a lot of interesting papers from the top people in GML.

GNN
• From Graph Low-Rank Global Attention to 2-FWL Approximation with Yaron Lipman
• Graph Meta Learning via Local Subgraphs with Marinka Zitnik
• Data Augmentation for Graph Neural Networks
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization
• Learning Graph Models for Template-Free Retrosynthesis with Regina Barzilay
• Wide and Deep Graph Neural Networks with Distributed Online Learning
• Pointer Graph Networks with Petar Veličković
• Optimal Transport Graph Neural Networks with Octavian-Eugen Ganea, Regina Barzilay, Tommi Jaakkola
• Manifold structure in graph embeddings
• On the Bottleneck of Graph Neural Networks and its Practical Implications

Conferences
• Exploring Algorithmic Fairness in Robust Graph Covering Problems NeurIPS 2019

Surveys
• A Survey on Generative Adversarial Networks: Variants, Applications, and Training

ICML 2020. Comprehensive analysis of authors, organizations, and countries.

Finally here is my post on the analysis of ICML 2020. There are several things I learned from that. For example that USA participates in 3/4 of the papers 😱 Or that DeepMind makes approximately half of all papers for UK. Or that Google does not collaborate with other companies. Or that, except the USA, there is only China that can brag about several companies that publish regularly. Or that a Japanese professor published 12 papers. And much more.

The code and data is on the github, but the cool part is that you can make your own interactive plots in colab notebook (with no installation required) including a collaboration graph between universities and companies.

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

The first blog post of Michael Bronstein about graph learning.

Optimal transport: a hidden gem that empowers today’s machine learning

Very simple explanation of what optimal transport problem is and how it can be applied to various domains such as computer vision. Interestingly just yesterday there was a paper on optimal transport GNN.

June Arxiv: how many graphs papers?

From 18 March to 17 April there were 282 new and 98 updated papers in ArXiv CS section. This is 18 papers less that in the previous period.

PhD Theses on Graph Machine Learning

Here are some PhD dissertations on GML. Part 2 (previous here).

Haggai Marron: Deep and Convex Shape Analysis

Benoit Playe: Machine learning approaches for drug virtual screening

Graph Machine Learning research groups: Tommi Jaakkola

I do a series of posts on the groups in graph research, previous post is here. The eighth is Tommi Jaakkola. He has 7 papers in upcoming ICML 2020. His recent interests include molecular graph design and he maintains AI initiative for finding promising antiviral molecules for COVID-19.


Tommi Jaakkola (~1971)
- Affiliation: MIT
- Education: Ph.D. at MIT in 1997 (supervised by Michael Jordan);
- h-index: 76;
- Awards: Sloan research fellowship, AAAI Fellow;
- Interests: molecular generation, models of GNN

DeepSnap

There is a release of DeepSnap by Stanford group. I have not tested it, but it should allow applying graph algorithms from networkx to pytorch-geometric graphs.

Implicit Neural Representations by Yaron Lipman

The talk Implicit Neural Representations by Yaron Lipman from CVPR 20 workshop on Deep Learning Foundations of Geometric Shape.

Fresh picks from ArXiv
This week highlights applications of GNNs to molecules, contagion, NLP, recommender systems and more.

GNN
• Generalizing Graph Neural Networks Beyond Homophily
• Finding Patient Zero: Learning Contagion Source with Graph Neural Networks with Albert-László Barabási
• MoFlow: An Invertible Flow Model for Generating Molecular Graphs
• Quantifying Challenges in the Application of Graph Representation Learning
• Neural Architecture Optimization with Graph VAE
• Interactive Recommender System via Knowledge Graph-enhanced Reinforcement Learning
• Subgraph Neural Networks with Marinka Zitnik
• Temporal Graph Networks for Deep Learning on Dynamic Graphs with Michael Bronstein
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs with Andreas Loukas
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Isometric Graph Neural Networks
• Modeling Graph Structure via Relative Position for Better Text Generation from Knowledge Graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting with Michael Bronstein

Math:
• Local limit theorems for subgraph counts
• Longest and shortest cycles in random planar graphs


Conferences
• How to Count Triangles, without Seeing the Whole Graph KDD 2020
• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training KDD 2020

Surveys
• Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison

Spektral

Spektral is a library to code GNN in Tensorflow 2 and Keras. New version includes:

- a unified message-passing interface based on gather-scatter
- 7 new GNN layers
- Huge performance improvements
- Improved utils, docs, and examples

The paper will be presented in GRL workshop.

Criteo papers at ICML 2020

Criteo, where I work, this year has record number of accepted papers at ICML. We have 9 papers on various topics, from online learning to theory of optimization to GANs. It makes us 1st company in EU and top-7 company worldwide (among 134 companies who have their papers accepted). So I wrote a short description of each paper in a new blog post.