Instance Correlation Graph-based Naive Bayes
Authors: Chengyuan Li
Liangxiao Jiang
Wenjun Zhang
Liangjun Yu
Huan Zhang
Venue: ICML 2025 spotlightposter (2025)
Keywords: Naive Bayes
Numerical attribute
Instance correlation graph
Variational graph auto-encoder
Primary area: general_machine_learning->supervised_learning
TL;DR: A novel instance correlation graph-based naive Bayes (ICGNB) algorithm is proposed.

Abstract: Due to its simplicity, effectiveness and robustness, naive Bayes (NB) has continued to be one of the top 10 data mining algorithms. To improve its performance, a large number of improved algorithms have been proposed in the last few decades. However, in addition to Gaussian naive Bayes (GNB), there is little work on numerical attributes. At the same time,  none of them takes into account the correlations among instances. To fill this gap, we propose a novel algorithm called instance correlation graph-based naive Bayes (ICGNB). Specifically, it first uses original attributes to construct an instance correlation graph (ICG) to represent the correlations among instances. Then, it employs a variational graph auto-encoder (VGAE) to generate new attributes from the constructed ICG and uses them to augment original attributes.
Finally, it weights each augmented attribute to alleviate the attribute redundancy and builds GNB on the weighted attributes. The experimental results on tens of datasets show that ICGNB significantly outperforms its deserved competitors.Our codes and datasets are available at https://github.com/jiangliangxiao/ICGNB.

Due to its simplicity, effectiveness and robustness, naive Bayes (NB) has continued to be one of the top 10 data mining algorithms. To improve its per- formance, a large number of improved algorithms have been proposed in the last few decades. How- ever, in addition Gaussian naive Bayes (GNB), there is little work numerical attributes. At the same time, none of them takes into account the correlations among instances. To fill this gap, we propose novel algorithm called instance correla- tion graph-based naive Bayes (ICGNB). Specifi- cally, it first uses original attributes to construct an instance correlation graph (ICG) represent the correlations among instances. Then, it ploys variational graph auto-encoder (VGAE) to generate new attributes from the constructed ICG and uses them to augment original attributes. Finally, it weights each augmented attribute to alleviate the attribute redundancy and builds GNB on the weighted attributes. The experimental results on tens of datasets show that ICGNB significantly outperforms its deserved competi- tors. Our codes and datasets are available at Instance Correlation Graph-based Naive Bayes
Chengyuan Li'
Liangxiao Jiang'
Wenjun Zhang'
Liangjun Yu? Huan Zhang?
Abstract
attribute value vector < 01, 02 Ajy am. >, where
aj is the value of æ on Aj. Let C represeett the class variable and e represent the value that C' takes, Bayesian networks use Eq. (1) to classify æ:
ō(x) = arg maz T.P a2 aj. am amlc) (c),
(I)
cEC
where ((x) is the class label of æ predicted by Bayesian networks and Te is the prior probability of c. Because di- rectly estimating P(a1, 022,-.. aj...., am (c) is an NP-hard problem (Chickering, 1995), naive Bayes (NB) proposes an assumption that all attributes are fully independent given the class, i.c. attribute conditional independence assumption. Based on this assumption, NB uses Eq. (2) to classify
ē(x²) arg max Te
II 10,ler j=1
(2)
dEC
where 0agle is the conditional probability of aj given
Despite its simplicity, NB has demonstrated remarkable performance and continued to be one of the top 10 data mining algorithms (Wu et al., 2008). Nevertheless, the at- tribute conditional independence assumption is difficult to hold in reality, which limits the performance of NB. To mitigate the attribute conditional independence assump- tion, numerous improved algorithms of NB have been pro- posed, which can be broadly divided into four categories: structure-oriented probability-oriente. attribute-oriented and instance-oriented algorithms.
1. Introduction
Supervised classification is one of the most fundamental and significant tasks in data mining (Han et al., 2011). Due to the explicit interpretability and the powerful expression ability, Bayesian networks (Pearl, 1989; Friedman et al., 1997; Tang et al., 2016; Zhang et al., 2020a) are commonly used su- pervised classification. Assume that A1, A2, Aj:... Am are m attribute variables, an instance æ can be represented as
However, in addition Gaussian naive Bayes (GNB), there is little work numerical attributes. At the same time, none of them takes into account the correlations among instances. To address these issues, we propose novel algo- rithm called instance correlation braph-based naive Bayes (ICGNB). Firstly, we construct an instance correlation graph (ICG) using original attributes to represent the correlations among instances. Then, we employ a variational graph auto-encoder (VGAE) (Kipf & Welling, 2016) generate attributes from the constructed ICG and use them to augment original attributes. Finally, we weight each aug- mented attribute by maximizing the model's conditional logelikeli (CLL) to alleviate the attribute redundancy and then build GNB on the weighted attributes. summary, the contributions of this paper can be highlighted as:
'choool of Computer Science, China University of Geo- sciences, Wuhan 430074, China 'College of Computer, Hubei University of Education, Wuhan 430074, China 'Sehool of Com- puter Science and Artificial Intelligence, Zhengzhou University, Zhengzhou 450001, China. Correspondence to: Liangxiao Jiang <Ijiang @cug.ccuuuu edu.en>..
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Instance Correlation Graph-based Naive Bayes
We argue that the correlations among instances should be introduced to improve NB. In contrast to existing im- proved algorithms focusing on individual instances, we intend to mine additional information across instances.
Attribute-oriented algorithms handle attributes through dif- ferent strategies, which can be further divided into attribute selection, attribute weighting and attribute generation. In attribute selection (Hall, 2000; Tang et al., 2016; Chen et al., 2020), irrelevant and redundant attributes are removed from original attributes to obtain an optimal subset of attributes. Attribute selection includes filters and wrappers, which re- move attributes by employing general data characteristics and classification accuracies of NB, respectively. In at- tribute weighting (Zaidi et al., 2013; Jiang et al., 2019b; Zhang et al., 2020b), due to attributes holding different im- portance on classification, they should be assigned different weights based on their predictive abilities (Lee et al., 201 1). Evaluating the predictive ability of each attribute is the most crucial problem of attribute weighting. The same as at- tribute selection, attribute weighting also includes filters and wrappers. In attribute generation (Ou et al., 2022: He et al., 2023; Zhang et al., 2023), new attributes are generated by mapping original attributes to another attribute space, which can capture latent characteristics of the data. New attributes can enhance the identification abilitics of original attributes by replacing, augmenting or acting as a new view.
We develop novel instance correlation graph (ICG)- based representation learning method, which exploits the correlations among instances to generate new at- tributes and thus enhances the identification abilities of the original attributes.
We propose an instance correlation graph-based naive Bayes (ICGNB) algorithm, which enjoys the advan- tages of attribute generation, attribute augmentation and attribute weighting and thus provides a new path- way to improve NB.
The rest of this paper is organized as follows: Section 2 conducts a survey on improved algorithms of NB. Section 3 describes the proposed ICGNB in detail. Section 4 reports the experiments and results. Section 5 concludes this paper and outlines the research directions for future work.
2. Related work
Instance-oriented algorithms can also be further divided into instance selection, instance weighting and instance genera- tion. In instance selection (Bilmes & Ng, 2009; Langley & Sage, 2013; Wang et al., 2015), a local subset of instances is selected to build NB. Considering that the attribute condi- tional independence assumption is difficult to satisfy on the entire training instances, however, it may hold by selecting a local subset of instances for a given test instance. In instance weighting (Jiang et al., 2012; 2014; Xu et al., 2019), each instance is assigned a numerical weight between 0 and I based on its reliability. Then the weight of each instance is incorporated into the formulae of the prior and conditional probabilities to get a more accurate probability estimation. In instance generation (Jiang et al., 2005; Jiang & Zhang, 2005; Jiang al., 2008), new instances are generated based the original instances and added to the dataset. The in- stance distribution of the data is optimized by using new instances and original instances simultancously.
In recent years, numerous improved algorithms of NB have been proposed, which can be broadly divided into four cat- egories: structure-oriented, probability attribute- oriented and instance-oriented algorithms.
Structure-oriented algorithms (Webb et al., 2005; Jiang et al., 2009; Qiu et al., 2015) improve NB by extending its net- work structure. Specifically, the original network structure lacks edge connections among attribute vertices, which re- stricts the ability of NB to represent attribute dependen- cies. To overcome this limitation, structure-orientee algo- rithms extend the network structure by adding directed arcs, which point from the parent vertices to the child vertices to represent attribute dependencies. Distinguished from NB, where the conditional probabilities are calculated given the class vertex, in cructure-orreeted algorithms, the con- ditional probabilities of each attribute are calculated given both the class vertex and its parent vertices.
To the best of our knowledge, except for two attribute- oriented algorithms (Ou et al., 2022; He et al., 2023), al- most all above improved algorithms focus on nominal at- tributes. Moreover, all of these improved algorithms con- sider individual instances solely and ignore the correlations among instances. These limitations motivate us to propose more comprehensive algorithm that can handle numerical attributes and leverage the correlations among instances.
Probability- rroiabilit--oriented oriented algorithms (Hindi, 2014; Diab & Hindi, 2017; Hindi et al., 2020; Zhang& & Jiang, 2022) provide a strategy to obtain more reliable conditional probabilities than those estimated by NB. In NB, conditional probabili- ties are roughly estimated based on frequencies, however, they might be unreliable when dataset is too small or the attribute conditional independence assumption is violated. probability-oorinte algorithms adjust them to be more reli- able conditional probabilities by employing eager and lazy learning. Eager learning spends the main calculating cost in the training stage, while lazy learning spends the main calculating cost in the classification stage.
3. ICGNB
To address the limitations mentioned above, first develop novel ICG-based representation learning method. In our
2

---

Instance Correlation Graph-based Naive Bayes
Stage ICG Construction
Stage Attribute Generation and Augmentation
Stage Attribute Weighting
CLI
Zm
M
Gradient Descent Search
Fii
Construct
Cancationtt
1
%
..e
d
Weight
Build
Original Amribte Matrix
ICG
New Attribute Mairix
Augmentad Attribute Manrix
VGAB
Amribut Weighted GNB
Figure Framework ICGNB.
method, we construct an ICG to represent the correlations among instances and transform the correlations into new
Algorithm ICGGconstruuttion(X
Input: X the original attribute matrix.
attributes to augment original attributes. Based on the de- veloped representation learning method, we further propose
2: Output: F. the set of edges in ICG.
3: Construct a full connection graph of instances and store its
novel algorithm called instance correlation graph-based maive Bayes (ICGNB). The framework of ICGNB is graphed in Figure 1. From Figure 1, we can see clearly that ICGNB is a three-stage algorithm. In the first stage, we mine the cor- relations among instances from the original attribute matrix and construct an ICG to represent the correlations. In the second stage, we input ICG and the original attribute matrix into VGAE generate new attribute matrix and augment the original attribute matrix by it. In the third stage, max- imize the CLL by the gradient descent search to optimize the weight vector and finally build attribute weighted GNB
edges in Fi;;
4: for i 1 r:
5: for [= to vz
6:
Calculate d(x;; as)) between æ, and wy by Eq. (3);
7: end for
8: end for
9: Sort edges EP by Euclidean distances in ascending order;
10: Initialize an empty set E;
11: for = to n(n 1)/2
12: if two vertices connected by the i-th edge in Ep are not
reachable through the edges in then Add the the i-th edge in Ep E: E' contains r--1 edges then Break;
13:
14:
15:
on augmented attributes.
16: end if
17: end
3.1. ICG construction
18: end for
19: for i= 1 to do
In this subsection, we construct ICG to connect all instances
20: Add self-connecting edge for the i-th vertex to E;
into a complete structure and represent the correlations as an undirected graph. ICG presents a topological structure of the data, connecting instances with high correlations while separating those with low correlations. In ICG, to avoid containing redundant correlations, we construct it sparse graph. Under the condition that all instances should be connected into a complete structure, we add as few edges as possible to ICG.
21: end for
22: return E.
Firstly, we construct a full connection graph of instances and store its edges in Ep. Then, we calculate the distances between instances two by two and sort edges in Ep by the distances ascending order. In this paper, we take advantage of the widely used Euclidean distance to measure the distance d(æ;, xx) between two instances æ, and æ., which can be formulated as Eq. (3):
Given a dataset with n instances and m attributes, can be represented as {X, c). where X Raxm is the original attribute matrix, is the class label vector. The i-th row in X is represented as 2;, corresponding to the i-th instance. The ICG is represented as O =< V, E >, where V is the set of vertices, and E is the set of edges. Each vertex in ICG represents an instance, and each edge represents a connection between two instances. In addition, we define Er as the set of edges in a full connection graph of instances, which contains n(n - 1)/2 edges. The ICG is constructed using original attributes, and the construction (ICG-construction) process is depicted by Algorithm 1.
d(æ,, (:) =
(an 0zj)2
where a, and ay the j-th attribute values of æ; and wt, respectively. Next, we process each edge in Ep iteratively, checking whether the two vertices connected by it are reach- able through the edges in E. If not reachable, the edge is added to E. This process continues until exactly n- edges have been added. Finally, we add self-connecting edge
3

---

Instance Correlation Graph-based Naive Bayes
for each vertex to consider the correlation between each instance and itself. After constructing ICG, we transform O into an adjacency matrix G. The element of G in the i-th row and the j-th column is represented as Gty, which takes the value 1 if there is an edge between the i-th vertex and the j-th vertex and 0 otherwise.
distributions, respectively. 14, T and σ are inferred by the graph convolution operation. Formally, the graph convo- lution operation from the r-th layer to the (r+1)-th layer in VGAE can be represented as Eq. (6):
H = 8(D GD H'""".
(6)
where 8(-) is a RELU function, D is the degree matrix of G. D2 = Σÿ= Gij. W is the weight matrix in the r-th layer, H" is the activation matrix in the r-th layer, H X. The inference of means and variances can be represented as Eq. (7) and Eq. (8), respectively:
3.2. Attribute generation and augmentation
In this subsection, to fully leverage the correlations among instances and mine additional information across instances, we take an embedding matrix generated from ICG as the new attribute matrix for instances. During the generation of the embedding matrix, the graph convolution operation in VGAE plays crucial role, which calculates the response of a vertex based on its neighbors through Fourier trans- form & Welling, 2017). Through the graph convo- lution operation, we encode the correlations among each instance and its neighbors into the embedding matrix.
1 DD D HW
(7)
p
o = D GD 1 HW..
(8)
where W F and W. are the weight matrices corresponding to the mean and variance, respectively. After inferring Z, the decoder p(G Z) is employed to reconstruct the original adjacency matrix G from Z through adopting the inner product by Eq. (9):
In VGAE, the embedding matrix Z consists of embedding vectors, and the i-th row in Z is the i-th embedding vector z; Similar to the variational auto-encoder ( (VAE) (Kingma & Welling, 2014), VGAE contains an encoder gZ|| G), a decoder p( Z) and a variational prior p( Z). Among them, the encoder q( X G) transforms X and G' into Z based on p( 2). The decoder Z) reconstructs G from Z. According to the mean field theory (Blei et al., 2016), p(Z) can be expressed by several mutually independent components, Specifically, treating the embedding vectors as the independent components, the process of generating Z through (Z X G¹ can be represented as Eq. (4):
p Z)
((=T21) i=1==1
(9)
where ((-) is a sigmoid function. g G) and p are trained simultaneously by maximizing the evidence lower bound (ELBO), which can be formulated as Eq. (10);
L C C=Enztx.cc|lbbpp(GG -KL (XX] Z)),
(10)
q (Z II M(z.)),)
(4)
where
is the expectation of
the binary cross entropy loss between the original adjacency matrix and the reconstructed matrix, and K LL ( G)Ilp(() is the Kullback-Leible divergence between q( (Z| G) and variational prior (Z).
where ((z is the vector prior of z; oi is the parame- ter set of ((z.) For each embedding vector, we design a mixture of two multivariate Gaussian distributions with di- agonal covariance as the vector prior (Blundell et al., 2015). The two multivariate Gaussian distributions have the same means but different variances, and the vector prior can be represented as Eq. (5):
To make new attributes align with the attribute conditional independence assumption and the Gaussian distribution re- quired by GNB, we set the variational prior p( (Z) as an independent zero-mean Gaussian distribution with unit vari- ances. VGAE ensures that the distribution of the embedding matrix closely approximates p( Z). Each variate in P( corresponds to a new attribute in Z, and thus the new at- tribute closely approximates the Gaussian distribution. The independent zero-mean in p( Z)) ensures that the covariance matrix of pl Z) is a diagonal matrix, implying that covari- ances between new attributes approximate zero, i.e., new attributes are approximately independent of each other.
()))())) -M(zi oii 0
(5)
= -1 diag(oid)) + (( diag ())
where μi is the mean vector, of and oi are the variance vectors, ( and ( are the diagonal covari- ance matrices. The variances of the first multivariate Gaus- sian distribution are configured to be considerably larger than those of the second, i.e. of >> o²2- of, and 02 increase the diversity of the vector prior by providing a heav- ier tail and a higher peak in the two multivariate Gaussian
Based on L. we update the parameters W of VGAE over P iterations by Eq. (11):
Wp+1 = Wp- ''w'
(11)
4

---

Instance Correlation Graph-based Naive Bayes
where Wp represents the parameters in the p-th iteration and n represents the learning rate. When p 1, Wp represents randomly initialized parameters.
where Yew; (w) is the product of me and each 0t of 26 which can be formulated as Eq. (17):
ayle
2m
Finally, after generating Z, to enhance the identification abilities of original attributes, we augment original attributes by concatenating Z with X. In this paper, we construct a VGAE consisting of three layers of neurons, with the num- ber of neurons in each layer being m, 2m and m, respectively. Therefore, total of m new attributes are added. For each instance, we represent the j-th value of z; as zij and define 2g as the (m + f)-th attribute value of x;,
Ycæ; (w) = Te
(17)
ayle
j=1
Before calculating the gradient of CLL(w) with respect to Wj we can first calculate the gradient of Yem, (w) with respect to wy as Eq. (18):
2
a g Owy asle
Ow, Yea, (w) = Te
gh agrle
J' J'=1N'' #)
3.3. Attribute weighting
2m
mn 0,ylo
0w' a,lc log log(Oayle)
Although attribute augmentation enhances the identification abilities of original attributes, it may lead to redundant at- tributes. To alleviate the attribute redundancy, we can assign different weights for different augmented attributes. Then, we build attribute weighted GNB based on the weighted attributes and use Eq. (12) predict the class label:
Tee
= Yon, (w) log (0a((0,)) (0),
(18)
Then, the gradient of CLL(w) with respect to wy can be represented as Eq. (19):
201
i CLL(W)
a(x) = arg max TTc
II 0
agle
(12)
Dwy
GEC
3=1
0
h
where wy is the weight of Aj. Te and Oay e are estimated by Eq. (13) and Eq. (14), respectively:
Σ
log (Yerar (w)) log
Σ
Year (w))
ow
i=1
E [cc,, +1
Σ Vea; (w) log(Oay)e (aayle)
ne
(13)
Yecas (w) log log(Oa)1o2) (02))
nu + k
Yeree, (w)
(a; Mej)
Yax (w)
Oayic c
exp
(14)
V 2
20² ej
4:
where is the number of classes, n4 is the number of training instances, e; is the class label of the i-th instance, Mej and Jej are the mean and standard deviation of Aj given c, respectively, and I(.) is a binary function, which takes the value 1 if its two parameters are identical and otherwise.
log(Oayla))) -
Σ P(cla,, w) log log(Pagle)
(19)
ICGNB can be partitioned into training (ICGNB-trainiing and classification are depicted by Algorithms 2 and 3 provided in Appendix A. The time complexity is provided in Appendix B.
algorithms. They
Now, the only left question is how to calculate attribute weights. At first, we initialize each weight in the weight vector w using random value between 0 and 1. Then, we optimize the initialized weights by the gradient descent search. The objective function of optimization defined to maximize the CLL of the attribute weighted GNB, which can be formulated as Eq. (15):
4. Experiments and results
We design two groups of experiments 24 real-world datasets and synthetic dataset, respectively. On the real- world datasets, we observe the classification performance of ICGNB compared to its five competitors and conduct an ablation study. On the synthetic dataset, we validate the ef- fectiveness, independence and Gaussianity of the generated new attributes as well as the sensitivity of ICGNB.
The
CLL(w)= = log P(C)D w) Σ log P(c/kz w),
(15)
where D; is the training dataset, P(c æ., w) is the posterior probability of o; estimated by the weighted GNB given æ; and w, which can be formulated as Eq. (16):
4.1. Experiments on real-world datasets
From the real-world datasets published by the KEEI.' dataset repository, we choose the whole 24 datasets only
Necar, (w)
Plcla, w)
(16)
k
Σ
Yews (ww)
5

---

Instance Correlation Graph-based Naive Bayes
Table 1. Classification accuracy (%) comparisons for ICGNB WANBIA, CFWNB, AG-NRC, AE-NBC and GNB.
Dataset
ICGNB
WANBIA
CFWNB
AG-NBC
AF-NBC
GNB
appendicitis
89.0947.66
88. 18.1867.66
90.0026.03
83.6446.80
83.18=10.77
86.3626. 10
balance
88.00+3.12
90.24+2.84
88.32#3.87
91.68+1.53
79.84=5.22
90.24+2.84
banana
69.53+0.80
62.00=0.91
1..74=1.48
84.80+3.83
62.41=3.19
62.00+0.91
cleveland
57.67+4.84
58.00:4.27
54,83+4.86
53.67=3.88 86
55.50=7.82
51.67=10.22
ecoli
79.1245.46
79. 19.
60,29
70.00=6.35
78.53+2.81
60.7446.61
glass
63.02+8.85
59.07=7.44
51.40=11.7 1.74
60.70#6.61
60.47=8.06
47.2149.70
iris
96.33+3.14
96.00=3.27
95.33+3.71
90.33+6.90
91.00=7.31
95.33+3.71
led7digit-01
72.40s4.27
70.40=5.90
64.20=9.11
71.30+4.73
71.70#3.26
63.30#12.12
magic
78.38+0.78
77.05=00.67
74.5620.56
1..04
17.69=1.35
72.5620.64
movement_libra
36.11+4.31
62.92+4.97
62.22+4.76
69.17+6.77
70.97=6.38
61.94+5.63
phoneme
76.46+1.10
75.91=1.40
16.85+1.58
77.22+1.69
76.91
75.97+1.65
pima
75.3242.29
75.52+2.69
75.06+2.99
73.12+2.23
73.70=2.94
74.61+3.45
ring
97.98=0.36
97.90=0.20
97.96+0.30
13.
94.73=0.51
97.92+0.28
segment
90.41
88.81#1226
80.52+1.26
88.01=1.76
83.35+2.60
19.42+1.48
sonar
78.57+5.73
78.33
67.8645.46 466
76.67+7.81
67.15=8.05
66.6745.11
spambase
90.67+108
89.9921.08
1..71
86.52+1.83
86.51=0.98
82.08+1.25
texture
96.8420.52
84.47=1.00
1..
94.91=0.78
94.22=0.74
17.45+1.39
titanic
19.41
77.64#1.21
76.98=0.89
1.
76.98=0.89
76.98+0.89
twonorm
97.66+0.22
97.72+0.27
97.71
96.37=0.61
95.31=0.91
97.70+0.28
wdbc
96.32+1.51
96.40=1.54
93.95+1.90
94.65#1.
85.53+2.97
92.9842.29
wine
96.94+1.94
97.50=1.50
96.94+1.94
97.50=1.94
92.22+5.53
97.50+1.50
winequality-red
59.53+2.56
58.4441.78
58.47+1.49
58.8443.19
57.1642.93
54.72+2.56
winequality white
52.64+1.27
52.21=1.51
19.23#1.14
51.0211. 1.94
51,51+143
44.38+161
yeast
56.5343.26
54.28+3.20
18.22+3.83
50.03+3.07
55,4921.87
14.4143.38
(W/T/L)
17/0/7
18/1/5
19/0/5
22/0/2
20/0/4
Average
78.87
77.84
73.03
77.67
75.92
71.84
Table 2. Wilcoxon tests for ICGNB versus WANBIA, CFWNB, AG-NBC, AE-NBC and GNB.
Algorithm
ICGNB
WANBIA
CFWNB
AG-NBC
AE-NBC
GNB
ICGNB
WANBIA
O
CFWNB
D
AG-NBC
AE-NBC
GNB
containing numerical attributes, which represent a wide range of domains and data characteristics. The detailed de- scription of these datasets provided in Appendix C. In our experiments, apply z-score normalization (Patro & Sahu, 2015) to attributes before inputting them into algorithms. We compare the classification accuracy (%) of ICGNB with its five competitors and ablation variants on these datasets by running 10 separate stratified hold-out validations. In each validation, we use stratified sampling to split the dataset into training set (80%) and a testing set (20%).
NBC) (Ou et al., 2022) and GNB. WANBIA and CFWNB are two existing state-of-the-art improved algorithms of NB focusing on nominal attributes with attribute weighting. In experiments, to enable them to handle numeric attributes directly, we replace the NB in them with GNB. AG-NBC and AE-NBC are two existing state-of-the-arr improved algorithms of NB focusing on numerical attributes with at- tribute generation. Different from our proposed ICGNB, they generate independent attribute groups or attributes to align with the attribute conditional independence assump- tion. Among all competitors, GNB is the baseline. We implement ICGNB, WANBIA, CFWNB, AG-NBC, AE- NBC and GNB by using Python, respectively. In ICGNB, the number of iterations P is 500, the learning rate 7) is 0.01, and i 0 100002 In AE-NBC, the number of iterations and the learning rate are the same as those ICGNB. In AG-NBC, the stopping threshold is 0.001 and the regular-
Classification performance. We compare ICGNB with its five competitors, including weighting attributes to alle- viate naive Bayes' independence assumption (WANBIA) (Zaidi et al., 2013), correlation-based feature weighting fil- ter for naive Bayes (CFWNB) (Jiang et al., 2019a), attribute grouping-basee based naive Bayesian classifier (AG-NBC) (He al., 2023), auto-encoding naive Bayesian classifier (AE-
6

---

Instance Correlation Graph-based Naive Bayes
ization factors S1, 62 are -1, respectively.
78.87
Jocrace dhaditcaion acuee
77.84
Table I shows the detailed classification accuracy of each algorithm on each dataset. We bold the highest classifica- tion accuracy on each dataset to show the algorithm which performs best in that dataset. If two algorithms have the same accuracy on the same dataset, we bold the accuracy with a small variance. The Win / Tie/ / Lose values and the averages are summarized at the bottom of the table. The
76-
74-
73.70
12:44
72-
71.34
70
GNB
JCONB-X
ICGND-A
ICOND W
ICGND
Win / Tie Lose (W/ / LL)) values of each entry in the table provide concise summary of how ICGNB fares against its competitors. They imply that, compared to its competitors, ICGNB wins on W datasets, ties on T datasets, and loses on datasets. The average (arithmetic mean) of each algorithm across all datasets provides a gross indicator of the relative performance. Based on the classification accuracy results presented in Table 1, we employ the Wilcoxon signed-ranks test (Demsar, 2006) to conduct comprehensive comparison of each pair of algorithms. This non- parametrae statistical test ranks the differences in performance for each dataset, ignoring the signs, and compares the ranks for positive and negative differences. The comparison results are summa- rized in Table 2, where indicates that the algorithm in the column outperforms the one in the corresponding row, and signifies the opposite. The lower-diagonal significance level is a = 0.05, while the upper-diagonal level is a = 0.1. These results show that our proposed ICGNB significantly outperforms all the other competitors. Now, we summarize the highlights as follows:
Figure 2. Results of the ablation study.
(5) According to the Wilcoxon signed-ranks test results presented in Table 2, ICGNB significantly outperforms all existing state-of-the-art competitors whether a = 0.05 or a 0.1, which strongly validates the classification performance of ICGNB.
Ablation study. To thoroughly analyze whether each part in ICGNB takes effect, we conduct an ablation study about three ablation variants. They retain different parts in ICGNB to observe the effectiveness of specific parts. ICGNB-N is the first variant, in which the part of attribute generation is the same as that of ICGNB while attribute augmentation and weighting are removed. ICGNB-A is the second variant, in which the parts of attribute generation and augmentation are the same as those of ICGNB while attribute weight- ing is removed. In addition to ICGNB-N and ICGNB-A, WANBIA can serve as another ablation variant of ICGNB. We represent it as ICGNB-VV -W in which the part of attribute weighting is the same that of ICGNB while attribute gen- eration and augmentation are removed. According to the results shown in Figure 2, we summarize the conclusions as follows: (1) The accuracy of ICGNB-A is higher than that of GNB and ICGNB-N, which indicates that attribute aug- mentation necessary for leveraging original attributes and new attributes simultaneously. (2) The accuracy of ICGNB is higher than that of ICGNB-A, which proves that attribute weighting is necessary for alleviating the attribute redun- dancy. (3) The accuracy of ICGNB is also higher than that of ICGNB-W, which suggests that attribute generation and augmentation are necessary for enhancing the identification abilities of original attributes.
(1) Compared WANBIA and CFWNB, ICGNB wins on 17 and 18 datasets and only loses on 7 and datasets, respec- tively. ICGNB obtains much better performance than the existing state-of of-the-ar competitors with attribute weight- ing. This indicates the effectiveness of using new attributes containing the correlations among instances.
(2) Compared AG-NBC and AE-NBC, ICGNB wins on 19 and 22 datasets and loses on and 2 datasets, respectively. ICGNB performs much better than existing tftte-of-the-art competitors with attribute generation. This indicates the effectiveness of alleviating the attribute redundancy by as- signing different weights for different augmented attributes.
(3) Compared to GNB, ICGNB wins on 20 datasets and loses only on 4 datasets. This verifies that ICGNB demon- strates significant effectiveness in enhancing the perfor- mance of NB and our proposed ICG-based representation learning method is powerful.
4.2. Experiments on synthetic dataset
To further verify the effectiveness, independence and Gaus- sianity of the generated new attributes as well as the sensi- tivity of ICGNB, we design another group of experiments on a synthetic dataset. The synthetic dataset contains classes, 100 instances and 50 attributes. The synthesis pro- cess initially creates Gaussian clusters around the vertices of 40-dimensional hy hypercube and assigns an equal number of clusters to each class. By sampling from these clusters, in- stances containing 40 informative attributes can be obtained. Then, 10 redundant attributes are generated by random lin-
(4) The average classification accuracy of ICGNB on 24 datasets is 78.87%, which is remarkably higher than those of WANBIA (77.84%), CFWNB (73.03%), AG-NBC (77.67%), ), AB-NBC (75.9%% and GNB (71.84%) respec- tively. This proves that ICGNB is generally the best among all the competitors
7

---

Instance Correlation Graph-based Naive Bayes
0.5
origial attristes closs
0.4
odginal utribures dlss
0.3
new atinbutess class
Kolmngooon
(a) original attributes
(b) ICG
(c) new attributes
Artrbuuts (a) statistics
Figure 3. Class distributions synthetic dataset.
class
50
Numberr ansthrics
400
30-
20
14
31-
10
original attributes
artributes
(b) signi ficances
21
41
50
21
31
41
50
Figure 5. Gaussianity of attribute comparisons of the Kolmogorov- Smirnov tests.
(a) original attributes class
(b) original attributes
class 2
tively connects instances of the same class. This is helpful in representing the correlations among instances on original attributes. Figure 3c, instances of the same classes generally distributed within the same regions, and instances of different classes can be separated by a clear boundary, The class distribution with augmented attributes demon- strates significant distinguishability compared to that with original attributes in Figure 3a, in which instances of dif- ferent classes are scattered. This suggests that augmented attributes containing new attributes are more effective for classification than original attributes.
41-
21
21
50
41
(c) new attributes class
(d) new attributes class
Figure 4. Pearson coefficients between original attributes and new attributes in two classes.
Independence. To investigate whether new attributes align better with the attribute conditional independence assump- tion than original attributes, we calculate the absolute value of the Pearson coefficient (Cohen Israel, 2009) as the correlation between each pair of attributes given c. We plot the correlations heat maps, in which the lower correla- tions correspond to the lighter colors, shown in Figure 4. The elements the diagonal indicate the correlations of the attributes to themselves, which are excluded from our analysis and are set to the darkest color. Figure 4c and Fig- ure are much lighter in color than Figure 4a and Figure 4b, indicating that new attributes have lower correlations with each other given than original attributes. Therefore. attributes align better with the attribute conditional independence assumption than original attributes.
combinations of these informative attributes. To shift the distribution of each attribute away from the Gaussian distri- bution, attribute values are mapped by using the transform function as Eq. (20):
a' = sign((a)) a.s
(20)
where a' is the mapped attribute value, a, an original attribute value, sign(.) is a signed function taking 0, -1 if as zero, positive, negative, respectively.
Effectiveness. To facilitate clear observations of the class distributions of the synthetic dataset, employ the t-SNE algorithm (van der Maaten & Hinton, 2008) to map the syn- thetic dataset to a two-dimensional dataset. Figure shows the class distributions with original attributes, ICG and aug- mented attributes. For ICG, we hide the self celf-connecting edges of instances. In Figure 3b, we can see that ICG effec-
Gaussianity. We use the Colmogorov-Sminee test to in- vestigate whether new attributes conform to the Gaussian distribution required by GNB better than original attributes. The Kolmogorov-Sming Smirooy test can compare whether there
8

---

Instance Correlation Graph-based Naive Bayes
450
390
0.008
6012
78
78, 22.00
76.50
Neerage slastfuuttoo
75
74
72-
650
0.04
0015
VGAE
GlsphSAGE
GAI
6018
(a) Number of iterations
(b) Learning rate
Figure 7. Average classification accuracy (%) of ICGNB with dif- ferent graph convolution functions.
Figure 6. Average classification accuracy (%) of ICGNB with dif- ferent parameters.
demonstrates that ICGNB is not sensitive to P and r). In addition to changing the adjustable parameters, we replace the graph convolution function of VGAE in ICGNB with those of GraphSAGE (Hamilton et al., 2017) and Graph Attention Network (GAT) (Velickovic al., 2018), and then observe the classification performance. The detailed experi- mental results are shown in Figure 7. From Figure 7, we can see that the average classification accuracy corresponding to three graph convolution functions are 77.50%, 78.00% and 76.50% respectively. These results show that using the graph convolution function of GraphS AGE slightly in- creases the performance of ICGNB, while using that of GAT slightly reduces it. This demonstrates that ICGNB is not sensitive to the graph convolution function.
a significant difference between two distributions. On origi- nal attributes and new attributes, we calculate the statistics and significances between the conditional probability distri- bution of each attribute given c and the Gaussian distribution which has the same mean and variance as the distribution to be tested. The higher statistics indicate the greater dif- ference between the two distributions. A significance level below 0.05 indicates that the conditional probability distribu- tion is significantly different from the Gaussian distribution. Conversely, the conditional probability distribution demon- strates significant Gaussianity. We present the comparisons of sorted statistics for original attributes and new attributes in two classes in Figure 5a. The comparisons show that new attributes consistently exhibit lower statistics compared to original attributes in both class 1 and class 2. This indicates that new attributes are generally closer to the Gaussian dis- tribution than original attributes. We present the number of attributes with significance levels exceeding 0.05 in two classes in Figure 5b. It can be found that there are 10 and 14 original attributes in class 1 and class demonstrating significant Gaussianity, respectively. In contrast, there are 44 and 41 new attributes in class and class demonstrating significant Gaussianity, respectively. These results indicate that new attributes conform to the Gaussian distribution required by GNB better than original attributes.
5. Conclusion and future work
To leverage the correlations among instances and then en- hance the identification abilities of original attributes, we develop an instance correlation graph (ICG)-based represen- tation learning method. Based this method, propose novel algorithm called instance correlation graph-based naive Bayes (ICGNB). In ICGNB, we first construct an ICG by using original attributes to represent the correlations among instances. Then, we employ a variational graph auto- encoder (VGAE) to generate new attributes from the ICG and then augment original attributes using the generated new attributes. Finally, weight each augmented attribute to alleviate attribute redundancy and then build GNB on the weighted attributes.
Sensitivity. To analyze the sensitivity of ICGNB with differ- ent parameters and graph convolution functions, observe its classification performance on the synthetic dataset, and the experimental setup remains identical to that outlined in subsection 4.1. In ICGNB, the main adjustable parameters are the number of iterations P and the learning rate v). We conduct two parameter sensitivity analysis experiments by fixing one parameter while changing another one, and then observe the classification performance. The detailed exper- imental results are shown in Figures 6a and 6b, where the blue circle corresponds to P = 500 and = 0.01. From these results, we can see that the average classification ac- curacy is consistently near the blue circle, displaying no significant fluctuation with the changing of P or 17. This
The strategy of constructing ICG is critical, which deter- mines the precision and effectiveness of representing the correlations among instances. this paper, we do not incor- porate class labels when constructing ICG, leading to the omission of the supervised information. Exploring how to construct ICG with supervised information is the main di- rection for future work. In addition, we construct ICG using a greedy search strategy, which increases the computational cost of ICGNB. In this context, exploring how to design a strategy with lower computational cost is another direction for future work.

---

Instance Correlation Graph-based Naive Bayes
Acknowledgments
Hamilton, W. L.., Ying, Z., and Leskovec, Inductive representation learning large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024-1034, 2017.
The work was partially supported by National Natural Sci- ence Foundation of China (62276241) and Hubei Provincial Collaborative Innovation Center for Basic Education Infor- mation Technology Services (OFHUE202312).
Impact Statement
Han, J., Kamber, M., and Pei, J. Data Mining: Concepts and Techniques, 3rd edition. Morgan Kaufmann, 2011.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
He, Y., Ou, G., FournierViieer, P., and Huang. J. Z. Attribute grouping- naive bayesian classifier. Sci. China Inf. Sci., 2023.
Hindi, K. M. E. Fine tuning the naïve bayesian learning
References
algorithm. Al Commun., 27(2):133-11) 141-111, 2014.
Bilmes, J. A. and Ng, A. Y. (eds.). UAI 2009, Proceedings of the Twenty-Fifth Conference Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009, 2009. AUAI Press.
Hindi, K. M. E., Aljulaidan, R. R., and AlSalman, H. Lazy
fine-tuning algorithms for naïve bayesian text classifica- tion. Appl. Soft Comput., 96: 06652, 2020.
Jiang, L. and Zhang, H. Learning instance greedily cloning naive bayes for ranking. Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), 27-30 November 2005, Houston, Texas, USA, pp- 202- 209. IEEE Computer Society, 2005.
Blei. D. M.. Kucukelbir, A., and McAuliffe, J. D. Vari- ational inference: A review for statisticians. CoRR, abs/1601.0065 006600007 2016.
Blundell, C., Cornebise, J., Kavukeuoglu, K., and Wier- stra, D. Weight uncertainty in neural networks. CoRR, abs/1 50005444 2015.
Jiang. L., Zhang. H., and Su, J. Instance cloning local naive bayes. In Advances Artificial Intelligence, 18th Confer- ence of the Canadian Society for Computational Studies of Intelligence. Canadian Al 2005, Victoria, Canada, May 9-11, 2005, Proceedings, volume 3501 of Lecture Notes in Computer Science, pp. 280-291. Springer, 2005.
Chen, S., Webb, I., Liu, L., and Ma, X. A novel selective naïve bayes algorithm. Knowl. Based Syst., 192: 105361, 2020.
Chickering, D. M. Learning bayesian networks is np- complete. In Learning from Data - Fifth International Workshop on Artificial Intelligence and Statistics, AIS- TATS 1995, Key West, Florida, USA, January 4-7, 1995. Proceedings, pp. 121-130. Springer, 1995.
Jiang, L., Wang, D., Zhang, H., Cai, Z., and Huang, B. Us- ing instance cloning improve naive bayes for ranking. Int. J. Pattern Recognit. Artif. Intell., 22(6): 121-1110, 2008.
Cohen and Israel. Pearson correlation coefficient. Noise reduction in speech processing. (1-4), 2009.
Jiang, L., Zhang, H., and Cai, Z. A novel bayes model: Hidden naive bayes. IEEE Trans. Knowl. Data Eng., 21 (10):1361-1371,2 2009.
Demsar, J. Statistical comparisons of classifiers over multi- ple data sets. J. Mach. Learn. Res., 7:1-30, 2006.
Jiang, L.. Wang, D., and Cai, Z. Discriminatively weighted naive bayes and its application in text classification. Int. J. Artif. Intell. Tools, 21))), 2012.
Diab, D. M. and Hindi, K. M. E. Using differential evo- lution for fine tuning naive bayesian classifiers and its application for text classification. Appl. Soft Comput., 54: 183-199, 2017.
Jiang, L., Li, C., and Wang, S. Cost-sensitive bayesian network classifiers. Pattern Recognit. Lett., 45:211-216 2014.
Friedman, N., Geiger, D., and Goldszmidr, M. Bayesian net- work classifiers. Mach. Learn., 29(2-3):131-163, 1997.
Jiang, I.., Zhang, I., Li, C., and Wu, J. correlation-baset feature weighting filter for naive bayes. IEEE Trans. Knowl. Data Eng., 31(2):201-213, 2019a.
Hall, M. A. Correlation- based feature selection for discrete and numeric class machine learning. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 July 2, 2000, pp. 359-366. Morgan Kaufmann, 2000.
Jiang, L., Zhang, L., Yu, L., and Wang. D. Class-specific attribute weighted naive bayes. Pattern Recognit., 88: 321-330, 2019b.
10

---

Instance Correlation Graph-based Naive Bayes
Kingma, D. P. and Welling, M. Auto-encoding variational bayes. In 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16. 2014, Conference Track Proceedings, 2014.
Webb, G. I., Boughton, J. R., and Wang, Z. Not naive bayes: Aggregating one-dependence estimators. Mach. Learn., Leam., 58(1):5-24, 2005,
Wu, X., Kumar, V., Quinlan, J. R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G. J., Ng, A. F. M., Liu, B., Yu, S., Zhou, Z., Steinbach, M. S., Hand, D. J., and Steinberg, D. Top 10 algorithms in data mining, Knowl. Inf. Syst., 14(1): --7,, 2008.
Kipf, T. N. and Welling, M. Variational graph auto-encoders. CoRR, abs/161 1.7308,, 2016.
Kipf, T. N. and Welling, M. Semi- semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Xu, W., Jiang, L., and Yu, L. An attribute value frequency- based instance weighting filter for naive bayes. J. Exp. Theor. Artif. Intell., 31(2):225-233 2019.
Zaidi, N. A., Cerquides, J., Carman, M. J., and Webb, I. Alleviating naive bayes attribute independence assump- tion by attribute weighting. Mach. Learn. Res., 14(1): 1947-1988, 2013.
Langley, P. and Sage, S. Induction of selective bayesian classifiers. CoRR, abs/1302.682. 2013.
Lee, C.. Gutierrez, F., and Dou, D. Calculating feature weights in naive bayes with kullback-leibler measure. In 11th IEEE International Conference on Data Mining, ICDM 2011, I, Vancouver, BC, Canada, December 11-14, 2011, pp. 1146-1151, IEEE Computer Society, 2011.
Zhang, B., Sanner, S., Bouadjenek, M. R., and Gupta, Bayesian networks for data integration the absence of foreign keys. IEEE Trans. Knowl. Data Eng., 32(4): 803 803-808, 2020a.
Ou, G., He, Y., Fournier- Vigge,, P., and Huang. J. Z. Auto- encoding independent attribute transformation for naive bayesian classifier. In International Joint Conference Neural Networks, IJCNN 2022, Padua, Italy, July 18-23, 2022, pp. 1-8. IEEE, 2022.
Zhang, H. and Jiang, L. Fine tuning attribute weighted naive bayes. Neurocomputing, 488:402 411. 2022.
Zhang, H., Jiang, L., and Yu, L. Class-specific attribute value weighting for naive bayes. Inf. Sci., 508:260-274, 2020b.
Patro, S. G. K. and Sahu, K. K. Normalization: A prepro- cessing stage. CoRR, 1b3//5003.0 2015.
Zhang, H., Jiang, I.., Zhang, W., and Li, C. Multi-view attribute weighted naive bayes. IEEE Trans. Knowl. Data Eng. 35(7):7291-7302, 2023.
Pearl, Probabilistic reasoning in intelligent systems net- works of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
Qiu, C., Jiang, L., and Li, C. Not always simple classifica- tion: Learning superparent for class probability estima- tion. Expert Syst. Appl., 42(13):5433-5540 2015.
Tang, B., Kay, S., and He, H. Toward optimal feature selection in naive bayes for text categorization. IEEE Trans. Knowl, Data Eng., (009):2508-25211 2016.
van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of Machine Learning Research, 9:11, 2008.
Velickovic, P., Cucurull, G., Casanova, A., Romero, A.,
Liò, P., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representationss ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Wang, S., Jiang, Lnd C. Adapting naive bayes tree for text classification. Knowl. Inf. Syst., 44(1):77-89, 2015.

---

Instance Correlation Graph-based Naive Bayes
A. Training (ICGNB-training) and classification (ICGNB-Casssfication) algorithms of ICGNB.
Algorithm 3ICGNB-tranningD)
1: Input: D == ( -the dataset.
2: Output: - the new attribute matrix, w the weight vector.
Construct ICG by Algorithm 1;
4: Transform ICG into an adjacency matrix G;
5: Initialize the parameters of VGAE W1:
6: po to P do
7: Generate the embedding matrix by Eq. (4) with Wp;
8: Reconstruct the original adjacency matrix by Eq. (9);
9: Calculate the loss by Eq. (10);
10: Update the parameters by Eq. (11);
end for
12: Generate the new attribute matrix Z by Eq. (4) with Wr+1;
13: for i= 1 to nıe do
14: j= 1 to m do
15: Define the 2zj as the (m + /)-th attribute value of æ;;
16: end for
17: end for
for c= do
19: Estimate the prior probability Te by Eq. (13);
20: for 1 to 2m do
21:
Estimate the conditional probability le by Eq. (14);
22:
end for
23:
end for
Initialize each weight in the weight vector un;
Optimize the initialized weight vector w by Eqs. (15) (19);
26: return Z,
Algorithm 3 CaGGNN-Clasiffictton// Z, w, x)
1: Input: Z thee new attribute matrix, w the weight vector, a test instance.
2: Output: c(x)- the predicted class label of x.
3: Extract the embedding vector z corresponding to x from Z:
4: for 1 to m do
Define 2iy as the (m + j)-th attribute value of æ;;
6: end for
7: c= to l: do
8: Estimate the prior probability by Eq. (13);
9: for to 2m do
10: Estimate the conditional probability Oa by Eq. (14);
11: end for
end for
Predict the class label ?(x) of by Eq. (12):
14: return ((a:).
12

---

Instance Correlation Graph-based Naive Bayes
B. Time complexity of ICGNB.
Algorithm 1, line 3 constructs full connection graph with time complexity O Lines 4-8 calculate the Euclidean distance with time complexity of (n"m).. Line 9 sorts edges with time complexity Onnllogn). Lines 10-18 add edges ICG with time complexity of (n)))(n)), where ((a(n)) the time complexity of checking two vertices reachable. Lines 19-21 add self-connecting edges with time complexity of O(n). Due to usually being greater than logn and (n), considering only the highest-order terms, the overall time complexity of Algorithm is O(n²m).
In Algorithm 2, line 3 constructs ICG with a time complexity of Onn²m). Lines 4-5 transform ICG into G and initialize the parameters in VGAE with time complexity O Lines 6-11 train a VGAE with a time complexity of ( + m)). Line 12 generates new attributes with time complexity of ( Lines 13-17 augment original attributes with a time complexity of ( Lines 18-23 train a GNB with time complexity of O(kum). Lines 24-25 weight augmented attributes with a time complexity of O(3(m)), where ((m) has linear relationship with m. Due usually being greater than m, considering only the highest-order terms, the overall time complexity of Algorithm 2 is
In Algorithm& 3, line 3 extracts the embedding vector with time complexity of O(1). Lines 4-6 augment original attributes with time complexity of (m). Lines 7-12 estimate Te and each Deyle with a time complexity of O(km). Line 13 predicts d(z) with a time complexity (m)) Considering only the fighest-order terms, the overall time complexity of Algorithm is (km).
C. Descriptions of 24 real-world datasets used in experiments.
Table 3. Descriptions of 24 real-world datasets used in experiments. "#Attributes" denotes the number of attributes, "#Classes" denotes the number classes and "flnstances" denotes the number of instances.
Dataset
# #Attributes
#Classes
#Instances
appendicitis
106
balance
625
banana
2
2
5300
cleveland
13
5
297
ecoli
7
8
336
glass
9
7
214
iris
4
3
150
led7digit-01
10
500
magic
2
19020
movement libras
90
15
360
phoneme
5
2
5404
pima
8
2
768
ring
20
2
7400
segement
19
7
2310
sonar
60
2
208
spambase
57
4597
texture
40
11
5500
titanic
2
2201
twonorm
20
2
7400
wdbe
30
2
569
wine
13
3
178
winequality-red
11
1599
wirtt
11
4898
yeast
10
1484
13


Reviews:
[{"review_id": "ug3SCDWwpK", "reviewer": "Reviewer_tsnb", "summary": "The paper introduces **Instance Correlation Graph-based Naïve Bayes (ICGNB)**, a novel enhancement of the **Gaussian Naïve Bayes (GNB)** classifier. Traditional Naïve Bayes methods assume conditional independence among attributes, limiting their effectiveness, especially for numerical data. The proposed **ICGNB** method addresses this by incorporating **correlations among instances**, which have been largely ignored in prior research.\n\n**Main Algorithmic Ideas:**\n1. **Instance Correlation Graph (ICG) Construction**: Instances are connected in a graph based on similarity, forming an **Instance Correlation Graph (ICG)**.\n2. **Graph-Based Representation Learning**: A **Variational Graph Auto-Encoder (VGAE)** generates new attributes from the ICG, capturing latent instance correlations.\n3. **Attribute Augmentation and Weighting**: The generated attributes are combined with original ones, and a weighting scheme optimizes attribute significance, reducing redundancy.\n\n**Main Findings & Results:**\n- **ICGNB outperforms traditional GNB and state-of-the-art Naïve Bayes enhancements** across multiple datasets.\n- It significantly improves classification accuracy by leveraging graph-based attribute generation and augmentation.\n- Empirical validation on **24 real-world datasets** and synthetic data confirms **ICGNB’s robustness and generalization ability**.\n\nBy integrating instance correlation insights into Naïve Bayes classification, ICGNB presents a **new paradigm** for improving probabilistic classifiers with graph-based learning techniques.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "The paper presents **Instance Correlation Graph-based Naïve Bayes (ICGNB)** as an improvement over **Gaussian Naïve Bayes (GNB)**, claiming that leveraging instance correlations via graph-based representation learning significantly enhances classification performance. Most claims are backed by **theoretical justification and empirical evidence**, but there are some concerns regarding the **generality and robustness** of the approach.\n\n**Supported Claims:**\n1. **Effectiveness of ICGNB**: The claim that ICGNB outperforms GNB and other enhanced Naïve Bayes models is well-supported. The **Wilcoxon signed-rank test** across **24 real-world datasets** provides **statistically significant** improvements, strengthening the empirical validation.\n2. **Attribute Independence and Gaussianity**: The paper convincingly shows that the **generated attributes align better with the Gaussian assumption**, validated through the **Kolmogorov-Smirnov test**.\n\n**Potentially Problematic Claims:**\n1. **Scalability**: The computational overhead of constructing the **Instance Correlation Graph (ICG)** and training the **Variational Graph Auto-Encoder (VGAE)** is not fully analyzed. Large-scale applications may face challenges.\n2. **Generality**: The method is benchmarked on **numerical datasets only**. Performance on **mixed or high-dimensional categorical data** remains unclear.\n3. **Causality vs. Correlation**: While ICG captures correlations, it does not necessarily improve **causal relationships**, potentially leading to **overfitting**.", "methods_and_evaluation_criteria": "The proposed **Instance Correlation Graph-based Naïve Bayes (ICGNB)** method is evaluated using **well-established datasets and appropriate evaluation criteria**, making the study **methodologically sound**. However, there are **certain limitations in dataset diversity and scalability analysis** that should be considered.\n\n **Strengths of Methods and Evaluation:**\n1. **Benchmark Datasets**: The study uses **24 real-world datasets from KEEL**, covering various domains and numerical attributes. This is **appropriate for testing Gaussian Naïve Bayes (GNB) extensions**.\n2. **Comparative Baselines**: The comparison against **state-of-the-art Naïve Bayes enhancements** (WANBIA, CFWNB, AG-NBC, AE-NBC, and GNB) is **comprehensive and fair**.\n3. **Statistical Validation**: The **Wilcoxon signed-rank test** ensures that reported improvements are **statistically significant**, strengthening the reliability of results.\n\n**Potential Limitations:**\n1. **Dataset Scope**: The evaluation **excludes categorical or mixed-type datasets**, limiting its **generalizability** beyond numerical data.\n2. **Scalability Considerations**: While VGAE improves feature representation, **its computational cost is not analyzed**. The method’s efficiency on **large-scale datasets** is uncertain.\n3. **Alternative Evaluation Metrics**: The study **focuses primarily on classification accuracy**, without analyzing robustness to **adversarial noise, missing data, or class imbalance**.\n\n **Overall Assessment:**\nThe methodology is **well-structured** and **empirical validation is strong**, but additional **scalability analysis** and **broader dataset selection** would enhance the **practical applicability** of ICGNB.", "theoretical_claims": "The paper presents **theoretical claims** primarily related to **the effectiveness of the Instance Correlation Graph (ICG), the variational graph auto-encoder (VGAE) for attribute generation, and the weighted Gaussian Naïve Bayes (GNB) formulation**. While the overall framework is well-motivated, some theoretical aspects require **closer scrutiny**.\n\n**Checked Theoretical Claims:**\n1. **ICG Construction and Sparsity**:  \n   - The paper claims that **ICG captures meaningful instance correlations** while maintaining **a sparse structure**. The **edge selection algorithm** ensures connectivity using a minimal number of edges. This is **conceptually sound**, though a formal proof of optimality is missing.\n   \n2. **VGAE-Based Attribute Generation**:  \n   - The theoretical justification relies on **graph convolutional embedding** preserving instance relationships. The **variational objective (ELBO) is correctly formulated** following standard **VGAE methodology** (Kingma & Welling, 2014). However, the assumption that **generated attributes are inherently more independent** is **not formally proven**, only empirically suggested.\n   \n3. **Attribute Weighting via Conditional Log-Likelihood (CLL) Maximization**:  \n   - The gradient-based weight optimization process follows a **standard likelihood maximization framework**. However, convergence guarantees or sensitivity analysis are **not provided**.\n\n**Potential Issues:**\n- **No proof of Gaussianity**: The claim that **VGAE-generated attributes better fit Gaussian assumptions** is only empirically tested, lacking **a theoretical derivation**.\n- **Scalability of VGAE training**: No theoretical analysis of **complexity bounds** is presented.\n\n**Overall Assessment:**  \nThe proofs presented are **generally correct**, but some **key claims (e.g., independence of generated features, scalability) lack formal justification** and are **only validated empirically**. A more rigorous **theoretical treatment** of these aspects would strengthen the paper.", "experimental_designs_or_analyses": "The experimental design of the paper is **generally well-structured**, incorporating a **broad set of real-world datasets**, **comparative baselines**, and **statistical validation**. However, there are some **limitations in dataset diversity and certain evaluation aspects** that could impact the validity of the findings.\n\n **Checked Experimental Designs and Analyses:**\n\n1. **Dataset Selection and Preprocessing:**  \n   - The use of **24 numerical datasets from KEEL** ensures that the method is tested across multiple domains. However, it **excludes categorical or mixed-type data**, limiting generalizability beyond purely numerical datasets.\n   - **Z-score normalization** is applied, which is **appropriate** for Gaussian-based methods but may not reflect real-world data preprocessing variations.\n\n2. **Comparative Baselines:**  \n   - The paper compares ICGNB against **five well-established Naïve Bayes enhancements (WANBIA, CFWNB, AG-NBC, AE-NBC, and GNB)**, making the evaluation **comprehensive**.\n   - However, the **absence of deep learning-based classifiers or ensemble methods** as additional baselines means the **broader competitiveness** of ICGNB remains unclear.\n\n3. **Statistical Evaluation and Significance Tests:**  \n   - The **Wilcoxon signed-rank test** is an **appropriate choice** for measuring statistical significance in performance comparisons.\n   - However, the paper does not include **confidence intervals for accuracy improvements**, which would provide a clearer measure of variability.\n\n4. **Scalability and Computational Analysis:**  \n   - There is **no discussion of computational efficiency**, particularly regarding **VGAE training costs** and **graph construction overhead**.\n   - The method’s viability for **large-scale datasets** is uncertain.\n\n**Potential Issues and Suggestions:**\n- The exclusion of **non-numerical datasets** limits generalizability.\n- The **lack of alternative evaluation metrics** (e.g., runtime analysis, robustness to noise, or class imbalance) makes it hard to assess **real-world applicability**.\n- **Computational cost analysis** is missing, which could be a key bottleneck for practical deployment.\n\n**Overall Assessment:**  \nThe experimental setup is **rigorous in its scope and statistical validation**, but additional **efficiency analysis, dataset diversity, and robustness tests** would enhance the study’s reliability and practical impact.", "relation_to_broader_scientific_literature": "The key contributions of this paper are closely related to several existing lines of research in **Naïve Bayes improvements, graph-based learning, and representation learning with autoencoders**. While the paper introduces a novel **Instance Correlation Graph-based Naïve Bayes (ICGNB)** framework, its ideas build upon well-established methodologies in **probabilistic classification and graph neural networks**.\n\n**Relation to Prior Research:**\n\n1. **Naïve Bayes Enhancements:**  \n   - The paper follows a long tradition of **improving Naïve Bayes by addressing its independence assumption**. Previous works have explored **attribute weighting (WANBIA, CFWNB)** and **attribute transformation (AG-NBC, AE-NBC)**.  \n   - ICGNB extends these by **introducing instance-instance correlations**, which are generally ignored in prior Naïve Bayes improvements.\n\n2. **Graph-Based Representation Learning:**  \n   - The use of **Instance Correlation Graphs (ICG)** aligns with advances in **graph-based semi-supervised learning**, particularly **Graph Convolutional Networks (GCN)** and **Variational Graph Autoencoders (VGAE)** (Kipf & Welling, 2017).  \n   - VGAE has been widely used for **latent feature extraction**, and this paper leverages it to **generate new attributes** that improve classification performance.\n\n3. **Attribute Augmentation and Weighting:**  \n   - The method shares similarities with **feature learning techniques in deep learning**, where new attributes are derived via **embedding-based transformations**.  \n   - However, unlike deep learning methods, ICGNB retains the **probabilistic interpretability of GNB**.\n\n **Broader Impact and Limitations:**\n- The **combination of Naïve Bayes with graph-based learning is novel**, but similar ideas have been explored in **relational learning and Bayesian networks**.  \n- The paper focuses on **numerical data only**, which limits its applicability in domains where **categorical attributes** play a significant role.\n- While the approach improves Naïve Bayes, it does not explore how it compares to **modern deep learning classifiers**.\n\n**Overall Assessment:**  \nICGNB contributes meaningfully to **graph-enhanced probabilistic classification**, bridging **Naïve Bayes improvements with representation learning**. However, its relation to broader **graph-based Bayesian models and deep learning-based feature learning** could be explored further.", "essential_references_not_discussed": "The paper effectively cites foundational works on **Naïve Bayes improvements, graph-based learning, and variational autoencoders**, but **some key references in graph-based Bayesian learning and scalable feature learning are missing**.\n\n1. **Graph-Based Bayesian Models**:  \n   - The paper does not discuss **Graphical Models for Naïve Bayes Extensions**, such as **Tree-Augmented Naïve Bayes (TAN)** (Friedman et al., 1997), which also address feature dependencies while maintaining Naïve Bayes simplicity.  \n   - **Relational Bayesian Models** (Getoor & Taskar, 2007) have explored **leveraging inter-instance relationships** in probabilistic classification.\n\n2. **Scalability of Graph Autoencoders**:  \n   - The paper uses **Variational Graph Autoencoders (VGAE)** (Kipf & Welling, 2017) but does not discuss **scalable alternatives** such as **GraphSAGE (Hamilton et al., 2017)**, which may offer better efficiency for large-scale applications.\n\n3. **Feature Learning for Naïve Bayes**:  \n   - **Autoencoder-based feature learning for probabilistic models** (Kingma & Welling, 2014) is relevant but not fully explored in terms of direct Naïve Bayes applications.\n\n**Overall Suggestion**  \nDiscussing **TAN, relational Bayesian models, and scalable GNN methods** would provide **a more complete context** for the proposed approach and highlight its novelty better.", "other_strengths_and_weaknesses": "**Strengths**  \n1. **Novel Integration of Graph-Based Learning with Naïve Bayes**: The use of **Instance Correlation Graphs (ICG)** and **Variational Graph Autoencoders (VGAE)** to enhance Naïve Bayes classification is an **original contribution**, effectively addressing the attribute independence assumption.  \n2. **Strong Empirical Validation**: The **comprehensive experiments on 24 datasets**, along with **statistical significance testing (Wilcoxon signed-rank test)**, provide **credible evidence** of the method’s effectiveness.  \n3. **Interpretability**: Unlike deep learning-based classifiers, the method **preserves the interpretability of Naïve Bayes**, making it more suitable for explainable AI applications.\n\n**Weaknesses**  \n1. **Scalability Concerns**: **No discussion on computational complexity**, particularly regarding **graph construction and VGAE training**, which may hinder practical deployment on large datasets.  \n2. **Limited Generalization**: The approach is **only evaluated on numerical datasets**, excluding categorical and mixed-type data, limiting its **applicability in broader domains**.  \n3. **Clarity of Theoretical Justifications**: While empirically validated, **some theoretical claims (e.g., feature independence in VGAE-generated attributes)** lack formal proofs.  \n\n**Overall**  \nThe paper presents an **innovative and promising approach**, but addressing **scalability and broader dataset applicability** would enhance its impact.", "other_comments_or_suggestions": "No additional comments or suggestions.", "questions_for_authors": "1. **Scalability and Computational Complexity**  \n   - What is the computational complexity of constructing the **Instance Correlation Graph (ICG)** and training the **Variational Graph Autoencoder (VGAE)**? Have you evaluated runtime performance on larger datasets?  \n   - A response showing that ICGNB is computationally efficient would **strengthen confidence in its practicality**.\n\n2. **Applicability to Categorical and Mixed-Type Data**  \n   - Since the experiments focus only on **numerical datasets**, how would ICGNB handle **categorical or mixed-type features**? Would discretization or embedding techniques be required?  \n   - If the method is adaptable to broader data types, its **generalizability and impact would increase**.\n\n3. **Independence and Gaussianity of Generated Attributes**  \n   - The empirical results suggest that **VGAE-generated attributes align better with the Naïve Bayes assumptions**, but is there a **theoretical justification** for this claim?  \n   - A formal proof or additional justification would **strengthen the theoretical contributions of the paper**.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UQ40Vnud2B", "reviewer": "Reviewer_XTK4", "summary": "This paper presents ICGNB, an enhanced Naïve Bayes method based on the Instance Correlation Graph (ICG). ICGNB leverages ICG to capture instance correlations, employs a Variational Graph Autoencoder (VGAE) to generate new attributes, and optimizes attribute weighting using Conditional Log-Likelihood (CLL). Experimental results demonstrate that ICGNB achieves an average classification accuracy of 78.87% across 24 real-world datasets, significantly outperforming existing methods. Its effectiveness is further validated through Wilcoxon statistical tests. Ablation studies and synthetic dataset analysis further confirm that ICGNB generates attributes with higher independence and Gaussianity, leading to improved classification performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments. We sincerely appreciate the time and effort you have dedicated to reviewing our work. Below, we provide detailed responses to each of your concerns.\n\n**Author Response to Computational Complexity:** We complement the time complexity analysis as follows: In Algorithm 1, line 3 constructs a full connection graph with a time complexity of $O(n^{2})$.  Lines 4-8 calculate the Euclidean distance with a time complexity of $O(n^{2}m)$. Line 9 sorts edges with a time complexity of $O(n^{2}logn)$. Lines 10-18 add edges to ICG with a time complexity of $O(n^{2}\\alpha(n))$, where $O(\\alpha(n))$ is the time complexity of checking if two vertices are reachable. Lines 19-20 add self-connecting edges with a time complexity of $O(n)$. Due to $m$ usually being greater than $logn$ and $\\alpha(n)$, considering only the highest-order terms, the overall time complexity of Algorithm 1 is $O(n^{2}m)$. In Algorithm 2, lines 4-5 transform ICG into $G$ and initialize the parameters in VGAE with a time complexity of $O(n^2)$. Lines 6-11 train a VGAE with a time complexity of $O(P(nm^2+n^{2}m))$. Line 12 generates new attributes with a time complexity of $O(nm^2)$. Lines 13-17 augment original attributes with a time complexity of $O(nm)$. Lines 18-23 train a GNB with a time complexity of $O(knm)$. Lines 24-25 weight augmented attributes with a time complexity of $O(\\beta(m))$, where $\\beta(m)$ has a linear relationship with $m$.  Due to $n$ usually being greater than $m$, considering only the highest-order terms, the overall time complexity of Algorithm 2 is $O(Pn^{2}m)$. In the final version of the paper, we will add all these time complexity analyses.\n\n**Author Response to Theoretical Support:** We perform a formal analysis of Gaussianity, independence, and convergence proof for attribute weighting optimization as follows:\n\n1. Gaussianity: VGAE ensures that the distribution of the embedding vectors closely approximates $p(\\mathbf{Z})$, which is an independent zero-mean multivariate Gaussian distribution with unit variances. Each variate in $p(\\mathbf{Z})$ corresponds to a new attribute in $\\mathbf{Z}$, and thus the new attribute closely approximates the Gaussian distribution.\n\n2. Independence: The independent zero-mean in $p(\\mathbf{Z})$ ensures that the covariance matrix of $p(\\mathbf{Z})$ is a diagonal matrix, which implies that covariances between variates (new attributes) are zero, i.e., variates (new attributes)  are independent of each other.\n\n3. Convergence proof for attribute weighting optimization: In ICGNB, we perform the gradient descent search by using the L-BFGS algorithm. According to [1],  the L-BFGS algorithm is globally convergent on uniformly convex problems. The objective function in our optimization maximizes the conditional log-likelihood (CLL)  of the attribute weighted GNB, which is a uniformly convex problem. Therefore, the optimization process is guaranteed to converge.\n\n[1] Pearl, J. Probabilistic reasoning in intelligent systems-net-works of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.\n\n**Author Response to Sensitivity Analysis:**  The hyperparameters in ICGNB include the number of iterations $P$ and the learning rate $\\eta$, which are set to default values of 500 and 0.01, respectively. To address the reviewer’s concerns, we conduct parameter sensitivity experiments on the first real-world dataset (appendicitis) to evaluate ICGNB’s performance. In each experiment, we fix one hyperparameter and vary the remaining one and use the same setup described in Section 4.1. The results are as follows:\n|$P$|300|400|500|600|700|\n|:--:|:--:|:--:|:--:|:--:|:--:|\n|Average Accuracy (%)|88.64|88.18|89.09|88.64|90.00|\n||\n\n|$\\eta$|0.005|0.0075|0.01|0.0125|0.015|\n|:--:|:--:|:--:|:--:|:--:|:--:|\n|Average Accuracy (%)|88.64|90.00|89.09|89.09|88.18|\n||\n\nThese results show that ICGNB’s performance varies slightly with changes in hyperparameter values, which demonstrates that ICGNB is insensitive to parameters.\n\n**Author Response to Essential References:** Indeed, GraphSAGE is closely related to our ICGNB and provides an effective graph representation learning strategy. To address the reviewer’s concerns, we will cite GraphSAGE and discuss its correlation with our study. In addition, we conduct an experiment to explore whether GraphSAGE can be used for our ICGNB. Specifically, we replace the graph convolution function of VGAE with that of GraphSAGE and perform a stratified hold-out validation on 24 real-world datasets. The average classification accuracy is as follows:\n||ICGNB_VGAE|ICGNB_GraphSAGE|\n|:--:|:--:|:--:|\n|Average Accuracy (%)|80.22|80.46|\n||\n\nThe results show that the graph convolution function of GraphSAGE can also be used for our ICGNB.", "claims_and_evidence": "Yes, the paper demonstrates through Wilcoxon statistical tests that incorporating instance correlations enhances Naïve Bayes' ability to handle numerical attributes. Additionally, Pearson correlation heatmaps reveal a significant reduction in correlation among the newly generated attributes, making them more aligned with the Naïve Bayes assumption.", "methods_and_evaluation_criteria": "This approach is meaningful as it utilizes the ICG to capture instance relationships, overcoming the limitation of NB, which relies solely on independent attributes. By leveraging VGAE to generate new attributes, the method enhances the representational capacity of the original attributes while ensuring their independence.", "theoretical_claims": "The theoretical claims of this paper primarily lie in the fact that the new attributes generated by ICGNB align with the core assumptions of NB, and that attribute weighting optimization enhances classification performance. However, the paper does not provide a rigorous mathematical proof; instead, these claims are validated empirically through experiments.", "experimental_designs_or_analyses": "At present, the experiments are all reasonable, but there is a lack of parametric sensitivity experiments.", "relation_to_broader_scientific_literature": "This paper integrates an enhanced NB approach with graph representation learning, leveraging instance correlations to optimize numerical attribute classification. Unlike traditional NB improvements that solely rely on the independence assumption, this method introduces a novel perspective by incorporating instance relationships. Moreover, it aligns with GNN-related research, bridging the gap between probabilistic classification and graph-based learning.", "essential_references_not_discussed": "The paper does not discuss classification methods based on GNN and VGAE, such as GraphSAGE [1], which have had a significant impact in the field of graph representation learning and are closely related to ICGNB’s graph-based representation approach. Additionally, the paper does not cite more advanced probabilistic graphical models, which could be relevant to optimizing the compatibility of ICGNB with the NB assumption. Including discussions on these methods could provide a broader contextual understanding and highlight potential improvements to the proposed approach.\n\n- [1] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[J]. Advances in neural information processing systems, 2017, 30.", "other_strengths_and_weaknesses": "Strengths:\n- Innovative Extension of NB: By integrating ICG and VGAE, the method enhances NB classification performance for numerical attributes, representing a novel extension of NB.\n- Broader Applicability: The approach is well-suited for numerical attribute classification tasks and introduces a new perspective on instance correlation learning, making it potentially adaptable to other graph-based classification tasks.\n\nWeaknesses:\n- Unassessed Computational Cost: The construction of ICG and the training of VGAE increase computational complexity. However, the paper does not provide an analysis of runtime or computational complexity.\n- Lack of Theoretical Support: While experimental results support the claims, the paper lacks a formal analysis of the independence and Gaussianity of the VGAE-generated attributes, as well as a convergence proof for attribute weighting optimization.", "other_comments_or_suggestions": "None.", "questions_for_authors": "The paper presents extensive experimental results but lacks a complete theoretical derivation, as mentioned in the weaknesses. Providing a detailed theoretical derivation would improve the overall score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IqRqcFMfGW", "reviewer": "Reviewer_DoNX", "summary": "This paper proposes a novel instance correlation graph (ICG) based Naïve Bayes classification framework. It first constructs an ICG from original attributes, and then employs a variational graph autoencoder (VGAE) to generate embeddings based on both ICG and original attributes. Extensive experiments have been conducted to verify the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** Constructing a full connection graph of instances based on Euclidean distance is time consuming and usually introduces noisy edges, how to address these issues?  \n  \n**Author Response to Q1:** Thanks for your valuable comments. In our paper, to construct the instance correlation graph (ICG), we first define a full connection graph containing $n(n-1)/2$ edges among all instances. Then, to reduce time costs, we only select $n-1$ edges from this full connection graph to construct ICG. As a result, the ICG we constructed is a sparse graph, with most noisy edges from the fully connected graph removed. In the final version of the paper, we will include the above explanations to clarify this point. Thanks again for your valuable comments. \n  \n**Q2 and W1:** The ICG construction algorithm adopts a greedy strategy, and its output is similar to a minimum spanning tree of the full connection graph. Moreover, the class labels of training instances are not incorporated into the ICG construction, which might lead to the omission of supervised information. Therefore, the correctness and advantages of this algorithm should be thoroughly discussed.  \n  \n**Author Response to Q2 and W1:** Thanks for your valuable comments. In ICGNB, VGAE requires a graph that includes both training and test instances. Since the class labels of test instances are unavailable during the training stage, their supervised information cannot be incorporated into the construction of the ICG. To ensure consistency between training and test instances, the supervised information of training instances is also excluded from the ICG construction. Although supervised information is not used during ICG construction, it is incorporated into the attribute weighting stage of ICGNB. Therefore, the overall ICGNB framework fully considers supervised information. In the final version of the paper, we will include the above explanations to clarify this point. Thanks again for your valuable comments. \n  \n**W2:** The authors claim that using a VGAE to generate augmented attributes from ICG and reweighting these attributes is effective for improving classification accuracy. However, this technique is similar to Graph Attention Networks (GAT), so the advantages of the proposed method over GAT should be clearly explained.  \n  \n**Author Response to W2:** Thanks for your valuable comments. The advantages of ICGNB over GAT are summarized in the following two aspects. First, GAT fails to retain the original attributes during training, thereby losing their interpretability. In contrast, ICGNB simultaneously utilizes both the original attributes and the newly generated attributes of all instances, which preserves the interpretability of the original attributes while capturing potential correlations among instances through the new attributes. Second, GAT applies a local attention mechanism to assign weights to the neighbors of each node. However, ICGNB applies a global weighting strategy to all 2$m$ augmented attributes, enabling it to capture the overall characteristics of the dataset more effectively. By combining these two aspects, ICGNB demonstrates clear advantages over GAT. We will include a discussion on these advantages in the final version of the paper. Thanks again for your valuable comments.", "claims_and_evidence": "Yes. The authors claim that they improve the performance of Naïve Bayes classifier by leveraging the correlations among instances, which is supported by clear and convincing theoretical analysis and experiments.", "methods_and_evaluation_criteria": "Yes. The proposed method and evaluation criteria in the paper make sense for the problem and application.", "theoretical_claims": "Yes. I have checked the correctness of theoretical claims in this paper.", "experimental_designs_or_analyses": "Yes. I have checked the soundness of the experimental settings and results analysis. Twenty-four real-world datasets were adopted for evaluating the classification performance of the proposed method, and synthetic data was used to verify the independence and Gaussianity of the attributes generated by ICG. These experimental designs and analyses look sound.", "relation_to_broader_scientific_literature": "This paper proposes a novel Naïve Bayes (NB) classifier, named ICGNB, to improve the performance of NB on numerical attributes by effectively utilizing the correlations among instances with VGAE.", "essential_references_not_discussed": "No. All essential references are currently cited/discussed in the paper.", "other_strengths_and_weaknesses": "S1. Unlike most variants of Naïve Bayes that assume instance independence, this paper enhances Naïve Bayes based on the correlations among instances, which seems both reasonable and effective.\n\nS2. The proposed model ICGNB contains an attribute weighting module to reduce the redundancy information from the correlations of instances, which is interesting and effective.\n\nS3. Extensive experiments on several real-world and synthetic datasets have been conducted and the results verify the effectiveness, independence and Gaussianity of the proposed model.\n\nS4. The organization of the paper is quite good and it is easy to follow.\n\nW1. The ICG construction algorithm appears to employ a greedy strategy. Thus, the correctness of this algorithm should be discussed more clearly.\n\nW2. The authors claim that using a VGAE to generate augmented attributes from ICG and reweighting these attributes is effective for improving classification accuracy. However, this technique is similar to Graph Attention Networks (GAT), so the advantages of the proposed method over GAT should be clearly explained.", "other_comments_or_suggestions": "I do not have any additional comments or suggestions for the authors.", "questions_for_authors": "Q1. Constructing a full connection graph of instances based on Euclidean distance is time consuming and usually introduces noisy edges, how to address these issues?\n\nQ2. The ICG construction algorithm adopts a greedy strategy, and its output is similar to a minimum spanning tree of the full connection graph. Moreover, the class labels of training instances are not incorporated into the ICG construction, which might lead to the omission of supervised information. Therefore, the correctness and advantages of this algorithm should be thoroughly discussed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RmygSu5k6q", "reviewer": "Reviewer_XBWa", "summary": "The authors propose a novel algorithm called instance correlation graph-based naive Bayes (ICGNB), which can work with numerical attributes and utilize the correlations among instances. The average classification accuracy of ICGNB on 24 datasets is higher than the best competitors.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Questions For Authors:** How about the performance if other graph convolution functions are used?\n\n**Author Response:** Thanks for your valuable comments. In addition to the graph convolution function used in VGAE, some other graph convolution functions in GraphSAGE and GAT can also be used. To address the reviewer’s concerns, we perform experiments by replacing the graph convolution function of VGAE with those of GraphSAGE and GAT to evaluate the performance of ICGNB. We perform a stratified hold-out validation on 24 real-world datasets. All other experimental settings remain consistent with those described in the paper. The average classification accuracy of ICGNB with different graph convolution functions across the 24 datasets is summarized as follows:\n||ICGNB_VGAE|ICGNB_GraphSAGE|ICGNB_GAT|\n|:--:|:--:|:--:|:--:|\n| Average Accuracy (%)|80.22|80.46|79.22|\n||\n\nThese results show that using the graph convolution function of GraphSAGE is also effective, but using that of GAT slightly reduces our ICGNB’s performance.\n\n**Experimental Designs Or Analyses:** The experimental designs of both real and synthetic datasets are checked. I think the ablation study part can be extended to include more variants.\n\n**Author Response:** Thanks for your valuable comments. We agree that including additional ablation variants can provide a more thorough analysis of the effectiveness of each part in ICGNB. To address the reviewer’s concerns, we have introduced two new ablation variants and conducted a more comprehensive ablation study using the experimental setup described in Section 4.1. The two new variants are denoted as ICGNB-G and ICGNB-GW. Here, ICGNB-G only retains the part of attribute generation and removes attribute augmentation and weighting. ICGNB-GW retains the part of attribute generation and weighting and removes original attributes. Meanwhile, the existing two ablation variants are denoted as ICGNB-A and ICGNB-W. ICGNB-A only retains the part of attribute generation and attribute augmentation and removes attribute weighting. ICGNB-W retains the part of attribute weighting and removes attribute generation and attribute augmentation. The experimental results are as follows:\n||ICGNB|ICGNB\\-A|ICGNB\\-W|ICGNB\\-G|ICGNB\\-GW|\n|:--:|:--:|:--:|:--:|:--:|:--:|\n|Average Accuracy (%)|78.87|73.70|77.84|72.44|72.61|\n||\n\nFrom these results, it can be found that ICGNB-A achieves higher accuracy than ICGNB-G, demonstrating that attribute augmentation is essential for ICGNB. ICGNB-GW achieves higher accuracy than ICGNB-G, confirming that attribute weighting is necessary for new attributes. Meanwhile, ICGNB consistently outperforms all its variants, further validating the rationality of ICGNB. In the final version of the paper, we will add these two new variants into our ablation study. Thanks again for your valuable comments.\n\n**Other Comments Or Suggestions:**\n\nI would suggest to put the columns of ICGNB and ICGNB-A together for easy comparison. \n\nI wonder whether the formulas in the introduction section are necessary since they are not used in the motivation illustration of ICGNB.\n\n**Author Response:** \nThanks for your valuable comments. In the final version of the paper, we will put the columns of ICGNB and ICGNB-A together for easy comparison. \n\nIn our paper, the introduction section includes two formulas, Eqs (1) and (2), which are used by Bayesian networks and NB to classify instances, respectively. As the starting point of our work, they demonstrate that NB relies on the attribute conditional independence assumption (ACIA). Considering that ACIA is difficult to hold in real-world scenarios, numerous improved algorithms have subsequently been proposed. However, these algorithms overlook leveraging the correlations among instances to improve NB, which motivates us to propose the ICGNB in this paper. Therefore, the formulas in the introduction section are necessary. Thanks again for your valuable comments.", "claims_and_evidence": "The results on synthetic data demonstrate that the newly generated attributes are more effective than original ones. The authors consider all feasible datasets from KEEL for evaluation, and thus I think they did not hide negative results. Hence, I'm overall satisfied with the improvements, despite that the proposed ICGNB does not always perform the best.", "methods_and_evaluation_criteria": "The main framework of ICGNB in Figure 1 is intuitive. The optimization of ELBO aligns with the choice of VGAE. The choice of datasets is ok to me, since ALL datasets containing only numerical attributes from KEEL are considered.", "theoretical_claims": "NA", "experimental_designs_or_analyses": "The experimental designs of both real and synthetic datasets are checked. I think the ablation study part can be extended to include more variants.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "No, to my knowledge.", "other_strengths_and_weaknesses": "No other strengths and weaknesses need to be highlighted.", "other_comments_or_suggestions": "I would suggest to put the columns of ICGNB and ICGNB-A together for easy comparison.\n\nI wonder whether the formulas in the introduction section are necessary, since they are not used in the motivation illustration of ICGNB.", "questions_for_authors": "1.How about the performance if other graph convolution functions are used?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes an enhancement of Gaussian Naive Bayes method called ICGNB. Its advantages include: 1) combining graph-based learning with probabilistic modeling and introducing a new angle to Naive Bayes by modeling inter-instance relationships; 2) maintaining the clarity of GNB while enhancing performance; 3) providing formal arguments on Gaussianity, independence, and convergence of attribute weighting. However, there are concerns about scalability, generalization to data types, and a lack of comparison with broader models. Overall, this is a qualified paper and I recommend acceptance.
Decision: Accept (spotlight poster)