Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction
This addresses graph clustering challenges in computational linguistics, offering a generic method applicable to various linguistic networks, though it appears incremental as it builds on existing clustering techniques.
The paper tackles the problem of fuzzy graph clustering by introducing the Watset meta-algorithm, which creates an intermediate disambiguated graph and uses hard clustering, showing competitive results in synset, semantic frame, and semantic class induction.
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.