{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T03:59:29Z","timestamp":1791345569450,"version":"4.3.1"},"reference-count":136,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2015,10,12]],"date-time":"2015-10-12T00:00:00Z","timestamp":1444608000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Nat. Lang. Eng."],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graphs are a powerful representation formalism that can be applied to a variety of aspects related to language processing. We provide an overview of how Natural Language Processing problems have been projected into the graph framework, focusing in particular on graph construction \u2013 a crucial step in modeling the data to emphasize the phenomena targeted.<\/jats:p>","DOI":"10.1017\/s1351324915000340","type":"journal-article","created":{"date-parts":[[2015,10,13]],"date-time":"2015-10-13T02:58:06Z","timestamp":1444705086000},"page":"665-698","source":"Crossref","is-referenced-by-count":40,"title":["A survey of graphs in natural language processing"],"prefix":"10.1017","volume":"21","author":[{"given":"VIVI","family":"NASTASE","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"RADA","family":"MIHALCEA","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"DRAGOMIR R.","family":"RADEV","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2015,10,12]]},"reference":[{"key":"S1351324915000340_ref136","doi-asserted-by":"crossref","unstructured":"Zhu X. , and Lafferty J. 2005. Harmonic mixtures: combining mixture models and graph-based methods for inductive and scalable semi-supervised learning. In Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 7\u201311 August 2005, pp. 1052\u20131059.","DOI":"10.1145\/1102351.1102484"},{"key":"S1351324915000340_ref132","author":"Zhu","year":"2014"},{"key":"S1351324915000340_ref134","unstructured":"Zhu X. 2007. Semi-supervised learning literature survey. Technical Report TR 1530, Computer Sciences, University of Wisconsin, Madison."},{"key":"S1351324915000340_ref127","unstructured":"Yan R. , Lapata M. , and Li X. 2012. Tweet recommendation with graph co-ranking. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, Jeju Island, Korea, 8\u201314 July 2012, pp. 516\u2013525."},{"key":"S1351324915000340_ref123","doi-asserted-by":"crossref","unstructured":"Widdows D. , and Dorow B. 2002. A graph model for unsupervised lexical acquisition. In Proceedings of the 19th International Conference on Computational Linguistics, Taipei, Taiwan, 24 August\u20131 September 2002.","DOI":"10.3115\/1072228.1072342"},{"key":"S1351324915000340_ref121","doi-asserted-by":"crossref","unstructured":"Wan X. 2008. An exploration of document impact on graph-based multi-document summarization. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 755\u2013762.","DOI":"10.3115\/1613715.1613811"},{"key":"S1351324915000340_ref119","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00146"},{"key":"S1351324915000340_ref117","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2010.36.1.36101"},{"key":"S1351324915000340_ref116","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1613\/jair.3118","article-title":"Evaluating temporal graphs built from texts via transitive reduction","volume":"40","author":"Tannier","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1351324915000340_ref113","unstructured":"Szummer M. , and Jaakkola T. 2001. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems, pp. 945\u2013952."},{"key":"S1351324915000340_ref112","unstructured":"Subramanya A. , Petrov S. , and Pereira F. 2010. Efficient graph-based semi-supervised learning of structured tagging models. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, Cambridge, MA, 9\u201311 Ocotber 2010, pp. 167\u2013176."},{"key":"S1351324915000340_ref109","doi-asserted-by":"publisher","DOI":"10.1007\/11744085_46"},{"key":"S1351324915000340_ref107","first-page":"193","article-title":"Automatic text structuring and summarization","volume":"33","author":"Salton","year":"1997","journal-title":"Journal of Information Processing and Management: an International Journal \u2013 Special issue: methods and tools for the automatic construction of hypertext"},{"key":"S1351324915000340_ref105","unstructured":"Razmara M. , Siahbani M. , Haffari R. , and Sarkar A. 2013. Graph propagation for paraphrasing out-of-vocabulary words in statistical machine translation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, Sofia, Bulgaria, 4\u20139 August 2013, pp. 1105\u20131115."},{"key":"S1351324915000340_ref104","doi-asserted-by":"crossref","unstructured":"Rao D. , and Ravichandran D. 2009. Semi-supervised polarity lexicon induction. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, Athens, Greece, 30 March\u20133 April 2009, pp. 675\u2013682.","DOI":"10.3115\/1609067.1609142"},{"key":"S1351324915000340_ref103","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v29i3.2160"},{"key":"S1351324915000340_ref101","volume-title":"Semantic Information Processing","author":"Quillian","year":"1968"},{"key":"S1351324915000340_ref100","unstructured":"Qian T. , Ji D. , Zhang M. , Teng C. , and Xia C. 2014. Word sense induction using lexical chain based hypergraph model. In Proceedings of the 25th International Conference on Computational Linguistics, Dublin, Ireland, 23\u201329 August 2014, pp. 1601\u20131611."},{"key":"S1351324915000340_ref097","doi-asserted-by":"crossref","unstructured":"Pang B. and Lee L. 2004. A sentimental education: sentiment analysis using subjectivity summarization based on minimum cuts. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, 21\u201326 July 2004, pp. 271\u2013278.","DOI":"10.3115\/1218955.1218990"},{"key":"S1351324915000340_ref093","doi-asserted-by":"crossref","unstructured":"Nicolae C. , and Nicolae G. 2006. Bestcut: a graph algorithm for coreference resolution. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, Sydney, Australia, 22\u201323 July 2006, pp. 275\u2013283.","DOI":"10.3115\/1610075.1610115"},{"key":"S1351324915000340_ref086","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1162\/tacl_a_00179","article-title":"Entity linking meets word sense disambiguation: a unified approach","volume":"2","author":"Moro","year":"2014","journal-title":"Transactions of the Association for Computational Linguistics"},{"key":"S1351324915000340_ref085","doi-asserted-by":"crossref","unstructured":"Minkov E. , and Cohen W. W. 2008. Learning graph walk based similarity measures for parsed text. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 907\u2013916.","DOI":"10.3115\/1613715.1613832"},{"key":"S1351324915000340_ref084","doi-asserted-by":"crossref","unstructured":"Mihalcea R. , Tarau R. , and Figa E. 2004. PageRank on semantic networks, with application to word sense disambiguation. In Proceedings of the 20th International Conference on Computational Linguistics, Geneva, Switzerland, 23\u201327 August 2004, pp. 1126\u20131132.","DOI":"10.3115\/1220355.1220517"},{"key":"S1351324915000340_ref083","unstructured":"Mihalcea A. , and Tarau P. 2004. Textrank: bringing order into texts. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, Barcelona, Spain, 25\u201326 July 2004, pp. 404\u2013411."},{"key":"S1351324915000340_ref081","unstructured":"Mihalcea R. , and Moldovan D. 2001. eXtended WordNet: progress report. In Proceedings of NAACL Workshop on WordNet and Other Lexical Resources, pp. 95\u2013100."},{"key":"S1351324915000340_ref080","doi-asserted-by":"crossref","unstructured":"Mihalcea R. 2005. Unsupervised large-vocabulary word sense disambiguation with graph-based algorithms for sequence data labeling. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Canada, 6\u20138 October 2005, pp. 411\u2013418.","DOI":"10.3115\/1220575.1220627"},{"key":"S1351324915000340_ref079","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.86.056111"},{"key":"S1351324915000340_ref077","doi-asserted-by":"crossref","unstructured":"McDonald R. , Pereira F. , Ribarov K. , and Hajic J. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Canada, 6\u20138 October 2005, pp. 523\u2013530.","DOI":"10.3115\/1220575.1220641"},{"key":"S1351324915000340_ref076","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1162\/tacl_a_00217","article-title":"Dijkstra-wsa: a graph-based approach to word sense alignment","volume":"1","author":"Matuschek","year":"2013","journal-title":"Transactions of the Association for Computational Linguistics"},{"key":"S1351324915000340_ref073","doi-asserted-by":"crossref","unstructured":"Malioutov I. , and Barzilay R. 2006. Minimum cut model for spoken lecture segmentation. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Sydney, Australia, 17\u201321 July 2006, pp. 25\u201332.","DOI":"10.3115\/1220175.1220179"},{"key":"S1351324915000340_ref069","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"S1351324915000340_ref067","doi-asserted-by":"crossref","unstructured":"Korkontzelos I. , Klapaftis I. , and Manandhar S. 2009. Graph connectivity measures for unsupervised parameter tuning of graph-based sense induction systems. In Proceedings of the Workshop on Unsupervised and Minimally Supervised Learning of Lexical Semantics, pp. 36\u201344, Boulder, Colorado, USA, June. Association for Computational Linguistics.","DOI":"10.3115\/1641968.1641973"},{"key":"S1351324915000340_ref135","unstructured":"Zhu X. , and Ghahramani Z. 2002. Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University."},{"key":"S1351324915000340_ref063","unstructured":"Klein D. , and Manning C. D. , 2001. Parsing and hypergraphs. In Proceedings of the 7th International Workshop on Parsing Technologies, Beijing, China, 17\u201319 October, pp. 123\u2013134."},{"key":"S1351324915000340_ref106","first-page":"363","article-title":"Transforming graph data for statistical relational learning","volume":"45","author":"Rossi","year":"2012","journal-title":"Journal of Machine Learning Research"},{"key":"S1351324915000340_ref061","doi-asserted-by":"publisher","DOI":"10.3115\/1621474.1621566"},{"key":"S1351324915000340_ref060","doi-asserted-by":"crossref","unstructured":"Johansson R. , and Nieto Pi\u00f1a L. 2015. Embedding a semantic network in a word space. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, Colorado, USA, May 31\u2013June 5 2015, pp. 1428\u20131433.","DOI":"10.3115\/v1\/N15-1164"},{"key":"S1351324915000340_ref130","unstructured":"Zhang Y. , and Clark S. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 562\u2013571."},{"key":"S1351324915000340_ref059","unstructured":"Joachims T. 2003. Transductive learning via spectral graph partitioning. In Proceedings of the 18th International Conference on Machine Learning, Williams College, Williamstown, MAWashington, D.C., USA, August 21\u201324 2003, pp. 290\u2013297."},{"key":"S1351324915000340_ref058","doi-asserted-by":"crossref","unstructured":"Jia Z. , and Zhao H. 2014. A joint graph model for pinyin-to-chinese conversion with typo correction. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, Baltimore, Maryland, USA, 22\u201327 June, 2014, pp. 1512\u20131523.","DOI":"10.3115\/v1\/P14-1142"},{"key":"S1351324915000340_ref055","unstructured":"Huang L. , and Chiang D. 2007. Forest rescoring: faster decoding with integrated language models. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, Prague, Czech Republic, 23\u201330 June 2007, pp. 144\u2013151."},{"key":"S1351324915000340_ref054","doi-asserted-by":"crossref","unstructured":"Huang L. , and Chiang D. 2005. Better k-best parsing. In Proceedings of IWPT 2005.","DOI":"10.3115\/1654494.1654500"},{"key":"S1351324915000340_ref052","unstructured":"Hirakawa H. 2001. Semantic dependency analysis method for Japanese based on optimum tree search algorithm. In Proceedings of the 5th Meeting of the Pacific Association for Computational Linguistics, Kitakyushu, Japan, 11\u201314 September 2001."},{"key":"S1351324915000340_ref051","doi-asserted-by":"crossref","unstructured":"Hearst M. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of the 15th International Conference on Computational Linguistics, Nantes, France, 23\u201328 August 1992, pp. 539\u2013545.","DOI":"10.3115\/992133.992154"},{"key":"S1351324915000340_ref056","unstructured":"Hughes T. , and Ramage D. 2007. Lexical semantic relatedness with random graph walks. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Language Learning, Prague, Czech Republic, 28\u201330 June 2007, pp. 581\u2013589."},{"key":"S1351324915000340_ref050","unstructured":"Hatzivassiloglou V. , and McKeown K. R. 1997. Predicting the semantic orientation of adjectives. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and of the 8th Conference of the European Chapter of the Association for Computational Linguistics, Madrid, Spain, 7\u201312 July 1997, pp. 174\u2013181."},{"key":"S1351324915000340_ref049","unstructured":"Hassan H. , and Menezes A. 2013. Social text normalization using contextual graph random walks. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, Sofia, Bulgaria, 4\u20139 August 2013, pp. 1577\u20131586."},{"key":"S1351324915000340_ref099","unstructured":"Alexandre T. , Pardo S. , Antiqueira L. , das Gra\u00e7as Volpe Nunes M. , Oliveira O. N. Jr. , and da Fontoura Costa L. 2006. Modeling and evaluating summaries using complex networks. In Proceedings of Computational Processing of the Portuguese Language, the Seventh International Workshop (PROPOR-2006), Springer, pp. 1\u201310."},{"key":"S1351324915000340_ref047","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00192"},{"key":"S1351324915000340_ref045","unstructured":"Guinaudeau C. , and Strube M. 2013. Graph-based local coherence modeling. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, Sofia, Bulgaria, 4\u20139 August 2013, pp. 93\u2013103."},{"key":"S1351324915000340_ref042","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00207"},{"key":"S1351324915000340_ref040","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90045-P"},{"key":"S1351324915000340_ref039","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1613\/jair.3456","article-title":"The cqc algorithm: cycling in graphs to semantically enrich and enhance a bilingual dictionary","volume":"43","author":"Flati","year":"2012","journal-title":"Journal of Artificial Intelligence Research"},{"key":"S1351324915000340_ref075","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.026102"},{"key":"S1351324915000340_ref037","first-page":"65","volume-title":"TextGraphs-2: Graph-Based Algorithms for Natural Language Processing","author":"Ferrer i Cancho","year":"2007"},{"key":"S1351324915000340_ref035","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/7287.001.0001","volume-title":"WordNet: An Electronic Lexical Database","author":"Fellbaum","year":"1998"},{"key":"S1351324915000340_ref032","doi-asserted-by":"crossref","unstructured":"Erkan G. , and Radev D. 2004. The university of Michigan at DUC 2004. In Document Understanding Conference (DUC), Boston, Massachusetts, May.","DOI":"10.6028\/NIST.SP.500-261.novelty-u.michigan"},{"key":"S1351324915000340_ref030","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00003"},{"key":"S1351324915000340_ref029","doi-asserted-by":"crossref","unstructured":"Eisner J. M. 1996. Three new probabilistic models for dependency parsing: an exploration. In Proceedings of the 16th International Conference on Computational Linguistics, Copenhagen, Denmark, 5\u20139 August 1996, pp. 340\u2013345.","DOI":"10.3115\/992628.992688"},{"key":"S1351324915000340_ref027","doi-asserted-by":"crossref","unstructured":"Doyle P. G. , and Snell J. L. 1984. Random walks and electric networks. Technical Report math.PR\/0001057, Arxiv.org.","DOI":"10.5948\/UPO9781614440222"},{"key":"S1351324915000340_ref090","unstructured":"Navigli R. , and Lapata M. 2007. Graph connectivity measures for unsupervised word sense disambiguation. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 6\u201312 January 2007, pp. 1683\u20131688, Hyderabad, India."},{"key":"S1351324915000340_ref026","doi-asserted-by":"crossref","unstructured":"Dorow B. , Laws F. , Michelbacher L. , Scheible C. , and Utt J. 2009. A graph-theoretic algorithm for automatic extension of translation lexicons. In Proceedings of the Workshop on Geometrical Models of Natural Language Semantics, pp. 91\u201395.","DOI":"10.3115\/1705415.1705427"},{"key":"S1351324915000340_ref025","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.2001.1824"},{"key":"S1351324915000340_ref022","doi-asserted-by":"crossref","unstructured":"Coursey K. , and Mihalcea R. 2009. Topic identification using wikipedia graph centrality. In Proceedings of the Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics and the 4th International Joint Conference on Natural Language Processing, Singapore, 2\u20137 August 2009, pp. 117\u2013120.","DOI":"10.3115\/1620853.1620887"},{"key":"S1351324915000340_ref021","unstructured":"Cmejrek M. , Mi H. , and Zhou B. 2013. Flexible and efficient hypergraph interactions for joint hierarchical and forest-to-string decoding. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, Seattle, USA, 18\u201321 October 2013, pp. 545\u2013555."},{"key":"S1351324915000340_ref020","first-page":"1396","article-title":"On the shortest arborescence of a directed graph","volume":"14","author":"Chu","year":"1965","journal-title":"Science Sinica"},{"key":"S1351324915000340_ref019","unstructured":"Chen C. , and Ji H. 2010. Graph-based clustering for computational linguistics: a survey. In Proceedings of the 2010 Workshop on Graph-based Methods for Natural Language Processing, TextGraphs-5, pp. 1\u20139."},{"key":"S1351324915000340_ref017","doi-asserted-by":"crossref","unstructured":"Carbonell J. G. , and Goldstein J. 1998. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 335\u2013336.","DOI":"10.1145\/290941.291025"},{"key":"S1351324915000340_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"S1351324915000340_ref007","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rne J. , Heimonen J. , Ginter F. , Airola A. , Pahikkala T. , and Salakoski T. 2009. Extracting complex biological events with rich graph-based feature sets. In Proceedings of the BioNLP 2009 Workshop, Companion Volume for Shared Task, pp. 10\u201318.","DOI":"10.3115\/1572340.1572343"},{"key":"S1351324915000340_ref005","unstructured":"Biemann C. 2006. Chinese whispers - an efficient graph clustering algorithm and its application to natural language processing problems. In Proceedings of TextGraphs: the Second Workshop on Graph Based Methods for Natural Language Processing, New York City, NY, USA, June 2006, pp. 73\u201380."},{"key":"S1351324915000340_ref133","doi-asserted-by":"crossref","unstructured":"Zhu L. , Gao S. , Pan J. , Li H. , Deng D. , and Shahabi C. , 2013. Graph-based informative-sentence selection for opinion summarization. In Proceedings of the International Conference on Advances in Social Network Analysis and Mining (ASONAM-2013), Niagara, Ontario, Canada, August 25\u201329, 2013, pp. 408\u2013412.","DOI":"10.1145\/2492517.2492651"},{"key":"S1351324915000340_ref125","doi-asserted-by":"publisher","DOI":"10.1162\/0891201054223977"},{"key":"S1351324915000340_ref102","unstructured":"Radev D. R. 2004. Weakly supervised graph-based methods for classification. Technical Report CSE-TR-500-04, University of Michigan. Department of Electrical Engineering and Computer Science."},{"key":"S1351324915000340_ref122","unstructured":"Watanabe Y. , Asahara M. , and Matsumoto Y. 2007. A graph-based approach to named entity categorization in Wikipedia using conditional random fields. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Language Learning, Prague, Czech Republic, 28\u201330 June 2007, pp. 649\u2013657."},{"key":"S1351324915000340_ref016","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2006-00091-3"},{"key":"S1351324915000340_ref128","doi-asserted-by":"crossref","unstructured":"Zens R. , and Ney H. , 2005. Word graphs for statistical machine translation. In Proceedings of the ACL Workshop on Building and Using Parallel Texts, Ann Arbor, Michigan, June. Association for Computational Linguistics, pp. 191\u2013198.","DOI":"10.3115\/1654449.1654491"},{"key":"S1351324915000340_ref053","unstructured":"Huang L. 2008. Forest reranking: discriminative parsing with non-local features. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Columbus, Ohio, 15\u201320 June 2008, pp. 586\u2013594."},{"key":"S1351324915000340_ref096","doi-asserted-by":"crossref","unstructured":"Otterbacher J. , Erkan G. , and Radev D. 2005. Using random walks for question-focused sentence retrieval. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Canada, 6\u20138 October 2005, pp. 915\u2013922.","DOI":"10.3115\/1220575.1220690"},{"key":"S1351324915000340_ref087","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.065102"},{"key":"S1351324915000340_ref068","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00195"},{"key":"S1351324915000340_ref091","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.36"},{"key":"S1351324915000340_ref118","unstructured":"Tsatsaronis G. , Varlamis I. , and N\u00f8rv\u00e5g K. 2010. Semanticrank: ranking keywords and sentences using semantic graphs. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 1074\u20131082."},{"key":"S1351324915000340_ref115","doi-asserted-by":"crossref","unstructured":"Talukdar P. P. , Reisinger J. , Pasca M. , Ravichandran D. , Bhagat R. , and Pereira F. 2008. Weakly-supervised acquisition of labeled class instances using graph random walks. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 582\u2013590.","DOI":"10.3115\/1613715.1613787"},{"key":"S1351324915000340_ref001","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00164"},{"key":"S1351324915000340_ref070","unstructured":"Laws F. , Michelbacher L. , Dorow B. , Scheible C. , Heid U. , and Sch\u00fctze H. 2010. A linguistically grounded graph model for bilingual lexicon extraction. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 614\u2013622."},{"key":"S1351324915000340_ref023","first-page":"1","article-title":"Signatures of small-world and scale-free properties in large computer programs","volume":"68","author":"de Moura","year":"2003","journal-title":"American Physical Society"},{"key":"S1351324915000340_ref089","doi-asserted-by":"crossref","unstructured":"Nastase V. 2008. Topic-driven multi-document summarization with encyclopedic knowledge and spreading activation. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 763\u2013772.","DOI":"10.3115\/1613715.1613812"},{"key":"S1351324915000340_ref024","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00148"},{"key":"S1351324915000340_ref009","unstructured":"Blum A. , and Chawla S. 2001. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the 18th International Conference on Machine Learning, Williams College, Williamstown, MA, USA, June 28\u2013July 1 2001, pp. 19\u201326."},{"key":"S1351324915000340_ref114","unstructured":"Talukdar P. P. , and Pereira F. 2010. Experiments in graph-based semi-supervised learning methods for class-instance acquisition. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Uppsala, Sweden, 11\u201316 July 2010, pp. 1473\u20131481."},{"key":"S1351324915000340_ref031","doi-asserted-by":"crossref","unstructured":"Erkan G. 2006. Language model-based document clustering using random walks. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, New York, N.Y., 4\u20139 June 2006, pp. 479\u2013486.","DOI":"10.3115\/1220835.1220896"},{"key":"S1351324915000340_ref004","unstructured":"Berant J. , Dagan I. , and Goldberger J. 2010. Global learning of focused entailment graphs. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Uppsala, Sweden, 11\u201316 July 2010, pp. 1220\u20131229."},{"key":"S1351324915000340_ref057","doi-asserted-by":"crossref","unstructured":"Jeh G. , and Widom J. 2002. SimRank: a measure of structural-context similarity. In Proceedings of the 10th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, 23\u201326 July 2002, pp. 538\u2013543.","DOI":"10.1145\/775047.775126"},{"key":"S1351324915000340_ref034","unstructured":"Fahrni A. , Nastase V. , and Strube M. 2011. Hits graph-based system at the ntcir-9 cross-lingual link discovery task. In Proceedings of the 9th NTCIR (NII Test Collection for IR Systems) Workshop Meeting, Tokyo, Japan, 6\u20139 December 2011, pp. 473\u2013480."},{"key":"S1351324915000340_ref002","doi-asserted-by":"crossref","unstructured":"Alexandrescu A. , and Kirchhoff K. 2009. Graph-based learning for statistical machine translation. In Proceedings of Human Language Technologies 2009: The Conference of the North American Chapter of the Association for Computational Linguistics, Boulder, Col., 31 May\u20135 June 2009, pp. 119\u2013127.","DOI":"10.3115\/1620754.1620772"},{"key":"S1351324915000340_ref028","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"S1351324915000340_ref108","unstructured":"Scheible C. , Laws F. , Michelbacher L. , and Sch\u00fctze H. 2010. Sentiment translation through multi-edge graphs. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 1104\u20131112."},{"key":"S1351324915000340_ref120","unstructured":"Velikovich L. , Blair-Goldensohn S. , Hannan K. , and McDonald R. 2010. The viability of web-derived polarity lexicons. In Proceedings of Human Language Technologies 2010: The Conference of the North American Chapter of the Association for Computational Linguistics, Los Angeles, Cal., 2\u20134 June 2010, pp. 777\u2013785."},{"key":"S1351324915000340_ref041","unstructured":"Ganesan K. , Zhai C. X. , and Han J. 2010. Opinosis: a graph based approach to abstractive summarization of highly redundant opinions. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 340\u2013348."},{"key":"S1351324915000340_ref124","doi-asserted-by":"crossref","unstructured":"Wiebe J. , and Mihalcea R. 2006. Word sense and subjectivity. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Sydney, Australia, 17\u201321 July 2006, pp. 1065\u20131072.","DOI":"10.3115\/1220175.1220309"},{"key":"S1351324915000340_ref098","unstructured":"Papineni K. , Roukos S. , Ward T. , and Zhu W.-J. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, Philadelphia, Penn., 7\u201312 July 2002, pp. 311\u2013318."},{"key":"S1351324915000340_ref074","unstructured":"Mani I. , and Bloedorn E. 1997. Multi-document summarization by graph searching and matching. In Proceedings of the 14th National Conference on Artificial Intelligence, Providence, R.I., 27\u201331 July 1997, pp. 622\u2013628."},{"key":"S1351324915000340_ref111","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog2901_3"},{"key":"S1351324915000340_ref048","doi-asserted-by":"crossref","unstructured":"Hassan H. , Hassan A. , and Emam O. 2006. Unsupervised information extraction approach using graph mutual reinforcement. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, Sydney, Australia, 22\u201323 July 2006, pp. 501\u2013508.","DOI":"10.3115\/1610075.1610144"},{"key":"S1351324915000340_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25923-4"},{"key":"S1351324915000340_ref126","unstructured":"Xu G. , Meng X. , and Wang H. 2010. Build chinese emotion lexicons using a graph-based algorithm and multiple resources. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 1209\u20131217."},{"key":"S1351324915000340_ref064","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"S1351324915000340_ref038","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.2001.1800"},{"key":"S1351324915000340_ref015","unstructured":"Cai J. , and Strube M. 2010. End-to-end coreference resolution via hypergraph partitioning. In Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, China, 23\u201327 August 2010, pp. 143\u2013151."},{"key":"S1351324915000340_ref062","unstructured":"Klapaftis I. , and Manandhar S. 2008. Word sense induction using graphs of collocations. In Proceedings of the 18th European Conference on Artificial Intelligence, Patras, Greece, 21\u201325 July 2008, pp. 298\u2013302."},{"key":"S1351324915000340_ref046","doi-asserted-by":"crossref","unstructured":"Haghighi A. , Ng A. , and Manning C. 2005. Robust textual inference via graph matching. In Proceedings of the Human Language Technology Conference and the 2005 Conference on Empirical Methods in Natural Language Processing, Vancouver, B.C., Canada, 6\u20138 October 2005, pp. 387\u2013394.","DOI":"10.3115\/1220575.1220624"},{"key":"S1351324915000340_ref065","doi-asserted-by":"crossref","unstructured":"Komachi M. , Kudo T. , Shimbo M. , and Matsumoto Y. 2008. Graph-based analysis of semantic drift in Espresso-like bootstrapping algorithms. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, Waikiki, Honolulu, Hawaii, 25\u201327 October 2008, pp. 1011\u20131020.","DOI":"10.3115\/1613715.1613847"},{"key":"S1351324915000340_ref033","unstructured":"Esuli A. , and Sebastiani F. 2007. PageRanking WordNet synsets: an application to opinion mining. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, Prague, Czech Republic, 23\u201330 June 2007, pp. 424\u2013431."},{"key":"S1351324915000340_ref088","doi-asserted-by":"crossref","unstructured":"Muthukrishnan P. , Gerrish J. , and Radev D. R. 2008. Detecting multiple facets of an event using graph-based unsupervised methods. In Proceedings of the 22nd International Conference on Computational Linguistics, Manchester, UK, 18\u201322 August 2008, pp. 609\u2013616.","DOI":"10.3115\/1599081.1599158"},{"key":"S1351324915000340_ref110","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.022341799"},{"key":"S1351324915000340_ref008","unstructured":"Blair-Goldensohn S. , Neylon T. , Hannan K. , Reis G. A. , McDonald R. , and Reynar J. 2008. Building a sentiment summarizer for local service reviews. In WWW Workshop on NLP in the Information Explosion Era (NLPIX)."},{"key":"S1351324915000340_ref082","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976247"},{"key":"S1351324915000340_ref129","doi-asserted-by":"crossref","unstructured":"Zha H. 2002. Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering. In SIGIR2002, pp. 113\u2013120.","DOI":"10.1145\/564376.564398"},{"key":"S1351324915000340_ref003","doi-asserted-by":"crossref","unstructured":"Barzilay R. , and Lee L. 2003. Learning to paraphrase: an unsupervised approach using multiple-sequence alignment. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, Edmonton, Alberta, Canada, 27 May \u20131 June 2003.","DOI":"10.3115\/1073445.1073448"},{"key":"S1351324915000340_ref013","doi-asserted-by":"crossref","unstructured":"Bramsen P. , Deshpande P. , Lee Y. K. , and Barzilay R. 2006. Inducing temporal graphs. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing, Sydney, Australia, 22\u201323 July 2006, pp. 189\u2013198.","DOI":"10.3115\/1610075.1610105"},{"key":"S1351324915000340_ref094","doi-asserted-by":"crossref","unstructured":"Niu Z.-Y. , Ji D.-H. , and Tan C. L. 2005. Word sense disambiguation using label propagation based semi-supervised learning. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics, Ann Arbor, Mich., 25\u201330 June 2005, pp. 395\u2013402.","DOI":"10.3115\/1219840.1219889"},{"key":"S1351324915000340_ref011","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"1985"},{"key":"S1351324915000340_ref131","unstructured":"Zhou D. , Huang J. , and Sch\u00f6lkopf B. 2006. Learning with hypergraphs: clustering, classification, and embedding. In Advances in Neural Information Processing Systems, pp. 1601\u20131608."},{"key":"S1351324915000340_ref078","first-page":"328","volume-title":"Corpus Linguistics. An International Handbook of the Science of Language and Society","author":"Mehler","year":"2007"},{"key":"S1351324915000340_ref044","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03981-6"},{"key":"S1351324915000340_ref043","doi-asserted-by":"crossref","unstructured":"Goldberg A. B. , and Zhu J. 2006. Seeing stars when there aren\u2019t many stars: graph-based semi-supervised learning for sentiment categorization. In HLT-NAACL 2006 Workshop on Textgraphs: Graph-based Algorithms for Natural Language Processing, pp. 45\u201352.","DOI":"10.3115\/1654758.1654769"},{"key":"S1351324915000340_ref095","unstructured":"Nivre J. , and McDonald R. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Columbus, Ohio, 15\u201320 June 2008, pp. 950\u2013958."},{"key":"S1351324915000340_ref072","unstructured":"Liu S. , Li C.-H. , Li M. , and Zhou M. 2012. Learning translation consensus with structured label propagation. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics, Jeju Island, Korea, 8\u201314 July 2012, pp. 302\u2013310."},{"key":"S1351324915000340_ref036","first-page":"60","volume-title":"Problems of Quantitative Linguistics","author":"Ferrer i Cancho","year":"2005"},{"key":"S1351324915000340_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S1351324915000340_ref071","first-page":"147","article-title":"Using corpus statistics and WordNet relations for sense identification","volume":"24","author":"Leacock","year":"1998","journal-title":"Computational Linguistics"},{"key":"S1351324915000340_ref010","unstructured":"Bollegala D. , Matsuo Y. , and Ishizuka M. 2008. A co-occurrence graph-based approach for personal name alias extraction from anchor texts. In Proceedings of the 3rd International Joint Conference on Natural Language Processing, Hyderabad, India, 7\u201312 January 2008, pp. 865\u2013870."},{"key":"S1351324915000340_ref092","doi-asserted-by":"crossref","unstructured":"Ng V. 2009. Graph-cut-based anaphoricity determination for coreference resolution. In Proceedings of Human Language Technologies 2009: The Conference of the North American Chapter of the Association for Computational Linguistics, Boulder, Col., 31 May\u20135 June 2009, pp. 575\u2013583.","DOI":"10.3115\/1620754.1620838"},{"key":"S1351324915000340_ref018","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262033589.001.0001"},{"key":"S1351324915000340_ref066","unstructured":"Konstas I. and Lapata M. 2012. Unsupervised concept-to-text generation with hypergraphs. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Montr\u00e9al, Quebec, Canada, 3\u20138 June 2012, pp. 752\u2013761."}],"container-title":["Natural Language Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1351324915000340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T18:38:38Z","timestamp":1718131118000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1351324915000340\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,12]]},"references-count":136,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S1351324915000340"],"URL":"https:\/\/doi.org\/10.1017\/s1351324915000340","relation":{},"ISSN":["1351-3249","1469-8110"],"issn-type":[{"value":"1351-3249","type":"print"},{"value":"1469-8110","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,12]]}}}