Graph-of-word and TW-IDF: New Approach to Ad Hoc IR
📜 Abstract
In this paper, we introduce novel document representation (graph-of-word) and retrieval model (TW-IDF) for ad hoc IR. Questioning the term independence assumption behind the traditional bag-of-word model, we propose a different representation of a document that captures the relationships between the terms using an unweighted directed graph of terms. From this graph, we extract at indexing time meaningful term weights (TW) that replace traditional term frequencies (TF) and from which we define a novel scoring function, namely TW-IDF, by analogy with TF-IDF. This approach leads to a retrieval model that consistently and significantly outperforms BM25 and in some cases its extension BM25+ on various standard TREC datasets. In particular, experiments show that counting the number of different contexts in which a term occurs inside a document is more effective and relevant to search than considering an overall concave term frequency in the context of ad hoc IR.
✨ Summary
Summary
The paper proposes graph-of-word, an alternative to the bag-of-words representation for ad hoc information retrieval. A document is represented as an unweighted directed graph: vertices are unique terms, and directed edges connect terms that co-occur within a fixed sliding window, with direction encoding term order. The authors use the indegree of a term as its graph-based term weight (TW), replacing traditional term frequency (TF) in the inverted index. The resulting TW-IDF scoring function applies pivoted document-length normalization and inverse document frequency.
The experiments use four TREC collections—Disks 1&2, Disks 4&5, WT10G, and GOV2—and compare TW-IDF with TF-IDF, BM25, Piv+, and BM25+. With the default slope parameter of 0.003, TW-IDF achieves higher MAP than BM25 on all four collections and higher P@10 on all four collections in the reported untuned comparison. The authors interpret the improvement as evidence that counting the number of distinct contexts in which a term occurs is more useful for retrieval than counting its total occurrences with a concave TF normalization. The model does not require explicit concave or lower-bounding normalization, although it still benefits from document-length pivoting.
The paper identifies several limitations and future directions: normalized weighted graphs, graph representations of document collections, and applications to summarization and phrasal indexing.
Subsequent influence
Later research explicitly cites the paper as an early graph-based term-weighting and document-representation method. It is referenced in work on general graph-based text representations, including Bag of Textual Graphs (2019), and in later discussions of graph-based retrieval and passage reranking. A subsequent dissertation also describes graph-of-word and TW-IDF as methods that capture term relationships and compute graph-based term weights. These references indicate continued use of the paper as background for graph-based text modeling, but the sources located do not establish widespread industrial deployment of TW-IDF itself. (asistdl.onlinelibrary.wiley.com)