Semantic Word Clusters Using Signed Normalized Graph Cuts

João Sedoc, Jean Gallier, Lyle H. Ungar, Dean P. FosterarXiv 2016 · arXiv

Introduction

Standard word embeddings, such as word2vec and GloVe, are built on the "Distributional Hypothesis," which posits that words appearing in similar contexts share similar meanings. While effective for capturing general semantic relatedness, this approach often fails to distinguish between synonyms (e.g., "happy" and "joyful") and antonyms (e.g., "happy" and "sad"). Because opposites frequently appear in identical syntactic structures—such as "The weather is great" versus "The weather is awful"—vector space models often place them in close proximity.

Table showing how standard embeddings like word2vec and GloVe conflate synonyms and antonyms.

This paper introduces a novel signed spectral normalized graph cut algorithm designed to address this limitation. By incorporating negative edge weights to represent antonymy, the model effectively "pushes" opposite words into different clusters while maintaining the cohesion of synonym groups.

Methodology: Signed Graph Partitioning

The authors treat word clustering as a graph partition problem characterized by both "attraction" (similarity) and "repulsion" (antonymy).

Graph Construction

The system builds a graph where nodes represent individual words.

  • Positive Edges: Weights are derived from the cosine similarity of distributional word embeddings.
  • Negative Edges: Weights are assigned based on known antonym pairs from established thesauri like WordNet and Roget’s.
A signed graph representation where blue lines indicate similarity and red lines indicate antonymy between words like "happy" and "sad".

The Signed Laplacian and sNcut

To cluster this graph, the authors utilize a signed Laplacian ($\bar{L} = \bar{D} - W$), where $\bar{D}$ is the signed degree matrix based on the absolute values of edge weights. They define a Signed Normalized Cut (sNcut) objective function that simultaneously minimizes:

  1. Positive edges spanning different clusters.
  2. Negative edges contained within the same cluster.

Since finding the exact discrete solution is NP-hard, the problem is solved via spectral relaxation—calculating the eigenvectors of the normalized signed Laplacian—followed by an alternating optimization process to recover discrete clusters.

Experimental Evaluation

The method was evaluated using various embeddings (word2vec, GloVe, Eigenwords) and thesauri (Roget’s, Microsoft Word, WordNet 3.0).

Key Results

  • Antonym Separation: The signed clustering algorithm reduced the occurrence of antonym pairs within the same cluster by approximately 90% compared to standard K-means.
  • Semantic Accuracy: On SimLex-999, a benchmark specifically designed to test similarity over relatedness, the combination of thesaurus data and signed clustering achieved an accuracy of 0.96. This significantly outperforms raw word2vec (0.36) and GloVe (0.33).
  • Downstream Impact: Using these refined synonym clusters as features for sentiment analysis improved prediction accuracy on the Stanford Sentiment Treebank, surpassing several neural network baselines.

Discussion and Future Directions

A key insight of this work is that the method is "embedding-agnostic." It functions as a post-processing layer that overlays linguistic knowledge onto statistical data without requiring the retraining of word vectors. However, the approach remains dependent on the coverage of the input thesauri. Furthermore, the current model does not account for polysemy; future work may involve incorporating word sense disambiguation to create sense-specific clusters.

The authors also suggest extending this framework to "evolutionary signed clustering" to track how semantic relationships shift over time within a corpus.

Summary updated

Abstract

Vector space representations of words capture many aspects of word similarity, but such methods tend to make vector spaces in which antonyms (as well as synonyms) are close to each other. We present a new signed spectral normalized graph cut algorithm, signed clustering, that overlays existing thesauri upon distributionally derived vector representations of words, so that antonym relationships between word pairs are represented by negative weights. Our signed clustering algorithm produces clusters of words which simultaneously capture distributional and synonym relations. We evaluate these clusters against the SimLex-999 dataset (Hill et al.,2014) of human judgments of word pair similarities, and also show the benefit of using our clusters to predict the sentiment of a given text.
BibTeX
@misc{sedoc2016semantic,
  author = {João Sedoc and Jean Gallier and Lyle H. Ungar and Dean P. Foster},
  title = {{Semantic Word Clusters Using Signed Normalized Graph Cuts}},
  year = {2016},
  eprint = {1601.05403},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.05403},
}
Figure