Fixed versus dynamic co-occurrence windows in TextRank term weights for information retrieval

Wei Lu, Qikai Cheng, Christina LiomaSIGIR 2012 · OpenReview

TL;DR

This paper explores how the way we define "co-occurrence" for terms in a document can impact the effectiveness of TextRank for information retrieval. By moving from fixed-size windows to dynamic windows that adapt to sentence or paragraph boundaries, they show promising improvements in early search result precision.

What Problem Does This Paper Address?

Traditional methods for calculating term importance in information retrieval often rely on fixed-size windows to determine when terms are considered "related" (co-occurring). The TextRank algorithm, a popular graph-based approach, typically uses a fixed window of k terms to build its co-occurrence graph. However, the authors question whether this fixed window is optimal. They hypothesize that meaningful term relationships might naturally span across sentence or paragraph structures, and that a rigid window might miss these broader connections or incorrectly group unrelated terms. This paper investigates whether adapting the co-occurrence window to the document's natural linguistic structure can lead to better term weights for information retrieval.

Methods

The core of this work involves modifying how TextRank's co-occurrence graphs are constructed.

  • TextRank Algorithm: The paper uses the standard TextRank algorithm, which is a variant of PageRank. In this context, terms in a document are represented as vertices in a graph, and edges represent co-occurrence. TextRank iteratively computes a score (weight) for each term based on its connections to other terms and their weights.
  • Dynamic Co-occurrence Windows: The novel aspect is the definition of the co-occurrence window. Instead of a fixed k terms, they propose two dynamic approaches:
  • Sentence-level: Terms are considered co-occurring if they appear within the same sentence.
  • Paragraph-level: Terms are considered co-occurring if they appear within the same paragraph.
  • Information Retrieval: The computed TextRank term weights are then used in a ranking function. Specifically, they are combined linearly with inverse document frequency (IDF) weights, as proposed in prior work [1, 2]. This combined score is used to re-rank the top 1000 documents initially retrieved by a search system.

Datasets

The experiments were conducted on two standard information retrieval datasets:

  • Reuters RCV1: A large dataset (2.5GB) with 50 title-only queries.
  • INEX 2005: A dataset (764MB) with 47 content-only queries. For INEX, relevance was assessed at the document section level, and a document was considered relevant if any of its sections were marked as relevant.

Key Insights and Ideas

  • Linguistic Structure Matters: The paper strongly suggests that the natural linguistic boundaries of sentences and paragraphs are more meaningful for defining term relationships than arbitrary fixed-size windows.
  • Fixed Windows May Be Suboptimal: The assumption that a fixed window of k terms is universally optimal for TextRank term weights is challenged.
  • Sentence-Level Wins for Early Precision: Dynamically adjusting the co-occurrence window to sentence boundaries appears to be particularly beneficial for improving precision in the very first search results.
  • Dynamic Windows Can Outperform Fixed Ones: The experiments demonstrate that dynamic windows, especially at the sentence level, can achieve better performance than fixed windows, even those tuned to commonly cited optimal values in the literature.

Key Results

The paper presents results from a re-ranking scenario, comparing fixed windows (5 and 6 terms) against sentence-level and paragraph-level dynamic windows.

  • Sentence-based co-occurrence outperformed fixed-window co-occurrence in terms of early precision (P@10 and MRR) on the RCV1 dataset.
  • On the INEX dataset, sentence-based co-occurrence also showed gains in early precision (P@10 and MRR) over fixed windows.
  • MRR (Mean Reciprocal Rank), a metric sensitive to the rank of the first relevant document, consistently benefited from dynamic windows across both datasets.
  • While results varied for NDCG (Normalized Discounted Cumulative Gain), sentence-based co-occurrence was often competitive or superior to fixed windows.
  • Paragraph-based co-occurrence generally performed comparably to or slightly worse than sentence-based co-occurrence, though it still showed advantages over fixed windows in some metrics.
  • The authors note that the statistical significance of the results varied, and some differences were not statistically significant when using a t-test.

Limitations and Future Work

  • Re-ranking Scenario: The experiments were conducted in a re-ranking setting, meaning they only optimized the order of the top 1000 initially retrieved documents. The authors suggest that full-ranking experiments on larger datasets are needed to further investigate the optimal co-occurrence vicinity.
  • Dataset Size: While RCV1 and INEX are substantial, the authors acknowledge that more extensive experiments are required.
  • Statistical Significance: The authors note that some results were not statistically significant, indicating a need for more robust validation.
  • Future Work: The paper calls for further investigation into optimal term co-occurrence vicinity through larger-scale experiments and full-ranking scenarios.

Summary updated

Abstract

TextRank is a variant of PageRank typically used in graphs that represent documents, and where vertices denote terms and edges denote relations between terms. Quite often the relation between terms is simple term co-occurrence within a fixed window of k terms. The output of TextRank when applied iteratively is a score for each vertex, i.e. a term weight, that can be used for information retrieval (IR) just like conventional term frequency based term weights. So far, when computing TextRank term weights over co-occurrence graphs, the window of term co-occurrence is always fixed. This work departs from this, and considers dynamically adjusted windows of term co-occurrence that follow the document structure on a sentence- and paragraph-level. The resulting TextRank term weights are used in a ranking function that re-ranks 1000 initially returned search results in order to improve the precision of the ranking. Experiments with two IR collections show that adjusting the vicinity of term co-occurrence when computing TextRank term weights can lead to gains in early precision.
BibTeX
@inproceedings{lu2012fixed,
  author = {Wei Lu and Qikai Cheng and Christina Lioma},
  title = {{Fixed versus dynamic co-occurrence windows in TextRank term weights for information retrieval}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2012},
  url = {https://openreview.net/forum?id=HJ-AEI-_WB},
}
Figure