On Explainability of Graph Neural Networks via Subgraph Explorations

This is a guest post by Shuiwang Ji about their recent work, accepted to ICML 2021.

Title: "On Explainability of Graph Neural Networks via Subgraph Explorations"

TL; DR:
- We propose a novel method, known as SubgraphX, to explain GNNs by exploring and identifying important subgraphs.
- We propose to incorporate the Monte Carlo tree search to explore subgraphs and propose efficient approximation schemes to measure subgraphs via Shapley values.
- Our proposed method consistently and significantly outperforms state-of-the-art techniques.
Code is now available as part of our DIG library.

We study the explainability of Graph Neural Networks and propose a novel method (SubgraphX) to provide subgraph-level explanations. While existing methods mainly focus on explaining GNNs with graph nodes or edges, we argue that subgraphs are more intuitive and human-intelligible.

In our SubgraphX, we propose to explore different subgraphs with the Monte Carlo tree search. For each subgraph, we measure its importance using Shapley values, which can capture the interactions among different graph structures. We further improve the efficiency with our proposed approximation schemes to compute Shapley values for graph data. Both quantitative and qualitative studies show our method obtain higher-quality and more human-intelligible explanations while keeping time complexity acceptable.

Our method represents the first attempt to explain GNNs by explicitly studying the subgraphs. We hope that this work can provide a new direction for the community to investigate the explainability of GNNs in the future.

GraphDF: A Discrete Flow Model for Molecular Graph Generation

This is a guest post by Shuiwang Ji about their recent work, accepted to ICML 2021.

Title: “GraphDF: A Discrete Flow Model for Molecular Graph Generation”

TL; DR:
- We propose GraphDF, a novel discrete latent variable model for molecular graph generation method.
- We propose to use invertible modulo shift transform to sequentially generate graph nodes and edges from discrete latent variables.
- Our proposed method outperforms prior methods on random generation, property optimization, and constrained optimization tasks.
Code is now available as part of our DIG library.

We study the molecular generation problem and propose a novel method (GraphDF) achieving new state-of-the-art performance. While prior methods use continuous latent variables, we argue that discrete latent variables are more suitable to model the categorical distribution of graph nodes and edges.

In our GraphDF, the molecular graph is generated by sequentially using modulo shift transform to convert a sampled discrete latent variable to the categorical number of the graph node or edge type. The use of discrete latent variables eliminates the bad effect of dequantization and models the underlying distribution of graph structures more accurately. The modulo shift transform captures conditional information from the last sub-graph by graph convolutional networks to ensure the order invariance. Comprehensive studies show that our method outperform prior methods on random generation, property optimization, and constrained optimization tasks.

Our method is the first work to model the density of complicated molecular graph data with discrete latent variables. We hope that it can provide a new insight for the community to explore more powerful graph generation models in the future.

Rethinking Graph Neural Architecture Search from Message-passing

With abundance of GNNs architectures it's natural to ask how to select the right architecture for your task. In a recent CVPR 2021 work propose a generic architecture that encompasses many existing GNNs, which is then optimized via gradient descent. After optimization resulted GNNs may get different architectures for each layer of GNNs.

Graph Machine Learning research groups: Yizhou Sun

I do a series of posts on the groups in graph research, previous post is here. The 28th is Yizhou Sun, a professor at UCLA, who co-authored a book on heterogeneous information networks.

Yizhou Sun (~1982)
- Affiliation: UCLA
- Education: Ph.D. at UIUC in 2012 (advisors: Jiawei Han)
- h-index 48
- Interests: heterogeneous information networks, self-supervised learning, community detection
- Awards: best research papers at KDD, ASONAM

Mathematicians Answer Old Question About Odd Graphs

A new post at Quanta about the work that settles the question (c. 1960s) of the biggest subgraph with all vertices having odd degree within that subgraph.

Fresh picks from ArXiv
This week on ArXiv: graph embeddings for drug discovery, new largest GNN, and a gym for solving combinatorial problems ⛹️‍

If I forgot to mention your paper, please shoot me a message and I will update the post.

Drug discovery
* Predicting Potential Drug Targets Using Tensor Factorisation and Knowledge Graph Embeddings
* Understanding the Performance of Knowledge Graph Embeddings in Drug Discovery with William L Hamilton

Software
* Dorylus: Affordable, Scalable, and Accurate GNN Training over Billion-Edge Graphs
* GNNIE: GNN Inference Engine with Load-balancing and Graph-Specific Caching

Combinatorics
* GraphSAT -- a decision problem connecting satisfiability and graph theory
* OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems

GNNs
* Residual Network and Embedding Usage: New Tricks of Node Classification with Graph Convolutional Networks

Survey
* Federated Graph Learning -- A Position Paper

NAACL-2021 Papers

A list of accepted papers to NLP conference NAACL-2021 is available at digest console. There are ~40 graph papers out of 476 papers.

TechViz - The Data Science Guy

A nice YouTube playlist explaining in details many works on graph embeddings.

GNN User Group: meeting 5

Fifth meeting of GNN user group will include talks from:

* 4:00 - 4:25 (PST): Graphite: GRAPH-Induced feaTure Extraction for Point Cloud Registration (Mahdi Saleh, TUM).
* 4:25 - 4:50 (PST): Optimizing Graph Transformer Networks with Graph-based Techniques (Loc Hoang, University of Texas at Austin)
* 4:50 - 5:15 (PST): Encoding the Core Business Entities Using Meituan Brain (Mengdi Zhang, Meituan)
* 5:15 - 5:30 (PST): Open Discussion and Networking

Please join us today, 27 May! Zoom link in the description.

Reinforcement learning for combinatorial optimization: A survey

Our work that surveys recent RL methods for solving combinatorial optimization problems is accepted at Computers & Operations Research journal.

This is very active field right now and it shows a lot of promise. Traditionally, NP-hard problems such as Traveling Salesman Problem were solved by algorithms, that were designed specifically for each problem. With RL, it's possible to extend the toolbox by learning a function on available data. I really hope that in 10 years from now using ML approaches for combinatorial problems will be a commonplace.

Fresh picks from ArXiv
This week on ArXiv: equivariant GNNs to new groups, new metrics for graph similarity, and parsing emotions with GNNs 😢‍

If I forgot to mention your paper, please shoot me a message and I will update the post.

GNNs
* How Attentive are Graph Attention Networks?
* Symmetry-driven graph neural networks
* Graph Similarity Description: How Are These Graphs Similar? KDD 2021
* SLGCN: Structure Learning Graph Convolutional Networks for Graphs under Heterophily
* Linguistic Structures as Weak Supervision for Visual Scene Graph Generation CVPR 2021
* Directed Acyclic Graph Network for Conversational Emotion Recognition ACL 2021
* On the Universality of Graph Neural Networks on Large Random Graphs
* Differentially Private Densest Subgraph Detection ICML 2021

Survey
* Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future
* A Comprehensive Survey on Community Detection with Deep Learning
* A Survey of the Bridge Between Combinatorics and Probability

Graph papers at ICML 2021

ICML 2021 papers are announced, here is some analysis on this.

There are about 58 graph papers (if I didn't mention your paper, let me know, I'll fix it).

The top authors are displayed.

Almost Free Inductive Embeddings Out-Perform Trained Graph Neural Networks in Graph Classification in a Range of Benchmarks

A nice blog post by Vadym Safronov (in Russian also here) which shows that you can use not-trained GCN to match or exceed performance of end-to-end trained GCN on graph classification benchmarks.

Graph Machine Learning research groups: Gal Chechik

I do a series of posts on the groups in graph research, previous post is here. The 29th is Gal Chechik, a professor at the Gonda Brain research institute and a director of AI at NVIDIA in Israel.

Gal Chechik (~1976)
- Affiliation: Bar Ilan University, Israel; NVIDIA
- Education: Ph.D. at Hebrew University, Israel in 2004 (advisors: Naftali Tishby and Israel Nelken)
- h-index 37
- Interests: biological systems, theory of GNNs, equivariant functions.
- Awards: best papers at ICML, ISMB; fullbright fellowship, Alon fellowship

Pytorch Geometric tutorial: Special Guest: Matthias Fey

A recent talk by Matthias Fey, a founder of pytorch geometric library, about the news and future directions of the library. Large-scale graphs, sparse tensors, pytorch lightning, torchscript, and more.

Fresh picks from ArXiv
This week on ArXiv: self-supervised approach without negatives, review of generative models, and semantic search at AliBaba 👞

If I forgot to mention your paper, please shoot me a message and I will update the post.

GNNs
* Neural message passing for joint paratope-epitope prediction with Petar Veličković
* Graph Infomax Adversarial Learning for Treatment Effect Estimation with Networked Observational Data KDD 21
* GraphMI: Extracting Private Graph Data from Graph Neural Networks IJCAI 21
* Graph Barlow Twins: A self-supervised representation learning framework for graphs
* Motif Prediction with Graph Neural Networks
* SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks

Algorithms
* AliCG: Fine-grained and Evolvable Conceptual Graph Construction for Semantic Search at Alibaba KDD 2021
* Stochastic Iterative Graph Matching ICML 2021
* Convergent Graph Solvers

Survey
* Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions with Karsten Borgwardt
* Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey
* Graph-based Deep Learning for Communication Networks: A Survey

Graph Neural Networking Challenge 2021

An interesting competition, organized by Technical University of Catalonia (UPC) and ITU, about building GNNs to predict source-destination routing time. The goal is to test generalization abilities of GNNs: training on small graphs and testing on much larger graphs.

Udemy Graph Neural Network course

Online course at Udemy that covers the basics of representation learning on graphs (e.g. DeepWalk, node2vec) and popular GNN architectures, plus some PyG implementations.

Deep Learning on Graphs for Natural Language Processing

Interesting tutorial at NAACL 2021 about applications of graph models to NLP tasks such as text classification, semantic parsing, machine translation, and more. It's based on Graph4NLP library and the slides are available here.

Graphs at ICLR 2021

Very good digest of a few graph papers at ICLR 2021. Talks about new GNNS to solve overmoothing, over-squashing, heterophily, and attention problems.

PyTorch-Geometric Tutorial Talk

Today, I will speak about our ICLR work "Boost then Convolve: Gradient Boosting Meets Graph Neural Networks". If you want to learn more about how GBDT and GNN work, and how they can be applied successfully for node prediction tasks, please join here at 15 (Paris time).