数学科学研究所
Insitute of Mathematical Science

Comparing large-scale graphs based on quantum probability theory

Time:10:30-11:30, Jan. 4th, Friday

LocationRoom 302,  Library


Speaker: Dr. Hayound Choi, School of Information Science and Technology, ShanghaiTech University

Abstract:  Graph is one of the most common representations of complex data and plays a crucial role in various research areas and many practical applications. Recently many different approaches to find similarity between two graphs are proposed for efficient algorithms. However, these methods are not scalable to large-scale graphs containing millions of edges, which are common in today’s applications. As a result, effective and scalable methods for large-scale graphs comparison are urgently needed.

In this talk, a new distance to compare two large-scale graphs based on the theory of quantum probability is introduced. Our proposed distance between two graphs is defined as the distance between the corresponding moment matri- ces of their spectral distributions. An explicit form for the spectral distribution of the corresponding adjacency matrix of a graph is established. It is shown that the spectral distributions of their adjacency matrices in a vector state includes information not only about their eigenvalues, but also about the corresponding eigenvectors. Also, such distance includes enough information of the structure of a graph. Moreover, we prove that such distance is graph invariant and sub- structure invariant. Various examples are given, and distances between graphs with few vertices are checked. Computational results for real large-scale net- works show that its accuracy is better than any existing methods and time cost is extensively cheap.


地址:上海市浦东新区华夏中路393号
邮编:201210
上海市徐汇区岳阳路319号8号楼
200031(岳阳路校区)