NetLSD: Hearing the Shape of a Graph

paper · pdf · code · slides pptx pdf · video · talk
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.