The Startup
Published in

The Startup

Whatโ€™s new for KGs in Graph ML?

Machine Learning on Knowledge Graphs @ NeurIPS 2020

Your guide to the KG-related research in NLP, December edition

Behind the curtain of transductive link prediction we step into the valley of logical reasoning tasks for KGs to excel at

Get some โ˜•๏ธ, ๐Ÿต, or even some Glรผhwein - today in our agenda:

  1. Query Embedding: Beyond Query2Box
  2. KG Embeddings: NAS, ๐Ÿ“ฆ vs ๐Ÿ”ฎ, Meta-Learning
  3. SPARQL and Compositional Generalization
  4. Benchmarking: OGB, GraphGYM, KeOps
  5. Wrapping out

Query Embedding: Beyond Query2Box

Query embedding (QE) is about answering queries against a KG directly in the embedding space without any SPARQL or graph database engines. Given that most of KGs are sparse and incomplete, query embedding algorithms are able to infer missing links (with a certain probability). This is one of the hottest topics in Graph ML so far! ๐Ÿ”ฅ
In the ICLR 2020 post, we covered Query2Box, a strong QE baseline capable of answering logical queries with conjunction (โˆง), disjunction (โˆจ), and existential quantifiers (โˆƒ) by modeling entities as d-dimensional boxes ๐Ÿ“ฆ.

Answering a FOL query โ€œList the presidents of European countries that have never held the World Cupโ€ with conjunction, disjunction, and negation operators. Source: Ren and Leskovec
Source: Sun et al

KG Embeddings: NAS, ๐Ÿ“ฆ vs ๐Ÿ”ฎ, Meta-Learning

Something really interesting this year at NeurIPS going beyond โ€˜yet-another-KG-embedding-algorithmโ€™. Youโ€™ve probably heard about Neural Architecture Search (NAS) and its successes in computer vision โ€” for instance, recent architectures like EfficientNet are not designed by humans ๐Ÿค–. Instead, a NAS system generates a neural net from a bunch of smaller building blocks ๐Ÿงฑoptimizing certain metrics. Can we have a NAS to generate efficient architectures for KG-related tasks?

When NAS for KG embeddings actually works
Source: Zhang et al
Source: Abboud et al
Source: Srivastava et al
Source: Baek et al

SPARQL and Compositional Generalization

๐Ÿ“ In question answering over KGs (KGQA), semantic parsing transforms a question into a structured query (say, in SPARQL) which is then executed against a database. One of the ๐Ÿ”‘ problems there is compositional generalization, that is, can we build complex query patterns after observing simple atoms? In the ICLRโ€™20 post, we reviewed a new large-scale dataset Complex Freebase Question (CFQ) (letโ€™s forgive them for ๐ŸงŸโ€โ™‚๏ธ Freebase) that was designed to measure compositional generalization capabilities of NL 2 SPARQL approaches. Notably, baselines like LSTMs and Transformers perform quite poorly: <20% accuracy on average ๐Ÿ˜•

Source: Guo et al

๐Ÿ‹ Benchmarking: OGB, GraphGYM, KeOps

Tired of seeing Cora/Citeseer/Pubmed in every other GNN paper? You should be: they are small, expose certain biases, and modelsโ€™ performance has pretty much saturated. Time for a big change! โ˜„๏ธ

Source: Hu et al
96 setups sampled from 10M possible combinations. Source: You, Ying, and Leskovec
  • You can also perform a kNN search and be competitive with FAISS!
  • Some implementations in PyTorch-Geometric already work well with KeOPS
KeOps uses symbolic matrices! Source: Feydy et al

Wrapping Up

NeurIPS concludes the line-up of top AI conferences, but ICLR 2021 scores are already out there ๐Ÿ˜‰. If you want to keep updated on Graph ML topics, you could subscribe to the regular newsletter by Sergey Ivanov or join the Telegram GraphML channel!



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Michael Galkin

AI Research Scientist @ Intel Labs. Working on Graph ML, Geometric DL, and Knowledge Graphs