The Computational Complexity of Concise Hypersphere Classification

Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider

Abstract

Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data than real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists.

Introduction

In the quest for Explainable AI (XAI), researchers often look for simple geometric models that humans can easily visualize. One of the simplest is the hypersphere: a "bubble" in high-dimensional space that contains all "blue" (positive) data points while excluding all "red" (negative) ones.

If your data consists of real numbers, finding this sphere is computationally efficient—it can be solved quickly using standard linear programming. However, many real-world datasets, such as medical symptom lists or software feature flags, are binary (0s and 1s). Surprisingly, the binary version of this problem, Binary Hypersphere Classification (BHC), had remained largely unexplored until this study.

Problem Definition

The core challenge of BHC is to determine if a binary vector $\vec{c}$ and a radius $r$ exist such that the resulting hypersphere correctly separates two sets of binary vectors. The authors specifically focus on "concise" classifications. In a binary setting, a concise explanation is a sphere center with very few "1" coordinates. For instance, if a model identifies a disease based on only 3 specific symptoms (a concise center), it is far more interpretable than a model citing 50 different symptoms.

Formal definition of the Binary Hypersphere Classification (BHC) problem.

Methodology: Parameterized Complexity

To navigate the inherent difficulty of BHC, the authors use the lens of parameterized complexity. Instead of just asking if the problem is "hard" (NP-hard), they look at different "knobs" (parameters) of the data to see if fixing them makes the problem solvable in reasonable time. These parameters include:

  • $d$: The number of dimensions (features).
  • $econ$: The conciseness of the explanation (number of 1s in the center vector).
  • $dcon$: The conciseness of the input data (max number of 1s in any input vector).
  • $tw$: The treewidth of the data's incidence graph, which measures how "interconnected" the features and data points are.

The Complexity Landscape

The study reveals a nuanced landscape of complexity, showing that the difficulty of BHC is highly sensitive to the interaction between these parameters. The results are summarized in the table below:

The complexity landscape of BHC across various structural and conciseness parameters.

Key Insights

  • The Binary Gap: The jump from real-valued to binary data fundamentally changes the problem's nature. While the real-valued version is "smooth" and easy for solvers, the binary version is discrete and combinatorial, leading to NP-hardness even in very simple cases (e.g., having only two red vectors).
  • The "3 vs 4" Threshold: One of the most striking findings is a phase transition in data conciseness ($dcon$). If every data point has at most 3 ones, the problem is solvable in polynomial time. As soon as you allow 4 ones, it becomes NP-hard.
  • Conciseness isn't enough: Simply wanting a short explanation ($econ$) isn't enough to make the problem easy. The authors prove that finding a concise center is W[2]-hard, meaning it's likely impossible to find an algorithm that scales efficiently with the length of the explanation alone.
  • Treewidth as a Savior: The authors show that if the data has a "well-structured" layout (low treewidth), the problem becomes much more manageable, even with complex constraints.

Conclusion and Future Work

This research provides the first comprehensive map of the computational complexity of BHC. By identifying the boundaries between tractability (Fixed-Parameter Tractability) and intractability, it sets a foundation for developing practical XAI tools.

The authors identify one specific "missing link" in their map: while they proved that BHC is XP-tractable for treewidth (meaning it's solvable in polynomial time for any fixed treewidth), they don't yet know if it is FPT for treewidth alone. This remains an open question for future research. Additionally, while this paper focuses on exact solutions, future work could explore approximation algorithms for cases where an exact concise hypersphere doesn't exist.

Summary updated

BibTeX
@inproceedings{eiben2023computational,
  author = {Eduard Eiben and Robert Ganian and Iyad Kanj and Sebastian Ordyniak and Stefan Szeider},
  title = {{The Computational Complexity of Concise Hypersphere Classification}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=1Ntj4pRk7E},
}
Figure