Timezone: »

 
Oral
Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications
Pin-Yu Chen · Lingfei Wu · Sijia Liu · Indika Rajapakse

Tue Jun 11 04:40 PM -- 05:00 PM (PDT) @ Room 201
in General ML »

The von Neumann graph entropy (VNGE) facilitates the measure of information divergence and distance between graphs in a graph sequence and has successfully been applied to various learning tasks driven by network-based data. Albeit its effectiveness, it is computationally demanding by requiring the full eigenspectrum of the graph Laplacian matrix. In this paper, we propose a fast incremental von Neumann graph entropy (FINGER) framework, which approaches VNGE with a performance guarantee. FINGER reduces the cubic complexity of VNGE to linear complexity in the number of nodes and edges, and thus enables online computation based on incremental graph changes. We also show asymptotic equivalency of FINGER to the exact VNGE, and derive its approximation error bounds. Based on FINGER, we propose efficient algorithms for computing Jensen-Shannon distance between graphs. Our experimental results on different random graph models demonstrate the computational efficiency and the asymptotic equivalency of FINGER. In addition, we also apply FINGER to two real-world applications and one synthesized anomaly detection dataset, and corroborate its superior performance over seven baseline graph similarity methods.

[ Slides]  [ Video] 

Author Information

Pin-Yu Chen (IBM Research AI)
Lingfei Wu (IBM Research)
Sijia Liu (MIT-IBM Watson AI Lab)

Sijia Liu is a Research Staff Member at MIT-IBM Watson AI Lab, IBM research. Prior to joining in IBM Research, he was a Postdoctoral Research Fellow at the University of Michigan, Ann Arbor. He received the Ph.D. degree (with All University Doctoral Prize) in electrical and computer engineering from Syracuse University, NY, USA, in 2016. His recent research interests include deep learning, adversarial machine learning, gradient-free optimization, nonconvex optimization, and graph data analytics. He received the Best Student Paper Finalist Award at Asilomar Conference on Signals, Systems, and Computers (Asilomar'13). He received the Best Student Paper Award at the 42nd IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP'17). He served as a general chair of the Symposium 'Signal Processing for Adversarial Machine Learning' at GlobalSIP, 2018. He is also the co-chair of the workshop 'Adversarial Learning Methods for Machine Learning and Data Mining' at KDD, 2019.

Indika Rajapakse

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors