AAAI 2020 is taking place tomorrow in NYC.

AAAI 2020 stats
7737 number of submissions
1591 number of accepted
21% acceptance rate
142 graph accepted papers (9% of total)

ICLR 2020 stats
2213 number of submissions
687 number of accepted
31% acceptance rate
49 graph accepted papers (7% of total)

Two tutorials on GML at AAAI 2020.

Graph Neural Networks: Models and Applications https://aaai.org/Conferences/AAAI-20/aaai20tutorials/#fa4

Differential Deep Learning on Graphs and its Applications https://aaai.org/Conferences/AAAI-20/aaai20tutorials/#fp1

KDD deadline is coming next week and it is one of the most popular places to submit strong GML paper, even though it is a general data mining conference, with all sorts of papers in computer science.

4 out of 5 last years, the best papers were assigned to graph research.

2019 Network Density of States
https://www.kdd.org/kdd2019/accepted-papers/view/network-density-of-states

2018 Adversarial Attacks on Neural Networks for Graph Data
https://www.kdd.org/kdd2018/accepted-papers/view/adversarial-attacks-on-neural-networks-for-graph-data

2016 FRAUDAR: Bounding Graph Fraud in the Face of Camouflage
https://www.kdd.org/kdd2016/subtopic/view/fraudar-bounding-graph-fraud-in-the-face-of-camouflage

2015 Efficient Algorithms for Public-Private Social Networks
https://ai.googleblog.com/2015/08/kdd-2015-best-research-paper-award.html

Tutorial slides from AAAI 20.

Graph Neural Networks: Models and Applications
https://cse.msu.edu/~mayao4/tutorials/aaai2020/

Differential Deep Learning on Graphs and its Applications
https://www.calvinzang.com/DDLG_AAAI_2020.html

Workshop materials from AAAI 20.

Workshop on Deep Learning on Graphs: Methodologies and Applications (DLGMA’20)
https://dlg2019.bitbucket.io/aaai20/

There are two big libraries to build and use GNN: Deep Graph Library (DGL) and PyTorch-Geometric (PTG).

I personally used only the latter, because it's been more popular, but it seems DGL is catching up.

* DGL is written for PyTorch, but TF is on its way.
* DGL 4K github stars vs PTG 6.5K.
* DGL has more support from academia and industry (e.g. available on AWS).
* DGL is faster (at least in their presentations).

There is a nice workshop video from NeurIPS 19 on DGL: https://slideslive.com/38921873/graph-representation-learning-4

There are also overlapping workshop slides from AAAI 20:
https://dlg2019.bitbucket.io/aaai20/keynote_slides/George-dgl-aaai2020.pdf

Fresh picks from ArXiv
ICML 20 submissions, AISTATS 20, graphs in math, and Stephen Hawking 👨‍🔬

ICML 2020 submissions
Fast Detection of Maximum Common Subgraph via Deep Q-Learning (https://arxiv.org/abs/2002.03129)
Random Features Strengthen Graph Neural Networks (https://arxiv.org/abs/2002.03155)
Hierarchical Generation of Molecular Graphs using Structural Motifs (https://arxiv.org/pdf/2002.03230.pdf)
Graph Neural Distance Metric Learning with Graph-Bert (https://arxiv.org/abs/2002.03427)
Segmented Graph-Bert for Graph Instance Modeling (https://arxiv.org/abs/2002.03283)
Haar Graph Pooling (https://arxiv.org/abs/1909.11580)
Constant Time Graph Neural Networks (https://arxiv.org/abs/1901.07868)

AISTATS 20
Laplacian-Regularized Graph Bandits: Algorithms and Theoretical Analysis (https://arxiv.org/abs/1907.05632)

Math
Some arithmetical problems that are obtained by analyzing proofs and infinite graphs (https://arxiv.org/abs/2002.03075)
Extra pearls in graph theory (https://arxiv.org/abs/1812.06627)
Distance Metric Learning for Graph Structured Data (https://arxiv.org/abs/2002.00727)

Surveys
Generalized metric spaces. Relations with graphs, ordered sets and automata : A survey (https://arxiv.org/abs/2002.03019)

Stephen Hawking 👨‍🔬
Stephen William Hawking: A Biographical Memoir (https://arxiv.org/abs/2002.03185)

More knowledge graphs to the god of knowledge graphs ⚡️

https://medium.com/@mgalkin/knowledge-graphs-aaai-2020-c457ad5aafc0

Manually-curated list of GML papers in top AI conferences 📚

https://github.com/naganandy/graph-based-deep-learning-literature

Combinatorial Optimization + ML

How can you solve traveling salesman problem (TSP) with ML? One way is to train the agent to make decisions about the next step. This requires that you either imitate already existing solutions or obtain the reward and then update the policy. This works if you have a solver to the problem which can generate solutions or if the problem is easy enough to converge to optimal value fast (e.g. Euclidean TSP).

For harder problems, you can integrate ML inside the solver (which has exponential runtime in the worst-case). So your solver still guarantees the optimality of the solutions but heuristic choices, which exist in most solvers, are done by ML. This is what Exact Combinatorial Optimization with Graph Convolutional Neural Networks (https://arxiv.org/abs/1906.01629) proposes for Branch & Bound procedure, which heuristically chooses the next node for branching. Results are quite impressive, showing that you can decrease the running time of SOTA solvers while preserving optimality, even if the branching choice of ML model does not have guarantees.

Graphs in Industry

What should be the order of authors in your ML paper?

The more you write papers, the more you ask questions like this.

On some occasions, it's a bit more subtle than you expect. For example, one guy did experiments and another made all the theory. Who should go first? It's not clear.

So I asked a few experienced professors and here are the insights:

* The first author is the one who did the most for the paper. If there is more than one, put a corresponding sign.
* The last places are reserved for supervisors.
* The middle are sorted by contribution.

But no one has any precise formula for computing contribution. So I proposed one.

Check it out in my latest blog post and clap if you like it 👏

WebConf 2020 stats (April 20-24, Taipei)

1129 number of submissions
217 accepted
19% acceptance rate
~30% graph papers

Graph Tutorials at WebConf 2020

Entity Summarization in Knowledge Graphs: Algorithms, Evaluation, and Applications by Nanjing University, Samsung, Bosch

Learning Graph Neural Networks with Deep Graph Library by Amazon

Constructing Knowledge Graph for Social Networks in A Deep and Holistic Way by LinkedIn

Mining signed networks: theory and applications by Aalto University

Graph Workshops at WebConf 2020

4th International Workshop on Mining Actionable Insights from Social Networks

The Fifth International Workshop on Deep Learning for Graphs

Network Science Institute at Northeastern University
networkscienceinstitute.org

With the director Albert-László Barabási, the focus is on biological networks, epidemiology, and formation.
They also have a YouTube channel with guest presentations on graph theory.

Fresh picks from ArXiv
ICML and KDD 20 submissions, AISTATS 20, Graph Isomorphism, and Review


ICML 20 submissions
Graph Convolutional Gaussian Processes For Link Prediction
When Labelled Data Hurts: Deep Semi-Supervised Classification with the Graph 1-Laplacian
Improving Graph Neural Network Representations of Logical Formulae with Subgraph Pooling
Differentiable Graph Module (DGM) for Graph Convolutional Network by group of Michael Bronstein
Deep Multi-Task Augmented Feature Learning via Hierarchical Graph Neural Network
Graph Universal Adversarial Attacks: A Few Bad Actors Ruin Graph Learning Models
Towards Similarity Graphs Constructed by Deep Reinforcement Learning by Yandex team
Connectivity-driven Communication in Multi-agent Reinforcement Learning through Diffusion Processes on Graphs
Explainable Deep Modeling of Tabular Data using TableGraphNet
Graph Filtration Learning
Graph Prolongation Convolutional Networks
Deep Coordination Graphs
Unifying Graph Convolutional Neural Networks and Label Propagation by group of Jure Leskovec

KDD 20 submissions
Disease State Prediction From Single-Cell Data Using Graph Attention Networks
Entity Context and Relational Paths for Knowledge Graph Completion by group of Jure Leskovec

Theory
Generalization and Representational Limits of Graph Neural Networks by group of Tommi Jaakkola

Graph Isomorphism
A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors
Isomorphism for Random k-Uniform Hypergraphs

Review
Hypergraphs: an introduction and review

Do Deep Graph Neural Networks exist?

One of the open questions in GNN literature is whether deep GNN, i.e. GNN with many layers (e.g. more than 10), is useful.

There is a theoretical paper, What graph neural networks cannot learn: depth vs width, that proves that at least the number of layers * the embedding size of each layer should be proportional to the number of the nodes in the graph if GNN can compute many Turing computable functions. So if a graph has 10K nodes, then d*w = O(10K). For example, common embedding size, w, is 128 or 256, which means that a number of layers should be 40.

There is a cost associated with each layer: each node has to look at every neighbor and aggregate its information. So most of the implementations have up to 5 layers for obvious reasons, it's very time-consuming to compute.

Somewhat contrary, another theoretical paper, Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, shows that under the certain conditions on the graph, GNN will essentially carry only degree information for each node, which is the most local property you can have for a node. This does not contradict the previous paper as (1) this paper works in a limit, (2) previous paper says that if d*w < O(n) then there is an instance of a graph for which GNN fails, which does not mean the result is universal for all graphs, and (3) this paper has certain conditions to hold which are only applicable to a narrow family of graphs.

Beyond this, there is a question of double descent, whether it occurs in GNN setting, which is yet the next question to solve.

So, my response is that for now we still have little understanding if deep GNN is useful and if so, how we can make them efficient in practice.

NeurIPS 2019 stats

6743 number of submissions
1428 accepted
21% acceptance rate
75 graph papers (5% of accepted)