Research map / Graph learning / Graph algorithms and clustering
Instance Correlation Graph-based Naive Bayes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ICGNB, which builds an instance correlation graph from attributes, uses a VGAE to generate new attributes that augment the originals, then weights attributes via CLL-optimized gradient descent and builds Gaussian NB on them.
Problem
Naive Bayes improvements have mostly targeted nominal attributes and individual instances, leaving numerical attributes (beyond GNB) and correlations among instances largely unexplored.
Approach
Construct a sparse instance correlation graph (minimum spanning tree-like over Euclidean distances), use a VGAE with a Gaussian-mixture prior to generate new attributes that are approximately Gaussian and independent, augment original attributes with them, and weight all attributes by maximizing conditional log-likelihood before building attribute-weighted GNB.
Key results
- ICGNB average accuracy 78.87% over 24 datasets vs. WANBIA 77.84%, AG-NBC 77.67%, AE-NBC 75.92%, CFWNB 73.03%, GNB 71.84%.
- ICGNB wins on 20 of 24 datasets against GNB and 17 against WANBIA (loses on 7).
- Ablation: attribute augmentation, generation, and weighting each raise average accuracy over GNB (72.44%, 73.70%, 77.84% for ICGNB-N, ICGNB-A, ICGNB-W respectively).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add instance-correlation graph-derived attributes and weight augmented attributes | ICGNB vs GNB · 24 real-world datasets (average) | accuracy (%): 71.84 -> 78.87 | Helped |
| add instance-correlation graph-derived attributes and weighting | ICGNB vs WANBIA · 24 real-world datasets | accuracy (%) | Helped |
| add instance-correlation graph-derived attributes and weighting | ICGNB vs CFWNB · 24 real-world datasets | accuracy (%) | Helped |
| add instance-correlation graph-derived attributes and weighting | ICGNB vs AG-NBC · 24 real-world datasets | accuracy (%) | Helped |
| add instance-correlation graph-derived attributes and weighting | ICGNB vs AE-NBC · 24 real-world datasets | accuracy (%) | Helped |
| remove attribute augmentation and weighting; retain attribute generation (ablation) | ICGNB · 24 real-world datasets (average) | accuracy (%): 78.87 -> 72.44 | Hurt |
| remove attribute weighting (ablation) | ICGNB · 24 real-world datasets (average) | accuracy (%): 78.87 -> 73.70 | Hurt |
| remove attribute generation and augmentation; use WANBIA weighting (ablation) | ICGNB · 24 real-world datasets (average) | accuracy (%): 78.87 -> 77.84 | Hurt |
| replace VGAE graph convolution with GraphSAGE (ablation) | ICGNB · synthetic dataset | accuracy (%): 77.50% -> 78.00% | Helped |
| replace VGAE graph convolution with GAT (ablation) | ICGNB · synthetic dataset | accuracy (%): 77.50% -> 76.50% | Hurt |
Surprising findings
- Ablation ICGNB-W (WANBIA-style weighting alone) reaches 77.84%, close to full ICGNB at 78.87%, suggesting weighting contributes much of the gain.
Limitations
- ICG is constructed without class labels, omitting supervised information.
- Greedy ICG construction increases computational cost.
- Evaluated only on 24 KEEL datasets with numerical attributes and one synthetic dataset.
Experimental setup
Datasets: KEEL 24 numerical-attribute classification datasets synthetic dataset (2 classes, 100 instances, 50 attributes)
Benchmarks: KEEL 24 datasets
Metrics: classification accuracy Wilcoxon signed-ranks test win/tie/loss
Baselines: WANBIA CFWNB AG-NBC AE-NBC GNB
Builds on: naive Bayes variational graph auto-encoder WANBIA CFWNB
Closest papers by meaning
- Structured Features in Naive Bayes Classification (AAAI 2016 · similarity 0.81)
- SEC: More Accurate Clustering Algorithm via Structural Entropy (AAAI 2024 · similarity 0.78)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.78)
- Disentangling Tabular Data Towards Better One-Class Anomaly Detection (AAAI 2025 · similarity 0.78)
- RDB2G-Bench: A Comprehensive Benchmark for Automatic Graph Modeling of Relational Databases (NeurIPS 2025 · similarity 0.77)
- DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization (AAAI 2024 · similarity 0.77)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.