Graph Machine Learning

Paper Notes in Notion Vitaly Kurin discovered a great format to track notes for the papers he reads. These are short and clean digestions of papers in the intersection of GNNs and RL and I would definitely recommend to look it up if you are studying the same papers. You can also create the same format in Notion by adding a new page (database -> list) and then clicking on New button selectin the properties that are necessary.

Graph Machine Learning research groups: TylerDerr I do a series of posts on the groups in graph research, previous post is here. The 24th is Tyler Derr, a young professor graph ML, who proposed signed GNNs on graphs with negative links. Tyler Derr (~1992) - Affiliation: Vanderbilt University - Education: Ph.D. at Michigan State University in 2020 (advisors: Jiliang Tang) - h-index 10 - Awards: best papers at SDM - Interests: adversarial attacks, graph neural networks

Trapped in a Desert Maze: AlphaZero learns to deal with graphs A fun video and blog post about AlphaZero playing a simple game of node covering in graphs. I wish there is some human interface to play against these creatures.

Theoretical Foundations of Graph Neural Networks Video presentation by Petar Veličković who covers design, history, and applications of GNNs. A lot of interesting concepts such as permutation invariance and equivariance discussed. Slides can be found here.

Video and slides:GNN User Group meeting 2 In the second meeting of GNN user group, there is a discussion of new release of DGL, graph analytics on GPU, as well as new approaches for training GNNs, including those on disassortative graphs. Slides can be found in the slack channel.

Fresh picks from ArXiv This week on ArXiv: 2 surveys on self-supervised graph learning, fair embeddings, and combined structural and positional node embeddings 🎭 If I forgot to mention your paper, please shoot me a message and I will update the post. Survey * Graph Self-Supervised Learning: A Survey with Philip S. Yu * Graph-based Semi-supervised Learning: A Comprehensive Review * Meta-Learning with Graph Neural Networks: Methods and Applications * Benchmarking Graph Neural Networks on Link Prediction * A Survey of RDF Stores & SPARQL Engines for Querying Knowledge Graphs Embeddings * Towards a Unified Framework for Fair and Stable Graph Representation Learning with Marinka Zitnik * Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding with Danai Koutra

GML Newsletter: Homophily, Heterophily, and Oversmoothing for GNNs Apparently, Cora and OGB datasets are mostly assortative datasets, i.e. nodes of the same labels tend to be connected. In many real-world applications, it's not the case, i.e. nodes of different groups are connected, while within the groups the connections are sparse. Such datasets are called disassortative graphs. What has been realized in 2020 and now in 2021 is that typical GNNs like GCN do not work well in disassortative graphs. So several GNN architectures were proposed to get good performance for these datasets. Not only these new GNNs work well on assortative and disassortative graphs, but also they solve the problem of oversmoothing, i.e. effectively designing many layers for GNNs. In my new email newsletter I discuss this change from assortative to disassortative GNNs and its relation to oversmoothing. What's interesting is that existing approaches still do not rely explicitly on the labels, but rather learn parameters to account for heterophily. In the future, I think there will be more hacks how to integrate target labels directly into the GNN algorithm.

The Transformer Network for the Traveling Salesman Problem (video and slides) Another great tutorial from Xavier Bresson on traveling salesman problem (TSP) and recent ML approaches to solve it. It gives a nice overview of the current solvers such as Concorde or Gurobi and their computational complexity.

The Easiest Unsolved Problem in Graph Theory Our new blog post about reconstruction conjecture, a well-known graph theory problem with 80 years of results but no final proof yet. I have already written several posts in this channel about it and it to me it's one of the grand challenges in graph theory (along with graph isomorphism problem). It seems there is quite some progress, so I hope to see it being resolved during my lifetime. In the meantime, we considered graph families for which reconstruction conjecture is known to be true and tried to come up with the easiest family of graphs that is still not resolved and have very few vertices. The resulted family is a type of bidegreed graphs (close to regular) on 20 vertices, which is probably possible to verify on the computer (though it would take a year or so).

GNNSys'21 -- Workshop on Graph Neural Networks and Systems A graph-related workshop organized at MLSys 2021, with submission deadline of 7 of March. This could be particularly interesting as it would highlight applications of GNNs in the real production systems.

Fresh picks from ArXiv This week on ArXiv: improved generalization bound, deblurring images with Laplacians, and new datasets for drug discovery 💊 If I forgot to mention your paper, please shoot me a message and I will update the post. GNNs * Generalization bounds for graph convolutional neural networks via Rademacher complexity * SSFG: Stochastically Scaling Features and Gradients for Regularizing Graph Convolution Networks * Dissecting the Diffusion Process in Linear Graph Convolutional Networks * E(n) Equivariant Graph Neural Networks with Max Welling * Combinatorial optimization and reasoning with graph neural networks with Petar Veličković * Topological Graph Neural Networks with Karsten Borgwardt Applications * Graph Laplacian for image deblurring * Interpretable Stability Bounds for Spectral Graph Filters * On the Similarity between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications * A Review of Biomedical Datasets Relating to Drug Discovery: A Knowledge Graph Perspective with William Hamilton

GNN User Group: meeting 2 The second meeting of the GNN user group organized by AWS and Nvidia. There are 3 presentations about GNN on GPU, CuGraph, and learning mechanisms of GNN. The event is free.