Word-Graph2vec: An efficient word embedding approach on word co-occurrence graph using random walk technique

Wenting Li, Yuanzhe Cai, Zeyu Chen, Chen, Huacan, Chen, Zeyu, Huang, Feijuan, Cai, YuanzhearXiv 2023 · DOI · arXiv

TL;DR

Word-Graph2vec is a novel word embedding approach that dramatically speeds up training on massive datasets by shifting the focus from raw text to a word co-occurrence graph. By performing biased random walks on this graph to generate a representative "sampling corpus," the authors achieve training speeds 4–5x faster than Word2vec and 2–3x faster than FastText, without sacrificing accuracy.

What Problem Does This Paper Address?

In the world of Natural Language Processing (NLP), word embeddings (like Word2vec and GloVe) are the bedrock of most tasks. However, these models have a scaling problem: their training time increases linearly with the size of the corpus. As we move into the era of "big data" with datasets spanning billions of words, training these models becomes prohibitively expensive in terms of time and compute.

The authors identify a specific bottleneck: standard models repeatedly scan the entire raw text to learn statistical correlations. They argue that this is inefficient because language has a finite vocabulary and many fixed expressions. Once you've seen a certain amount of text, the underlying relationships between words (the "word graph") stabilize, even if the total number of words in the corpus continues to grow.

Methods

The authors propose a three-step pipeline called Word-Graph2vec:

  1. Graph Construction: Instead of reading the text line-by-line during training, they first convert the entire corpus into a weighted directed word co-occurrence graph.
  2. Nodes: Unique words.
  3. Edges: Represent word order (direction) and co-occurrence.
  4. Edge Weights: Based on how often two words appear together.
  5. Node Weights: Calculated using TF (Term Frequency) or TF-IDF to represent word importance.
  6. Random Walk Sampling: They use a biased random walk technique (inspired by Node2vec) to traverse the graph. The number of times a walk starts at a specific word is determined by that word's TF-IDF weight. This process generates a "sampling corpus"—a set of word sequences that capture the structural essence of the original text but in a much smaller volume.
  7. Embedding Training: Finally, they apply the standard Skip-gram model to this sampled corpus to generate the final word vectors.

What’s new? While random walks on graphs aren't new (e.g., DeepWalk), applying them to a co-occurrence graph specifically to compress the training data for traditional word embedding models is a clever architectural shift.

Datasets

The researchers evaluated their model using several standard benchmarks:

  • Text8: A 100MB slice of cleaned Wikipedia text.
  • One Billion Words Benchmark: A large-scale corpus (2.51GB) used to test statistical language modeling.
  • En-Wikipedia: A massive 8.22GB corpus of English Wikipedia articles.
  • Concatenated Sets: To test scalability, they merged multiple Wikipedia datasets to create corpora up to 24.6GB.

Key Insights and Ideas

  • The "Finite Vocabulary" Advantage: The most profound insight is that while a corpus can grow infinitely, the English vocabulary does not. An adult's active vocabulary is roughly 20,000 words. Consequently, as a dataset grows from 1GB to 10GB, the density and size of the word graph change only slightly. This allows Word-Graph2vec to have a nearly stable runtime regardless of how massive the input data becomes.
  • Sampling vs. Scanning: By training on a sampled version of the graph, the complexity moves from $O(N)$ (where $N$ is total words) to $O(nl)$ (where $n$ is the number of walks and $l$ is walk length). Since $nl$ can be kept much smaller than $N$ on large datasets, the efficiency gains are massive.
  • Capturing Marginal Words: Surprisingly, the random walk approach is better at capturing "marginal words" (words that appear infrequently) than standard linear scans, which helps the model maintain high accuracy even with less training data.

Key Results

  • Efficiency: Word-Graph2vec is 4 to 5 times faster than traditional Word2vec and 2 to 3 times faster than FastText.
  • Scalability: As shown in the paper's "Times vs. Size" graph, the runtime for Word2vec and FastText increases linearly with data size. In contrast, Word-Graph2vec’s runtime stays relatively flat, with only a slight increase due to the initial overhead of loading the corpus.
  • Accuracy: On tasks like Categorization (BLESS, Battig), Similarity (MEN, SimLex999), and Analogy (MSR), Word-Graph2vec performed comparably to or better than the baselines. For example, on the En-Wikipedia dataset, it achieved a score of 83.5 on the BLESS categorization task, significantly outperforming Word2vec (70.5) and FastText (77.0).

Limitations and Future Work

  • I/O Bottlenecks: The authors note that while the training is fast, the "slight increase" in runtime on very large sets is mostly due to the time required to load the raw corpus into memory to build the graph.
  • Hyperparameter Sensitivity: The performance relies on choosing the right parameters for the random walks ($p$ and $q$ values). The paper finds that a $(p, q)$ combination of $(1, 0.001)$ works best, but this might vary across different languages.
  • Future Directions: While the paper focuses on English, future work could explore how this graph-based approach handles morphologically rich languages or specialized domains (like medical or legal texts) where word co-occurrence patterns might be more complex.

Summary updated

Abstract

Word embedding has become ubiquitous and is widely used in various natural language processing (NLP) tasks, such as web retrieval, web semantic analysis, and machine translation, and so on. Unfortunately, training the word embedding in a relatively large corpus is prohibitively expensive. We propose a graph-based word embedding algorithm, called Word-Graph2vec, which converts the large corpus into a word co-occurrence graph, then takes the word sequence samples from this graph by randomly traveling and trains the word embedding on this sampling corpus in the end. We posit that because of the limited vocabulary, huge idioms, and fixed expressions in English, the size and density of the word co-occurrence graph change slightly with the increase in the training corpus. So that Word-Graph2vec has stable runtime on the large-scale data set, and its performance advantage becomes more and more obvious with the growth of the training corpus. Extensive experiments conducted on real-world datasets show that the proposed algorithm outperforms traditional Word2vec four to five times in terms of efficiency and two to three times than FastText, while the error generated by the random walk technique is small.
BibTeX
@misc{li2023word,
  author = {Wenting Li and Yuanzhe Cai and Zeyu Chen and Chen, Huacan and Chen, Zeyu and Huang, Feijuan and Cai, Yuanzhe},
  title = {{Word-Graph2vec: An efficient word embedding approach on word co-occurrence graph using random walk technique}},
  year = {2023},
  eprint = {2301.04312},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2301.04312},
}
Figure