NetLSD: Hearing the shape of a graph

Tsitsulin A, Mottin D, Karras P, Bronstein AM, Müller E. 2018. NetLSD: Hearing the shape of a graph. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2347–2356.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Tsitsulin, Anton; Mottin, Davide; Karras, Panagiotis; Bronstein, Alex M.ISTA ; Müller, Emmanuel
Abstract
Comparison among graphs is ubiquitous in graph analytics. However, it is a hard task in terms of the expressiveness of the employed similarity measure and the efficiency of its computation. Ideally, graph comparison should be invariant to the order of nodes and the sizes of compared graphs, adaptive to the scale of graph patterns, and scalable. Unfortunately, these properties have not been addressed together. Graph comparisons still rely on direct approaches, graph kernels, or representation-based methods, which are all inefficient and impractical for large graph collections. In this paper, we propose the Network Laplacian Spectral Descriptor (NetLSD): the first, to our knowledge, permutation- and size-invariant, scale-adaptive, and efficiently computable graph representation method that allows for straightforward comparisons of large graphs. NetLSD extracts a compact signature that inherits the formal properties of the Laplacian spectrum, specifically its heat or wave kernel; thus, it \em hears the shape of a graph. Our evaluation on a variety of real-world graphs demonstrates that it outperforms previous works in both expressiveness and efficiency.
Publishing Year
Date Published
2018-07-19
Proceedings Title
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher
ACM
Page
2347 - 2356
Conference
KDD: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Conference Location
London, United Kingdom
Conference Date
2018-08-19 – 2018-08-23
IST-REx-ID

Cite this

Tsitsulin A, Mottin D, Karras P, Bronstein AM, Müller E. NetLSD: Hearing the shape of a graph. In: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2018:2347-2356. doi:10.1145/3219819.3219991
Tsitsulin, A., Mottin, D., Karras, P., Bronstein, A. M., & Müller, E. (2018). NetLSD: Hearing the shape of a graph. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 2347–2356). London, United Kingdom: ACM. https://doi.org/10.1145/3219819.3219991
Tsitsulin, Anton, Davide Mottin, Panagiotis Karras, Alex M. Bronstein, and Emmanuel Müller. “NetLSD: Hearing the Shape of a Graph.” In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2347–56. ACM, 2018. https://doi.org/10.1145/3219819.3219991.
A. Tsitsulin, D. Mottin, P. Karras, A. M. Bronstein, and E. Müller, “NetLSD: Hearing the shape of a graph,” in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, London, United Kingdom, 2018, pp. 2347–2356.
Tsitsulin A, Mottin D, Karras P, Bronstein AM, Müller E. 2018. NetLSD: Hearing the shape of a graph. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2347–2356.
Tsitsulin, Anton, et al. “NetLSD: Hearing the Shape of a Graph.” ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2018, pp. 2347–56, doi:10.1145/3219819.3219991.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1805.10712

Search this title in

Google Scholar