Skip to Content

NetLSD: Hearing the Shape of a Graph

Posted on One min read
NetLSD descriptors
How can we model the structure of this graph on multiple scales?

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.