A Summarization Technique for Heterogeneous Graphs
Querying heterogeneous and large-scale knowledge graphs is expensive. This project studies a graph summarization framework to facilitate knowledge graph search. (1) We introduce a class of reduced summaries. Characterized by approximate graph pattern matching, these summaries are capable of summarizing entities in terms of their neighborhood similarity up to a certain hop, using small and informative graph patterns. (2) We study a diversified graph summarization problem. (a) We show that there exists a 2-approximation algorithm to discover diversified summaries. We further develop an anytime sequential algorithm which discovers summaries under resource constraints. (b) We present a new parallel algorithm with quality guarantees. (3) We also develop a summary-based query evaluation scheme, which only refers to a small number of summaries.
Qi Song, Yinghui Wu, Peng Lin, Mohammad Hossein Namaki
Mining Summaries for Knowledge Graph Search. [Paper]
IEEE Transactions on Knowledge and Data Engineering(TKDE), Vol.30 (Issue No. 10), 1887-1900, 2018.
Qi Song, Yinghui Wu, Peng Lin, Luna Xin Dong, Hui Sun
Parallel Graph Summarization for Knowledge Search. [Paper][Poster]
International Workshop on Mining and Learning with Graphs (MLG), 2017.
Qi Song, Mohammad Hossein Namaki, Peng Lin, Yinghui Wu
Mining Summaries for Knowledge Graph Search. [Paper][Full Version][Slide]
IEEE International Conference on Data Mining (ICDM), 2016.
Qi Song, Yinghui Wu, Luna Xin Dong
This project is supported in part by NSF IIS-1633629 and Google Faculty Research Award.