Towards graphical models for text processing | Knowledge and Information Systems Skip to main content
Springer Nature Link
Log in

Towards graphical models for text processing

  • Regular Paper
  • Published:
Knowledge and Information Systems Aims and scope Submit manuscript

Abstract

The rapid proliferation of the World Wide Web has increased the importance and prevalence of text as a medium for dissemination of information. A variety of text mining and management algorithms have been developed in recent years such as clustering, classification, indexing, and similarity search. Almost all these applications use the well-known vector-space model for text representation and analysis. While the vector-space model has proven itself to be an effective and efficient representation for mining purposes, it does not preserve information about the ordering of the words in the representation. In this paper, we will introduce the concept of distance graph representations of text data. Such representations preserve information about the relative ordering and distance between the words in the graphs and provide a much richer representation in terms of sentence structure of the underlying data. Recent advances in graph mining and hardware capabilities of modern computers enable us to process more complex representations of text. We will see that such an approach has clear advantages from a qualitative perspective. This approach enables knowledge discovery from text which is not possible with the use of a pure vector-space representation, because it loses much less information about the ordering of the underlying words. Furthermore, this representation does not require the development of new mining and management techniques. This is because the technique can also be converted into a structural version of the vector-space representation, which allows the use of all existing tools for text. In addition, existing techniques for graph and XML data can be directly leveraged with this new representation. Thus, a much wider spectrum of algorithms is available for processing this representation. We will apply this technique to a variety of mining and management applications and show its advantages and richness in exploring the structure of the underlying text documents.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. We assume that stop-words have already been removed from the document \(D\).

  2. The distance of a word to itself is zero.

  3. http://kdd.ics.uci.edu/databases/20newsgroups.

  4. http://kdd.ics.uci.edu/databases/reuters21578.

  5. http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/webkb-data.gtar.gz.

  6. http://tartarus.org/martin/PorterStemmer.

References

  1. Aggarwal C (2010) Managing and mining graph data. Springer, Berlin

    Book  MATH  Google Scholar 

  2. Aggarwal C, Yu PS (2011) On clustering massive text and categorical data streams. Knowl Inf Syst 24(2):171–196

    Article  Google Scholar 

  3. Aggarwal C, Zhao P (2010) Graphical models for text: a new paradigm for text representation and processing. In: The 33rd international ACM SIGIR conference on research and development in, information retrieval (SIGIR’10), pp 899–900

  4. Aggarwal C, Zhai C (2012) A survey of text clustering algorithms, Mining text data. Springer, Berlin

    Book  Google Scholar 

  5. Aggarwal C, Ta N, Feng J, Wang J, Zaki MJ (2007) XProj: a framework for projected structural clustering of XML documents. In: The 13th ACM SIGKDD international conference on knowledge discovery and data mining (KDD’07), pp 46–55

  6. Aggarwal C, Lin W, Yu PS (2012) Searching by corpus with fingerprints. In: EDBT conference, pp 348–359

  7. Bishop C (1995) Neural networks for pattern recognition. Oxford University Press, Oxford

    Google Scholar 

  8. Cavnar W, Trenkle J (1994) N-gram based text categorization. In: Symposium on document analysis and, information retrieval (SDAIR’94), pp 161–194

  9. Collins MJ (1996) A new statistical parser based on bigram statistical dependencies. In: The 34th annual meeting on association for, computational linguistics (ACL’96), pp 184–191

  10. Cutting D, Karger D, Pedersen J, Tukey J (1992) Scatter/gather: a cluster-based approach to browsing large document collections. In: The 15th annual international ACM SIGIR conference on research and development in, information retrieval (SIGIR’92), pp 318–329

  11. Debole F, Sebastiani F (2004) An analysis of the relative hardness of reuters-21578 subsets. J Am Soc Inf Sci Tech 56(6):584–596

    Article  Google Scholar 

  12. Fuhr N, Buckley C (1990) Probabilistic document indexing from relevance feedback data. In: The 13th annual international ACM SIGIR conference on research and development in, information retrieval (SIGIR’90), pp 45–61

  13. Hearst M (1992) Automatic acquisition of hyponyms from large text corpora. In: The 14th conference on, computational linguistics (COLING’92), pp 539–545

  14. Jain A, Dubes R (1988) Algorithms for clustering data. Prentice-Hall, New Jersey

    MATH  Google Scholar 

  15. Joachims T (1997) A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization. In: The fourteenth international conference on, machine learning (ICML’97), pp 143–151

  16. Lewis DD (1996) reuters-21578 data set. http://www.daviddlewis.com/resources/test-collections/reuters21578

  17. Lin D (1998) Extracting collocations from text corpora. In; First workshop on computational terminology

  18. Maron M (1961) Automatic indexing: an experimental inquiry. J ACM 8(3):404–417

    Article  MATH  Google Scholar 

  19. McCallum A (1996) Bow: a toolkit for statistical language modeling. Text retrieval, classification and clustering. http://www.cs.cmu.edu/~mccallum/bow

  20. Salton G, Mcgill MJ (1983) An introduction to modern information retrieval. McGraw Hill, New York

    Google Scholar 

  21. Schutze H, Silverstein C (1997) Projections for efficient document clustering, In: The 20th annual international ACM SIGIR conference on research and development in, information retrieval (SIGIR’97), pp 74–81

  22. Smadja F (1993) Retrieving collocations from text: Xtract. Comput Linguist 19(1):143–177

    Google Scholar 

  23. Steinbach M, Karypis G, Kumar V (2000) A comparison of document clustering techniques. In: KDD text mining, workshop, pp 109–111

  24. Wang H, Park S, Fan W, Yu PS (2003) ViST: a dynamic index method for querying XML data by tree structures. In: The 2003 ACM SIGMOD international conference on management of data (SIGMOD’03), pp 110–121

  25. Wang F, Zhang C, Li T (2007) Regularized clustering for documents. In: The 30th annual international ACM SIGIR conference on research and development in, information retrieval (SIGIR’07), pp 95–102

  26. Yan X, Han J (2003) CloseGraph: mining closed frequent graph patterns. In: The ninth ACM SIGKDD international conference on knowledge discovery and data mining (KDD’03), pp 286–295

  27. Yan X, Yu PS, Han J (2005a) Graph indexing based on discriminative frequent structure analysis. ACM Trans Database Syst 30(4):960–993

    Article  Google Scholar 

  28. Yan X, Yu PS, Han J (2005b) Substructure similarity search in graph databases. In: The 2005 ACM SIGMOD international conference on management of data (SIGMOD’05), pp 766–777

  29. Yan X, Cheng H, Han J, Yu PS (2008) Mining significant graph patterns by scalable leap search. In: The 2008 ACM SIGMOD international conference on management of data (SIGMOD’08), pp 433–444

  30. Zaki MJ, Aggarwal C (2003) XRules: an effective structural classifier for XML data. In: The ninth ACM SIGKDD international conference on knowledge discovery and data mining (KDD’03), pp 316–325

  31. Zhao P, Han J (2010) On graph query optimization in large networks. PVLDB 3(1):340–351

    Google Scholar 

  32. Zhao Y, Karypis G (2004) Empirical and theoretical comparisons of selected criterion functions for document clustering. Mach Learn 55(3):311–331

    Article  MATH  Google Scholar 

  33. Zhao P, Xu J, Yu PS (2007) Graph indexing: tree + delta >= graph. In: The 33rd international conference on very large data bases (VLDB’07), pp 938–949

Download references

Author information

Authors and Affiliations

  1. IBM T. J. Watson Research Center, Yorktown Heights, NY, 10598, USA

    Charu C. Aggarwal

  2. Florida State University, Tallahassee, FL, 32306, USA

    Peixiang Zhao

Authors
  1. Charu C. Aggarwal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peixiang Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Charu C. Aggarwal.

Additional information

This paper is an extended version of Aggarwal and Zhao [3].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aggarwal, C.C., Zhao, P. Towards graphical models for text processing. Knowl Inf Syst 36, 1–21 (2013). https://doi.org/10.1007/s10115-012-0552-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10115-012-0552-3

Keywords

Search

Navigation