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.
Share this post
Reddit
LinkedIn
Email