Entity Summarisation with Limited Edge Budget on Undirected and Directed Knowledge Graphs

Main Article Content

Marcin Sydow
Mariusz Pikuła
Ralf Schenkel


The paper concerns a novel problem of summarising entities with limited presentation budget on entity-relationship knowledge graphs and propose an efficient algorithm for solving this problem. The algorithm has been implemented in two variants: undirected and directed, together with a visualisation tool. Experimental user evaluation of the algorithm was conducted on real large semantic knowledge graphs extracted from the web. The reported results of experimental user evaluation are promising and encourage to continue the work on improving the algorithm.


Download data is not yet available.

Article Details

Jak cytować
Sydow, M., Pikuła, M., & Schenkel, R. (2010). Entity Summarisation with Limited Edge Budget on Undirected and Directed Knowledge Graphs. Investigationes Linguisticae, 21, 76-89. https://doi.org/10.14746/il.2010.21.5


  1. Ai, D., Zheng, Y., Zhang, D.: Automatic text summarization based on latent semantic indexing. Artificial Life and Robotics 15, 25–29 (2010), http://dx.doi.org/10.1007/s10015-010-0759-x, 10.1007/s10015-010-0759-x
  2. Amini, M.R., Tombros, A., Usunier, N., Lalmas, M.: Learning-based summarisation of xml documents. Inf. Retr. 10(3), 233–255 (2007)
  3. Bedathur, S.J., Berberich, K., Dittrich, J., Mamoulis, N., Weikum, G.: Interesting-phrase mining for ad-hoc text analytics. PVLDB 3(1), 1348–1357 (2010)
  4. Consens, M.P., Miller, R.J., Rizzolo, F., Vaisman, A.A.: Exploring xml web collections with describex. TWEB 4(3) (2010)
  5. Demartini, G., Missen, M.M.S., Blanco, R., Zaragoza, H.: Entity summarization of news articles. In: Proceeding of the 33rd international ACM SIGIR conference on Research and development in information retrieval. pp. 795–796. SIGIR ’10, ACM, New York, NY, USA (2010), http://doi.acm.org/10.1145/1835449.1835620
  6. Elbassuoni, S., Ramanath, M., Schenkel, R., Sydow, M., Weikum, G.: Language-modelbased ranking for queries on rdf-graphs. In: CIKM ’09: Proceeding of the 18th ACM conference on Information and knowledge management. pp. 977–986. ACM, New York, NY, USA (2009)
  7. Etzioni, O., Banko, M., Soderland, S., Weld, D.S.: Open information extraction from the web. Commun. ACM 51(12), 68–74 (2008)
  8. Harth, A., Hose, K., Karnstedt, M., Polleres, A., Sattler, K.U., Umbrich, J.: Data summaries for on-demand queries over linked data. In: WWW. pp. 411–420 (2010)
  9. Hassan, A., Fader, A., Crespin, M.H., Quinn, K.M., Monroe, B.L., Colaresi, M., Radev, D.R.: Tracking the dynamic evolution of participants salience in a discussion. In: COLING. pp. 313–320 (2008)
  10. Huang, Y., Liu, Z., Chen, Y.: Query biased snippet generation in xml search. In: SIGMOD Conference. pp. 315–326 (2008)
  11. Koutrika, G., Simitsis, A., Ioannidis, Y.: Pr´ecis: The essence of a query answer. In: ICDE ’06: Proceedings of the 22nd International Conference on Data Engineering. p. 69. IEEE Computer Society, Washington, DC, USA (2006)
  12. Li, N., Motta, E.: Evaluations of user-driven ontology summarization. In: The 17th International Conference on Knowledge Engineering and Knowledge Management by the Masses (2010)
  13. Mani, I.: Automatic Summarization. MIT Press (2001)
  14. M.Ramanath, K.S.Kumar: A rank-rewrite framework for summarizing xml documents. In: ICDE Workshops. pp. 540–547 (2008)
  15. Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: SIGMOD Conference. pp. 419–432 (2008)
  16. Ramanath, M., Kumar, K.S.: A rank-rewrite framework for summarizing xml documents. In: ICDE Workshops. pp. 540–547 (2008)
  17. Ramanath, M., Kumar, K.S., Ifrim, G.: Generating concise and readable summaries of xml documents. CoRR abs/0910.2405 (2009)
  18. Rusu, D., Fortuna, B., Mladeni´c, D., Grobelnik, M., Sipoˇs, R.: Visual analysis of documents with semantic graphs. In: Proceedings of the ACM SIGKDD Workshop on Visual Analytics and Knowledge Discovery: Integrating Automated Analysis with Interactive
  19. Exploration. pp. 66–73. VAKD ’09, ACM, New York, NY, USA (2009), http://doi.acm.org/10.1145/1562849.1562857
  20. Sydow, M., Pikuła, M., Schenkel, R.: DIVERSUM: Towards diversified summarisation of entities in knowledge graphs. In: Proceedings of Data Engineering Workshops (ICDEW) at IEEE 26th ICDE Conference. pp. 221–226. IEEE (2010)
  21. Sydow, M., Pikuła, M., Schenkel, R., Siemion, A.: Entity summarisation with limited edge budget on knowledge graphs. In: Proceedings of the International Multiconference on Computer Science and Information Technology. pp. 513–516. IEEE (2010)
  22. Tian, Y., Hankins, R.A., Patel, J.M.: Efficient aggregation for graph summarization. In: SIGMOD Conference. pp. 567–580 (2008)
  23. Wan, X.: Topic analysis for topic-focused multi-document summarization. In: CIKM. pp. 1609–1612 (2009)
  24. Wan, X., Xiao, J.: Exploiting neighborhood knowledge for single document summarization and keyphrase extraction. ACM Trans. Inf. Syst. 28(2) (2010)
  25. Wang, N., Parthasarathy, S., Tan, K.L., Tung, A.K.H.: Csv: visualizing and mining cohesive subgraphs. In: SIGMOD Conference. pp. 445–458 (2008)
  26. Yu, C., Jagadish, H.V.: Schema summarization. In: VLDB. pp. 319–330 (2006)
  27. Zhang, N., Tian, Y., Patel, J.M.: Discovery-driven graph summarization. In: ICDE. pp. 880–891 (2010)