Source-linked AI summary
QGB-W$k$NN: Quantum Granular-Ball Learning for Robust Classification
Suzhen Yuan, Dehang Chen, Lifeng Shen, Shuyin Xia, Jeremiah D. Deng
TL;DR
Conventional nearest-neighbor classification faces costly retrieval and noise-sensitive decisions, while reliable decision-making remains less explored in quantum nearest-neighbor approaches. QGB-WkNN combines quantum granular-ball representation with purity-guided HNSW navigation and weighted voting. On benchmark datasets, it achieves competitive accuracy, improved robustness under Gaussian noise, and enhanced performance–cost trade-offs.
Problem
Conventional k-NN requires full training-sample traversal and uniform voting is noise-sensitive; reliable decisions also remain underexplored in quantum nearest-neighbor approaches.
Source: §1 · pp. 1–2Method
QGB-WkNN combines quantum-kernel granular-ball representation, purity-guided HNSW graph navigation, and weighted voting that uses granular-ball similarity and purity.
Source: §1 · pp. 2–3, §2 · p. 3Results
Experiments on real-world and synthetic benchmarks show competitive classification accuracy, improved robustness under Gaussian noise, and enhanced trade-offs between classification performance and computational cost.
Source: §4 · p. 14Takeaways & Limitations
Under the quantum-kernel estimation model and M ≪ N granular balls, the method can reduce search from sample-level retrieval to granule-level graph search.
Source: §4 · p. 14The experiments use classical quantum-circuit simulation, so reported results do not reflect runtime performance on real quantum hardware.
Source: §4 · p. 14
Abstract
from arXiv · showhide
Nearest-neighbor classification is widely used in machine learning, yet existing methods often suffer from low computational efficiency and limited robustness in noisy environments. To jointly address these challenges, this paper proposes an efficient and reliable weighted $K$-nearest neighbor classification framework based on quantum granular balls, termed QGB-W$k$NN. The proposed framework improves computational efficiency by integrating quantum-enhanced granular-ball representation with hierarchical nearest-neighbor search, while enhancing classification reliability through a purity-aware weighted decision mechanism. Specifically, quantum-kernel granular balls are constructed to reduce retrieval redundancy and strengthen nonlinear feature representation under limited quantum resources. A granular-ball purity-guided HNSW optimization strategy is developed to exploit structural reliability for hierarchical graph construction during neighbor retrieval, alleviating the local optimality issue caused by conventional random layering. Finally, a weighted voting mechanism jointly incorporating granular-ball similarity and purity is introduced to produce more reliable classification decisions in noisy environments. Extensive experiments on benchmark datasets demonstrate that QGB-W$k$NN achieves competitive classification accuracy while exhibiting favorable Pareto trade-offs between classification performance and computational cost. Moreover, the proposed framework consistently improves robustness under various noisy conditions, suggesting that reliability-aware quantum granular-ball learning provides a promising paradigm for efficient and robust nearest-neighbor classification.
1. Introduction
Conventional nearest-neighbor methods face both costly retrieval and noise-sensitive decisions, while existing quantum and granular-ball approaches leave reliability and efficiency challenges unresolved. QGB-WkNN brings quantum granular-ball representation, purity-guided graph navigation, and reliability-aware voting into one framework.
1. Introduction
- Full traversal makes conventional k-NN computationally inefficient, while uniform voting is vulnerable to noise.These limitations restrict its applicability in complex real-world tasks.Source: §1 · p. 1
- Graph-based ANN, including HNSW, supports efficient retrieval, but existing methods retain sample-level search overhead on large datasets.HNSW builds multilayer navigable topologies; other graph-index approaches also retain fine-grained retrieval.Source: §1 · pp. 1–2
- Granular-ball methods reduce retrieval redundancy, but classical distance metrics limit nonlinear representation and their decisions remain insufficiently robust to noise.Existing quantum granular-learning methods also cannot jointly optimize retrieval efficiency, nonlinear feature extraction, and noise robustness under limited qubit resources.Source: §1 · p. 2
- Efficient retrieval alone does not ensure reliable classification: noisy neighbors can destabilize predictions even when retrieval accuracy is high.The paper motivates granular-ball purity as structural confidence to incorporate into graph navigation and decisions.Source: §1 · p. 2
- QGB-WkNN combines quantum-enhanced granular-ball representation, purity-guided HNSW organization, and purity-aware weighted classification.The graph strategy addresses local optimality from conventional random layering, while the decision mechanism jointly considers neighborhood similarity and structural reliability.Source: §1 · pp. 2–3
2. Methodology
QGB-WkNN combines granular-ball compression, purity-aware HNSW navigation, and weighted voting to address retrieval redundancy, nonlinear similarity representation, and decision reliability.
2. Methodology
- The framework has three coupled components: quantum-kernel granular-ball representation, purity-guided HNSW navigation, and reliability-aware weighted decisions.They compress samples using quantum-kernel similarity, organize the graph by granular-ball purity, and fuse purity with similarity for voting.Source: §2 · p. 3
- Quantum-kernel similarity compresses raw samples into representative granular balls.This component targets sample-level retrieval redundancy and enhances nonlinear similarity representation.Source: §2 · p. 3
- Granular-ball purity guides HNSW graph organization, while purity and similarity jointly inform robust weighted voting.Source: §2 · p. 3
2.1. Reliability-Preserving Quantum Granular-ball Representation
The representation procedure groups samples using quantum-kernel similarity, then applies purity checks to form granular balls. Quantum encoding, fidelity measurement, threshold comparison, and iterative assignment implement this process.
2.1. Reliability-Preserving Quantum Granular-ball Representation
- Quantum-kernel similarity is used to group samples around seed points, and the resulting sets are checked against a purity threshold to form granular balls.Sets below the threshold are split into class-specific sub-balls; the generation procedure removes assigned samples and repeats until none remain.Source: §2.1 · pp. 3–4, §2.1.4 · p. 5
2.1.1. Quantum Encoding Preprocessing
- LDA reduces dimensionality, then MinMax normalization maps features to [0, π] for angle encoding into quantum states.Source: §2.1.1 · p. 4
2.1.2. Fidelity Calculation
- The fidelity circuit estimates quantum-kernel similarity as the probability of measuring the all-zero state after encoding one sample and applying the inverse encoding for the other.The resulting similarity ranges from 0 to 1, with values closer to 1 indicating greater similarity.Source: §2.1.2 · p. 4
2.1.3. Quantum Comparator
- A quantum comparator converts similarity and its threshold to matching t-bit encodings and outputs whether similarity meets the threshold.Measurement outcomes are counted to select eligible candidate samples.Source: §2.1.3 · pp. 4–5
2.1.4. Iterative Update
- After each ball is generated, its samples are removed from the remaining set, and generation repeats until all samples are assigned.The ball records its center, radius, purity, and category.Source: §2.1.4 · p. 5
2.2. Reliability-Guided Graph Navigation
The method replaces purely random HNSW level assignment with a purity-guided strategy intended to reflect the reliability and distribution of granular-ball regions. It also reuses purity information to avoid additional density-estimation overhead.
2.2. Reliability-Guided Graph Navigation
- Random HNSW levels ignore regional data distribution, causing redundant assignments in dense regions, sparse cross-region connections, and local optima.Source: §2.2 · p. 5
- Purity dynamically adjusts layer assignment: high-purity nodes receive fewer layers, while low-purity nodes receive more for longer-range connections.The strategy treats purity as a structural-reliability indicator for homogeneous versus ambiguous regions.Source: §2.2 · pp. 5–6
- Using granular-ball purity for density measurement adds no computational overhead and avoids the O(n^2) complexity of distance-matrix density estimation.Source: §2.2 · p. 6
- The final layer count is capped at log M.Source: §2.2 · p. 6
2.3. Reliability-Aware Decision Learning
QGB-WkNN replaces single-granularity or equal-weight decisions with voting weighted by granular-ball reliability and query similarity. It selects the class with the greatest accumulated weight, using ball purity to break ties.
2.3. Reliability-Aware Decision Learning
- The method addresses the limited noisy-scenario robustness of single-granularity decisions and equal-weight voting with a weighted classification mechanism.The paper describes granular-ball purity and similarity as inputs to the comprehensive weight.Source: §2.3 · pp. 6–7
- Each granular ball’s comprehensive weight combines its purity, normalized similarity to the query, and an adjustable coefficient.Purity measures within-ball class consistency; the coefficient controls how strongly purity amplifies the weight.Source: §2.3 · p. 7
- Raw similarity is calculated from the query’s distance to a ball center, with a small epsilon preventing a zero denominator.The similarity values are normalized to eliminate scale differences across test samples.Source: §2.3 · p. 7
- The classifier sums weights by each ball’s dominant class and predicts the class with the highest total score.If classes tie, it selects the class of the ball with the highest purity.Source: §2.3 · p. 7
2.4. Theoretical Analysis
The theoretical analysis describes construction and search costs under a quantum-kernel estimation model. Its empirical runtimes come from classical simulation and do not represent quantum-hardware acceleration.
2.4. Theoretical Analysis
- The analysis is framed under a quantum-kernel estimation model, but classical-simulation runtimes do not measure actual quantum-hardware acceleration.This qualifies what the empirical runtime can establish about acceleration.Source: §2.4 · p. 7
2.4.1. Construction Phase
- Construction comprises quantum encoding preprocessing, iterative quantum granular-ball generation, and HNSW construction.Preprocessing applies LDA dimensionality reduction, normalization, and quantum state encoding; LDA maps d-dimensional samples to n_q dimensions, with n_q much smaller than d.Source: §2.4.1 · p. 7
- Each granular-ball generation iteration calculates similarities to remaining samples and compares them with a threshold; splitting low-purity balls does not change the stated asymptotic order.The similarity comparisons scale with the number of remaining samples in that iteration.Source: §2.4.1 · p. 8
- HNSW construction inserts granular-ball centers using a constant number of candidate nodes per layer, and its hierarchical traversal overhead is O(M log M).The overall construction complexity integrates the preprocessing, granular-ball generation, and HNSW construction costs.Source: §2.4.1 · p. 8
2.4.2. Search Phase
- Search processes the query with LDA and normalization, then uses HNSW to retrieve the k nearest granular-ball centers.The query projection’s dominant preprocessing term is O(d·n_q); distance calculations during traversal use the n_q-dimensional quantum feature space.Source: §2.4.2 · p. 8
- The retrieved balls are classified by weighted voting based on each ball’s purity and similarity to the query.The stated search-cost expression is simplified under the conditions that k is a small constant and M is typically much smaller than N.Source: §2.4.2 · pp. 8–9
3. Experiments
The experiments evaluate QGB-W𝑘NN on real-world and synthetic datasets against representative conventional, granular-ball, prototype, graph-search, and quantum classifiers. They use shared train/test sets and report results under specified settings, while noting that quantum operations are simulated classically.
3.1.1. Data Preparation
- Eight public real-world datasets spanning several domains and two synthetic datasets were evaluated; missing values were column-mean imputed and categorical features one-hot encoded.Unknown categories were ignored during encoding.Source: §3.1.1 · p. 9
3.1.2. Compared Algorithms
- The comparison covers kNN, GB𝑘NN++ [10], GLVQ, HNSW, and QSVC, with all methods using the same train/test sets.These represent conventional nearest-neighbor, granular-ball, prototype-based, graph-based, and quantum classifiers, respectively.Source: §3.1.2 · pp. 9–10
3.1.3. Parameter Settings
- Experiments used a purity threshold of 0.8, initial similarity of 0.3, and HNSW with L2 distance, 8-neighbor graph construction, and α=2.2.Quantum circuits ran on a classical simulator, so reported efficiency does not include actual quantum speedup; each experiment was repeated three times with seed 42 and averaged.Source: §3.1.3 · p. 10
3.2. Results
QGB-W𝑘NN performs best or competitively on several complex datasets and offers a favorable accuracy-cost balance, while maintaining competitive performance under Gaussian noise. Sensitivity tests identify settings where performance stabilizes and motivate the chosen thresholds.
3.2.1. Effectiveness
- QGB-W𝑘NN achieves the best or highly competitive accuracy and Macro-F1 on several real-world datasets, especially 20 Newsgroups and Splice, but not uniformly across datasets.On simpler, highly separable datasets such as Mushrooms, classical baselines can approach perfect performance, leaving limited room for improvement.Source: §3.2.1 · p. 10, Table 5 · p. 11
3.2.2. Pareto Trade-off
- On 20newsgroups and Ionosphere, QGB-W𝑘NN offers a favorable trade-off between classification accuracy and computational overhead during construction and inference.The figures omit baselines that are dominated by other methods.Source: §3.2.2 · p. 11, Figure 4 · p. 11, Figure 5 · p. 12
3.2.3. Robustness
- Across different Gaussian-noise levels, QGB-W𝑘NN maintains competitive accuracy and Macro-F1, with the authors attributing improved robustness to reliability-aware voting.Tables 6 and 7 report results at noise ratios 0.2 and 0.4.Source: §3.2.3 · p. 11, Table 6 · p. 12, Table 7 · p. 12
3.2.4. Parameter Sensitivity Analysis
- Performance stabilizes for purity threshold T≥0.8, while increasing similarity threshold Ts degrades results; the best overall performance occurs at Ts=0.3.The authors set T=0.8 and Ts=0.3; they report limited gains above T=0.7 and a trade-off between sample retention and screening at Ts=0.3.Source: §3.2.4 · pp. 12–13, Figure 6 · p. 13
3.3. Ablation Study
The ablation results distinguish the roles of weighted voting and purity-guided HNSW assignment, and report that the full framework has a more stable overall balance across accuracy, Macro-F1, search efficiency, and noise robustness.
3.3. Ablation Study
- The ablation variants were Basic, standard HNSW without modifications; P-𝑘NN, without weighted classification; and W-𝑘NN, without purity-guided HNSW layer assignment.Detailed results are reported in Tables 8 and 9.Source: §3.3 · p. 13
- Weighted voting mainly improves robustness by reducing the influence of low-purity or weakly related granular balls, while purity-guided HNSW assignment affects graph organization and the efficiency-robustness trade-off.The variants were tested on multiple datasets under different noise ratios.Source: §3.3 · p. 13
- The full QGB-W𝑘NN framework provides a more stable overall balance across accuracy, Macro-F1, search efficiency, and noise robustness.A single module may achieve slightly higher accuracy on particular datasets, whose distributions and noise patterns differ.Source: §3.3 · pp. 13–14, Table 8 · p. 14
4. Conclusion and Limitations
QGB-WkNN shifts sample-level classification to quantum-enhanced, structure-aware granule-level learning, using purity in graph assignment and weighted voting. It reports competitive accuracy, Gaussian-noise robustness, and efficiency–accuracy trade-offs, but its experiments use classical quantum-circuit simulation.
4. Conclusion and Limitations
- Purity guides HNSW layer assignment and joins granular-ball similarity in weighted voting, making decisions less sensitive to noisy or ambiguous neighboring granules.The framework reformulates sample-level kNN as quantum-enhanced, structure-aware granule-level learning.Source: §4 · p. 14
- QGB-WkNN achieves competitive classification accuracy, improved robustness under Gaussian noise, and enhanced efficiency–accuracy trade-offs on real-world and synthetic benchmarks.Ablations indicate that purity-guided graph navigation and reliability-aware voting contribute to robustness and the efficiency–accuracy balance from different perspectives.Source: §4 · p. 14
- Under quantum-kernel estimation with M≪N granular balls, analysis indicates that search burden can shift from sample-level retrieval to granule-level graph search.Source: §4 · p. 14
- Experiments use classical quantum-circuit simulation, so reported results do not establish runtime performance on real quantum hardware.Validation on practical quantum devices under realistic noise conditions is future work.Source: §4 · p. 14
CRediT authorship contribution statement
The statement credits Yuan with review, formal analysis, and conceptualization; Chen with the original draft, methodology, and data curation; and the other listed authors with supervisory or review contributions.
CRediT authorship contribution statement
- Yuan is credited with review, formal analysis, and conceptualization; Chen with the original draft, methodology, and data curation; Shen, Xia, and Deng with supervisory roles.Shen and Deng are also credited with review and editing; Deng with writing and review, and Xia with supervision.Source: CRediT authorship contribution statement · p. 15