Graph Machine Learning

On the evaluation of graph neural networks Over the last year there have been many revealing benchmark papers that re-evaluate existing GNNs on standard tasks such as node classification (see this and this for example). However, the gap between claimed and real results still exist and especially noticeable when the baselines are not properly selected. For one using MLP only on node features often leads to better results than those from GNNs. This is surprising as GNNs can be seen as a generalization of MLP. I encounter this more and more on new data sets, although for several data sets (e.g. Cora) you can clearly see advantage of using GNNs. Another ML model that I haven't seen being tried at graph settings is GBDT model (e.g. XGBoost, CatBoost, LightGBM). GBDT model are de-facto winners of many Kaggle competitions where the data is tabular, so you could expect if you have enough variability in your node features just using GBDT on them would often make a good baseline. I have tried this for several problems and it often outperforms the proposed method in the paper. For example, for node classification using GBDT on Bus data set achieves 100% accuracy (vs. ~80% in the paper). Or on graph classification GBDT can beat other top GNN models (see image below). Considering how easy it is to run experiments with GBDT models I would expect it would be a good counterpart to MLP in the realm of baselines.

Graph ML at Twitter A post by Michael Bronstein and Zehan Wang that talks about the current challenges of using graph models for industry settings: scalability, heterogeneous settings, dynamic graphs, and presence of noise.

Fresh picks from ArXiv This week on ArXiV is a new library for KG embeddings, a version of batch norm for graphs, and a survey on SVD decompositions 🎙 GNN • TorchKGE: Knowledge Graph Embedding in Python and PyTorch • Heterogeneous Graph Neural Network for Recommendation • FairGNN: Eliminating the Discrimination in Graph Neural Networks with Limited Sensitive Attribute Information Scaling • GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training • Rethinking Graph Regularization For Graph Neural Networks • Lifelong Graph Learning Survey • A Survey of Singular Value Decomposition Methods for Distributed Tall/Skinny Data

DeepMind's Traffic Prediction with Advanced Graph Neural Networks A new blog post by DeepMind has been released recently that describes how you can apply GNN for travel time predictions. There are not many details about the model itself (which makes me wonder if deep net trained across all supersegments would suffice), but there are curious details about training. 1. As the road network is huge I suppose, they use sampling sampling of subgraphs in proportion to traffic density. This should be similar to GraphSAGE-like approaches. 2. Sampled subgraphs can vary a lot in a single batch. So they use RL to select subgraph properly. I guess it's some form of imitation learning that selects graphs in a batch based on some objective value. 3. They use MetaGradients algorithm to select a learning rate, which was previously used to parametrize returns in RL. I guess it parametrizes learning rate instead in this blog post.

Graph Convolutional Networks Lecture A lecture by Xavier Bresson as part of NYU course is now available on YouTube. This covers spectral and spatial architectures as well as benchmarking between those. Additionally you can find practical session and slides on the course webpage.

GML Newsletter Issue #2 The second newsletter is out! Blog posts (graph laplacians, SIGN, quantum GNN, TDA), videos (MLSS-Indo, PNA), events (KDD, Israeli workshops, JuliaCon), books, and upcoming events (graph drawing symposium, data fest).

GNN aggregators talk Today (6 pm Europe time) Petar Veličković will speak about their work on Principal Neighbourhood Aggregation for Graph Nets. He will discuss how you can design better neighborhood aggregators for your GNNs. Stream: https://youtube.com/watch?v=c00GuCe62mk Slides: https://petar-v.com/talks/PNA-AISC.pdf

Topology-Based Papers at ICML 2020 Topological data analysis studies the applications of topological methods to real-world data, for example constructing and studying a proper manifold given only 3D points. This topic is increasingly gaining attention and a new post by Bastian Rieck discusses topological papers at ICML 2020 that includes graph filtration techniques, topological autoencoders, and normalizing flows.

Number of papers in GML: Aug 2020 There are 277 new GML papers in CS section of ArXiv in Aug 2020 (vs 339 in July).

Fresh picks from ArXiv This week ArXiv presents papers on visualization of graphs, robustness certificates, and a survey on combinatorial optimization ♟ GNN • All About Knowledge Graphs for Actions • The Effectiveness of Interactive Visualization Techniques for Time Navigation of Dynamic Graphs on Large Displays • Argo Lite: Open-Source Interactive Graph Exploration and Visualization in Browsers • Accelerating Force-Directed Graph Drawing with RT Cores • Learning Robust Node Representation on Graphs • Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation • Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More Survey • Graph Embedding for Combinatorial Optimization: A Survey

JuliaCon2020 Graph Videos 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. Check out the full program here.

Graph Machine Learning research groups: PietroLiò I do a series of posts on the groups in graph research, previous post is here. The 13th is Pietro Liò, a computational biologist and a supervisor of Petar Veličković. He has also been very active in GML recently (with 54 papers in 2020) so he could be a good choice if you want to do a PhD in this area. Pietro Liò (~1965) - Affiliation: University of Cambridge - Education: Ph.D. in Theoretical Genetics at University of Firenze, Italy in 1995 and Ph.D. in Engineering at University of Pavia, Italy in 2007; - h-index: 50; - Awards: Lagrange Fellowship, best papers at ISEM, MCED, FET; - Interests: graph neural networks, computational biology, signal processing.