โ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.
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.
โ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.
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.
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.
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.
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.
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.
โScene Graph Generation by Iterative Message Passing
There are numerous applications of graphs in computer vision, which usually boil down to reduction of the image to a sparse graph. This has found applications in image captioning, human action identification, predicting trajectories, or transferring knowledge to new data sets, among others (see Applications section from this survey). One of the recent interesting advancements is from 2017 CVPR paper (a group of Fei-Fei Li), Scene Graph Generation by Iterative Message Passing, where the authors proposed an image encoder that produces essentially a knowledge graph of objects in the image and their relationships, which can be then used for downstream tasks.
There are numerous applications of graphs in computer vision, which usually boil down to reduction of the image to a sparse graph. This has found applications in image captioning, human action identification, predicting trajectories, or transferring knowledge to new data sets, among others (see Applications section from this survey). One of the recent interesting advancements is from 2017 CVPR paper (a group of Fei-Fei Li), Scene Graph Generation by Iterative Message Passing, where the authors proposed an image encoder that produces essentially a knowledge graph of objects in the image and their relationships, which can be then used for downstream tasks.
Applications of graphs in NLP
In addition to computer vision, there are many applications of graphs to NLP too. For example, knowledge graphs have been used extensively in research to bring fact knowledge to dialogue and question-answering systems, besides approaches for commonsense reasoning and named entity recognition (see these conference reviews of NLP+KG domains by Michael Galkin). And sometimes you even get more technical papers in this domain, like in this video Relation Embedding with Dihedral Group in Knowledge Graph of ACL '19 paper, where the authors model composition of relationships with some group theory.
In addition to computer vision, there are many applications of graphs to NLP too. For example, knowledge graphs have been used extensively in research to bring fact knowledge to dialogue and question-answering systems, besides approaches for commonsense reasoning and named entity recognition (see these conference reviews of NLP+KG domains by Michael Galkin). And sometimes you even get more technical papers in this domain, like in this video Relation Embedding with Dihedral Group in Knowledge Graph of ACL '19 paper, where the authors model composition of relationships with some group theory.
Medium
Michael Galkin โ Medium
Read writing from Michael Galkin on Medium. AI Research Scientist @ Intel Labs. Working on Graph ML, Geometric DL, and Knowledge Graphs. Every day, Michael Galkin and thousands of other voices read, write, and share important stories on Medium.
The forbidden sidetrip by Lรกszlรณ Babai.
Lรกszlรณ Babai, the top mathematician in the field of graph isomorphism, turns out, has a zingy autobiographical story called "The forbidden sidetrip" about his trip to Minsk, Moscow, and Leningrad, when it was 1978 and he was 28. It's just fun on its own, but it also contains lots of names of Soviet mathematicians and references about the places where and how math was being built in the late USSR. To my surprise, he knows (knew?) Russian quite well (originally Hungarian) to listen to lectures in the universities.
There are stories about how he generally despises anti-semitism by another talented Russian mathematician Pontryagin, and how he was getting into the soviet queues before knowing what they sell, and how you can give "chervonets sverhu" (i.e. greasing the palm) to get the ticket when they are sold out, and lots of other soviet-related stuff that I really love asking older generation about. But among others, it's just interesting to look at the young, not-yet-famous guy who will then climb to the olymp of mathematics. I wish there was a movie about it.
Lรกszlรณ Babai, the top mathematician in the field of graph isomorphism, turns out, has a zingy autobiographical story called "The forbidden sidetrip" about his trip to Minsk, Moscow, and Leningrad, when it was 1978 and he was 28. It's just fun on its own, but it also contains lots of names of Soviet mathematicians and references about the places where and how math was being built in the late USSR. To my surprise, he knows (knew?) Russian quite well (originally Hungarian) to listen to lectures in the universities.
There are stories about how he generally despises anti-semitism by another talented Russian mathematician Pontryagin, and how he was getting into the soviet queues before knowing what they sell, and how you can give "chervonets sverhu" (i.e. greasing the palm) to get the ticket when they are sold out, and lots of other soviet-related stuff that I really love asking older generation about. But among others, it's just interesting to look at the young, not-yet-famous guy who will then climb to the olymp of mathematics. I wish there was a movie about it.
โHow powerful are graph neural networks? Part II
This is the second insight I recently got from the paper, How powerful are graph neural networks. It's about the initial node features. In the paper they write:
This is the second insight I recently got from the paper, How powerful are graph neural networks. It's about the initial node features. In the paper they write:
This first X (which is in latex \mathcal{X}) is the set of all input features. What this theorem says is that you need to have input features that are countable. Countable means rational or categorical, but not irrational numbers. So this condition "prohibits" any "continuous" features such as real numbers (e.g. degrees). If your set of features is uncountable then the sum is not injective anymore and hence GNN becomes less powerful than 1-WL test. So that's why if you use one-hot encoding of features your GNN becomes theoretically more powerful.
GraphChallenge
Challenges such as YOHO, MNIST, HPC Challenge, ImageNet, and VAST have played important roles in driving progress in fields as diverse as machine learning, high performance computing, and visual analytics.
GraphChallenge encourages community approaches to developing new solutions for analyzing graphs and sparse data derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field.
Challenges such as YOHO, MNIST, HPC Challenge, ImageNet, and VAST have played important roles in driving progress in fields as diverse as machine learning, high performance computing, and visual analytics.
GraphChallenge encourages community approaches to developing new solutions for analyzing graphs and sparse data derived from social media, sensor feeds, and scientific data to enable relationships between events to be discovered as they unfold in the field.
Fresh picks from ArXiv
This week presents a new challenge on the computing of triangles, connection between graphs and prime numbers, and as usual submissions to ICML ๐
Survey
โข Pre-trained Models for Natural Language Processing: A Survey
โข Survey of Privacy-Preserving Collaborative Filtering
WebConf 20
โข What is Normal, What is Strange, and What is Missing in a Knowledge Graph: Unified Characterization via Inductive Summarization
ICML 20
โข Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks
โข Probabilistic Dual Network Architecture Search on Graphs
Applications
โข GFTE: Graph-based Financial Table Extraction
โข GraphChallenge.org Triangle Counting Performance
Graph Theory
โข Classification of vertex-transitive digraphs via automorphism group
โข A Graph Theoretic Formula for the Number of Primes ฯ(n)
โข Large cycles in essentially 4-connected graphs
โข Countable graphs are majority 3-choosable
This week presents a new challenge on the computing of triangles, connection between graphs and prime numbers, and as usual submissions to ICML ๐
Survey
โข Pre-trained Models for Natural Language Processing: A Survey
โข Survey of Privacy-Preserving Collaborative Filtering
WebConf 20
โข What is Normal, What is Strange, and What is Missing in a Knowledge Graph: Unified Characterization via Inductive Summarization
ICML 20
โข Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks
โข Probabilistic Dual Network Architecture Search on Graphs
Applications
โข GFTE: Graph-based Financial Table Extraction
โข GraphChallenge.org Triangle Counting Performance
Graph Theory
โข Classification of vertex-transitive digraphs via automorphism group
โข A Graph Theoretic Formula for the Number of Primes ฯ(n)
โข Large cycles in essentially 4-connected graphs
โข Countable graphs are majority 3-choosable
Deep Weisfeiler Leman
Surprisingly this paper is not about applying deep neural networks to Weisfeiler Lehman algorithm. It's quite technical but well-written and I could understand the main results and ideas of the paper.
They propose an extension of k-WL algorithm, when instead of adding all k-tuples to the input graph at each iteration, they add only a subset of k-tuples. Because you reduce the size of the graph comparing to the original k-WL algorithm, your DeepWL algorithm becomes more efficient, and hence they show that it can solve some graphs in polynomial time that original k-WL algorithm cannot (in particular CFI graphs).
Surprisingly this paper is not about applying deep neural networks to Weisfeiler Lehman algorithm. It's quite technical but well-written and I could understand the main results and ideas of the paper.
They propose an extension of k-WL algorithm, when instead of adding all k-tuples to the input graph at each iteration, they add only a subset of k-tuples. Because you reduce the size of the graph comparing to the original k-WL algorithm, your DeepWL algorithm becomes more efficient, and hence they show that it can solve some graphs in polynomial time that original k-WL algorithm cannot (in particular CFI graphs).
Limitations of GNN
A compiled version of the recent insights I gained from the recent studies on theoretical properties of GNN.
A compiled version of the recent insights I gained from the recent studies on theoretical properties of GNN.
Medium
Limitations of Graph Neural Networks
Reading between the lines of the latest advancements in GML.
Graph Machine Learning research groups: Le Song
I do a series of posts on the groups in graph research. The second is Le Song.
His group had 7 accepted papers at ICLR 2020. The top-2 result after Sergey Levine.
Le Song (~1981)
- Affiliation: Georgia Institute of Technology;
- Education: Ph.D. at U. of Sydney in 2008 (supervised by Alex Smola);
- h-index: 59;
- Awards: best papers at ICML, NeurIPS, AISTATS;
- Interests: generative and adversarial graph models, social network analysis, diffusion models.
I do a series of posts on the groups in graph research. The second is Le Song.
His group had 7 accepted papers at ICLR 2020. The top-2 result after Sergey Levine.
Le Song (~1981)
- Affiliation: Georgia Institute of Technology;
- Education: Ph.D. at U. of Sydney in 2008 (supervised by Alex Smola);
- h-index: 59;
- Awards: best papers at ICML, NeurIPS, AISTATS;
- Interests: generative and adversarial graph models, social network analysis, diffusion models.
Chess is the Drosophila of Artificial Intelligence
While writing another post on the life of Andrei Leman, I found that John McCarthy, the creator of Lisp, author of the term Artificial Intelligence, and one of the first and most influential programmers has an interesting remark, where he discusses the importance of long-term research. Apparently this saying, Chess is the Drosophila of Artificial Intelligence, is attributed to a legendary Soviet scientist, Alexander Kronrod, who arguably founded the first AI lab in the USSR. Back in '70s there were some huge ICL machines (analog of IBM machines), people used punch cards to provide the input, and calculations lasted for days, without the possibility to run a program in parallel. Yet, Kronrod's lab, which included Weisfeiler, Leman, and many other famous CS scientists and engineers, were working among others on the development of the chess programs, which in 1974, by the name Kaissa, won the first international chess tournament among machines.
While writing another post on the life of Andrei Leman, I found that John McCarthy, the creator of Lisp, author of the term Artificial Intelligence, and one of the first and most influential programmers has an interesting remark, where he discusses the importance of long-term research. Apparently this saying, Chess is the Drosophila of Artificial Intelligence, is attributed to a legendary Soviet scientist, Alexander Kronrod, who arguably founded the first AI lab in the USSR. Back in '70s there were some huge ICL machines (analog of IBM machines), people used punch cards to provide the input, and calculations lasted for days, without the possibility to run a program in parallel. Yet, Kronrod's lab, which included Weisfeiler, Leman, and many other famous CS scientists and engineers, were working among others on the development of the chess programs, which in 1974, by the name Kaissa, won the first international chess tournament among machines.
Fresh picks from ArXiv
This week ranges applications of graphs from social studies to astrophysics to robotics ๐ค Also checkout latest survey of deep learning impact on scientific discovery by Eric Schmidt, ex-Google CEO ๐ And lots of other coolest graph papers from last week.
Applications
โข Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers โ combinatorial optimization
โข A Heterogeneous Dynamical Graph Neural Networks Approach to Quantify Scientific Impact โ scientific impact
โข Investigating Software Usage in the Social Sciences: A Knowledge Graph Approach โ social sciences
โข Graph Neural Networks for Particle Reconstruction in High Energy Physics detectors โ physics
โข Representing Multi-Robot Structure through Multimodal Graph Embedding for the Selection of Robot Teams โ robotics
โข Identification of Patterns in Cosmic-Ray Arrival Directions using Dynamic Graph Convolutional Neural Networks โ astrophysics
Survey
โข word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data by Martin Grohe
โข A Survey of Deep Learning for Scientific Discovery by Eric Schmidt (ex-Google CEO)
โข COVID-19 and Computer Audition: An Overview on What Speech & Sound Analysis Could Contribute in the SARS-CoV-2 Corona Crisis
CVPR
โข Distillating Knowledge from Graph Convolutional Networks
GNN
โข Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks
Graph Theory
โข The 1-2-3 Conjecture holds for graphs with large enough minimum degree
โข Bounds for the rainbow disconnection number of graphs
This week ranges applications of graphs from social studies to astrophysics to robotics ๐ค Also checkout latest survey of deep learning impact on scientific discovery by Eric Schmidt, ex-Google CEO ๐ And lots of other coolest graph papers from last week.
Applications
โข Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers โ combinatorial optimization
โข A Heterogeneous Dynamical Graph Neural Networks Approach to Quantify Scientific Impact โ scientific impact
โข Investigating Software Usage in the Social Sciences: A Knowledge Graph Approach โ social sciences
โข Graph Neural Networks for Particle Reconstruction in High Energy Physics detectors โ physics
โข Representing Multi-Robot Structure through Multimodal Graph Embedding for the Selection of Robot Teams โ robotics
โข Identification of Patterns in Cosmic-Ray Arrival Directions using Dynamic Graph Convolutional Neural Networks โ astrophysics
Survey
โข word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data by Martin Grohe
โข A Survey of Deep Learning for Scientific Discovery by Eric Schmidt (ex-Google CEO)
โข COVID-19 and Computer Audition: An Overview on What Speech & Sound Analysis Could Contribute in the SARS-CoV-2 Corona Crisis
CVPR
โข Distillating Knowledge from Graph Convolutional Networks
GNN
โข Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks
Graph Theory
โข The 1-2-3 Conjecture holds for graphs with large enough minimum degree
โข Bounds for the rainbow disconnection number of graphs
arXiv.org
Representing Multi-Robot Structure through Multimodal Graph...
Multi-robot systems of increasing size and complexity are used to solve
large-scale problems, such as area exploration and search and rescue. A key
decision in human-robot teaming is dividing a...
large-scale problems, such as area exploration and search and rescue. A key
decision in human-robot teaming is dividing a...
CS 520: Knowledge Graphs
Today starts a Stanford course on knowledge graphs. It's available for everyone for free via Zoom (although there is no guarantee to have the videos afterwards).
Today starts a Stanford course on knowledge graphs. It's available for everyone for free via Zoom (although there is no guarantee to have the videos afterwards).
Graph Isomorphism Software
Open-source software for finding isomorphism or canonical forms of graphs.
* Nauty/Traces
* Bliss
* saucy
* conauto
* Gi-ext
Open-source software for finding isomorphism or canonical forms of graphs.
* Nauty/Traces
* Bliss
* saucy
* conauto
* Gi-ext
pallini.di.uniroma1.it
Nauty Traces โ Home
Nauty Traces Home: Graph canonical labeling and automorphism group computation for graph isomorphism
CS 520: Knowledge Graphs
There is no promise for the materials afterwards, but here is a page where presentations can be stored (so far there is a single presentation from Michael Galkin).
There is no promise for the materials afterwards, but here is a page where presentations can be stored (so far there is a single presentation from Michael Galkin).