Text Analytics: Graph-based Methods for NLP

Graph-based methods for NLP

The seminar takes place Thursdays, 14:15 – 15:45 in S2|02 room A126.


Graphs have become more and more popular in the area of knowledge processing during the last years. In particular, if the underlying resources already contain a graph structure, such as the Wikipedia link graph, for example, that connects related concepts, it seems natural to make use of this structure by means of graph algorithms. Otherwise, graph structures have to be established first by modeling the problem in an appropriate way. Nevertheless, graphs grant some obvious benefits from an algorithmic perspective: there are efficient algorithms for a wide variety of problems, that take into account both, local as well as global relations such as neighborhoods of entities.

The seminar provides detailed coverage of current graph approaches in natural language processing and information retrieval, their strengths and limitations, and current research directions by including recent research papers. In the course of the seminar, students will acquire key skills like the fundamentals in academic research and scientific writing, and they will be encouraged to improve their presentation skills.

Applications include but are not limited to:

  • Word Sense Disambiguation
  • Text Similarity
  • Sentiment Analysis / Opinion Mining
  • Question Answering
  • Word Sense Induction
  • Named Entities
  • Wikipedia discussion / revisions
  • Text Quality Assesment
  • Cross-lingual retrieval

Methods include but are not limited to:

  • Graph Traversal Algorithms
  • Shortest Paths Algorithms
  • Graph Clustering Algorithms
  • Matching / Assignment Algorithms
  • Heuristics, Random Walks, etc.


Jurafsky, Daniel, and James H. Martin (2009). Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. 2nd edition. Prentice-Hall.

For each topic, current research papers will be discussed in class.

Prerequisites and Preparation

Every student should have the knowledge of the introductory chapters of Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics or comparable. It is expected that the texts have been thoroughly worked through by the fourth session at the latest. Knowledge in graph algorithms (for example the lecture “Efficient Graph Algorithms” held in the winter term) are useful but not mandatory.


Each student is expected to

  • give a talk in class and answer some questions afterwards
  • write a term paper
  • show active participation in class

Materials and Forum

Access to course materials will be provided in the first seminar session on 12th of April. The introductory slides can be found here:


Natrural language graphs

Graph algorithms in NLP

For general advice on presenting your topic, please have a look at these guidelines and these helpful instructions.


Dr. Wolfgang Stille: Office hours every Thursday from 11:00 until 12:00

Prof. Dr. Iryna Gurevych

Tucan number for registration: 20-00-0596-se