Graphs, Computation, and Language
Creators: name: Ustalov, Dmitry
Publisher: name: Zenodo
Year: 2021
Subjects: Bradley-Terry
Centrality
Chinese Whispers
Classification Evaluation
Clustering Evaluation
Co-occurrence Graphs
Crowdsourcing
Dawid-Skene
DeepWalk
Evaluation
Games with a Purpose
Graph Clustering
Graph Convolutional Network
Graph Embeddings
Graph Theory
GraphSAGE
Inter-Rater Agreement
Language Graphs
Laplacian Eigenmaps
Louvain
Markov Clustering
Matrix Representations
MaxMax
Microtasks
Natural Language Processing
Network Science
PageRank
Power Method
Quality Assessment
Quality Control
Ranking Evaluation
Representation Learning
Semantic Networks
Sparse Matrix
Spectral Clustering
Statistical Testing
TextRank
Tutorial
Watset
Wikipedia
Wisdom of the Crowds
Word2Vec
reCAPTCHA

description: Graphs and networks offer a convenient way to study systems around us, including such complex ones as human language. Graph-based representations are proven to be a practical approach for a wide variety of Natural Language Processing (NLP) tasks. This course has five lectures on Language Graphs, Graph Clustering, Graph Embeddings, Evaluation, and Crowdsourcing. They elaborately go through the corresponding algorithms step-by-step and suggest important linguistic datasets. The target audience of this course is advanced graduate students, data analysts, and researchers in NLP and IR (but it is not limited to them). The course is held online in Spring 2021 at Computer Science Club in Saint Petersburg, Russia: https://compsciclub.ru/en/courses/graphscomplang/2021-spring/. Lectures are in Russian, but the slides are in English.
description: {"references": ["Agirre, E., L\u00f3pez de Lacalle, O., Soroa, A.: Random Walks for Knowledge-Based Word Sense Disambiguation. Computational Linguistics. 40, 57\u201384 (2014). https://doi.org/10.1162/COLI_a_00164.", "von Ahn, L., Dabbish, L.: Labeling Images with a Computer Game. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. pp. 319\u2013326. ACM, Vienna, Austria (2004). https://doi.org/10.1145/985692.985733.", "von Ahn, L., Dabbish, L.: Designing Games with a Purpose. Communications of the ACM. 51, 58\u201367 (2008). https://doi.org/10.1145/1378704.1378719.", "von Ahn, L., Maurer, B., McMillen, C., Abraham, D., Blum, M.: reCAPTCHA: Human-Based Character Recognition via Web Security Measures. Science. 321, 1465\u20131468 (2008). https://doi.org/10.1126/science.1160379.", "Alonso, O.: The Practice of Crowdsourcing. Morgan &amp; Claypool Publishers (2019). https://doi.org/10.2200/S00904ED1V01Y201903ICR066.", "Alonso, O., Rose, D.E., Stewart, B.: Crowdsourcing for Relevance Evaluation. SIGIR Forum. 42, 9\u201315 (2008). https://doi.org/10.1145/1480506.1480508.", "Ardila, R., Branson, M., Davis, K., Henretty, M., Kohler, M., Meyer, J., Morais, R., Saunders, L., Tyers, F.M., Weber, G.: Common Voice: A Massively-Multilingual Speech Corpus. In: Proceedings of The 12th Language Resources and Evaluation Conference. pp. 4218\u20134222. European Language Resources Association (ELRA), Marseille, France (2020).", "Artstein, R., Poesio, M.: Inter-Coder Agreement for Computational Linguistics. Computational Linguistics. 34, 555\u2013596 (2008). https://doi.org/10.1162/coli.07-034-R2.", "Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R., Ives, Z.: DBpedia: A Nucleus for a Web of Open Data. In: The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007, Busan, Korea, November 11\u201315, 2007. Proceedings. pp. 722\u2013735. Springer Berlin Heidelberg, Berlin; Heidelberg, Germany (2007). https://doi.org/10.1007/978-3-540-76298-0_52.", "Azadani, M.N., Ghadiri, N., Davoodijam, E.: Graph-based biomedical text summarization: An itemset mining and sentence clustering approach. Journal of Biomedical Informatics. 84, 42\u201358 (2018). https://doi.org/10.1016/j.jbi.2018.06.005.", "Baker, C.F., Fillmore, C.J., Lowe, J.B.: The Berkeley FrameNet Project. In: Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume\u00a01. pp. 86\u201390. Association for Computational Linguistics, Montr\u00e9al, QC, Canada (1998). https://doi.org/10.3115/980845.980860.", "Barab\u00e1si, A.-L., Albert, R.: Emergence of Scaling in Random Networks. Science. 286, 509\u2013512 (1999). https://doi.org/10.1126/science.286.5439.509.", "Bavelas, A.: Communication Patterns in Task-Oriented Groups. The Journal of the Acoustical Society of America. 22, 725\u2013730 (1950). https://doi.org/10.1121/1.1906679.", "Belkin, M., Niyogi, P.: Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation. 15, 1373\u20131396 (2003). https://doi.org/10.1162/089976603321780317.", "Bernstein, M.S., Little, G., Miller, R.C., Hartmann, B., Ackerman, M.S., Karger, D.R., Crowell, D., Panovich, K.: Soylent: A Word Processor with a Crowd Inside. In: Proceedings of the 23Nd Annual ACM Symposium on User Interface Software and Technology. pp. 313\u2013322. ACM, New York, NY, USA (2010). https://doi.org/10.1145/1866029.1866078.", "Biemann, C.: Chinese Whispers: An Efficient Graph Clustering Algorithm and Its Application to Natural Language Processing Problems. In: Proceedings of the First Workshop on Graph Based Methods for Natural Language Processing. pp. 73\u201380. Association for Computational Linguistics, New York, NY, USA (2006). https://doi.org/10.3115/1654758.1654774.", "Biemann, C.: Structure Discovery in Natural Language. Springer Berlin Heidelberg (2012). https://doi.org/10.1007/978-3-642-25923-4.", "Biemann, C.: Creating a system for lexical substitutions from scratch using crowdsourcing. Language Resources and Evaluation. 47, 97\u2013122 (2013). https://doi.org/10.1007/s10579-012-9180-5.", "Biemann, C., Riedl, M.: Text: now in 2D! A framework for lexical expansion with contextual similarity. Journal of Language Modelling. 1, 55\u201395 (2013). https://doi.org/10.15398/jlm.v1i1.60.", "Bird, S., Klein, E., Loper, E.: Natural Language Processing with Python. O'Reilly Media (2017).", "Blondel, V.D., Guillaume, J.-L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment. 2008, P10008 (2008). https://doi.org/10.1088/1742-5468/2008/10/P10008.", "Blumenstock, J.E.: Size Matters: Word Count As a Measure of Quality on Wikipedia. In: Proceedings of the 17th International Conference on World Wide Web. pp. 1095\u20131096. ACM, Beijing, China (2008). https://doi.org/10.1145/1367497.1367673.", "Bocharov, V., Alexeeva, S., Granovsky, D., Protopopova, E., Stepanova, M., Surikov, A.: Crowdsourcing morphological annotation. In: Computational Linguistics and Intellectual Technologies: papers from the Annual conference \"Dialogue\". pp. 109\u2013124. RGGU (2013).", "Bojanowski, P., Grave, E., Joulin, A., Mikolov, T.: Enriching Word Vectors with Subword Information. Transactions of the Association for Computational Linguistics. 5, 135\u2013146 (2017). https://doi.org/10.1162/tacl_a_00051.", "Bonacich, P.: Power and Centrality: A Family of Measures. American Journal of Sociology. 92, 1170\u20131182 (1987). https://doi.org/10.1086/228631.", "Bordea, G., Lefever, E., Buitelaar, P.: SemEval-2016 Task 13: Taxonomy Extraction Evaluation (TExEval-2). In: Proceedings of the 10th International Workshop on Semantic Evaluation. pp. 1081\u20131091. Association for Computational Linguistics, San Diego, CA, USA (2016). https://doi.org/10.18653/v1/S16-1168.", "Bordes, A., Chopra, S., Weston, J.: Question Answering with Subgraph Embeddings. In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. pp. 615\u2013620. Association for Computational Linguistics, Doha, Qatar (2014). https://doi.org/10.3115/v1/D14-1067.", "Boudin, F.: A Comparison of Centrality Measures for Graph-Based Keyphrase Extraction. In: Proceedings of the Sixth International Joint Conference on Natural Language Processing. pp. 834\u2013838. Asian Federation of Natural Language Processing, Nagoya, Japan (2013).", "Bradley, R.A., Terry, M.E.: Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons. Biometrika. 39, 324\u2013345 (1952). https://doi.org/10.2307/2334029.", "Bragg, J., Mausam, Weld, D.S.: Sprout: Crowd-Powered Task Design for Crowdsourcing. In: Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology. pp. 165\u2013176. ACM, Berlin, Germany (2018). https://doi.org/10.1145/3242587.3242598.", "Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Social Networks. 30, 136\u2013145 (2008). https://doi.org/10.1016/j.socnet.2007.11.001.", "Braslavski, P., Ustalov, D., Mukhin, M.: A Spinning Wheel for YARN: User Interface for a Crowdsourced Thesaurus. In: Proceedings of the Demonstrations at the 14th Conference of the European Chapter of the Association for Computational Linguistics. pp. 101\u2013104. Association for Computational Linguistics, Gothenburg, Sweden (2014). https://doi.org/10.3115/v1/E14-2026.", "Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems. 30, 107\u2013117 (1998). https://doi.org/10.1016/S0169-7552(98)00110-X.", "Buckley, C., Voorhees, E.M.: Evaluating Evaluation Measure Stability. In: Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 33\u201340. Association for Computing Machinery, Athens, Greece (2000). https://doi.org/10.1145/345508.345543.", "Cai, H., Zheng, V.W., Chen-Chuan Chang, K.: A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications. IEEE Transactions on Knowledge and Data Engineering. 30, 1616\u20131637 (2018). https://doi.org/10.1109/TKDE.2018.2807452.", "Callison-Burch, C.: Fast, Cheap, and Creative: Evaluating Translation Quality Using Amazon's Mechanical Turk. In: Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing. pp. 286\u2013295. Association for Computational Linguistics; Asian Federation of Natural Language Processing, Singapore (2009). https://doi.org/10.3115/1699510.1699548.", "Chang, J., Boyd-Graber, J., Gerrish, S., Wang, C., Blei, D.M.: Reading Tea Leaves: How Humans Interpret Topic Models. In: Advances in Neural Information Processing Systems 22. pp. 288\u2013296. Curran Associates, Inc., Vancouver, BC, Canada (2009).", "Chapelle, O., Metlzer, D., Zhang, Y., Grinspan, P.: Expected Reciprocal Rank for Graded Relevance. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management. pp. 621\u2013630. Association for Computing Machinery, Hong Kong, China (2009). https://doi.org/10.1145/1645953.1646033.", "Chen, D., Lin, Y., Li, W., Li, P., Zhou, J., Sun, X.: Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. Proceedings of the AAAI Conference on Artificial Intelligence. 34, 3438\u20133445 (2020). https://doi.org/10.1609/aaai.v34i04.5747.", "Chicco, D., Jurman, G.: The advantages of the Matthews correlation coefficient (MCC) over F1 score and accuracy in binary classification evaluation. BMC Genomics. 21, 6 (2020). https://doi.org/10.1186/s12864-019-6413-7.", "Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2009).", "Cs\u00e1rdi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Systems. 1695, 1\u20139 (2006).", "Dacrema, M.F., Cremonesi, P., Jannach, D.: Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches. In: Proceedings of the 13th ACM Conference on Recommender Systems. pp. 101\u2013109. Association for Computing Machinery, Copenhagen, Denmark (2019). https://doi.org/10.1145/3298689.3347058.", "Daniel, F., Kucherbaev, P., Cappiello, C., Benatallah, B., Allahbakhsh, M.: Quality Control in Crowdsourcing: A Survey of Quality Attributes, Assessment Techniques, and Assurance Actions. ACM Computing Surveys. 51, 7:1\u20137:40 (2018). https://doi.org/10.1145/3148148.", "Davis, J., Goadrich, M.: The Relationship between Precision-Recall and ROC Curves. In: Proceedings of the 23rd International Conference on Machine Learning. pp. 233\u2013240. Association for Computing Machinery, Pittsburgh, PA, USA (2006). https://doi.org/10.1145/1143844.1143874.", "Dawid, A.P., Skene, A.M.: Maximum Likelihood Estimation of Observer Error-Rates Using the EM Algorithm. Journal of the Royal Statistical Society: Series\u00a0C (Applied Statistics). 28, 20\u201328 (1979). https://doi.org/10.2307/2346806.", "Devlin, J., Chang, M.-W., Lee, K., Toutanova, K.: BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume\u00a01 (Long and Short Papers). pp. 4171\u20134186. Association for Computational Linguistics, Minneapolis, MN, USA (2019). https://doi.org/10.18653/v1/N19-1423.", "Difallah, D.E., Demartini, G., Cudr\u00e9-Mauroux, P.: Pick-A-Crowd: Tell Me What You Like, and I'll Tell You What to Do. In: Proceedings of the 22Nd International Conference on World Wide Web. pp. 367\u2013374. ACM, Rio de Janeiro, Brazil (2013). https://doi.org/10.1145/2488388.2488421.", "Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik. 1, 269\u2013271 (1959). https://doi.org/10.1007/BF01386390.", "van Dongen, S.: Graph Clustering by Flow Simulation, (2000).", "Dorogovtsev, S.N., Mendes, J.F.F.: Language as an evolving word web. Proceedings of the Royal Society of London B: Biological Sciences. 268, 2603\u20132606 (2001). https://doi.org/10.1098/rspb.2001.1824.", "Dorow, B., Widdows, D.: Discovering Corpus-Specific Word Senses. In: Proceedings of the Tenth Conference on European Chapter of the Association for Computational Linguistics - Volume\u00a02. pp. 79\u201382. Association for Computational Linguistics, Budapest, Hungary (2003). https://doi.org/10.3115/1067737.1067753.", "Dror, R., Baumer, G., Shlomov, S., Reichart, R.: The Hitchhiker's Guide to Testing Statistical Significance in Natural Language Processing. In: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume\u00a01: Long Papers). pp. 1383\u20131392. Association for Computational Linguistics, Melbourne, VIC, Australia (2018). https://doi.org/10.18653/v1/P18-1128.", "Dwivedi, V.P., Joshi, C.K., Laurent, T., Bengio, Y., Bresson, X.: Benchmarking Graph Neural Networks, https://arxiv.org/abs/2003.00982, (2020).", "Estell\u00e9s-Arolas, E., Gonz\u00e1lez-Ladr\u00f3n-de-Guevara, F.: Towards an integrated crowdsourcing definition. Journal of Information Science. 38, 189\u2013200 (2012). https://doi.org/10.1177/0165551512437638.", "Esteves, D., Rula, A., Reddy, A.J., Lehmann, J.: Toward Veracity Assessment in RDF Knowledge Bases: An Exploratory Analysis. Journal of Data and Information Quality. 9, 16:1\u201316:26 (2018). https://doi.org/10.1145/3177873.", "Faralli, S., Panchenko, A., Biemann, C., Ponzetto, S.P.: Linked Disambiguated Distributional Semantic Networks. In: The Semantic Web \u2013 ISWC\u00a02016, 15th International Semantic Web Conference, Kobe, Japan, October 17\u201321, 2016, Proceedings, Part\u00a0II. pp. 56\u201364. Springer International Publishing, Cham, Switzerland (2016). https://doi.org/10.1007/978-3-319-46547-0_7.", "Fellbaum, C.: WordNet: An Electronic Database. MIT Press (1998).", "Fey, M., Lenssen, J.E.: Fast Graph Representation Learning with PyTorch Geometric. In: ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds (2019).", "Fillmore, C.J.: Frame Semantics. In: Linguistics in the Morning Calm. pp. 111\u2013137. Hanshin Publishing Co., Seoul, South Korea (1982).", "Finin, T., Murnane, W., Karandikar, A., Keller, N., Martineau, J., Dredze, M.: Annotating Named Entities in Twitter Data with Crowdsourcing. In: Proceedings of the NAACL\u00a0HLT 2010 Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk. pp. 80\u201388. Association for Computational Linguistics, Los Angeles, CA, USA (2010).", "Finnerty, A., Kucherbaev, P., Tranquillini, S., Convertino, G.: Keep It Simple: Reward and Task Design in Crowdsourcing. In: Proceedings of the Biannual Conference of the Italian Chapter of SIGCHI. pp. 14:1\u201314:4. ACM, Trento, Italy (2013). https://doi.org/10.1145/2499149.2499168.", "Florescu, C., Caragea, C.: PositionRank: An Unsupervised Approach to Keyphrase Extraction from Scholarly Documents. In: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume\u00a01: Long Papers). pp. 1105\u20131115. Association for Computational Linguistics, Vancouver, BC, Canada (2017). https://doi.org/10.18653/v1/P17-1102.", "Fortunato, S.: Community detection in graphs. Physics Reports. 486, 75\u2013174 (2010). https://doi.org/10.1016/j.physrep.2009.11.002.", "Fowlkes, E.B., Mallows, C.L.: A Method for Comparing Two Hierarchical Clusterings. Journal of the American Statistical Association. 78, 553\u2013569 (1983). https://doi.org/10.1080/01621459.1983.10478008.", "Freeman, L.C.: A Set of Measures of Centrality Based on Betweenness. Sociometry. 40, 35\u201341 (1977). https://doi.org/10.2307/3033543.", "Frey, B.J., Dueck, D.: Clustering by Passing Messages Between Data Points. Science. 315, 972\u2013976 (2007). https://doi.org/10.1126/science.1136800.", "Gadiraju, U., Demartini, G., Kawase, R., Dietze, S.: Crowd Anatomy Beyond the Good and Bad: Behavioral Traces for Crowd Worker Modeling and Pre-selection. Computer Supported Cooperative Work (CSCW). 28, 815\u2013841 (2019). https://doi.org/10.1007/s10606-018-9336-y.", "Gallardo, P.F.: Google's secret and Linear Algebra. EMS Newsletter. 63, 10\u201315 (2007).", "Geiger, R.S., Halfaker, A.: When the Levee Breaks: Without Bots, What Happens to Wikipedia's Quality Control Processes? In: Proceedings of the 9th International Symposium on Open Collaboration. pp. 6:1\u20136:6. ACM, Hong Kong, China (2013). https://doi.org/10.1145/2491055.2491061.", "Goldhahn, D., Eckart, T., Quasthoff, U.: Building Large Monolingual Dictionaries at the Leipzig Corpora Collection: From 100 to 200 Languages. In: Proceedings of the Eight International Conference on Language Resources and Evaluation. pp. 759\u2013765. European Language Resources Association (ELRA), Istanbul, Turkey (2012).", "Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: GraphX: Graph Processing in a Distributed Dataflow Framework. In: 11th USENIX Symposium on Operating Systems Design and Implementation. pp. 599\u2013613. USENIX Association, Broomfield, CO, USA (2014).", "Good, B.H., Montjoye, Y.-A. de, Clauset, A.: Performance of modularity maximization in practical contexts. Physical Review\u00a0E. 81, 046106 (2010). https://doi.org/10.1103/PhysRevE.81.046106.", "Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press, Cambridge, MA, USA (2016).", "Gorodkin, J.: Comparing two K-category assignments by a K-category correlation coefficient. Computational Biology and Chemistry. 28, 367\u2013374 (2004). https://doi.org/10.1016/j.compbiolchem.2004.09.006.", "Goyal, P., Ferrara, E.: Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems. 151, 78\u201394 (2018). https://doi.org/10.1016/j.knosys.2018.03.022.", "Grover, A., Leskovec, J.: node2vec: Scalable Feature Learning for Networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 855\u2013864. ACM, San Francisco, CA, USA (2016). https://doi.org/10.1145/2939672.2939754.", "Gurevych, I., Kim, J. eds: The People's Web Meets NLP: Collaboratively Constructed Language Resources. Springer-Verlag Berlin Heidelberg, Berlin; Heidelberg, Germany (2013). https://doi.org/10.1007/978-3-642-35085-6.", "Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring Network Structure, Dynamics, and Function using NetworkX. In: Proceedings of the 7th Python in Science Conference. pp. 11\u201315, Pasadena, CA, USA (2008).", "Halfaker, A., Geiger, R.S.: ORES: Lowering Barriers with Participatory Machine Learning in Wikipedia. Proceedings of the ACM on Human-Computer Interaction. 1, 148:1\u2013148:37 (2020). https://doi.org/10.1145/3415219.", "Halfaker, A., Geiger, R.S., Morgan, J.T., Riedl, J.: The Rise and Decline of an Open Collaboration System: How Wikipedia's Reaction to Popularity Is Causing Its Decline. American Behavioral Scientist. 57, 664\u2013688 (2013). https://doi.org/10.1177/0002764212469365.", "Hamilton, W.L., Ying, R., Leskovec, J.: Inductive Representation Learning on Large Graphs. In: Advances in Neural Information Processing Systems 30. pp. 1024\u20131034. Curran Associates, Inc., Vancouver, BC, Canada (2017).", "Han, L., Checco, A., Difallah, D., Demartini, G., Sadiq, S.: Modelling User Behavior Dynamics with Embeddings. In: Proceedings of the 29th ACM International Conference on Information &amp; Knowledge Management. pp. 445\u2013454. Association for Computing Machinery, Virtual Event, Ireland (2020). https://doi.org/10.1145/3340531.3411985.", "Hansen, P.C.: The truncatedSVD as a method for regularization. BIT Numerical Mathematics. 27, 534\u2013553 (1987). https://doi.org/10.1007/BF01937276.", "Hartigan, J.A., Wong, M.A.: Algorithm AS\u00a0136: A K-Means Clustering Al