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.

​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 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.

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

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).

Limitations of GNN

A compiled version of the recent insights I gained from the recent studies on theoretical properties of GNN.

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.

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.

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

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).

Graph Isomorphism Software

Open-source software for finding isomorphism or canonical forms of graphs.

* Nauty/Traces
* Bliss
* saucy
* conauto
* Gi-ext

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).

​Deep Graph Library v0.4.3

In version 0.4.3, a popular GNN library DGL has now support for TensorFlow (originally supported PyTorch only), spin-off packages for Knowledge Graphs and Life Sciences (DGL-KE and DGL-LifeSci) and more flexible distributed training.

For me it's really interesting to see a big uplift in training time against PyTorch-BigGraph library, this looks great.

Knowledge Graph course 2019

Michael Galkin had a course on knowledge graphs in 2019 and there are presentations of the course (though most in Russian) if you are interested.

Network Epidemiology Online Workshop Series

In April, there are seminars, tutorials, and discussion groups organized by University of Maryland to study how network science can help fighting virus contamination. It's for free, although there is a limitation on the number of participants (~150). There are two tracks: just listen to the tutorials or additionally participate in the groups. Lectures through Zoom. Deadline for application: tomorrow, 7th April.

CS 520 Knowledge Graphs Video Materials

It seems that they will make the lectures available on YouTube 👍

Fresh picks from ArXiv
This week is full of CVPR papers with graphs, surveys on recommendation, and a historical note of the discovery of TSP algorithm is USSR 👨‍🚀

CVPR
• HOPE-Net: A Graph-based Model for Hand-Object Pose Estimation
• Graph Structured Network for Image-Text Matching
• Spatio-Temporal Graph for Video Captioning with Knowledge Distillation
• Multi-Modal Graph Neural Network for Joint Reasoning on Vision and Scene Text
• Disentangling and Unifying Graph Convolutions for Skeleton-Based Action Recognition
• Deep Homography Estimation for Dynamic Scenes
• Iterative Context-Aware Graph Inference for Visual Dialog
• Geometrically Principled Connections in Graph Neural Networks with Michael Bronstein
• LiDAR-based Online 3D Video Object Detection with Graph-based Message Passing and Spatiotemporal Transformer Attention

WebConf
• Graph Enhanced Representation Learning for News Recommendation

Survey
• Deep Learning on Knowledge Graph for Recommender System: A Survey
• Heterogeneous Network Representation Learning: Survey, Benchmark, Evaluation, and Beyond — essentially a survey on KG
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem — show that Christofides algorithm used for TSP was discovered in USSR around the same time
• A Survey on Conversational Recommender Systems

Graph Theory
• Longest paths in random hypergraphs
• A Fast Algorithm for the Product Structure of Planar Graphs
• Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs"

RL for TSP

There is already a rich literature on applying RL methods for Traveling Salesman Problem (TSP). In one line of research the solution is built incrementally, one node at a time. This is for example in a popular paper, Attention, Learn to Solve Routing Problems!. Recently another approach appeared: start with some solution to TSP and update this solution by swapping nodes. For example, Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning uses policy gradient method and shows that it significantly outperforms incremental approaches.

Graph Representation Learning Workshop ICML 20

One of the places that gather a lot of researchers in GML is the workshop on Graph Representation Learning. This year it will appear at ICML 20. You can submit short papers (4 pages), including the works that you can resubmit later to a full conference elsewhere. This year there will be a separate track on using graphs for COVID-19 resolution. Deadline: 29th May.

Some notes on reconstruction conjecture

Studying reconstruction conjecture is going down the rabbit hole 🐇 It seems so simple, but after a few steps its complexity unfolds and you find yourself reading another paper that provides some extra insights which only steer you away from the target.

Formulation. You have a graph. You delete one vertex from it, and put obtained subgraph to a list, called deck. Then you return to the original graph, delete another vertex and again add obtained subgraph to the deck. And so on, for all n different vertices. The main question is whether there are two non-isomorphic graphs that have the same deck.

Difficulty. I already wrote about this conjecture, showing that if you delete more than 1 vertex then there are indeed two different graphs with the same decks. That's the fact that you delete only one vertex makes it more difficult. Now think, you have n subgraphs, each has (n-1) original vertices, it seems you just have so much information as an input, O(n^3), to say everything about the original graph, which has only O(n^2). But no, it's still very hard to solve it.

So what if we have a deck instead and try to recover original graph. Can we do it fast? I'm maybe wrong, but it seems there is no known polynomial-time algorithms and even the complexity of this problem is not clear. This paper, for specific type of graphs, shows an algorithm O(n^8), which is the biggest factor I've seen for poly-time algorithms. This paper studies some similar problems related to reconstruction conjecture, showing that just checking that a graph has specific deck is already equivalent to graph isomorphism. Finally, there is a manual 1991 on all major achievements to date showing that reconstruction conjecture is solved for some families of graphs such as regular graphs.

Insights. After reading all this, I have the following thoughts.

* It would be cool to write a paper on the algorithm for reconstruction of the graph from its deck. I have some trivial idea how to do it via graph isomorphism solver and some heuristics. Actually the problem is not purely abstract and has a lot of important applications to chemoinformatics for example, so it's interesting.

* It would be cool to write a follow-up paper which uses RL to improve heuristics. Graph reconstruction is under radar compared to TSP, so it would be first-of-its-kind RL algorithm for such problem.

* Initially I had the idea that if I take hard instances for graph isomorphism and compute decks for such graphs then I would get the same decks for non-isomorphic graphs, solving reconstruction conjecture. The reason why I thought this was that hard non-isomorphic graphs are very similar to each other, so their subgraphs would be identical. But, regular graphs are already proved to be reconstructible, so many hard instances won't work (such as SRG or Miyazaki graphs). Then, there are "very hard" graphs, which are half-regular (there are only two values for degrees across all nodes). I tried those, but found that decks are completely different for non-isomorphic graphs. So my idea failed and I spent two days reading, thinking, and implementing it 😀