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.
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.
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:
- Positive edges spanning different clusters.
- 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