Accelerated Combinatorial Search for Outlier Detection with Provable Bound on Sub-Optimality

Guihong Wan, Haim SchweitzerAAAI 2021 · DOI

Abstract

Principal Component Analysis (PCA) is a fundamental tool for dimensionality reduction, yet its sensitivity to outliers remains a significant challenge. Robust subspace recovery—finding the optimal subset of inliers—is a combinatorial problem that typically forces a choice between fast heuristics and slow, exact methods. This paper presents Chunk-A, an algorithm that bridges this gap by framing outlier detection as a graph search. By integrating "chunk recursive elimination" with A search heuristics, Chunk-A* provides a scalable solution with provable mathematical bounds on sub-optimality.

Introduction

The core challenge in robust subspace recovery is identifying $k$ outliers in a dataset of $n$ points such that their removal minimizes the PCA reconstruction error for the remaining inliers. Standard PCA is notoriously fragile; a single distant outlier can drastically rotate the principal components, leading to misleading results.

PCA vs. Robust PCA with an outlier

While combinatorial search methods like A can find optimal solutions, they suffer from exponential complexity, making them impractical for large datasets. Conversely, ranking heuristics are fast but often fail to find the global optimum in complex data distributions. Chunk-A addresses these limitations by optimizing the search process through data "chunking."

Methodology: The Chunk-A* Algorithm

Chunk-A innovates on traditional A search through three primary mechanisms:

1. Chunking and Super-Children

In a standard A search for outliers, each level of the search tree adds a single point to the outlier set. Chunk-A introduces "chunking," where the algorithm identifies a group (or "chunk") of $c$ potential outliers and processes them as a single "super child" node. This allows the search to skip multiple levels of the tree, drastically reducing the number of nodes explored.

Standard A* vs. Chunk-A* Search Trees

2. Filter Functions for Pruning

To efficiently navigate the search space, the algorithm employs filter functions that calculate lower ($l$) and upper ($u$) bounds on the PCA error based on data eigenvalues. These bounds "sandwich" the true error, allowing the algorithm to prune branches that are mathematically guaranteed not to contain the optimal solution.

3. Iterative Refinement

Following the search, an iterative refinement step is applied. Similar to k-means, it alternates between calculating the PCA subspace and updating the outlier set based on reconstruction errors. This step ensures that even if the initial search was slightly sub-optimal, the final result is highly accurate.

Experimental Evaluation

The researchers tested Chunk-A* across synthetic models (Haystack, Blurryface) and large-scale real-world datasets (Sift, YPMSD, Covtype).

  • Scalability: On the Sift dataset containing 1 million points, Chunk-A* identified outliers in just 65 seconds. In comparison, existing methods like R-graph and iSearch often exceeded memory limits or required significantly more time.
  • Accuracy: In image-based experiments using the Yale Face Database B, Chunk-A* consistently achieved lower reconstruction errors than established robust methods such as FMS, GGD, and R1PCA.
  • Provable Bounds: Unlike purely heuristic methods, Chunk-A* provides a fractional bound, offering a theoretical guarantee on how close the found solution is to the global optimum.

Conclusion

Chunk-A represents a significant advancement in robust outlier detection. By combining the rigor of combinatorial search with the efficiency of chunk-based elimination, it enables high-accuracy subspace recovery on datasets with millions of points. While future work may focus on optimizing performance for sparse data and automated parameter selection, Chunk-A currently stands as a powerful tool for reliable data cleaning and dimensionality reduction.

Full Citation: Wan, G., & Schweitzer, H. (2021). Accelerated Combinatorial Search for Outlier Detection with Provable Bounds on Sub-Optimality. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12436-12444.

Summary updated

BibTeX
@inproceedings{wan2021accelerated,
  author = {Guihong Wan and Haim Schweitzer},
  title = {{Accelerated Combinatorial Search for Outlier Detection with Provable Bound on Sub-Optimality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17475},
}
Figure