Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction
arXiv:1808.06696 · doi:10.1162/COLI_a_00354
Abstract
We present a detailed theoretical and computational analysis of the Watset meta-algorithm for fuzzy graph clustering, which has been found to be widely applicable in a variety of domains. This algorithm creates an intermediate representation of the input graph that reflects the "ambiguity" of its nodes. Then, it uses hard clustering to discover clusters in this "disambiguated" intermediate graph. After outlining the approach and analyzing its computational complexity, we demonstrate that Watset shows competitive results in three applications: unsupervised synset induction from a synonymy graph, unsupervised semantic frame induction from dependency triples, and unsupervised semantic class induction from a distributional thesaurus. Our algorithm is generic and can be also applied to other networks of linguistic data.
arXiv comment58 pages, 17 figures, accepted at the Computational Linguistics journal
References in corpus (9)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- From Frequency to Meaning: Vector Space Models of Semantics
- Cross-lingual Annotation Projection for Semantic Roles
- Human and Machine Judgements for Russian Semantic Relatedness
- Watset: Automatic Induction of Synsets from a Graph of Synonyms
- Unsupervised Semantic Frame Induction using Triclustering