NetLSD: Hearing the Shape of a Graph

#Anton_Tsitsulin_(Hasso_Plattner_Institute); #Davide_Mottin_(Hasso_Plattner_Institute); #Panagiotis_Karras_(Aarhus_University); #Alexander_Bronstein_(Israel_Institute_of_Technology); #Emmanuel_Müller;

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.

グラフの比較について

computation的にも、類似度の表現力的にも難しいよね

理想的にはノードの順序とグラフの大きさに普遍で、グラフパターンのスケールに適応し、スケーラブル???

現状は、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.

https://www.youtube.com/watch?v=aiPOa1NTgvM

PDF url: https://dl.acm.org/authorize?N665738

https://arxiv.org/abs/1805.10712

github: https://github.com/xgfs/NetLSD

Intro

Related word

https://gyazo.com/f41ee01729ab16939760ce39c713a474

Direct Methods

Graph edit distance(GED)

DELTACON

a family of tractable distances (FTD)

Kernel Methods

Shortest-path (SP) kernel

Multi-scale Laplacian Graph kernel (MLG)

Statistical representation

NETSIMILE

the Family of Spectral Distances (FSGD)

spectral representation

Method

Rather than using the Laplacian spectrum per se, we consider an associated heat diffusion process on the graph, to obtain a more expressive representation, in a manner reminiscent of random walk models 12

ラプラシアン行列の固有値（spectrum）、固有行列を使って、

a heat trace signature, a wave signatureを定義

固有ベクトル使ってkernel行列を定義して、その行列のtraceをとる感じ?

tの数がベクトルの次元数になるはず、