Sylow theorems and algebraic geometry

There is a fresh thread on Sylow theorems, which are popular results in group theory. I'm not sure how much the waste of time is studying group theory, that's something in my todo list, but this thread is giving a good intro to it.

Bringing Light Into the Dark: A Large-scale Evaluation of Knowledge Graph Embedding Models Under a Unified Framework

This is a post by Michael Galkin (@gimmeblues) about their new work on comprehensive evaluation of knowledge graph embeddings. A lot of interesting insights about knowledge graphs.

Today we are publishing the results of our large-scale benchmarking study of knowledge graph (KG) embedding approaches. Further, we are releasing the code of PyKEEN 1.0 - the library behind the study (in PyTorch)! What makes KGs special: they often have hundreds or thousands of different relations (edge types), and having good representations is essential for reasoning in embedding spaces as well as for numerous NLP tasks.

We often evaluate KG embeddings on the link prediction task - given subject+predicate, the model has to predict most plausible objects. As typical KGs contain 50k-100k different entities, you can guess the top1/top10 ranking task is quite complex!

Why benchmarking is important: currently, there is no baseline numbers to refer to. Lots of papers in the domain are not reproducible, or the authors simply take metrics values as reported in other papers withougt reproducing their results.

In this study, we ran 65K+ experiments and spent 21K+ GPU hours evaluating 19 models spanning from RESCAL first published in 2011 to the late 2019's RotatE and TuckER, 5 loss functions, training strategies with/without negative sampling, and many more hyper-parameters that turn out to be important to consider.

Key findings:
- Careful HPO optimization brings us new SOTA results giving significant gains of 4-5% compared to reported results in respective papers (btw, we used Optuna for HPO);
- Properly tuned classical models (TransE, DistMult) are still good and actually outperform several newer models;
- No Best-of-the-Best Silver Bullet model that beats all others across all tasks - some models better capture transitivity, whereas other better capture symmetric relations;
- Surprisingly, for the inherently ranking task, the ranking loss (or MarginRankingLoss in PyTorch) is suboptimal. Instead, Cross-Entropy and its variations show better result;
- Using all enities for negative sampling, i.e., sigmoid/softmax distribution over all enities, works well but can be quite expensive on large KGs. Stochastic negative sampling is a way to go then;
- Computationally expensive and bigger models do not yield that big and drastic performance gains. In fact, 64-d Rotate is better than most 500-d models.


Paper: https://arxiv.org/abs/2006.13365
Code: https://github.com/pykeen/pykeen

Machine Learning Summer School 2020

Today starts Machine Learning Summer School 2020 with great list of speakers on various topics of machine learning, including geometric deep learning. The lectures will be live-streamed on YouTube and are open to everyone.

Manually-curated List of Combinatorial Conferences

Mostly mathematical, with some occasions on CS, here is a manually-curated list of upcoming conferences, workshops, symposiums on combinatorics, among which you can find graph-related topics.

Fresh picks from ArXiv
This week we have papers on theory of GNN, their applications to recommendation and other fields, a historical reference on available graph repositories, and a discussion of peer review vs biblio metrics to assess scientific performance 👨‍⚖️

GNN
• Characterizing the Expressive Power of Invariant and Equivariant Graph Neural Networks
• Building powerful and equivariant graph neural networks with message-passing with Andreas Loukas
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case ICML 2020

Applications
• Graph Convolutional Network for Recommendation with Low-pass Collaborative Filters
• Scalable Deep Generative Modeling for Sparse Graphs with Yujia Li, ICML 2020
• GPT-GNN: Generative Pre-Training of Graph Neural Networks KDD 2020
• Molecule Edit Graph Attention Network: Modeling Chemical Reactions as Sequences of Graph Edits

Graph Problems
• Attentional Graph Convolutional Networks for Knowledge Concept Recommendation in MOOCs in a Heterogeneous View with Philip S. Yu
• Bringing Light Into the Dark: A Large-scale Evaluation of Knowledge Graph Embedding Models Under a Unified Framework with Mikhail Galkin
• Graph Policy Network for Transferable Active Learning on Graphs with Jian Tang
• Online Dense Subgraph Discovery via Blurred-Graph Feedback with Masashi Sugiyama, ICML 2020

Surveys
• A survey of repositories in graph theory
• Metrics and peer review agreement at the institutional level

UAI 2020 stats

UAI is a small but strong conference on AI.

Dates: 3-6 Aug
Where: Online
Cost: 125$
Papers available online.

• 580 submissions (vs 450 in 2019)
• 140 accepted (vs 118 in 2019)
• 24.1% acceptance rate (vs 26% in 2019)
• 5 graph papers (4% of total)

Open Problems - Graph Theory and Combinatorics

In addition to Open Problem Garden, there is a list of open problems in graph theory and a corresponding old archive. Sometimes proof to these is just a specific graph that even people without background may find.

Graph Machine Learning research groups: Stephan Günnemann

I do a series of posts on the groups in graph research, previous post is here. The nineth is Stephan Günnemann. His research interests include adversarial attacks on graphs and graph generative models.


Stephan Günnemann (~1984)
- Affiliation: Technical University of Munich
- Education: Ph.D. at RWTH Aachen University in 2012 (supervised by Thomas Seidl);
- h-index: 30;
- Awards: best paper at KDD;
- Interests: graph adversarial attacks; clustering; graph generative models

Graphs with the same degree distribution

Degree distribution plays a key distinctive role between graphs. In networks science there are specific models that generate you a graph according to some distribution of degrees. For example, scale-free networks are the ones with power law degree distribution, which we observe in real world (e.g. social networks). Scale-free networks use preferential attachment mechanism that mimics the way people connect with others in a new society: we connect to people with high degree and people that we know. The Barabási–Albert model is the most famous example of such a model.

What's interesting in some cases is to provide explicitly the degrees that you expect to have in a graph and then generate a graph with this sequence of degrees. There is a model for that too: it's called Chung-Lu model. Yet, in some other cases, you want to generate a graph exactly with some degree sequence. This is quite simple, you just connect pairs of vertices one by one, until you make a desired degree sequence. It shows how many actually there are different graphs with the same degree sequence. Here is an explanation of this.

Beyond Weisfeiler-Lehman: using substructures for provably expressive graph neural networks

This is the second post by Michael Bronstein, where he discussed his recent architecture of GNN. In one sentence, they append information about graph statistics, such as number of 4-cliques, to message-passing mechanism and show that it is theoretically equivalent to k-WL, with fraction of its cost.

For more than 6 months, I wondered why do we try to design GNN that can solve graph isomorphism (GI), if in all cases we are at most as good as already known algorithms to GI. What if we just take a automorphism group of a graph and then append this information to GNN, hoping it will help for downstream tasks. This way we solve GI by default by using automorphism group, and just measure effectiveness of the GNN for the tasks that matter.

Fresh picks from ArXiv
This week highlights clustering with GNN, scalable GNN, recommendation with graphs, and surveys on mathematical perspective of ML 💭

GNN
• Graph Clustering with Graph Neural Networks with Anton Tsitsulin and Bryan Perozzi
• Scaling Graph Neural Networks with Approximate PageRank with Bryan Perozzi, Stephan Günnemann, KDD 2020
• Simple and Deep Graph Convolutional Networks
• AM-GCN: Adaptive Multi-channel Graph Convolutional Networks KDD 2020
• Adaptive Graph Encoder for Attributed Graph Embedding KDD 2020
• A Novel Higher-order Weisfeiler-Lehman Graph Convolution
• Hierarchical Graph Matching Network for Graph Similarity Computation

Applications
• Disentangled Graph Collaborative Filtering SIGIR 2020
• Scene Graph Reasoning for Visual Question Answering with Stephan Günnemann
• An Efficient Neighborhood-based Interaction Model for Recommendation on Heterogeneous Graph with Alexander J. Smola, KDD 2020
• Interactive Path Reasoning on Graph for Conversational Recommendation KDD 2020
• New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut

Survey
Mathematical Perspective of Machine Learning
Model-based Reinforcement Learning: A Survey
Boosting Deep Neural Networks with Geometrical Prior Knowledge: A Survey

Pytorch-Geometric version 1.6

In a new release PyG features support for static graph, a zoo of new models, and supplementary frameworks such as DeepSnap.

Graphs and Networks Workshop

There is one-day free online workshop for those who love network science, happening this Friday, July 10.

ICML GRL Workshop Papers

There are 73 interesting short papers on various topics of GML at ICML GRL workshop.

Easiest unsolved case of reconstruction conjecture

We spent some time thinking about reconstruction conjecture and got into a conclusion that no one yet solved a simple case as follows.

You have a graph composed of two parts X and Y. In X you have n vertices, in Y you have 2 vertices only. Vertices in Y are connected to X such that all vertices in X have degree 5 and all vertices in Y have degree 4.

So final graph has only two values of degrees, 4 and 5. It's know that when a graph is regular, it can be reconstructed. Here there are only 2 vertices of different degree, nonetheless the problem becomes harder. In more general case you have 2 vertices of degree a and n vertices of degree a+1, but it seems to be much harder to reason about.

Knowledge Graphs at ACL 2020

Another brilliant post by Michael Galkin on usage of knowledge graphs in NLP at ACL 2020.

"Knowledge graphs demonstrate better capabilities to reveal higher-order interdependencies in otherwise unstructured data."

Content:
1. Question Answering over Structured Data
2. KG Embeddings: Hyperbolic and Hyper-relational
3. Data-to-text NLG: Prepare your Transformer
4. Conversational AI: Improving Goal-Oriented Bots
5. Information Extraction: OpenIE and Link Prediction