Symposium on Graph Drawing and Network Visualization

It's cool to see there is a small conference on how you can visualize graphs. Registration is free until 10 September.

KDD 2020 Highlights

I haven't found highlights about KDD 2020, so did my own. What's interesting there are many papers on scalability of GNNs, intersection of graphs and recommendation, and clustering algorithms. Paper digest allows you to browse quickly through the papers.

Fresh picks from ArXiv
This week in ArXiv new graph data sets for language recommendation, new optimization methods of GNNs, and applications to RL 🕹

GNN
• Optimization of Graph Neural Networks with Natural Gradient Descent
• Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks

Data sets
• VisualSem: a high-quality knowledge graph for vision and language
• COOKIE: A Dataset for Conversational Recommendation over Knowledge Graphs in E-commerce

Applications
• Multi-Agent Reinforcement Learning with Graph Clustering
• SF-GRASS: Solver-Free Graph Spectral Sparsification
• Learning Graph Edit Distance by Graph Neural Networks
• Community-Aware Graph Signal Processing

Graph Machine Learning Books

For a long time I was thinking that the community lacks proper books on graph machine learning and even thought maybe I should write one. But luckily there are other active people. With the difference of one day 2 (!) books were announced.

Graph Representation Learning Book by Will Hamilton, which so far has 3 main chapters on node embeddings, GNNs, and generative models. While the drafts are ready, there is still a long way to make it comprehensive book and the author promises to work on that. Great start.

Deep Learning on Graphs by Yao Ma and Jiliang Tang. This should be available next month and should focus on foundations of GNNs as well as applications.


That's great, hopefully they will become handbooks for those who want to start in this area. Now waiting the same but for educational courses 🙏

Mining and Learning with Graphs Workshop

MLG workshop is a regular workshop on various ML solutions for graphs. The videos for each poster can be found here. Keynotes should be available soon (except for Danai Koutra, which is available now).

Graph Machine Learning research groups: Pietro Liò

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.

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.

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

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).

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.

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

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).

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.

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.

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

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.

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 Machine Learning research groups: Danai Koutra

I do a series of posts on the groups in graph research, previous post is here. The 14th is Danai Koutra, ex-PhD student of Christos Faloutsos, she leads the graph exploration lab at University of Michigan, and could be a great Ph.D. advisor if you are interested in GML.


Danai Koutra (~1988)
- Affiliation: University of Michigan
- Education: Ph.D. in Carnegie Mellon University in 2010 (advisor: Christos Faloutsos)
- h-index 25
- Awards: ACM SIGKDD 2016 Dissertation Award; best paper awards at ICDM, PAKDD, ICDT
- Interests: graph mining, knowledge graphs, graph embeddings

Latent graph neural networks: Manifold learning 2.0?

One of the hot topics of this year is construction of a graph from unstructured data (e.g. 3d points or images). In a new post Michael Bronstein discusses existing approaches to latent graph learning and suggests that using GNN both to learn the structure of the graph and to solve the downstream tasks can be a better alternative than a de-coupled approach. This is indeed an exciting and active area of research with open problems and known applications to NLP, physics, and biology.

Fresh picks from ArXiv

This week on ArXiv: robot planning in the presence of many objects by researchers at MIT, a new SOTA on probabilistic type inference for software, application of GNN to trying clothes to different body shapes 👚

Applications
- Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks with Joshua Tenenbaum
- Advanced Graph-Based Deep Learning for Probabilistic Type Inference
- GINet: Graph Interaction Network for Scene Parsing ECCV 20
- Fully Convolutional Graph Neural Networks for Parametric Virtual Try-On SIGGRAPH 2020
- Addressing Cold Start in Recommender Systems with Hierarchical Graph Neural Networks

Theory
- Learning an Interpretable Graph Structure in Multi-Task Learning
- Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
- Adversarial Attack on Large Scale Graph