Graph Machine Learning

Twitter conference There is an interesting format of neuroscience conference happening right now: 24-hour of papers on Twitter. Each paper is presented as a series of tweets at the allocated time slot. No registration, no videos, but you can still talk to the authors. To get an idea, take a look at this graph paper, Characterising group-level brain connectivity using exponential random graph models. You get limited understanding of the paper, but what's cool is that you have a permanent opportunity to ping the authors about their paper even when the conference ends.

This is very interesting as essentially it means that in the best case scenario GIN will be as powerful as 1-WL but in general it's not and this what most people including myself don't get right about this work. It would be very interesting to see a counterexample when GIN cannot distinguish graphs that 1-WL can.

But then, they say that GIN in fact uses MLP as the aggregation function \phi and they only hope that it will learn injective function. There is no constraint on the MLP so in principle it can easily learn non-injective function, in which case it will be less powerful then 1-WL.

​How powerful graph neural networks? I spent last night on studying the proofs from the ground-breaking ICLR paper of 2018, How Poweful are Graph Neural Networks by Xu et al. (a collaboration between MIT and Stanford). I almost convinced myself that everything is correct when I got a major insight that I think I need to share. This paper is revolutionary because it shows that you can build GNN such that it would solve graph isomorphism problem almost surely. In particular, their model, Graph Isomorphism Network (GIN) is as powerful as 1-WL algorithm, which is known for 50 years and almost solves graph isomorphism problem, except for a few edge cases. I think this is how everyone in the field think about this paper: there is an architecture which you can train such that it solves very hard combinatorial problem. But I realized it's not the case and there are situations when GIN cannot distinguish non-isomorphic graphs, essentially meaning that sometimes GIN can be less powerful than 1-WL. In their paper they show that if your aggregation and readout functions are injective then GNN will be as powerful as 1-WL algorithm. Look at theorem below.

​How many graphs papers are there? From 14 February to 17 March there were 335 new and 152 updated papers in ArXiv CS section. This section is usually the place for all GML works. I didn't include here a more theoretical section, ArXiv math, which usually has more or less the same number of papers as CS section.

Fresh picks from ArXiv This week continues with accepted papers to CVPR and WebConf, submissions to ICML, lots of interesting surveys and even happiness in graphs ☺️ Survey • Reconfiguration of Colourings and Dominating Sets in Graphs: a Survey • A Survey of Adversarial Learning on Graphs • Graph Spanners: A Tutorial Review • A Survey on Contextual Embeddings • Hyper-Parameter Optimization: A Review of Algorithms and Applications • Integrating Physics-Based Modeling with Machine Learning: A Survey CVPR 20 • Towards High-Fidelity 3D Face Reconstruction from In-the-Wild Images Using Graph Convolutional Networks • VSGNet: Spatial Attention Network for Detecting Human Object Interactions Using Graph Convolutions • Adaptive Graph Convolutional Network with Attention Graph Clustering for Co-saliency Detection WebConf 20 • Reinforced Negative Sampling over Knowledge Graph for Recommendation ICML 20 • Gauge Equivariant Mesh CNNs: Anisotropic convolutions on geometric graphs by group of Max Welling • Learning Algebraic Multigrid Using Graph Neural Networks • Wasserstein-based Graph Alignment • Evaluating Logical Generalization in Graph Neural Networks by group of William L. Hamilton • Universal Function Approximation on Graphs using Multivalued Functions Physics • Characterization of solvable spin models via graph invariants Graph Theory • Maximizing Happiness in Graphs of Bounded Clique-Width • The Reconstruction Conjecture for finite simple graphs and associated directed graphs Libraries • An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs

Graph Machine Learning research groups: Jure Leskovec I will do a series of posts on the groups in graph research. The first one will be on the most famous researcher in GML, Jure Leskovec. Once I had a chance to visit his lab at Stanford and to talk to his students. By the time I already worked in a company and when I asked if there are topics we can work together, they said that typically a company needs to make a "gift" to start working for them. Naively, I asked what's the gift. They answered "somewhat, around 200-300K USD". So I still wait for my publications with them:) Jure Leskovec (1980) - Affiliation: Stanford, Pinterest; - Education: Ph.D. at CMU in 2008 (supervised by Christos Faloutsos); - h-index: 103; - Awards: best papers at KDD, ICDM, WSDM; Lagrange prize; - Interests: new models for GNN, social network analysis, diffusion models.

Random Features Strengthen Graph Neural Networks Continuation of the previous post, a recent submission to ICML 20 by Sato et al. This is quite cool as it shows you can add a random number to your node embedding and it would become a more powerful GNN. They improved bounds on Minimum Dominating Set and Maximum Matching problems and showed that it can recognize graphs that other GNNs cannot.

A Survey on The Expressive Power of Graph Neural Networks This is the best survey on the theory on GNNs I'm aware of. It produces so many illustrative examples on what GNN can and cannot distinguish. It's funny, it's made by Ryoma Sato who I already saw from other works on GNNs and I thought it's one of these old Japanese professors with long beard and strict habits, but it turned out to be a 1st year MSc student 🇯🇵

https://twitter.com/PeterWBattaglia/status/1237425685766995974?s=20

Learning to Simulate Complex Physics with Graph Networks For those who are interested in the overlap of physics and graph machine learning, there is a nice video by Peter Battaglia (DeepMind), who has been working on this topic for years. Also they have a recent submission to ICML 20 with some cool videos of GNN predictions of real physics. Beyond the cool research that they do, it's incredible to see the animation that they accompany their papers with. You know what they say it's more important how you present the paper than what your paper is about.