Manually-curated list of GML papers in top AI conferences 📚
https://github.com/naganandy/graph-based-deep-learning-literature
https://github.com/naganandy/graph-based-deep-learning-literature
GitHub
GitHub - naganandy/graph-based-deep-learning-literature: links to conference publications in graph-based deep learning
links to conference publications in graph-based deep learning - 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.
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.
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 👏
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 👏
Medium
What should be the order of authors in your ML paper?
Answering this sometimes is harder than the P=NP question.
WebConf 2020 stats (April 20-24, Taipei)
1129 number of submissions
217 accepted
19% acceptance rate
~30% graph papers
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
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
Google
Entity Summarization Tutorials - WWW 2020
Entity Summarization in Knowledge Graphs: Algorithms, Evaluation, and Applications
Knowledge graphs encapsulate entities and relationships that describe the entities. The concise representation format and graph nature of knowledge graphs have resulted in…
Knowledge graphs encapsulate entities and relationships that describe the entities. The concise representation format and graph nature of knowledge graphs have resulted in…
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.
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
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.
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.
OpenReview
What graph neural networks cannot learn: depth vs width
Several graph problems are impossible unless the product of a graph neural network's depth and width exceeds a polynomial of the graph size.
NeurIPS 2019 stats
6743 number of submissions
1428 accepted
21% acceptance rate
75 graph papers (5% of accepted)
6743 number of submissions
1428 accepted
21% acceptance rate
75 graph papers (5% of accepted)
Ringel’s conjecture is proved.
Ringel's conjecture states that every complete graph with
This conjecture was known for 60 years and finally has been proved last month. At last this article makes a good job explaining how it was done.
Ringel's conjecture states that every complete graph with
2n+1 nodes can be decomposed into a set of any identical non-overlapping trees of order n. In other words, take any tree with n nodes, place it on the complete graph with 2n+1 nodes, remove the edges your tree covers, and continue with the remaining graph. No matter which tree you have started with, there is a procedure to remove all the edges in a complete graph by placing your tree step by step. This conjecture was known for 60 years and finally has been proved last month. At last this article makes a good job explaining how it was done.
Quanta Magazine
Rainbow Proof Shows Graphs Have Uniform Parts
Mathematicians have proved that copies of smaller graphs can always be used to perfectly cover larger ones.
Visualization of small graphs and corresponding statistics.
https://dominikschmidt.xyz/spectral-clustering-exp/
https://dominikschmidt.xyz/spectral-clustering-exp/
dominikschmidt.xyz
Spectral Clustering on Graphs
Graph ML Surveys
A good way to start in this domain is to read what people already have done.
Videos
* Learning on Non-Euclidean Domains
* Stanford Course CS 224w
GNN
* Graph Neural Networks: A Review of Methods and Applications 2018
* A Comprehensive Survey on Graph Neural Networks 2019
* A Gentle Introduction to Deep Learning for Graphs 2019
* Deep Learning on Graphs: A Survey 2018
* Relational inductive biases, deep learning, and graph networks 2018
* Geometric deep learning: going beyond Euclidean data 2016
* Graph Neural Networks for Small Graph and Giant Network Representation Learning: An Overview 2019
* Machine Learning on Graphs: A Model and Comprehensive Taxonomy 2020
Graph kernels
* A Survey on Graph Kernels 2019
* Graph Kernels: A Survey 2019
Adversarial Attacks
* Adversarial Attack and Defense on Graph Data: A Survey 2018
Representation Learning
* Learning Representations of Graph Data -- A Survey 2019
* Representation Learning on Graphs: Methods and Applications 2017
* Representation Learning for Dynamic Graphs: A Survey 2020 JMLR
Books
Graph Representation Learning Book by Will Hamilton
Deep Learning on Graphs by Yao Ma and Jiliang Tang
A good way to start in this domain is to read what people already have done.
Videos
* Learning on Non-Euclidean Domains
* Stanford Course CS 224w
GNN
* Graph Neural Networks: A Review of Methods and Applications 2018
* A Comprehensive Survey on Graph Neural Networks 2019
* A Gentle Introduction to Deep Learning for Graphs 2019
* Deep Learning on Graphs: A Survey 2018
* Relational inductive biases, deep learning, and graph networks 2018
* Geometric deep learning: going beyond Euclidean data 2016
* Graph Neural Networks for Small Graph and Giant Network Representation Learning: An Overview 2019
* Machine Learning on Graphs: A Model and Comprehensive Taxonomy 2020
Graph kernels
* A Survey on Graph Kernels 2019
* Graph Kernels: A Survey 2019
Adversarial Attacks
* Adversarial Attack and Defense on Graph Data: A Survey 2018
Representation Learning
* Learning Representations of Graph Data -- A Survey 2019
* Representation Learning on Graphs: Methods and Applications 2017
* Representation Learning for Dynamic Graphs: A Survey 2020 JMLR
Books
Graph Representation Learning Book by Will Hamilton
Deep Learning on Graphs by Yao Ma and Jiliang Tang
CS236605: Deep Learning
Lecture 11: Learning on Non-Euclidean Domains
Toeplitz operators, graphs, fields, gradients, divergence, Laplace-Beltramioperator, non-euclidean convolution, spectral and spatial CNN for graphs.
Fresh picks from ArXiv
More ICML and KDD submissions and large body on mathematical graph theory 📖
ICML
Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
Neural Networks on Random Graphs
Embedding Graph Auto-Encoder with Joint Clustering via Adjacency Sharing
Adaptive Graph Auto-Encoder for General Data Clustering
Computationally Tractable Riemannian Manifolds for Graph Embeddings
Set2Graph: Learning Graphs From Sets
Node Masking: Making Graph Neural Networks Generalize and Scale Better
Deep Graph Mapper: Seeing Graphs through the Neural Lens
Learning Dynamic Knowledge Graphs to Generalize on Text-Based Games by Microsoft and group of William L. Hamilton
Learning to Simulate Complex Physics with Graph Networks by Deepmind + group of Jure Leskovec
KDD
Self-Enhanced GNN: Improving Graph Neural Networks UsingModel Outputs
Graph4Code: A Machine Interpretable Knowledge Graph for Code
Localized Flow-Based Clustering in Hypergraphs by group of Jon Kleinberg
WWW
Beyond Clicks: Modeling Multi-Relational Item Graph for Session-Based Target Behavior Prediction
Graph Theory
Building large k-cores from sparse graphs
Distributed graph problems through an automata-theoretic lens
Computing the k Densest Subgraphs of a Graph
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Planar graphs have bounded queue-number
Review
Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
More ICML and KDD submissions and large body on mathematical graph theory 📖
ICML
Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
Neural Networks on Random Graphs
Embedding Graph Auto-Encoder with Joint Clustering via Adjacency Sharing
Adaptive Graph Auto-Encoder for General Data Clustering
Computationally Tractable Riemannian Manifolds for Graph Embeddings
Set2Graph: Learning Graphs From Sets
Node Masking: Making Graph Neural Networks Generalize and Scale Better
Deep Graph Mapper: Seeing Graphs through the Neural Lens
Learning Dynamic Knowledge Graphs to Generalize on Text-Based Games by Microsoft and group of William L. Hamilton
Learning to Simulate Complex Physics with Graph Networks by Deepmind + group of Jure Leskovec
KDD
Self-Enhanced GNN: Improving Graph Neural Networks UsingModel Outputs
Graph4Code: A Machine Interpretable Knowledge Graph for Code
Localized Flow-Based Clustering in Hypergraphs by group of Jon Kleinberg
WWW
Beyond Clicks: Modeling Multi-Relational Item Graph for Session-Based Target Behavior Prediction
Graph Theory
Building large k-cores from sparse graphs
Distributed graph problems through an automata-theoretic lens
Computing the k Densest Subgraphs of a Graph
Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems
Planar graphs have bounded queue-number
Review
Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
Reinforcement Learning for Combinatorial Optimization: A Survey
Our new submission to IJCAI survey track. We surveyed all of the literature we found on applying RL methods for combinatorial optimization problems (e.g. TSP, Knapsack, MaxCut).
There are three types of the RL approaches we categorized the papers: Value-based, Policy-based, and Monte-Carlo Tree Search based. This is one of the domains that appeared very recently, a few years ago, and has an increasing number of successful applications to traditional problems each year. I would say it's a good topic for a fresh Ph.D. student to start working on.
Our new submission to IJCAI survey track. We surveyed all of the literature we found on applying RL methods for combinatorial optimization problems (e.g. TSP, Knapsack, MaxCut).
There are three types of the RL approaches we categorized the papers: Value-based, Policy-based, and Monte-Carlo Tree Search based. This is one of the domains that appeared very recently, a few years ago, and has an increasing number of successful applications to traditional problems each year. I would say it's a good topic for a fresh Ph.D. student to start working on.
Recent approaches to Graph Convolutional Networks, Graph Representation Learning and Reinforcement Learning
Surprisingly discovered a local workshop on GML with strong list of keynote speakers. Free of charge 🤫
https://gcn-grl-rl.sciencesconf.org/
Surprisingly discovered a local workshop on GML with strong list of keynote speakers. Free of charge 🤫
https://gcn-grl-rl.sciencesconf.org/
ML and NLP Publications in 2019
One of the reasons why I have this channel is to encourage people do more research in general. And looking at the recent analysis of the number of accepted papers by countries you can understand why.
USA has almost as much publications last year as all other countries combined.
In particular, it's 2.5x > China, 6x > UK, and 100x > Russia.
The reasons are obvious, USA spends more budget on research from both government and industry, but also the culture of doing research is different: making a publication at top conferences is considered a big deal and a lot of efforts is put on this, — which can definitely adopted by other countries.
One of the reasons why I have this channel is to encourage people do more research in general. And looking at the recent analysis of the number of accepted papers by countries you can understand why.
USA has almost as much publications last year as all other countries combined.
In particular, it's 2.5x > China, 6x > UK, and 100x > Russia.
The reasons are obvious, USA spends more budget on research from both government and industry, but also the culture of doing research is different: making a publication at top conferences is considered a big deal and a lot of efforts is put on this, — which can definitely adopted by other countries.