Locality preserving indexing for document representation

Xiaofei He, Deng Cai, Haifeng Liu, Wei-Ying MaSIGIR 2004 · DOI

TL;DR

This paper introduces Locality Preserving Indexing (LPI), a novel method for representing and indexing documents. Unlike traditional methods like Latent Semantic Indexing (LSI) that focus on global document structure, LPI leverages local neighborhood information to capture more discriminative semantic features, leading to improved representation accuracy.

What Problem Does This Paper Address?

Efficiently representing and indexing documents is crucial for tasks like clustering, classification, and retrieval. Existing methods, notably Latent Semantic Indexing (LSI), often rely on dimensionality reduction techniques like Singular Value Decomposition (SVD). While LSI is effective at uncovering the global structure of the document space, it tends to focus on identifying the most representative features rather than the most discriminative ones. This can lead to suboptimal performance when distinguishing between documents with subtle semantic differences. The paper argues that the intrinsic structure of document spaces might be more complex than a simple linear subspace and that local relationships between documents are often more important for capturing semantic similarity, especially in real-world applications.

Methods

The core of the proposed method, Locality Preserving Indexing (LPI), is built upon Locality Preserving Projections (LPP). LPP is a linear dimensionality reduction technique that aims to preserve the local neighborhood structure of data.

Here's a breakdown of the LPI approach:

  • Locality Preserving Projections (LPP): LPP assumes that the data lies on a manifold and seeks to find a low-dimensional representation that preserves the local geometry. It does this by constructing an adjacency graph where nodes represent documents and edges connect neighboring documents. The algorithm then finds a transformation that minimizes the distance between projected neighboring points while maximizing the distance between non-neighboring points. This is achieved by solving a generalized eigenvalue problem involving the graph Laplacian.
  • PCA Preprocessing: To handle the high dimensionality of document spaces and computational challenges, LPI first applies Principal Component Analysis (PCA) to project documents into a lower-dimensional subspace. This step also helps in noise reduction.
  • Adjacency Graph Construction: An adjacency graph is built where documents are nodes. An edge is placed between two documents if they are considered "close" (e.g., one is among the k-nearest neighbors of the other). The weights of these edges (Sij) reflect the similarity between documents.
  • Eigenmap Computation: The algorithm then computes eigenvectors and eigenvalues for a generalized eigenvector problem derived from the adjacency graph and the document data. These eigenvectors form the transformation matrix that maps documents to a low-dimensional semantic subspace.

The paper also provides a theoretical analysis showing that LPP can be seen as an optimal approximation to Linear Discriminant Analysis (LDA) under the assumption that neighboring documents are semantically related, even when class labels are unavailable.

Datasets

The paper evaluates LPI on two standard document collections:

  • Reuters-21578: A collection of news articles. For experiments, the authors selected the largest 20 semantic categories and further split the data into 30 subsets for detailed analysis.
  • TDT2: A corpus of news from various sources. Similar to Reuters-21578, the largest 20 categories were selected, and the data was split into 30 subsets.

Key Insights and Ideas

  • Local Structure Matters: The central idea is that preserving local neighborhood relationships in the document space is more effective for capturing semantic similarity than solely focusing on global structure, as LSI does.
  • LPI as an Optimal Approximation to LDA (Unsupervised): The theoretical analysis suggests that LPI can act as an unsupervised proxy for LDA, effectively discovering discriminative features even without explicit class labels, by assuming that nearby documents share similar topics.
  • Non-linear Structure Discovery: While LPI is a linear projection method, its locality-preserving nature allows it to capture some aspects of non-linear manifold structures in the document space, which is a limitation of linear methods like LSI.
  • Improved Similarity Measures: The experiments demonstrate that LPI leads to more accurate similarity measures (evaluated using average precision) compared to LSI and a baseline (original representation).

Key Results

The experimental results on both Reuters-21578 and TDT2 datasets consistently show that LPI outperforms LSI and the baseline in terms of average precision.

  • Reuters-21578: LPI achieved an overall average precision of 64.78%, significantly outperforming LSI (60.22%) and the baseline (59.10%). LPI also achieved a much lower optimal dimensionality (12.7) compared to LSI (246).
  • TDT2: LPI achieved an overall average precision of 90.6%, again significantly outperforming LSI (81.5%) and the baseline (81.4%). The optimal dimensionality for LPI was remarkably low at 9.1, compared to LSI's 469.6.

These results indicate that LPI is more effective at discovering the intrinsic semantic structure of documents and requires significantly fewer dimensions for representation.

Limitations and Future Work

  • Real-world Application Uncertainty: The authors acknowledge that while LPI shows promise, its effectiveness in real-world applications like information retrieval remains an open question.
  • Estimating Intrinsic Dimensionality: A key challenge is determining the optimal intrinsic dimensionality of the document space, which is not fully addressed by current methods.
  • Manifold Assumption: While LPI can capture some non-linear structure, the assumption of data lying on a manifold might need further exploration for highly complex document relationships.

Future work could focus on applying LPI to information retrieval tasks and exploring methods for more robust estimation of intrinsic dimensionality.

Summary updated

BibTeX
@inproceedings{he2004locality,
  author = {Xiaofei He and Deng Cai and Haifeng Liu and Wei-Ying Ma},
  title = {{Locality preserving indexing for document representation}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2004},
  doi = {10.1145/1008992.1009012},
}
Figure