Graphs, Computation, and Language
Creators: name: Ustalov, Dmitry
Publisher: name: Zenodo
Year: 2022
Subjects: Centrality
Chinese Whispers
Classification Evaluation
Clustering Evaluation
Co-occurrence Graphs
DeepWalk
Evaluation
Graph Attention Network
Graph Clustering
Graph Convolutional Network
Graph Embeddings
Graph Theory
Hearst Patterns
Inter-Rater Agreement
Knowledge Graphs
Language Graphs
Laplacian Eigenmaps
Linked Data
Louvain
Markov Clustering
Matrix Representations
MaxMax
Natural Language Processing
Network Science
node2vec
OntoLearn
Ontology
PageRank
Poincare Embeddings
Power Method
Quality Assessment
RDF
Ranking Evaluation
Representation Learning
Resource Description Framework
Semantic Networks
Semantic Web
Sparse Matrix
Spectral Clustering
Statistical Testing
Taxonomy
TextRank
TransE
Translating Embeddings
Tutorial
Watset
Word2Vec

description: Employing the properties of linguistic networks allows discovering structure and making predictions. This course seeks answers to three questions: (1) how to express the linguistic phenomena as graphs, (2) how to gain knowledge based on them, and (3) how to assess the quality of this knowledge. We will start with traditional graph-based Natural Language Processing (NLP) methods like TextRank and Markov Clustering and finish with such contemporary Machine Learning techniques as DeepWalk and Graph Convolutional Networks. As the growing interest in NLP methods urges their meaningful evaluation, we pay special attention to quality assessment and human judgements. The course has five lectures on Language Graphs, Graph Clustering, Graph Embeddings, Knowledge Graphs, and Evaluation. They elaborately go through the essential algorithms step-by-step, discuss case studies, and suggest insightful references and datasets. The target audience is undergraduate and graduate students, data analysts, and interdisciplinary researchers (but it is not limited to them). The course was held in person in August 2022 at the 33rd European Summer School in Logic, Language and Information (ESSLLI 2022) in Galway, Ireland: https://2022.esslli.eu/courses-workshops-accepted/week-1-and-2-schedule.html.
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", "Ali, M., Berrendorf, M., Hoyt, C.T., Vermue, L., Sharifzadeh, S., Tresp, V., Lehmann, J.: PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings. Journal of Machine Learning Research. 22, 1\u20136 (2021)", "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 1. 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", "Bartunov, S., Kondrashkin, D., Osokin, A., Vetrov, D.: Breaking Sticks and Ambiguities with Adaptive Skip-gram. In: Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. pp. 130\u2013138. PMLR, Cadiz, Spain (2016)", "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", "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", "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.: 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.: Structure Discovery in Natural Language. Springer Berlin Heidelberg (2012). https://doi.org/10.1007/978-3-642-25923-4", "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", "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", "Bonnabel, S.: Stochastic Gradient Descent on Riemannian Manifolds. IEEE Transactions on Automatic Control. 58, 2217\u20132229 (2013). https://doi.org/10.1109/TAC.2013.2254619", "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", "Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., Yakhnenko, O.: Translating Embeddings for Modeling Multi-relational Data. In: Advances in Neural Information Processing Systems 26. pp. 2787\u20132795. Curran Associates, Inc., Lake Tahoe, NV, USA (2013)", "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)", "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", "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", "Brody, S., Alon, U., Yahav, E.: How Attentive are Graph Attention Networks? In: 10th International Conference on Learning Representations. OpenReview.net, Virtual (2022)", "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", "Camacho-Collados, J., Delli Bovi, C., Espinosa-Anke, L., Oramas, S., Pasini, T., Santus, E., Shwartz, V., Navigli, R., Saggion, H.: SemEval-2018 Task 9: Hypernym Discovery. In: Proceedings of The 12th International Workshop on Semantic Evaluation. pp. 712\u2013724. Association for Computational Linguistics, New Orleans, LA, USA (2018). https://doi.org/10.18653/v1/S18-1115", "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", "Cimiano, P., Chiarcos, C., McCrae, J.P., Gracia, J.: Linguistic Linked Data: Representation, Generation and Applications. Springer International Publishing (2020). https://doi.org/10.1007/978-3-030-30225-2", "Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press (2022)", "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", "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", "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 1 (Long and Short Papers). pp. 4171\u20134186. Association for Computational Linguistics, Minneapolis, MN, USA (2019). https://doi.org/10.18653/v1/N19-1423", "Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik. 1, 269\u2013271 (1959). https://doi.org/10.1007/BF01386390", "Dong, X., Gabrilovich, E., Heitz, G., Horn, W., Lao, N., Murphy, K., Strohmann, T., Sun, S., Zhang, W.: Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 601\u2013610. Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2623330.2623623", "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", "Dorogovtsev, S.N., Mendes, J.F.F.: The Nature of Complex Networks. Oxford University Press, Oxford, UK (2022)", "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 2. 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 1: Long Papers). pp. 1383\u20131392. Association for Computational Linguistics, Melbourne, VIC, Australia (2018). https://doi.org/10.18653/v1/P18-1128", "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", "Faralli, S., Panchenko, A., Biemann, C., Ponzetto, S.P.: Linked Disambiguated Distributional Semantic Networks. In: The Semantic Web \u2013 ISWC 2016, 15th International Semantic Web Conference, Kobe, Japan, October 17\u201321, 2016, Proceedings, Part II. pp. 56\u201364. Springer International Publishing, Cham, Switzerland (2016). https://doi.org/10.1007/978-3-319-46547-0_7", "Faruqui, M., Dodge, J., Jauhar, S.K., Dyer, C., Hovy, E., Smith, N.A.: Retrofitting Word Vectors to Semantic Lexicons. In: Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1606\u20131615. Association for Computational Linguistics, Denver, CO, USA (2015). https://doi.org/10.3115/v1/N15-1184", "Fellbaum, C.: WordNet: An Electronic Database. MIT Press, Massachusetts, MA, USA (1998). https://doi.org/10.7551/mitpress/7287.001.0001", "Fey, M., Lenssen, J.E.: Fast Graph Representation Learning with PyTorch Geometric. In: ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds, New Orleans, LA, USA (2019)", "Fillmore, C.J.: Frame Semantics. In: Linguistics in the Morning Calm. pp. 111\u2013137. Hanshin Publishing Co., Seoul, South Korea (1982)", "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 1: 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", "Fu, R., Guo, J., Qin, B., Che, W., Wang, H., Liu, T.: Learning Semantic Hierarchies via Word Embeddings. In: Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers. pp. 1199\u20131209. Association for Computational Linguistics, Baltimore, MD, USA (2014). https://doi.org/10.3115/v1/P14-1113", "Gallardo, P.F.: Google's secret and Linear Algebra. EMS Newsletter. 63, 10\u201315 (2007)", "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., de Montjoye, Y.-A., Clauset, A.: Performance of modularity maximization in practical contexts. Physical Review E. 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", "G\u00f6sgens, M., Tikhonov, A., Prokhorenkova, L.: Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures. In: Proceedings of the 38th International Conference on Machine Learning. pp. 3799\u20133808. PMLR, Online (2021)", "G\u00f6sgens, M., Zhiyanov, A., Tikhonov, A., Prokhorenkova, L.: Good Classification Measures and How to Find Them. In: Advances in Neural Information Processing Systems 34. pp. 17136\u201317147. Curran Associates, Inc., Online (2021)", "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)", "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, X., Cao, S., Lv, X., Lin, Y., Liu, Z., Sun, M., Li, J.: OpenKE: An Open Toolkit for Knowledge Embedding. In: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. pp. 139\u2013144. Association for Computational Linguistics, Brussels, Belgium (2018). https://doi.org/10.18653/v1/D18-2024", "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 136: A K-Means Clustering Algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics). 28, 100\u2013108 (1979). https://doi.org/10.2307/2346830", "Hearst, M.A.: Automatic Acquisition of Hyponyms from Large Text Corpora. In: Proceedings of the 14th Conference on Computational Linguistics - Volume 2. pp. 539\u2013545. Association for Computational Linguistics, Nantes, France (1992). https://doi.org/10.3115/992133.992154", "Heo, Y.-J., Kim, E.-S., Choi, W.S., Zhang, B.-T.: Hypergraph Transformer: Weakly-Supervised Multi-hop Reasoning for Knowledge-based Visual Question Answering. In: Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 373\u2013390. Association for Computational Linguistics, Dublin, Ireland (2022). https://doi.org/10.18653/v1/2022.acl-long.29", "Hitzler, P.: A Review of the Semantic Web Field. Communications of the ACM. 64, 76\u201383 (2021). https://doi.org/10.1145/3397512", "Hochreiter, S., Schmidhuber, J.: Long Short-Term Memory. Neural Computation. 9, 1735\u20131780 (1997). https://doi.org/10.1162/neco.1997.9.8.1735", "Hogan, A., Blomqvist, E., Cochez, M., D'amato, C., Melo, G.D., Gutierrez, C., Kirrane, S., Gayo, J.E.L., Navigli, R., Neumaier, S., Ngomo, A.-C.N., Polleres, A., Rashid, S.M., Rula, A., Schmelzeisen, L., Sequeda, J., Staab, S., Zimmermann, A.: Knowledge Graphs. ACM Computing Surveys. 54, 1\u201337 (2021). https://doi.org/10.1145/3447772", "Hope, D., Keller, B.: MaxMax: A Graph-Based Soft Clustering Algorithm Applied to Word Sense Induction. In: Computational Linguistics and Intelligent Text Processing, 14th International Conference, CICLing 2013, Samos, Greece, March 24-30, 2013, Proceedings, Part I. pp. 368\u2013381. Springer Berlin Heidelberg, Berlin; Heidelberg, Germany (2013). https://doi.org/10.1007/978-3-