Graph-based Approaches to Text Processing

Cornell University, Ithaca NY

Investigators

Abstract

Graph-based methods form a powerful framework for a range of data-intensive applications: any dataset involving pairwise relationships such as similarities can be naturally expressed as a graph on the underlying objects, and structuring natural-language and related data in graph form makes this data accessible to powerful combinatorial algorithms. Crucially, efficient graph algorithms enable the analysis of data relationships in a global fashion, which greatly increases the amount of information that can be distilled from both annotated and un-annotated data. This work develops new algorithms based on graph-theoretic ideas, including network flow and spectral analysis. It applies these methods to a range of different application areas in text and language processing, including sentiment-based text categorization and document retrieval; it also develops connections between these problems and some current issues in social network analysis. The main results of this work will be to open up to the natural language processing community a new set of effective, theoretically sound graph-based paradigms for learning from language data. In addition, this work will make resources available to the broader research community through the dissemination of novel datasets and through educational activities.