Organization: Aarhus University
Email: panos@cs.au.dk
Title: NetLSD: Hearing the Shape of a Graph
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 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.
Bio:
Panagiotis Karras (Panos) is an Associate Professor in Computer Science at Aarhus University. In his research he designs robust and versatile methods for data access, mining, and representation. He earned an MEng in Electrical and Computer Engineering from the National Technical University of Athens and a PhD in Computer Science from the University of Hong Kong. Has has been awarded with a Hong Kong Young Scientist Award, a Lee Kuan Yew Postdoctoral Fellowship at the National University of Singapore, a Teaching Excellence Fellowship at Rutgers Business School, and a Best Faculty Performance Award at the Skolkovo Institute of Science and Technology. Panos’ work has been published in venues such as VLDB, KDD, SIGMOD, ICDE, SIGIR, and WWW, and cited over 2000 times. He regularly serves as a PC member and referee for major conferences and journals in those areas.
