# A Historical Review of Forty Years of Research on CMAC

Frank Z. Xing
School of Computer Science and Engineering
Nanyang Technological University
<EMAIL_ADDRESS>

###### Abstract

The Cerebellar Model Articulation Controller (CMAC) is an influential brain-
inspired computing model in many relevant fields. Since its inception in the
1970s, the model has been intensively studied and many variants of the
prototype, such as KCMAC, MCMAC, and LCMAC, have been proposed. This review
article focus on how the CMAC model is gradually developed and refined to meet
the demand of fast, adaptive, and robust control. Two perspective, CMAC as a
neural network and CMAC as a table look-up technique are presented. Three
aspects of the model: the architecture, learning algorithms and applications
are discussed. In the end, some potential future research directions on this
model are suggested.

##  I INTRODUCTION

The Cerebellar Model Articulation Controller (CMAC) was proposed by J. S.
Albus in 1975 [2]. Parallel at this time in the history, the concept of
perceptron [23] had already been popular, whereas effective learning schemes
to tune perceptrons [24] were not on the stage yet. In 1969, Minsky and Papert
also pointed out the limitations that the exclusive disjunction logic cannot
be solved by the perceptron model in their book Perceptrons: An Introduction
to Computational Geometry. These facts made it less promising to consider CMAC
as a neural network form. Consequently, although the name of CMAC appears bio-
inspired enough, and the theory that the cerebellum is analogous to a
perceptron has been proposed earlier [1], CMAC was emphasized to be understood
as a table referring technique that can adaptive to real-time control system.
Nevertheless, the underlying bioscience mechanism was addressed again in 1979
by Albus [3], which always gives the CMAC model two different ways of
interpretation.

The structure of CMAC was originally described as two inter-layer mappings
illustrated in Fig. 1. The control functions are represented in the weighted
look-up table, rather than by solution of analytic equations or by analog [2].

Figure 1: The primary CMAC structure

If we use $\mathit{S}$ to denote sensory input vectors, and let $\mathit{A}$
and $\mathit{P}$ stand for association cells and response output vectors
respectively, both CMAC and multilayer percptrons (MLP) model can be
formalized as:

$\displaystyle f:\mathit{S}\rightarrow\mathit{A}$ $\displaystyle
g:\mathit{A}\rightarrow\mathit{P}$

the final output can be calculated as:

$y=\sum\mathit{A}^{*}_{i}w_{i}$

where the asterisk denotes a link or activation between certain association
cell and the output. The nuance between MLP and CMAC model is that, for
mapping $f$, MLP model is fully connected but CMAC restricts the association
in a certain neighboring range. This property of mapping significantly
accelerates the learning process of CMAC, which is considered a main advantage
of it comparing to other neural network models.

It is notable that CMAC may not represent accurately how the human cerebellum
works, even at a most simplified level. For instance, recent biological
evidence from eyelid conditioning experiments suggests that the cerebellum is
capable of computing exclusive disjunction [34]. However, CMAC is still an
important computational model, because the restriction on mapping function
effectively decreased the chance of been trapped in a local minimum during
learning process.

Despite the advantage aforementioned, CMAC has the following disadvantages as
well [25]:

  * •

many more weight parameters are needed comparing to normal MLP model

  * •

local generalization mechanism may cause some training data to be incorrectly
interpolated, especially when data is sparse considering the size of CMAC

  * •

CMAC is a discrete model, analytical derivatives do not exist

As a response to these problems, modified or high order CMAC, storage space
compressing, and fast convergent learning algorithms are continuously studied.
These discoveries will be elaborated in the following sections. Recent
advances in Big Data and computing power seem to have watered down these
problems. But in many physical scenarios, the computing power are still
restricted and high speed responses are required. This serves for the reason
to further study CMAC-like models, though it has been in and out of fashion
for several times.

Although there has been few other pioneer review works on CMAC, for instance
by Mohajeri et al. in 2009 [20], this article is inventive for its
chronological perspective. rather than emphasizing on detailed techniques. The
remainder of the article is organized as follows: Section II provides the
evolution trajectory of CMAC structure and efficient storage techniques.
Section III discusses the learning algorithms. Section IV presents various
circumstances that CMAC model has been applied. Section V summarizes the
paper, and instigates discussions about potential improvements that can be
made on CMAC model.

##  II ARCHITECTURE

###  II-A Basic Architectures

Before the CMAC was proposed in the 1970s, the anatomy and physiology of
cerebellum has been studied for a long time. It is widely agreed that many
different type of nerve cells are involved in cerebellar functioning. Fig. 2
shows the computational model proposed by Mauk and Donegan [18]. A more simple
and implementable model proposed by Albus [3] is exhibited in Fig. 3.

Figure 2: Mauk’s model assumes complex interaction between different type of
cells: open arrow stands for plastic synapses; filled circle arrow stands for
inhibitory synapses; hollow square arrow stands for excitatory synapses.
Figure 3: Albus’ model [1] of cerebellum resembles a forward feed perceptron.
It assumes climbing fiber activity would cause parallel fiber synapses to be
weakened. S stands for stellate b cells, B stands for basket cells

Based on the computational model of cerebellum (Fig. 3), the primary CMAC
structure as shown in Fig. 1 is conceived. While it is obvious that high
dimensional proximity of association rules cannot be captured in this primary
form, because the nodes are arranged into one dimensional array. A simple
solution to this problem is to introduce some nonlinearity to the first
mapping. As a result, another layer called “conceptual memory” was soon added
to the CMAC structure, which involves one additional mapping to the primary
structure. The function of conceptual memory is illustrated in Fig. 4.

If we use $\mathit{A}$ to represent the actual memory (Association Cells),
$\mathit{M}$ is the conceptual memory to encode $\mathit{S}$. Then the
conceptual mapping $f$ is more sparse and constrained within a certain range,
but mapping $g$ could be random.

$\displaystyle f:\mathit{S}\rightarrow\mathit{M}$ $\displaystyle
g:\mathit{M}\rightarrow\mathit{A}$ $\displaystyle
h:\mathit{A}\rightarrow\mathit{P}$

When it comes to implementation, the connectivism perspective to recognize
CMAC as a neural network and the table referring perspective are equivalent.
Fig. 5 illustrates the difference at a conceptual level [25]. To the upper
part is a two input one output neural network structure, to the lower part is
a two input one output table look-up structure.

An intuitive observation from both Fig. 4 and Fig. 5 is that the number of
weights will increase exponentially with the number of input variables. This
problem brings out two challenges: 1) The storage of weights become space
consuming; 2) The training process becomes difficult to converge and waiting
time before termination will lengthen.

Figure 4: CMAC with conceptual memory

Figure 5: A conceptual level comparison of two different perspectives

A previously used technique to solve the first challenge is called tile
coding, which latter was developed to an adaptive version as well [36]. The
advantage of tile coding is that we can strictly control the number of
features through tile split. Another commonly employed trick is called
hashing. This technique is applied to CMAC in the 1990s, and maps a large
virtual space $\mathit{A}$ to a smaller physical address
$\mathit{A^{\prime}}$. Many common hashing function $f_{h}$ can be used, for
instance from MD5 or DES, which are fundamental methods in cryptography.
However, how to reduce the collision for specific problems according to the
data property is still considered an art.

Literature [25] introduced a hardware implementation which uses selected
binary bits of indexes as the hashing code. Whereas other research, e. g.
[35], claims that due to the learning rate diminishing and slower convergence,
hashing is not effective for enhancing the capability of approximation by
CMAC. Therefore, many other attempts have been made, such as neighbor
sequential, CMAC with general basis functions, and adaptive coding [7], which
is a similar idea to hashing in the sense of weight space compression.

###  II-B Modified Architectures

Since simply increasing the CMAC size gives diminishing returns, two
directions of modification are undertaken to push forward the research on
CMAC. The _first_ consideration is to combine multiple low dimensional CMACs.
The _second_ consideration is to introduce other properties, for example
spline neurons, fuzzy coding or cooperative PID controller.

Cascade CMAC architecture was firstly proposed in 1997 for the purpose of
printer calibration [10] (Fig. 6). Input variables are sequentially added to
keep each of the CMAC component two dimensional.

Figure 6: Cascade CMAC architecture

Another method to combine multiple CMACs can be realized by voting technique.
If we regard the Cascade CMAC model as a fusion of input information at a
feature level, then the voting CMACs can be reckoned as a fusion at decision
level. Each small CMAC just accept a subset of the whole input space. In this
case an important antecedent is that input data is well partitioned. The
reason to this requirement is that voting lift can only be achieved by
heterogeneous expert networks. Taken this into account, some prior knowledge
of input data or unsupervised clustering techniques can be applied in this
stage.

If we make more efforts for dimension reduction, multiple levels of voting can
be used. Then the architecture can be reckoned as a Hierarchical CMAC
(H-CMAC), which is described by Tham [32] in 1996. H-CMAC has several
advantages, such as less storage space and fast adaptation for learning non-
linear functions. In Fig. 7, a two level H-CMAC is illustrated. It is
noticeable that each conventional CMAC components in different layers plays
different role. The gating network works at a higher level.

Figure 7: Hierarchical CMAC architecture, adapted from [32]

These architectures can be employed at the same time with more fundamental
modifications for the second consideration. In 1992, Lane et al. [11] descried
high order CMAC as CMAC with binary neuron output replaced by spline
functions. This modification brings about more parameters of splines, but
makes the output derivable, which sometimes gives a better performance because
the learning phase goes deeper. Sharing the idea to allow more meticulous
transfer function, a similar modification can be made by introducing
linguistic rules and fuzzy logic.

Linguistic CMAC (LCMAC) was proposed by He and Lawry based on label semantics,
rather than mapping functions in 2009. A cascade of LCMAC series was further
developed in 2015 [8]. Borrowing the terminology of “focal element” from
evidence theory, the properties used to activate it is represented as
membership function (usually trapezoidal) of several attributes. Therefore,
for each input tuple, the excited neurons form a hypercube in the matrix of
all the weights as memory. The responsive output can be distributionally
depicted as:

$P(a|\mathbf{x})=\prod\limits_{d=1}^{N}m_{x_{d}}(F_{d_{i}})$

where $P$ is the probability of some memory unit $a$ been activated given the
input vector $\mathbf{x}$. $F$ denotes focal element. $d_{i}$ is the index of
linguistic attributes. $m$ is the hidden weights for $F$ called “mass
assignment”.

Fuzzy CMAC (FCMAC) is yet another form of fuzzy coding. The intuition to use
fuzzy representation is similar to using spline function. For most well
defined problems, the nature of CMAC approximation is using multiple steps to
emulate a smooth surface. Proper selection of fuzzy membership function would
obviously relief the pressure of weight storage and training. From my
understanding, FCMAC is an inverse structure of many established Neuro-Fuzzy
Inference Systems. Usually, two extra fuzzy/defuzzy layers are added next to
the association layer, the consequents can be Mamdani type, TSK type, weights,
or a hybrid of them, e. g. Parametric-FCMAC (PFCMAC) [21]. More advanced FCMAC
models, maybe inspired by spline methods, use interpolation to solve the
discrete inference problem. In 2015, Zhou and Quek proposed FIE-FCMAC [39],
which adds fuzzy interpolation and extrapolation to a rigid CMAC structure.

Recently, CMAC applications to more specific scenarios are studied. For
example, for control of time-varying nonlinear system, a combination of Radial
Basis Function network and the local learning feature of CMAC is proposed
(RBFCMAC). It is reported that using RBFs can prevent parameter drift and
accelerate synchronization speed to the changing system [17]. For this type of
combination, beside RBF, Wavelet Neural Network (WNN), fuzzy rule neuron and
recurrent mechanism [15] or a mingle of them can also be employed with CMAC
model simultaneously. Previous works, such as [38], have provided evidence
that these features are effective for modeling complicated dynamic systems.

In a broader scenario, CMAC can be applied with other control systems as well
(Fig. 8). Traditionally, the role of CMAC at the primary stage is to assist
the output of a main controller. As the training proceed, error between CMAC
and the actual model decays. CMAC takes charge of the main controller. Back-
forward signal acceptor or conjugated CMACs are often used to accelerate this
process [13]. More precisely, this arrangement is a change of information flow
but not a change of architecture.

Figure 8: A combined control system of CMAC and PID

Similarly, CMAC structures that modifies the storage optimizing methods, for
example quantization [16] and multi-resolution [19], will only result in
architectural difference from a hardware implementation sense. According to my
personal understanding, they are the same thing regarding the conceptual
structure, though these techniques are of sufficient interests to be discussed
in Section III.

##  III LEARNING ALGORITHM

The original form of learning proposed Albus is based on backward propagation
of errors. The fast convergence of this algorithm is proved mathematically by
succeeding researches. Specifically, the convergence rate is only governed by
the size of receptive fields for association cells [37]. Some study [25]
suggests that it would be useful to distinguish between target training and
error training, despite they share the same mathematical form. In the weights
updating rule,

$w_{i}(k+1)=w_{i}(k)+\alpha\frac{Error}{count(\mathit{A}^{*})}\ x_{i}$

$k$ is the epoch times, $\alpha\in[0,1]$ is the learning rate, $x_{i}$ is a
state indicator of activation. The learning process is theoretically faster
with a larger $\alpha$, while overshooting may occur. If the difference
between output and the desired value $\Delta y=y-\hat{y}$ can well define the
error, target training and error training will be equivalent. In certain
cases,

$Error=\frac{1}{2c}\ (y-\hat{y})^{2}$

is a popular cost function as well.

Based on the original learning algorithm, many developments are further
derived. Most of them can be categorized into two directions of improvement.
The first relies on extra supervisory signals or value assignment mechanism
based on statistics. The second endeavors to optimize the use of memory. From
a more practical sense, the dichotomy can be understood as learning to adjust
value of weights, and learning to adjust number or size of weights.

###  III-A Adjusting value of weights

Facing the trade off between speed of convergence and learning stability, it
is intuitive to consider using a relatively large $\alpha$ at the beginning,
and slow down the weight adjustment near the optimum point. This improvement
is called adaptive learning rate [14]. It can be achieved by using two CMAC
components, one as main controller, another as supervisory controller or
compensated controller. Another way to achieve this adaption is by imposing a
resistant term to the weight updating rule:

$w_{i}(k+1)=w_{i}(k)+\frac{\alpha_{0}}{c\alpha_{i}}\frac{Error}{count(\mathit{A}^{*})}\
x_{i}$

In the above rule, $\alpha_{0}$ and $c$ are constants, $\alpha_{i}$ denotes
the average activation times of the memory units that have been activated by
training sample $i$.

For both fixed learning rate and adaptive learning rate, weights adjustment
start from a randomized set of parameters. Experiments suggest that for sparse
data, even if the training samples are within the local generalization range,
perfect linear interpolation may not be achieved [25]. As a result, the
approximation may appears to have many small zigzag patterns. Therefore, the
weight smoothing technique is proposed. After each iteration, the weights are
globally adjusted according to:

$w_{i}(A^{*}_{j})=(1-\delta)\
w_{i}(A^{*}_{j})+\frac{\delta}{count(\mathit{A}^{*})}\sum\limits^{count(\mathit{A}^{*})}_{k=1}w_{i}(A^{*}_{k})$

where $\delta$ is the proportional coefficient measuring the share of the
weight with index $j$ that needs to be replaced by the average of all
activated weights $\mathit{A}^{*}$.

While the weight smoothing technique tries to affect as much memory as
possible in one iteration, repeated activation of the same units may not be a
good thing. In 2003, research [26] pointed out that equally assign the error
to each weight is not a meticulous method. During the learning process, if an
associative memory is activated many times, which means many relevant samples
are already learned, the weight should be more close to the desired value. In
other words, the weight value is more “credible”. In this situation, less
error should be assigned to it so that other memory units can learn faster.
This rule is called learning based on credit assignment:

$w_{i}(k+1)=w_{i}(k)+\frac{\alpha f(i)^{-1}}{\sum\limits^{g}_{i=1}f(i)^{-1}}\
(y-\sum\limits^{g}_{i=1}w_{i}(k))\ x_{i}$

where $g$ is a parameter regarding the degree of local generalization, $f(i)$
records the times memory unit $i$ has been activated. Further research has
proved that the convergence is guaranteed with learning rate $\alpha<2$.

The hardware implementation of CMAC memory enables other interpretations of
the associative architecture. If we recognize it as a self-organizing feature
map (SOFM), competitive learning algorithm can be realized. With input
variables $\bm{x}=\\{x_{1},\ x_{2},\ ...,\ x_{n}\\}$, the output can directly
be the weight of the winning neuron. The weights updating rule can be
formalized according to Hebbian theory:

$w_{\bm{x}}(k+1)=w_{\bm{x}}(k)+\alpha\ (y(k)-w_{\bm{x}}(k))$

Note that the index of $\bm{x}$ can be time dependent.

A modified version of the aforementioned rule involves not only inputs, but
also errors as feedback:

$w_{\bm{x},\bm{e}}(k+1)=w_{\bm{x},\bm{e}}(k)+\alpha\
(y(k)-w_{\bm{x},\bm{e}}(k))$

Using this learning mechanism, the SOFM-like CMAC is named MCMAC. In 2000, Ang
and Quek [5] proposed learning with momentum, neighborhood, and averaged fuzzy
output for both CMAC and MCMAC. For CMAC and MCMAC with momentum, the weights
updating rules can be written as:

$\displaystyle\Delta w_{j}(k+1)=\alpha\ \Delta w_{j}(k)+\eta\
\delta_{j}(k)y_{j}(k)$ $\displaystyle\Delta w_{\bm{x},\bm{e}}(k+1)=\alpha\
\Delta w_{\bm{x},\bm{e}}(k)+\lambda(1-\alpha)[y(k)-w_{\bm{x},\bm{e}}(k)]$

where the first term represents a momentum, the second term is a back
propagation term with learning rate $\eta$ and local gradient $\delta_{j}$.
$j$ is the index for activated weights.

Therefore, given a sequential learning process, the aggregational weights
adjustment can be derived from the above rules:

$\displaystyle\Delta w_{j}(k+1)$ $\displaystyle=\eta\
\sum\limits^{k}_{i=1}\alpha^{k-1}\delta_{j}(i)y_{j}(i)$ $\displaystyle=-\eta\
\sum\limits^{k}_{i=1}\alpha^{k-1}\frac{\partial Error}{\partial w_{j}(k)}$

When the sign of $\frac{\partial Error}{\partial w_{j}}$ keeps unchanged,
$\Delta w_{j}$ is accelerating; while if the sign is reversing, $\Delta w_{j}$
will slow down to stabilize the learning process.

The neighborhood learning rule proposed by Ang and Quek [5] serves the same
purpose as weight smoothing technique. However, they used the Gaussian
function to put more attention to those neurons surrounding the winning neuron
instead of evenly adjusting each weight regardless of the distance. Weights
updating rule for MCMAC with momentum and neighborhood in singular form is:

$\Delta w_{i}(k+1)=\alpha\ \Delta
w_{i}(k)+h_{ij}[\lambda(1-\alpha)(y(k)-w_{i}(k))]$

where

$h_{ij}=\exp\Big{(}-\frac{|r_{j}-r_{i}|^{2}}{2\sigma^{2}}\ \Big{)}$

is the distance metric between neuron $j$ and the winning neuron $i$.

Beside using additional terms such as momentum and neighborhood, kernel method
can also be applied to CMAC learning. In 2007, Kernel CMAC (KCMAC) was
proposed [9, 11] to reduce the CMAC dimension which usually hazard the
training speed and convergence. KCMAC treats the association memory as the
feature space of a kernel machine, thus weights can be determined by solving
an optimization problem. The supervised learning using error $\bm{e}$ as slack
variables is to achieve:

$\displaystyle\min_{\bm{w},\bm{e}}\
\frac{1}{2}\bm{w}^{T}\bm{w}+\frac{\beta}{2}\sum\limits_{i=1}^{n}\bm{e}_{i}^{2}$
$\displaystyle s.t.\ \bm{w}^{T}\phi(u_{i})+\frac{\beta}{2}\bm{e}_{i}\geqslant
1,\ \ i=1,2,...,n$

where $\bm{w}$ denotes weights, coefficient $\beta$ serves as penalty
parameter, $\phi(\cdot)$ is the mapping function and
$K(\bm{u},\bm{w})=\phi(\bm{u})\cdot\phi(\bm{w})$ is the kernel function.

The standard procedure to this problem is to solve the maxima-minima of
Lagrangian function. Though other learning method can be employed as well, for
instance, using Bayesian Ying-Yang (BYY) learning as proposed in 2013 by Tian
et al [33]. The key idea behind BYY learning can be represented by harmonizing
the joint probability with different product form of Bayesian components. In
this specific KCMAC case, $\bm{u}$ and output $\bm{z}$ are observable, while
$\bm{w}$ is a hidden variable. The joint distribution can either be written as
$ying$ form or $yang$ form.

$\displaystyle
p_{ying}(\bm{u},\bm{z},\bm{w})=p(\bm{w})p(\bm{u}|\bm{w})p(\bm{z}|\bm{u},\bm{w})$
$\displaystyle
p_{yang}(\bm{u},\bm{z},\bm{w})=p(\bm{u})p(\bm{z}|\bm{u})p(\bm{w}|\bm{u},\bm{z})$

Our goal is to maximize $\mathscr{H}(p_{ying},p_{yang})$,

$\mathscr{H}(p_{ying},p_{yang})=\iiint p_{ying}\ln p_{yang}\
d\bm{u}\,d\bm{z}\,d\bm{w}$

In practice, $\Delta\mathscr{H}$ is frequently calculated depending on how the
conditional probabilities are estimated and maximum of $\mathscr{H}$ is
achieved by searching heuristically.

###  III-B Adjusting number of weights

Adjusting number of weights is chiefly realized by introducing multi-
resolution and dynamic quantization techniques. As Section I has explained,
CMAC was firstly used for real time control system. Consequently, the
structural design fits the hardware implementation well. Many CMAC variants,
such as LCMAC and FCMAC, inherit the memory units division with a lattice-
based manner. Inputs are generally built on grids with equal space. This
characteristic adds local constraints to the value of adjacent units.

If we consider this problem from a function approximation perspective, it is
also rather intuitive that local complex shape needs a larger number of low-
order elements to approach. Naturally, multi-resolution lattice techniques
[19] were proposed in the 1990s.

With our prior knowledge, some metrics can be used to determine the
resolution, for example, the variation of output in certain memory unit areas,
which can be formalized as following:

$resolution\ \propto\ v=\frac{1}{N}\sum\limits_{j=1}^{N}|y_{j}-\bar{y}|$

where $N$ is the number of output samples, $v$ is the variance. Other attempts
use a tree structure to manage the resolution hierarchically. New high
resolution lattice is generated only if the threshold of variance is exceeded.

The concept of quantization is almost identical to resolution. The nuance may
be that the terminology _quantization_ puts more emphasis on the discretion of
continuous signal. Furthermore, increasing resolution will also cause the
number of weights to grow. Quantization deals with a given memory capacity
problem.

To the best of my knowledge, the idea of adaptive quantization was initially
proposed in 2006 [16]. The algorithm used to interpolate points looks on
change of slopes, which is also similar to the variance metric discussed
above. The input space is initialized with uniform quantization. For each
point $x_{i}$, the slopes are calculated by neighbor points.

$\hat{slope}_{j}=\frac{f(x_{j})-f(x_{i})}{x_{j}-x_{i}},\ \ j=1,2,3...$

Here $f$ stands for the mapping function between input vector and association
cells. The change of sign for corresponding directions indicates finer local
structure, or fluctuation in other words, thus a new critical point is added
to split the interval. The termination condition is that, within all
intervals, the difference of output values should not exceed an experimental
constant $\mathit{C}$ [28]. The adaptive quantization technique is later
developed to the Pseudo Self Evolving CMAC (PSECMAC) model [30], which further
introduced neighborhood activation mechanism.

##  IV APPLICATION

Though CMAC was firstly proposed for manipulator control, during the past
decades it has been proved effective in robotic arm control, fractionator
control, piezoelectric actuator control [22], mechanic system, signal
processing, intelligent driver warning system, fuel injection, canal control
automation, printer color reproduction, ATM cash demand [31], and many other
fields [7]. This can be attributed to the fast learning and stable performance
of CMAC models. Moreover, engineering-oriented software and toolkit also help
to promote the application of CAMC. In the following part, CMAC application to
two emerging engineering fields are elaborated.

###  IV-A Financial Engineering

The practice side of financial engineering has employed various instruments to
model the price and risk of bond, stock, option, future and other derivatives.
In most cases, historic data can be partitioned into chunks of selected time
span to enable a supervised learning process. In 2008, Teddy et al [29]
proposed an improved CMAC variant (PSECMAC) to model the price of currency
exchange American call option. Three variables are taken into consideration:
difference between strike price and current price, time of maturity, and
pricing volatility. Thus the pricing function is formulated as:

$C_{0}=f(S_{0}-X,T,\sigma_{30})$

The article reported PSECMAC as the best-performing model among several CMAC-
like systems. It is also reported that most of the CMAC models produce better
result than using Black-Scholes model in sense of RMSE. Though for American
option, Black-Scholes model is not a good benchmark because it is sensitive to
details of calculation.

This work further constructed an arbitrage system based on the pricing model.
Positions are adjusted according to the Delta hedging ratio. Experiments
suggested the model has a marginal positive ROI, omitting transaction costs.

###  IV-B Adaptive Control

The application of CMAC on commercial devices may be more advantageous. The
pressure to reduce cost and demand of embedded controller make CMAC-like
models a good choice. Recently, studies have been carried on adaptive control
of disabled wheelchair and seatless unicycle [12]. This type of problems can
be formalized as controlling a set of variables in certain range (e. g. speed
and balance angle) with a set of unknown and varying variables (e. g. friction
to the ground and weight of the rider).

Li et al [12] proposed a TSK type FCMAC to synthesis the equations of adaptive
steering control. The back-stepping error is associated with the torque
$\tau$, which can simultaneously effect on critical moments.

$\displaystyle\ddot{\theta}=\bar{A}(\theta,\dot{\theta})+\bar{B}(\theta)(\tau-\mu\dot{\phi}-c\
\texttt{sgn}(\dot{\phi}))$
$\displaystyle\ddot{\phi}=\bar{C}(\theta,\dot{\theta})+\bar{D}(\theta)(\tau-\mu\dot{\phi}-c\
\texttt{sgn}(\dot{\phi}))$

As the output adapting to the moment parameters, the balance angle is
controlled near zero.

The performance of FCMAC is benchmarked with a linear-quadratic regulator for
differential equations to describe the state of the motor. Simulations suggest
that LQR is not able to converge speed and angle of balance, while FCMAC
provides satisfactory result.

##  V DISCUSSIONS

Referring to Section IV, CMAC was proved to be effective in many classic
control problem and has been applied to emerging engineering problems.
However, this model seems have encountered a bottleneck because of the lack of
fundamental breakthrough during the past decade. Nowadays, issues discussed
are mainly focused on trivial modification on memory structure and learning
algorithm. The framework of error propagation or minimization of loss function
is kept unchanged.

According to my understanding, the limitation of current CMAC models can be
ascribe to its over simplification of the cerebellum structure. Therefore, the
next generation cerebellar model may adopt new discoveries from neuroscience.
For example, the associative memory cells may take different roles rather than
been treated identically. In fact, anatomical models usually feature several
types of elementary cerebellar processing units. Meanwhile, the theory of
Spike Timing Dependent Plasticity (STDP) suggests that the learning process of
firing neurons may be ordered [6]. This feature can introduce far more
complexity to the current learning algorithm.

## References

  * [1] J. S. Albus, “A Theory of Cerebellar Function,” _Mathematical Biosciences_ , pp. 25–-61, 1971.
  * [2] J. S. Albus, “A New Approach to Manipulator Control: the Cerebellar Model Articulation Controller (CMAC),” _Trans. ASME, Series G. Journal of Dynamic Systems, Measurement and Control_ , 97, pp. 220–-233, 1975.
  * [3] J. S. Albus, “Mechanisms of Planning and Problem Solving in the Brain,” _Mathematical Biosciences_ , 45, pp. 247–-293, 1979.
  * [4] P. C. E. An, W.T. Miller, and P.C. Parks, “Design Improvements in Associative Memories for Cerebellar Model Articulation Controllers,” in _Proceedings of ICANN_ , pp. 1207–-10, 1991.
  * [5] K. K. Ang and C. Quek, “Improved MCMAC with momentum, neighborhood, and averaged trapezoidal output,” _IEEE Transactions on Systems. Man and Cybernetics: PartB_ , 30(3), pp. 491–-590, 2013.
  * [6] N. Caporale and Y. Dan, “Spike Timing–Dependent Plasticity: A Hebbian Learning Rule,” _Annual Review of Neuroscience_ , 31(1), pp. 25–-46, 2008.
  * [7] P. Duan and H. Shao, “CMAC Neural Network based Neural Computation and Neuro-control,” _Information and Control (in Chinese)_ , 28(3), 1999.
  * [8] H. He, Z. Zhu, A. Tiwari, and A. Mills, “A Cascade of Linguistic CMAC Neural Networks for Decision Making,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2015.
  * [9] G. Horváth and T. Szabó, “Kernel CMAC with improved capability,” _IEEE Transactions on Systems. Man and Cybernetics: PartB_ , 37(1), pp. 124–38, 2007.
  * [10] K.-L. Huang, S.-C. Hsieh, and H.-C. Fu, “Cascade-CMAC neural network applications on the color scanner to printer calibration,” in _International Conference on Neural Networks_ , 1997.
  * [11] S. H. Lane, D. A. Handelman, and J. J. Gelfand, “Theory and development of higher-order CMAC neural networks,” _IEEE Control Systems_ , April, pp. 23–30, 1992.
  * [12] Y.-Y. Li, C.-C. Tsai, F.-C. Tai and H.-S. Yap, “Adaptive steering control using fuzzy CMAC for electric seatless unicycles,” _IEEE International Conference on Control & Automation_, pp. 556–561, 2014.
  * [13] C. C. Lin and F. C. Chen, “On a new CMAC control scheme, and its comparisons with the PID controllers,” _Proceedings of the American Control Conference_ , pp. 769–774, 2001.
  * [14] C.-M. Lin and Y.-F. Peng, “Adaptive CMAC-based supervisory control for uncertain nonlinear systems,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B_ , 34(2), pp. 1248–60, 2004.
  * [15] C.-M. Lin and H.-Y. Li, “Self-organizing adaptive wavelet CMAC backstepping control system design for nonlinear chaotic systems,” _Nonlinear Analysis: Real World Applications_ , 14(1), pp. 206–223, 2013.
  * [16] H.-C. Lu, M.-F. Yeh, and J.-C. Chang, “CMAC Study with Adaptive Quantization,” _IEEE Intl. Conf. on Systems, Man, and Cybernetics_ , Taipei, pp. 2596–2601, 2006.
  * [17] C. J. B. Macnab, “Using RBFs in a CMAC to prevent parameter drift in adaptive control,” _Neurocomputing_ , pp. 45–52, 2016.
  * [18] M. D. Mauk and N. H. Donegan, “A Model of Pavlovian Eyelid Conditioning Based on The Synaptic Organization of Cerebellum,” _Learn. Mem._ , 3, pp. 130–-158, 1997.
  * [19] A. Menozzi and M.-Y. Chow, “On the training of a multi-resolution CMAC neural network,” in _Proceedings of the IEEE International Symposium on Industrial Electronics_ , 1997.
  * [20] K. Mohajeri, G. Pishehvar, and M. Seifi, “CMAC neural networks structures,” in _IEEE International Symposium on Computational Intelligence in Robotics and Automation_ , 2009.
  * [21] K. Mohajeri, M. Zakizadeh, B. Moaveni, and M. Teshnehlab, “Fuzzy CMAC structures,” in _IEEE International Conference on Fuzzy Systems_ , 2009.
  * [22] Y.-F. Peng, R.-J. Wai and C.-M. Lin, “Adaptive CMAC model reference control system for linear piezoelectric ceramic motor,” in _IEEE International Symposium on Computational Intelligence in Robotics and Automation_ , 2003.
  * [23] F. Rosenblatt, “Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms,” _Spartan Books_ , Washington DC, 1961.
  * [24] D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning Internal Representations by Error Propagation,” _Nature_ , 323(9), 1986.
  * [25] R. L. Smith, “Intelligent Motion Control with an Artificial Cerebellum,” _PhD Thesis of The University of Auckland, New Zealand_ , Chapter 3, 1998.
  * [26] S.-F. Su, T. Tao, and T.-H. Hung, “Credit assigned CMAC and its application to online learning robust controllers,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 33(2), 2003.
  * [27] R. S. Sutton, “Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding,” _Advances in Neural Information Processing Systems_ , pp. 1038–1044, MIT Press, 1996.
  * [28] S. D. Teddy, E. M.-K. Lai, and C. Quek, “Hierarchically Clustered Adaptive Quantization CMAC and Its Learning Convergence,” _IEEE TRANSACTIONS ON NEURAL NETWORKS_ , 18(6), 2007.
  * [29] S. D. Teddy, C. Quek, and E. M.-K. Lai, “A cerebellar associative memory approach to option pricing and arbitrage trading,” _Neurocomputing_ , 19(4), 2008.
  * [30] S. D. Teddy, C. Quek, and E. M.-K. Lai, “PSECMAC: A Novel Self-Organizing Multiresolution Associative Memory Architecture,” _IEEE Trans. Neural Networks_ , 19(4), pp. 689–712, 2008.
  * [31] S. D. Teddy and S. K. Ng, “Forecasting ATM cash demands using a local learning model of cerebellar associative memory network,” _International Journal of Forecasting_ , 27(3), pp. 760–776, 2011.
  * [32] C.-K. Tham, “A hierarchical CMAC architecture for context dependent function approximation,” in _IEEE International Conference on Neural Networks_ , 1996.
  * [33] K. Tian, B. Guo, G. Liu, I. Mitchell, D. Cheng, and W. Zhao, “KCMAC-BYY: Kernel CMAC using Bayesian Ying–Yang learning,” _Neurocomputing_ , 101, pp. 24–-31, 2013.
  * [34] H. Voicu, “The Cerebellum: An Incomplete Multilayer Perceptron?,” _Neurocomputing_ , 72, pp. 592–-599, 2008.
  * [35] Z.-Q. Wang, J. L. Shiano, and M. Ginsberg, “Hash-coding in CMAC Neural Networks,” in _IEEE International Conference on Neural Networks_ , Washington, pp. 1698–-1703, 1996.
  * [36] S. Whiteson, M. E. Taylor, and P. Stone “Adaptive Tile Coding for Value Function Approximation,” _AI Technical Report AI-TR-07-339_ , University of Texas at Austin, 2007.
  * [37] Y.-F. , “CMAC Learning is Governed by a Single Parameter,” in _IEEE International Conference on Neural Networks_ , San Francisco, pp. 1439–-43, 1993.
  * [38] F. Z. Xing, E. Cambria and X. Zou, “Predicting Evolving Chaotic Time Series with Fuzzy Neural Networks,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2017.
  * [39] W. J. Zhou, D. L. Maskell and C. Quek, “FIE-FCMAC: A novel fuzzy cerebellum model articulation controller (FCMAC) using fuzzy interpolation and extrapolation technique,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2015.


# Incremental Learning with Concept Drift Detection and Prototype-based
Embeddings for Graph Stream Classification ††thanks: This paper was supported
by the European Research Council (ERC) under grant agreement No 951424 (Water-
Futures), the European Union’s Horizon 2020 research and innovation programme
under grant agreement No 739551 (KIOS CoE), the Republic of Cyprus through the
Deputy Ministry of Research, Innovation and Digital Policy, and the Cyprus
Academy of Sciences, Letters and Arts.

Kleanthis Malialisa, Jin Lia, b, Christos G. Panayiotoua, b and Marios M.
Polycarpoua, b aKIOS Research and Innovation Center of Excellence
bDepartment of Electrical and Computer Engineering
University of Cyprus, Nicosia, Cyprus
Email: {malialis.kleanthis, li.jin, christosp<EMAIL_ADDRESS>
ORCID: {0000-0003-3432-7434, 0000-0002-3534-524X, 0000-0002-6476-9025,
0000-0001-6495-9171}

###### Abstract

Data stream mining aims at extracting meaningful knowledge from continually
evolving data streams, addressing the challenges posed by nonstationary
environments, particularly, concept drift which refers to a change in the
underlying data distribution over time. Graph structures offer a powerful
modelling tool to represent complex systems, such as, critical infrastructure
systems and social networks. Learning from graph streams becomes a necessity
to understand the dynamics of graph structures and to facilitate informed
decision-making. This work introduces a novel method for graph stream
classification which operates under the general setting where a data
generating process produces graphs with varying nodes and edges over time. The
method uses incremental learning for continual model adaptation, selecting
representative graphs (prototypes) for each class, and creating graph
embeddings. Additionally, it incorporates a loss-based concept drift detection
mechanism to recalculate graph prototypes when drift is detected.

###### Index Terms:

graph streams, concept drift, incremental learning, graph prototypes,
nonstationary environments.

##  I Introduction

The explosive growth of data that we currently encouter has rendered
traditional data analysis methods insufficient in addressing the velocity,
volume, and variety of data generated. Data stream mining is dedicated to
extracting insights and meaningful knowledge from high-speed, continuously
evolving data streams. These time-varying and non-stationary environments pose
significant challenges as the underlying data distribution evolves over time,
which is referred to as concept drift [1, 2, 3].

Concept drift can manifest itself in various forms; for example, in critical
infrastructure systems [4] (such as, water networks, power and energy systems,
transportation networks, and telecommunication networks) drift may be the
result of seasonality or periodicity effects (e.g., demands in water
networks), software or hardware faults (e.g., sensor or actuator faults), and
changes in user behaviour. Therefore, this requires new learning algorithms
which are able to learn as data are observed one-by-one, and to continually
adapt in order to maintain their effectiveness under drifting dynamics.

While data stream mining focuses on the arising challenges by dynamic data
streams, the emergence of interconnected and complex systems requires a
further evolution in our data analysis methods. For example, in the area of
critical infrastructure systems [4], as the demand for their services is
growing rapidly, these systems become larger, more complex and have evolved
over time to become more heterogeneous and distributed. This has created
interdependencies between them, with fault effects propagating to
interdependent infrastructures. Other real-world examples include recommender
systems in e-commerce, molecular graphs for drug discovery in chemistry,
citation networks in academia, and social networks [5].

The intricate relationships and dependencies inherent in many real-world
systems, are best modelled through graph structures, which encapsulate
entities as nodes and relationships as edges [5]. Graph stream mining extends
the principles of data stream mining to dynamic graph structures, and aims at
discovering insights and unraveling hidden patterns within evolving graph
structures. This becomes a necessity for understanding the dynamics of graph
structures and facilitating informed decision-making.

The contributions of this work are as follows. We consider the general setting
where a data generating process produces a graph at each time of a variable
number of nodes and edges, and propose a new method which uses incremental
learning to continually update a model to perform graph classification. To
achieve this, the method selects representative graphs per class, referred to
as prototypes, which are then used to create graph embeddings; i.e., it embeds
graphs into vectors. Furthermore, we complement incremental learning with a
loss-based concept drift detection mechanism which re-calculates the graph
prototypes when drift is detected.

The rest of the paper is structured as follows. Section II provides the
relevant definitions and formulates the problem of graph stream
classification. Related work is discussed in Section III. The proposed method
is presented in Section IV. Section V describes the experimental setup, while
Section VI discusses the experiments results. Section VII concludes the paper
and provides directions for future work.

##  II Definitions and Problem Formulation

A graph $g$ is defined as $g=(V,E)$, where $V$ is the set of vertices or
nodes, and $E$ is the set of edges [5]. Let $v_{i}\in V$ be a node, and
$e_{i,j}=(v_{i},v_{j})\in E,i\neq j$ be an edge pointing from $v_{i}$ and
$v_{j}$. Let $A\in\mathbb{R}^{N\times N}$ denote the adjacency matrix with
$A_{i,j}=1$ if $e_{i,j}\in E$ and $A_{i,j}=0$ if $e_{i,j}\notin E$. A graph
can be directed where all edges are directed from one node to another, or
undirected where any pair of connected nodes have inverse directions, i.e.,
$A=A^{\intercal}$.

An attributed graph [5] refers to a graph which may have node and edge
attributes or features. Let the number of nodes and edges in a graph be
$|V|=N$ and $|E|=M$ respectively. Let $X_{V}\in\mathbb{R}^{N\times d}$ be the
node feature matrix, with $x_{v}\in\mathbb{R}^{d}$ being a $d$-dimensional
feature vector of node $v\in V$. Let $X_{E}\in\mathbb{R}^{M\times c}$ be the
edge feature matrix, with $x_{e_{i,j}}\in\mathbb{R}^{c}$ being a
$c$-dimensional feature vector of edge $(v_{i},v_{j})\in E$. Additionally, a
graph may also have global features referring to the overall graph. Attributed
graphs enable the representation of richer information beyond structural
relationships, thus facilitating the modeling of complex systems.

Graph stream classification addresses the challenges posed by continuous and
dynamic sequences of attributed graphs. We consider a data generating process
that provides a graph at each time step $t$ as follows:
$D=\\{(g^{t},y^{t})\\}^{\infty}_{t=1}$, where the data are typically sampled
from a potentially infinite sequence. The examples are drawn from an unknown
probability distribution $p^{t}(g,y)$, where $g^{t}\in G$ is an attributed
graph in the graph space $G$, and $y^{t}\in\\{1,...,K\\}$ denotes the graph’s
class label (ground truth) in the target space $Y\subset\mathbb{Z}^{+}$, and
$K\geq 2$ is the number of classes. Importantly, in this general framework,
graphs can have a variable number of nodes and edges, and can be directed or
undirected, thus covering a vast number of real-world applications.

A graph classifier observes a new graph $g^{t}$ at time $t$ and makes a
prediction $\hat{y}^{t}$ based on a concept $h:G\rightarrow Y$. The classifier
receives the true label $y^{t}$, its performance is evaluated using a loss
function and is then trained based on the loss incurred. This process is
repeated at each step. The gradual adaptation of the classifier without
complete re-training $h^{t}=h^{t-1}.train(\cdot)$ is termed incremental
learning [6].

Data non-stationarity [1] is a significant challenge in some streaming
applications which is, typically, caused by concept drift [2, 3], which
represents a change in the joint probability distribution, defined as:
$p^{t_{i}}(g,y)\neq p^{t_{j}}(g,y),i\neq j$.

##  III Related Work

###  III-A Concept drift adaptation

Typically, methods to address drift are grouped into active and passive [1].
Active methods employ explicit mechanisms to detect drift, such as statistical
tests to detect changes in a data distribution (e.g., MannWhitney U test [7]),
or threshold-based methods which monitor a performance metric (e.g., [8]).
Typically, the model is completely retrained once drift is detected.

Alternatively, implicit methods exist which are referred to as passive
methods, where they use incremental training to learn the drift [9] to
continually update the classifier. Typically, they are memory-based, i.e.,
they have a memory (e.g., sliding windows) to store recent examples, which the
model is incrementally trained on (e.g., [10]). Ensemble-based methods are
also applied where a collection of classifiers exists, and members of the
ensemble are added or discarded based on their performance (e.g., [11]).

Other methods include hybrid methods which attempt to combine the strengths of
both worlds (e.g., [12]), while an alternative approach is called drift
unlearning [13] which attempts to remove the effects / impact of drift on the
data, and to revert the data distribution to the original (pre-drift).

###  III-B Graph stream classification

Many methods have been proposed for traditional graph classification111Other
graph tasks exist, such as node classification and link prediction, which are
outside the scope of this work. [5, 14, 15], however, existing work on graph
stream classification is limited. The survey in [16] provides a comprehensive
overview of anomaly detection in dynamic networks. In [17], change point
detection has been examined in the context of correlation networks; a
correlation network is a special type of network obtained by defining the
edges based on some measure of correlation between each pair of nodes. The
work in [18] formalises the network change point detection problem in an
online probabilistic learning framework, while the work in [19] focuses on
network surveillance and proposes a block model for detecting a structural
change.

Figure 1: Overview of the proposed method.

The seminal paper [20] constitutes the first work that uses graph embeddings
for anomaly detection; it embeds each graph in the stream into a vector domain
based on graph prototypes, thus enabling the use of a conventional change
detection method to a more manageable setting. This paper [21] adopts the idea
of using graph embeddings, but instead, it learns the embeddings by training
an autoencoder to represent graphs on constant-curvature Riemannian manifolds.

In our work, we adopt the use of prototype-based graph embeddings, but
contrary to [20, 21]: (a) We depart from anomaly detection (normality vs
abnormality) and propose a method for multi-class graph stream classification;
(b) The proposed drift detection method is loss-based, in contrast to previous
works where drift and anomaly are considered the same; (c) Our proposed method
is hybrid as it proposes a synergy between incremental learning and drift
detection.

##  IV Method for Graph Stream Classification

The overview of the proposed method is shown in Fig. 1. A new graph $g^{t}$ is
observed at time $t$, while a graph memory $q$ is maintained to store recent
graphs (this is displayed in blue colour). The method also considers class
prototypes $p$, i.e., representative graphs per class. Using the prototypes,
the embedding $e_{g^{t}}$ of graph $g^{t}$ is calculated which is stored in a
graph embeddings memory $e$ (yellow). Given the embedding, a classifier
outputs a prediction $\hat{y}^{t}$ (purple). A concept drift detector is in
place which updates the graph prototypes and embeddings if drift is detected
(grey). The true label $y^{t}$ is provided (green, and the pairs
$(g^{t},y^{t})$ and $(e_{g^{t}},y^{t})$ are appended to the graph memory and
embeddings memory respectively. Lastly, incremental training is performed to
update the classifier (orange). The pseudocode of the proposed method is
provided in Alg. 1. A detailed description of each component in Fig. 1 and
each line in Alg. 1 is presented below.

###  IV-A Incremental learning

Graph Memory. The proposed method has multiple queues, one for each class,
which is populated by arriving graphs as follows:

$q=\\{q^{c}\\}^{K}_{c=1},$ (1)

where $K\geq 2$ is the number of classes, and $q^{c}$ is the queue
corresponding to class $c$. Each queue is defined as follows:

$q^{c}=\\{g_{i}\\}^{L}_{i=1},$ (2)

where $L$ is the size of each queue, and for any two $g_{i},x_{j}\in q^{c}$
such that $j>i$, $g_{j}$ has been observed more recently in time. This is
shown on the left-hand side of Fig. 2.

Graph prototypes. For each class $c$ we calculate its prototype set $p^{c}$,
that is, its representative graphs:

$p^{c}=\\{p_{i}\\}^{R}_{i=1},$ (3)

where $p_{i}\in q^{c}$ and $1\leq R<L$ is the number of prototypes or
representative graphs per class. The whole prototype set is then defined as
follows:

$p=\\{p^{c}\\}^{K}_{c=1},$ (4)

This is shown on the right-hand side of Fig. 2. To obtain the class prototypes
$p^{c}$ we use the Centers algorithm [22], which assumes that the median graph
in $q^{c}$ is the central graph. This is defined as the graph whose sum of
distances to all other graphs is minimal:

$p^{c}=med(q^{c})=\operatorname*{argmin}_{g_{1}\in q^{c}}\sum_{g_{2}\in
q^{c}}\delta(g_{1},g_{2}),$ (5)

where $\delta(\cdot,\cdot)$ is a distance metric between two graphs. To select
$R$ prototypes per class we repeat the procedure but each time we exclude the
already selected median graphs.

Graph embeddings. We adopt the embedding method from [22] which was also
adopted in [20] for anomaly detection in graph streams. Given a graph $g\in G$
and all prototypes $p$, we calculate its embedding
$e_{g}\in\mathbb{R}^{R\times K}$ as follows:

$e_{g}=\\{\delta(g,p_{i})\\}_{i=1}^{R\times K},$ (6)

where $p_{i}\in p$. Using this process, we convert all the graphs in the
memory to their embedding form, analogous to Eqs. (1) and (2), as follows:

$\displaystyle e$ $\displaystyle=\\{e^{c}\\}^{K}_{c=1}$ (7) $\displaystyle
e^{c}$ $\displaystyle=\\{e_{g_{i}}\\}^{L}_{i=1}$

Figure 2: Class prototypes from graph memory.

Incremental training. A classifier $h$ observes a graph embedding
$e_{g}\in\mathbb{R}^{R\times K}$ and makes a prediction $\hat{y}\in
Y,Y\in\\{1,2,...,K\\}$, that is, $h:\mathbb{R}^{R\times K}\rightarrow Y$. The
training set consists of the embeddings $e$ of the graphs in $q$. The cost
function is defined as follows:

$C=\frac{1}{L\times K}\sum_{i=1}^{L\times K}l(y_{i},h(e_{g_{i}}))$ (8)

where $h(e_{g_{i}})$ is the predicted class of graph $g_{i}$ with an embedding
$e_{g_{i}}$, and $l(\cdot,\cdot)$ is a loss function, such as the categorical
cross-entropy. At each time step $t$, the classifier is incrementally updated
based on the cost incurred, that is:

$h^{t}=h^{t-1}.train(\cdot)$ (9)

###  IV-B Concept drift detection

Error modelling. The prediction or 0/1 score at time $t$ is defined as
$\mathbb{I}_{y^{t}==\hat{y}^{t}}\in\\{0,1\\}$, where $\mathbb{I}$ is the
identify function, $y^{t}$ is the ground truth and $\hat{y}^{t}$ is the
prediction. We maintain two queues, a reference queue $q_{ref}$ and a moving
queue $q_{mov}$, where $W=|q_{ref}|=|q_{mov}|$. The moving queue stores the
most recent prediction scores, which will be compared to older scores stored
in the reference queue. The prediction scores are modeled as Binomial
distributions [8]. For example, the mean and standard deviation for the
reference queue are defined as:

$\displaystyle\mu_{ref}=p_{ref}$ (10)
$\displaystyle\sigma_{ref}=\sqrt{\frac{p_{ref}(1-p_{ref})}{W}},$

where $p_{ref}=\frac{1}{|q_{ref}|}\sum_{s\in q_{ref}}s$ is the estimated
parameter of the Binomial distribution, $s$ being each 0/1 prediction score.
The mean $\mu_{mov}$ and standard deviation $\sigma_{mov}$ for $q_{mov}$ are
calculated in a similar fashion.

Algorithm 1 Proposed method for graph stream classification

1:$L$ (Memory size per class); $R$ (Number of prototypes per class); $W$
(Window size for drift detection); $\beta$ (Threshold for drift detection).

2:for each time step $t$ do

3: observe graph $g^{t}$

4: get its embedding $e_{g^{t}}$ $\triangleright$ Eq. (6)

5: predict graph class $\hat{y}^{t}=h^{t}(e_{g^{t}})$

6: get ground truth $y^{t}$

7: append 0/1 prediction score to $q_{mov}$

8: check for drift between $q_{mov}$ and $q_{ref}$ $\triangleright$ Eq. (12)

9: if drift detected then

10: re-calculate graph prototypes $\triangleright$ Eq. (4)

11: update embeddings in graph memory $\triangleright$ Eq. (7)

12: increment. train model $h^{t}=h^{t-1}.train(\cdot)$ $\triangleright$ Eq.
(8)

Distribution change. To detect a change in the distribution of prediction
scores and, specifically, a decline in the model’s performance, we calculate
the following threshold:

$\displaystyle\theta_{ref}$ $\displaystyle=\mu_{ref}-\beta\sigma_{ref},$ (11)

where $\beta>0$ is a sensitivity parameter which is task-dependant. A concept
drift alarm will be triggered when the average of recent prediciton scores
fall below the above threshold, i.e., when the following condition is
satisfied:

$\mu_{mov}\leq\theta_{ref}$ (12)

Re-calculation of graph prototypes. When concept drift is detected the graph
prototypes $p$ are re-calculated, and all the graph embeddings $e$ in the
memory are replaced.

##  V Experimental Setup

This section describes the datasets used in our experimental study, the
compared methods, and the evaluation methodology.

###  V-A Datasets

Letter [23]. The dataset considers the three capital letters “A”, “I” and “Z”,
which are converted into graphs by representing lines by undirected edges and
ending points of lines by nodes. The graphs are uniformly distributed over the
three classes. Each node is labelled with a two-dimensional attribute giving
its position relative to a reference coordinate system. To test the compared
methods under conditions of concept drift, distortions of different levels are
applied on the graphs as shown in Fig. 3. We consider two variants of the
dataset, in which we vary the frequency and severity of concept drift:

  * •

Letter_high. There are 300 arriving graphs without any distortions, followed
by 450 with high distortion level.

  * •

Letter_med_high. There are 300 arriving graphs without any distortions,
followed by 450 with medium distortion level, and 450 with high distortion
level.

Figure 3: Distortions levels of character “A” in the Letter dataset. Figure 4:
Distortion levels of GREC images.

(a) left

(b) arch

Figure 5: Examples of the two classes in the Fingerprint dataset.

GREC [23]. The GREC dataset comprises graphs representing symbols found in
architectural and electronic drawings, with images at five distortion levels.
In Fig. 4, each distortion level showcases a drawing example. Distortion
levels determine the application of morphological operations, such as erosion
or dilation. The resulting images are thinned to one-pixel-wide lines, from
which graphs are extracted by tracing lines and detecting intersections and
corners. Three classes are considered in this study. The graphs are uniformly
distributed over the three classes. Nodes represent endpoints, corners,
intersections, and circles, labeled with two-dimensional attributes indicating
their positions. Undirected edges connect nodes, labeled as either lines or
arcs.

Fingerprint [23]. This dataset comprises two distinct fingerprint types,
namely ’arch’ and ’left’, as shown in Fig. 5, which are transformed into
graphs by nodes and edges. Each node is assigned a two-dimensional attribute
representing its position, while the edges are characterised by an angle
indicating their orientation relative to the horizontal direction. Derived
from the NIST-4 reference database of fingerprints, this dataset features
graphs that are evenly distributed across the specified classes.

For our implementation we have used NetworkX [24], a Python package for the
creation, manipulation, and study of graphs. For the graph similarity /
distance metric, we have used the Graph Edit Distance [25], which is defined
as the minimum cost of a series of edit operations (e.g., insert a link)
required to transform one graph into another.

###  V-B Compared methods

TABLE I: Hyper-parameter values for each dataset | Letter | GREC | Fingerprint
---|---|---|---
Learning rate | 0.001 | 0.001 | 0.01
Hidden layers | [128, 64] | [128, 64] | [32]
Mini-batch size | 128 | 128 | 128
L2 regularisation | 0.0001 | 0.0001 | 0.0
Weight initialiser | He Normal [26]
Optimiser | Adam [27]
Hidden activation | Leaky ReLU [28]
Num. epochs | 1 | 10 | 1
Output activation | Softmax
Loss function | Categorical cross-entropy

Proposed method. This has been described in Section IV and its pseudocode is
shown in Alg. 1.

Feature-based method. We implement the method from [20], which uses two
features to represent graphs. The first feature of graph $g$ is the density of
edges defined as: $\phi_{1}(g)=\frac{M}{N(N-1)}$, where $N=|V|$ and $M=|E|$
are the number of nodes and edges respectively. The second feature is the
spectral gap of graph $g$ defined as:
$\phi_{2}(g)=|\lambda_{1}|-|\lambda_{2}|$, where $\lambda_{1}$ and
$\lambda_{2}$ are the largest and second-largest eigenvalues of the graph’s
Laplacian matrix. The reasoning behind this particular choice is that both
features are suitable for describing graphs with a variable number of nodes
and edges.

For fairness, the graph memory from the proposed method is also used in the
feature-based method to store the features (instead of the embeddings).
Additionally, for both methods the memory is assumed to be initially full by
limited historical data (e.g., $L=10$ graphs per class). No pre-training takes
place as learning starts at time $t=1$.

Both methods use the same classifier, a standard fully-connected neural
network whose hyper-parameters for each dataset are shown in Table I. This is
implemented in Keras [29] with the PyTorch backend [30].

###  V-C Evaluation methodology

We use the popular performance metric geometric mean [31], which is suitable
for imbalanced datasets, and is defined as follows:

$G\text{-}mean=\displaystyle\sqrt[K]{\prod_{c=1}^{K}r_{c}},$ (13)

where $r_{c}$ is the recall of class $c$ and $K$ is the number of classes. It
has the desirable property that it is high when all recalls are high and when
their difference is small [32].

Additionally, we use the widely adopted prequential evaluation with fading
factors method [33], which has two major advantages. First, it has been proven
to converge to the Bayes error when learning in stationary data. Second, it
does not require a holdout set and the predictive algorithm is always tested
on unseen data. The fading factor is set to 0.99. In all simulations, we plot
the prequential G-mean in every step averaged over 10 repetitions, including
the error bars displaying the standard error around the mean.

##  VI Experimental Results

Role of the graph memory. In this study, we will inspect the role of the graph
memory in the proposed method. The result for Letter (without drift) is shown
in Fig. 6, where using the graph memory significantly outperforms the proposed
method without memory. The main benefit of the graph memory concerns the
learning speed as towards the end, they end up with a small performance
different. Another major advantage of using the memory is that it would allow
us to re-calculate the class prototypes when concept drift is detected. For a
fair assessment, we have chosen the Letter variant without drift in this
experiment. From now on, the graph memory will be used.

Figure 6: Performance of the proposed method with and without graph memory.

(a) Letter_high

(b) Letter_med_high

(c) GREC

(d) Fingerprint

Figure 7: The performance of the proposed method with different number of
prototypes ($R=1,3$) per class.

Number of class prototypes. In this study, we examine the impact of the number
of class prototypes on the model’s performance. The memory size per class for
all datasets is $L=10$. As depicted in Fig. 7a and Fig. 7b, it is evident that
the model’s performance is superior with three prototypes compared to using
only one when there is no concept drift or when drift is mild. After severe
concept drift, the performance deteriorates indicating that old prototypes may
no longer be accurate class representatives, therefore, a smaller number of
them is preferred. In Fig. 7c, it is evident that the model’s performance
significantly improves when employing three prototypes as opposed to just one.
In Fig. 7d, although the model’s performance with three prototypes initially
lags behind that of one prototype, it steadily improves over time and
ultimately slightly surpasses the latter. These findings collectively affirm
that in scenarios with limited or without drift, the model consistently
exhibits superior performance when using three prototypes as opposed to
relying on only one.

(a) Letter_high

(b) Letter_med_high

Figure 8: The performance of the proposed method with and without concept
drift detection.

Concept drift detection. Here, we examine the impact of the drift detector on
the model’s performance. The experiment is carried out with a memory size of
$L=10$, $R=3$ prototypes per class, and $\beta=4.5$ for the drift detection
sensitivity parameter. As depicted in Fig. 8, the model’s performance is
similar in both cases regardless of the presence of the drift detector.
However, following a drift occurrence, there is a noticeable improvement in
performance for the model equipped with the drift detector. This provides
empirical evidence supporting the assertion that a drift detection mechanism
can effectively enhance overall model performance. This is attributed to the
fact that the graph prototypes are re-calculated, thus replacing the old
“obsolete” ones.

Comparative study. In this section, we present a comparative analysis of our
proposed method (which uses graph embeddings) against the feature-based
method. The outcomes are shown in Fig. 9. A significant performance difference
between the two methods is evident across all datasets. Our proposed method
consistently surpasses the feature-based, both prior to and following the
occurrence of drift in the Letter dataset. Also, our method performs better in
the GREC and Fingerprint datasets.

(a) Letter_high

(b) Letter_med_high

(c) GREC

(d) Fingerprint

Figure 9: Comparison between the proposed method (using embeddings) and the
feature-based method.

##  VII Conclusion and Future Work

This work introduces a novel method for graph stream classification which
operates under the general setting where graphs have a variable number of
nodes and edges. It proposes the use of incremental learning for continual
model adaptation using class prototype-based graph embeddings, in conjunction
with a loss-based concept drift detection mechanism. Directions for future
work are provided below.

Learning graph embeddings. In this work, the graph embeddings were calculated
based on graph prototypes. Future work will examine methods to learn the
embeddings (e.g., [21]), which we will allow us to apply the proposed method
to large-scale graph stream problems.

Limited ground truth availability. In this work, we have assumed the
availability of the graph class label after each prediction step. Future work
will consider other learning paradigms, such as unsupervised [7], semi-
supervised [34] and active [35] learning, and methods, such as few-shot
learning [36] and data augmentation [37]; all of which have been shown to be
effective in traditional data stream mining.

## References

  * [1] G. Ditzler, M. Roveri, C. Alippi, and R. Polikar, “Learning in nonstationary environments: A survey,” _IEEE Computational Intelligence Magazine_ , vol. 10, no. 4, pp. 12–25, 2015.
  * [2] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, and A. Bouchachia, “A survey on concept drift adaptation,” _ACM Computing Surveys_ , vol. 46, no. 4, p. 44, 2014.
  * [3] J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, and G. Zhang, “Learning under concept drift: A review,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 31, no. 12, pp. 2346–2363, 2018.
  * [4] E. Kyriakides and M. Polycarpou, _Intelligent monitoring, control, and security of critical infrastructure systems_. Springer, 2014, vol. 565.
  * [5] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [6] V. Losing, B. Hammer, and H. Wersing, “Incremental on-line learning: A review and comparison of state of the art algorithms,” _Neurocomputing_ , vol. 275, pp. 1261–1274, 2018.
  * [7] J. Li, K. Malialis, and M. M. Polycarpou, “Autoencoder-based anomaly detection in streaming data with incremental learning and concept drift adaptation,” in _2023 International Joint Conference on Neural Networks (IJCNN)_ , 2023\.
  * [8] J. Gama, P. Medas, G. Castillo, and P. Rodrigues, “Learning with drift detection,” in _Advances in Artificial Intelligence–SBIA 2004: 17th Brazilian Symposium on Artificial Intelligence, Sao Luis, Maranhao, Brazil, September 29-Ocotber 1, 2004. Proceedings 17_ , 2004, pp. 286–295.
  * [9] R. Elwell and R. Polikar, “Incremental learning of concept drift in nonstationary environments,” _IEEE Transactions on Neural Networks_ , vol. 22, no. 10, pp. 1517–1531, 2011.
  * [10] K. Malialis, C. G. Panayiotou, and M. M. Polycarpou, “Online learning with adaptive rebalancing in nonstationary environments,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 10, pp. 4445–4459, 2020\.
  * [11] B. Krawczyk, L. L. Minku, J. Gama, J. Stefanowski, and M. Woźniak, “Ensemble learning for data stream analysis: A survey,” _Information Fusion_ , vol. 37, pp. 132–156, 2017.
  * [12] K. Malialis, M. Roveri, C. Alippi, C. G. Panayiotou, and M. M. Polycarpou, “A hybrid active-passive approach to imbalanced nonstationary data stream classification,” in _2022 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2022, pp. 1021–1027.
  * [13] A. Artelt, K. Malialis, C. Panayiotou, M. Polycarpou, and B. Hammer, “Unsupervised unlearning of concept drift with autoencoders,” in _2023 IEEE Symposium Series on Computational Intelligence (SSCI)_ , 2023.
  * [14] Z. Zhang, P. Cui, and W. Zhu, “Deep learning on graphs: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 1, pp. 249–270, 2020.
  * [15] M. Jin, H. Y. Koh, Q. Wen, D. Zambon, C. Alippi, G. I. Webb, I. King, and S. Pan, “A survey on graph neural networks for time series: Forecasting, classification, imputation, and anomaly detection,” _arXiv preprint arXiv:2307.03759_ , 2023.
  * [16] S. Ranshous, S. Shen, D. Koutra, S. Harenberg, C. Faloutsos, and N. F. Samatova, “Anomaly detection in dynamic networks: a survey,” _Wiley Interdisciplinary Reviews: Computational Statistics_ , vol. 7, no. 3, pp. 223–247, 2015.
  * [17] I. Barnett and J.-P. Onnela, “Change point detection in correlation networks,” _Scientific reports_ , vol. 6, no. 1, p. 18893, 2016.
  * [18] L. Peel and A. Clauset, “Detecting change points in the large-scale structure of evolving networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 29, no. 1, 2015.
  * [19] J. D. Wilson, N. T. Stevens, and W. H. Woodall, “Modeling and detecting change in temporal networks via the degree corrected stochastic block model,” _Quality and Reliability Engineering International_ , vol. 35, no. 5, pp. 1363–1378, 2019.
  * [20] D. Zambon, C. Alippi, and L. Livi, “Concept drift and anomaly detection in graph streams,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 11, pp. 5592–5605, 2018.
  * [21] D. Grattarola, D. Zambon, L. Livi, and C. Alippi, “Change detection in graph streams by learning graph embeddings on constant-curvature manifolds,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 6, pp. 1856–1869, 2019.
  * [22] K. Riesen, M. Neuhaus, and H. Bunke, “Graph embedding in vector spaces by means of prototype selection,” in _Graph-Based Representations in Pattern Recognition: 6th IAPR-TC-15 International Workshop, GbRPR 2007, Alicante, Spain, June 11-13, 2007. Proceedings 6_. Springer, 2007, pp. 383–393.
  * [23] K. Riesen and H. Bunke, “Iam graph database repository for graph based pattern recognition and machine learning,” in _Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings_. Springer, 2008, pp. 287–297.
  * [24] A. Hagberg, P. Swart, and D. S Chult, “Exploring network structure, dynamics, and function using networkx,” Los Alamos National Lab.(LANL), Los Alamos, NM (United States), Tech. Rep., 2008.
  * [25] Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, and P. Martineau, “An exact graph edit distance algorithm for solving pattern recognition problems,” in _4th International Conference on Pattern Recognition Applications and Methods 2015_ , 2015.
  * [26] K. He, X. Zhang, S. Ren, and J. Sun, “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2015, pp. 1026–1034.
  * [27] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_ , 2015.
  * [28] A. L. Maas, A. Y. Hannun, and A. Y. Ng, “Rectifier nonlinearities improve neural network acoustic models,” in _Proceedings of the 30th International Conference on Machine Learning_ , 2013.
  * [29] F. Chollet _et al._ , “Keras,” https://keras.io, 2015.
  * [30] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [31] Y. Sun, M. S. Kamel, and Y. Wang, “Boosting for learning multiple classes with imbalanced class distribution,” in _Sixth International Conference on Data Mining (ICDM’06)_. IEEE, 2006, pp. 592–602.
  * [32] H. He and E. A. Garcia, “Learning from imbalanced data,” _IEEE Transactions on Knowledge and Data Engineering_ , no. 9, pp. 1263–1284, 2008.
  * [33] J. Gama, R. Sebastião, and P. P. Rodrigues, “On evaluating stream learning algorithms,” _Machine Learning_ , vol. 90, no. 3, pp. 317–346, 2013.
  * [34] S. Pan, X. Zhu, C. Zhang, and S. Y. Philip, “Graph stream classification using labeled and unlabeled graphs,” in _2013 IEEE 29th International Conference on Data Engineering (ICDE)_. IEEE, 2013, pp. 398–409.
  * [35] I. Žliobaitė, A. Bifet, B. Pfahringer, and G. Holmes, “Active learning with drifting streaming data,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 25, no. 1, pp. 27–39, 2013.
  * [36] K. Malialis, C. G. Panayiotou, and M. M. Polycarpou, “Nonstationary data stream classification with online active learning and siamese neural networks,” _Neurocomputing_ , vol. 512, pp. 235–252, 2022.
  * [37] K. Malialis, D. Papatheodoulou, S. Filippou, C. G. Panayiotou, and M. M. Polycarpou, “Data augmentation on-the-fly and active learning in data stream classification,” in _2022 IEEE Symposium Series on Computational Intelligence (SSCI)_. IEEE, 2022, pp. 1408–1414.