# Density Encoding Enables Resource-Efficient Randomly Connected Neural
Networks

Denis Kleyko, Mansour Kheffache, E. Paxon Frady, Urban Wiklund, and Evgeny
Osipov *D. Kleyko, M. Kheffache, and E. Osipov are with the Department of
Computer Science Electrical and Space Engineering, Luleå University of
Technology, Luleå, Sweden. E-mail:$\\{$denis.kleyko,
<EMAIL_ADDRESS><EMAIL_ADDRESS>Frady is with the
Helen Wills Neuroscience Institute at the University of California, Berkeley,
USA. E-mail<EMAIL_ADDRESS>Wiklund is with the Department of Radiation
Sciences, Biomedical Engineering, Umeå University, Umeå, Sweden. E-mail:
<EMAIL_ADDRESS>
###### Abstract

The deployment of machine learning algorithms on resource-constrained edge
devices is an important challenge from both theoretical and applied points of
view. In this article, we focus on resource-efficient randomly connected
neural networks known as Random Vector Functional Link (RVFL) networks since
their simple design and extremely fast training time make them very attractive
for solving many applied classification tasks. We propose to represent input
features via the density-based encoding known in the area of stochastic
computing and use the operations of binding and bundling from the area of
hyperdimensional computing for obtaining the activations of the hidden
neurons. Using a collection of $121$ real-world datasets from the UCI Machine
Learning Repository, we empirically show that the proposed approach
demonstrates higher average accuracy than the conventional RVFL. We also
demonstrate that it is possible to represent the readout matrix using only
integers in a limited range with minimal loss in the accuracy. In this case,
the proposed approach operates only on small n-bits integers, which results in
a computationally efficient architecture. Finally, through hardware FPGA
implementations, we show that such an approach consumes approximately eleven
times less energy than that of the conventional RVFL.

###### Index Terms:

random vector functional link networks, hyperdimensional computing, density-
based encoding

##  I Introduction

An ability to provide insights and predictive analytics in real-time is the
greatest demand from businesses and industries to data-driven technologies.
The vector of the current development targets enabling machine learning
applications on connected devices (edge computing) such as smartphones,
robots, vehicles, etc. The benefits of computing at the edge are tremendous:
higher reliability of solutions due to the decoupling from the network
connectivity and bandwidth availability; very low latency; higher security and
privacy as sensitive data is processed locally on a device.

Randomly connected neural networks in general and Random Vector Functional
Link (RVFL) [1, 2] in particular have become an increasingly popular topic of
modern theoretical and applied research. On the theoretical side, the main
result is that RFVLs provide universal approximation for continuous maps and
functional approximations that converge in Kullback-Leibler divergence, when
the target function is a probability density function [3]. When this is
combined with the simplicity of RVFL’s design and training process, it makes
them a very attractive alternative for solving practical machine learning
problems in edge computing.

This article presents an approach for an order of magnitude increase of the
resource-efficiency (memory footprint, computational complexity, and energy
savings) of RVFLs operations. The proposed approach combines techniques from
two fields of computer science: stochastic computing [4] and hyperdimensional
computing [5]. The fundamental idea is in the realization of activations of
the hidden layer with the computationally simple operations of
hyperdimensional computing and the usage of the density-based encoding of the
input features as in stochastic computing. Moreover, we enhance this approach
with the integer-only readout matrix. This combination allows us to use
integer arithmetics end-to-end. The key contributions of the article are as
follows:

  * •

Resource-efficient approach to RVFLs, which uses only integer operations;

  * •

The empirical evaluation on $121$ real-world classification datasets
demonstrate that the accuracy of the proposed approach is higher that of the
conventional RVFL;

  * •

FPGA implementation of the proposed approach is an order of magnitude more
energy-efficient and $2.5$ times faster than the conventional RVFL. 111 For a
network with: $16$ features, $4$ classes, and $512$ hidden neurons, which are
the median values for the considered $121$ datasets.

The article is structured as follows. The background of methods used for the
proposed approach is presented in Section II. The approach itself is described
in Section III. The performance evaluation follows in Section IV. Section V
covers related work. Section VI presents the concluding remarks.

##  II Background and methods

###  II-A Random Vector Functional Link

This subsection briefly describes the conventional RVFL. For the detailed
survey of RVFLs diligent readers are referred to [6]. Fig. 1 depicts the
architecture of the conventional RVFL, which includes three layers of neurons.
The input layer with $K$ neurons represents the current values of input
features denoted as $\textbf{x}\in[K\times 1]$. The output layer ($L$ neurons)
produces the prediction of the network (denoted as y) during the operating
phase. The layer in is middle is the hidden layer of the network, which
performs a nonlinear transformation of input features. The hidden layer
contains $N$ neurons and its state is denoted as h.

In general, the connectivity of an RVFL is described by two matrices and a
vector. A matrix $\textbf{W}^{\text{in}}\in[N\times K]$ describes connections
between the input layer neurons and the hidden layer neurons. This matrix
projects the given input features to the hidden layer. Each neuron in the
hidden layer has a parameter called a bias. Biases of the hidden layer are
stored in a vector and denoted as $\textbf{b}\in[N\times 1]$. The other matrix
of readout connections $\textbf{W}^{\text{out}}\in[L\times N]$ between the
hidden and the output layers transforms the current activations in the hidden
layer stored in h into the network’s output y.222Strictly speaking, in the
most general case, the readout matrix could also include connections between
the input layer and the output layer. However, in the scope of this study, we
only consider the case when the output layer predictions are obtained from the
activations of the hidden layer. The interested readers are referred to work
[7], which performed a comprehensive evaluation of different design choices
for the RVFL.

The main feature of the RVFL is that matrix $\textbf{W}^{\text{in}}$ and
vector b are randomly generated at the network initialization and stay fixed
during the network’s lifetime. There are no strict limitations for the
generation of $\textbf{W}^{\text{in}}$ and b. They are usually randomly drawn
from either normal or uniform distributions. Here, both
$\textbf{W}^{\text{in}}$ and b are generated from a uniform distribution.
Following [8], the range for $\textbf{W}^{\text{in}}$ is $[-1,1]$ while the
range for b is $[-0.1,0.1]$. Since $\textbf{W}^{\text{in}}$ and b are fixed
the process of training RVFL is focused on learning the values of the readout
matrix $\textbf{W}^{\text{out}}$. The main advantage of training only
$\textbf{W}^{\text{out}}$ is that the corresponding optimization problem is
strictly convex, thus, the solution could be found a single analytical step.

The activations of the network’s hidden layer h are described by the following
equation:

$\textbf{h}=g(\textbf{W}^{\text{in}}\textbf{x}+\textbf{b}),$ (1)

where $g(x)$ is a nonlinear activation function applied to each neuron. Here,
the sigmoid function $g(x)=\frac{1}{1+e^{-x}}$ is used. Thus, the activation
function restricts the range of possible activation values in the hidden layer
in the range $[0,1]$.

The predictions issued by the output layer are calculated as:

$\textbf{y}=\textbf{W}^{\text{out}}\textbf{h}.$ (2)

Figure 1: The architecture of the conventional Random Vector Functional Link.
In the presented example, the number of hidden neurons is set to $N=4$.

With respect to the training of RVFLs, the article focuses on classification
tasks333Though, the proposed approach is also applicable to regression
problems. One may, however, expect that the quality of predictions might be
more sensitive to the use of the density-based encoding. considering only
supervised-learning scenarios when the network is provided with the ground
truth classifications for each training example. The total size of the
training dataset is denoted as $M$. In this setting, the standard way of
acquiring weights of the trainable connections between the hidden and the
output layers in $\textbf{W}^{\text{out}}$ matrix is via solving the ridge
regression (also known as Tikhonov regularization) problem, which minimizes
the mean square error between predictions (2) and the ground truth. In
particular, the activations of the hidden layer $\textbf{h}^{T}$ for each
training example are collected together in matrix $\textbf{H}\in[M\times N]$.
Matrix $\textbf{Y}\in[M\times L]$ stores the corresponding ground truth
classifications using ohe-hot encodings. Given H and Y,
$\textbf{W}^{\text{out}}$ is calculated as follows:

$\textbf{W}^{\text{out}}=(\textbf{H}^{T}\textbf{H}+\lambda\textbf{I})^{-1}\textbf{H}^{T}\textbf{Y},$
(3)

where I denotes an identity matrix of the suitable dimensionality
($\textbf{I}\in[N\times N]$); $\lambda$ is a hyperparameter (scalar)
determining the weight of the regularization part.444Note that (3) is
computationally simpler compared to, e.g., the backprop algorithm and it is
implementable efficiently on CPUs as well as on GPUs.

###  II-B Density-based encoding of scalars

The idea of representing scalars as vectors is not new. It has been
independently proposed in several areas. The area of stochastic computing [4]
is probably the most notable example since the whole idea of the stochastic
computing is that it is possible to implement arithmetics on scalars using
boolean operations on vectors (in general, streams) of bits. The rate coding
model of neuronal firing used, e.g., in spiking neural networks is another
notable example. The stochastic computing operates with scalars between $0$
and $1$, which are represented as random bit vectors where the scalar being
encoded determines the probability of generating ones. Thus, the density of
ones in the obtained bit vector encodes the scalar, hence such a
representation method is called the density-based encoding. Generating random
streams is important because the independence of two vectors is a prerequisite
for using boolean operations to implement the arithmetics on them (e.g., AND
for multiplication). Since in the scope of this study we do not have to
perform arithmetics directly on representations and the main goal is
simplicity, a simpler version of the density-based encoding is used. It is
also known under the name thermometric encoding [9].

Figure 2: An example of the density-based encoding when the dimensionality of
representation is set to $N=4$.

The most intuitive way of presenting the concept of the density-based encoding
is via the visualization. Fig. 2 illustrates all possible values, which could
be encoded when dimensionality of the representation555It will become evident
in Section III why the same notation $N$ as for the number of hidden neurons
is used. is set to $N=4$. Fig. 2 indicates that using the density-based
encoding it is possible to represent $N+1$ different values. The most
convenient way of denoting these values is by using integers in the range
$[0,N]$ (nodes on the left in the figure). In this case, in order to obtain
the encoding of a given value $v$, it is necessary to set $v$ leftmost
positions of the vector to “one” (hashed red nodes in the figure) while the
rest of the vector is set to “zero” (filled green nodes). In the case of
bipolar representations used below, “one” corresponds to $-1$ while “zero”
corresponds to $1$.

Recall, however, that input features are not scalars integers in the range
$[0,N]$. Instead, it is assumed that a feature $x_{i}$ is represented by a
real number in the range $[0,1]$. The task is to represent the current value
of the feature as a vector $\textbf{f}\in[N\times 1]$ using the above density-
based encoding. Since, the encoding requires a finite set of values between 0
and $N$ real numbers are first discretized using a fixed quantization step,
which is determined by $N$. Given the current value the feature, it is
quantized to the closest integer as:

$v=\lfloor x_{i}N\rceil,$ (4)

where $\lfloor*\rceil$ denotes rounding to the the closest integer. The
obtained $v$ will determine the density-based encoding f. The presented
procedure allows generating density-based encodings for the whole feature
vector x. Matrix $\textbf{F}\in[N\times K]$ contains the density-based
encodings f of the current values of x.

###  II-C Hyperdimensional computing

Hyperdimensional computing [10, 11] also known as Vector Symbolic
Architectures is a family of bio-inspired methods of representing and
manipulating concepts and their meanings in a high-dimensional space. Vectors
of high (but fixed) dimensionality (denoted as $N$) are the basis for
representing information in hyperdimensional computing.666These vectors are
referred to as high-dimensional vectors or HD vectors. The information is
distributed across HD vector’s positions, therefore, HD vectors use
distributed representations. Distributed representations [12] are contrary to
the localist representations since any subset of the positions can be
interpreted. This is very relevant to the density-based encoding introduced in
the previous subsection since the encoding in f is also distributed.

In the scope of this article, columns of $\textbf{W}^{\text{in}}$ matrix are
interpreted as HD vectors, which are generated randomly. These HD vectors are
bipolar ($\textbf{W}^{\text{in}}\in\\{-1,+1\\}^{[N\times K]}$) and random with
equal probabilities for $+1$ and $-1$. It is worth noting that an important
property of high-dimensional spaces is that with an extremely high probability
all random HD vectors are dissimilar to each other (quasi orthogonal). In
order to manipulate HD vectors, hyperdimensional computing defines operations
on them. In this article, we implicitly use only two key operations: binding
and bundling.

The binding operation is used to associate two HD vectors together. The result
of binding is another HD vector. Here, the result of binding (denoted as z)
two vectors x and y is calculated as follows:
$\textbf{z}=\textbf{x}\odot\textbf{y}$, where the notation $\odot$ for the
Hadamard product is used to denote the binding operation since this article
uses position-wise multiplication for binding. An important property of the
binding operation is that the resultant HD vector z is quasi orthogonal to the
HD vectors being bound.

The second operation is called bundling. The bundling operation combines
several HD vectors into a single HD vector. Its simplest realization is a
position-wise addition. However, when using the position-wise addition, the
vector space becomes unlimited, therefore, it is practical to limit the values
of the result. This could be achieved with, e.g., a clipping function (denoted
as $f_{\kappa}(*)$):

$f_{\kappa}(x)=\begin{cases}-\kappa&x\leq-\kappa\\\ x&-\kappa<x<\kappa\\\
\kappa&x\geq\kappa\end{cases}$ (5)

In the clipping function, $\kappa$ is a configurable threshold parameter.
Thus, in this article, the bundling operation is implemented via position-wise
addition limited via the clipping function. For example, the result (denoted
as a) of bundling HD vectors x and y is simply:
$\textbf{a}=f_{\kappa}(\textbf{x}+\textbf{y})$. In contrast to the binding
operation, the resultant HD vector a is similar to all bundled HD vectors,
which allows, e.g., storing information in HD vectors [13].

##  III RVFL with density-based encodings

This section presents an architecture of the RVFL utilizing the density-based
encoding. The approach is illustrated in Fig. 3. The architecture is
intentionally depicted to be as structurally identical to the conventional
RVFL (Fig. 1) as possible. The major difference is that the proposed approach
is illustrated with four layers of neurons: input layer (x, $K$ neurons);
density-based representation layer (F, $NK$ neurons); hidden layer (h, $N$
neurons); and output layer (y, $L$ neurons). Thus, in contrast to the
conventional RVFL, the hidden layer is not connected directly to the input
layer. Instead, each input feature is first transformed to a row of neurons
storing its density-based encodings. These vectors constitute the density-
based representation layer, which in turn is connected to the hidden layer.
Note also, that the input and density-based representation layers are not
fully-connected. Each neuron in the input layer is only connected to $N$
neurons in the corresponding row of the next layer. Moreover, these
connections (blue lines in Fig. 3) are called “feature-dependent” because the
activation of the $i$-th input neuron $\textbf{x}_{i}$ will be quantized to
the closest integer $v$ according to (4); in turn $v$ determines the number of
the rightmost connections, which transmit $-1$, the remaining connections from
that neuron transmit $+1$. Since each neuron in the density-based
representation layer has only one incoming connection, the input activations
are projected in the form of the bipolar matrix F .

Figure 3: The architecture of the Random Vector Functional Link, which relies
on the density-based encoding. In the presented example, the number of hidden
neurons as well as the dimensionality of encoding are set to $N=4$.

It is also important to mention that the density-based representation and
hidden layers are not fully-connected. In fact, each neuron in the density-
based representation layer has only one outgoing connection. Therefore, the
matrix $\textbf{W}^{\text{in}}$ describing the fixed random connections to the
hidden layer is still $\textbf{W}^{\text{in}}\in[N\times K]$. Moreover, these
connections have a clear structure. In Fig. 3 the connections are structured
in such a way that each column in F is connected to one of the hidden layer
neurons. It explains why the number of hidden neurons $N$ also determines the
dimensionality of the density-based encoding of features: each hidden neuron
has its corresponding column in F (see Fig. 4).

Similar to the conventional RVFL, the values of $\textbf{W}^{\text{in}}$ are
also generated randomly. However, the values are drawn equiprobably from
$\\{-1,+1\\}$. Thus, similar to F, $\textbf{W}^{\text{in}}$ is also a bipolar
matrix. When reflecting to the ideas of hyperdimensional computing,
$\textbf{W}^{\text{in}}$ should be interpreted as $K$ $N$-dimensional bipolar
HD vectors. In other words, each feature is assigned with the corresponding HD
vector. Thus, a conceptual intermediate step before getting input values of
the hidden neurons is the binding operation between features’ HD vectors and
their current density-based encoding.

Finally, the proposed approach uses different nonlinear activation function in
the hidden layer, clipping (5) is used instead of the sigmoid function. The
clipping function is characterized by the threshold value $\kappa$ regulating
nonlinear behavior of the neurons and limiting the range of activation values.
Summarizing aforementioned differences, activations of the hidden layer h are
as follows:

$\textbf{h}=f_{\kappa}(\sum\textbf{F}\odot\textbf{W}^{\text{in}}),$ (6)

where $\sum$ is a column-wise summation. Note that in contrast to (1) there is
no bias term since it has been found empirically that its presence does not
improve classification performance. Once the activations of the hidden layer h
are obtained, the rest of the network works in the same way as the
conventional RVFL. The predictions in y are calculated according to (2).

In order to make operations of the proposed approach more intuitive, Fig. 4
presents a numeric example of acquiring the activations of the hidden layer.
First, the input layer with $K=5$ neurons sets the values of the current
feature vector. These values are quantized to integers in the range [0,10]
(since $N=10$). The quantized values determine the neurons of the density-
based encoding, which are set to $-1$ (the rest is $+1$). For example, since
the third feature is quantized to $v=10$ all values of its density-based
encoding are set to $-1$. The bottom left panel shows a randomly generated
$\textbf{W}^{\text{in}}$. Once F is obtained, we calculate the Hadamard
product $\textbf{F}\odot\textbf{W}^{\text{in}}$, which is denoted as “bound
representations” in Fig. 4. The row-wise summation of the resultant matrix
represents the input values of the hidden layer. Finally, the clipping
function ($\kappa=2$ in Fig. 4) is used in the hidden layer to get h.

Note that due to the way of forming F and $\textbf{W}^{\text{in}}$, the input
to the hidden layer neurons is always integers in the range $[-K,K]$.
Moreover, even after the clipping the activations of neurons are integers in
the range $[-\kappa$ and $\kappa]$ (practically, $\kappa<K$). Thus, each
hidden neuron can be represented using only $\lceil\log_{2}(2\kappa+1)\rceil$
bits of memory. For example, when $\kappa=3$, there are seven unique
activations of a neuron, which can be stored with just three bits. Last but
not least, it is worth mentioning that for an efficient implementation the
explicit calculation of F is redundant. As it could be seen from Fig. 4, the
same result as $\textbf{F}\odot\textbf{W}^{\text{in}}$ could be obtained if
for each feature we use $v$ as an indicator of which signs should be changed
in $\textbf{W}^{\text{in}}$. As it will be shown in the next section, these
properties give a major advantage over the conventional RFVL for resource-
efficient implementation on digital hardware.

Figure 4:  An example of activating the hidden layer with density-based
encodings: $K=5$; $N=10$.

Since in the proposed approach the part of the network between the hidden and
output layers is not modified, the simplest case is to train the readout
matrix $\textbf{W}^{\text{out}}$ in the same manner as for the conventional
RVFL (Section II-A). However, since the goal is to obtain a very simplistic
implementation, it is worth considering alternatives where
$\textbf{W}^{\text{out}}$ would contain only integer values in a small limited
range. In particular, we have considered three options: quantizing the result
of regression (3); using a genetic algorithm (GA) initialized randomly; using
GA initialized with the quantized result of regression. During the search, GA
used the cost function for the generalized Learning Vector Quantization [14].

##  IV Performance evaluation

Figure 5:  Cross-validation accuracy of the conventional RVFL against the
proposed approach. A point corresponds to a dataset.

Figure 6:  Average cross-validation accuracy of the proposed approach for
different integer readout strategies.

Figure 7:  Cross-validation accuracy of the finite precision RVFL against the
proposed approach in case of the fixed energy budget.

In this section, the proposed approach is verified in three scenarios. The
first scenario compares it against the conventional RVFL in the case when the
weights of the readout matrix are real numbers for both approaches. The second
scenario compares the results for the real-valued readout matrix against the
considered strategies of obtaining integer-valued readout matrix. The final
scenario compares FPGA implementations of the proposed approach and the finite
precision RVFL [8] in the case of a limited energy budget. All reported
results are based on $121$ real-world classification datasets obtained from
the UCI Machine Learning Repository777UCI. Available online:
https://archive.ics.uci.edu/ml/datasets.php.. The considered collection of
datasets has been initially analyzed in a large-scale comparison study of
different classifiers and the interested readers are kindly referred to the
original work [15] for more details. The only preprocessing step was to
normalize features in the range $[0,1]$. Finally, the reported accuracies were
averaged across five independent initializations.

###  IV-A Comparison with the conventional RVFL

First, we compare the conventional RVFL with the proposed approach when
computational resources for both approaches are not limited. The search of the
hyperparameters has been done according to [15] using the grid search over
$\lambda$ and $N$ in the case of the conventional RVFL and additionally
considering $\kappa$ for the proposed approach; $N$ varied in the range
$[50,1500]$ with step $50$; $\lambda$ varied in the range $2^{[-10,5]}$ with
step $1$; and $\kappa$ varied between $\\{1,3,5,7\\}$. The obtained optimal
hyperparameters were used to estimate the cross-validation accuracy on all
datasets. In order to visualize the results, we rely on the same approach as
reported in [16]. Fig. 7 presents the accuracy of the conventional RVFL
against the proposed approach. First, it is important to note that as expected
the correlation coefficient between the obtained results is high ($0.86$).
Moreover, the average accuracy for the conventional RVFL is $0.76$ while that
for the proposed approach is $0.80$.888In [15] the highest mean accuracy
$0.82$ was obtained for Random Forest. It is not absolutely intuitive why the
proposed approach demonstrates higher accuracy. Nevertheless, one hypothesis
is that the quantization for the density-based encoding might provide extra
regularization.999For the conventional RVFL with quantized inputs the mean
accuracy was $0.753$ ($0.755$ for non-quantized). The correlation coefficient
was $0.986$. Thus, the improvement cannot be caused barely by the input
quantization.

###  IV-B The effect of quantized readout weights

Fig. 7 presents the average accuracy of the proposed approach for three
considered strategies of obtaining the readout matrix with integer values
against the average accuracy from the previous experiment. The considered
ranges are symmetric and the figure indicates only positive boundaries. It is
clear that if the result of regression is quantized (dashed line) to very few
levels the accuracy is affected significantly. However, with the increased
number of levels, the accuracy approaches the baseline and it is concluded
that 5-bits per weight results in a very close approximation. Refining the
quantized result of regression with GA (dash-dot line) certainly improved the
accuracy for a small number of quantization levels, which is in line with the
results in [8]. However, using GA for the number of levels larger than six was
not beneficial. Random GA initialization (dotted line) decreased the accuracy.

###  IV-C Performance in the case of limited resources

The third experiment compares FPGA hardware implementations of the proposed
approach and the finite precision RVFL in the case of a fixed energy budget
per one classification pass. The idea of restricting the energy budget could
be seen as an intuitive set-up for comparing bounded-optimality [17] of two
approaches. Finite precision RVFL [8] with $8$-bits per neuron/weight was used
since it is more efficient than the conventional RVFL.101010 When comparing
FPGA implementations of the conventional RVFL and the proposed approach
(integer readout) for a network where $K=16$, $N=512$, and $L=4$ (median
values for the $121$ UCI datasets) the proposed approach consumed about $11$
times less energy and was $2.5$ times faster.  Following the conclusions from
the previous experiment, the resolution of the readout weights of the proposed
approach was set to $5$-bits. Both approaches were deployed on ZedBoard FPGA
and the energy consumption was estimated with the Xilinx Power Estimator tool.
The energy budget was set to $3.2\text{\,}\mathrm{\SIUnitSymbolMicro J}$ to
reflect an average network.111111Since in each dataset input and output sizes
are fixed, the budget was enforced by determining number of hidden layer
neurons within the budget. Fig. 7 presents the accuracy of the proposed
approach (average $0.73$) against the finite precision RVFL (average $0.65$).
Due to the limited resources, values are lower than in the first experiment,
nevertheless, the results are impressive when the performance of our approach
is compared to the fixed point RVFL.

##  V Related work

This section briefly describes the related work. First of all, the readers
generally interested in neural networks, which rely on randomly created
connections, are kindly referred to the survey in [6]. In order to design a
resource-efficient RVFL algorithm, the proposed approach combines the ideas
from two areas. These are the density-based encoding from stochastic computing
and the binding and bundling operations from hyperdimensional computing. Since
both are research fields on their own, here we only indicate the introductory
papers facilitating entrance to the areas. Recent magazine article [4] is
probably the most approachable reading for stochastic computing. With respect
to hyperdimensional computing, the best starting point is the tutorial-like
article [5] by Kanerva.

Since even the conventional RVFLs are considered as one of the simplest
approaches for machine learning, it explains why the efforts on pushing their
resource-efficiency to the extreme are limited. The most relevant works in
this direction are [8, 18]. Similar to the present study, both works use FPGA
for hardware experiments. Moreover, both works rely on finite precision
implementation for improving the resource-efficiency. The work [18], however,
heavily focuses on the process of obtaining the weights of the readout matrix,
which is not the case here. The work [8], which focuses on the operating
phase, is used here as the baseline for comparison with the proposed approach.
However, none of the previous works in the area of RVFL, to the best of our
knowledge, have been focusing on using the combination of the density-based
encoding with the binding operation.

Finally, it is worth mentioning that in recent years the simplification of
computing architectures for neural networks is an important research topic.
Notable examples are works [19, 20, 21], which have been evaluated on
convolutional neural networks; work [22] that has introduced networks with
ternary activations and work [23] that has introduced networks where all
parameters are binary. It is worth mentioning that in contrast to the bit-wise
networks [23], the proposed use of the density-based encoding does not
requires the binarization of the input features, which often worsens the
accuracy.

##  VI Conclusions

This article proposed a resource-efficient fully-integer approach to randomly
connected neural networks. The key enabler for efficiently obtaining
activations of the hidden neurons is the combination of representing input
features via the density-based encoding used in the stochastic computing with
the use of binding and bundling operations from hyperdimensional computing
domain. Integer values of the readout matrix could be obtained with minimal
loss in the accuracy, e.g., by simple rounding of the ridge regression
solution, which in turn could be fine-tuned by the genetic algorithm. The
empirical evaluation was performed on $121$ real-world datasets. The proposed
approach demonstrated a higher average accuracy than the conventional RVFL
networks while being $2.5$ times faster and consuming eleven times less energy
(typical network on FPGA). Finally, the accuracy of the proposed approach
significantly prevailed that of the finite precision RVFL networks when both
networks implemented on hardware were constrained to a fixed limited energy
budget.

Despite that this work has focused only on classification tasks it is worth
mentioning that the proposed approach of forming the activations of the hidden
layer should be seen as a generic structured representation scheme based on
high-dimensional random projections that allow for direct learning of complex
nonlinear functions. Therefore, a promising direction for future work is to
develop an analytical theory similar to the capacity theory of such
representations [13] that would relate the quality of approximations based on
the complexity of a nonlinear function, number of its inputs and outputs, and
a number hidden neurons and their resolution.

Last but not least, we conjecture that the density-based encoding will be
useful for developing resource-efficient versions of other neural networks.
For example, as it has been recently shown in [24] binarizing initial layers
of convolutional neural networks could easily harm their accuracy. We expect
that the density-based encoding of input features will solve this issue.

## References

  * [1] B. Igelnik and Y. Pao, “Stochastic Choice of Basis Functions in Adaptive Function Approximation and the Functional-Link Net,” _IEEE Transactions on Neural Networks_ , vol. 6, pp. 1320–1329, 1995.
  * [2] G. Huang and Q. Zhu and C. Siew, “Extreme Learning Machine: Theory and Applications,” _Neurocomputing_ , vol. 70, no. 1-3, pp. 489–501, 2006.
  * [3] H. D. Nguyen, D. Wang, and G. J. McLachlan, “Randomized Mixture Models for Probability Density Approximation and Estimation,” _arXiv:1804.08341_ , pp. 1–31, 2018.
  * [4] A. Alaghi and J.P. Hayes, “Computing with Randomness,” _IEEE Spectrum_ , vol. 55, no. 3, pp. 46–51, 2018.
  * [5] P. Kanerva, “Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors,” _Cognitive Computation_ , vol. 1, no. 2, pp. 139–159, 2009.
  * [6] S. Scardapane and D. Wang, “Randomness in Neural Networks: an Overview,” _Data Mining and Knowledge Discovery_ , vol. 7, pp. 1–18, 2017.
  * [7] L. Zhang and P. Suganthan, “A Comprehensive Evaluation of Random Vector Functional Link Networks,” _Information Sciences_ , vol. 367-368, pp. 1094–1105, 2016.
  * [8] A. Rosato, R. Altilio, and M. Panella, “Finite Precision Implementation of Random Vector Functional-Link Networks,” in _22nd International Conference on Digital Signal Processing (DSP)_ , 2017, pp. 1–5.
  * [9] D. A. Rachkovskij, S. V. Slipchenko, E. M. Kussul, and T. N. Baidyk, “Sparse Binary Distributed Encoding of Scalars,” _Journal of Automation and Information Sciences_ , vol. 37, no. 6, pp. 12–23, 2005.
  * [10] T. A. Plate, _Holographic Reduced Representations: Distributed Representation for Cognitive Structures_. Stanford: Center for the Study of Language and Information (CSLI), 2003.
  * [11] S. I. Gallant and T. W. Okaywe, “Representing Objects, Relations, and Sequences,” _Neural Computation_ , vol. 25, no. 8, pp. 2038–2078, 2013\.
  * [12] G. E. Hinton, J. L. McClelland, and D. E. Rumelhart, “Distributed Representations,” in _Parallel Distributed Processing. Explorations in the Microstructure of Cognition. Volume 1. Foundations_ , D. Rumelhart and J. McClelland, Eds. MIT Press, 1986, pp. 77–109.
  * [13] E. P. Frady, D. Kleyko, and F. T. Sommer, “A Theory of Sequence Indexing and Working Memory in Recurrent Neural Networks,” _Neural Computation_ , vol. 30, pp. 1449–1513, 2018.
  * [14] A. Sato and K. Yamada, “Generalized Learning Vector Quantization,” in _Advances in Neural Information Processing Systems 8 (NeurIPS)_ , 1996, pp. 423–429.
  * [15] M. Fernandez-Delgado, E. Cernadas, S. Barro, and D. Amorim, “Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?” _Journal of Machine Learning Research_ , vol. 15, pp. 3133–3181, 2014.
  * [16] M. Olson, A. J. Wyner, and R. Berk, “Modern Neural Networks Generalize on Small Data Sets,” in _Advances in Neural Information Processing Systems 32 (NeurIPS)_ , 2018, pp. 1–10.
  * [17] S. J. Russell and D. Subramanian, “Provably Bounded-Optimal Agents,” _Journal of Artificial Intelligence Research_ , vol. 2, pp. 575–609, 1995.
  * [18] J. M. Martinez-Villena and A. Rosado-Munoz and E. Soria-Olivas, “Hardware Implementation Methods in Random Vector Functional-Link Networks,” _Applied Intelligence_ , vol. 41, no. 1, pp. 184–195, 2014.
  * [19] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko, “Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference,” _arXiv:1712.05877_ , pp. 1–14, 2017.
  * [20] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio, “Binarized Neural Networks,” in _Advances in Neural Information Processing Systems 29 (NeurIPS)_ , 2016, pp. 1–9.
  * [21] ——, “Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations,” _Journal of Machine Learning Research_ , vol. 18, pp. 1–30, 2018.
  * [22] H. Alemdar, V. Leroy, A. Prost-Boucle, and F. Petrot, “Ternary Neural Networks for Resource-Efficient AI Applications,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2017, pp. 2547–2554.
  * [23] M. Kim and P. Smaragdis, “Bitwise Neural Networks,” in _31st International Conference on Machine Learning (ICML)_ , 2015, pp. 1–5.
  * [24] A. G. Anderson and C. P. Berg, “The High-Dimensional Geometry of Binary Neural Networks,” in _International Conference on Learning Representations (ICLR)_ , 2018, pp. 1–13.


# definitions

Kristina Dedndreaj This research has been funded by the European Social Fund
(ESF). SAB PRANO Nr: 1562608885160. University of Applied Sciences Mittweida

# Two extremal problems in the light of Lex graphs

Kristina Dedndreaj This research has been funded by the European Social Fund
(ESF). SAB PRANO Nr: 1562608885160. University of Applied Sciences Mittweida

###### Abstract

Extremal problems involving independent sets are much studied. Two of the most
important extremal problems in this context are concerned with the sharp upper
bounds for the number of independent sets of fixed size and the independence
number. In literature, these sharp upper bounds are derived in completely
different contexts. In this paper, we show that both of these sharp upper
bounds can be derived by considering Lex graphs. More exactly, they depend on
two parameters of a sequence defined on them.

##  1 Introduction

By complementation, counting independent sets is equivalent to clique
counting. The study of the latter was greatly influenced by the discovery of
the Turán’s theorem [10]. For different aspects of the study of the clique
counting the reader is referred to [5], [2], [9], [7], [8], [11] and [1, ch.
VI].

We will focus on the sharp upper bounds for the number of independent sets of
fixed size and the independence number of $G(n,m)$ graphs, that is, graphs of
order $n$ and size $m$. Hanani and Erdös [5] proved that the maximal number of
complete subgraphs of order $r$ contained in a $G(n,m)$ graph depends only on
$m$.

######  Theorem 1 ([5]).

Let $G(m)$ be a graph on $m$ edges and let $r\geq 3$ be a natural number. Let
$s,t$ be two natural numbers such that $m=\binom{s}{2}+t$ with $0<t\leq s$.
Then

$c_{r}\leq\binom{s}{r}+\binom{t}{r-1}.$ (1)

Where $c_{r}$ denotes the number of cliques of order $r$ contained in $G(m)$.

######  Remark 1.

For given $m$ the numbers $s$ and $t$ in Theorem 1 are unique. This implies
that $s$ is the smallest positive integer which satisfies

$m\leq\dfrac{s(s+1)}{2}.$ (2)

Therefore we have

$s=\left\lceil\sqrt{\frac{1}{4}+2m}-\frac{1}{2}\right\rceil$ (3)

from where the value of $t$ is evident.

######  Lemma 1.

Let $x$ be a real number and let $\\{x\\}=x-\lfloor x\rfloor$ denote its
fractional part. The following holds

$\left\lceil x-\frac{1}{2}\right\rceil=\begin{cases}\left\lfloor
x+\dfrac{1}{2}\right\rfloor-1&\text{if }\\{x\\}=\dfrac{1}{2},\\\\[11.38109pt]
\left\lfloor x+\dfrac{1}{2}\right\rfloor&\text{otherwise}.\end{cases}$ (4)

Note that when we want to find the maximal number of independent sets of size
$r$ by using Theorem 1 then we need to find the maximal number of cliques of
size $r$ in its complement. Thus, the maximal number of independent sets of
fixed size depends on the order and the size of the graph, unlike the maximal
number of cliques of fixed size. We re-write Theorem 1 in terms of independent
sets.

######  Theorem 2.

Let $G(n,m)$ be a graph on $n$ vertices and $m$ edges and let $r\geq 3$ be a
natural number. Let $s,t$ be two natural numbers such that
$\binom{n}{2}-m=\binom{s}{2}+t$ with $0<t\leq s$. Then

$i_{r}\leq\binom{s}{r}+\binom{t}{r-1}.$ (5)

Where $i_{r}$ denotes the number of independent sets of order $r$ contained in
$G(n,m)$.

By putting $\binom{n}{2}-m$ instead of $m$ in Equation (3) the value of $s$ in
Theorem 2 is

$\left\lceil-\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rceil.$ (6)

For notation convenience, in the following Theorem we will let ${\alpha}_{u}$
denote the sharp upper bound for the independence number of $G(n,m)$ graphs.
As we will see later, the number $s$ has the following property.

######  Theorem 3.

For a given $G(n,m)$ graph let the numbers $s,t$ be as in Theorem 2. The
followig holds

$s=\begin{cases}{\alpha}_{u}-1&\text{if }\binom{n}{2}-m=\binom{s}{2}+s,\\\
{\alpha}_{u}&\text{otherwise }.\end{cases}$ (7)

It seems that this interesting fact was not proved nor noticed by Hanani and
Erdös in [5] where Theorem 1 makes its first appearance. However, as we will
show later, it can be understood and explained in the context of Lex graphs.
In the next section, we will prove Theorem 2 and Theorem 3 by using Lex
graphs.

##  2 Lex graphs

######  Definition 1 ([3]).

Given $A,B\subset\mathbf{N}$ we say $A$ precedes $B$ in lexicographic (or lex)
ordering, written $A{<}_{L}B$, if $\min\\{A\triangle B\\}\in A$.

The lex graph, denoted $L(n,m)$, is the graph with vertex set
$[n]=\\{1,\ldots,n\\}$ and edge set the first $m$ elements of $\binom{[n]}{2}$
under the lex ordering. The first few elements of the lex order on
$\binom{[n]}{2}$ are

$\\{1,2\\},\\{1,3\\},\\{1,4\\},\ldots,\\{1,n\\},\\{2,3\\},\\{2,4\\},\ldots,\\{2,n\\},\\{3,4\\},\ldots$

[ V/.style = circle,thick,fill=white,scale=0.4] [V] (1) at (6,4)
[scale=0.5,draw] 1; [V] (2) at (1,4) [scale=0.5,draw] 2; [V] (3) at (3,2)
[scale=0.5,draw] 3; [V] (4) at (3,6) [scale=0.5,draw] 4; [V] (5) at (9,4)
[scale=0.5,draw] 5; [black,very thick] (1) to (2) (1) to (3) (1) to (4) (1) to
(5) (2) to (3) (2) to (4);

Figure 1: $L(5,6)$

The class of the lex graphs is interesting because they are extremal for the
number of the independent sets. The lex graph $L(n,m)$ maximizes both, the
total number independent sets and the number of independent sets of fixed size
for $G(n,m)$ graphs [3].

######  Lemma 2.

[4] Let $m,n$ be two natural numbers such that $1\leq m\leq\binom{n}{2}$. Then
there exists a unique sequence ${\\{p_{i}\\}_{i=1}^{k}}$ such that

$\sum\limits_{i=1}^{k}p_{i}=m$ (8)

where:

  1. 1.

$p_{i}>0$ and $1\leq k\leq n-1$,

  2. 2.

$p_{i}=n-i$ for $i<k$,

  3. 3.

If $p_{k}\neq n-k$ then $p_{k}\in\\{1,\ldots,n-k-1\\}$.

###### Proof.

The proof can be done by induction on $m$. ∎

######  Definition 2.

[4] Let $m,n$ be two natural numbers such that $1\leq m\leq\binom{n}{2}$.
Expansion (8) satisfying conditions (1)-(3) in Lemma (2) is called subsequent
decreasing summation decomposition of $m$ with base $n$ or shortly $sds(m,n)$.
The number $k$ is called depth of the summation (8) or the depth of
$sds(m,n)$.

######  Remark 2.

From Definition 2 we have that the depth $k$ of $sds(m,n)$ is the smallest
number in the set $\\{1,\ldots,n-1\\}$ which satisfies

$m\leq\frac{k(2n-k-1)}{2}.$ (9)

Therefore the value for $k$ is

$\left\lceil n-\frac{1}{2}-\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rceil.$ (10)

The value for $p_{k}$ is

$m-\sum\limits_{i=1}^{k-1}n-i=m-\frac{(k-1)(2n-k)}{2}.$ (11)

Let $L(n,m)$ be a lex graph on $n$ vertices and $m$ edges such that $m\geq 1$.
The depth of $sds(m,n)$ is called the depth of the lex graph $L(n,m)$. Let
$N(i)$ denote the open neighborhood of the vertex $i$. For $1\leq i\leq n$ let
$A(i)=\\{v\in[n]:v<i\\}$ and $B=\\{k+1,\ldots,k+p_{k}\\}$ then by virtue of
the definition of $L(n,m)$ we have

$N(i)=\begin{cases}V\setminus\\{i\\}&\text{ for }i\in\\{1,\ldots,k-1\\},\\\
A(i)\cup B&\text{ for }i=k,\\\ A(k+1)&\text{ for
}i\in\\{k+1,\ldots,k+p_{k}\\},\\\ A(k)&\text{ for
}i\in\\{k+p_{k}+1,\ldots,n\\}.\end{cases}$

For given $m,n$ where $1\leq m\leq\binom{n}{2}$, the sequence
${\\{p_{i}\\}_{i=1}^{k}}$, the numbers $p_{k}$ and $k$ as in Remark 2 will be
crucial for the derivation of the sharp upper bounds for the number of
independent sets of fixed size and the independence number for graphs of order
$n$ and size $m$.

######  Theorem 4.

Let $L(n,m)$ be the lex graph with $n$ vertices, $m$ edges and depth $k$. Then
the maximum independent sets of $L(n,m)$ have size $n-k$.

###### Proof.

Let $A=\\{1,\ldots,k-1\\}$, $B=\\{k,p_{k}+1,\ldots,n\\}$ and
$C=\\{k+1,\ldots,n\\}$. Notice that $A\cup B\cup C=V$ and $B^{\complement}\cap
C^{\complement}\subset A$. Also, notice that no element of $A$ can belong to
an independent set with cardinality greater than one because for such elements
we have $N(i)=V\setminus\\{i\\}$. We claim that every independent set with
cardinality greater than one is a subset of $B$ or a subset of $C$. Assume the
opposite, that there exists an independent set $I$ with cardinality greater
than one which is not a subset of $B$ nor a subset of $C$. This means that

$I\cap B^{\complement}\neq\emptyset\text{ and }I\cap
C^{\complement}\neq\emptyset,$ (12)

therefore, $I\cap A\neq\emptyset$. As a consequence, there exists an element
of $A$ which belongs to an independent set with cardinality greater than one,
a contradiction.

Next we will show that the sets $B,C$ are independent dominating sets and
therefore maximal independent sets. That they are independent it is clear from
the construction of the graph $L(n,m)$. The set $B$ is dominating because
every element of $B^{\complement}$ is adjacent to an element of $B$. In the
same way we conclude that the set $C$ is dominating.

Note that $|B|=n-k-p_{k}+1$ and $|C|=n-k$. If $p_{k}>1$, the set $C$ is the
only maximum independent set of the graph $L(n,m)$. If $p_{k}=1$ then
$|B|=|C|$ and the graph has two maximum independent sets, $B$ and $C$. ∎

Since the lex graph $L(n,m)$ maximizes the number of independent sets of fixed
size for $G(n,m)$ then $n-k$ is a sharp upper bound for the independence
number $\alpha$ of $G(n,m)$-graphs. Therefore by combining Remark 2 and
Theorem 4 we have the following theorem. This result was found first by Hansen
and Zheng [6]. We present a new and simple proof here.

######  Theorem 5.

Let $G$ be a graph with $n$ vertices and $m$ edges and with independence
number $\alpha$ then

$\alpha\leq\left\lfloor\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rfloor$
(13)

and the bound is sharp.

###### Proof.

Note that for real numbers $a$ and $b$ we have: $a-(b+1)<a-\lceil b\rceil\leq
a-b$. This imples that

$\displaystyle-\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}$
$\displaystyle<n-\left\lceil
n-\frac{1}{2}-\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rceil$ (14)
$\displaystyle\leq\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}$ (15)

and therefore by the definition of the floor function

$n-\left\lceil
n-\frac{1}{2}-\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rceil=\left\lfloor\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rfloor.$
(16)

By Theorem 4 we have that $\alpha\leq n-k$. By inserting the solution for $k$
from Remark 2 we have:

$\displaystyle\alpha$ $\displaystyle\leq n-\left\lceil
n-\frac{1}{2}-\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rceil$
$\displaystyle=\left\lfloor\frac{1}{2}+\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\rfloor.$

∎

######  Theorem 6.

Let $L(n,m)$ be the lex graph with $n$ vertices, $m$ edges and depth $k$. Then
the number of independent sets of size $r>2$ in $L(n,m)$, denoted $i_{r}$ is

$\binom{n-k-p_{k}}{r-1}+\binom{n-k}{r}.$

###### Proof.

There are two types of independent sets of size $r$:

  1. 1.

Independent sets which contain the vertex $k$. There are

$\binom{n-k-p_{k}}{r-1}$ (17)

such sets.

  2. 2.

Independent sets which do not contain the element $k$. There are

$\binom{n-k}{r}$ (18)

such sets.

∎

By using the extremality of $L(n,m)$, Theorem 6 and Remark 2 we have the
following corollary which gives a sharp upper bound for the number of
independent sets of fixed size.

######  Corollary 1.

Let $G(n,m)$ be a graph with $n$ vertices and $m$ edges and let $i_{r}$ be its
number of independent sets of size $r$ then

$i_{r}\leq\binom{n-k-p_{k}}{r-1}+\binom{n-k}{r}$ (19)

where $k$ and $p_{k}$ are as in Remark 2 and the bound is sharp.

######  Remark 3.

When $m=\sum\limits_{i=1}^{k}n-i$ then $n-k-p_{k}=0$ and the Inequality (19)
becomes

$i_{r}\leq\binom{n-k}{r}=\binom{n-k-1}{r}+\binom{n-k-1}{r-1}.$ (20)

Note that

  1. 1.

$m=\sum\limits_{i=1}^{k}n-i\Longleftrightarrow\binom{n}{2}-m=\binom{s}{2}+s$
and

  2. 2.

$\left\\{\sqrt{\frac{1}{4}+n^{2}-n-2m}\right\\}=\frac{1}{2}\Longleftrightarrow\binom{n}{2}-m=\binom{s}{2}+s$

where $k$ and $s$ are some natural numbers. By making use of these
observations and Lemma 1 we can see that Theorem 2 and Theorem 3 are
consequences of Corollary 1.

## References

  * [1] Béla Bollobás  “Extremal graph theory”  Dover Publications Inc., 2004
  * [2] Béla Bollobás  “On complete subgraphs of different orders”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 79.1, 1976, pp. 19–24  Cambridge University Press
  * [3] Jonathan Cutler and AJ Radcliffe  “Extremal problems for independent set enumeration”  In _The Electronic Journal of Combinatorics_ 18.1, 2011, pp. #P169
  * [4] Kristina Dedndreaj and Peter Tittmann  “On the activities and partitions of the vertex subsets of graphs”  In _Enumerative Combinatorics and Applications_ 2.2, 2022, pp. #S2R11
  * [5] Paul Erdös  “On the number of complete subgraphs contained in certain graphs”  In _A Magyar Tudományos Akadémia Matematikai Kutató Intézet Közleményei_ 7.3, 1962, pp. 459–464
  * [6] Pierre Hansen and Maolin Zheng  “Sharp bounds on the order, size, and stability number of graphs”  In _Networks_ 23.2 Wiley Online Library, 1993, pp. 99–102
  * [7] László Lovász and Miklós Simonovits  “On the number of complete subgraphs of a graph II”  In _Studies in Pure Mathematics_ Birkhäuser, Basel, 1983
  * [8] John W Moon and Leo Moser  “On cliques in graphs”  In _Israel journal of Mathematics_ 3.1 Springer, 1965, pp. 23–28
  * [9] JW Moon  “On independent complete subgraphs in a graph”  In _Canadian Journal of Mathematics_ 20 Cambridge University Press, 1968, pp. 95–102
  * [10] Paul Turán  “On an external problem in graph theory”  In _Matematikai és Fizikai Lapok_ 48, 1941, pp. 436–452
  * [11] David R Wood  “On the maximum number of cliques in a graph”  In _Graphs and Combinatorics_ 23.3 Springer, 2007, pp. 337–352


$\mathcal{F}\colon(\mathbf{R},\leq)\to\mathbf{Digraph}_{0}$ is a filtration,
and the composition of functors in (7) yields the categorical persistence
function. Furthermore, for each pair of real numbers $u\leq v$, Hochschild
homology gives the linear maps

$\mathrm{HH}_{0}(\mathbf{K}\mathcal{PG}_{u}^{(n)})\to\mathrm{HH}_{0}(\mathbf{K}\mathcal{PG}_{v}^{(n)})\
\text{ and }\
\mathrm{HH}_{1}(\mathbf{K}\mathcal{PG}_{u}^{(n)})\to\mathrm{HH}_{1}(\mathbf{K}\mathcal{PG}_{v}^{(n)})$

of finite dimensional vector spaces. By taking the images of these maps, we
get the desired persistent Betti numbers:

######  Definition 4.6.

The $(n,1)$-persistent Betti number of a filtration in $\mathbf{Digraph}_{0}$
is the persistent Betti number induced by
$\mathrm{HH}_{1}(\mathbf{K}\mathcal{PG}_{u}^{(n)})\to\mathrm{HH}_{1}(\mathbf{K}\mathcal{PG}_{v}^{(n)})$,
in dimension $1$. The $(n,0)$-persistent Betti number for dimension $0$ is
defined analogously.

######  Remark 4.7.

Note that degrees of Hochschild homology are only 0 and 1. The higher
"homological" degrees $n$, and the $n$-th Betti numbers, are defined by the
connectivity digraphs of $n$-simplices. This is in our view the lifting of
Hochschild homology beyond degree 1.

In this functorial framework, given a categorical persistence function $p$ and
a (tame) filtration $\mathcal{F}$, it is possible to define a persistence
diagram $D\mathcal{F}$ as well [8]. In the case of real-indexed filtrations,
the morphisms $u\leq v\in\mathbf{R}$ are in bijection with the positive half-
plane $\Delta^{+}=\\{(u,v)\in\mathbf{R}^{2}\ |\ u\leq v\\}$. We therefore get
an induced persistence function
$p_{\mathcal{F}}\colon\Delta^{+}\rightarrow\mathbf{Z}$ given by $(u,v)\mapsto
p(\mathcal{F}(u\leq v))$. For $u<v$ we define the multiplicity $\mu(u,v)$ as

$\min_{I_{u},I_{v}}\\{p_{\mathcal{F}}(\text{sup}(I_{u}),\text{inf}(I_{v}))-p_{\mathcal{F}}(\text{inf}(I_{u}),\text{inf}(I_{v}))-p_{\mathcal{F}}(\text{sup}(I_{u}),\text{sup}(I_{v}))+p_{\mathcal{F}}(\text{inf}(I_{u}),\text{sup}(I_{v}))\\},$

where $I_{u}$ and $I_{v}$ range over disjoint connected neighborhoods of $u$
and $v$. The persistence diagram $D\mathcal{F}$ associated to
$p_{\mathcal{F}}$ is then defined by those points $(u,v)$ such that
$\mu(u,v)>0$, together with the diagonal $\\{(u,u)\mid u\in[0,\infty)\\}$ [8,
Definition 6]. Note that for small enough neighborhoods $I_{u}$ and $I_{v}$ we
have
$\text{inf}(I_{u})\rightarrow\text{sup}(I_{u})\rightarrow\text{inf}(I_{v})\rightarrow\text{sup}(I_{v})$,
and the above minimized expression is exactly that of condition 2. in
Definition 4.5 with strict inequality.

We get an immediate stability theorem, in fact an isometry theorem, between
our Hochschild homology valued filtrations and their persistence diagrams. Let
$d_{\mathbf{FinVect}}(\mathcal{F},\mathcal{G})$ be the interleaving distance
between two filtrations
$\mathcal{F},\mathcal{G}\colon(\mathbf{R},\leq)\rightarrow\mathbf{FinVect}$
and let $d(D\mathcal{F},D\mathcal{G})$ be the bottleneck distance between the
associated persistence diagrams.

######  Theorem 4.8.

Let $\mathcal{F,G}\colon(\mathbf{R},\leq)\to\mathbf{Digraph}_{0}$ be two
filtrations of digraphs. Then,

$d_{\mathbf{FinVect}}(\mathrm{HH}_{1}\circ\mathbf{K}\mathcal{P}^{(n)}\circ\mathcal{F},\mathrm{HH}_{1}\circ\mathbf{K}\mathcal{P}^{(n)}\circ\mathcal{G})=d(D\mathcal{F},D\mathcal{G})$

where $D\mathcal{F}$ and $D\mathcal{G}$ represent the persistence diagrams
associated to $\mathcal{F}$ and $\mathcal{G}$.

###### Proof.

The proof follows directly from [8, Theorem 3.27 & 3.29]. ∎

The theorem says that the persistent Hochschild homology groups associated to
a filtration of digraphs are stable, one of the required properties in
persistent homology applications. We refer to this as _persistent Hochschild
homology_. Note that in the terminology of [11] we have introduced a
generalised persistence along with a _hard stability theorem_ : the map from
persistence modules to discrete invariants is 1-Lipschitz. This still leaves
open the (very hard) problem of proving a stable persistent Hochschild
homology pipeline starting from the space of (acyclic) digraphs. The main
obstacle here lies in the difficulty of having an appropriate metric for
digraphs that behaves well with filtrations.

Note that persistent Hochschild homology does not behave as the usual
persistent homology; in fact, we have the following:

######  Remark 4.9.

Consider an edge weighted directed graph $\mathcal{G}$, and consider the
filtration induced by sorting the weights in an increasing order – the first
digraph in the sequence being the spanning subgraph on the vertices of
$\mathcal{G}$. Then, generators in persistent Hochschild homology applied to
such filtration always persist until $\infty$. Therefore we cannot talk about
births and deaths as is usually done in the context of barcodes.

Similarly, as for Hochschild homology, we can consider compositions

$(\mathbf{R},\leq)\xrightarrow{\mathcal{F}}\mathbf{Digraph}\xrightarrow{\mathcal{P}^{(n)}}\mathbf{Digraph}\xrightarrow{\mathrm{Ch}\circ\mathrm{dFl}}\mathbf{Ch}\xrightarrow{\mathrm{H}_{n}}\mathbf{Ab}$

involving the homology of directed flag complexes, or the path homology
functors. For $n=0$, these compositions yield the usual persistence homology
in the first case, and the persistent path homology introduced in [19], in the
second. Henceforth, composition with the higher connectivity digraphs allows
us to extend the usual classical pipelines.

###  4.2 A persistent Hochschild homology pipeline for directed graphs

As seen in the previous section, Hochschild homology gives rise to a
persistence function when considering directed graphs without oriented cycles;
however, this approach fails with graphs having oriented cycles, due to
Proposition 2.22. We now introduce a persistence-like framework for Hochschild
homology that extends our set-up to the whole category $\mathbf{Digraph}$.

Our pipeline proceeds as follows:

  1. 1.

We start with a filtration
$\mathcal{F}\colon(\mathbf{R},\leq)\to\mathbf{Digraph}$.

  2. 2.

At each filtration step $t$ we obtain a connectivity digraph
$E\mathcal{F}_{t}$ by applying the $n$-path digraph $\mathcal{P}^{(n)}$ for
some $n$, or the $q$-graph for some $(q,\widehat{d_{i}},\widehat{d_{j}})$.

  3. 3.

The resulting digraphs $E\mathcal{F}_{t}$ can in general have oriented cycles.
We therefore consider the condensation $c(E\mathcal{F}_{t})$ (Definition
1.10).

  4. 4.

By Remark 1.11, $c(E\mathcal{F}_{t})$ does not have oriented cycles. Hence, we
compute the Hochschild characteristic
$\mathcal{X}_{\mathrm{HH}}(c(E\mathcal{F}_{t}))=\dim_{k}\mathrm{HH}_{0}(A)-\dim_{k}\mathrm{HH}_{1}(A)$,
where $A$ is the associated path algebra. Note that
$\dim_{k}\mathrm{HH}_{0}(A)$ agrees with the number of connected components
and $\dim_{k}\mathrm{HH}_{1}(A)$ with the formula $1-n+\sum_{e\in
E(\mathcal{G})}\dim_{k}e_{t(e)}Ae_{s(e)}$ of Theorem 2.25. As the digraph
$c(E\mathcal{F}_{t})$ does not have oriented cycles, this is exactly the
characteristic introduced in Definition 2.29.

Diagrammatically, we have:

$(\mathbf{R},\leq)\xrightarrow{\mathcal{F}}\mathbf{Digraph}\xrightarrow{E}\mathbf{Digraph}\xrightarrow{c}\mathbf{Digraph}_{0}\xrightarrow{k-}k\text{-}\mathbf{Alg}\xrightarrow{\mathcal{X}_{\mathrm{HH}}}\mathbf{FinVect}\
.$ (8)

Note that the process lands in the category of finite vector spaces, but the
composition is not functorial anymore; we refer to the discussion after Remark
1.11.

######  Remark 4.10.

Observe that taking the condensation of a digraph and the connectivity
digraphs do not commute. In particular, killing the cycles in the condensation
process may kill also ordered cliques; this is the reason why we first apply
$E$ and then the condensation $c$.

We demonstrate our persistent Hochschild homology pipeline, by applying it to
the filtrations of the following digraphs:

  * •

Random Erdös–Rényi (ER) digraph with probability 0.5 for directed edges
between any pair of vertices. We make it randomly edge weighted by replacing
each non-zero entry of the adjacency matrix with a value sampled uniformly
from $[0,1)$.

  * •

Random necklace digraph, as represented in Figure 6. Similarly, to make it
random we first construct the associated adjacency matrix, which has ones on
the first upper and lower diagonals, and we then replace these with a value
sampled uniformly from $[0,1)$.

$\bullet$$\bullet$$\bullet$…$\bullet$$\bullet$$\bullet$ Figure 6: The necklace
digraph.

In both examples, we take the digraph filtration induced by the random entries
of the associated adjacency matrices: at a filtration value $t$ we take the
digraph induced by keeping only edges whose weight is $\leq t$. The digraphs
we used had 20 vertices, so were represented by $20\times 20$ adjacency
matrices.

Figure 7 shows the persistent Hochschild characteristics for the random
Erdös–Rényi and necklace digraphs, and for their associated 1-path digraphs.
Figure 8 shows the results for $q$-graphs with
$(q,\widehat{d_{i}},\widehat{d_{j}})$ equal to
$(q,\widehat{d_{0}},\widehat{d}_{q+1})$ for $q\in\\{1,2,3,4\\}$ for the random
Erdös–Rényi, and $(0,\widehat{d_{0}},\widehat{d_{1}})$ for the necklace
digraph.

As observed in Remark 4.9, generators in persistent Hochschild homology always
persist until $\infty$, and therefore the associated Betti curves yield
monotone functions. Experiments involving the persistent Hochschild
characteristics of random ER digraphs, and more structured necklace digraphs –
_cf._ Figure 7 – show instead that the associated curves are not monotone.
This is caused by the condensation step in the pipeline introduced in this
section. Condensation also has the effect of reducing the number of edges and
paths in the graph, a number that is correlated to the first Hochschild
homology group – _cf._ Theorem 2.25. The effect of condensation is seen in the
plots as zig-zagging; particularly large positive jumps correspond to large
cyclic components being killed.

Note that a common feature in all plots is that the early parts of the
filtrations are dominated by the connected components. This occurs until a
certain saturation point in which more structured graphs appear and the number
of edges, paths, and of oriented cycles, is more prominent. It is interesting
to note that this saturation point is reached very soon when dealing with
random digraphs and much later for the necklace digraphs. Essentially this is
observed in the plots when the value of $\mathcal{X}_{\mathrm{HH}}$ drops to
negative. The plots for ER $q$-digraphs also begin slightly positive before
more paths begin to dominate dropping the values very negatively. Exception is
the ER (4,0,5)-digraph: due to the required high-dimensional connecting faces
the digraphs are predominantly rather empty of edges and dominated by
connected components.

When oriented cycles are more likely to be created with long paths, the
variations in $\mathcal{X}_{\mathrm{HH}}$ are stronger. Compare this effect on
the persistent Hochschild characteristics of random ER digraphs and of
necklace digraphs in Figure 7. Necklace digraphs, perturbed with addition of
white noise, present small cycles, so that the persistent Hochschild
characteristics is changing almost linearly. Changing the associated
connectivity digraph may change completely the behaviour of
$\mathcal{X}_{\mathrm{HH}}$. Note the change in the persistent Hochschild
characteristics associated to the line digraphs of the same random and
necklace digraphs.

Finally, we remark that the $\mathcal{X}_{\mathrm{HH}}$ of the $q$-digraphs in
Figure 8 show drastically larger values compared to Figure 7. Recall that
these digraphs have as vertices all the simplices of dimension $\geq q$. The
simplicial face inclusions are also always near resulting in edges (Definition
3.10). Therefore the $q$-digraphs are larger and more dominated by paths along
the filtration. This is particularly visible in the plot for ER
(2,0,3)-digraph.

Figure 7: Persistent Hochschild characteristics. Left: condensed digraph and
condensed $1$-path digraph of a random Erdös–Rényi. Right: condensed digraph
and condensed $1$-path digraph of a random necklace digraph. Both digraphs had
20 vertices.

Figure 8: Persistent Hochschild characteristics. Left: condensed $q$-digraphs
of a random Erdös–Rényi. Right: condensed $q$-digraph of a random necklace
digraph. The choices for $(q,\widehat{d_{i}},\widehat{d_{j}})$ are shown in
the figures. Both digraphs had 20 vertices.

As already mentioned, the pipeline we have introduced uses the condensation of
a digraph to kill the oriented cycles. By producing acyclic digraphs, this
also has an effect in the computational efficiency since many graph
algorithms, for example finding paths, have lower complexity; this was taken
advantage of in [63] in computing $q$-connected pathways of simplices. Other
approaches are possible, for example in [47, Algorithm 1] a Berger and Shor
algorithm [7] has been used for the same task. Using condensation leads to our
pipeline not being functorial, and we do not know if the persistent Hochschild
characteristic defined this way is stable in the sense of Theorem 4.8; this
leaves open the following question:

######  Question 4.11.

Is it possible to modify the composition of Equation (8) in a functorial way?
Is the composition of Equation (8) stable in the sense of Theorem 4.8?

## References

  * [1] R. Aharoni, E. Berger, and R. Meshulam.  Eigenvalues and homology of flag complexes and vector representations of graphs.  Geometric and Functional Analysis, 15:555–566, 2005.
  * [2] R. Atkin.  From cohomology in physics to $q$-connectivity in social science.  International Journal of Man-Machine Studies, 4:139–167, 1972.
  * [3] R. Atkin.  Mathematical Structure In Human Affairs.  Heinemann, London, 1974.
  * [4] J. Barmak.  Algebraic Topology of Finite Topological Spaces and Applications.  Springer, 2011.
  * [5] H.-J. Baues and G. Wirsching.  Cohomology of small categories.  Journal of Pure and Applied Algebra, 38(2):187–211, 1985.
  * [6] P. Bendich, J. Marron, E. Miller, A. Pieloch, and S. Skwerer.  Persistent homology analysis of brain artery trees.  The Annals of Applied Statistics, 10:198–218, 2014.
  * [7] B. Berger and P. W. Shor.  Approximation alogorithms for the maximum acyclic subgraph problem.  In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’90, page 236–243, USA, 1990. Society for Industrial and Applied Mathematics.
  * [8] M. G. Bergomi and P. Vertechi.  Rank-based persistence.  Theory and Applications of Categories, 35:228–260, 2020.
  * [9] M. Brion.  Representations of quivers.  Available at https://www-fourier.ujf-grenoble.fr/~mbrion/notes_quivers_rev.pdf.
  * [10] J. Brodzki, F. Belchí, R. Djukanovic, J. Conway, M. Pirashvili, and M. Bennett.  Lung topology characteristics in patients with chronic obstructive pulmonary disease.  Scientific Reports, 8, 5341, 2018.
  * [11] P. Bubenik, V. de Silva, and J. Scott.  Metrics for generalized persistence modules.  Foundations of Computational Mathematics, 15:1501–1531, 2015.
  * [12] L. Caputi, D. Celoria, and C. Collari.  Categorifying connected domination via graph überhomology.  2022\.  ArXiv:2201.00721.
  * [13] L. Caputi, D. Celoria, and C. Collari.  Monotone cohomologies and oriented matchings.  2022\.  ArXiv:2203.03476.
  * [14] L. Caputi, C. Collari, and S. Di Trani.  Combinatorial and topological aspects of path posets, and multipath cohomology, 2021.  Arxiv:2110.11206.
  * [15] L. Caputi, C. Collari, and S. Di Trani.  Multipath cohomology of directed graphs, 2021.  Arxiv:2108.02690.
  * [16] L. Caputi, A. Pidnebesna, and J. Hlinka.  Promises and pitfalls of topological data analysis for brain connectivity analysis.  NeuroImage, 238:118245, 2021.
  * [17] T. Chaplin.  First betti number of the path homology of random directed graphs, 2021\.  ArXiv:2111.13493.
  * [18] B. Chen, S.-T. Yau, and Y.-N. Yeh.  Graph homotopy and graham homotopy.  Discrete Mathematics, 241(1):153–170, 2001.  Selected Papers in honor of Helge Tverberg.
  * [19] S. Chowdhury and F. Mémoli.  Persistent path homology of directed networks.  Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1152–1169, 2018.
  * [20] M.K. Chung, J.L. Hanson, J. Ye, R.J. Davidson, and S.D. Pollak.  Persistent homology in sparse regression and its application to brain morphometry.  IEEE Transactions on Medical Imaging, 34:1928–1939, 2014.
  * [21] M. G. Citterio.  Classifying spaces of categories and term rewriting.  Theory and Applications of Categories, 9(5):92–105, 2001.
  * [22] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer.  Stability of persistence diagrams.  Discrete and Computational Geometry, 37:130–120, 2007.
  * [23] P. Conceiç$\tilde{\text{a}}$o, D. Govc, J. Lazovskis, R. Levi, H. Riihimäki, and J. Smith.  An application of neighbourhoods in digraphs to the classification of binary dynamics.  To appear in Network Neuroscience, 2021.
  * [24] T. K. Dey, T. Li, and Y. Wang.  An efficient algorithm for $1$-dimensional (persistent) path homology, 2020.  ArXiv:2001.09549.
  * [25] T. K. Dey, S. Mandal, and W. Varcho.  Improved Image Classification using Topological Persistence.  In Matthias Hullin, Reinhard Klein, Thomas Schultz, and Angela Yao, editors, Vision, Modeling and Visualization. The Eurographics Association, 2017.
  * [26] R. Diestel.  Graph theory.  Springer Heidelberg, 2010.
  * [27] J. Dubut, É. Goubault, and J. Goubault-Larrecq.  Natural homology.  In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Automata, Languages, and Programming, pages 171–183. Springer Berlin Heidelberg, 2015.
  * [28] O. Dunaeva, H. Edelsbrunner, A. Lukyanov, M. Machin, D. Malkova, R. Kuvaev, and S. Kashin.  The classification of endoscopy images with persistent homology.  Pattern Recognition Letters, 83:13 – 22, 2016.
  * [29] P. Gabriel and M. Zisman.  Calculus of Fractions and Homotopy Theory.  Springer Berlin Heidelberg, 1967.
  * [30] N. Giansiracusa, R. Giansiracusa, and C. Moon.  Persistent homology machine learning for fingerprint classification.  18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 1219–1226, 2019.
  * [31] M. Gidea.  Topology data analysis of critical transitions in financial networks.  SSRN Electronic Journal, 01 2017.
  * [32] D. Govc, R. Levi, and J. P. Smith.  Complexes of tournaments, directionality filtrations and persistent homology.  Journal of Applied and Computational Topology, 5:313–337, 2021\.
  * [33] R. Grady and A. Schenfisch.  Zig-zag modules: Cosheaves and K-theory.  2021\.  ArXiv:2110.04591.
  * [34] A. Grigorian, R. Jimenez, Y. Muranov, and S.-T. Yau.  On the path homology theory of digraphs and eilenberg–steenrod axioms.  Homology, Homotopy and Applications, 20:179–205, 01 2018.
  * [35] A. Grigorian, Y. Lin, Y. Muranov, and S.-T. Yau.  Cohomology of digraphs and (undirected) graphs.  Asian Journal of Mathematics, 19:887–932, 11 2015.
  * [36] A. Grigor’yan, Y. Lin, Y. Muranov, and S.-T. Yau.  Homologies of path complexes and digraphs, 2013.  ArXiv:1207.2834.
  * [37] A. Grigor’yan, Y. Lin, Y. Muranov, and S.-T. Yau.  Homotopy theory for digraphs, 2014.  ArXiv:1407.0234.
  * [38] A. Grigor’yan, Yong Lin, Y. Muranov, and S.-T. Yau.  Path complexes and their homologies.  Journal of Mathematical Sciences, 248:564–599, 2020.
  * [39] A. Grigor’yan, Y. Muranov, V. Vershinin, and S.-T. Yau.  Path homology theory of multigraphs and quivers.  Forum Mathematicum, 30(5):1319–1337, 2018.
  * [40] A. Grigor’yan, Y. Muranov, and S.-T. Yau.  Homologies of digraphs and künneth formulas.  Communications in Analysis and Geometry, 25(5):969–1018, 2017.
  * [41] D. Happel.  Hochschild cohomology of finite-dimensional algebras.  Lecture Notes in Math, 1404:108–126, 1989.
  * [42] F. Harary and R. Z. Norman.  Some properties of line digraphs.  Rendiconti del Circolo Matematico di Palermo, 9:161–168, 1960.
  * [43] A. Hatcher.  Algebraic topology.  Cambridge University Press, 2000.
  * [44] G. Hochschild.  On the cohomology groups of an associative algebra.  Annals of Mathematics, 46:58–67, 1945.
  * [45] A. V. Ivashchenko.  Contractible transformations do not change the homology groups of graphs.  Discrete Mathematics, 126(1):159–170, 1994.
  * [46] C. Kassel.  Cyclic homology, comodules, and mixed complexes.  Journal of Algebra, 107(1):195–216, 1987.
  * [47] M. Kaul and D. Tamaki.  A Weighted Quiver Kernel using Functor Homology.  arXiv e-prints, 2020.  ArXiv:2009.12928.
  * [48] A. Khalid, B.S. Kim, M.K. Chung, J.C. Ye, and D. Jeon.  Tracing the evolution of multi-scale functional networks in a mouse model of depression using persistent brain network homology.  NeuroImage, 101, 2014.
  * [49] S. Krishnan.  Flow-cut dualities for sheaves on graphs, 2014.  ArXiv:1409.6712.
  * [50] L. Kuang, D. Zhao, J. Xing, Z. Chen, F. Xiong, and X. Han.  Metabolic brain network analysis of fdg-pet in alzheimer’s disease using kernel-based persistent features.  Molecules, 24:2301, 2019.
  * [51] H. Lee, M.K. Chung, H. Kang, B.-N. Kim, and D.S. Lee.  Discriminative persistent homology of brain networks.  Proceedings - International Symposium on Biomedical Imaging, pages 841–844, 03 2011.
  * [52] F. Li and B. Yu.  The geometric realization of regular path complexes via (co-)homology, 2020.  Arxiv:1808.05337.
  * [53] J.-L. Loday.  Cyclic Homology.  Springer Berlin Heidelberg, 1998.
  * [54] D. Lütgehetmann, D. Govc, J. P. Smith, and R. Levi.  Computing persistent homology of directed flag complexes.  Algorithms, 13(1):19, 2020.
  * [55] S. MacLane.  Categories for the Working Mathematician.  Springer-Verlag, 1971.
  * [56] P. Masulli and A.E.P. Villa.  The topology of the directed clique complex as a network invariant.  SpringerPlus, 5(388), 2016.
  * [57] J. R. Munkres.  Elements of Algebraic Topology.  Addison Wesley, 1984.
  * [58] G. Palla, I. Derényi, I. Farkas, and T. Vicsek.  Uncovering the overlapping community structure of complex networks in nature and society.  Nature, 435:814–818, 2005.
  * [59] D. Quillen.  Higher algebraic K-theory: I.  In H. Bass, editor, Higher K-Theories, pages 85–147, Berlin, Heidelberg, 1973. Springer Berlin Heidelberg.
  * [60] J. Redondo.  Hochschild cohomology: some methods for computations.  Resenhas do Instituto do Matemática e Estatística da Universidade de São Paulo, 2, 2001.
  * [61] M. W. Reimann, M. Nolte, M. Scolamiero, K. Turner, R. Perin, G. Chindemi, P. Dłotko, R. Levi, K. Hess, and H. Markram.  Cliques of neurons bound into cavities provide a missing link between structure and function.  Frontiers in Computational Neuroscience, 11, 2017.
  * [62] S. Ren and C. Wang.  Differential algebras on digraphs and generalized path homology.  2021\.  ArXiv:2103.15870.
  * [63] H. Riihimäki.  Simplicial $q$-connectivity of directed graphs with applications to network analysis.  2021\.  ArXiv:2202.07307.
  * [64] B. Schröder.  Ordered Sets, 2ed. Birkhäuser, 2016.
  * [65] P. Turner and E. Wagner.  The homology of digraphs as a generalisation of Hochschild homology.  Journal of Algebra and Its Applications, 11:1250031, 2012.
  * [66] D. B. West.  Introduction to graph theory.  Prentice-Hall, 2005.
  * [67] E. Wong, S. Palande, B. Wang, B. Zielinski, J. Anderson, and P. Fletcher.  Kernel partial least squares regression for relating functional brain network topology to clinical measures of behavior.  IEEE 13th International Symposium on Biomedical Imaging (ISBI), pages 1303–1306, 04 2016.