KGSum Example

A Summarization Technique for Heterogeneous Graphs


About GSum

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.

KGSum Example

People

Qi Song, Yinghui Wu, Peng Lin, Mohammad Hossein Namaki

Publications

  • 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


    • Questions?

    Contact Qi Song

    Acknowledgements

    This project is supported in part by NSF IIS-1633629 and Google Faculty Research Award.