Sparse Projections over Graph

Deng Cai, Xiaofei He, Jiawei Han

Introduction

Dimensionality reduction is a fundamental technique in machine learning used to simplify high-dimensional data. Standard algorithms like Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) are widely used but suffer from a significant "interpretability" flaw: the resulting low-dimensional components are linear combinations of all original features. In a text dataset with 20,000 words, a standard PCA component is a dense mix of every word, making it impossible for humans to discern which specific features are driving the model.

Research suggests that the human brain utilizes sparse representations, focusing on specific, salient components. To bridge this gap, the authors propose Sparse Projection over Graphs (SPG), a framework that identifies a minimal subset of relevant features to create interpretable and accurate models.

The Sparse Projections over Graph (SPG) Framework

The core innovation of SPG is a two-step process that leverages the efficiency of Graph Laplacians to achieve sparsity:

  1. Graph Embedding: The algorithm first constructs an affinity graph (e.g., a nearest-neighbor graph) to capture the geometric or categorical structure of the data. It then solves for an "ideal" low-dimensional embedding by finding the eigenvectors of the Graph Laplacian.
  2. Lasso Regression: Once the target coordinates are established, the algorithm employs Lasso regression ($L_1$-penalized least squares) to find a transformation vector. The $L_1$ penalty naturally shrinks the coefficients of irrelevant features to exactly zero, resulting in a sparse projection.

A key theoretical contribution is Theorem 1, which proves that this two-step approach is a valid relaxation of the computationally harder problem of finding sparse eigenvectors directly. This makes SPG significantly faster than previous greedy approaches like sparse LDA.

Experimental Evaluation

The authors evaluated SPG on two classic document corpora for text clustering: TDT2 (9,394 documents, 30 categories) and Reuters-21578 (8,067 documents, 30 categories). These datasets are notoriously difficult due to their high dimensionality and class imbalance.

Key Results

SPG demonstrated remarkable performance across both datasets, particularly in its ability to maintain high accuracy with minimal features:

  • Superior Accuracy: On the TDT2 dataset, SPG achieved an average clustering accuracy of 98.1%, far outperforming baseline K-means (79.9%) and Non-negative Matrix Factorization (88.5%).
  • Extreme Sparsity: The model maintained peak performance while achieving over 99% sparsity, meaning it categorized thousands of documents using only a handful of key words.
  • Robustness at Low Cardinality: Unlike other sparse methods such as SparsePCA (SPCA), which require a larger number of features to stabilize, SPG reaches near-peak performance even when the cardinality ($k$) is very low.
Clustering accuracy on the TDT2 dataset as a function of cardinality (k). SPG (stars) significantly outperforms SPCA (circles) and baselines.
Clustering accuracy on the Reuters-21578 dataset, demonstrating SPG's consistent performance gains across different corpora.

Discussion and Future Work

The success of SPG highlights a "less is more" effect: by discarding 99% of features, the model removes noise and improves clustering accuracy. However, the authors note that performance is sensitive to the quality of the initial affinity graph. Future work may explore more sophisticated manifold encoding techniques or extend the framework to non-linear projections via Reproducing Kernel Hilbert Space (RKHS) to handle more complex data structures.

Conclusion

Sparse Projection over Graphs (SPG) provides a powerful alternative to traditional dimensionality reduction. By combining graph-based structural learning with Lasso-driven sparsity, it offers a fast, flexible, and highly interpretable method for analyzing high-dimensional data without sacrificing predictive power.

Summary updated

Abstract

Recent study has shown that canonical algorithms such as Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) can be obtained from graph based dimensionality reduction framework. However, these algorithms yield projective maps which are linear combination of all the original features. The results are difficult to be interpreted psychologically and physiologically. This paper presents a novel technique for learning a sparse projection over graphs. The data in the reduced subspace is represented as a linear combination of a subset of the most relevant features. Comparing to PCA and LDA, the results obtained by sparse projection are often easier to be interpreted. Our algorithm is based on a graph embedding model, which encodes the discriminating and geometrical structure in terms of the data affinity. Once the embedding results are obtained, we then apply regularized regression for learning a set of sparse basis functions. Specifically, by using L1-norm regularizer (e.g. lasso), the sparse projections can be efficiently computed. Experimental results on two document databases demonstrate the effectiveness of our method.
BibTeX
@inproceedings{cai2008sparse,
  author = {Deng Cai and Xiaofei He and Jiawei Han},
  title = {{Sparse Projections over Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure