TL;DR
This paper introduces corpus2graph, a Python package designed to efficiently generate and process word co-occurrence networks from large text corpora like Wikipedia. It addresses the computational challenges of building these networks, offering a faster, more scalable solution that supports flexible configurations and integrates with existing graph libraries.
What Problem Does This Paper Address?
Word co-occurrence networks are fundamental to many Natural Language Processing (NLP) tasks, including keyword extraction and word sense disambiguation. These networks represent relationships between words based on how often they appear together in a given text. However, generating these networks from massive datasets, such as the entire English Wikipedia, is computationally intensive. Existing NLP tools often lack the specialized components needed to directly process text into networks, forcing researchers to manually handle word preprocessing, sentence analysis, and edge weight definition. Furthermore, experimenting with different network configurations (e.g., the maximum distance between co-occurring words) requires rebuilding the network from scratch each time, which is time-consuming and inefficient.
Methods
corpus2graph tackles these challenges through a multi-stage, efficient pipeline:
- Node Level: Word Preprocessing: The package processes files in parallel, encoding words into local numerical IDs for each file to reduce memory usage. It offers customizable preprocessing options like tokenization, stemming, and punctuation removal. A global dictionary maps all unique words to global IDs.
- Node Co-occurrences: Sentence Analysis: This stage enumerates word co-occurrences within a defined maximum distance (
dmax) in sentences. It supports both fixed-size sliding windows and a maximum distance definition. The tool can also compute global word counts, which are useful for filtering nodes based on frequency. - Edge Attribute Level: Word Pair Analysis: Here, co-occurrence counts are aggregated to define edge weights. The paper highlights a progressive calculation design where networks are built incrementally, allowing for faster rebuilding when configurations change. They also support user-defined weight functions and filtering of nodes based on frequency or vocabulary size.
- Matrix-Type Representations: For efficient processing,
corpus2graphutilizes matrix-type representations for graph data, adapting network algorithms to matrix calculations. This is particularly beneficial for tasks like calculating transition matrices for random walks, where it significantly outperforms traditional network-based approaches.
Datasets
The paper uses the English Wikipedia dump (April 2017) for its experiments, both a small subset (7416 tokens) and the entire corpus. No new benchmarks are introduced; rather, the focus is on efficiently processing existing large-scale text data.
Key Insights and Ideas
- Progressive Calculation is Key: The "nodes-edges-weight three-level progressive calculation design" is a core innovation. It means that if you want to change a parameter (like
dmax), you don't have to start from scratch. You can build upon previously computed results, drastically speeding up experimentation. - Matrix Math for NLP Graphs: Representing graph data as matrices and performing calculations in a matrix-fashion (rather than purely network-based) offers significant speedups, especially for algorithms like random walk transition matrix calculation.
- Parallelization for Scale: Efficiently distributing the processing of large corpora across multiple cores is crucial for handling datasets like Wikipedia within reasonable timeframes.
Key Results
The experiments demonstrate corpus2graph's efficiency:
- Network Generation Speed: For a small corpus,
corpus2graphgenerated word networks in approximately 15 seconds, outperforming a baseline method using igraph and graph-tool. Even without multiprocessing, it was faster. - Large Corpus Processing: For the entire English Wikipedia dump,
corpus2graphtook less than 3 hours to generate all nodes and weighted edges, a significant achievement for such a large dataset. - Random Walk Transition Matrix Calculation: The tool achieved a remarkable speedup, calculating the transition matrix 2390 times faster than the built-in NetworkX method.
Limitations and Future Work
- Limitations: The paper notes that not all network algorithms are suitable for adaptation into a matrix version, and
corpus2graphis intended as a supplement, not a replacement, for existing graph libraries. The baseline method with NetworkX was faster for smaller corpora, though it became memory-intensive with larger ones. - Future Work: The authors suggest extending
corpus2graphto support more graph processing methods and to connect with additional graph libraries.
Summary updated