Modeling Text as Word Co-occurrence Graphs

39 concepts35 papers2 proposals

For decades, natural language processing has operated under a fundamental tension between two representational paradigms. On one hand, the Bag-of-Words (BoW) model treats documents as unstructured collections of word frequencies, completely discarding word order and syntactic context. On the other hand, sequence models (such as LSTMs and Transformers) treat text as a rigid, linear stream of tokens.

While sequential modeling is highly powerful, it can be remarkably brittle. As noted by François Rousseau et al. in Text Categorization as a Graph Classification Problem, minor variations or inversions in phrasing—such as changing "news article" to "article about news"—can break rigid sequence matches or alter $n$-gram features entirely. Furthermore, sequence models scale poorly when trying to ingest long-term histories or large corpora due to context window limitations.

The Graph-of-Words (GoW) framework offers an elegant solution to this tension. By mapping text into a network where unique words are nodes and local co-occurrences are edges, this approach captures non-linear structural relationships while remaining invariant to minor word-order permutations.


How the Graph-of-Words is Built

The construction of a word co-occurrence graph is straightforward and unsupervised. It relies on a sliding window mechanism:

  1. Node Definition: Every unique word or term within a document (or corpus) is mapped to a single, unique node in the graph.
  2. Edge Creation: A sliding window of a fixed size $k$ moves through the text token by token. An edge is drawn between any two words that appear together within this window.
  3. Weighting: Edges can be unweighted, directed to preserve sequential flow, or weighted based on co-occurrence frequency or metrics like Positive Point-wise Mutual Information (PMI).
Text: "data science is the science of data"
Sliding Window (size k=3)

[data science is]        -> Edges: (data, science), (science, is), (data, is)
     [science is the]    -> Edges: (science, the), (is, the)
         [is the science]-> Edges: (the, science)
...

As demonstrated by Antoine J.-P. Tixier et al. in GoWvis: A Web Application for Graph-of-Words-based Text Visualization and Summarization, this simple pipeline transforms a linear sequence into a topological map. It preserves local syntactic context while abstracting away the rigid constraints of absolute token positioning.


Why It Works: The Structural Advantages

The power of the Graph-of-Words representation stems from three core structural properties: permutation invariance, long-distance bridging, and context compression.

1. Invariance to Word Order Permutations

Because edges connect words within a flexible neighborhood rather than enforcing a strict sequence, structural text models are highly robust to stylistic variations. Giannis Nikolentzos et al. exploit this property in Shortest-Path Graph Kernels for Document Similarity. By measuring similarity via graph kernels that evaluate shortest paths between terms, their model successfully identifies semantic alignment between documents even when the phrasing is inverted or non-adjacent.

2. Long-Distance Bridging

In a standard sequence model, two related terms separated by hundreds of words can only communicate if an attention mechanism or recurrent state successfully propagates information across the entire intermediate sequence. In a Graph-of-Words, if a central keyword appears in both the introduction and the conclusion, it acts as a topological "bridge."

As shown by Yufeng Zhang et al. in A Graph-based Relevance Matching Model for Ad-hoc Retrieval, this allows information to propagate across distant sections of text via graph neural networks, capturing long-range semantic dependencies that linear models often miss.

3. Context Compression

For tasks involving long-form text or historical user data, sequence lengths can quickly overwhelm model memory. A graph representation compresses this history. Kun Wu et al. leverage this in PASUM: A Pre-training Architecture for Social Media User Modeling Based on Text Graph by compressing a user's entire historical corpus of posts into a single, fixed-size word graph. This effectively bypasses the input length limitations inherent to Transformers.


Unsupervised Topology: PageRank and Degeneracy

Once text is represented as a graph, we can discard traditional frequency metrics like $tf-idf$ and instead use graph theory to determine term importance.

Centrality and PageRank

Instead of asking how often a word appears, we can ask how central it is to the network topology. Nikolaos Aletras et al. demonstrate this in Labelling Topics using Unsupervised Graph-based Methods, applying the PageRank algorithm to co-occurrence graphs to automatically extract highly descriptive labels for topic models without requiring any labeled training data.

Graph Degeneracy ($k$-Core)

A powerful metric for text analysis is graph degeneracy, specifically $k$-core decomposition. A $k$-core is the maximal subgraph where every node has at least degree $k$. The words that persist in the highest-order cores represent the most cohesive, interconnected nucleus of the text.

[Word A] --- [Word B]
   |  \       /  |
   |   [Word C]  |  <- High k-core (Dense, central topic)
   |  /       \  |
[Word D] --- [Word E]
                 |
              [Word F] <- Low k-core (Peripheral detail)

The authors of Combining Graph Degeneracy and Submodularity for Unsupervised Extractive Summarization use this property to identify the most critical sentences in a document by scoring them based on their words' $k$-core values. Similarly, Polykarpos Meladianos et al. utilize graph degeneracy in Degeneracy-Based Real-Time Sub-Event Detection in Twitter Stream to detect sudden shifts in vocabulary density, allowing them to spot breaking news events in real time.


Supervised Learning with Text-Level GNNs

Early applications of Graph Neural Networks (GNNs) to text classification constructed a single, massive global graph across an entire dataset (where both documents and words were nodes). However, this setup was transductive, meaning it could not easily evaluate new, unseen documents without recomputing the entire global graph.

Modern architectures solve this by building individual text-level graphs for each document.

Document 1 Stream -> [Graph 1] -> GNN -> Classification
Document 2 Stream -> [Graph 2] -> GNN -> Classification

Lianzhe Huang et al. introduce this paradigm in Text Level Graph Neural Network for Text Classification, demonstrating that independent document graphs drastically reduce memory consumption and enable real-time inference.

Crucially, this shift enables inductive learning. As Xueli Yu argues in Every Document Owns Its Structure: Inductive Text Classification via Graph Neural Networks, because the GNN learns message-passing dynamics over local word interactions rather than global node identities, the model can seamlessly generalize to entirely new documents containing unseen words at test time.

To optimize feature extraction from these structures, researchers have introduced specialized layers. For instance, Hongyang Gao et al. propose gPool and hConv layers in Learning Graph Pooling and Hybrid Convolutional Operations for Text Representations, which adaptively select critical word nodes and blend graph operations with standard 1D convolutions.

Similarly, Giannis Nikolentzos et al. develop the MPAD framework in Message Passing Attention Networks for Document Understanding, utilizing message-passing attention with a virtual "master node" to aggregate document-level semantics efficiently.

By treating text as a network of co-occurring terms, the Graph-of-Words representation transforms natural language from a rigid sequence into a flexible topological space—capturing the structural essence of language while remaining robust to its surface-level variations.

Key Foundational Work

Graph-of-word and TW-IDF: new approach to ad hoc IR (2013) — contributed 2 concept elements to this direction.
Unsupervised Natural Language Processing Using Graph Models (2007) — contributed 1 concept elements to this direction.
JoBimText Visualizer: A Graph-based Approach to Contextualizing Distributional Similarity (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_of_words_representation_c863548a,
  title = {graph-of-words representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-of-words-representation/rdr_c863548acb014d7fa297635e13f50ba8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_of_words_representation_c863548a_v1,
  title = {graph-of-words representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-of-words-representation/rdr_c863548acb014d7fa297635e13f50ba8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake