ACL 2010 Workshop

Recent years have shown an increased amount of interest in applying graph theoretic models to computational linguistics. Both graph theory and computational linguistics are well studied disciplines, which have traditionally been perceived as distinct, embracing different algorithms, different applications, and different potential end-users. However, as recent research work has shown, the two seemingly distinct disciplines are in fact intimately connected, with a large variety of Natural Language Processing (NLP) applications adopting effcient and elegant solutions from graph-theoretical framework.

Traditional graph theory, which is studied as a sub-discipline of mathematics, as well as complex network theory, a popular modeling paradigm in statistical mechanics and physics of complex systems, have been successfully applied in modeling and solving several applications in NLP. These disciplines are proven to be a promising tool in understanding the structure and dynamics of languages. Graphs are natural ways to encode information for NLP. Entities can be naturally represented as nodes and relations between them can be represented as edges. Recent research has shown that graph-based representations of linguistic units as diverse as words, sentences and documents give rise to novel and efficient solutions in a variety of tasks, ranging from part-of-speech tagging, word sense disambiguation and parsing to information extraction, semantic role labeling, summarization, and sentiment analysis. Complex network-based models have been applied to areas as diverse as language evolution, acquisition, historical linguistics, mining and analyzing the social networks of blogs and emails, link analysis and information retrieval, information extraction, and representation of the mental lexicon.

The TextGraphs workshop series addresses a broad spectrum of research areas and brings together specialists working on graph-based models and algorithms for natural language processing and computational linguistics, as well as on the theoretical foundations of related graph-based methods. This workshop is aimed at fostering an exchange of ideas by facilitating a discussion about both the techniques and the theoretical justification of the empirical results among the NLP community members. Spawning a deeper understanding of the basic theoretical principles involved, such interaction is vital to the further progress of graph-based NLP applications.

Special Theme

Previous TextGraphs workshops have featured special themes (such as "Cognitive and Social Dynamics of Languages in the framework of Complex Networks" in Textgraphs-4, and "Large Scale Lexical Acquisition and Representation" in TextGraphs-3), or conducted tutorials (such as "Graph-based methods for IR and NLP"). For the fifth edition of TextGraphs, we propose the special theme: "Graph Methods for Opinion analysis". This choice is motivated by two important factors: (1) advanced opinion analysis that aims to go beyond polarity recognition necessitates the integration of syntactic, semantic and logic structures and (2) previous work in NLP has shown that graph methods are very well suited to represent and exploit such structures in learning systems.

The aim is to bring together researchers from graph theory and opinion analysis in order to enable cross-fertilization of ideas. The proposed theme will encourage publication of early results and initiate discussions of issues in this area. We hope that this will help to shape future directions for ambitious opinion analysis research and provide new, challenging problem motivation for research in graph algorithms.

In more detail, the positive aspects of the theme are:

• Opinion and Sentiment analysis research has garnered great interest in recent times. Research in this field spans a wide array of NLP problems like word semantics, lexicon induction, discourse analysis, multilingual analysis and multi-modal processing.
• Graph-based approaches such as label propagation, min-cut, potts model and random walks have been also studied for opinion analysis and TextGraphs has been the natural venue for the publication of part of this work.
• Graphs provide an effective framework for representing different types of interrelated information, which are promising for opinion analysis, e.g. orientation relations between words at the semantic level, relations between sentences at the discourse level or relations between speeches (or speakers) at the dialog level.

Finally, as the field of opinion mining advances towards deeper analysis and more complex systems, graphical approaches may become even more pertinent. For instance, graphs may be employed to capture opinion dynamics over time, or to model interactions between opinion expressions across multiple modalities and, to realize this, new graph-based algorithms and inference methods may need to be developed.

List of the Workshop Topics

Overall TextGraphs-5 will invite submissions on the following (but not limited to) general topics:

• Graph methods for sentiment lexicon induction
• Analysis of blog and web linking structures
• Graph methods for sentiment/opinion propagation
• Graph representation of data for opinion analysis
• Synonym/antonym graphs and their usage to extrapolate semantic orientation
• Social graphs and opinion analysis
• Graph-based representations, acquisition and evaluation of lexicon and ontology
• Dynamic graph representations for NLP
• Properties of lexical, semantic, syntactic and phonological graphs
• Clustering-based algorithms
• Application of spectral graph theory in NLP
• Unsupervised and semi-supervised learning models based-on graphs
• Dynamic graph representations for NLP
• Comparative analysis of graph-based methods and traditional machine learning techniques for NLP applications
• Kernel Methods for Graphs, e.g. random walk, tree and sequence kernels
• Graph methods for NLP tasks, e.g. morpho-syntactic annotation, word sense disambiguation, syntactic/semantic parsing
• Graph methods for NLP applications, e.g. retrieval, extraction and summarization of information
• Semantic inference using graphs, e.g. question answering and text entailment recognition

Both submission and review processes are double blind and handled electronically.