NetLSD: Hearing the Shape of a Graph

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

KDD 2018

How can we model the structure of this graph on multiple scales?

How can we model the structure of this graph on multiple scales?

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.