# AE SemRL: Learning Semantic Association Rules with Autoencoders

Erkan Karabulut University of Amsterdam, 1098 XH, North Holland, The
Netherlands
{e.karabulut, v.o.degeler<EMAIL_ADDRESS>Victoria Degeler University of
Amsterdam, 1098 XH, North Holland, The Netherlands
{e.karabulut, v.o.degeler<EMAIL_ADDRESS>Paul Groth University of
Amsterdam, 1098 XH, North Holland, The Netherlands
{e.karabulut, v.o.degeler<EMAIL_ADDRESS>
###### Abstract

Association Rule Mining (ARM) is the task of learning associations among data
features in the form of logical rules. Mining association rules from high-
dimensional numerical data, for example, time series data from a large number
of sensors in a smart environment, is a computationally intensive task. In
this study, we propose an Autoencoder-based approach to learn and extract
association rules from time series data (AE SemRL). Moreover, we argue that in
the presence of semantic information related to time series data sources,
semantics can facilitate learning generalizable and explainable association
rules. Despite enriching time series data with additional semantic features,
AE SemRL makes learning association rules from high-dimensional data feasible.
Our experiments show that semantic association rules can be extracted from a
latent representation created by an Autoencoder and this method has in the
order of hundreds of times faster execution time than state-of-the-art ARM
approaches in many scenarios. We believe that this study advances a new way of
extracting associations from representations and has the potential to inspire
more research in this field.

_Keywords_ Rule learning $\cdot$ Association rules $\cdot$ Autoencoders
$\cdot$ Semantics $\cdot$ Time series data

##  1 Introduction

Association Rule Mining (ARM) aims to discover commonalities in data in the
form of logical rules and has successful applications in a wide variety of
domains and tasks such as anomaly detection (Nassif et al., 2021),
recommendation systems (Khanal et al., 2020), and product design (Jiang et
al., 2018). Initial ARM algorithms (Agrawal et al., 1994; Han et al., 2000)
were designed for categorical data in the form of transactions. However, when
applied to numerical data with greater size and dimension, ARM algorithms are
inefficient to execute (Kaushik et al., 2023; Telikani et al., 2020). Despite
the broad range of success of deep learning (Sarker, 2021), including learning
logical rules from graph data (Qu et al., 2020), applying deep learning-based
methods directly for learning association rules in a transaction dataset is
not yet well-studied.

Besides inefficiency, ARM also faces the challenge of producing a high number
of rules that are difficult to explain (Kaushik et al., 2023). Processing a
large number of rules e.g., to decide which ones are useful for a certain task
is computationally expensive and time-consuming. Explainability is
particularly important when it comes to verifying the rules by a human expert
or an automated symbolic system. This paper focuses on addressing these three
issues in the case of learning association rules from mixed categorical and
numerical time series data in the form of transactions.

To overcome the challenges of rule quantity and explainability, we utilize
semantics. Knowledge graphs (Hogan et al., 2021) \- large database of
structured semantic information - are being increasingly used with time series
data e.g., from sensors in a smart environment (Karabulut et al., 2023a) or
video processing (Greco et al., 2021). When knowledge graphs are linked to
time series data, association rules with semantic properties can be learned
facilitating generalizability and explainability. For instance, in a smart
environment without semantics, an association rule might state: ‘if sensor1
measures a value in range R, then sensor2 must measure a value in range R2’.
With semantics, rules can take a more contextual form, as seen in the water
network domain example: if a sensor with type T placed inside a Pipe P
measures a value in range R, then another sensor with type T2 inside a
Junction J that is connected to P must measure a value in range R2. The
association rule with semantics is no longer about individual time series data
sources (sensor1 and sensor2). Instead, it describes a certain context that
the time series data source is in, and therefore is more generically
applicable and explainable.

On the other hand, enriching time series data with semantics increases input
size and therefore results in even higher execution times. We show that the
state-of-the-art ARM algorithms have impractical execution times when run on a
realistic semantically enriched time series dataset. Therefore, there is a
greater need to apply machine learning-based solutions when utilizing
semantics.

Hence, this paper proposes an Autoencoder-based approach (AE SemRL) to learn
semantic association rules. We show that Autoencoders can learn associations
among their input features, and the associations can be extracted from their
latent representation in the form of logical rules. We evaluate our approach
on three time series datasets with associated semantics from two domains;
water networks, and energy. Our experiments show that AE SemRL has hundreds of
times faster execution time than the state-of-the-art methods in many
scenarios, and the association rules learned by AE SemRL imply strong
associations based on commonly used rule quality criteria.

A list of concrete contributions of this paper is given below:

  * •

In Section 3, we provide a formal problem definition for semantic association
rule learning from time series data and knowledge graphs.

  * •

Section 4 introduces the first deep learning-based approach (AE SemRL) to
learn semantic association rules from time series data.

  * •

Section 5 provides empirical evidence that a latent representation created by
an Autoencoder captures associations among its input features and the
associations can be extracted in the form of logical rules, which makes
association rule learning feasible with high-dimensional data.

Section 2 presents the background concepts and related work. Section 6
discusses current and future perspectives for learning semantic association
rules. Lastly, Section 7 concludes with a summary of findings and future work.

##  2 Related Work

This section introduces the related work and background concepts.

###  2.1 Numerical Association Rule Mining (NARM)

Association rules are first-order horn clauses which are formal logical
statements in Conjuctive Normal Form (CNF) with at most one positive literal.
They are in the form of an implication, e.g., $X\rightarrow Y$ which is read
as if X then Y. X is called the antecedent or body, and Y is called consequent
or head of the rule.

Following the categorization in a recent extensive systematic literature
review by Kaushik et al. (2023), there are 3 main categories of approaches to
NARM: discretization, optimization, and statistical methods. In the
discretization-based methods, numerical data is divided into intervals in a
way that can facilitate the mining of interesting association rules. It is
further categorized into partitioning, clustering, fuzzy, and hybrid
approaches. However discretization-based algorithms may suffer from
information loss. Another major category of NARM is optimization-based
algorithms that include evolutionary, differential evolution, swarm
intelligence, and physics-based approaches. These algorithms essentially
provide a heuristic-based search process that aims to find association rules
that optimize one or more (multi-objective) rule quality criteria. Therefore
they are named optimization-based algorithms. These methods as well as the
statistical methods that do not include learning a model of input data suffer
from handling big high-dimensional data, together with other broader issues in
NARM such as having a large number of rules, and explainability as also
mentioned by Kaushik et al. (2023) and others (Berteloot et al., 2023; Kishore
et al., 2021).

###  2.2 Association Rule Mining and Semantics

There have been a number of works focused on association rule mining over
knowledge bases typically using Resource Description Framework (RDF) as the
representation language (Barati et al., 2017). Data mining from RDF also
suffers from the efficiency problem (d’Amato, 2020). Our approach differs in
that we are focused on learning association rules from time series data that
has semantic properties.

There has been only one study utilizing semantics when learning association
rules from time series data (Karabulut et al., 2023b). This existing approach
is based on the well-known FP-Growth (Han et al., 2000) algorithm and uses
knowledge graphs to enrich pre-discretized time series data with semantics. We
adopt a similar enrichment approach to that work but develop a completely new
model based on deep learning.

###  2.3 Deep Learning-based Association Rule Mining

Deep learning has been part of rule learning tasks either directly or as part
of a pipeline of operations. In a recent example, Qu et al. (2020), proposed a
rule learning approach for learning logical rules on knowledge graphs. Simsek
et al. (2021) utilized and compared many deep learning architectures as part
of a rule extraction task, however only to label unstructured data which is
then fed into a rule mining algorithm. Another common usage of deep neural
networks for rule learning is to understand the effect of input features on a
prediction task (Chakraborty et al., 2020). This is different than learning
associations as it is an unsupervised task.

Patel et al. (2022) proposed to use of Autoencoders for learning frequent
patterns in a grocery dataset, which are then used to create association
rules. However, no source code or pseudo-code is given in the paper.
Autoencoders are used to create a lower-dimensional representation of a given
input data in the literature (Chen and Guo, 2023). To the best of our
knowledge, Berteloot et al. (2023), proposed the only deep learning-based
approach to learn association rules directly (ARM-AE). ARM-AE is an
Autoencoder-based ARM algorithm for categorical tabular datasets only, and not
for time series datasets. ARM-AE extracts associations from a trained
Autoencoder based on the reconstruction success for a given set of input
vectors. It uses an Autoencoder with equal size layers and assumes that input
to the trained Autoencoder represents a consequent while the successful
reconstruction represents antecedents of an association rule. We argue that
this assumption does not hold in real data, and input to an inference step
should represent an antecedent while the output represents a consequent. We
adapt ARM-AE to the case of semantic association rule learning from time
series data. Furthermore, we provide an improved Autoencoder architecture that
employs denoising with probability distributions in its output layer per input
feature, as well as a new algorithm to extract associations from a trained
Autoencoder (AE SemRL).

##  3 Problem Definition

Association rules are in the form of implications, e.g. $X\rightarrow Y$,
where $X\rightarrow Y$ is a horn clause with $|Y|=1$ referring to a single
literal and $|X|\geq 1$ referring to a set of literals. A horn clause is
defined as a disjunction of literals with at most one positive literal.

Given a time series dataset T mapped to a knowledge graph G with binding B,
produce a set of semantic association rules with clauses based on T and G. An
example of T would be sensor measurements or frame in a video. Note that the T
is converted to a set of transactions before the learning process. G is in the
form of a directed property graph which contains semantic information
regarding the items in T, such as where a sensor is placed. The third one is a
binding B that reports which item in T corresponds to which node in G,
assuming that each item has a representation in G. Output rules can express
conditions on the sensor measurements and its context such as the environment
that the sensor is placed in, or a frame in a video and entities in the frame
such as cats and dogs.

###  3.1 Input

Table 1: Input notation, explanations and examples from water networks domain. Notation |  Explanation |  Example
---|---|---
C |  Classes in an Ontology/Data schema |  Pipe, Junction
R, r |  Relations in between the classes |  (Pipe)_connectedTo_(Junction)
A, a |  Properties for the classes and relations in the Ontology/Data schema |  (Junction).elevation, elevation property of the class Junction
V |  Node IDs in the knowledge graph |  P1, J2
E, e |  IDs of the edges in between nodes in the knowledge graph |  (P1)_(e1)_(J2), P1 and J2 are node IDs, e1 is an edge ID
L, l |  Labels for the nodes and edges in the knowledge graph |  (P1:Pipe)_(e1:connected_to) _(J2:Junction)
P, U, p |  Property-value pairs for nodes and edges in the knowledge graph |  (P1:Pipe).elevation=v1, v1 is the value for the elevation property of P1 which is a Pipe
M, S, s |  set of value and source pairs |  a sensor with the ID s1, measures u1
M, F, f |  set of values and timestamps |  a value v1 is obtained at the t1
V, S, b |  there is a node in the knowledge graph for each source |  each sensor is represented with a node in the knowledge graph

Knowledge graph. The knowledge graph described in this section is a property
graph with an ontology or data schema as the underlying structure
(Tamašauskaitė and Groth, 2023). We adapt the definition for a property graph,
given in the next paragraph, from the Knowledge Graphs book by Hogan et al.
(2021) (see Table 1 for high-level explanations of the notation and examples):

Property Graph. Let Con be a countably infinite set of constants. A property
graph is a tuple $G=(V,E,L,P,U,e,l,p)$, where $V\subseteq Con$ is a set of
node IDs, $E\subseteq Con$ is a set of edge IDs, $L\subseteq Con$ is a set of
labels, $P\subseteq Con$ is a set of properties, $U\subseteq Con$ is a set of
values, $e:E\rightarrow V\times V$ maps an edge ID to a pair of node IDs,
$l:V\cup E\rightarrow 2L$ maps a node or edge ID to a set of labels, and
$p:V\cup E\rightarrow 2P\times U$ maps a node or edge ID to a set of
property–value pairs.

Ontology/Data Schema. Let $O=(C,R,A,r,a)$ be an ontology or data schema, where
$C\subseteq Con$ is a set of classes, $R\subseteq Con$ is a set of relations,
$A\subseteq Con$ be a set of properties, $r:R\rightarrow C\times C$ maps a
relation to a pair of classes, and $a:C\cup R\rightarrow 2P$ maps a class or a
relation to a set of properties.

To express that G has O as its underlying structure, we define the following;
i) $L\subseteq C\cup R$, meaning that the labels in G can only be one of the
classes or relations defined in O, ii) $P\subseteq A$, meaning that the
properties of V and E in G, can only be one of the properties in A. This
definition is enough to show that knowledge graphs can help in learning
generalizable association rules.

Time series data. We define time series data generically as a tuple
$T=(M,S,F,s,f)$, where $M\subseteq Con$ is a set of values, $S\subseteq Con$
is a set of source IDs, $F\subseteq Con$ is a set of timestamps and
$s:S\rightarrow M$ where $\exists x,x^{\prime}\in
S,\neg(s(x)=s(x^{\prime})\implies x=x^{\prime})$ (non-injective), and $\forall
y\in M(\exists x\in S(s(x)=y))$ (surjective). A source ID refers to the source
of a value M, such as a sensor ID, or a frame ID in a video. This means that s
maps each source ID to one or more values in a way that all values are matched
with exactly one source ID. Finally, $f:M\rightarrow F$ maps each value to a
timestamp. Note that there is no assumed order for timestamps since the task
is not to learn temporal rules, and the time series data is represented as a
set of transactions to enable generalizable rule learning.

####  3.1.1 Binding

Binding is a tuple $B=(V,S,b)$, where $V$ is the set of node IDs from G, and
$S$ is the set of sources from T, $b:V\rightarrow S$ maps each source to a
node in G, and $S\subseteq V$ meaning that there is a node ID for each source
ID, and there can be node IDs for more e.g., instances of classes in C.

###  3.2 Output

The output is a set of association rules of the below-described form.

Let $I=\\{i^{\prime}_{1},i^{\prime}_{2},...,i^{\prime}_{b}\\}$ be a set of $b$
items. We define the following 5 forms for an item: $\forall i^{\prime}\in
I(((i^{\prime}=(p^{\prime}\\#z^{\prime}))\lor(i^{\prime}=(m^{\prime}\\#z^{\prime}))\lor(i^{\prime}=(v^{\prime}_{l}=l^{\prime}))\lor(i^{\prime}=(e^{\prime}_{l}=l^{\prime}))\lor(i^{\prime}=(v^{\prime}\rightarrow
v^{\prime\prime}=e^{\prime})))$, with $p^{\prime}\in P$, $m^{\prime}\in M$,
$v^{\prime},v^{\prime\prime}\in V$, $e^{\prime}\in E$,
$l^{\prime},v^{\prime}_{l},e^{\prime}_{l}\in L$ where $v^{\prime}_{l}$ refers
to a label mapped to a node with the ID $v^{\prime}$, and $e^{\prime}_{l}$
refers to a label mapped to an edge with the ID $e^{\prime}$. $z^{\prime}$
refers to a value that is either categorical or numerical, $\\#$ refers to one
of the comparison operations with a truth value defined below:

$\\#_{categorical}(p,g)::=(p=g)|(p\neq g)|(p\in\\{g\\})|(p\notin\\{g\\})$

$\\#_{numerical}(p,g)::=(p=g)|(p\neq g)|(p>g)|(p<g)|(p\leq g)|(p\geq g)$

Table 2: Item forms, explanations and examples from water network domain. Form |  Example |  Explanation
---|---|---
$(i^{\prime}=(p^{\prime}\\#z^{\prime}))$ |  $(p1:).length>100$ |  A node p1 has length bigger than 100
$(i^{\prime}=(m^{\prime}\\#z^{\prime}))$ |  $(s1:Sensor).value<10$ |  A sensor s1 with measurement value smaller than 10
$(i^{\prime}=(v^{\prime}_{l}=l^{\prime}))$ |  $(p1:Pipe)$ |  A node p1 has the label ’Pipe’
$(i^{\prime}=(e^{\prime}_{l}=l^{\prime}))$ |  $(e1:Junction)$ |  An edge e1 has the label ’Junction’
$(i^{\prime}=(v^{\prime}\rightarrow v^{\prime\prime}=e^{\prime}))$ |  $(p1:)\rightarrow(p2:)=(e1:)$ |  node p1 is connected to p2 with the edge e1

$X\rightarrow Y$ is an implication (association rule) where $(X,Y\subseteq
I)\wedge(|Y|=1)$. This means that on both sides of the implication, items can
only consist of properties of classes or relations defined in the ontology,
and the consequence side of the implication can only have 1 item. A set of 5
possible item forms are given together with explanations and examples in Table
2. The item forms consist of comparisons over $m\in M$ or $p\in P$, labels
$l\in L$, and whether an edge $e\in E$ exists for a pair of $v\in V$.

##  4 Learning Semantic Association Rules - AE SemRL

AutoEncoder-based Semantic association Rule Learning (AE SemRL) is a method
and an algorithm that facilitates Autoencoders to learn representations of
semantically enriched time series data in the form of transactions and extract
association rules from the representation.

###  4.1 Autoencoder Architecture

In this study, we utilized a denoising under-complete Autoencoder (Vincent et
al., 2008). It aims to reconstruct the input from its noisy variant, which is
created by adding a noise value to the input. In this way, the model becomes
more robust to noise in the input data. During the training process,
$tanh(z)=\frac{e^{z}-e^{-z}}{e^{z}+e^{-z}}$ is preferred in the hidden layers
and $softmax(z_{i})=\frac{e^{z_{i}}}{\sum_{j=1}^{n}e^{z_{j}}}$ preferred at
the output layer, as activation functions. The softmax function is applied per
category of features so that for each category, probabilities per class values
are obtained. As the lost function, aggregated binary cross entropy loss,
$BCE\\_Loss=\frac{1}{n}\sum_{i=1}^{n}-(y_{i}log(p_{i})+(1-y_{i})log(1-p_{i}))$,
is applied to each feature to calculate the loss between Autoencoder
reconstruction and noise-free input.

###  4.2 Pipeline

Figure 1: Full pipeline of operations for AE SemRL.

Figure 1 depicts the full pipeline of operations for AE SemRL. Time series
data is discretized using equal frequency discretization method (Foorthuis,
2020), also to be comparable to baseline FP-Growth where we also use the same
pre-discretization. Binding B is utilized to generate a semantically enriched
set of transactions from time series data. Let $j$ be the number of time
series data sources in $S$, $i$ be the number of semantic property values in
$U$ mapped to each $s_{1..j}$, $z$ be the number of classes per input feature
for simplicity, and $n$ be the number of transactions. In practice, $i$ and
$z$ usually are different per $s_{1..j}$, and property values $p\in U$ can be
different per transaction if G changes over time. Property values from
neighbors of node $v$, i.e., $p_{v^{\prime}_{j}}^{k}$ where $\exists e\in
E:v\rightarrow v^{\prime}$, can also be in the transaction set depending on
the application.

Semantically enriched transactions are then one-hot encoded and fed into the
Autoencoder. AE SemRL keeps track of which data is fed into which neuron.

Input transactions to the Autoencoder look as follows:

$[\\{m1_{s_{1}}^{1},m1_{s_{1}}^{2},...,m1_{s_{1}}^{z},...,m1_{s_{j}}^{z},p1_{{s_{1}}_{1}}^{1},...,p1_{{s_{1}}_{1}}^{z},...,p1_{{s_{1}}_{i}}^{z},...,p1_{{s_{j}}_{i}}^{z}\\},\\\
\indent\\{m2_{s_{1}}^{1},m2_{s_{1}}^{2},...,m2_{s_{1}}^{z},...,m2_{s_{j}}^{z},p2_{{s_{1}}_{1}}^{1},...,p2_{{s_{1}}_{1}}^{z},...,p2_{{s_{1}}_{i}}^{z},...,p2_{{s_{j}}_{i}}^{z}\\}\\\
\indent...\\\
\indent\\{mn_{s_{1}}^{1},mn_{s_{1}}^{2},...,mn_{s_{1}}^{z},...,mn_{s_{j}}^{z},pn_{{s_{1}}_{1}}^{1},...,pn_{{s_{1}}_{1}}^{z},...,pn_{{s_{1}}_{i}}^{z},...,pn_{{s_{j}}_{i}}^{z}\\}]$

###  4.3 Rule Extraction from Autoencoders

Intuition: AE SemRL exploits the reconstruction loss of a trained Autoencoder
to learn associations. If reconstruction for an input vector with marked
features is more successful than a certain threshold (similarity threshold)
then we say that the marked features imply the successfully reconstructed
features. Marking features is done by assigning 1 (100%) probability to a
certain class value for a feature, 0 to the other classes for the same
feature, and then assigning equal probabilities to the rest of the features in
an input vector.

Example: Figure 2 depicts an example rule extraction process. Assume that
there are only two features in the input vector where one has 2 and the other
has 3 possible class values, namely $f_{1}=\\{a,b\\}$ and $f_{2}=\\{c,d,e\\}$.
One-hot encoded version of $f_{1}$ and $f_{2}$ can be represented with 5
digits. Assume that we want to test whether $f_{1}(a)\rightarrow f_{2}(c)$,
meaning whether $f_{1}$ being ‘$a$’ implies $f_{2}$ being ‘$c$’ or not, based
on the similarity threshold of 0.8. In this case, we do a forward run on the
trained Autoencoder with the input vector $[1,0,0.33,0.33,0.33]$. We call this
a $test\\_vector$. Assume that the output is $[0.8,0.2,0.9,0.04,0,06]$. The
third output digit that corresponds to $f_{2}(c)$ is bigger than the
threshold, 0.9. Therefore, we say that $f_{1}(a)\rightarrow f_{2}(c)$.

Figure 2: An illustration of association rule extraction from a trained
Autoencoder.

Algorithm: The algorithm for extracting association rules from a trained
Autoencoder is given in Algorithm 1. The parameters are a trained Autoencoder
(ae_model), a similarity threshold (similarity_threshold), and a maximum
number of antecedents (max_antecedents) that the rules will contain. Based on
the $max\\_antecedents$, in line 3, the algorithm creates combinations of
features to be tested. Instead of marking each combination of input features
to create test vectors, it goes through all unique input vectors (line 4) to
create test vectors, since a pattern that is not in the input vectors can not
be an association. In lines 6 and 7, it creates a test vector (as demonstrated
in the previous examples), where candidate antecedents are marked features,
and the rest of the features have equal probabilities. In lines 8-12, it
performs a forward run on the ae_model with the test vector and compares the
probabilities of class values per feature in the Autoencoder output with the
similarity threshold. If the probability is bigger than the threshold, then it
constructs the rule as demonstrated in the examples. In line 13, it returns
the extracted association rules.

Algorithm 1 AE SemRL

1:procedure AESemRL(ae_model, similarity_threshold, max_antecedent)

2: rules = []

3: candidate_antecedents = combinations(ae_model.features, max_antecedents)

4: for input_vector in unique(ae_model.input_vectors) do

5: for feature_list in candidate_antecedent do

6: test_vector = init_vector_with_equal_probabilities(ae_model.features)

7: test_vector[feature_list] = input_vector[feature_list]

8: if test_vector not tested before then:

9: output = ae_model.forward(test_vector)

10: for feature in output do:

11: if feature.class_with_max_prob() $>$ similarity_threshold then:

12: rules.append({antecedent: feature_list, consequent: feature})

13: return rules

##  5 Evaluation

This section includes an evaluation of the AE SemRL on 3 different open-source
datasets and 2 baselines. The entire source code is written in Python and is
available online (anonymously) including the source codes for knowledge graph
construction, parsing time series data, baselines, and AE
SemRL111https://anonymous.4open.science/r/semantic-association-rule-
learning-5372.

###  5.1 Setup

3 open-source time series datasets with associated semantics from two
different domains, water networks, and energy, are used in the evaluation.
LeakDB (Vrachimis et al., 2018) is an artificially generated realistic dataset
for leak detection in water distribution networks. It contains time series
data from 96 sensors of various types, and semantic information such as the
formation of the network, sensor placement, and properties of network
components, i.e., pipes. L-Town(Vrachimis et al., 2020) is another dataset in
the water distribution networks domain with the same characteristics. It has
118 sensors. The third is LBNL Fault Detection and Diagnostics Datasets
(Granderson et al., 2022) that contains time series data from 29 sensors and
semantics for Heating, Ventilation, and Air Conditioning (HVAC) systems such
as the placement of the sensors and structure of the HVAC system. A knowledge
graph is created per dataset.

An Autoencoder with the given architecture (Section 4.1) is trained for each
dataset. During training, the following parameters were found to be performing
best based on a grid search: learning rate is set to $5e^{-3}$, the models are
trained for 20 epochs, Adam (Kingma and Ba, 2014) optimizer is used for
gradient optimization with a weight decay of $2e^{-8}$, and the noise factor
for the denoising Autoencoder is $0.5$.

###  5.2 Evaluation Metrics

The metrics that are used in the evaluation are number of rules, execution
time for learning rules (excluding KG construction, semantic enrichment, model
training, etc.), rule overlap and rule quality. Measuring rule quality is the
most common way to evaluate ARM algorithms (Kaushik et al., 2023; Telikani et
al., 2020). We selected the following most common rule quality criteria that
are used to measure the implied strength of association in a rule (lift,
leverage, Zhang’s metric) since our hypothesis is to show that Autoencoders
can learn associations among its input features:

  * •

Support: Percentage of transactions with a certain item or rule, among all
transactions (D): $support(X\rightarrow Y)=\frac{|X\cup Y|}{|D|}$

  * •

Confidence: Conditional probability of a rule, e.g., given the transactions
with the antecedent X in, the probability of having the consequent Y in the
same transaction set: $confidence(X\rightarrow Y)=\frac{|X\cup Y|}{|X|}$

  * •

Lift: Frequency of a rule $X\rightarrow Y$ occurring compared to the case
where they were statistically independent. A score of 1 indicates independence
and $>1$ indicates association: $lift(X\rightarrow
Y)=\frac{confidence(X\rightarrow Y)}{support(Y)}$

  * •

Leverage: Difference between antecedent and consequent appearing together and
the expected frequency of their independence. A score of $0$ indicates
independence while a score of $>0$ indicates association.
$leverage(X\rightarrow Y)=support(X\rightarrow Y)-(support(X)\times
support(Y))$

  * •

Zhang’s Metric (Yan et al., 2009): This metric also considers the case in
which the consequent appears alone in the transaction set, besides their co-
occurrence, and therefore measures dissociation as well. A score of $>0$
indicates an association, 0 indicates independence and $<0$ indicates
dissociation: $zm(X\rightarrow Y)=\frac{confidence(X\rightarrow
Y)-confidence(X^{\prime}\rightarrow C)}{max(confidence(X\rightarrow
Y),confidence(X^{\prime}\rightarrow Y))}$ in which $X^{\prime}$ refers to the
absent of $X$ in the transaction set.

###  5.3 Baselines

Two baselines are used for evaluation. The first one is the only existing
approach for learning semantic association rules from time series data
(Karabulut et al., 2023b) that is based on the well-known FP-Growth (Han et
al., 2000) algorithm. It relies on a pre-discretization of the time series
data for mining, and it is implemented using MLxtend Python package (Raschka,
2018). FP-Growth takes a minimum support and confidence threshold value as
parameters and produces rules that have higher values than the thresholds. The
second baseline is a state-of-the-art optimization-based ARM method, based on
highly influential Harris’ Hawk Optimization (HHO) (Heidari et al., 2019)
algorithm, implemented using NiaPy and NiaARM Python packages (Vrbančič et
al., 2018; Stupan and Fister, 2022). HHO does not require a pre-discretization
step, takes an initial population size (random set of solutions, in this case,
association rules), and several iterations for optimization steps, and
produces a set of association rules optimizing a fitness function (rules with
high confidence is mined with HHO).

###  5.4 Experiments

This section includes a set of experiments to evaluate and compare AE SemRL
with baselines FP-Growth and HHO from different aspects.

####  5.4.1 How fast is AE SemRL in comparison to baselines?

The time complexity of FP-Growth is $D(2N+D+2^{D})+2^{D}$ (Yuan and Ding,
2012), where $D$ refers to the data dimension and $N$ refers to the number of
transactions, with the most expensive operation being finding maximum frequent
sets in the data, $O(2^{D})$. The time complexity of HHO is $O(N×(T+TD+1))$
(Heidari et al., 2019) with T being the number of iterations. AE SemRL, on the
other hand, has the time complexity of $O(N^{A})$ where $A$ is the number of
antecedents. However, the time complexity depends highly on the algorithm
parameters such as support and confidence for FP-Growth, initial population
size for HHO, maximum number of antecedents for AE SemRL, as well as dataset
characteristics such as the number of unique items. Therefore, we provide an
execution time analysis below.

Figure 3: (Bottom-Left) Execution time of FP-Growth (confidence = 0.8).
(Bottom-Right) Effect of the number of time series data sources on execution
time (AE SemRL’s similarity threshold = 0.5, support=0.25, confidence=0.8 for
FP-Growth). (Top-Left) The number of rules learned by AE SemRL. (Top-Right)
Execution time of AE SemRL per different number of antecedents.

First, we show that it is impractical to run FP-Growth on the full datasets.
The hardware used in the experiment is a Lenovo ThinkPad X1 Yoga Gen 7
personal computer with 12th Gen Intel® Core™ i5-1240P × 16 model CPU and 16,0
GiB memory. The bottom-right graph in Figure 3 shows the results of an
execution time experiment of both approaches on all 3 datasets for learning
semantic association rules with 1 antecedent. This experiment is carried out
by randomly picking time series data sources 10 times, and calculating average
execution times for each of the points on the graph. The results show that FP-
Growth is highly sensitive to the width of each transaction and the execution
time of the algorithm becomes impractical after considering roughly 10 time
series data sources and associated semantics. On the other hand, AE SemRL
shows a more stable behavior and is resilient to the choice of data source
selection. The graph on the bottom-left side of Figure 3 shows the effect of
the minimum support threshold on FP-Growth’s execution time. Depending on the
dataset, after reducing the threshold (to somewhere between 0.2 and 0.01), FP-
Growth starts to perform poorly in terms of execution time.

Top-left and top-right of Figure 3 shows the effect of the number of
antecedents parameter in AE SemRL on the execution time and the number of
rules learned. Due to the combination operation on the number of antecedents
to create test vectors in the AE SemRL algorithm (line 3 in Algorithm 1), we
see a factorial-grade increase in the execution time. Overall, these
experiments show that FP-Growth is sensitive to the minimum support threshold
and the number of time series data sources, while AE SemRL is sensitive to the
number of antecedent parameters in terms of their execution time.

Since the execution time of HHO is directly influenced by the manually set
maximum iterations parameter, we base our evaluation on rule quality. We first
run AE SemRL, measure rule quality, and then run HHO for approximately enough
time to get similar confidence values to AE SemRL. The initial population of
HHO is set to the number of rules obtained by the AE SemRL approach. Table 3
shows the result of this analysis. The results show that HHO takes 100s of
times longer to compute and produces 10s of times more rules with lower
implied association strength on average.

Table 3: Comparison of AE SemRL and HHO (p=initial population, i=max iteration) on the 3 datasets. Dataset |  Approach |  Support |  Confidence |  Lift |  Leverage |  Zhang’s Metric |  Exec. time |  Rule Count
---|---|---|---|---|---|---|---|---
LeakDB |  AE SemRL |  0.263 |  0.903 |  1.467 |  0.015 |  0.41 |  0.056 |  450
HHO(p=450, i=20000) |  0.208 |  0.827 |  1.838 |  0.014 |  0.181 |  38.915 |  8457
L-Town |  AE SemRL |  0.333 |  0.877 |  0.157 |  0.008 |  0.443 |  0.039 |  200
HHO(p=200, i=10000) |  0.285 |  0.849 |  1.629 |  0.002 |  0.04 |  14.908 |  3975
LBNL |  AE SemRL |  0.356 |  0.973 |  1.024 |  0.0006 |  0.374 |  0.078 |  206
HHO(p=206, i=50000) |  0.417 |  0.817 |  1.54 |  0.0021 |  0.099 |  180.551 |  21851

####  5.4.2 How good are the rules found by AE SemRL?

As FP-Growth is based on counting items in the transaction dataset, we assume
that it can already find strong associations based on a given criterion. The
goal of AE SemRL is to approximate FP-Growth as much as possible. To avoid the
unfeasible runtime of FP-Growth (see previous experiment), we only picked 7
time series data sources randomly for this experiment. It is repeated 10 times
to prevent bias in the choice of data source selection and average results are
presented. FP-Growth is run with different minimum support thresholds as this
value has a direct impact on the rule quality, and the AE SemRL is run with a
0.5 similarity threshold.

Table 4 shows that the rules learned by AE SemRL have high confidence (87%+).
Lift, leverage and Zhang’s metrics for AE SemRL show that the rules imply
association, and not only statistical significance. The quality of the rules
mined by FP-Growth with relatively higher support values, is significantly
higher than the AE SemRL but produces a low number of rules. When run with
lower support values, this difference becomes smaller and the number of rules
increases. According to the rule overlap results, a significant amount of
association rules (50%+ on average) mined by FP-Growth is also learned by AE
SemRL.

A rule quality comparison of AE SemRL and HHO is already given in Table 3.
Note that the rule overlap criterion does not apply to HHO, since it does not
do a pre-discretization, and hence intervals for numerical properties are
different. An additional experiment showing how similarity threshold effects
rule quality in AE SemRL is given in Appendix A.

Table 4: Comparison of AE SemRL and FP-Growth (FPG, sup=minimum support threshold) on the 3 datasets. Dataset |  Approach |  Support |  Confidence |  Lift |  Leverage |  Zhang’s Metric |  Rule Count |  Rule Overlap
---|---|---|---|---|---|---|---|---
LeakDB |  AE SemRL |  0.263 |  0.903 |  1.467 |  0.015 |  0.41 |  450.1 |  -
FPG(sup$\geq$0.4) |  0.457 |  1 |  2.131 |  0.197 |  0.93 |  5.2 |  77%
FPG(sup$\geq$0.3) |  0.334 |  0.993 |  2.976 |  0.219 |  0.99 |  40.8 |  41%
FPG(sup$\geq$0.2) |  0.258 |  0.99 |  3.882 |  0.185 |  0.99 |  77.4 |  31%
L-Town |  AE SemRL |  0.333 |  0.877 |  1.157 |  0.008 |  0.443 |  199.6 |  -
FPG(sup$\geq$0.4) |  0.701 |  0.985 |  1.528 |  0.11 |  0.95 |  16.2 |  68%
FPG(sup$\geq$0.3) |  0.545 |  0.968 |  1.566 |  0.089 |  0.785 |  28 |  65%
FPG(sup$\geq$0.2) |  0.366 |  0.97 |  1.67 |  0.079 |  0.611 |  78 |  82%
LBNL |  AE SemRL |  0.356 |  0.973 |  1.024 |  0.0006 |  0.374 |  206.5 |  -
FPG(sup$\geq$0.4) |  0.904 |  0.989 |  1.029 |  0.012 |  0.932 |  27.6 |  62%
FPG(sup$\geq$0.3) |  0.843 |  0.997 |  1.078 |  0.018 |  0.885 |  35.4 |  60%
FPG(sup$\geq$0.2) |  0.587 |  0.99 |  1.926 |  0.086 |  0.875 |  47.6 |  55%

##  6 Discussion

This section discusses the experiment results and future research directions.

Need for learning-based approaches. State-of-the-art ARM approaches perform
poorly on big high-dimensional data. Both FP-Growth and HHO are highly
sensitive to the number of time series data sources as shown in the
experiments. Furthermore, FP-Growth is highly sensitive to lower minimum
support thresholds which allows the algorithm to capture rare but consistent
events. HHO, on the other hand, has to run a long time compared to AE SemRL to
be able to extract high-quality association rules. Therefore, there is a great
research opportunity on the learning-based approaches to replace ARM
algorithms.

Learning associations with Autoencoders. The experiments showed that
Autoencoders are capable of learning associations in the input data. However,
AE SemRL has high execution times when run to learn rules with a relatively
higher number of antecedents. Rules with a bigger set of antecedents refer to
more specific cases in the data compared to the rules with a smaller set of
antecedents. Therefore, we can say that AE SemRL can learn more generalizable
patterns faster than more specific patterns in the data. A natural next step
is to experiment with different levels of semantic properties in the
antecedent of a rule to decide how much semantics is enough to achieve a
certain task.

Extracting association rules from latent representations. Autoencoders are one
way to encode associations in the data. However, different representation
learning methods should also be tested for the task of learning associations.
For instance, graph neural networks are better at capturing a graph’s
structure and therefore are a good candidate to learn associations from a
knowledge graph. Another aspect is to extract associations from a
representation. AE SemRL offers a straightforward intuitive method, however,
more sophisticated methods, e.g., based on output probability distributions
are to be investigated.

Post-processing of the semantic association rules. This paper, and most
articles on ARM, offers an evaluation based on the quality of the rules.
Another way to evaluate the rules is to test them for a certain task such as
leak detection for water networks, fault detection for energy use cases, or
anomaly detection in general. This requires building hypotheses using the
rules and testing them on unseen data. Another open research question is to
understand the strengths and weaknesses of semantic association rules on such
tasks.

##  7 Conclusion

This study showed that Autoencoders can learn association rules in a
semantically enriched time series dataset. Rules in this form are called
semantic association rules which are more generically applicable and
explainable. We proposed a pipeline of operations to semantic association rule
learning and an algorithm named AE SemRL that can extract associations from an
Autoencoder. Our evaluation results based on 3 datasets from 2 domains show
that the quality of the rules learned by AE SemRL implies associations and the
algorithm can run much faster than the state-of-the-art ARM algorithms in many
scenarios.

These findings led to new research questions including investigating learning
associations with other neural network architectures and finding other ways to
extract associations from latent representations that are more efficient or
can lead to stronger associations. Once learned, semantic association rules
can be used in many applications such as leak detection in water networks, and
fault diagnosis in the energy domain. Another research direction is to post-
process the rules to find a subset that can be used for a certain task or to
adopt the learning process (e.g., via a feedback mechanism) for a certain
task.

Acknowledgements. This work has received support from The Dutch Research
Council (NWO), in the scope of the Digital Twin for Evolutionary Changes in
water networks (DiTEC) project, file number 19454.

## References

  * Nassif et al. [2021] Ali Bou Nassif, Manar Abu Talib, Qassim Nasir, and Fatima Mohamad Dakalbab.  Machine learning for anomaly detection: A systematic review.  _Ieee Access_ , 9:78658–78700, 2021.
  * Khanal et al. [2020] Shristi Shakya Khanal, PWC Prasad, Abeer Alsadoon, and Angelika Maag.  A systematic review: machine learning based recommendation systems for e-learning.  _Education and Information Technologies_ , 25:2635–2664, 2020.
  * Jiang et al. [2018] Huimin Jiang, Chun Kit Kwong, WY Park, and Kai Ming Yu.  A multi-objective pso approach of mining association rules for affective design based on online customer reviews.  _Journal of Engineering Design_ , 29(7):381–403, 2018.
  * Agrawal et al. [1994] Rakesh Agrawal, Ramakrishnan Srikant, et al.  Fast algorithms for mining association rules.  In _Proc. 20th int. conf. very large data bases, VLDB_ , volume 1215, pages 487–499. Santiago, Chile, 1994.
  * Han et al. [2000] Jiawei Han, Jian Pei, and Yiwen Yin.  Mining frequent patterns without candidate generation.  _ACM sigmod record_ , 29(2):1–12, 2000.
  * Kaushik et al. [2023] Minakshi Kaushik, Rahul Sharma, Iztok Fister Jr, and Dirk Draheim.  Numerical association rule mining: A systematic literature review.  _arXiv preprint arXiv:2307.00662_ , 2023.
  * Telikani et al. [2020] Akbar Telikani, Amir H Gandomi, and Asadollah Shahbahrami.  A survey of evolutionary computation for association rule mining.  _Information Sciences_ , 524:318–352, 2020.
  * Sarker [2021] Iqbal H Sarker.  Machine learning: Algorithms, real-world applications and research directions.  _SN computer science_ , 2(3):160, 2021.
  * Qu et al. [2020] Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang.  Rnnlogic: Learning logic rules for reasoning on knowledge graphs.  _arXiv preprint arXiv:2010.04029_ , 2020.
  * Hogan et al. [2021] Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia d’Amato, Gerard de Melo, Claudio Gutiérrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan F. Sequeda, Steffen Staab, and Antoine Zimmermann.  _Knowledge Graphs_.  Number 22 in Synthesis Lectures on Data, Semantics, and Knowledge. Springer, 2021.  ISBN 9783031007903.  doi:10.2200/S01125ED1V01Y202109DSK022.  URL https://kgbook.org/.
  * Karabulut et al. [2023a] Erkan Karabulut, Salvatore F Pileggi, Paul Groth, and Victoria Degeler.  Ontologies in digital twins: A systematic literature review.  _Future Generation Computer Systems_ , 2023a.
  * Greco et al. [2021] Luca Greco, Pierluigi Ritrovato, and Mario Vento.  On the use of semantic technologies for video analytics.  _Journal of Ambient Intelligence and Humanized Computing_ , 12:567–587, 2021.
  * Berteloot et al. [2023] Théophile Berteloot, Richard Khoury, and Audrey Durand.  Association rules mining with auto-encoders.  _arXiv preprint arXiv:2304.13717_ , 2023.
  * Kishore et al. [2021] Sai Kishore, Vikram Bhushan, and KR Suneetha.  Applications of association rule mining algorithms in deep learning.  In _Computer Networks and Inventive Communication Technologies: Proceedings of Third ICCNCT 2020_ , pages 351–362. Springer, 2021.
  * Barati et al. [2017] Molood Barati, Quan Bai, and Qing Liu.  Mining semantic association rules from rdf data.  _Knowledge-Based Systems_ , 133:183–196, 2017.
  * d’Amato [2020] Claudia d’Amato.  Machine learning for the semantic web: Lessons learnt and next research directions.  _Semantic Web_ , 11(1):195–203, 2020.
  * Karabulut et al. [2023b] Erkan Karabulut, Victoria Degeler, and Paul Groth.  Semantic association rule learning from time series data and knowledge graphs.  In _Proceedings of the 2nd International Workshop on Semantic Industrial Information Modelling (SemIIM 2023) co-located with 22nd International Semantic Web Conference (ISWC 2023)_ , pages 1–7, 2023b.
  * Simsek et al. [2021] Mehmet Ulvi Simsek, Feyza Yildirim Okay, and Suat Ozdemir.  A deep learning-based cep rule extraction framework for iot data.  _The Journal of Supercomputing_ , 77:8563–8592, 2021.
  * Chakraborty et al. [2020] Manomita Chakraborty, Saroj Kumar Biswas, and Biswajit Purkayastha.  Rule extraction from neural network trained using deep belief network and back propagation.  _Knowledge and Information Systems_ , 62:3753–3781, 2020.
  * Patel et al. [2022] Harvendra Kumar Patel et al.  An innovative approach for association rule mining in grocery dataset based on non-negative matrix factorization and autoencoder.  _Journal of Algebraic Statistics_ , 13(3):2898–2905, 2022.
  * Chen and Guo [2023] Shuangshuang Chen and Wei Guo.  Auto-encoders in deep learning—a review with new perspectives.  _Mathematics_ , 11(8):1777, 2023.
  * Tamašauskaitė and Groth [2023] Gytė Tamašauskaitė and Paul Groth.  Defining a knowledge graph development process through a systematic review.  _ACM Transactions on Software Engineering and Methodology_ , 32(1):1–40, 2023.
  * Vincent et al. [2008] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol.  Extracting and composing robust features with denoising autoencoders.  In _Proceedings of the 25th international conference on Machine learning_ , pages 1096–1103, 2008.
  * Foorthuis [2020] Ralph Foorthuis.  The impact of discretization method on the detection of six types of anomalies in datasets.  _arXiv preprint arXiv:2008.12330_ , 2020.
  * Vrachimis et al. [2018] Stelios G Vrachimis, Marios S Kyriakou, et al.  Leakdb: a benchmark dataset for leakage diagnosis in water distribution networks:(146).  In _WDSA/CCWI Joint Conference Proceedings_ , volume 1, 2018.
  * Vrachimis et al. [2020] SG Vrachimis, DG Eliades, R Taormina, A Ostfeld, Z Kapelan, S Liu, MS Kyriakou, P Pavlou, M Qiu, and M Polycarpou.  Dataset of battledim: Battle of the leakage detection and isolation methods.  In _Proc., 2nd Int CCWI/WDSA Joint Conf. Kingston, ON, Canada: Queen’s Univ_ , 2020.
  * Granderson et al. [2022] Jessica Granderson, Guanjing Lin, Yimin Chen, Armando Casillas, Piljae Im, Sungkyun Jung, Kyle Benne, Jiazhen Ling, Ravi Gorthala, Jin Wen, Zhelun Chen, Sen Huang, , and Draguna. Vrabie.  Lbnl fault detection and diagnostics datasets, 08 2022.  URL https://data.openei.org/submissions/5763.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Yan et al. [2009] Xiaowei Yan, Chengqi Zhang, and Shichao Zhang.  Confidence metrics for association rule mining.  _Applied Artificial Intelligence_ , 23(8):713–737, 2009.
  * Raschka [2018] Sebastian Raschka.  Mlxtend: Providing machine learning and data science utilities and extensions to python’s scientific computing stack.  _The Journal of Open Source Software_ , 3(24), April 2018.  doi:10.21105/joss.00638.  URL https://joss.theoj.org/papers/10.21105/joss.00638.
  * Heidari et al. [2019] Ali Asghar Heidari, Seyedali Mirjalili, Hossam Faris, Ibrahim Aljarah, Majdi Mafarja, and Huiling Chen.  Harris hawks optimization: Algorithm and applications.  _Future generation computer systems_ , 97:849–872, 2019.
  * Vrbančič et al. [2018] Grega Vrbančič, Lucija Brezočnik, Uroš Mlakar, Dušan Fister, and Iztok Fister.  Niapy: Python microframework for building nature-inspired algorithms.  _Journal of Open Source Software_ , 3(23):613, 2018.
  * Stupan and Fister [2022] Žiga Stupan and Iztok Fister.  Niaarm: a minimalistic framework for numerical association rule mining.  _Journal of Open Source Software_ , 7(77):4448, 2022.
  * Yuan and Ding [2012] Jingbo Yuan and Shunli Ding.  Research and improvement on association rule algorithm based on fp-growth.  In _Web Information Systems and Mining: International Conference, WISM 2012, Chengdu, China, October 26-28, 2012. Proceedings_ , pages 306–313. Springer, 2012.

##  Appendix A Additional experiment

###  A.1 What is the effect of similarity threshold on the quality of the
rules learned by AE SemRL?

In this experiment, we investigate the effect of the similarity threshold of
AE SemRL on the quality of the rules on the 3 datasets. The experiments are
repeated 10 times on a subset of 7 randomly selected sensors each time (to
avoid the impractical run time of Naive SemRL as shown in Section 5.4.1), and
the average results are presented. Table 5 shows the results with similarity
threshold values varying between 0.9 and 0.5. The results show that when run
with relatively lower similarity thresholds, rules learned by AE SemRL imply
stronger associations based on the lift, leverage, and Zhang’s metric values.
Lower threshold values result in less statistical significance (lower support
and confidence).

Table 5: Effect of similarity threshold on the rule quality on the 3 datasets. Dataset |  Similarity Threshold |  Support |  Confidence |  Lift |  Leverage |  Zhang’s Metric
---|---|---|---|---|---|---
LeakDB |  0.9 |  0.277 |  0.951 |  1.49 |  0.017 |  0.427
0.8 |  0.267 |  0.919 |  1.59 |  0.019 |  0.458
0.7 |  0.26 |  0.896 |  1.657 |  0.021 |  0.47
0.6 |  0.253 |  0.875 |  1.735 |  0.022 |  0.49
L-Town |  0.9 |  0.468 |  0.994 |  1.064 |  0.008 |  0.502
0.8 |  0.452 |  0.871 |  1.138 |  0.016 |  0.53
0.7 |  0.436 |  0.918 |  1.169 |  0.018 |  0.567
0.6 |  0.409 |  0.864 |  1.176 |  0.018 |  0.549
LBNL |  0.9 |  0.42 |  0.985 |  1.044 |  0.004 |  0.447
0.8 |  0.416 |  0.976 |  1.057 |  0.005 |  0.449
0.7 |  0.416 |  0.967 |  1.05 |  0.005 |  0.446
0.6 |  0.416 |  0.96 |  1.05 |  0.005 |  0.454
0.5 |  0.413 |  0.955 |  1.052 |  0.005 |  0.453


$\displaystyle\hat{t}=2[(u_{2}+v_{2})\tan\theta-(u_{1}+v_{1})\cot\theta]^{2}$
(132) $\displaystyle\hat{y}=(x_{2}^{\prime}\tan\theta-
x_{1}^{\prime}\cot\theta)^{2}+(x_{2}\tan\theta-
x_{1}\cot\theta)^{2}+(y_{2}^{\prime}\tan\theta-y_{1}^{\prime}\cot\theta)^{2}$
$\displaystyle\hskip 5.69046pt+(y_{2}\tan\theta-
y_{1}\cot\theta)^{2}+(z_{2}^{\prime}\tan\theta-
z_{1}^{\prime}\cot\theta)^{2}+(z_{2}\tan\theta-z_{1}\cot\theta)^{2}$ (133)
$\displaystyle\hat{z}=(x_{1}+x_{2})[(x_{2}^{\prime}+x_{2})\tan\theta-(x_{1}^{\prime}+x_{1})\cot\theta]+(y_{1}+y_{2})[(y_{2}^{\prime}+y_{2})\tan\theta-(y_{1}^{\prime}+y_{1})\cot\theta]$
$\displaystyle\hskip
5.69046pt+(z_{1}+z_{2})[(z_{2}^{\prime}+z_{2})\tan\theta-(z_{1}^{\prime}+z_{1})\cot\theta]$
(134)
$\displaystyle\hat{s}=[(x_{2}^{\prime}+x_{2})\tan\theta-(x_{1}^{\prime}+x_{1})\cot\theta]^{2}+[(y_{2}^{\prime}+y_{2})\tan\theta-(y_{1}^{\prime}+y_{1})\cot\theta]^{2}$
$\displaystyle\hskip
5.69046pt+[(z_{2}^{\prime}+z_{2})\tan\theta-(z_{1}^{\prime}+z_{1})\cot\theta]^{2}$
(135)

From (116) and (117), it can be seen that the $Z^{\prime}$ mass squared,
$M_{Z^{\prime}}^{2}$, is determined by:

$\displaystyle
M_{Z^{\prime}}^{2}=\frac{\bar{M}_{Z^{\prime}}^{2}}{c_{Z^{\prime}}^{2}}\;.$
(136)

##  Appendix D Process of integrating out $Z^{\prime}$

From (116), the solution of Eq.(44) is

$\displaystyle
Z_{c}^{\prime\mu}(x)=-D^{\mu\nu}_{Z}J_{Z,\nu}(x)+O(p^{3})+\mbox{loop
corrections}\;,$ (137)

then

$\displaystyle\bar{S}_{Z^{\prime}}$ $\displaystyle=$ $\displaystyle\int
d^{4}x\bigg{[}-\frac{1}{2}J_{Z,\mu}D_{Z}^{\mu\nu}J_{Z,\nu}-J_{3Z,\mu^{\prime}}(D_{Z}^{\mu^{\prime}\nu^{\prime}}J_{Z,\nu^{\prime}})(D_{Z}^{\mu\nu}J_{Z,\nu})^{2}+g_{4Z}(D_{Z}^{\mu\nu}J_{Z,\nu})^{4}\bigg{]}$
(138) $\displaystyle+\mbox{loop corrections}\;,~{}~{}~{}$

where

$\displaystyle
D_{Z}^{-1,\mu\nu}D_{Z,\nu\lambda}=D_{Z}^{\mu\nu}D_{Z,\nu\lambda}^{-1}=g^{\mu}_{\lambda}\;,$
(139)

It can be shown that if our accuracy is on the order of $p^{4}$, then $p^{1}$
order $Z_{c}^{\prime}$ solution is sufficient because all contributions from
$p^{3}$ order $Z^{\prime}_{c}$ are at least on the order of $p^{6}$.

Combining (138), (117) and (118)and ignoring loop corrections, we obtain:

$\displaystyle\bar{S}_{Z^{\prime}}=\\!\int\\!d^{4}x\bigg{[}-\frac{1}{2}J_{Z0,\mu}D_{Z}^{\mu\nu}J_{Z0,\nu}-\frac{1}{\bar{M}_{Z^{\prime}}^{2}}J_{Z0,\mu}(\tilde{J}^{\mu}_{Z}\\!+\\!g_{1}\gamma\partial_{\nu}B^{\mu\nu})-\frac{1}{\bar{M}_{Z^{\prime}}^{6}}J_{3Z,\mu}J_{Z0}^{\mu}J_{Z0}^{2}+\frac{g_{4Z}}{\bar{M}_{Z^{\prime}}^{8}}J_{Z0}^{4}\bigg{]}\;.~{}~{}~{}~{}$
(140)

With the help of the following algebraic relations,

$\displaystyle\partial_{\mu}\mathrm{tr}[\tau^{3}X^{\mu}]=0$
$\displaystyle\mathrm{tr}[\tau^{3}(\partial_{\mu}X_{\nu}-\partial_{\nu}X_{\mu})]=-2\mathrm{tr}(\tau^{3}X_{\mu}X_{\nu})+i\mathrm{tr}(\tau^{3}\overline{W}_{\mu\nu})-ig_{1}B_{\mu\nu}$
$\displaystyle{\rm tr}(\tau^{3}X_{\mu}X_{\nu}){\rm
tr}(\tau^{3}X^{\mu}X^{\nu})$ (141) $\displaystyle=[{\rm
tr}(X_{\mu}X_{\nu})]^{2}-[{\rm tr}(X_{\mu}X^{\mu})]^{2}-{\rm
tr}(X_{\mu}X_{\nu}){\rm tr}(\tau^{3}X^{\mu}){\rm tr}(\tau^{3}X^{\nu})+{\rm
tr}(X_{\mu}X^{\mu})[{\rm tr}(\tau^{3}X_{\nu})]^{2}$
$\displaystyle\mathrm{tr}(TA)\mathrm{tr}(TBC)+\mathrm{tr}(TB)\mathrm{tr}(TCA)+\mathrm{tr}(TC)\mathrm{tr}(TAB)=2\mathrm{tr}(ABC)\;,$

where $\mathrm{tr}A=\mathrm{tr}B=\mathrm{tr}C=0$ and $T^{2}=1$. We can
simplify (140) into the form of the EWCL.

##  Appendix E $\mathcal{K}$ coefficients

In Minkowski space,

$\displaystyle\hat{F}_{0}^{2}$ $\displaystyle=$ $\displaystyle 2\int
d\tilde{p}\bigg{[}(-2\Sigma^{2}_{p}-p^{2}\Sigma_{p}\Sigma^{\prime}_{p})X_{p}^{2}+(2\Sigma^{2}_{p}+p^{2}\Sigma_{p}\Sigma^{\prime}_{p})\frac{X_{p}}{\Lambda^{2}}\bigg{]},$
(142) $\displaystyle{\cal K}_{1}$ $\displaystyle=$ $\displaystyle 2\int
d\tilde{p}\bigg{[}-2A_{p}X_{p}^{3}+2A_{p}\frac{X_{p}^{2}}{\Lambda^{2}}-A_{p}\frac{X_{p}}{\Lambda^{4}}+\frac{p^{2}}{2}\Sigma^{\prime
2}_{p}\frac{X_{p}}{\Lambda^{2}}-\frac{p^{2}}{2}\Sigma^{\prime
2}_{p}X_{p}^{2},\bigg{]},$ $\displaystyle{\cal K}_{2}$ $\displaystyle=$
$\displaystyle\int
d\tilde{p}\bigg{[}-2B_{p}X_{p}^{3}+2B_{p}\frac{X_{p}^{2}}{\Lambda^{2}}-B_{p}\frac{X_{p}}{\Lambda^{4}}+\frac{p^{2}}{2}\Sigma^{\prime
2}_{p}\frac{X_{p}}{\Lambda^{2}},-\frac{p^{2}}{2}\Sigma^{\prime
2}_{p}X_{p}^{2}\bigg{]},$ $\displaystyle{\cal K}_{3}$ $\displaystyle=$
$\displaystyle 2\int
d\tilde{p}\bigg{[}(\frac{4\Sigma^{4}_{p}}{3}-\frac{2p^{2}\Sigma^{2}_{p}}{3}+\frac{p^{4}}{18})(6X_{p}^{4}-\frac{6X_{p}^{3}}{\Lambda^{2}}+\frac{3X_{p}^{2}}{\Lambda^{4}}-\frac{X_{p}}{\Lambda^{6}}),$
$\displaystyle+(-4\Sigma^{2}_{p}+\frac{p^{2}}{2})(-2X_{p}^{3}+\frac{2X_{p}^{2}}{\Lambda^{2}}-\frac{X_{p}}{\Lambda^{4}})-\frac{X_{p}}{\Lambda^{2}}+X_{p}^{2}\bigg{]},$
$\displaystyle{\cal K}_{4}$ $\displaystyle=$ $\displaystyle\int
d\tilde{p}\bigg{[}(\frac{-4\Sigma^{4}_{p}}{3}+\frac{2p^{2}\Sigma^{2}_{p}}{3}+\frac{p^{4}}{18})(6X_{p}^{4}-\frac{6X_{p}^{3}}{\Lambda^{2}}+\frac{3X_{p}^{2}}{\Lambda^{4}}-\frac{X_{p}}{\Lambda^{6}})+4\Sigma^{2}_{p}(-2X_{p}^{3}+\frac{2X_{p}^{2}}{\Lambda^{2}}$
$\displaystyle-\frac{X_{p}}{\Lambda^{4}})+\frac{X_{p}}{\Lambda^{2}}-X_{p}^{2}\bigg{]},$
$\displaystyle{\cal K}_{5}$ $\displaystyle=$ $\displaystyle{\cal K}_{6}=0,$
$\displaystyle{\cal K}_{7}$ $\displaystyle=$ $\displaystyle 2\int
d\tilde{p}\bigg{[}(3\Sigma^{2}_{p}+2p^{2}\Sigma_{p}\Sigma^{\prime}_{p})X_{p}^{2}+[-2\Sigma^{2}_{p}-p^{2}(1+2\Sigma_{p}\Sigma^{\prime}_{p})]\frac{X_{p}}{\Lambda^{2}}\bigg{]},$
$\displaystyle{\cal K}_{8}$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle{\cal K}_{9}$ $\displaystyle=$ $\displaystyle 2\int
d\tilde{p}\bigg{[}(\Sigma^{2}_{p}+2p^{2}\Sigma_{p}\Sigma^{\prime}_{p})X_{p}^{2}-p^{2}(1+2\Sigma_{p}\Sigma^{\prime}_{p})\frac{X_{p}}{\Lambda^{2}}\bigg{]},$
$\displaystyle{\cal K}_{10}$ $\displaystyle=$ $\displaystyle 0,$
$\displaystyle{\cal K}_{11}$ $\displaystyle=$ $\displaystyle 4\int
d\tilde{p}\bigg{[}(-4\Sigma^{3}_{p}+p^{2}\Sigma_{p})X_{p}^{3}+(4\Sigma^{3}_{p}-p^{2}\Sigma_{p})\frac{X_{p}}{\Lambda^{2}}-(2\Sigma^{3}_{p}-\frac{1}{2}p^{2}\Sigma_{p})\frac{X_{p}}{\Lambda^{4}}+3\Sigma_{p}\frac{X_{p}}{\Lambda^{2}}$
$\displaystyle-3\Sigma_{p}X_{p}^{2}\bigg{]},$ $\displaystyle{\cal K}_{12}$
$\displaystyle=$ $\displaystyle 0,$ $\displaystyle{\cal K}_{13}$
$\displaystyle=$ $\displaystyle\int
d\tilde{p}\bigg{[}(\frac{1}{2}p^{2}\Sigma^{\prime}_{p}\Sigma^{\prime\prime}_{p}+\frac{1}{6}p^{2}\Sigma_{p}\Sigma^{\prime\prime\prime}_{p})X_{p}+(C_{p}-D_{p})\frac{X_{p}}{\Lambda^{2}}-(C_{p}-D_{p})X_{p}^{2}-2E_{p}X_{p}^{3}$
$\displaystyle+2E_{p}\frac{X_{p}^{2}}{\Lambda^{2}}-E_{p}\frac{X_{p}^{2}}{\Lambda^{4}}\bigg{]},$
$\displaystyle{\cal K}_{14}$ $\displaystyle=$ $\displaystyle-4\int
d\tilde{p}\bigg{[}-2F_{p}X_{p}^{3}+2F_{p}\frac{X_{p}^{2}}{\Lambda^{2}}-F_{p}\frac{X_{p}}{\Lambda^{4}}+\frac{p^{2}}{2}\Sigma_{p}^{\prime
2}\frac{X_{p}}{\Lambda^{2}}-\frac{p^{2}}{2}\Sigma^{\prime
2}_{p}X_{p}^{2}\bigg{]},$ $\displaystyle{\cal K}_{15}$ $\displaystyle=$
$\displaystyle-4\int
d\tilde{p}\bigg{[}-(\Sigma_{p}+\frac{1}{2}p^{2}\Sigma^{\prime}_{p})\frac{X_{p}}{\Lambda^{2}}+(\Sigma_{p}+\frac{1}{2}p^{2}\Sigma^{\prime}_{p})X_{p}^{2}\bigg{]},$
$\displaystyle{\cal K}^{\Sigma\neq 0}_{i}$ $\displaystyle=$
$\displaystyle{\cal K}_{i}-{\cal K}_{i}\bigg{|}_{\hat{\Sigma}=0}\hskip
56.9055pti=1,2,\ldots,15$ (143)

in which the short notations are

$\displaystyle\int d\tilde{p}\equiv
iN\int\frac{d^{4}p}{(2\pi)^{4}}e^{\frac{p^{2}-\hat{\Sigma}^{2}(p^{2})}{\Lambda^{2}}},$
(144) $\displaystyle\Sigma_{p}$ $\displaystyle\equiv$
$\displaystyle\hat{\Sigma}(p^{2}),$ $\displaystyle X_{p}$
$\displaystyle\equiv$ $\displaystyle\frac{1}{p^{2}-\hat{\Sigma}^{2}(p^{2})},$
$\displaystyle A_{p}$ $\displaystyle=$
$\displaystyle-\frac{2}{3}p^{2}\Sigma_{p}\Sigma^{\prime}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})-\frac{1}{3}\Sigma^{2}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})+\frac{1}{3}p^{2}\Sigma^{2}_{p}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})$
$\displaystyle-\frac{1}{6}p^{4}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p}),$ $\displaystyle B_{p}$
$\displaystyle=$
$\displaystyle-\frac{2}{3}p^{2}\Sigma_{p}\Sigma^{\prime}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})-\frac{1}{3}\Sigma^{2}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})+\frac{1}{3}p^{2}\Sigma^{2}_{p}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})$
$\displaystyle-\frac{1}{18}p^{4}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})-\frac{1}{6}p^{2}(-1-2\Sigma_{p}\Sigma^{\prime}_{p}),$
$\displaystyle C_{p}$ $\displaystyle=$
$\displaystyle\frac{1}{3}-\frac{1}{3}\Sigma_{p}\Sigma^{\prime}_{p}-\frac{1}{2}p^{2}\Sigma^{\prime
2}_{p},$ $\displaystyle D_{p}$ $\displaystyle=$
$\displaystyle\frac{1}{2}p^{2}\Sigma^{\prime
2}_{p}-\frac{1}{3}p^{2}\Sigma_{p}\Sigma^{\prime\prime}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})-\frac{2}{9}p^{4}\Sigma^{\prime}_{p}\Sigma^{\prime\prime}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})]-\frac{2}{9}p^{4}\Sigma^{\prime
2}_{(}p-\Sigma^{\prime 2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})$
$\displaystyle-\frac{1}{3}p^{2}\Sigma_{p}\Sigma^{\prime}_{p}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p}),$ $\displaystyle E_{p}$
$\displaystyle=$
$\displaystyle-\frac{1}{6}p^{2}\Sigma_{p}\Sigma^{\prime}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})^{2}-\frac{1}{9}kp^{4}\Sigma^{\prime
2}_{p}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})^{2},$ $\displaystyle F_{p}$
$\displaystyle=$
$\displaystyle-\frac{4}{3}p^{2}\Sigma_{p}\Sigma^{\prime}_{p}+\frac{4}{3}p^{2}(\Sigma_{p}\Sigma^{\prime}_{p})^{2}-\frac{2}{3}\Sigma^{2}_{p}+\frac{2}{3}\Sigma_{p}^{3}\Sigma^{\prime}_{p}+\frac{1}{3}p^{2}\Sigma^{2}_{p}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})$ (145)
$\displaystyle-\frac{1}{9}p^{4}(-\Sigma^{\prime
2}_{p}-\Sigma_{p}\Sigma^{\prime\prime}_{p})-\frac{1}{3}p^{2}(-1-2\Sigma_{p}\Sigma^{\prime}_{p})-\frac{1}{2}p^{2}.$

## References

  * (1) C.T.Hill, Phys.Lett.B 345, 483(1995).
  * (2) R. S. Chivukula, B. A. Dobrescu, and J. Terning, Phys. Lett. B 353, 289(1995).
  * (3) K.Lane and E.Eichten, Phys.Lett. B 352, 382(1995).
  * (4) D. Kominis, Phys. Lett. B 358, 312(1995); G. Buchalla, G. Burdman, C. T. Hill, and D. Kominis, Phys. Rev. D 53, 5185(1996).
  * (5) K.Lane, Phys. Rev. D 54, 2204(1996).
  * (6) T.Appelquist and G-H. Wu, Phys. Rev. D 48, 3235(1993); D 51, 240(1995).
  * (7) E. Farhi and L. Susskind, Phys. Rep. 74, 277 (1981) and references therein.
  * (8) H.H.Zhang, S.Z.Jiang, J.Y.Lang and Q.Wang, Phys. Rev. D. 77, 055003(2008).
  * (9) J.Y.Lang, S.Z.Jiang and Q.Wang, Phys. Rev. D. 79, 015002(2009).
  * (10) F.Braam, M.Flossdorf, R.S.Chivukula, S.DiChiara and E.H.Simmons, Phys. Rev. D 77, 055005(2008).
  * (11) J.Y.Lang, S.Z.Jiang and Q.Wang, Phys. Lett. B 673, 63(2009).
  * (12) E.Bagan, D.Espriu, J.Manzano, Phys. Rev. D 60, 114035(1999).
  * (13) F. Sannino, arXiv:0804.0182[hep-ph].
  * (14) T.Appelquist and F.Sannino, Phys.Rev. D 59, 067702(1999).
  * (15) D. D. Dietrich and F. Sannino, Phys. Rev. D. 75, 085018(2007).
  * (16) T. Banks and A. Zaks, Nucl. Phys. B 196, 189(1982).
  * (17) K.Yamawaki, Int. J. Mod. Phys. A 25, 5128(2010).
  * (18) K.I.Aoki, M.Bando, T.Kugo, M.G.Mitchard and N.Nakatani, Prog. Theor. Phys. 84, 683(1990).
  * (19) T.Appelquist, G.T.Fleming and E.T.Neil, Phys. Rev. D 79, 076010(2009).
  * (20) T.Appelquist, M.Piai, and R.Shrock, Phys. Rev. D 69, 015002(2004).
  * (21) H.Pagels and S.Stokar, Phys. ReV. D 20, 2947(1979).
  * (22) S.Dutta, K.Hagiwara, Q.S.Yan, K.Yoshida, Nucl. Phys. B 790, 111(2008).