# Fast & Efficient Learning of Bayesian Networks from Data: Knowledge
Discovery and Causality

Sein Minn1, Fu Shunkai2
1 Independent Researcher, Canada
2 Huaqiao University, China

###### Abstract

Structure learning is essential for Bayesian networks (BNs) as it uncovers
causal relationships, and enables knowledge discovery, predictions,
inferences, and decision-making under uncertainty. Two novel algorithms, FSBN
and SSBN, based on the PC algorithm, employ local search strategy and
conditional independence tests to learn the causal network structure from
data. They incorporate d-separation to infer additional topology information,
prioritize conditioning sets, and terminate the search immediately and
efficiently. FSBN achieves up to 52% computation cost reduction, while SSBN
surpasses it with a remarkable 72% reduction for a 200-node network. SSBN
demonstrates further efficiency gains due to its intelligent strategy.
Experimental studies show that both algorithms match the induction quality of
the PC algorithm while significantly reducing computation costs. This enables
them to offer interpretability and adaptability while reducing the
computational burden, making them valuable for various applications in big
data analytics.

###### Index Terms:

Bayesian networks, knowledge discovery, causality, constraint-based learning,
local search, time-efficient learning

##  I Introduction

Bayesian networks provide a compact and expressive framework for modeling
causality by utilizing joint probability distributions (JPDs) and enabling
causal inference. This allows for a systematic representation of causal
relationships between variables and facilitates reasoning and decision-making
under uncertainty. They consist of a directed acyclic graph (DAG) where nodes
represent random variables and conditional probability distributions are
assigned to variables based on their parents in the graph [1, 2]. However,
learning the graph structure of BNs from data poses significant challenges to
computation and data efficiency, even when the data is complete [3, 4, 5].

Figure 1: An example of Bayesian network structure.

In the field of structure learning for Bayesian networks, existing algorithms
can be broadly categorized into two approaches: constraint learning and search
& score methods. The constraint learning approach, outlined in the work by
Spirtes, Glymour, and Scheines (SGS) [6], involves performing a series of
conditional independence tests on the available data. Based on the results of
these tests, a BN is constructed that aligns with the observed dependencies
among variables. In contrast, the search & score approach, introduced by
Cooper and Herskovits [7], focuses on finding a graph structure that maximizes
a chosen scoring metric. This metric acts as a measure of the goodness of fit
between the BN’s structure and the provided data. The search & score approach
employs an iterative search process to explore and evaluate different graph
structures based on the chosen scoring criterion [3]. Both constraint learning
and search & score methods have their strengths and limitations.

The constraint learning approach leverages statistical tests to directly
identify the conditional independence relationships among variables, which
allows for the construction of a BN that adheres to the observed dependencies
in the data. On the other hand, search & score methods provide flexibility in
selecting a scoring metric that captures the desired properties of the BN. By
searching through the space of possible graph structures, these methods aim to
find the structure that optimally fits the given data according to the chosen
scoring criterion [8, 9]. The search & score algorithms are known to be more
computationally expensive compared to constraint-based learning algorithms,
especially when dealing with large feature spaces [10]. As a result, these
algorithms can become practically infeasible for such scenarios. They use
greedy strategies to explore the space of directed acyclic graphs (DAGs) and
often rely on prior knowledge or assumptions to guide the search process. The
selection of the appropriate approach depends on various factors, including
the characteristics of the available data, the complexity of the BN structure,
and the specific goals of the analysis. Researchers and practitioners often
consider the trade-offs between time efficiency, accuracy in capturing
dependencies, and the interpretability of the resulting BN structure when
choosing among structure learning algorithms.

Both the constraint learning and search & score approaches for structure
learning in BNs are known to be computationally challenging. It has been
proven that determining the optimal structure is an NP-hard problem [11],
meaning that finding an exact solution becomes increasingly difficult as the
number of variables grows. The best exact methods available exhibit
exponential time complexity, which limits their applicability to small-scale
problems with around 30 variables [3, 12, 2016Efficient]. To handle larger
networks, approximate procedures are often employed. However, these
approximate methods can encounter difficulties in getting trapped in local
maxima, leading to suboptimal structures. Despite this challenge, the quality
of the learned structure is crucial for the accuracy of the resulting BN
model. If the dependencies among variables are not correctly captured during
the structure learning process, the estimated distribution may deviate
significantly from the true distribution. Researchers and practitioners in the
field continue to develop and refine algorithms that strike a balance between
time efficiency and accuracy in structure learning. Various techniques, such
as heuristics, optimization algorithms, and parallel computing, are being
explored to improve the scalability and effectiveness of structure learning
algorithms for BNs.

This paper introduces two novel algorithms for learning the structure of
Bayesian networks from data, both falling under the category of constraint-
based learning methods. These algorithms utilize a series of local structure
inductions, where conditional independence (CI) tests (by using ${\chi}^{2}$
test) are employed to determine the presence or absence of connections between
pairs of nodes. To minimize the number of CI tests required, the algorithms
utilize topology information inferred from previously conducted CI tests. This
information is used to prioritize and sort future candidate CI tests. Tests
that are more likely to reveal connections that should not exist are given
higher priority, thereby avoiding unnecessary statistical tests. Additionally,
considering that the CI tests are employed across various constraint-based
learning algorithms for both inductions of Markov blankets and Bayesian
networks, the proposed techniques can also be employed and may assist in
accelerating the induction of the BN, as well as in the development of uni-
and multi-dimensional BN classifiers. The effectiveness and efficiency of both
algorithms are demonstrated through experiments conducted on synthetic and
classical networks. The results highlight the algorithms’ ability to
accurately learn the structure of BNs while minimizing computational overhead.
The remaining content is organized as follows: Section II, notations, basic
concepts of a Bayesian network, and its interpretability with causal reasoning
are presented. We introduce these novel heuristics, while the specifications
of the algorithms and the soundness of our approach with proofs are presented
in Sections III and IV, respectively. Experimental studies, prospective
discussions, and the conclusion are presented in Sections V, and VI
respectively.

##  II Background and Related Works

###  II-A Basic Knowledge

Given a set of variables $\textbf{X}=(X_{1},...,X_{n})$, where $n\geq 1$, the
Bayes theorem allows us to decompose the joint probability distribution of
these variables into a product of conditional probabilities. Throughout the
paper, a variable set by bold uppercase (e.g. X ), a single variable by non-
bold upper character (e.g. $X$), and their assignments by lowercase (e.g.
$\textbf{X}=\textbf{x},X=x$ ). A Bayesian network for $\mathbf{B}$ is defined
as a pair $\mathbf{B=(G,\Theta)}$, where $G$ is a directed acyclic graph (DAG)
with nodes corresponding to the random variables in $\mathbf{U}$. G=(V, A)  is
a DAG, G in which V corresponds to U, and an arc A contains the connectivity
information among V. If there exists a directed arc from node $X$ to node $Y$,
we say that $X$ is a parent of $Y$, and $Y$ is a child of $X$. Nodes $X$ and
$Y$ are considered neighbors if they are either parents or children of each
other. The parameters $\theta$ represent the conditional probability
distribution of each node $X\in\mathbf{B}$ given its parents. Parameter set
$\mathbf{\Theta}$ contains
$\mathbf{\Theta}_{x_{i}|Pa(x_{i})}=P(x_{i}|\textbf{Pa}(x_{i}))$, each of which
describes the conditional probability of the assignment $x_{i}$ given the
assignment $\textbf{Pa}(x_{i})$ to its parents. For those without parents,
prior probability $P(x_{i})$ is used instead. The joint probability
distribution as represented by a BN, B can be factorized below:

$P(X_{1},X_{2},..,X_{n})=\Pi_{i=1}^{n}P(X_{i}|\textbf{Pa}(X_{i}))$ (1)

Additionally, we define a path between nodes $X$ and $Y$ as any sequence of
nodes such that consecutive nodes are connected by directed arcs, and no node
appears in the sequence more than once. A directed path in a DAG is a path
where nodes $(X_{1},\ldots,X_{n})$ satisfy $1\leq i\leq n$ and $X_{i}$ is a
parent of $X_{i+1}$. If there exists a directed path from node $X$ to node
$Y$, we say that $X$ is an ancestor of $Y$ and $Y$ is a descendant of $X$.
Nodes $X$, $Y$, and $Z$ form a v-structure if node $Z$ has two incoming arcs
from $X$ and $Y$, but $X$ and $Y$ are not adjacent. This v-structure is
denoted as $X\rightarrow Z\leftarrow Y$, where $Z$ is a collider. In the
remainder of the paper, $|X|$ is used to denote the size of set $\mathbf{X}$.
The notation $X\perp Y\mid\mathbf{Z}$ represents the conditional independence
between $X$ and $Y$ given $\mathbf{Z}$, while $X\not\perp Y\mid\mathbf{Z}$
represents their conditional dependency.

###### Definition 1

( Markov Assumption ) A node in a BN is independent of its non-descendant
nodes, given its parents.

###### Definition 2

( Faithfulness Assumption ) A Bayesian Network $G$ and a joint distribution
$P$ are faithful to one another iff. every (conditional) independence relation
entailed by $P$ is also present in $G$.

###### Definition 3

( Blocked Path ) A path $S$ from $X$ to $Y$ is blocked by a set of nodes
$\mathbf{Z}$ if one of the following conditions holds true:

  * •

There is a non-collider node in $S$ belonging to $\mathbf{Z}$;

  * •

There is a collider node Z on $S$ such that neither $Z$ non any of its
descendants belong to $\mathbf{Z}$.

Otherwise, the path $S$ is known as _unblocked_ or _active_.

###### Definition 4

( d-Separation ) Two nodes $X$ and $Y$ are d-separated by a set of nodes
$\mathbf{Z}$ iff. every path from $X$ to $Y$ is blocked by $\mathbf{Z}$.

Such a set $\mathbf{Z}$ is called a _d-seperator_ of $X$ from $Y$, denoted as
$\mathbf{DS}(X,Y)$.

###### Theorem 1

Two nodes are adjacent iff. there exists no set $\mathbf{Z}$ such that $X\perp
Y\mid\mathbf{Z}$ and $X,Y\not\in\mathbf{Z}$.

###### Lemma 2

Two nodes are not adjacent if there exists set $\mathbf{Z}$ such that $X\perp
Y\mid\mathbf{Z}$.

###  II-B Causality based Reasoning

Methods of probabilistic reasoning have been developed to assist data
scientists in understanding the dependencies among variables, allowing for the
exploration of evidence needed for prognostic and diagnostic reasoning in
decision-making systems. Bayesian networks have emerged as a valuable
framework for representing the relationships between evidence and a target of
interest, leveraging probabilistic properties to handle uncertainty in
knowledge [13, 14, 15]. Within a Bayesian network, probabilistic reasoning can
be employed to account for direct causal influences originating from parent
nodes that impact a specific variable $X_{i}$. This allows for the following
lines of reasoning:

  1. 1.

In prognostic reasoning, the occurrence of an effect variable is influenced by
a direct cause, represented by the parent variable $\textbf{Pa}(X_{i})$. This
means that if we have information about the cause variable, we can make
predictions or inferences about the likelihood of the effect variable
occurring. Prognostic reasoning is commonly used for prediction purposes,
utilizing conditional probability tables associated with the target variable.

  2. 2.

Diagnostic reasoning in Bayesian networks involves inferring the probable
causes or factors that contributed to the occurrence of an effect variable,
based on the knowledge that the effect has already occurred. This type of
reasoning involves reasoning against the causal direction and is useful for
determining likely causes based on observed effects.

Figure 2: Illustration of prognostic and diagnostic reasoning in Bayesian
networks.

###  II-C Related Works

Constraint-based learning algorithms in Bayesian networks play a crucial role
in uncovering the dependencies between variables. Algorithms of constraint-
based learning rely on conditional independence (CI) tests (e.g. ${\chi}^{2}$
test), and they require enough samples to ensure the reliability of CI tests.
At least five samples available per cell of the conditional probability table
(CPT) is a widely accepted criterion [6]. The majority of these algorithms
assume faithfulness and utilize exact conditional independence (CI) tests,
without requiring any specific ordering of nodes. Representative works in this
category include the SGS algorithm and its updated version, the PC algorithm
[6]. The PC algorithm is specifically designed to avoid conducting high-number
CI tests. Another algorithm, the IC algorithm [16], shares similarities with
PC algorithm and was proposed by Pearl et. al during the same period. The GSBN
algorithm, available in both original and random versions [17], follows the
design of the SGS algorithm but relies on a sub-routine called GSMB to induce
local neighborhoods. Although the time complexity of GSMB is polynomial,
achieving acceptable results with this algorithm requires a large number of
samples. There are a series of algorithms like GSMB those focus on only
inducing the Markov blanket of the target variable. Those include Max-Min
Parents and Children/MB [18], HILTON-PC/MB [19], Parents and Children based
Markov Boundary [20], Iterative Parents and Children based Markov Blanket
[21], and Markov Boundary search using the OR condition [22]. These algorithms
mentioned aim to identify relevant features for the target variable using
partially directed structures and CI tests, similar to the PC algorithm.
However, their focus is solely on discovering the Markov blanket (MB) of a
specific target variable in BNs for feature selection. It is worth considering
that the proposed heuristics in this manuscript may be applicable to other
structure learning scenarios and the induction of Markov blankets that also
utilize CI tests. It is important to note that each category of constraint-
based learning algorithms has its own strengths and limitations, and the
choice of algorithm depends on factors such as available data, network
complexity, and desired accuracy and time efficiency.

In order to improve the time efficiency of constraint-based learning methods
for BNs, some approaches require the specification of node order, which
entails stricter assumptions or expert judgment. The use of node order
information can significantly reduce the search space and improve time
efficiency. One early attempt in this direction was made by Wermuth and
Lauritzen [23], but the Three-phase dependency algorithm (TPDA) by Cheng et.
al [24] is more widely recognized. TPDA relies on the assumption of “monotone
faithfulness” and achieves an acceptable time complexity of $O(n^{4})$.
Another algorithm, Polynomial Max-Min Skeleton (PMMS) [25], achieves a similar
time complexity with the same assumption. However, it has been shown by
Chickering et al. [26] that the assumption of monotone faithfulness is not
valid in many cases. Therefore, algorithms in this subgroup are not considered
in this study.

Most of the algorithms mentioned earlier are focused on learning the skeleton
or structure of the target networks, without determining the orientation of
the edges. Additional rules or methods are required to establish the correct
directionality of the edges. In general, the algorithms first identify the
v-structures (or colliders) in the network, and then the remaining edges are
arbitrarily oriented, as long as directed cycles are not introduced. The
ultimate goal is to recover a model that accurately captures the underlying
joint probability distribution (JPD). However, achieving a perfect match
between the model and the true JPD is challenging due to two main factors:
time efficiency and limited quality samples.

Time efficiency refers to the computational challenges in accurately inferring
the correct orientations of the edges, especially in larger networks. This
complexity increases exponentially with the number of variables and can be a
significant hurdle in achieving the ideal model. The limited number of
available samples also poses a challenge. Insufficient data or bad quality
data leads to incomplete information about the dependencies and relationships
among variables, making it difficult to determine the orientations accurately.
Algorithms alone cannot overcome this limitation since the underlying issue is
the lack of comprehensive information. Considering these challenges, while it
is desirable to recover a model that perfectly matches the underlying JPD, it
is often not feasible in practice due to the aforementioned factors.

Nonetheless, the algorithms play a crucial role in approximating the true
structure and providing valuable insights into the relationships among
variables, even with the inherent limitations imposed by time efficiency and
limited quality data samples.

##  III Structure Induction Algorithm Using Topology Information

Our work follows an overall strategy of recovering a BN from data samples
through a series of local neighbor inductions. During the induction process,
we employ a “backward selection” approach, assuming that a node $X$ is
connected to every other node $Y\in\mathbf{V}\setminus{X}$ and then
eliminating false connections based on the presence of a d-separation
($\mathbf{DS}(X,Y)$). This backward selection technique, initially introduced
in the PC algorithm, helps to keep the size of conditioning sets as small as
possible. This, in turn, improves the reliability of conditional independence
(CI) tests and enhances the overall learning quality. However, in previous
works such as PC, all CI tests are treated equally and conducted randomly
until a test reveals a conditional independence relation or no more tests
remain. This approach can result in a significant number of fruitless CI
tests. To address this issue, we propose two measures to quantify the
likelihood of a test being able to uncover the desired CI relation. These
measures are then utilized to develop two algorithms for the efficient
recovery of BNs.

###  III-A Search heuristics

In the context of the same dataset and two algorithms, A and B, if algorithm A
achieves a more accurate outcome compared to B, it can be considered more
“data efficient”. Among the existing constraint-based algorithms, the PC
algorithm is recognized as the most data-efficient. The PC algorithm employs a
strategy where it starts with an empty conditioning set and progressively
expands it. This means that CI tests with smaller conditioning sets are given
priority. However, while this strategy may be efficient to some extent, there
is still room for improvement. One possible limitation is that it may not
always be the most efficient approach. To address this, our work aims to
enhance the PC algorithm by extracting and utilizing topology information that
is hidden within the previously performed CI tests. By doing so, we can
potentially improve the overall efficiency of the algorithm and further
enhance its data efficiency.

####  III-A1 Search heuristic I

_During the process of searching for neighbors of node $X$, we observe that
certain nodes, such as node $Z$, may frequently appear in d-separators. Based
on this observation, we can infer that node $Z$ has a higher likelihood of
being selected as a candidate d-separator._

Figure 3: Illustration of selection diagrams depicting differences between
heuristic I (a) and heuristic II (b).

We can demonstrate the functionality of heuristic I using the network shown in
Figure 3 (a). In order to determine whether there is no connection between
nodes $X$ and $Y$, we need to identify the presence of a d-separator.
Initially, the empty set is not considered a valid d-separator.

When examining d-separators of size 1, there are six potential sets to
consider: ${Z}$, ${M}$, ${O}$, ${P}$, ${N}$, and ${Q}$. In the original PC
algorithm, any of these sets may be chosen with equal probability. In the
worst-case scenario, ${Z}$ could be the last set to be evaluated, resulting in
a total of six CI tests. However, if we were able to select ${Z}$ as the first
candidate, we could save the remaining five CI tests. This represents an 83%
reduction in computation compared to the worst-case scenario. Therefore, our
objective is to identify the most likely candidate set to be a d-separator. To
accomplish this, we introduce a quantitative measure called the _relative
d-separating ability (RDSA)_. For each node $X$, the RDSA of each node
$Y\in\mathbf{V}\setminus{X}$ is initially set to 0. Whenever a d-separator
$\mathbf{S}$ is discovered, the RDSA of each node $Z\in\mathbf{S}$ is updated
as follows:

$\forall Z\in\mathbf{S},\mathbf{RDSA}^{Z}_{X}=\mathbf{RDSA}^{Z}_{X}+1$ (2)

####  III-A2 Search heuristic II

_Sets with a higher number of nodes having a high RDSA value should be
prioritized during the search process to improve the efficiency of identifying
d-separators._

Correspondingly we define the RDSA of a set $\mathbf{S}$ as summing up the
RDSA of individuals as contained in $\mathbf{S}$ as below

$\mathbf{RDSA}^{\mathbf{S}}_{X}=\sum_{Y\in\mathbf{S}}\mathbf{RDSA}^{Y}_{X}$
(3)

We will demonstrate the effectiveness of these two measures by reusing the
example mentioned above. After searching for the d-separator of size 1, ${Z}$
is identified as a d-separator, and $\mathbf{RDSA}^{Z}_{X}$ is updated to 1
according to Equation 2. During the search for the d-separator of $X$ and $M$,
the set $\\{\textbf{Z}\\}$ is selected first due to its higher
$\mathbf{RDSA}^{Z}_{X}$ value. Since $\\{\textbf{Z}\\}$ indeed serves as the
d-separator for $X$ and $M$, the remaining CI tests can be disregarded, and
$\mathbf{RDSA}^{Z}_{X}$ is incremented to 2. By continuing the search in this
manner, the RDSA values of all $Y\in\mathbf{V}\setminus{X}$ are dynamically
updated. Utilizing these values during the selection of candidate d-separators
leads to a significant reduction in computational complexity, forming the
foundation of the FSBN (Fast Search of BN) algorithm to be introduced in the
next section.

####  III-A3 Search heuristic III

_The relative contribution of a node $X$ in a d-separator $S$ is expected to
be less significant compared to its occurrence in a smaller d-separator._

Given the network shown in Figure 3 (b), in order to d-separate $Y$ from $X$,
we require a set that includes at least ${Z,M}$. However, the set ${Z}$ is
sufficient to d-separate $X$ and $N$. To measure the RDSA in a more detailed
manner, we propose the concept of _weighted RDSA_ , and its updating rule is
as follows:

$\forall
Z\in\mathbf{S},\mathbf{RDSA}^{Z}_{X}=\mathbf{RDSA}^{Z}_{X}+1/|\mathbf{S}|$ (4)

Equation 4 represents one possible implementation of heuristic III, which is
utilized in the SSBN algorithm (Smart Search of BN). However, in SSBN, the
calculation of RDSA for a set remains unchanged. It is hypothesized that there
exist more advanced or smarter approaches for measuring the RDSA of a node or
set, going beyond the simple strategy employed in FSBN. As a result, SSBN is
proposed independently, even though it shares the same overall architecture as
FSBN.

##  IV Algorithm Specification

####  IV-1 FSBN (Fast Search of BN)

is constructed based on heuristic I and II, and it utilizes LSPC (Local Search
of Parents/Child) to generate local neighbors for each node $X\in\mathbf{V}$.
In this implementation, FSBN employs two global containers, $\mathbf{A}_{Ind}$
and $\mathbf{A}_{Del}$, to store induced disconnection and connection
information in the format of $X-Y$.

The crucial component of FSBN is LSPC. When LSPC is called on node $T$, it
assumes $T$ is connected to all nodes $X\in\mathbf{V}$, excluding pairs like
$T-X$ that are stored in $\mathbf{A}_{Del}$. This prevents redundant analysis
of pairs already known to be disconnected. Within LSPC, it starts with an
empty set and iteratively grows it. Candidate d-separators of size $dss$ are
generated using $\mathbf{GenSortDS}$, sorted in descending order based on
their RDSA values. When a d-separator $\mathbf{S}$ is found (Line 11), the
following steps are performed:

  1. 1.

$X$ is excluded from the neighbor set $\mathbf{V}_{CanPC}$ (Line 12);

  2. 2.

$X-Y$ is removed from both $\mathbf{A}_{Can}$ and $\mathbf{A}_{Del}$ (Line 13
and 14);

  3. 3.

The RDSA of each $Y\in\mathbf{S}$ is updated based on Equation 2 (Line 16);

  4. 4.

The analysis of node $X$ is terminated (Line 17), and the next node in
$\mathbf{V}_{CanPC}$ is processed

To save space, the explicit presentation of GenSortDS is omitted. It generates
all possible subsets of $\mathbf{V}_{CanPC}$ of size $dss$, calculates their
corresponding $\mathbf{RDSA}$ values according to Equation 3, and sorts them
in descending order.

$\begin{array}[]{l}\hline\cr\textbf{FSBN}(\textbf{D}\colon Dataset)\\\
01\hskip 8.5359pt{\textbf{A}_{Ind}}={\textbf{A}_{Del}}=\emptyset\\\ 02\hskip
8.5359ptfor\hskip 2.84544pt(\forall X\in\textbf{V})\hskip 2.84544ptdo\\\
03\hskip
17.07182pt{\textbf{A}_{Can}}=\\{X-Y|Y\in\textbf{V}\setminus\\{X\\}\\}\setminus\textbf{A}_{Del}\\\
04\hskip 17.07182pt{\textbf{A}_{Ind}}={\textbf{A}_{Ind}}\cup\hskip
2.84544pt\emph{{LSPC}}(X,\textbf{D},{\textbf{A}_{Can}},{\textbf{A}_{Del}})\\\
05\hskip 8.5359ptApply\hskip 2.84544ptorientation\hskip 2.84544ptrules\hskip
2.84544pton\hskip 2.84544pt{\textbf{A}_{Ind}}\\\ \hline\cr\end{array}$

$\begin{array}[]{l}\hline\cr\textbf{LSPC}(T,\textbf{D},{\textbf{A}_{Can}},{\textbf{A}_{Del}})\\\
01\hskip 8.5359ptdss=0;\\\ 02\hskip
8.5359pt{\textbf{V}_{CanPC(T)}}=\\{X|(T-X)\in{\textbf{A}_{Can}}\\};\\\
03\hskip 8.5359pt{\textbf{RDSA}^{X}_{T}}=0,\forall X\in\textbf{V}_{CanPC};\\\
04\hskip 8.5359ptwhile\hskip 2.84544pt(|{\textbf{V}_{CanPC}}|>dss)\hskip
2.84544pt\hskip 2.84544ptdo\\\ 05\hskip 34.14322ptfor\hskip 2.84544pt(\forall
X\in{\textbf{V}_{CanPC(T)}})\hskip 2.84544ptdo\\\ 06\hskip 51.21504ptif\hskip
2.84544pt(dss>0)\\\ 07\hskip
59.75095pt\textbf{SS}=\textbf{GenSortDS}({\textbf{V}_{CanPC(T)}},dss,\textbf{RDSA}_{T});\\\
08\hskip 51.21504ptelse\\\ 09\hskip 59.75095pt\textbf{SS}=\emptyset;\\\
10\hskip 51.21504ptfor\hskip 2.84544pt(\forall\hskip
2.84544pt\textbf{S}\in{\textbf{SS}})\hskip 2.84544ptdo\\\ 11\hskip
65.44142ptif\hskip 2.84544pt(\emph{{I}}_{D}(T,X|\textbf{S})\geq
1-\varepsilon)\hskip 2.84544ptthen\\\ 12\hskip
79.6678pt{\textbf{V}_{CanPC(T)}}={\textbf{V}_{CanPC(T)}}\setminus\\{X\\};\\\
13\hskip 79.6678pt{\textbf{A}_{Can}}={\textbf{A}_{Can}}\setminus\\{T-X\\};\\\
14\hskip 79.6678pt{\textbf{A}_{Del}}={\textbf{A}_{Del}}\cup\\{T-X\\};\\\
15\hskip 79.6678ptif\hskip 2.84544pt(|\textbf{S}|>0)\\\ 16\hskip
91.04872pt\forall\hskip 2.84544ptY\in\textbf{S},\hskip
2.84544pt\textbf{RDSA}^{Y}_{T}++;\\\ 17\hskip 79.6678ptbreak;\\\ 18\hskip
34.14322ptdss++;\\\ 19\hskip 8.5359ptreturn\hskip
2.84544pt{\textbf{A}_{Can}};\\\ \hline\cr\end{array}$

####  IV-2 SSBN (Smart Search of BN)

The overall architecture of SSBN is the same as FSBN, with the only difference
being in Line 16 of LSPC, specifically the updating of RDSA for each node $X$
appearing in the d-separator $\mathbf{S}$. SSBN is designed based on heuristic
III, thus it updates RDSA using Equation 4. The experimental study in the next
section demonstrates that SSBN is significantly more efficient than FSBN.

###  IV-A Proof of Soundness

The primary task of BN structure learning is to induce the skeleton of the
target BN. Therefore, in our study, we focus on proving that both FSBN and
SSBN will generate the correct skeleton. Both algorithms rely on the
assumption of faithfulness and the use of accurate CI tests.

###### Lemma 3

LSPC will not remove $X-Y$ if it truly exists in the target network.

Assuming that a true edge $X-Y$ is included in $\mathbf{Z}_{Ind}$ implies that
there exists a set of variables on which the conditional independence between
$X$ and $Y$ holds. However, this contradicts Theorem 1, which states that in a
BN, there should be a direct edge between any two non-independent variables.
Therefore, the inclusion of a true edge $X-Y$ in $\mathbf{Z}_{Ind}$ is not
consistent with the underlying structure of a BN.

###### Lemma 4

The edge $X-Y$ determined to be false in _LSPC( $X$)_ can be put into
$\mathbf{A}_{Del}$, and be ignored in the call of _LSPC( $Y$)_.

According to the commutative law of probability, if variables $X$ and $Y$ are
independent ($X\perp Y$), then it follows that $Y$ is also independent of $X$
($Y\perp X$). This property holds in probabilistic independence relationships,
allowing us to interchange the positions of variables without affecting their
independence, and if $X\not\perp Y$ then $Y\not\perp X$.

###### Lemma 5

The edge $X-Y$ determined to be left in $\mathbf{A}_{Ind}$ by _LSPC(X)_ may
actually be false.

Lemma 2 states that nodes directly connected to $X$, including its parents
denoted as $\mathbf{Pa}(X)$, will always be present in $\mathbf{V}_{CanPC}$.
By the Markov condition, when $dss=|\mathbf{Pa}(X)|$, all non-descendant nodes
will be removed from $\mathbf{V}_{CanPC}$ along with the corresponding edges.
However, there may be cases where the edges between $X$ and its descendants
fail to be removed from $\mathbf{A}_{Ind}$.

###### Lemma 6

False edge $X-Y$ left in $\mathbf{A}_{Ind}$ after the call of _LSPC( $X$)_
will be removed during the call of _LSPC( $Y$)_.

Based on Lemma 5, we know that false edges only exist between node $X$ and
it’s descendant $Y$. It is important to note that $X$ can never be a
descendant of $Y$ in the BN structure.

During the execution of _LSPC(X)_ , the set $\mathbf{V}_{CanPC}$ is
constructed to include all nodes connected to $X$, excluding pairs like $X-Y$
that are stored in $\mathbf{A}_{Del}$. Since $X$ is not a descendant of $Y$,
$Y$ will not be included in $\mathbf{V}_{CanPC}$.

Therefore, when _LSPC(X)_ is called, the false edge $X-Y$ will not be
considered as a candidate d-separator, and it will not be added to
$\mathbf{A}_{Ind}$. Consequently, the false edge $X-Y$ will be successfully
removed from $\mathbf{A}_{Ind}$ during the execution of _LSPC(X)_.

###### Lemma 7

True edges left in $\mathbf{A}_{Ind}$ after the call of _LSPC(X)_ will still
be found in $\mathbf{A}_{Ind}$ after the call of _LSPC(Y)_.

We will prove that FSBN and SSBN will produce the correct BN structure by
considering the following points:

Lemma 3 and Lemma 7 guarantee that true edges will not be wrongly deleted
during the execution of FSBN. Lemma 3 ensures that true edges will be
correctly identified as d-separators, while Lemma 7 ensures that true edges
will not be mistakenly removed from $\mathbf{A}_{Ind}$.

Lemma 4 and Lemma 6 demonstrate that false edges, if present in
$\mathbf{A}_{Ind}$, will be successfully removed during the execution of FSBN.
Lemma 4 ensures that false edges between non-descendant nodes are removed
during the LSPC process, while Lemma 6 ensures that false edges between a node
$X$ and its descendant $Y$ will be removed when _LSPC(Y)_ is called. The
search process in FSBN is applied to each node individually. This means that
each node is considered as the starting point of the LSPC process, ensuring
that the correct d-separators and edges are identified for each variable.

By considering these points, we can conclude that FSBN and SSBN will produce
the correct BN structure. It ensures that true edges are preserved, false
edges are removed, and the search is performed for each node individually.
Therefore, these two algorithms are capable of recovering the correct BN based
on the given data, under the assumptions of faithfulness and correct CI tests.

##  V Experimental Study

###  V-A Settings

Two classic well-known real networks, namely Asia and Alarm, are selected,
along with two synthetic larger networks, 100_130 and 200_250, which were
synthetically generated using the BN package of Weka. These networks are
chosen for comparison purposes (Table I). To evaluate the performance and
robustness of the proposed methods, we conducted experiments by randomly
generating samples from each of the four networks. We varied the population
sizes across a range of values, specifically from 1000 to 5000. For each
population size, we generated 10-fold datasets, ensuring a diverse and
representative set of samples in our experiment.

TABLE I: Description of data sets Data set(s) | # Instances | # Nodes | # Arcs
---|---|---|---
Asia | 1K to 5K | 8 | 8
Alarm | 1K to 5K | 37 | 46
100_130 | 1K to 5K | 100 | 130
200_250 | 1K to 5K | 200 | 250

Only PC algorithm is chosen for comparison considering:

  1. 1.

Most well-known and theoretically sound [27],

  2. 2.

Most data efficient methods among constraint-based learning algorithms [10],

  3. 3.

Monotone assumption required by a subgroup of algorithms like TPDA and PMMS is
proved not practical [26],

  4. 4.

FSBN and SSBN have the same assumptions as PC and all methods apply
${\chi}^{2}$ test as conditional independence test.

All the algorithms are implemented within the Weka framework, and the PC
algorithm implemented in Weka is used directly. For each experiment, we
calculated and reported average performance metrics. These metrics provided an
overall assessment of the network’s performance across the different folds and
population sizes. The evaluation is performed based on the following four
dimensions:

_Knowledge discovery-oriented learning quality_ : Each edge is treated equally
in knowledge discovery, regardless of the strength of the encoded dependency
relation. The ideal measure for this task is the  _Hamming distance_ [28],
which is defined as the number of actions required to transform the learned
network into the target network. The allowed actions include adding, deleting,
and reversing edges.

_Density estimation-oriented learning quality_ : This dimension aims to assess
the quality of the global network, distinct from knowledge discovery, by
considering the marginal likelihood of the training data over the parameter
distribution for the candidate network. To measure this, the Bayesian
Dirichlet likelihood-equivalent uniform joint distribution [29, 30] _BDeu
score_ is employed. The _BDeu score_ enables a comparison between the output
network and the structure of the true underlying model, assuming that the real
network is known. It provides a means to evaluate the fit of the candidate
network to the training data in terms of the underlying model’s structure.

_Time efficiency_ : The time efficiency is measured by calculating their
computational complexity in this study and is derived from the summation of
weights associated with each executed conditional independence test.
Specifically, the weight assigned to the test $I_{D}(X,Y|\mathbf{Z})$ is
defined as $2+|\mathbf{Z}|$. This weight-based approach serves as a standard
method for comparing conditional independence test-based algorithms [31]. It
is justified by the observation that the runtime of a statistical test on a
triplet $(X,Y|\mathbf{Z})$ is directly proportional to the size of the dataset
and the number of variables involved. Notably, the time complexity of the test
is $O(N(|\mathbf{Z}|+2))$ ( without exponential growth according to the number
of variables, which a naive implementation might wrongly assume). The reason
behind being able to construct all non-zero entries in the contingency table
used by the test by examining each point in the dataset exactly once is that
it can be done in a time proportional to the number of variables involved in
the test. Specifically, the time required is proportional to the sum of the
cardinality of the set X, Y and the set Z, which can be expressed as
$|{X,Y}+\textbf{Z}|=2+|\textbf{Z}|$. This property stems from the nature of
the conditional independence test and its relationship to the contingency
table. This efficiency measure is machine-independent, allowing for the
evaluation of computing costs across various observed quality levels.
Synthetic data sets are utilized in this study to provide insights into the
corresponding computational expenses under different quality conditions.

_Influence of network density_ : Increasing the density of the network results
in a higher-dimensional solution space, which may transform a feasible problem
into an infeasible one. Studying the influence of denser networks helps
determine the effectiveness of the newly proposed search heuristics.

These four dimensions provide a comprehensive evaluation of the algorithms.

###  V-B Quality of Knowledge Discovery

Figure 4 depicts the knowledge discovery quality of the PC, FSBN, and SSBN
algorithms. It shows the number of actions required to transform the induced
network into the true network. PC and FSBN exhibit similar performance, with
low Hamming Distances indicating a close resemblance to the true network, and
observed that FSBN achieves nearly the same quality of networks as the PC
algorithm. SSBN shows slightly poorer performance compared to the other two
algorithms, but it closes the gap with FSBN and PC as the network size
increases. For instance, when applied to the Alarm network, the accuracy rate
of SSBN is 91.37% (3.97/46) (which means it requires correction of average
3.97 arcs in an alarm network with 46 arcs), but it improves to 96.86%
(4.09/130) and 97.92% (5.20/250) for the 100_130 and 200_250 networks,
respectively. Therefore, both FSBN and SSBN perform well enough in the
knowledge discovery task.

Figure 4: The Hamming Distance between the true networks and the induced
networks by PC, FSBN, and SSBN (Note that the values on the Y-axis vary for
each graph in this figure).

###  V-C Quality of Density Estimation

Figure 5 illustrates the quality of the density estimation task achieved by
PC, FSBN, and SSBN. The results show that all three algorithms perform
comparably well across different sample sizes and network structures. This
indicates that the newly proposed heuristics in FSBN and SSBN are effective in
producing accurate density estimates. The similarity in performance among the
algorithms further supports the conclusion drawn from the knowledge discovery
task, highlighting the effectiveness of the proposed heuristics in producing
satisfactory results.

Figure 5: Quality of density estimation (_BDeu score_) about PC, FSBN, SSBN,
and true networks (Note that the values on the Y-axis vary for each graph in
this figure).

###  V-D Time efficiency

Figure 6: Computational complexity of PC, FSBN, and SSBN to induce given
networks (Note that the values on the Y-axis vary for each graph in this
figure).

Figure 6 showcases the relative time efficiency achieved by PC, FSBN, and
SSBN. The following observations can be made:

  1. 1.

FSBN and SSBN demonstrate a clear advantage over the PC algorithm in terms of
time efficiency. For instance, when applied to a dataset of 5,000 samples from
the 200_250 network, PC requires an average of 166,771 weighted CI tests. In
contrast, FSBN and SSBN only require 79,446 and 47,569 tests, respectively,
representing a reduction of 52.4% and 71.5% in the number of tests needed.

  2. 2.

SSBN exhibits greater time efficiency compared to FSBN, despite both
algorithms sharing the same overall framework. For example, when applied to
the 200_250 network, SSBN requires 40.1% fewer CI tests than FSBN.

  3. 3.

With an increase in the number of samples, all three algorithms experience an
increase in the number of CI tests required. However, the rate of increase is
significantly slower for SSBN compared to the other two algorithms.

These results demonstrate that both FSBN and SSBN offer improved time
efficiency compared to the PC algorithm, with SSBN exhibiting the highest
level of efficiency among the three algorithms, particularly as the number of
samples increases.

###  V-E Influence of Network Density

In the experiment, a synthetically produced 100 nodes network was used with a
fixed number of nodes but varying numbers of edges to simulate different
network densities (as shown in Table II). The results are presented in Figures
7, 8, and 9 for the comparison of knowledge discovery, density estimation, and
time efficiency.

TABLE II: Description of data sets Data set(s) | # Instances | # Nodes | # Arcs
---|---|---|---
100-I | 1K to 4K | 100 | 130
100-II | 1K to 4K | 100 | 200
100-III | 1K to 4K | 100 | 300
100-IV | 1K to 4K | 100 | 400

Figure 7: Hamming distance about PC, FSBN, and SSBN to true networks with
various densities.
Figure 8: Quality of density estimation (_BDeu score_) about PC, FSBN, and
SSBN and true networks with various densities (Note that the values on the
Y-axis vary for each graph in this figure).
Figure 9: Computational complexity of PC, FSBN and SSBN to induce given
networks with various densities (Note that the values on the Y-axis vary for
each graph in this figure).

The following observations can be made:

  1. 1.

All three algorithms (PC, FSBN, and SSBN) maintain a consistent level of
learning quality even as the network density increases. This indicates that
the proposed heuristics in FSBN and SSBN are effective in discovering the
network structure, and they perform well in capturing the dependencies between
variables.

  2. 2.

Similarly, all three algorithms demonstrate comparable performance in density
estimation as the network density increases. This suggests that the learning
quality of the algorithms is not significantly affected by the density of the
network.

  3. 3.

As expected, all three algorithms require more CI tests as the number of edges
increases in denser networks. However, SSBN exhibits a much slower growth rate
in the number of CI tests compared to PC and FSBN. This indicates that SSBN is
more efficient in terms of time consumption, particularly in denser networks.

Overall, the results indicate that all three algorithms (PC, FSBN, and SSBN)
maintain consistent learning quality as the network density increases.
However, SSBN demonstrates superior time efficiency compared to PC and FSBN,
making it a promising approach for learning the structure of denser networks.

##  VI Conclusion

The novel search heuristics proposed in FSBN and SSBN utilize the topology
information obtained from previously executed CI tests to guide future
searches. These algorithms have been proven to be sound and effective.
Experimental studies demonstrate that they can achieve comparable results in
terms of learning quality as the classical PC algorithm but with significantly
reduced computational resources. SSBN, in particular, shows even greater
efficiency than FSBN, especially in denser networks, indicating its potential
for solving larger-scale problems.

FSBN and SSBN highlight the untapped potential for enhancing traditional
constraint learning algorithms by leveraging the underlying topology
information. Future research in this area could focus on better utilization of
such information. For instance, the RDSA of a node $X$ showing a relative
degree of separation of ancestors, determined during the search for its
neighbors, is currently not utilized in the study of other nodes’ neighbors.
If methods can be developed to transfer and incorporate this type of
information, further improvements in time efficiency can be achieved.

Thus, the FSBN and SSBN algorithms have great potential for building causal
local surrogate models for black-box models and detecting concept/data drift
in the era of big data. Future research can investigate techniques that target
the reduction of computational burden in diverse application domains. This can
be achieved by focusing on the following directions: Causal Local Surrogate
Models: Black-box models, such as deep neural networks, often lack
interpretability, making it challenging to understand the underlying causal
relationships and provide explanations with the help of Markov blanket for
their predictions [32, 33, 34]. FSBN and SSBN can assist in building causal
local surrogate models that approximate the behavior of the black-box model in
a local region of the input space. These surrogate models, represented as BNs,
capture the causal relationships among variables and provide interpretable
explanations for the predictions made by the black-box model. They allow us to
understand how changes in the input variables affect the output and provide
insights into the decision-making process of the black-box model. Concept/Data
Drift Detection: In the era of big data, where the underlying data
distribution may change over time, it is crucial to detect concepts or data
drift quickly. Concept drift refers to the change in the underlying data-
generating process, while data drift refers to changes in the data
distribution itself. FSBN and SSBN can be applied to monitor the drift in the
causal relationships among variables. By periodically updating the learned
structure of the BNs and comparing it with the previous models, deviations or
changes in the causal relationships can be detected.

Overall, both algorithms of FSBN and SSBN have a high potential to assist in
building causal local surrogate models that can enhance our understanding of
complex black-box models, provide interpretability, and enable the detection
of changes in causal relationships over time. Those methods can also help to
identify when the black-box model’s assumptions are no longer valid or when
the data distribution has significantly changed, allowing for timely
adaptation and retraining of the models. This is particularly valuable in
domains where interpretability, trustworthiness, and adaptability to evolving
data are critical, such as healthcare, finance, and autonomous systems.

## References

  * [1] J. Pearl, _Probabilistic reasoning in intelligent systems: networks of plausible inference_. Morgan kaufmann, 1988.
  * [2] S. Fu, S. Minn, and Z. Li, “Structure learning algorithm for general multi-dimensional bayesian network classifiers,” _Journal of Computer Applications_ , vol. 34, no. 4, pp. 1083–1088, 2014.
  * [3] C. P. De Campos and Q. Ji, “Efficient structure learning of bayesian networks using constraints,” _The Journal of Machine Learning Research_ , vol. 12, pp. 663–689, 2011.
  * [4] S.-K. Fu, Z.-Q. Li, and S. Minn, “Accelerated structure learning for general multi-dimensional bayesian network classifier,” _Computer Science_ , 2015.
  * [5] S. Minn and S.-K. Fu, “Accelerating structure learning of bayesian network,” _Computer Science_ , 2016.
  * [6] P. Spirtes, C. N. Glymour, R. Scheines, and D. Heckerman, _Causation, prediction, and search_. MIT press, 2000.
  * [7] G. F. Cooper and E. Herskovits, “A bayesian method for the induction of probabilistic networks from data,” _Machine learning_ , vol. 9, pp. 309–347, 1992.
  * [8] W. Lam and F. Bacchus, “Learning bayesian belief networks: An approach based on the mdl principle,” _Computational intelligence_ , vol. 10, no. 3, pp. 269–293, 1994.
  * [9] D. Heckerman, D. Geiger, and D. M. Chickering, “Learning bayesian networks: The combination of knowledge and statistical data,” _Machine learning_ , vol. 20, pp. 197–243, 1995.
  * [10] K. Yu, X. Guo, L. Liu, J. Li, H. Wang, Z. Ling, and X. Wu, “Causality-based feature selection: Methods and evaluations,” _ACM Computing Surveys (CSUR)_ , vol. 53, no. 5, pp. 1–36, 2020.
  * [11] D. M. Chickering, D. Geiger, and D. Heckerman, “Learning bayesian network is np-hard,” _Microsoft Research_ , vol. 22, 1994.
  * [12] S. Fu, S. Minn, and M. C. Desmarais, “Towards the efficient recovery of general multi-dimensional bayesian network classifier,” in _Machine Learning and Data Mining in Pattern Recognition: 10th International Conference, MLDM 2014, St. Petersburg, Russia, July 21-24, 2014. Proceedings 10_. Springer, 2014, pp. 16–30.
  * [13] F. Taroni, A. Biedermann, P. Garbolino, and C. G. Aitken, “A general approach to bayesian networks for the interpretation of evidence,” _Forensic Science International_ , vol. 139, no. 1, pp. 5–16, 2004.
  * [14] S.-K. Fu, Z.-Z. Su, S. Minn, and T.-Y. Lv, “Accelerating the recovery of markov blanket using topology informatio,” _Computer Science_ , vol. 42(Z11), pp. 42–48, 2015.
  * [15] S. Minn, S.-k. Fu, T. Lv, and Y. Cai, “Algorithm for exact recovery of bayesian network for classification,” _Application Research of Computers_ , 2016.
  * [16] J. Pearl and T. S. Verma, “A theory of inferred causation,” in _Studies in Logic and the Foundations of Mathematics_. Elsevier, 1995, vol. 134, pp. 789–811.
  * [17] D. Margaritis and S. Thrun, “Bayesian network induction via local neighborhoods,” _Advances in neural information processing systems_ , vol. 12, 1999.
  * [18] I. Tsamardinos, C. F. Aliferis, and A. Statnikov, “Time and sample efficient discovery of markov blankets and direct causal relations,” in _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2003, pp. 673–678.
  * [19] C. F. Aliferis, I. Tsamardinos, and A. Statnikov, “Hiton: a novel markov blanket algorithm for optimal variable selection,” in _AMIA annual symposium proceedings_ , vol. 2003. American Medical Informatics Association, 2003, p. 21.
  * [20] J. M. Pena, R. Nilsson, J. Björkegren, and J. Tegnér, “Towards scalable and data efficient learning of markov boundaries,” _International Journal of Approximate Reasoning_ , vol. 45, no. 2, pp. 211–232, 2007.
  * [21] S. Fu and M. C. Desmarais, “Fast markov blanket discovery algorithm via local learning within single pass,” in _Advances in Artificial Intelligence: 21st Conference of the Canadian Society for Computational Studies of Intelligence, Canadian AI 2008 Windsor, Canada, May 28-30, 2008 Proceedings 21_. Springer, 2008, pp. 96–107.
  * [22] S. Rodrigues de Morais and A. Aussem, “A novel scalable and data efficient feature subset selection algorithm,” in _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part II 19_. Springer, 2008, pp. 298–312.
  * [23] N. Wermuth and S. L. Lauritzen, _R: Graphical and Recursive Models for Contingency Tables_. Eksp. Aalborg Centerboghandel, 1982.
  * [24] J. Cheng, D. A. Bell, and W. Liu, “Learning belief networks from data: An information theory based approach,” in _Proceedings of the sixth international conference on Information and knowledge management_ , 1997, pp. 325–331.
  * [25] L. E. Brown, I. Tsamardinos, and C. F. Aliferis, “A comparison of novel and state-of-the-art polynomial bayesian network learning algorithms,” in _AAAI_ , vol. 2005, 2005, pp. 739–745.
  * [26] D. M. Chickering and C. Meek, “Monotone dag faithfulness: A bad assumption,” _Microsoft Research. Redmond, WA: Microsoft Corporation_ , 2003.
  * [27] N. K. Kitson, A. C. Constantinou, Z. Guo, Y. Liu, and K. Chobtham, “A survey of bayesian network structure learning,” _Artificial Intelligence Review_ , pp. 1–94, 2023.
  * [28] R. W. Hamming, “Error detecting and error correcting codes,” _The Bell system technical journal_ , vol. 29, no. 2, pp. 147–160, 1950.
  * [29] W. Buntine, “Theory refinement on bayesian networks,” in _Uncertainty proceedings 1991_. Elsevier, 1991, pp. 52–60.
  * [30] Z. Liu, B. Malone, and C. Yuan, “Empirical evaluation of scoring functions for bayesian network model selection,” in _BMC bioinformatics_ , vol. 13, no. 15. BioMed Central, 2012, pp. 1–16.
  * [31] S. Minn, S.-k. Fu, and M. C. Desmarais, “Efficient learning of general bayesian network classifier by local and adaptive search,” in _2014 International Conference on Data Science and Advanced Analytics (DSAA)_. IEEE, 2014, pp. 385–391.
  * [32] M. T. Ribeiro, S. Singh, and C. Guestrin, “” why should i trust you?” explaining the predictions of any classifier,” in _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , 2016, pp. 1135–1144.
  * [33] M. Vu and M. T. Thai, “Pgm-explainer: Probabilistic graphical model explanations for graph neural networks,” _Advances in neural information processing systems_ , vol. 33, pp. 12 225–12 235, 2020.
  * [34] S. Minn, “Laplace: Probabilistic local model-agnostic causal explanations,” _arXiv preprint arXiv:2310.00570_ , 2023.


# Lightweight Encryption for the Low Powered IoT Devices

Muhammad Usman  Department of Computer Engineering, Chosun University,
Republic of Korea
Email<EMAIL_ADDRESS>
###### Abstract

The internet of things refers to the network of devices connected to the
internet and can communicate with each other. The term things is to refer non-
conventional devices that are usually not connected to the internet. The
network of such devices or things is growing at an enormous rate. The security
and privacy of the data flowing through these things is a major concern. The
devices are low powered and the conventional encryption algorithms are not
suitable to be employed on these devices. In this correspondence a survey of
the contemporary lightweight encryption algorithms suitable for use in the IoT
environment has been presented.

###### Index Terms:

Internet of things, privacy, security, IoT

##  I Introduction

The internet of things makes use of the existing global internet infra-
structure in order to connect the physical objects including devices, home
appliances and vehicles to name a few. The traditional fields of embedded
systems including the Radio-frequency identification (RFID), wireless sensor
networks (WSN) have all contributed towards building up and empower the IoT.
The IoT enables the objects and sensors to be identified uniquely on the
network and there are billions of such devices interconnected to each other.
According to an estimate, a revenue of more than $714$ billion will be
generated by the year $2022$ with more than $30$ billion connected devices to
the internet [1, 2]. The IoT is focused towards creating smart environments
and autonomous devices for use in constructing smart cities, smart
transportation and smart hospitals [3, 4]. New IoT applications are introduced
at a high pace, and the are generating huge amount of data that can have
security and privacy threat. Billions of devices connected to each other shall
pronounce the security related issues and shall expose the weaknesses in the
infrastructure. It has been predicted that if the security measures are not
taken into account, the attacks and malfunctions would outweigh the advantages
of IoT applications [5]. The things in the IoT environment are constrained due
to the limited battery life, size and computation, therefore, they cannot
support the existing security solutions. The traditional cryptography
algorithms and security schemes are insufficient for the ever evolving IoT
applications which require scalable and robust solutions [6, 7, 8]. This
requires the development of novel designs and architectures to effectively
deal with the security and privacy issues suitable for the resource
constrained devices in the IoT [9, 10, 11]. This correspondence is aimed to
review the security and privacy challenges in the IoT and survey the
contemporary lightweight cryptographic algorithms developed for the resource
constrained devices.

The rest of the paper is organized as follows: Section II presents the
security and privacy challenges in the internet of things, a review of
lightweight cryptography algorithms are presented in Section III and the paper
is concluded in Section IV.

##  II Security and Privacy Challenges in IoT

One of the aspect towards deployment of IoT at the root level is to ensure its
security. The proposed security solution must consider the resource
constrained devices i.e. they must be lightweight and should consume less
memory and computation power. Some of the lightweight solutions presented
recently does not take into consideration the inter-operability and
integration into the IoT. The interconnected devices have varied computational
capacity and operate on diversified protocols, thus the security models must
operate on the global standards [12]. Another issue in the IoT is that of the
privacy, which is the privilege of an individual or a device to define the
extent to which their data will be presented or shared with other elements on
the network. In the present situation where a large amount of data is
generated and is available on the network, the individual must have
appropriate control of their data that can be accessed by other entities. A
framework for the privacy support is yet to be developed by the researchers
that will provide scalability in the IoT. In the following section, the
security and privacy challenges are explicitly discussed.

###  II-A Security in IoT

The security refers to the protection of the devices and data in the IoT.
Different layers of IoT can be protected by implying different security
technologies. Some of the important security aspects in the IoT are
authentication, confidentiality, integrity and availability.

####  II-A1 Authentication

Authentication is vital requirement in the IoT, as it is sorely required to
keep the information away from the unauthorized devices and person.
Traditionally, the internet users authenticate themselves using the Secure
Socket Layers (SSL) through their browsers, where they present a secret key
(passwords). However, the mechanism of the passwords in the automated IoT
environment does not present a good solution. In the IoT, the devices are
usually connected to a central hub or gateway. Since the gateway is
responsible for the information exchange between the devices and cloud, the
authentication can be implied at the gateway to ensure the information is
transmitted to the authenticated device or user. By following proper
authentication protocols, it can be guaranteed that the information shall not
land into wrong hands. For the scenarios in the absence of gateway, where the
sensors themselves are responsible for the information exchange to and from
the cloud, lightweight authentication protocols are highly desirable [13, 14,
15].

####  II-A2 Confidentiality

The exchange of the private information between the billions of IoT devices
and their storage must possess confidentiality [16]. The components in the IoT
collaborating with each other in order to provide the desired service, are
vulnerable to the confidentiality attacks if an unauthorized access is made to
the sensitive information. Confidentiality being a primary concern, can be
ensured by employing an access control method or using a lightweight
encryption scheme.

####  II-A3 Integrity

Integrity refers to the protected data that is transmitted in its original
form, without being altered by the cyber criminals. Error detection techniques
such as cyclic redundancy check (CRC) can be utilized to ensure the uniqueness
of the message. Furthermore, Secure Hash Algorithm (SHA) are also regularly
used which is a mathematical algorithm to ensure the elements of the data are
unchanged. Suitable frameworks to provide integrity in the IoT environment are
thoroughly discussed in [17].

####  II-A4 Availability

In the IoT, the data must be available at all times to the authorized users.
Back-end cloud and storage devices must present the data, software service and
hardware whenever required. The software availability refers to the service
that has been given to the user to access or modify the information, whereas
the hardware availability refers to the availability of the gadgets and their
access.

###  II-B Privacy

The objects or things in the IoT tends to communicate the data autonomously,
therefore, the the information is vulnerable to attacks and threat. It is
highly desirable that the information is kept safe during the autonomous
transfer by ensuring the privacy. The end-to-end transfer of information is
somewhat immune to the attacks, however, the communication made via variety of
nodes and sensors is highly susceptible to privacy breach. Large amount of
data being shared and collected in different IoT technologies, is often human
centered. A person or the entity must verify the amount of information they
are willing to share to others. In the later section we review some of the
cryptography algorithms that are tailored for the resource constrained devices
and gadgets utilized in the IoT.

##  III Lightweight Cryptography for IoT

Two types of cryptography algorithms exists; symmetric and asymmetric, they
differ from each other on the basis of key that is used for encryption and
decryption. The symmetric ciphers use same key for the encryption and
decryption, on the other hand, the asymmetric ciphers makes use of a public
and private key for the sake of encrypting and decrypting the data. The
lightweight encryption algorithms commonly utilize the symmetric key
algorithms since the large key sizes in the asymmetric algorithms are not
suitable for the IoT. Another feature of using Feistel network in the
symmetric key algorithms is that the encryption and decryption process are
complement of each other, which reduces their code size and saves the memory
and circuit of the constrained device and results in the reduced latency. The
symmetric encryption algorithms however, can be use either block or stream
methods to generate the cipher text. The block cipher accepts a fixed length
block of input bits as the plain text and performs transformation according
the key. They are usually composed of substitution and permutation network
(SPN) which contains substitution boxes and permutation boxes to generate the
cipher text from the plain text. Symmetric algorithms employing a Feistel
network for the encryption of the data can utilize similar structure for
encryption and decryption. Some of the lightweight encryption algorithm are
discussed in the following. In the following, we shall discuss about the
recently proposed lightweight symmetric block ciphers that can be utilized in
the IoT.

###  III-A PRESENT

PRESENT [18] was developed for the resource constrained devices having a block
size of $80$ bits. The algorithm was synthesized to examine the resource and
power consumption, and it was observed that it requires $32$ clock cycles to
encrypt the $64$-bit plain text with $80$-bit key. It occupies $1570$ gate
equivalents (GE) which is suitable for the devices with limited resource. The
number of rounds to encrypt or decrypt the data is $32$ which involves
substitution and permutation of the plain text. The substitution and
permutation network of the algorithm is shown in Figure 1.

Figure 1: S-P Network of PRESENT

###  III-B KATAN

This cipher was developed for the resource constrained devices and consumes
$48$% less resources than PRESENT [19]. The key scheduling is simple which is
of $80$-bits and is generated using the Feistel structure to encrypt
$32$-bits, $48$-bits or $64$-bits of plain text. The shortcoming of the KATAN
cipher is the number of rounds it takes to generate the cipher text. With
$254$ rounds to generate on block of cipher text, the energy consumption is
very high an throughput is low. On of the rounds of KATAN is shown in Figure 2

Figure 2: Round of KATAN

###  III-C Humming Bird

Humming Bird was presented as an ultra-lightweight cryptographic algorithm for
the resource constrained devices such as smart cards and RFID tags [20]. It
uses $256$-bit key to encrypt the $16$-bit block of plain text. The algorithm
was implemented on a $16$-bit micro-controller and achieved better results in
terms of throughput when compared to PRESENT. Since it uses separate functions
for encryption and decryption, the resource footprint is larger.

###  III-D SIMON and SPECK

The SIMON and SPECK were proposed as a lightweight cryptography algorithms in
[21]. They were developed by the National Security Agency (NSA) in the U.S. as
an optimized algorithms for implementation in hardware and software. They
require atleast $22$ rounds to encrypt the data and the number of mathematical
operations are quite high.

###  III-E RECTANGLE

Bit-slice technique was utilized to make the algorithm lightweight and make
the implementation faster. It uses the substitution and permutation networks
to generate the cipher text in which the S-boxes are implemented in parallel
whereas the permutation block uses $3$ rotations. For $80$-key, it requires
$1600$ gates and which when implemented in parallel, yields a throughput of
$246$ Kbits/sec at $100$ KHz clock. The datapath of the algorithm is depicted
in Figure 3

Figure 3: Datapath of Rectangle-80

###  III-F SIT

A lightweight algorithm for the power constrained IoT devices named as SIT was
proposed in [22]. It is a combination of Feistel and SP network and therefore,
can withstand the attacks on the resource constrained devices. It uses only
$5$ rounds for encryption/decryption, and works on the block sizes of
$64$-bits with key size of the same size. It is composed of two modules
namely; key expansion and encryption, which are used for the key generation
and data encryption respectively. The operations the key expansion involve
XOR, concatenation, addition and shifting. The F-function shown in Figure 4
used in both key expansion and encryption/decryption block is inspired by the
Khazad block cipher and performs the linear and non-linear transformation to
remove any dependency of the output bits on the input bits [23]. This
algorithm has been implemented on a low cost micro-controller on which it
consumed only $22$ bytes of RAM, $3006$ and $2984$ clock cycles for encryption
and decryption respectively. Furthermore, recently the FPGA implementation of
the algorithm showed that a high throughput of upto $5682.56$ can be achieved
which is $180$% more than the LEA cipher [24].

Figure 4: F-function of SIT

##  IV Conclusion

Security and privacy are the vital elements in the communication, and they are
given more attention in the IoT because the data is usually human centered.
The resource constrained devices in the IoT cannot utilize the state-of-the-
art encryption algorithms, thus the development of lightweight encryption
algorithm is indispensable. In this correspondence the contemporary
lightweight block ciphers have been studied.

## References

  * [1] O. Vermesan and P. Friess, _Internet of things: converging technologies for smart environments and integrated ecosystems_. River publishers, 2013.
  * [2] H. Okkonen, O. Mazhelis, P. Ahokangas, P. Pussinen, M. Rajahonka, R. Siuruainen, S. Leminen, A. Shveykovskiy, J. Myllykoski, and H. Warma, “Internet-of-things market, value networks, and business models: state of the art report,” _Computer science and information systems reports. TR, Technical reports_ , no. 39, 2013.
  * [3] D. Miorandi, S. Sicari, F. De Pellegrini, and I. Chlamtac, “Internet of things: Vision, applications and research challenges,” _Ad hoc networks_ , vol. 10, no. 7, pp. 1497–1516, 2012.
  * [4] A. Whitmore, A. Agarwal, and L. Da Xu, “The internet of things—a survey of topics and trends,” _Information systems frontiers_ , vol. 17, no. 2, pp. 261–274, 2015.
  * [5] R. Roman, P. Najera, and J. Lopez, “Securing the internet of things,” _Computer_ , vol. 44, no. 9, pp. 51–58, 2011.
  * [6] G. Yang, J. Xu, W. Chen, Z.-H. Qi, and H.-Y. Wang, “Security characteristic and technology in the internet of things,” _Nanjing Youdian Daxue Xuebao(Ziran Kexue Ban)/ Journal of Nanjing University of Posts and Telecommunications(Natural Nanjing University of Posts and Telecommunications(Natural_ , vol. 30, no. 4, 2010.
  * [7] H. Suo, J. Wan, C. Zou, and J. Liu, “Security in the internet of things: a review,” in _2012 international conference on computer science and electronics engineering_ , vol. 3. IEEE, 2012, pp. 648–651.
  * [8] U. e Rabab, I. Ahmed, M. I. Aslam, and M. Usman, “Fpga implementation of secure internet of things (sit) algorithm for high throughput area ratio,” _International Journal of Future Generation Communication and Networking_ , vol. 11, no. 5, pp. 63–72, 2018.
  * [9] A. Al-Fuqaha, M. Guizani, M. Mohammadi, M. Aledhari, and M. Ayyash, “Internet of things: A survey on enabling technologies, protocols, and applications,” _IEEE communications surveys & tutorials_, vol. 17, no. 4, pp. 2347–2376, 2015.
  * [10] M. S. Ibrahim, I. Ahmed, M. I. Aslam, M. Ghazaal, M. Usman, K. Raza, and S. Khan, “A low cost fpga based cryptosystem design for high throughput area ratio,” _International Journal of Advanced Computer Science and Applications_ , vol. 8, no. 2, 2017. [Online]. Available: http://dx.doi.org/10.14569/IJACSA.2017.080249
  * [11] M. Usman, S. Z. Abidi, M. H. S. Siddiqui, and M. S. Ibrahim, “Implementation of secure force (64-bit) on low cost 8-bit microcontroller,” in _2016 International Conference on Open Source Systems Technologies (ICOSST)_ , 2016, pp. 102–105.
  * [12] Y. Yang, L. Wu, G. Yin, L. Li, and H. Zhao, “A survey on security and privacy issues in internet-of-things,” _IEEE Internet of Things Journal_ , vol. 4, no. 5, pp. 1250–1258, 2017.
  * [13] A.-T. Fadi and D. B. David, “Seamless authentication: For iot-big data technologies in smart industrial application systems,” _IEEE Transactions on Industrial Informatics_ , 2020.
  * [14] M. Dammak, O. R. M. Boudia, M. A. Messous, S. M. Senouci, and C. Gransart, “Token-based lightweight authentication to secure iot networks,” in _2019 16th IEEE Annual Consumer Communications & Networking Conference (CCNC)_. IEEE, 2019, pp. 1–4.
  * [15] M. Walshe, G. Epiphaniou, H. Al-Khateeb, M. Hammoudeh, V. Katos, and A. Dehghantanha, “Non-interactive zero knowledge proofs for the authentication of iot devices in reduced connectivity environments,” _Ad Hoc Networks_ , vol. 95, p. 101988, 2019.
  * [16] N. Boltz, M. Walter, and R. Heinrich, “Context-based confidentiality analysis for industrial iot,” in _2020 46th Euromicro Conference on Software Engineering and Advanced Applications (SEAA)_. IEEE, 2020, pp. 589–596.
  * [17] M. M. Dhanvijay and S. C. Patil, “Internet of things: A survey of enabling technologies in healthcare and its applications,” _Computer Networks_ , vol. 153, pp. 113–131, 2019.
  * [18] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. Robshaw, Y. Seurin, and C. Vikkelsoe, “Present: An ultra-lightweight block cipher,” in _International workshop on cryptographic hardware and embedded systems_. Springer, 2007, pp. 450–466.
  * [19] C. De Canniere, O. Dunkelman, and M. Knežević, “Katan and ktantan—a family of small and efficient hardware-oriented block ciphers,” in _International Workshop on Cryptographic Hardware and Embedded Systems_. Springer, 2009, pp. 272–288.
  * [20] D. Engels, X. Fan, G. Gong, H. Hu, and E. M. Smith, “Hummingbird: ultra-lightweight cryptography for resource-constrained devices,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2010, pp. 3–18.
  * [21] R. Beaulieu, D. Shors, J. Smith, S. Treatman-Clark, B. Weeks, and L. Wingers, “The simon and speck families of lightweight block ciphers.” _IACR Cryptol. ePrint Arch._ , vol. 2013, p. 404, 2013.
  * [22] M. Usman, I. Ahmed, M. I. Aslam, S. Khan, and U. A. Shah, “Sit: A lightweight encryption algorithm for secure internet of things,” _International Journal of Advanced Computer Science and Applications_ , vol. 8, no. 1, 2017. [Online]. Available: http://dx.doi.org/10.14569/IJACSA.2017.080151
  * [23] P. Barreto and V. Rijmen, “The khazad legacy-level block cipher,” _Primitive submitted to NESSIE_ , vol. 97, p. 106, 2000.
  * [24] Z. Mishra, S. Mishra, and B. Acharya, “High throughput novel architecture of sit cipher for iot application,” in _Nanoelectronics, Circuits and Communication Systems_. Springer, 2020, pp. 267–276.