# NetLSD: Hearing the Shape of a Graph

Anton Tsistulin, Davide Mottin, Panagiotis Karras, Alex Bronstein, Emmanuel Müller

KDD 2018

## TL;DR

Fast graph descriptors that allows to compare graphs:

• Fast – in $$O(1)$$ after fast precomputation
• On multiple scales – from connectivity to community structure
• Of different sizes – we can correct for size of graphs

In this paper:

• We take the geometrical perspective for computing the descriptors.
• We show how to compute them fast for million-scale graphs.
• We demonstrate how NetLSD is the only known representation that preserves the multi-scale structure of graphs.
• We show that NetLSD lower bounds theoretically powerful metric.
• We propose novel evaluation tasks (detection of graphs with communities, clustering) for graph representations.
• We provide easy-to-use Python package to compute the signatures with interfaces to popular graph libraries.