Introduction to Deep Learning (I2DL)

There is a course on deep learning by Technical University of Munich. Recordings, slides, and exercises are available online.

Secrets of the Surface: The Mathematical Vision of Maryam Mirzakhani

There is a documentary that you can watch on the life of Maryam Mirzakhani. In 2014, she was awarded the Fields medal for the work in "the dynamics and geometry of Riemann surfaces and their moduli spaces." You can read about her in this article. For the film, you can register here and they will send a link to the Vimeo, which will be available until 19th May.

AI and Theorem Proving

One of the topics that caught my attention was on using AI to automate theorem proving. Apparently, there is already a conference on this. At ICLR there was a paper on using graph networks for theorem proving.

I think besides this conference, which mainly explores how you can model mathematical logic using embeddings, another type of theorem proving is on smart pruning of combinatorial spaces (e.g. you have large space of graphs, from which you need to pick some particular examples).

Learning graph structure to help classification

I just recently discussed an idea whether it's possible to create a graph from a non-graph classification data set and improve classification performance by doing it and I found two works on it.

First approach just tries different values for knn to connect the points into a graph, obtains a graph for each parameter setting, and verifies the performance of classification of a graph model on the obtained graph. Clearly the problem with it is that you have to do classification many many times for different parameters of your knn.

Second approach (ICML 2019, link to presentation) is more data-driven: instead of freezing the parameters of knn, it uses a graph generative model that would generate a graph from the points. Then a graph neural network would make a classification prediction and, together with parameters of generative model, would be updated by backpropagation. It's still quite heavy as you need to update parameters of two different models instead of one. Perhaps, there are future works that would create the graphs at little computational cost and would boost the results for classification pipelines.

Fresh picks from ArXiv
This week highlights papers on scene graph generation, isomorphism testing by GNNs and WL, and weight estimation of pork cuts 🐖

GNN
• How hard is graph isomorphism for graph neural networks? by Andreas Loukas
• Neural Stochastic Block Model & Scalable Community-Based Graph Learning
• Graph Density-Aware Losses for Novel Compositions in Scene Graph Generation
• Structured Query-Based Image Retrieval Using Scene Graphs
• Isometric Transformation Invariant and Equivariant Graph Convolutional Networks
• SpectralWeight: a spectral graph wavelet framework for weight prediction of pork cuts

Conferences
• Integrating Semantic and Structural Information with Graph Convolutional Network for Controversy Detection ACL 20
• GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactions IJCAI 20
• Document Modeling with Graph Attention Networks for Multi-grained Machine Reading Comprehension ACL 20

Graph Theory
• Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles
• The Weifeiler-Leman Algorithm and Recognition of Graph Properties


Surveys
• Visual Relationship Detection using Scene Graphs: A Survey
• Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
• Recent Advances in SQL Query Generation: A Survey
• Explainable Reinforcement Learning: A Survey

ACL 2020 stats

ACL (Association for Computational Linguistics) is the top conferences in NLP. Each year there are more and more papers that use graphs with natural language.

Dates: July 5-10
Where: Online

• 3088 submissions (2906 submissions in 2019)
• 571/208 long and short papers (25% overall acceptance rate; 447/213 in 2019)
• 42/6 long/short graph papers (7%/3% of total)

CVPR 2020

Computer Vision and Pattern Recognition (CVPR) conference is the top conference in CV and has had increasing focus on application of graphs to images. Here are some facts about CVPR 2020.

Papers link
Dates: June 14-19
Where: Virtual

• 6,656 total papers
• 1,470 accepted papers
• 22% acceptance rate
• ~69 graph papers (~5% of total)

Graph Machine Learning research groups: Christos Faloutsos

I do a series of posts on the groups in graph research. The sixth is Christos Faloutsos. He was an advisor for many current professors in GML such as Jure Leskovec, Leman Akoglu, Stephan Guennemman, and Bruno Ribeiro.


Christos Faloutsos (~1960)
- Affiliation: Carnegie Mellon University; Amazon
- Education: Ph.D. at University of Toronto in 1987 (supervised by Stavros Christodoulakis);
- h-index: 131;
- Awards: ACM fellow, best paper awards at KDD, SIGMOD, ICDM;
- Interests: data mining; database; anomaly detection in graphs.

Social network data set

Anton @xgfsru shared a data set VK1M (password 1234), with first 1M users from social network vk.com (data is taken via public API). In addition to the friends of each user, the file contains meta-information such as education, country, birthday of each node. It can be useful for node classification or regression tasks as well as community or anomaly detection.

Fresh picks from ArXiv
This week has more papers from upcoming ACL, SIGIR, and KDD; a new survey on combinatorial optimization on graphs; and Borsuk's conjecture 🐹

Conferences
• Joint Item Recommendation and Attribute Inference: An Adaptive Graph Convolutional Network Approach SIGIR 20
• ATBRG: Adaptive Target-Behavior Relational Graph Network for Effective Recommendation SIGIR 20
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks KDD 20
• Understanding Negative Sampling in Graph Representation Learning KDD 20
• Leveraging Graph to Improve Abstractive Multi-Document Summarization ACL 20
• M2GRL: A Multi-task Multi-view Graph Representation Learning Framework for Web-scale Recommender Systems KDD 20
• Graph Structure Learning for Robust Graph Neural Networks KDD 20


Surveys
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• How to Build a Graph-Based Deep Learning Architecture in Traffic Domain: A Survey
• Motif Discovery Algorithms in Static and Temporal Networks: A Survey

Graph Theory
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Counterexamples to Borsuk's conjecture from a third strongly regular graph
• A Group-Theoretic Framework for Knowledge Graph Embedding

How hard is graph isomorphism for graph neural networks?

This is a new work by Andreas Loukas that sheds a little bit more light into the theory behind GNN. The analysis relies on the amount of information nodes should exchange in order to detect isomorphism class of each graph. This problem of finding isomorphism class is called graph canonization problem, which is probably even harder than graph isomorphism. As such a GNN model needs to output a number for each possible graph up to isomorphism, and needless to say the number of non-isomorphic graphs grows closely to factorial terms. Hence the experiments, while support the theory, are done only on very small graphs ~10 nodes.

On the universal equivariant functions

Yesterday's post was followed by a conversation with Andreas Loukas on the power of graph neural networks. There is one detail about the current analysis of GNN, which I didn't pay much attention before, even though I encountered it (it's a recurring phenomenon for me, when some major insight is given one sentence in the paper and is not highlighted in CAPITAL letters).

The insight is that there are two types of GNN, anonymous and non-anonymous. Anonymous case means you are invariant to the order of nodes, for example when you use the sum aggregation over nodes. It was shown that anonymous case is equivalent to WL algorithm and therefore has a lot limitations such as not being able to count subgraphs or distinguish graphons, etc. So the current anonymous models are not universal: they cannot compute all the functions of the inputs. It's a weaker model than non-anonymous case, when you give some orderings to the nodes and then you iterate over all orderings.

Non-anonymous models have additional node features, for example one-hot encodings of their position in adjacency matrix, which is one of the sufficient conditions for GNN to be universal. There are then two scenarios. Either you consider all possible permutations, in which case it grows in factorial terms and essentially it's a cheat. Or you resort to a single permutation, but then do not enjoy the invariance property of GNN, i.e. for different orderings it can give different set of embeddings for the same nodes.

So it's interesting to see if there are universal equivariant functions that do not use all node permutations, which is still an open question.

Other telegram channels

There are many other interesting channels, below are English-speaking that I follow. If I miss something valuable, feel free to send them to me and I will update the post.

https://t.iss.one/opendatascience
https://t.iss.one/ArtificialIntelligencedl
https://t.iss.one/ai_machinelearning_big_data
https://t.iss.one/j_links
https://t.iss.one/ArtificialIntelligenceArticles
https://t.iss.one/snakers4
https://t.iss.one/loss_function_porn
https://t.iss.one/yegor256news

Also quite useful aggregator https://infomate.club/ml/

Why `True is False is False` -> False?

Stumbled upon this little question why True is False is False evaluates to False in python. The answer is as simple as the question, but not obvious and many people could not answer it. So I wrote a quick post about it.

Fresh picks from ArXiv
This week has GNN variants for various types of graphs, NP-completeness of MaxCut problem, and a survey on graph data management 🖥

GNN
• Understanding the Message Passing in Graph Neural Networks via Power Iteration
• Interpretable and Efficient Heterogeneous Graph Convolutional Network
• Graph Neural Network for Hamiltonian-Based Material Property Prediction
• Non-IID Graph Neural Networks
• Hierarchical Fashion Graph Network for Personalized Outfit Recommendation
• Non-Local Graph Neural Networks

Graph Theory
• Complexity of Maximum Cut on Interval Graphs
• Planar Graphs that Need Four Pages

Surveys
• Benchmarking Graph Data Management and Processing Systems: A Survey

ICML 2020 stats

ICML is the top conference in ML.

Dates: July 12-18
Where: Online

• 4990 submissions (vs 3424 in 2019)
• 1088 accepted (vs 774 in 2019)
• 21.8% acceptance rate (vs 22.6% in 2019)
• 53 graph papers (5% of total)

Of course, there are many big names from graph machine learning for ICML 20 such as Jure Leskovec, Tom Jaakkola, Le Song, Peter Battaglia and others.

Online Seminar on Mathematical Foundations of Data Science

Virtual weekly seminars with excellent list of speakers, open to the public, on mathematics and statistics in ML.

Graph Machine Learning research groups: Joan Bruna

I do a series of posts on the groups in graph research, previous post is here. The seventh is Joan Bruna. He was one of the authors of the survey Geometric Deep Learning: going beyond Euclidean Data and now has increasingly more papers on the theoretical explanations of GNN.


Joan Bruna (~1981)
- Affiliation: New York University
- Education: Ph.D. at Ecole Polytechnique, France in 2013 (supervised by Stephane Mallat);
- h-index: 27;
- Awards: NSF career award, Sloan fellowship, ICMLA best paper;
- Interests: GNN theory, equivariant networks

ICML 2020 arxiv links

There is a nice website that gather all (available) links to papers at ICML. There are some interesting insights.
First, it's interesting to see what is the oldest paper that was accepted to ICML this year. Apparently this paper was published on arxiv in Sep 2017, waiting for a little bit less than 3 years to get accepted. There are 8 papers from 2018. And the authors probably started working on these papers 6-9 months before the publication date. It's brutal.
Another interesting observation is that the word graph appeared to be top-5 word among all words in titles, which show increased interest in graphs at ICML.

Fresh picks from ArXiv
This week is rich on explainable GNN literature, as well as papers on compression of graphs, combinatorial optimization and recommendation.

GNN
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
• Are Graph Convolutional Networks Fully Exploiting Graph Structure?
• Accurately Solving Physical Systems with Graph Learning
• Single-Layer Graph Convolutional Networks For Recommendation
• XAI for Graphs: Explaining Graph Neural Network Predictions by Identifying Relevant Walks
• XGNN: Towards Model-Level Explanations of Graph Neural Networks
• Universal Graph Compression: Stochastic Block Models
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs
• Fairness-Aware Explainable Recommendation over Knowledge Graphs

Graph Theory
• Hierarchical hyperbolicity of graph products
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw

Conferences
• Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction KDD 20

Surveys
• Generate FAIR Literature Surveys with Scholarly Knowledge Graphs
• A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions