Graphs, Computation, and Language

Graphs, Computation, and Language (GCL) is a series of tutorials by Dmitry Ustalov dedicated to human-computer interaction systems, graph theory, and computational linguistics. The tutorials discuss their real-world applications and elaborately go through the corresponding algorithms step-by-step.

Currently the GCL series includes two tutorials:

The tutorial slides are licensed under a CC BY-NC-SA 4.0 license and are available via the corresponding DOI links below.

GCL has been accepted as a course to the 13th Russian Summer School in Information Retrieval (RuSSIR 2020)!

Nearest Neighbor Graph

Nearest Neighbor Graph
(Source: Wikimedia)

Crowdsourcing for Language Resources and Evaluation


Crowdsourcing is an efficient approach for knowledge acquisition and data annotation that enables building impressive human-computer systems. In this tutorial we will discuss the relations between Crowdsourcing and Natural Language Processing, focusing on its practical use for Language Resource construction and evaluation. We will describe the established genres of crowdsourcing, show their strengths and weaknesses on real-world examples and case studies, and provide recommendations for ensuring the high quality of the crowdsourced annotation.

Crowdsourcing for Language Resources and Evaluation (DOI: 10.5281/zenodo.3960805)


  1. Introduction
  2. Wisdom of the Crowds
  3. Microtasks
  4. Games with a Purpose
  5. Miscellaneous
  6. Conclusion

Tutorial at AINL 2019 in Tartu, Estonia

Tutorial at AINL 2019 in Tartu, Estonia

Graph Clustering for Natural Language Processing


Graph-based representations are proven to be an effective approach for a variety of Natural Language Processing (NLP) tasks. Graph clustering makes it possible to extract useful knowledge by exploiting the implicit structure of the data. In this tutorial we will present several efficient graph clustering algorithms, show their strengths and weaknesses as well as their implementations and applications. Then, the evaluation methodology in unsupervised NLP tasks will be discussed.

Graph Clustering for Natural Language Processing (DOI: 10.5281/zenodo.1161505)


  1. Introduction
  2. Graph Theory Recap
  3. Clustering Algorithms
  4. Evaluation
  5. Case Studies
  6. Miscellaneous
  7. Conclusion

Tutorial at AINL 2018 in Saint Petersburg, Russia

Tutorial at AINL 2018 in Saint Petersburg, Russia