---
title: "Graph-Cut-Based Anaphoricity Determination for — Ng 2009"
description: "This paper tackles anaphoricity determination: deciding which mentions have an antecedent, so that a coreference resolver can skip the non-anaphoric ones."
authors: ["Vincent Ng"]
year: 2009
venue: "Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics"
source: "https://aclanthology.org/N09-1065/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/ng-2009-graph-cut-based-anaphoricity-determination/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/ng-2009-graph-cut-based-anaphoricity-determination/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2009](https://md.research.elamur.ai/free/papers/2009/) / Graph-Cut-Based Anaphoricity Determination for Coreference Resolution

# Graph-Cut-Based Anaphoricity Determination for Coreference Resolution

**Authors:** [Vincent Ng](https://md.research.elamur.ai/free/authors/vincent-ng/) · **Year:** 2009 · **Venue:** Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/N09-1065/) · [PDF](https://aclanthology.org/N09-1065.pdf) · [OpenAlex](https://openalex.org/W1965206833)

**Citations:** 34 citations (openalex-snapshot · 2026-10-14) · [17](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
This paper tackles anaphoricity determination: deciding which mentions have an antecedent, so that a coreference resolver can skip the non-anaphoric ones. Earlier work fell into two camps. Ng (2004) tuned a classifier threshold to maximize the coreference metric directly but ignored pairwise coreference probabilities. ILP-based joint inference used those probabilities but optimized an objective unrelated to the evaluation metric. Ng proposes a minimum-cut formulation that combines both strengths. It builds a graph from the outputs of a MaxEnt anaphoricity model and a MaxEnt pairwise coreference model. Two parameters are tuned on held-out data against the target metric. The method is compared with five existing approaches on three ACE data sets, scored with both MUC and CEAF. Unlike several prior studies, mentions come from an NP chunker rather than gold answer keys. The graph-cut system achieves the best F-score in all six data-set/scorer combinations, and none of the earlier methods wins consistently. This makes the paper a useful systematic benchmark of anaphoricity filtering under realistic, automatically extracted mentions.

## Key points
- **Baselines compared:** the five approaches are Ng and Cardie (2002a), Ng (2004), Luo (2007), Denis and Baldridge (2007, ILP), and Finkel and Manning (2008, ILP with transitivity constraints).
- **Models:** the coreference model is MaxEnt with 33 features (Ng 2007), trained on Soon et al. (2001) instances with closest-first clustering. The anaphoricity model is MaxEnt with 37 features (Ng and Cardie 2002a).
- **Data and evaluation:** the ACE data sets are Broadcast News, Newspaper and Newswire. One third of the training data was held out to tune the parameters c and c2, searched in steps of 0.1. Significance was tested with Approximate Randomization at p=0.05.
- **Main results:** the graph-cut system reaches MUC F of 59.4–63.9 and CEAF F of 59.4–63.8. Over the no-anaphoricity baseline this is a significant gain in all six cases: +2.0–4.4 MUC and +2.6–4.1 CEAF. The improvement comes mainly from higher precision, with a smaller loss in recall.
- **Comparison with baselines:** the graph-cut system significantly beats the strongest baseline (Denis and Baldridge) except on Newspaper/MUC and Newswire/MUC. Adding transitivity constraints (Finkel and Manning) never improved F-score over Denis and Baldridge.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

Topics: [Coreference resolution](https://md.research.elamur.ai/free/topics/coreference-resolution/)

## Cited by

Cited by

17 papers of our library cite it (of the 140673 whose bibliographies we read); 10 of them have a page here, 7 not yet.

- [Combining the Best of Two Worlds: A Hybrid Approach to Multilingual Coreference Resolution](https://md.research.elamur.ai/free/papers/chen-2012-combining-best-two-worlds-hybrid/)
- [Latent Trees for Coreference Resolution](https://md.research.elamur.ai/free/papers/fernandes-2014-latent-trees-coreference-resolution/)
- [Dependency-driven Anaphoricity Determination for Coreference Resolution](https://md.research.elamur.ai/free/papers/kong-2010-dependency-driven-anaphoricity-determination-coreference/)
- [Deterministic Coreference Resolution Based on Entity-Centric, Precision-Ranked Rules](https://md.research.elamur.ai/free/papers/lee-2013-deterministic-coreference-resolution-based-entity/)
- [Collective Classification for Fine-grained Information Status](https://md.research.elamur.ai/free/papers/markert-2012-collective-classification-fine-grained-information/)
- [Search Space Pruning: A Simple Solution for Better Coreference Resolvers](https://md.research.elamur.ai/free/papers/moosavi-2016-search-space-pruning-simple-solution/)
- [Supervised Noun Phrase Coreference Research: The First Fifteen Years](https://md.research.elamur.ai/free/papers/ng-2010-supervised-noun-phrase-coreference-research/)
- [Coreference Resolution across Corpora: Languages, Coding Schemes, and Preprocessing Information](https://md.research.elamur.ai/free/papers/recasens-2010-coreference-resolution-across-corpora-languages/)
- [A Typology of Near-Identity Relations for Coreference (NIDENT)](https://md.research.elamur.ai/free/papers/recasens-2010-typology-near-identity-relations-coreference/)
- [A Constraint-Based Hypergraph Partitioning Approach to Coreference Resolution](https://md.research.elamur.ai/free/papers/sapena-2013-constraint-based-hypergraph-partitioning-approach/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{ng2009graph,
  title = {{Graph-Cut-Based Anaphoricity Determination for Coreference Resolution}},
  author = {Ng, Vincent},
  booktitle = {Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  doi = {10.3115/1620754.1620838},
  url = {https://doi.org/10.3115/1620754.1620838}
}
```

- [← previous Graph-based Event Coreference Resolution](https://md.research.elamur.ai/free/papers/chen-2009-graph-based-event-coreference-resolution/)
- [next → Hebrew Dependency Parsing: Initial Results](https://md.research.elamur.ai/free/papers/lingbulk-2009-goldberg-hebrew-dependency-parsing-initial-results/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/papers/2009/)

## References

30 references, 15 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. D. Bean and E. Riloff. 1999. Corpus-based identification of non-anaphoric noun phrases. In Proc. of the ACL, pages 373–380. [find](https://scholar.google.com/scholar?q=D%2E+Bean+and+E%2E+Riloff%2E+1999%2E+Corpus%2Dbased+identification+of+non%2Danaphoric+noun+phrases%2E+In+Proc%2E+of+the+ACL%2C+pages+373%E2%80%93380%2E) [our card](https://md.research.elamur.ai/free/papers/bean-1999-corpus-based-identification-non-anaphoric/)
2. A. Berger, S. Della Pietra, and V. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71. [find](https://scholar.google.com/scholar?q=A%2E+Berger%2C+S%2E+Della+Pietra%2C+and+V%2E+Della+Pietra%2E+1996%2E+A+maximum+entropy+approach+to+natural+language+processing%2E+Computational+Linguistics%2C+22%281%29%3A39%E2%80%9371%2E) [our card](https://md.research.elamur.ai/free/papers/berger-1996-maximum-entropy-approach-natural-language/)
3. S. Bergsma, D. Lin, and R. Goebel. 2008. Distributional identification of non-referential pronouns. In Proc. of ACL-08:HLT, pages 10–18. [find](https://scholar.google.com/scholar?q=S%2E+Bergsma%2C+D%2E+Lin%2C+and+R%2E+Goebel%2E+2008%2E+Distributional+identification+of+non%2Dreferential+pronouns%2E+In+Proc%2E+of+ACL%2D08%3AHLT%2C+pages+10%E2%80%9318%2E)
4. S. Della Pietra, V. Della Pietra, and J. Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393. [find](https://scholar.google.com/scholar?q=S%2E+Della+Pietra%2C+V%2E+Della+Pietra%2C+and+J%2E+Lafferty%2E+1997%2E+Inducing+features+of+random+fields%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+19%284%29%3A380%E2%80%93393%2E)
5. P. Denis and J. Baldridge. 2007. Global, joint determination of anaphoricity and coreference resolution using integer programming. In Proc. of NAACL/HLT, pages 236–243. [find](https://scholar.google.com/scholar?q=P%2E+Denis+and+J%2E+Baldridge%2E+2007%2E+Global%2C+joint+determination+of+anaphoricity+and+coreference+resolution+using+integer+programming%2E+In+Proc%2E+of+NAACL%2FHLT%2C+pages+236%E2%80%93243%2E) [our card](https://md.research.elamur.ai/free/papers/denis-2007-joint-determination-anaphoricity-coreference-resolution/)
6. M. Elsner and E. Charniak. 2007. A generative discourse-new model for text coherence. Technical Report CS-07-04, Brown University. [find](https://scholar.google.com/scholar?q=M%2E+Elsner+and+E%2E+Charniak%2E+2007%2E+A+generative+discourse%2Dnew+model+for+text+coherence%2E+Technical+Report+CS%2D07%2D04%2C+Brown+University%2E)
7. R. Evans. 2001. Applying machine learning toward an automatic classification of it. Literary and Linguistic Computing, 16(1):45–57. [find](https://scholar.google.com/scholar?q=R%2E+Evans%2E+2001%2E+Applying+machine+learning+toward+an+automatic+classification+of+it%2E+Literary+and+Linguistic+Computing%2C+16%281%29%3A45%E2%80%9357%2E)
8. J. R. Finkel and C. Manning. 2008. Enforcing transitivity in coreference resolution. In Proc. of ACL-08:HLT Short Papers (Companion Volume), pages 45–48. [find](https://scholar.google.com/scholar?q=J%2E+R%2E+Finkel+and+C%2E+Manning%2E+2008%2E+Enforcing+transitivity+in+coreference+resolution%2E+In+Proc%2E+of+ACL%2D08%3AHLT+Short+Papers+%28Companion+Volume%29%2C+pages+45%E2%80%9348%2E) [our card](https://md.research.elamur.ai/free/papers/finkel-2008-enforcing-transitivity-coreference-resolution/)
9. C. Kennedy and B. Boguraev. 1996. Anaphor for everyone: Pronominal anaphora resolution without a parser. In Proc. of COLING, pages 113–118. [find](https://scholar.google.com/scholar?q=C%2E+Kennedy+and+B%2E+Boguraev%2E+1996%2E+Anaphor+for+everyone%3A+Pronominal+anaphora+resolution+without+a+parser%2E+In+Proc%2E+of+COLING%2C+pages+113%E2%80%93118%2E)
10. S. Lappin and H. Leass. 1994. An algorithm for pronominal anaphora resolution. Computational Linguistics, 20(4):535–562. [find](https://scholar.google.com/scholar?q=S%2E+Lappin+and+H%2E+Leass%2E+1994%2E+An+algorithm+for+pronominal+anaphora+resolution%2E+Computational+Linguistics%2C+20%284%29%3A535%E2%80%93562%2E) [our card](https://md.research.elamur.ai/free/papers/lappin-1994-algorithm-pronominal-anaphora-resolution/)
11. X. Luo, A. Ittycheriah, H. Jing, N. Kambhatla, and S. Roukos. 2004. A mention-synchronous coreference resolution algorithm based on the Bell tree. In Proc. of the ACL, pages 135–142. [find](https://scholar.google.com/scholar?q=X%2E+Luo%2C+A%2E+Ittycheriah%2C+H%2E+Jing%2C+N%2E+Kambhatla%2C+and+S%2E+Roukos%2E+2004%2E+A+mention%2Dsynchronous+coreference+resolution+algorithm+based+on+the+Bell+tree%2E+In+Proc%2E+of+the+ACL%2C+pages+135%E2%80%93142%2E) [our card](https://md.research.elamur.ai/free/papers/luo-2004-mention-synchronous-coreference-resolution-algorithm/)
12. X. Luo. 2005. On coreference resolution performance metrics. In Proc. of HLT/EMNLP, pages 25–32. [find](https://scholar.google.com/scholar?q=X%2E+Luo%2E+2005%2E+On+coreference+resolution+performance+metrics%2E+In+Proc%2E+of+HLT%2FEMNLP%2C+pages+25%E2%80%9332%2E) [our card](https://md.research.elamur.ai/free/papers/luo-2005-coreference-resolution-performance-metrics/)
13. X. Luo. 2007. Coreference or not: A twin model for coreference resolution. In Proc. of NAACL-HLT, pages 73–80. [find](https://scholar.google.com/scholar?q=X%2E+Luo%2E+2007%2E+Coreference+or+not%3A+A+twin+model+for+coreference+resolution%2E+In+Proc%2E+of+NAACL%2DHLT%2C+pages+73%E2%80%9380%2E) [our card](https://md.research.elamur.ai/free/papers/luo-2007-coreference-or-not-twin-model/)
14. C. Müller. 2006. Automatic detection of nonreferential it in spoken multi-party dialog. In Proc. of EACL, pages 49–56. [find](https://scholar.google.com/scholar?q=C%2E+Mu%CC%88ller%2E+2006%2E+Automatic+detection+of+nonreferential+it+in+spoken+multi%2Dparty+dialog%2E+In+Proc%2E+of+EACL%2C+pages+49%E2%80%9356%2E)
15. V. Ng. 2007. Shallow semantics for coreference resolution. In Proceedings of IJCAI, pages 1689–1694. [find](https://scholar.google.com/scholar?q=V%2E+Ng%2E+2007%2E+Shallow+semantics+for+coreference+resolution%2E+In+Proceedings+of+IJCAI%2C+pages+1689%E2%80%931694%2E)
16. V. Ng and C. Cardie. 2002a. Identifying anaphoric and non-anaphoric noun phrases to improve coreference resolution. In Proc. of COLING, pages 730–736. [find](https://scholar.google.com/scholar?q=V%2E+Ng+and+C%2E+Cardie%2E+2002a%2E+Identifying+anaphoric+and+non%2Danaphoric+noun+phrases+to+improve+coreference+resolution%2E+In+Proc%2E+of+COLING%2C+pages+730%E2%80%93736%2E)
17. V. Ng and C. Cardie. 2002b. Improving machine learning approaches to coreference resolution. In Proc. of the ACL, pages 104–111. [find](https://scholar.google.com/scholar?q=V%2E+Ng+and+C%2E+Cardie%2E+2002b%2E+Improving+machine+learning+approaches+to+coreference+resolution%2E+In+Proc%2E+of+the+ACL%2C+pages+104%E2%80%93111%2E) [our card](https://md.research.elamur.ai/free/papers/ng-2002-improving-machine-learning-approaches-coreference/)
18. V. Ng. 2004. Learning noun phrase anaphoricity to improve conference resolution: Issues in representation and optimization. In Proc. of the ACL, pages 151–158. [find](https://scholar.google.com/scholar?q=V%2E+Ng%2E+2004%2E+Learning+noun+phrase+anaphoricity+to+improve+conference+resolution%3A+Issues+in+representation+and+optimization%2E+In+Proc%2E+of+the+ACL%2C+pages+151%E2%80%93158%2E) [our card](https://md.research.elamur.ai/free/papers/ng-2004-learning-noun-phrase-anaphoricity-improve/)
19. E. W. Noreen. 1989. Computer Intensive Methods for Testing Hypothesis: An Introduction. John Wiley & Sons. [find](https://scholar.google.com/scholar?q=E%2E+W%2E+Noreen%2E+1989%2E+Computer+Intensive+Methods+for+Testing+Hypothesis%3A+An+Introduction%2E+John+Wiley+%26+Sons%2E)
20. C. Paice and G. Husk. 1987. Towards the automatic recognition of anaphoric features in English text: the impersonal pronoun ’it’. Computer Speech and Language, 2. [find](https://scholar.google.com/scholar?q=C%2E+Paice+and+G%2E+Husk%2E+1987%2E+Towards+the+automatic+recognition+of+anaphoric+features+in+English+text%3A+the+impersonal+pronoun+%E2%80%99it%E2%80%99%2E+Computer+Speech+and+Language%2C+2%2E)
21. B. Pang and L. Lee. 2004. A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts. In Proc. of the ACL, pages 271–278. [find](https://scholar.google.com/scholar?q=B%2E+Pang+and+L%2E+Lee%2E+2004%2E+A+sentimental+education%3A+Sentiment+analysis+using+subjectivity+summarization+based+on+minimum+cuts%2E+In+Proc%2E+of+the+ACL%2C+pages+271%E2%80%93278%2E)
22. M. Poesio, O. Uryupina, R. Vieira, M. Alexandrov-Kabadjov, and R. Goulart. 2004. Discourse-new detectors for definite description resolution: A survey and a preliminary proposal. In Proc. of the ACL Workshop on Reference Resolution. [find](https://scholar.google.com/scholar?q=M%2E+Poesio%2C+O%2E+Uryupina%2C+R%2E+Vieira%2C+M%2E+Alexandrov%2DKabadjov%2C+and+R%2E+Goulart%2E+2004%2E+Discourse%2Dnew+detectors+for+definite+description+resolution%3A+A+survey+and+a+preliminary+proposal%2E+In+Proc%2E+of+the+ACL+W)
23. S. P. Ponzetto and M. Strube. 2006. Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution. In Proc. of HLT/NAACL, pages 192–199. [find](https://scholar.google.com/scholar?q=S%2E+P%2E+Ponzetto+and+M%2E+Strube%2E+2006%2E+Exploiting+semantic+role+labeling%2C+WordNet+and+Wikipedia+for+coreference+resolution%2E+In+Proc%2E+of+HLT%2FNAACL%2C+pages+192%E2%80%93199%2E) [our card](https://md.research.elamur.ai/free/papers/ponzetto-2006-exploiting-semantic-role-labeling-wordnet/)
24. W. M. Soon, H. T. Ng, and D. Lim. 2001. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27(4):521–544. [find](https://scholar.google.com/scholar?q=W%2E+M%2E+Soon%2C+H%2E+T%2E+Ng%2C+and+D%2E+Lim%2E+2001%2E+A+machine+learning+approach+to+coreference+resolution+of+noun+phrases%2E+Computational+Linguistics%2C+27%284%29%3A521%E2%80%93544%2E) [our card](https://md.research.elamur.ai/free/papers/soon-2001-machine-learning-approach-coreference-resolution/)
25. O. Uryupina. 2003. High-precision identification of discourse new and unique noun phrases. In Proc. of the ACL Student Research Workshop. [find](https://scholar.google.com/scholar?q=O%2E+Uryupina%2E+2003%2E+High%2Dprecision+identification+of+discourse+new+and+unique+noun+phrases%2E+In+Proc%2E+of+the+ACL+Student+Research+Workshop%2E)
26. Y. Versley, A. Moschitti, M. Poesio, and X. Yang. 2008. Coreference systems based on kernels methods. In Proc. of COLING, pages 961–968. [find](https://scholar.google.com/scholar?q=Y%2E+Versley%2C+A%2E+Moschitti%2C+M%2E+Poesio%2C+and+X%2E+Yang%2E+2008%2E+Coreference+systems+based+on+kernels+methods%2E+In+Proc%2E+of+COLING%2C+pages+961%E2%80%93968%2E) [our card](https://md.research.elamur.ai/free/papers/versley-2008-coreference-systems-based-kernels-methods/)
27. R. Vieira and M. Poesio. 2000. Processing definite descriptions in corpora. In S. Botley and A. McEnery, editors, Corpus-based and Computational Approaches to Discourse Anaphora, pages 189–212. UCL Press. [find](https://scholar.google.com/scholar?q=R%2E+Vieira+and+M%2E+Poesio%2E+2000%2E+Processing+definite+descriptions+in+corpora%2E+In+S%2E+Botley+and+A%2E+McEnery%2C+editors%2C+Corpus%2Dbased+and+Computational+Approaches+to+Discourse+Anaphora%2C+pages+189%E2%80%93212%2E+UCL+Pr)
28. M. Vilain, J. Burger, J. Aberdeen, D. Connolly, and L. Hirschman. 1995. A model-theoretic coreference scoring scheme. In Proc. of MUC-6, pages 45–52. [find](https://scholar.google.com/scholar?q=M%2E+Vilain%2C+J%2E+Burger%2C+J%2E+Aberdeen%2C+D%2E+Connolly%2C+and+L%2E+Hirschman%2E+1995%2E+A+model%2Dtheoretic+coreference+scoring+scheme%2E+In+Proc%2E+of+MUC%2D6%2C+pages+45%E2%80%9352%2E) [our card](https://md.research.elamur.ai/free/papers/vilain-1995-model-theoretic-coreference-scoring-scheme/)
29. B. L. Webber. 1979. A Formal Approach to Discourse Anaphora. Garland Publishing, Inc. [find](https://scholar.google.com/scholar?q=B%2E+L%2E+Webber%2E+1979%2E+A+Formal+Approach+to+Discourse+Anaphora%2E+Garland+Publishing%2C+Inc%2E)
30. X. Yang and J. Su. 2007. Coreference resolution using semantic relatedness information from automatically discovered patterns. In Proc. of ACL, pages 528–535. [find](https://scholar.google.com/scholar?q=X%2E+Yang+and+J%2E+Su%2E+2007%2E+Coreference+resolution+using+semantic+relatedness+information+from+automatically+discovered+patterns%2E+In+Proc%2E+of+ACL%2C+pages+528%E2%80%93535%2E) [our card](https://md.research.elamur.ai/free/papers/yang-2007-coreference-resolution-semantic-relatedness-information/)