---
title: "Chinese Whispers - an Efficient Graph Clustering Algorithm and"
description: "Biemann introduces Chinese Whispers (CW), a randomized clustering algorithm named after the… 14 references, cited by 84 papers here."
authors: ["Chris Biemann"]
year: 2006
venue: "Proceedings of TextGraphs: the First Workshop on Graph Based Methods for Natural Language Processing"
source: "https://aclanthology.org/W06-3812/"
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/en/papers/biemann-2006-chinese-whispers-efficient-graph-clustering/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/biemann-2006-chinese-whispers-efficient-graph-clustering/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems

# Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems

**Authors:** [Chris Biemann](https://md.research.elamur.ai/free/en/authors/chris-biemann/) · **Year:** 2006 · **Venue:** Proceedings of TextGraphs: the First Workshop on Graph Based Methods for Natural Language Processing · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/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/W06-3812/) · [PDF](https://aclanthology.org/W06-3812.pdf) · [OpenAlex](https://openalex.org/W7045898636)

**Citations:** 32 citations (OpenAlex, 2026-10-14) · [84](https://md.research.elamur.ai/free/en/papers/biemann-2006-chinese-whispers-efficient-graph-clustering/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Many NLP datasets are naturally graphs, such as co-occurrence networks or word similarity graphs. They are often very large, so clustering methods must be cheap to run. Biemann introduces Chinese Whispers (CW), a randomized clustering algorithm named after the children's game. Each node starts in its own class. Then, over a few passes in random order, each node takes the class with the largest summed edge weight among its neighbours, and changes take effect immediately. The number of clusters emerges from the process, so CW needs no parameters, and its cost grows linearly with the number of edges. The paper frames CW as an extreme pruning of MCL and tests it on synthetic graphs. It then applies CW to three NLP tasks: language separation, inducing syntactic word classes from the BNC, and word sense induction. CW is unreliable on tiny graphs. On the NLP data, however, it matches or beats competing methods, which makes it practical for graphs too large for heavier algorithms.

## Key points
- **Complexity:** CW runs in O(k·|E|), versus O(k·n²) for MCL. Only on a fully connected graph do the two costs become equal.
- **Non-determinism on small graphs:** on 4-bipartite cliques, only about half the runs split the two cliques apart. This problem fades as graph size grows.
- **Word classes from the BNC:**
  - Setup: the 2000 most frequent words were excluded, and an edge joined two words when they had four or more neighbours in common on both the left and the right.
  - Result: CW found 282 clusters, 26 of them larger than 100 words, with a weighted tag purity of 88.8%. Schütze (1995) reported 53% on a related task.
- **Word sense induction:**
  - Setup: CW replaced MCL in a Dorow & Widdows-style neighbourhood graph. It was evaluated with Bordag's (2006) merged-neighbourhood framework on BNC co-occurrences, using 45 test words.
  - Result: P and R were roughly on par with Bordag's triplet-based method. rP and rR were often higher (e.g., noun rP 94.8 vs 90.9), suggesting CW leaves fewer words unclustered.

## Interesting ideas
- **Keep only the top entry:** viewing CW as MCL that keeps just the single largest entry per row shows a general trick. Aggressively sparsifying an iterative matrix process can turn quadratic cost into edge-linear cost.
- **Update in place:** letting a node's new label be seen at once by nodes processed later in the same pass speeds convergence. It also avoids the oscillating states that appear with synchronous matrix updates, which applies to many label-propagation schemes.
- **Cluster count is not an input:** the number of clusters emerges from the data rather than being set in advance. This suits skewed class distributions and tasks like sense induction, where the number of senses is unknown.
- **Pseudo-ambiguity evaluation:** merging the neighbourhood graphs of two different words and checking whether they can be separated again gives a gold-standard-free way to test sense induction. It could transfer to languages with few annotated resources, such as Ukrainian.
- **Cheap hierarchy:** collapsing each cluster into a hyper-node, weighted by the number of inter-class edges, and re-clustering yields a coarse hierarchy at little cost. This is useful for organising very large lexical or link graphs.

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

📚 Shelves (6): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [⚛️ Physics and Astronomy](https://md.research.elamur.ai/free/en/shelves/physics-and-astronomy/) · 25 works · [⚛️ Statistical and Nonlinear Physics](https://md.research.elamur.ai/free/en/shelves/physics-and-astronomy/statistical-and-nonlinear-physics/) · 22 works

## Cite

Cite as: Chris Biemann. 2006. Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems. Proceedings of TextGraphs: the First Workshop on Graph Based Methods for Natural Language Processing.

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

```bibtex
@inproceedings{biemann2006chinese,
  title = {{Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems}},
  author = {Chris Biemann},
  booktitle = {Proceedings of TextGraphs: the First Workshop on Graph Based Methods for Natural Language Processing},
  year = {2006},
  url = {https://aclanthology.org/W06-3812/}
}
```

- [← previous A (very) Brief Introduction to Fluid Construction Grammar](https://md.research.elamur.ai/free/en/papers/steels-2006-very-brief-introduction-fluid-construction/)
- [next → Fully Parsing the Penn Treebank](https://md.research.elamur.ai/free/en/papers/gabbard-2006-fully-parsing-penn-treebank/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

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

1. F. Amblard. 2002. Which ties to choose? A survey of social networks models for agent-based social simulations. In Proc. of the 2002 SCS International Conference On Artificial Intelligence, Simulation and Planning in High Autonomy Systems, pp.253-258, Lisbon, Portugal. [find](https://scholar.google.com/scholar?q=F%2E+Amblard%2E+2002%2E+Which+ties+to+choose%3F+A+survey+of+social+networks+models+for+agent%2Dbased+social+simulations%2E+In+Proc%2E+of+the+2002+SCS+International+Conference+On+Artificial+Intelligence%2C+Simulation+)
2. C. Biemann, S. Bordag, G. Heyer, U. Quasthoff, C. Wolff. 2004. Language-independent Methods for Compiling Monolingual Lexical Data, Proceedings of CicLING 2004, Seoul, Korea and Springer LNCS 2945, pp. 215-228, Springer, Berlin Heidelberg B. Bollobás. 1998. Modern graph theory, Graduate Texts in Mat… [find](https://scholar.google.com/scholar?q=C%2E+Biemann%2C+S%2E+Bordag%2C+G%2E+Heyer%2C+U%2E+Quasthoff%2C+C%2E+Wolff%2E+2004%2E+Language%2Dindependent+Methods+for+Compiling+Monolingual+Lexical+Data%2C+Proceedings+of+CicLING+2004%2C+Seoul%2C+Korea+and+Springer+LNCS+2945%2C+pp)
3. Trento C. Biemann and S. Teresniak. 2005. Disentangling from Babylonian Confusion – Unsupervised Language Identification. Proceedings of CICLing-2005, Mexico City, Mexico and Springer LNCS 3406, pp. 762-773 [find](https://scholar.google.com/scholar?q=Trento+C%2E+Biemann+and+S%2E+Teresniak%2E+2005%2E+Disentangling+from+Babylonian+Confusion+%E2%80%93+Unsupervised+Language+Identification%2E+Proceedings+of+CICLing%2D2005%2C+Mexico+City%2C+Mexico+and+Springer+LNCS+3406%2C+pp%2E+7)
4. S. van Dongen. 2000. A cluster algorithm for graphs. Technical Report INS-R0010, National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam. [find](https://scholar.google.com/scholar?q=S%2E+van+Dongen%2E+2000%2E+A+cluster+algorithm+for+graphs%2E+Technical+Report+INS%2DR0010%2C+National+Research+Institute+for+Mathematics+and+Computer+Science+in+the+Netherlands%2C+Amsterdam%2E)
5. T. Dunning. 1993. [Accurate Methods for the Statistics of Surprise and Coincidence](https://md.research.elamur.ai/free/en/papers/dunning-1993-accurate-methods-statistics-surprise-coincidence/), Computational Linguistics 19(1), pp. 61-74
6. M. Ester, H.-P. Kriegel, J. Sander and X. Xu. 1996. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proceedings of the 2nd Int. Conf. on Knowledge Discovery and Datamining (KDD'96) Portland, USA, pp. 291-316. [find](https://scholar.google.com/scholar?q=M%2E+Ester%2C+H%2E%2DP%2E+Kriegel%2C+J%2E+Sander+and+X%2E+Xu%2E+1996%2E+A+Density%2DBased+Algorithm+for+Discovering+Clusters+in+Large+Spatial+Databases+with+Noise%2E+In+Proceedings+of+the+2nd+Int%2E+Conf%2E+on+Knowledge+Discover)
7. B. Dorow and D. Widdows. 2003. Discovering Corpus-Specific Word Senses. In EACL-2003 Conference Companion (research notes and demos), pp. 79-82, Budapest, Hungary R. Ferrer-i-Cancho and R.V. [find](https://scholar.google.com/scholar?q=B%2E+Dorow+and+D%2E+Widdows%2E+2003%2E+Discovering+Corpus%2DSpecific+Word+Senses%2E+In+EACL%2D2003+Conference+Companion+%28research+notes+and+demos%29%2C+pp%2E+79%2D82%2C+Budapest%2C+Hungary+R%2E+Ferrer%2Di%2DCancho+and+R%2EV%2E)
8. Sole. 2001. The small world of human language. Proceedings of The Royal Society of London. Series B, Biological Sciences, 268(1482):2261-2265 [find](https://scholar.google.com/scholar?q=Sole%2E+2001%2E+The+small+world+of+human+language%2E+Proceedings+of+The+Royal+Society+of+London%2E+Series+B%2C+Biological+Sciences%2C+268%281482%29%3A2261%2D2265)
9. Schütze. 1995. Distributional tagging. In EACL 7, pages 141–148 part-of-speech J. Šíma and S.E. [find](https://scholar.google.com/scholar?q=Sch%C3%BCtze%2E+1995%2E+Distributional+tagging%2E+In+EACL+7%2C+pages+141%E2%80%93148+part%2Dof%2Dspeech+J%2E+%C5%A0%C3%ADma+and+S%2EE%2E)
10. Schaeffer. 2005. On the np-completeness of some graph cluster measures. Technical Report cs.CC/0506100, arXiv.org e-Print archive, [http://arxiv.org/](http://arxiv.org/). [↗](http://arxiv.org/)
11. B. Stein and O. Niggemann. 1999. On the Nature of Structure and Its Identification. Proceedings of WG'99, Springer LNCS 1665, pp. 122-134, Springer Verlag Heidelberg M. Steyvers, J. B. Tenenbaum. 2005. The large-scale structure of semantic networks: statistical analyses and a model of semantic growt… [find](https://scholar.google.com/scholar?q=B%2E+Stein+and+O%2E+Niggemann%2E+1999%2E+On+the+Nature+of+Structure+and+Its+Identification%2E+Proceedings+of+WG%2799%2C+Springer+LNCS+1665%2C+pp%2E+122%2D134%2C+Springer+Verlag+Heidelberg+M%2E+Steyvers%2C+J%2E+B%2E+Tenenbaum%2E+2005)
12. Ushioda, A. (1996). Hierarchical clustering of words and applications to NLP tasks. In Proceedings of the Fourth Workshop on Very Large Corpora, pp. 28-41. [find](https://scholar.google.com/scholar?q=Ushioda%2C+A%2E+%281996%29%2E+Hierarchical+clustering+of+words+and+applications+to+NLP+tasks%2E+In+Proceedings+of+the+Fourth+Workshop+on+Very+Large+Corpora%2C+pp%2E+28%2D41%2E)
13. Somerset, NJ, USA D. J. Watts. 1999. Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Univ. [find](https://scholar.google.com/scholar?q=Somerset%2C+NJ%2C+USA+D%2E+J%2E+Watts%2E+1999%2E+Small+Worlds%3A+The+Dynamics+of+Networks+Between+Order+and+Randomness%2C+Princeton+Univ%2E)
14. Press, Princeton, USA Z. Wu and R. Leahy (1993): An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence [find](https://scholar.google.com/scholar?q=Press%2C+Princeton%2C+USA+Z%2E+Wu+and+R%2E+Leahy+%281993%29%3A+An+optimal+graph+theoretic+approach+to+data+clustering%3A+Theory+and+its+application+to+image+segmentation%2E+IEEE+Transactions+on+Pattern+Analysis+and+Mac)

*Updated 24 October 2026*