# One Timestep is all you need: Training Spiking Neural Networks with Ultra
Low Latency

Sayeed Shafayet Chowdhury, Nitin Rathi & Kaushik Roy
School of Electrical and Computer Engineering
Purdue University
West Lafayette, IN 47905, USA
<EMAIL_ADDRESS>

###### Abstract

Spiking Neural Networks (SNNs) are energy efficient alternatives to commonly
used deep neural networks (DNNs). Through event-driven information processing,
SNNs can reduce the expensive compute requirements of DNNs considerably, while
achieving comparable performance. However, high inference latency is a
significant hindrance to the edge deployment of deep SNNs. Computation over
multiple timesteps not only increases latency as well as overall energy budget
due to higher number of operations, but also incurs memory access overhead of
fetching membrane potentials, both of which lessen the energy benefits of
SNNs. To overcome this bottleneck and leverage the full potential of SNNs, we
propose an Iterative Initialization and Retraining method for SNNs (IIR-SNN)
to perform single shot inference in the temporal axis. The method starts with
an SNN trained with T timesteps (T$>$1). Then at each stage of latency
reduction, the network trained at previous stage with higher timestep is
utilized as initialization for subsequent training with lower timestep. This
acts as a compression method, as the network is gradually shrunk in the
temporal domain. In this paper, we use direct input encoding and choose T=5,
since as per literature, it is the minimum required latency to achieve
satisfactory performance on ImageNet. The proposed scheme allows us to obtain
SNNs with up to unit latency, requiring a single forward pass during
inference. We achieve top-1 accuracy of 93.05%, 70.15% and 67.71% on CIFAR-10,
CIFAR-100 and ImageNet, respectively using VGG16, with just 1 timestep. In
addition, IIR-SNNs perform inference with 5-2500X reduced latency compared to
other state-of-the-art SNNs, maintaining comparable or even better accuracy.
Furthermore, in comparison with standard DNNs, the proposed IIR-SNNs provide
25-33X higher energy efficiency, while being comparable to them in
classification performance. 111Our code will be made publicly available at
https://github.com/SayeedChowdhury/IIR-SNN

##  1 Introduction

Deep neural networks (DNNs) have revolutionized the fields of object
detection, classification and natural language processing [1, 2, 3],
surpassing even human level performance. However, such performance boost has
been achieved at the cost of extremely energy-intensive DNN architectures [4].
Therefore, edge deployment of such DNNs remains a challenge, requiring
specialized architectures and training schemes [5]. One approach to counter
this is adopting model compression techniques such as pruning [6, 7], and data
quantization [8]. An alternative route for efficient computation is using
Spiking Neural Networks (SNNs) [9, 10], which are bio-inspired learning
frameworks and perform computations using binary spikes instead of analog
activations used in standard networks. In this paper, standard networks are
referred to as Analog Neural Networks (ANNs), while SNNs operate using spiking
inputs. As such, the sparse event-driven nature of SNNs make them an
attractive alternative to ANNs [11], specially for resource-constrained
machine intelligence.

SNNs derive their energy efficiency primarily from the sparsity of computation
at any given timestep and by substituting multiply–accumulate (MAC) operations
in ANNs with additions. However, ANNs and current SNNs differ in terms of
number of forward passes required for each input; ANNs infer in a single shot,
whereas SNNs require computation over multiple timesteps, resulting in high
inference latency. The requirement of multi-timestep processing causes
threefold challenges in SNNs in terms of edge deployment- (i) too long latency
might be unsuitable for real-time applications, (ii) accumulation of spikes
over timesteps results in higher number of operations, thereby reducing
efficiency, and (iii) accumulated neuronal membrane potentials of previous
steps are used for computation at each timestep which adds the requirement of
additional memory to store the intermediate potentials as well as the
expensive memory access cost to the total power budget. As a result, reduction
of inference latency while maintaining performance is a critical research
problem in SNNs. Again, surrogate-gradient based SNN training with multiple
timesteps is performed using backpropagation through time (BPTT) [12], similar
to Recurrent Neural Networks (RNNs), with membrane potential holding the
internal state having recurrent connections. However, DNN topologies indicate
that for static image classification tasks, recurrent connections are not
required, rather feed-forward networks are enough to reach convergence. This
motivates us to explore the possibility of obtaining SNNs where inference is
performed with just one forward pass.

Currently, most of the commonly used SNNs use Poisson rate coding [13, 14],
where the firing rate of the spiking neuron approximates the analog activation
of corresponding ANN unit. This scheme provides comparable results to full
precision ANNs, however it suffers from high inference latency [14, 15]. In
rate-coding, the discretization error caused by representing analog values
with spike-train is inversely proportional to the number of timesteps. Hence,
a large number of timesteps is usually adopted to obtain high performance
[14]. As such, it is a challenge to reduce latency considerably without
sacrificing performance degradation. On the other hand, with multiple timestep
computation, the total energy consumption increases significantly due to the
costly memory access operations for fetching membrane potentials. Though most
of the previous SNN works ignore it and consider the computational cost only,
the memory access cost can in fact be orders of magnitude higher compared to
floating point arithmetic operations [16]. This bottleneck can be overcome if
SNNs can be trained to infer in one timestep, no longer requiring the excess
memory access operations due to membrane potential. To that effect, our goal
here is to reduce latency all the way up to unity (lowest limit) without
hampering accuracy significantly.

In this paper, we propose an iterative training scheme to reduce the latency
requirement of SNNs. We adopt the hybrid method [17], so, first an ANN is
trained, followed by ANN-SNN conversion and SNN domain training with
backpropagation. The scheme utilizes direct input encoding [18, 19], since it
has enabled training SNNs with 5-6 timesteps only. The threshold of neurons at
each layer is a learnable parameter in our method. Starting with an SNN
trained with 5 timestep, we gradually reduce latency by iterative retraining.
At each timestep reduction stage, the network trained at previous iteration
with higher timestep is utilized as initialization for subsequent training
with lower timestep. Direct transition from ANN or 5 timestep SNN to 1
timestep for deep SNNs results in training failures due to spike vanishing at
the deeper layers. However, the proposed iterative process enables some spike
propagation till the final layer through which backpropagation can start
training and proper layerwise thresholds can be learnt for each corresponding
timestep. This method gradually compresses the temporal axis of SNNs, since
reduction of each timestep removes one forward pass from the computational
graph.

To summarize, the main contributions of this work are as follows,

  * •

We present an iterative training technique to obtain deep SNNs which infer
using a single timestep, which to the best of our knowledge, is the first SNN
method to achieve competitive classification performance on ImageNet using
unit timestep.

  * •

Since inference is done in one timestep (single forward pass), our approach
does not require the memory access cost of membrane potentials, unlike
previously proposed SNNs.

  * •

The proposed IIR-SNNs are able to infer with 5-2500X lower timesteps compared
to other state-of-the-art SNNs, while achieving comparable or even better
accuracy.

  * •

1 timestep inference also provides ultra-efficient computation due to low
spike rate, resulting in SNNs which are 25-33X energy efficient compared to
iso-architecture and iso-performing ANNs.

  * •

The proposed sequential training scheme enables obtaining deep-Q network based
reinforcement learning agents using SNN on Cartpole and Atari pong
environments which infer using 1 timestep.

##  2 Related Works

ANN-SNN Conversion. A widely used approach of obtaining deep SNNs involves
training an ANN and converting to SNN for finetuning [20, 13, 14]. To minimize
conversion loss, the ANNs are usually trained without bias, batch-norm or
maxpooling layers, though some works bypass these constraints using custom
layers [21]. Proper layerwise threshold adjustment is critical to convert ANNs
to SNNs successfully. One approach of threshold balancing is to choose the
layerwise thresholds as the maximum pre-activation of the neurons [14]. While
this provides high accuracy, the associated drawback is high inference latency
(about 1000 timesteps). Alternatively, [21] suggest choosing a certain
percentile of the pre-activation distribution as the threshold to reduce
inference latency and improve robustness. However, these conversion based
methods [21, 15] still require few hundred timesteps to perform
satisfactorily.

Backpropagation from Scratch and Hybrid Training. An alternate route of
training SNNs with reduced latency is learning from scratch using
backpropagation (bp). To circumvent the challenge posed by non-
differentiability of the spike function, surrogate gradient based optimization
has been proposed [12] to implement bp in SNNs effectively [22, 23]. [24]
propose surrogate gradient based bp on the membrane potential, while [25]
perform bp based on the gradients calculated using the difference between the
membrane potential and the threshold, but results seem limited to MNIST using
shallow architectures. [26] also perform backpropagation through time (BPTT)
on SNNs with a surrogate gradient defined on the continuous-valued membrane
potential. Overall, surrogate-gradients based BPTT training has resulted in
SNNs with high accuracy, but the training is very compute intensive compared
to conversion techniques and the latency is still significant ($\sim$100-125
timesteps). [17] propose a hybrid approach where a pre-trained ANN is used as
initialization for subsequent surrogate gradient SNN learning. This hybrid
approach improves upon conversion by reducing latency and speeds up
convergence of direct bp from scratch method.

Temporal Encoding. A different approach to train SNNs is based on the timing
of spike of neurons. Temporal coding schemes such as phase [27] or burst [28]
coding attempt to capture temporal information into the spike trains, but
incur high latency and large number of spikes. A related method is time-to-
first-spike (TTFS) coding [29, 30], where each neuron is allowed to spike just
once but the high latency persists. [31] propose using relative timing of
spikes to encode information, but only report results for simple tasks like
MNIST and its scalability to deeper architectures and more complex datasets
remains unclear. Notably, since our proposed scheme enables one step
inference, the neurons are automatically limited to maximum one spike per
neuron, however our latency is significantly lower.

Direct Encoding. The analog pixels are directly applied to the 1st
convolutional layer in direct encoding [21, 32, 18, 19]. Using this method,
[18] achieve competitive performance on ImageNet using just 5 timesteps.
Again, threshold-dependent batch normalization is employed together with
direct encoding by [19] to obtain high performing SNNs with 6 timesteps only.
Inspired by such promising performance, we adopt the direct encoding method in
this work.

##  3 Background

Spiking Neuron Model The Leaky Integrate and Fire (LIF) SNN model [33] is
described as-

$\tau_{m}\frac{dU}{dt}=-(U-U_{rest})+RI,~{}~{}~{}~{}U\leq V_{th}$ (1)

where $U$, $I$, $\tau_{m}$, $R$, $V_{th}$ and $U_{rest}$ denote membrane
potential, input representing weighted sum of spikes, time constant for
membrane potential decay, leakage path resistance, firing threshold and
resting potential, respectively. We employ a discretized version of Eqn. 1
given as-

$u_{i}^{t}=\lambda_{i}u_{i}^{t-1}+\sum_{j}w_{ij}o_{j}^{t}-v_{i}o_{i}^{t-1},$
(2)
$z_{i}^{t-1}=\frac{u_{i}^{t-1}}{v_{i}}~{}~{}~{}\text{and}~{}~{}~{}o_{i}^{t-1}=\left\\{\begin{array}[]{ll}1,~{}~{}~{}\text{if}~{}u_{i}^{t-1}>v_{i}\\\
0,~{}~{}~{}\text{otherwise}\end{array}\right.$ (3)

where $u$ is the membrane potential, subscripts $i$ and $j$ represent the post
and pre-neuron, respectively, t denotes timestep, $\lambda$ is the leak
constant= $e^{\frac{-1}{\tau_{m}}}$, $w_{ij}$ represents the weight between
the i-th and j-th neurons, $o$ is the output spike, and $v$ is the threshold.
As indicated by Eqn. 2, we implement a soft-reset, so, $u$ is reduced by $v$
upon crossing the threshold. The details of training SNN with a certain
inference timestep is provided in appendix section A.1. In particular,
Algorithm 2 depicts the training scheme for one iteration. We also train the
thresholds and leaks using bp; the implementation is publicly available at
https://github.com/SayeedChowdhury/IIR-SNN.

Figure 1: (a) Schematic of an SNN with dynamics shown for yellow neuron with x
as input and y as output, (b) No output spike for direct transition from 5 to
1 timestep, (c) Output spike in just 1 timestep through $V_{th}/w$ lowering,
(d) Layerwise spike rates, Tx represents a converged SNN with ‘x’ timestep,
Tx_y represents an SNN with ‘x’ timestep initialized with a ‘y’ timestep
trained SNN.

##  4 Proposed Latency Reduction Method

The starting point of our training pipeline follows the proposed methodology
in [18], difference being we utilize batch-norm (bn) during ANN training and
subsequently the bn parameters are fused with the layerwise weights as done in
[21]. With this pretrained ANN, the weights are copied to an iso-architecture
SNN and we select the 90.0 percentile of the pre-activation distribution at
each layer as its threshold. Then the SNN is trained for 5 timesteps using bp
which serves as our baseline; training steps are detailed in Algorithm 2. Our
starting point is chosen as a 5 timesteps trained network, since it is lowest
latency that previous works have reported for SNN ImageNet training [18, 19]
with high performance. Going below 5 results in convergence failure due to
spike vanishing at deeper layers.

Direct Inference with Unit Timestep. As mentioned in Section 1, our goal is to
obtain SNNs with unit latency to harness the maximum efficiency possible. To
that effect, next we explore the feasibility of directly reducing latency from
5 to 1. Fig. 1(a) schematically depicts an SNN with 3 neurons (one per layer),
we focus on the yellow neuron. Suppose it receives x as input and y is its
output. With the weight (w) and threshold (V${}_{\text{th}}$) trained for 5
timesteps, there is enough accumulation of membrane potential
(V${}_{\text{mem}}$) to cross V${}_{\text{th}}$ and propagate spikes to next
layer within that 5 timestep window. However, when we try to perform inference
with 1 timestep (Fig. 1(b)), there is no output spike as the
V${}_{\text{mem}}$ is unable to reach V${}_{\text{th}}$ instantly. So, the w
and V${}_{\text{th}}$ need to be adjusted such that information can propagate
even within 1 step. However, balancing the thresholds properly is critical for
SNNs to perform well. If V${}_{\text{th}}$ is too high, spikes vanish, but
lowering V${}_{\text{th}}$ too much results in too many spikes, leading to
unsatisfactory performance [19]. Hence, our goal is adjusting
V${}_{\text{th}}$/w through learning using bp, so that only neurons salient
for information propagation are able to spike in 1 timestep (Fig. 1(c)), while
other neurons remain dormant.

Direct Transition to Training with Unit Timestep. Next, we begin training with
1 timestep initialized with the 5 timestep trained SNN, however, the network
fails to train. To investigate this, we plot the layerwise spike rates for a
VGG16 on CIFAR10 in Fig. 1(d). For the rest of this paper, with Tx and Tx_y,
we denote converged SNN with ‘x’ timestep and an SNN with ‘x’ timestep
initialized with a ‘y’ timestep trained SNN, respectively. While T5 has
sufficient spiking activity till final layer, for T1_5, spikes die out in the
earlier layers. Due to such spike vanishing, all outputs at the end layer are
0, thus bp cannot start training. Again, this happens since the initial
V${}_{\text{th}}$ and w are trained for 5 timesteps, so the drastic transition
to 1 timestep hinders spikes to propagate till the end.

Gradual Latency Reduction. To mitigate the above issue, we adopt a gradual
latency reduction approach. We observe that for T3_5, though layerwise spike
activity decays significantly, there is still some spikes that reach the final
layer. So, we start training with 3 timesteps using T5 as initialization and
training is able to converge through bp. The spiking activity is recovered
when learning converges as shown in Fig. 1(d), case T3. Subsequently, we train
a network with just 1 timestep by initializing it with T3, and successfully
attain convergence. The results for this case is shown as T1 in Fig. 1(d).
Motivated by these observations, we propose an Iterative Initialization and
Retraining method for training SNNs with lowest possible latency (1 timestep),
abbreviated as IIR-SNN.

Algorithm 1 Pseudo-code for IIR-SNN training.

Input: Trained SNN with $N$ timesteps ($TN$), timesteps reduced per reduction
step ($x$), number of epochs to train ($e$)

Initialize: new SNN initialized with trained parameters of $TN$, reduced
latency $T_{r}=N-x$

while $T_{r}>0$ do

// Training Phase

for $epoch\leftarrow 1$ to $e$ do

//Train network with $T_{r}$ timesteps using algorithm 2

end for

// Initialize another iso-architecture SNN with parameters of above trained
network

// Timestep reduction

$T_{r}=T_{r}-x$

end while

A pseudo-code of IIR-SNN training is given in Algorithm 1. Beginning with T5,
we gradually reduce the latency by 1 at each step and train till convergence.
While training with a certain latency, the network is initialized with the
higher timestep network trained at previous training stage.

Latency Reduction as Form of Compression. SNNs with multiple timesteps are
trained with BPTT [12], like RNNs. If we unroll SNNs in time, it becomes
obvious that each timestep adds a hidden state to a spiking neuron. Thus,
reducing latency compresses the SNNs in the temporal axis and the eventual
unit timestep network consists of a single forward pass, with no internal
states. From a related perspective, we can perceive gradual latency reduction
as sequential temporal distillation, where at each step, the network with
higher timesteps acts as the teacher, while the student network with reduced
latency learns from it. Similar sequential distillation (training by
generations) has been implemented in ANNs [34, 35] to obtain better performing
students. However, in our case, there is no explicit distillation loss and the
sequential training is a requirement for convergence instead of being just a
performance enhancement tool. Also, unlike ANN sequential distillation, the
student architecture remains same spatially throughout all generations in the
proposed method and compression occurs in the temporal domain of SNNs.

##  5 Experiments and Results

Datasets and Models. We perform experiments on CIFAR10, CIFAR100 and ImageNet
using VGG16 and ResNet20 architectures. Some small scale studies involve VGG6.
We also investigate the performance of the proposed IIR-SNN in reinforcement
learning (RL) applications using Cartpole and Atari-pong. Appendix A.2
includes architectural details and training hyperparameters.

Results on CIFAR and ImageNet. The experimental results using the proposed
IIR-SNN scheme for CIFAR and ImageNet datasets are shown in Table 1. We
achieve top-1 accuracy of 93.05% and 70.15% on CIFAR-10 and CIFAR-100,
respectively using VGG16 architecture, with just 1 timestep (T1); results
using ResNet20 are shown too. Next, to investigate the scalability of the
proposed algorithm, we experiment with ImageNet where we obtain 67.71% top-1
accuracy with T1. As we sequentially reduce the timestep from 5 to 1, there is
a slight accuracy degradation, however that is due to the inherent accuracy
versus latency trade-off in SNNs. Notably, the proposed scheme allows us to
bring the SNN latency down to lowest possible limit (1 timestep) while
maintaining comparable accuracy to corresponding ANN as well as the 5 timestep
SNN. Additionally, this provides the option to choose the SNN model suitable
for application in hand from a range of timesteps; if latency and efficiency
is the priority, T1 would be preferred, albeit with slightly lower accuracy
compared to T5.

Table 1: Top-1 classification accuracy (%) using IIR-SNN, Tx denotes SNN with ‘x’ timestep Architecture | Dataset | ANN | T5 | T4 | T3 | T2 | T1
---|---|---|---|---|---|---|---
VGG6 | CIFAR10 | 91.59 | 90.61 | 90.52 | 90.40 | 90.05 | 89.10
VGG16 | CIFAR10 | 94.10 | 93.90 | 93.87 | 93.85 | 93.72 | 93.05
ResNet20 | CIFAR10 | 93.34 | 92.62 | 92.58 | 92.56 | 92.11 | 91.10
VGG16 | CIFAR100 | 72.46 | 71.58 | 71.51 | 71.46 | 71.43 | 70.15
ResNet20 | CIFAR100 | 65.90 | 65.57 | 65.37 | 65.16 | 64.86 | 63.30
VGG16 | ImageNet | 70.08 | 69.05 | 69.03 | 69.01 | 68.62 | 67.71

Performance Comparison. Next, we compare our performance with different state-
of-the-art SNNs in Table 2. IIR-SNN performs better than or comparably to all
these methods, while achieving significantly lower inference latency. In
particular, note that previously it was challenging to obtain satisfactory
performance with low latency on ImageNet, with lowest reported latencies of 5
[18] and 6 [19]. In contrast, we report 67.71% top-1 accuracy on ImageNet
using T1. Again, [36] achieve 90.53% accuracy on CIFAR-10 using 12 timesteps
with direct input encoding (similar to IIR-SNN), but the proposed method
enables us to obtain 93.05% accuracy on CIFAR-10 using T1. For CIFAR100, [18]
report 69.67% accuracy with 5 timesteps, whereas IIR-SNN achieves 70.15% with
T1. Overall, IIR-SNN demonstrates 5-2500X improvement in inference latency
compared to other works while maintaining iso or better classification
performance. Table 2 also demonstrates the continuum of training SNNs from
ANN-SNN conversion to T1 IIR-SNN. Initial ANN-SNN conversion methods required
latency on the order of thousands [14, 33]. Surrogate-gradient based bp [36,
23] reduced it to few tens to hundred, but scaling up to ImageNet was
challenging. Hybrid training [17] combined these two methods to bring the
latency down to few hundreds. Subsequently, direct input encoding enabled
convergence on ImageNet with latency of $\sim 5$ [18, 19]. The proposed IIR-
SNN method leverages all these previously proposed techniques and improves
upon them by incorporating the sequential reduction approach to obtain unit
latency. We also achieve better performance compared to different SNN encoding
schemes such as TTFS [30], phase [27], burst [28]; detailed comparison is
provided in Appendix section A.3.

Table 2: Comparison of IIR-SNN to other reported results. SGB, hybrid and TTFS denote surrogate-gradient based backprop, pretrained ANN followed by SNN fine-tuning, and time-to-first-spike scheme, respectively and (qC, dL) denotes an architecture with q conv layers and d linear layers. Reference | Dataset | Training | Architecture | Accuracy(%) | Timesteps
---|---|---|---|---|---
[33] | CIFAR10 | Conversion | 2C, 2L | 82.95 | 6000
[20] | CIFAR10 | Conversion | 3C, 2L | 77.43 | 400
[14] | CIFAR10 | Conversion | VGG16 | 91.55 | 2500
[23] | CIFAR10 | SGB | VGG9 | 90.45 | 100
[21] | CIFAR10 | Conversion | 4C, 2L | 90.85 | 400
[17] | CIFAR10 | Hybrid | VGG9 | 90.5 | 100
[30] | CIFAR10 | TTFS | VGG16 | 91.4 | 680
[28] | CIFAR10 | Burst-coding | VGG16 | 91.4 | 1125
[27] | CIFAR10 | Phase-coding | VGG16 | 91.2 | 1500
[26] | CIFAR10 | SGB | 2C, 2L | 50.7 | 30
[36] | CIFAR10 | SG | 5C, 2L | 90.53 | 12
[37] | CIFAR10 | Tandem Learning | 5C, 2L | 90.98 | 8
[38] | CIFAR10 | SGB | 5C, 2L | 91.41 | 5
[18] | CIFAR10 | Hybrid | VGG16 | 92.70 | 5
[19] | CIFAR10 | STBP-tdBN | ResNet-19 | 93.16 | 6
This work | CIFAR10 | IIR-SNN | VGG16 | 93.05 | 1
[32] | CIFAR100 | Conversion | VGG15 | 63.2 | 62
[17] | CIFAR100 | Hybrid | VGG11 | 67.9 | 125
[30] | CIFAR100 | TTFS | VGG16 | 68.8 | 680
[28] | CIFAR100 | Burst-coding | VGG16 | 68.77 | 3100
[27] | CIFAR100 | Phase-coding | VGG16 | 68.6 | 8950
[18] | CIFAR100 | Hybrid | VGG16 | 69.67 | 5
This work | CIFAR100 | IIR-SNN | VGG16 | 70.15 | 1
[14] | Imagenet | Conversion | VGG16 | 69.96 | 2500
[21] | Imagenet | Conversion | VGG16 | 49.61 | 400
[17] | Imagenet | Hybrid | VGG16 | 65.19 | 250
[37] | Imagenet | Tandem Learning | AlexNet | 50.22 | 10
[32] | Imagenet | Conversion | VGG15 | 66.56 | 64
[18] | Imagenet | Hybrid | VGG16 | 69.00 | 5
[19] | Imagenet | STBP-tdBN | ResNet-34 | 67.05 | 6
This work | Imagenet | IIR-SNN | VGG16 | 67.71 | 1

Inference Efficiency. Next, we compare the energy efficiency of IIR-SNNs with
ANNs and multi-timestep SNNs. In SNNs, the floating-point (FP) additions
replace the FP MAC operations. This results in higher compute efficiency as
the cost of a MAC ($4.6pJ$) is $5.1\times$ to an addition ($0.9pJ$) [39] in
45nm CMOS technology (as shown in Fig. 2(e)). Appendix A.4 contains the
equations of computational cost in the form of operations per layer in an ANN,
$\\#\text{ANN}_{\text{ops}}$. For IIR-SNN, the number of operations is given
as $\\#\text{IIR-SNN}_{\text{ops, q}}=\text{spike
rate}_{\text{q}}\times\\#\text{ANN}_{\text{ops, q}};$ spike
rate${}_{\text{q}}$ denoting the average number of spikes per neuron per
inference over all timesteps in layer q. The layerwise spike rates across T5
to T1 are shown in Fig. 2(a-c). Note, the spike rates decrease significantly
with latency reduction from 5 to 1, leading to considerably lower operation
count in T1 compared to T5. The overall average spike rates using T1 for
CIFAR-10, CIFAR-100 and ImageNet on VGG16 are 0.13, 0.15 and 0.18,
respectively; all significantly below 5.1 (relative cost of MAC to addition),
indicating the energy benefits of IIR-SNN over the corresponding ANN. The
first layer with direct input encoded SNNs receive analog inputs, hence the
operations are same as an ANN at this layer. Considering it, we compute the
compute energy benefits of IIR-SNN over ANN, $\alpha$ as ,

$\alpha=\frac{\text{E}_{\text{ANN}}}{\text{E}_{\text{IIR-
SNN}}}=\frac{\sum_{q=1}^{L}\\#\text{ANN}_{\text{ops,q}}*4.6}{\\#\text{IIR-
SNN}_{\text{ops,1}}*4.6+\sum_{q=2}^{L}\\#\text{IIR-
SNN}_{\text{ops,q}}*0.9}.\vspace{-2mm}$ (4)

The values of $\alpha$ for different datasets and architectures are given in
Fig. 2(d). For VGG16, we obtain $\alpha$ of 33.0, 29.24 and 24.61 on CIFAR-10,
CIFAR-100 and ImageNet, respectively. Besides compute energy, another
significant overhead in SNNs occurs due to memory access costs which can be
2-3 orders of magnitude higher [16] compared to FP adds as shown in Fig. 2(e).
In multi-timestep SNNs, weights and membrane potentials have to be fetched at
every timestep, incurring significant data movement cost. However, most
previous works [30, 18, 19, 17] did not consider this cost while comparing the
energy benefits of SNN to ANN. To obtain a fairer comparison, we analyze the
costs taking the memory access issue into consideration. For multi-timestep
SNNs, in addition to the weights, V${}_{\text{mem}}$ needs to be stored and
fetched at each timestep for all neurons, unlike ANNs. However, the memory
requirements for T1 SNNs are same as ANNs; T1 SNNs neither require any extra
memory to store V${}_{\text{mem}}$ for future timesteps, nor do they have any
extra memory accesses compared to ANNs as inference is single shot. The actual
improvements in energy due to this depends on the hardware architecture and
system configurations. Hence, we compare the reduction in terms of number of
memory access. For a VGG16, the proposed T1 reduces the number of memory
accesses by 5.03$\times$ compared to [18]. More generally, our scheme reduces
the number of memory accesses by approximately T$\times$ compared to an SNN
trained with T timesteps.

Figure 2: Layerwise spike rates for a VGG16 across T5 to T1 (average spike rate in parenthesis) on (a) CIFAR10, (b) CIFAR100, (c) ImageNet, (d) relative cost of compute between ANN and T1, (e) operation-wise energy consumption in 45nm CMOS technology [39]. Table 3: Comparison of IIR-SNN to ANNb Reference | Dataset | Accuracy(%)
---|---|---
[40] | CIFAR10 | 89.6
[41] | CIFAR10 | 85.2
[42] | CIFAR10 | 91.88
IIR-SNN | CIFAR10 | 93.05
[42] | CIFAR100 | 70.43
IIR-SNN | CIFAR100 | 70.15

Comparison with binary activated ANNs. A key distinction between ANNs and SNNs
is the notion of time, however, T1 IIR-SNN and ReLU activated ANN both infer
in single shot, difference being the neuronal functionality and output
precision. This difference reduces further with ANNs using binary activations
(ANNb) which also have 0/1 output, like SNNs. Thus, it is interesting to
compare the performance of T1 IIR-SNN and ANNb which is the focus of Table 3.
We observe that IIR-SNN outperforms other ANNb approaches in most cases; our
results are slightly lower on CIFAR100 compared to [42], however in their
case, the ANN ReLU output is thresholded to saturate at 2, but the values are
still analog. Note, in all cases, weights are full precision.

Efficacy of IIR-SNN with shallow networks. As mentioned in section 4, gradual
training is required due to spike vanishing at later layers for deep SNNs if
direct transition from T5 to T1 is attempted. However, for shallow networks,
if there is some propagation of spikes till the end, training with T1
following direct conversion from ANN might be possible. To validate this, we
experiment with a VGG6 on CIFAR10 and the results are shown in Table 5. In
this table, VGG6g denotes networks trained with gradual latency reduction and
VGG6d denotes networks directly converted from ANN and trained using that
particular timestep, so the result in the last row of Table 5 is obtained by
converting an ANN to SNN and directly training with 1 timestep. We observe
that proposed gradual training scheme provides slightly higher accuracy
compared to direct training in case of shallower networks, though it increases
the training overhead. This is consistent with ANN domain results [34, 6],
where the authors achieve better performing networks using sequential model
compression compared to direct compression.

IIR-SNN with and without batch-norm. Recent works have achieved low latency by
adopting batch-normalization (bn) suitably in SNNs [19, 43]. To disentangle
the effect of bn from the proposed gradual latency reduction scheme and ensure
that achieving convergence with 1 timestep is orthogonal to using bn, we
perform ablation studies as shown in Table 5. For both CIFAR10 and CIFAR100,
IIR-SNN enables training with T5 to T1 irrespective of using bn during ANN
training. Using bn enhances accuracy, but sequential latency reduction can be
performed independently from it. Also, [19] report that using threshold-
dependent bn allows reducing latency up to a minimum of 6 timesteps, but IIR-
SNN can go up to 1. Note, in IIR-SNN, bn is used only during ANN training and
the bn parameters are fused with the weights during ANN-SNN conversion as
proposed in [21]; bn is not used in SNN domain training, so the activations at
each layer output remain binary.

Table 4: Effect of IIR on VGG6 with CIFAR10 T | VGG6g(%) | VGG6d(%)
---|---|---
5 | 90.61 | 90.15
4 | 90.52 | 90.08
3 | 90.40 | 89.91
2 | 90.05 | 89.35
1 | 89.10 | 88.64

Table 5: Accuracy(%) of IIR-SNN with VGG16, D_bn and D_nbn denote dataset D with and without batch-norm respectively T | CIFAR10_bn | CIFAR10_nbn | CIFAR100_bn | CIFAR100_nbn
---|---|---|---|---
5 | 93.90 | 92.15 | 71.58 | 69.86
4 | 93.87 | 91.95 | 71.51 | 69.84
3 | 93.85 | 91.90 | 71.46 | 69.76
2 | 93.72 | 91.88 | 71.43 | 69.30
1 | 93.05 | 91.03 | 70.15 | 67.76

Skipping intermediate latency reduction steps. Since the proposed IIR-SNN
scheme increases training overhead due to sequential retraining, it is worth
investigating if this cost can be reduced by skipping in between latency
reduction steps. To that effect, we experiment with 2 cases- (i) training T5
followed by T3_5, followed by T1_3, (ii) IIR-SNN including all intermediate
latencies with the sequence- T5, T4_5, T3_4, T2_3 and T1_2. Interestingly,
both these cases perform comparably; for CIFAR10, we obtain 93.01% and 93.05%
accuracy, respectively with 1 timestep for cases (i) and (ii). Again, these
values for CIFAR100 are 69.92% and 70.15%, respectively, indicating if the end
goal is obtaining T1 SNN, training overhead can be reduced by skipping
intermediate steps. However, in this paper, we report the whole spectrum of
accuracy-latency trade-off from T5 to T1.

Is training following direct conversion from ANN with T1 thresholds feasible?
As mentioned above, a limitation of IIR-SNN is extra training overhead. Though
it does not affect our primary goal (inference efficiency) , it would be
better if direct conversion from ANN to T1 would be feasible. This is
challenging due to layerwise spike decay as discussed in detail in section 4.
In this part, we revisit this from a different angle. First, we obtain the
layerwise V${}_{\text{th}}$ for T1 using IIR-SNN. Then, using this set of
V${}_{\text{th}}$, we convert a VGG16 ANN to SNN, on CIFAR10 and CIFAR100 to
investigate whether these thresholds trained for T1 can enable direct training
with T1 following ANN-SNN conversion. However, training failure occurs in this
case too, since during IIR-SNN T1 training, the weights (w) get modified in
addition to the thresholds, and layerwise spike propagation depends on both
V${}_{\text{th}}$ and w. Even if training converged in this case, the
challenge would remain how to obtain the suitable V${}_{\text{th}}$ for T1
without IIR, however it would indicate the existence of deep T1 SNNs which can
be trained by ANN-SNN conversion followed by direct SNN domain T1 training.
But in our experiments, we are unable to find such networks, further
validating the need of IIR method.

IIR-SNN with magnitude based weight pruning. With T1 IIR-SNN, we can obtain
maximum compression possible in the temporal domain of SNNs, as 1 forward pass
is the minimum for any network to produce output. Additionally, we hypothesize
that T1 networks might be amenable to spatial pruning as there is significant
redundancy in the layerwise weights of DNNs [6, 16]. To investigate this, we
perform experiments on T1 with magnitude based weight pruning [16]. Our result
indicate that we can remove 90% of the total weights of a VGG16 without large
drop in performance. Using VGG16 (T1), we obtain 91.15% accuracy on CIFAR10
and 68.20% accuracy on CIFAR100, while retaining just 10% of the spatial
connections. This provides evidence that spatial pruning techniques can be
combined with T1 IIR-SNNs to achieve holistic spatio-temporal compression,
albeit with a slight hit to classification accuracy.

Figure 3: Average reward (errorbars depict mean$\pm$std), using DQN with ANN
and IIR-SNN- (a) on Cartpole and (b) Atari Pong, (c) layerwise spike rate with
IIR-SNN DQN (T1) on Atari Pong.

Reinforcement learning (RL) with IIR-SNN. Due to their inherent recurrence,
SNNs with multiple timesteps might be more useful in sequential decision-
making (such as RL tasks) than static image classification. However,
application of SNNs in RL may be limited if the latency is too high, since the
agent has to make decisions in real-time. [44] obtain high performing RL
agents on Atari games with SNNs, but with 500 timesteps. Hence, in this
section, we investigate if IIR-SNN technique can enable training SNNs for RL
tasks with low latency. Experiments are performed using SNN based deep
Q-networks (DQN) [45] on cartpole and Atari pong environments. As shown in
Fig. 3(a) and (b), for both cases, we can train SNNs up to 1 timestep. The
rewards are obtained by averaging over 20 trials and plotted with errorbars
showing mean$\pm$std. In (a), the reward is the duration of the cartpole
remaining balanced; DQN with ANN, SNN(T1) and SNN(T3) achieve 40.3$\pm$4.8,
38.7$\pm$5.4, 52.2$\pm$4.3, respectively. While T1 SNN performs slightly worse
compared to ANN-based DQN, SNN with T3 outperforms the ANN. Similar
performance improvement over ANN using SNN for some RL tasks has been reported
in [44]. Next, we experiment with a more complex task, Atari pong game; in
this case, T1 SNN achieves reward of 17.4$\pm$3.2 compared to ANN based DQN’s
19.7$\pm$1.1. However, with T5 SNN, we obtain comparable reward (19.4$\pm$1.3)
to ANN. Notably, with IIR-SNN, we can obtain SNNs for RL task (pong) with
significantly lower latency compared to prior art. On pong, [44] report reward
of 19.8$\pm$1.3 using 500 timesteps, whereas, we obtain 19.4$\pm$1.3 reward
using just 5 timesteps. So, IIR-SNN enables obtaining SNNs for RL tasks with
comparable performance to ANNs with $\sim 5$ timesteps, and up to 1 timestep
with slightly lower performance. Moreover, such latency reduction translates
to considerable energy savings which is critical for agents operating in the
real world. The layerwise spike rates for SNN-DQN (T1) are shown in Fig. 3(c),
the average spike rate is 0.08 only in this case, which results in 7.55X
higher energy efficiency compared to ANN-DQN. Again, if we compare iso-
performing networks to ANN-DQN, SNN-DQN (T5) infers with average spike rate
0.42, thus providing 5.22X higher energy efficiency compared to ANN-DQN. The
details of network topologies used, training setup and additional results are
given in appendix A.5.

##  6 Conclusion

Bio-plausible SNNs hold promise as energy efficient alternatives to ANNs.
However, to make SNNs suitable for edge deployment, mitigating high inference
latency is critical. To that end, we propose IIR-SNN, a sequential SNN
training approach which enables SNNs to infer in a single shot while
maintaining comparable performance to their ANN counterparts. We first train
an ANN followed by ANN-SNN conversion. Then SNN domain training is performed
with 5 timesteps using direct input encoding. At each subsequent stage of
training, latency is reduced gradually using the network trained at previous
stage as initialization, this allows us to obtain deep SNNs up to unit
latency. The proposed scheme enables inference with 25-33X higher energy
efficiency compared to an equivalent ANN with similar accuracy. Furthermore,
in comparison with other state-of-the-art SNNs, T1 IIR-SNNs reduce latency by
5-2500X without significant degradation of performance. Again, T1 SNNs get rid
of the memory access overhead associated with fetching membrane potentials
which is prevalent in SNNs with multiple timesteps. Moreover, inference with
unit latency improves compute efficiency of SNNs too since the total spike
count is reduced significantly compared to SNNs with high latency. We also
investigate the efficacy of IIR-SNN in obtaining low latency SNN solutions for
RL tasks (cartpole and Atari pong) and observe that SNN based DQNs can perform
reasonably well even with just 1 timestep, and comparably to ANN based DQNs
with 5 timesteps. In short, the proposed method tries to address the high
inference latency issue of SNNs and paves the way of obtaining SNNs with
lowest possible latency (1), albeit while incurring some extra training
overhead and a slight accuracy drop in some cases.

##  7 Acknowledgements

This work was supported in part by the Center for Brain Inspired Computing
(C-BRIC), one of the six centers in JUMP, a Semiconductor Research Corporation
(SRC) program sponsored by DARPA, by the SRC, the National Science Foundation,
Intel Corporation, the DoD Vannevar Bush Fellowship, and by the U.S. Army
Research Laboratory.

## References

  * [1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In Advances in neural information processing systems, pages 1097–1105, 2012.
  * [2] Geoffrey Hinton, Li Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al.  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups.  IEEE Signal processing magazine, 29(6):82–97, 2012.
  * [3] Li Deng and Yang Liu.  Deep learning in natural language processing.  Springer, 2018.
  * [4] Da Li, Xinbo Chen, Michela Becchi, and Ziliang Zong.  Evaluating the energy efficiency of deep convolutional neural networks on cpus and gpus.  In 2016 IEEE international conferences on big data and cloud computing (BDCloud), social computing and networking (SocialCom), sustainable computing and communications (SustainCom)(BDCloud-SocialCom-SustainCom), pages 477–484. IEEE, 2016.
  * [5] Ramyad Hadidi, Jiashen Cao, Yilun Xie, Bahar Asgari, Tushar Krishna, and Hyesoon Kim.  Characterizing the deployment of deep neural networks on commercial edge devices.  In 2019 IEEE International Symposium on Workload Characterization (IISWC), pages 35–48. IEEE, 2019.
  * [6] Song Han, Jeff Pool, John Tran, and William J Dally.  Learning both weights and connections for efficient neural networks.  arXiv preprint arXiv:1506.02626, 2015.
  * [7] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Learning structured sparsity in deep neural networks.  Advances in neural information processing systems, 29:2074–2082, 2016.
  * [8] Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio.  Binarized neural networks: Training deep neural networks with weights and activations constrained to+ 1 or-1.  arXiv preprint arXiv:1602.02830, 2016.
  * [9] Wolfgang Maass.  Networks of spiking neurons: the third generation of neural network models.  Neural networks, 10(9):1659–1671, 1997.
  * [10] Kaushik Roy, Akhilesh Jaiswal, and Priyadarshini Panda.  Towards spike-based machine intelligence with neuromorphic computing.  Nature, 575(7784):607–617, 2019.
  * [11] Charlotte Frenkel.  Sparsity provides a competitive advantage.  Nature Machine Intelligence, 3(9):742–743, 2021.
  * [12] Emre O Neftci, Hesham Mostafa, and Friedemann Zenke.  Surrogate gradient learning in spiking neural networks.  IEEE Signal Processing Magazine, 36:61–63, 2019.
  * [13] Peter U Diehl, Daniel Neil, Jonathan Binas, Matthew Cook, Shih-Chii Liu, and Michael Pfeiffer.  Fast-classifying, high-accuracy spiking deep networks through weight and threshold balancing.  In 2015 International Joint Conference on Neural Networks (IJCNN), pages 1–8. ieee, 2015.
  * [14] Abhronil Sengupta, Yuting Ye, Robert Wang, Chiao Liu, and Kaushik Roy.  Going deeper in spiking neural networks: Vgg and residual architectures.  Frontiers in neuroscience, 13:95, 2019.
  * [15] Bing Han, Gopalakrishnan Srinivasan, and Kaushik Roy.  Rmp-snn: Residual membrane potential neuron for enabling deeper high-accuracy and low-latency spiking neural network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13558–13567, 2020.
  * [16] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  arXiv preprint arXiv:1510.00149, 2015.
  * [17] Nitin Rathi, Gopalakrishnan Srinivasan, Priyadarshini Panda, and Kaushik Roy.  Enabling deep spiking neural networks with hybrid conversion and spike timing dependent backpropagation.  In International Conference on Learning Representations, 2020.
  * [18] Nitin Rathi and Kaushik Roy.  Diet-snn: Direct input encoding with leakage and threshold optimization in deep spiking neural networks.  arXiv preprint arXiv:2008.03658, 2020.
  * [19] Hanle Zheng, Yujie Wu, Lei Deng, Yifan Hu, and Guoqi Li.  Going deeper with directly-trained larger spiking neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11062–11070, 2021.
  * [20] Yongqiang Cao, Yang Chen, and Deepak Khosla.  Spiking deep convolutional neural networks for energy-efficient object recognition.  International Journal of Computer Vision, 113(1):54–66, 2015.
  * [21] Bodo Rueckauer, Iulia-Alexandra Lungu, Yuhuang Hu, Michael Pfeiffer, and Shih-Chii Liu.  Conversion of continuous-valued deep networks to efficient event-driven networks for image classification.  Frontiers in neuroscience, 11:682, 2017.
  * [22] Dongsung Huh and Terrence J Sejnowski.  Gradient descent for spiking neural networks.  In Advances in Neural Information Processing Systems, pages 1433–1443, 2018.
  * [23] Chankyu Lee, Syed Shakib Sarwar, Priyadarshini Panda, Gopalakrishnan Srinivasan, and Kaushik Roy.  Enabling spike-based backpropagation for training deep neural network architectures.  Frontiers in Neuroscience, 14, 2020.
  * [24] Friedemann Zenke and Surya Ganguli.  Superspike: Supervised learning in multilayer spiking neural networks.  Neural computation, 30(6):1514–1541, 2018.
  * [25] Sumit Bam Shrestha and Garrick Orchard.  Slayer: Spike layer error reassignment in time.  In Advances in Neural Information Processing Systems, pages 1412–1421, 2018.
  * [26] Yujie Wu, Lei Deng, Guoqi Li, Jun Zhu, and Luping Shi.  Spatio-temporal backpropagation for training high-performance spiking neural networks.  Frontiers in neuroscience, 12:331, 2018.
  * [27] Jaehyun Kim, Heesu Kim, Subin Huh, Jinho Lee, and Kiyoung Choi.  Deep neural networks with weighted spikes.  Neurocomputing, 311:373–386, 2018.
  * [28] Seongsik Park, Seijoon Kim, Hyeokjun Choe, and Sungroh Yoon.  Fast and efficient information transmission with burst spikes in deep spiking neural networks.  In 2019 56th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2019.
  * [29] Lei Zhang, Shengyuan Zhou, Tian Zhi, Zidong Du, and Yunji Chen.  Tdsnn: From deep neural networks to deep spike neural networks with temporal-coding.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1319–1326, 2019.
  * [30] Seongsik Park, Seijoon Kim, Byunggook Na, and Sungroh Yoon.  T2fsnn: Deep spiking neural networks with time-to-first-spike coding.  arXiv preprint arXiv:2003.11741, 2020.
  * [31] Iulia M Comsa, Thomas Fischbacher, Krzysztof Potempa, Andrea Gesmundo, Luca Versari, and Jyrki Alakuijala.  Temporal coding in spiking neural networks with alpha synaptic function.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8529–8533. IEEE, 2020.
  * [32] Sen Lu and Abhronil Sengupta.  Exploring the connection between binary and spiking neural networks.  arXiv preprint arXiv:2002.10064, 2020.
  * [33] Eric Hunsberger and Chris Eliasmith.  Spiking deep networks with lif neurons.  arXiv preprint arXiv:1510.08829, 2015.
  * [34] Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar.  Born again neural networks.  In International Conference on Machine Learning, pages 1607–1616. PMLR, 2018.
  * [35] Chenglin Yang, Lingxi Xie, Siyuan Qiao, and Alan L Yuille.  Training deep neural networks in generations: A more tolerant teacher educates better students.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5628–5635, 2019.
  * [36] Yujie Wu, Lei Deng, Guoqi Li, Jun Zhu, Yuan Xie, and Luping Shi.  Direct training for spiking neural networks: Faster, larger, better.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1311–1318, 2019.
  * [37] Jibin Wu, Yansong Chua, Malu Zhang, Guoqi Li, Haizhou Li, and Kay Chen Tan.  A tandem learning rule for efficient and rapid inference on deep spiking neural networks.  arXiv, pages arXiv–1907, 2019.
  * [38] Wenrui Zhang and Peng Li.  Temporal spike sequence learning via backpropagation for deep spiking neural networks.  Advances in Neural Information Processing Systems, 33, 2020.
  * [39] Mark Horowitz.  1.1 computing’s energy problem (and what we can do about it).  In 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), pages 10–14. IEEE, 2014.
  * [40] Charbel Sakr, Jungwook Choi, Zhuo Wang, Kailash Gopalakrishnan, and Naresh Shanbhag.  True gradient-based training of deep binary activated neural networks via continuous binarization.  In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2346–2350. IEEE, 2018.
  * [41] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  arXiv preprint arXiv:1308.3432, 2013.
  * [42] Shikuang Deng and Shi Gu.  Optimal conversion of conventional artificial neural networks to spiking neural networks.  In International Conference on Learning Representations, 2020.
  * [43] Youngeun Kim and Priyadarshini Panda.  Revisiting batch normalization for training low-latency deep spiking neural networks from scratch.  arXiv preprint arXiv:2010.01729, 2020.
  * [44] Weihao Tan, Devdhar Patel, and Robert Kozma.  Strategy and benchmark for converting deep q-networks to event-driven spiking neural networks.  arXiv preprint arXiv:2009.14456, 2020.
  * [45] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  nature, 518(7540):529–533, 2015.
  * [46] Paul J Werbos.  Backpropagation through time: what it does and how to do it.  Proceedings of the IEEE, 78(10):1550–1560, 1990.
  * [47] Guillaume Bellec, Darjan Salaj, Anand Subramoney, Robert Legenstein, and Wolfgang Maass.  Long short-term memory and learning-to-learn in networks of spiking neurons.  In Advances in Neural Information Processing Systems, pages 787–797, 2018.
  * [48] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: a simple way to prevent neural networks from overfitting.  The journal of machine learning research, 15(1):1929–1958, 2014\.
  * [49] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision, pages 1026–1034, 2015.

##  Appendix A Appendix

###  A.1 Training Methodology

####  A.1.1 surrogate-gradient based learning

To train deep SNNs, surrogate-gradient based backpropagation through time
(BPTT) [46] is used to perform temporal as well as spatial error credit
assignment. Spatial credit assignment is achieved by spatial error
distribution across layers, while the network is unrolled in time for temporal
credit assignment. The output layer neuronal dynamics is governed by-

$u_{i}^{t}=u_{i}^{t-1}+\sum_{j}w_{ij}o_{j}^{t},$ (5)

here $u_{i}$ corresponds to the membrane potential of i-th neuron of final
(L-th) layer. The final layer neurons just accumulate the potential over time
for classification purpose, without emitting spikes. We pass these accumulated
final layer outputs through a softmax layer which gives the class-wise
probability distribution and then the loss is calculated using the cross-
entropy between the true output and the network’s predicted distribution. The
governing equations are-

$Loss=-\sum_{i}y_{i}log(s_{i}),$ (6)
$s_{i}=\frac{e^{u_{i}^{T}}}{\sum_{k=1}^{N}e^{u_{k}^{T}}},$ (7)

where Loss represents the loss function, y denotes true label, s is the
predicted label, T is the total number of timesteps and N is the number of
classes. The derivative of the loss w.r.t. the membrane potential of the
neurons in the final layer is-

$\frac{\partial Loss}{\partial\bm{u}_{L}^{T}}=\bm{s}-\bm{y},$ (8)

and the weight updates at the output layer are done as-

$w_{ij,L}=w_{ij,L}-\eta\Delta w_{ij,L},$ (9) $\Delta
w_{ij,L}=\sum_{t}\frac{\partial Loss}{\partial
w_{ij,L}^{t}}=\sum_{t}\frac{\partial
Loss}{\partial\bm{u}_{L}^{T}}\frac{\partial\bm{u}_{L}^{T}}{\partial
w_{ij,L}^{t}}=\frac{\partial
Loss}{\partial\bm{u}_{L}^{T}}\sum_{t}\frac{\partial\bm{u}_{L}^{T}}{\partial
w_{ij,L}^{t}},$ (10)

where $\eta$ is the learning rate, and $w_{ij,L}^{t}$ denotes the weight
between i-th neuron at layer $L$ and j-th neuron at layer $L-1$ at timestep t.
Output layer neurons are non-spiking, hence the non-differentiability issue is
not involved here. The hidden layer parameter update is given by-

$\Delta w_{ij,k}=\sum_{t}\frac{\partial Loss}{\partial
w_{ij,k}^{t}}=\sum_{t}\frac{\partial Loss}{\partial o_{i,k}^{t}}\frac{\partial
o_{i,k}^{t}}{\partial u_{i,k}^{t}}\frac{\partial u_{i,k}^{t}}{\partial
w_{ij,k}^{t}},~{}~{}~{}k=2,3,...L-1$ (11)

where $o_{i,k}^{t}$ is the spike-generating function (Eqn. 3), k is layer
index. We approximate the gradient of this function w.r.t. its input using the
linear surrogate-gradient [47] as-

$\frac{\partial o}{\partial u}=\gamma max\\{0,1-|\frac{u-v}{v}|\\},$ (12)

where $\gamma$ is a hyperparameter chosen as 0.3 in this work. Again, the
layerwise threshold is updated using-

$v_{l}=v_{l}-\eta\Delta v_{l},$ (13) $\Delta v_{l}=\sum_{t}\frac{\partial
Loss}{\partial v_{l}}=\sum_{t}\frac{\partial
Loss}{\partial\bm{o}_{l}^{t}}\frac{\partial\bm{o}_{l}^{t}}{\partial\bm{z}_{l}^{t}}\frac{\partial\bm{z}_{l}^{t}}{\partial
v_{l}}=\sum_{t}\frac{\partial
Loss}{\partial\bm{o}_{l}^{t}}\frac{\partial\bm{o}_{l}^{t}}{\partial\bm{z}_{l}^{t}}\left(\frac{-v_{l}\bm{o}_{l}^{t-1}-\bm{u}_{l}^{t}}{v_{l}^{2}}\right)$
(14)

and during training stages where more than one timestep is involved, the leak
is updated as-

$\lambda_{l}=\lambda_{l}-\eta\Delta\lambda_{l},~{}~{}~{}\text{and}~{}~{}~{}\Delta\lambda_{l}=\sum_{t}\frac{\partial
Loss}{\partial\lambda_{l}}=\sum_{t}\frac{\partial
Loss}{\partial\bm{o}_{l}^{t}}\frac{\partial\bm{o}_{l}^{t}}{\partial\bm{u}_{l}^{t}}\frac{\partial\bm{u}_{l}^{t}}{\partial\lambda_{l}}=\sum_{t}\frac{\partial
Loss}{\partial\bm{o}_{l}^{t}}\frac{\partial\bm{o}_{l}^{t}}{\partial\bm{u}_{l}^{t}}\bm{u}_{l}^{t-1}$
(15)

Algorithm 2 Procedure of spike-based backpropagation learning for an
iteration.

Input: pixel-based mini-batch of input ($\bm{X}$) - target ($\bm{Y}$) pairs,
total number of timesteps ($T$), number of layers ($L$), pre-trained ANN
weights ($\bm{W}$), membrane potential ($\bm{U}$), layer-wise membrane leak
constants ($\bm{\lambda}$), layer-wise firing thresholds ($\bm{V}$), learning
rate ($\eta$)

Initialize: $\bm{U}_{l}^{t}=0,~{}\forall l=1,...,L$

// Forward Phase

for $t\leftarrow 1$ to $T$ do

$\bm{O}_{1}^{t}=\bm{X};$

for $l\leftarrow 2$ to $L-1$ do

// membrane potential integrates weighted sum of spike-inputs

$\bm{U}_{l}^{t}~{}=\lambda_{l}\bm{U}_{l}^{t-1}+\bm{W}_{l}*\bm{O}_{l-1}^{t}$

if $\bm{U}_{l}^{t}>V_{l}$ then

// if membrane potential exceeds $V_{l}$, a neuron fires a spike

$\bm{O}_{l}^{t}=1,~{}\bm{U}_{l}^{t}=\bm{U}_{l}^{t}-V_{l}$

else

// else, output is zero

$\bm{O}_{l}^{t}=0$

end if

end for

// final layer neurons do not fire

$\bm{U}_{L}^{t}~{}=\bm{U}_{L}^{t-1}+\bm{W}_{L}*\bm{O}_{L-1}^{t}$

end for

//calculate loss, Loss=cross-entropy($\bm{U}_{L}^{T},\bm{Y}$)

// Backward Phase

for $t\leftarrow T$ to $1$ do

for $l\leftarrow L-1$ to $1$ do

// evaluate partial derivatives of loss with respect to the trainable
parameters by unrolling the network over time

$\triangle\bm{W}_{l}^{t}=\frac{\partial
Loss}{\partial\bm{O}_{l}^{t}}\frac{\partial\bm{O}_{l}^{t}}{\partial\bm{U}_{l}^{t}}\frac{\partial\bm{U}_{l}^{t}}{\partial\bm{W}_{l}^{t}},~{}~{}\Delta
V_{l}^{t}=\frac{\partial
Loss}{\partial\bm{O}_{l}^{t}}\frac{\partial\bm{O}_{l}^{t}}{\partial\bm{z}_{l}^{t}}\frac{\partial\bm{z}_{l}^{t}}{\partial
V_{l}},~{}~{}\Delta\lambda_{l}^{t}=\frac{\partial
Loss}{\partial\bm{o}_{l}^{t}}\frac{\partial\bm{o}_{l}^{t}}{\partial\bm{u}_{l}^{t}}\frac{\partial\bm{u}_{l}^{t}}{\partial\lambda_{l}}$

end for

end for

//update the parameters
$\bm{W}_{l}=\bm{W}_{l}-\eta\sum_{t}\Delta\bm{W}_{l}^{t},V_{l}=V_{l}-\eta\sum_{t}\Delta
V_{l}^{t},\lambda_{l}=\lambda_{l}-\eta\sum_{t}\Delta\lambda_{l}^{t}$

###  A.2 Experimental details

####  A.2.1 Network architecture

We modify the VGG and ResNet architectures slightly to facilitate ANN-SNN
conversion. 3 plain convolutional layers of 64 filters are appended after the
input layer in the ResNet architecture [14]. In all cases, average pooling
(2$\times$2) is used and the basic block in ResNet employs a stride of 2 when
the number of filters increases. 1$\times$1 convolution is used in the
shortcut path of basic blocks where the number of filters is different in
input and output. The architectural details are-

VGG6: {64, A, 128, 128, A}, Linear

VGG16: {64, D, 64, A, 128, D, 128, A, 256, D, 256, D, 256, A, 512, D, 512, D,
512, A, 512, D, 512, D, 512}, Linear

ResNet20: {64, D, 64, D, 64, A, 64BB, 64BB, 128BB ($/$2), 128BB, 256BB ($/$2),
256BB, 512BB ($/$2), 512BB}

BB: basic block, Linear: {4096, D, 4096, D, number of classes}, D: Dropout
(probability (p)-ANN: 0.5, SNN: 0.2), A: Average Pooling (kernel size =
2$\times$ 2)

####  A.2.2 Training Hyperparameters

Standard data augmentation techniques are applied for image datasets such as
padding by 4 pixels on each side, and $32\times 32$ cropping by randomly
sampling from the padded image or its horizontally flipped version (with 0.5
probability of flipping). The original $32\times 32$ images are used during
testing. Both training and testing data are normalized using channel-wise mean
and standard deviation calculated from training set. The ANNs are trained with
cross-entropy loss with stochastic gradient descent optimization (weight
decay=0.0005, mometum=0.9). The ANNs domain are trained for 500 and 90 epochs
for CIFAR and ImageNet respectively, with an initial learning rate of 0.01.
The learning rate is divided by 5 at epochs of 0.45, 0.7 and 0.9 fraction of
total epochs. The ANNs are trained with batch-norm (bn) and the bn parameters
are fused with the layerwise weights during ANN-SNN conversion following [21],
we do not have bias terms as bn is used. Additionally, dropout [48] is used as
the regularizer with a constant dropout mask with dropout probability=0.5
across all timesteps while training the SNNs. Again, since max-pooling causes
significant information loss in SNNs [13], we use average-pooling layers to
reduce the feature maps. The ANN, the weights are initialized using He
initialization [49]. Upon conversion, at training iteration with the timestep
fixed, the SNNs are trained for 300 epochs with cross-entropy loss and adam
optimizer (weight decay=0). Initial learning rate is chosen as 0.0001, which
is divided by 5 at epochs of 0.6, 0.8 and 0.9 fraction of total epochs. While
training the SNNs, dropout probability is kept at 0.2.

###  A.3 Comparison of accuracy versus latency trade-off

Figure 4: Accuracy versus latency curve for various SNN coding methods on
VGG16, the values for TTFS [30], phase [27], burst [28] and rate [21] have
been adopted from [30].

.

In this part, we compare our results with other SNN encoding schemes in terms
of timesteps required to reach convergence for a VGG16 network and the results
are shown in Fig. 4. The figure demonstrates the results of “T2FSNN” encoding,
where the timing of spikes carries information and other rate and temporal
coding schemes including “Rate” [21], “Phase” [27], and “Burst” coding [28].
The left plot in Fig. 4 shows $\sim 200$ timesteps is needed for the fastest
convergence among these encoding methods for CIFAR10, whereas, we achieve
$\sim 93.05\%$ accuracy in just 1 timestep. Similarly, IIR-SNN obtains 70.15%
accuracy in 1 timestep with VGG16 on CIFAR100. The graph on the right in Fig.
4 shows the results for VGG16 on CIFAR100 using “T2FSNN”, “Burst”, “Phase” and
“Rate”. As can be seen, “T2FSNN” reaches 68% roughly at 500 steps, “Burst” at
1500, “Phase” at 2000, and “Rate” fails to cross 60% even at 3000 timesteps.
Notably, IIR-SNN not only is able to reduce latency by 2 to 3 orders of
magnitude compared to these works, but also outperforms them in top-1 accuracy
by $\sim 2\%$ using unit inference latency. So, IIR-SNN enhances the
performance on both ends of the accuracy-latency trade-off.

###  A.4 Computational Cost

The number of operations in an ANN layer is given as-

$\\#\text{ANN}_{\text{ops}}=\left\\{\begin{array}[]{ll}k_{w}\times k_{h}\times
c_{in}\times h_{out}\times w_{out}\times c_{out},~{}~{}~{}\text{Conv layer}\\\
n_{in}\times
n_{out},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{Linear
layer}\end{array}\right.$

where $k_{w}(k_{h})$ denote filter width (height), $c_{in}(c_{out})$ is number
of input (output) channels, $h_{out}(w_{out})$ is the height (width) of the
output feature map, and $n_{in}(n_{out})$ is the number of input (output)
nodes.

###  A.5 Additional Results on Reinforcement learning

Figure 5: Rewards during training on Cartpole environment with- (a) ANN-DQN
and (b) SNN-DQN (T1), (c) SNN-DQN (T3), and (d) SNN-DQN (T5).  Figure 6:
Rewards during training on Atari pong environment with- (a) ANN-DQN and (b)
SNN-DQN (T5), (c) SNN-DQN (T3), and (d) SNN-DQN (T1), (e) SNN-Conv DQN (T100),
and (f) layerwise spike rate for the network in (e).

In this section, we provide supplementary results on our experiments with IIR-
SNN on RL tasks (Cartpole and Atari pong). The details of network
architectures, training hyperparameters and training dynamics are described in
the following.

####  A.5.1 Results on Cartpole

For the cartpole task, we use a small network with 3 convolutional and a fully
connected layer. The first convolutional layer has 16 5X5 filters with stride
2, second and third convolutional layers have 32 5X5 filters with stride 2
each. The fully connected layer has 2 neurons, corresponding to the number of
actions. We use RMSProp as optimizer for training. The networks are trained
with batch size of 128, discount factor ($\gamma$) of 0.999 and replay memory
of 10000. Figure 5 shows the results for the cartpole environment. We repeat
all experiments for 400 episodes, in this game, the duration for which the
agent is able to continue the game (keep the balance), is the reward; so
higher game duration means better performance. The blue trajectory shows the
rewards at each episode, which has some variation across episodes, the yellow
curve shows the accumulated average reward. As can be seen, the SNN
outperforms the ANN in terms of reward with just 3 timesteps. For SNN-DQN with
1 timestep (T1), the SNNs performs slightly worse compared to ANN-DQN. As we
increase the simulation time-window (number of timesteps), the SNN performance
improves further as expected, with the average reward for T5 being
52.2$\pm$4.3 (mean$\pm$standard deviation), whereas for the ANN, this metric
is 40.3$\pm$4.8. We anticipate this improvement in multi-timestep SNNs is due
to inherent memory of previous inputs which results from the residual membrane
potential in the spiking neurons. As a result, SNNs offer an advantage
compared to feed-forward ANNs for tasks with a sequential component. In RL
tasks, since the decision-making is sequential and past frames possess some
information about what the next plausible state and corresponding action could
be, SNNs might be better suited to leverage such kind of environment. However,
cartpole balancing is a very simple task, so to further explore the potential
of the proposed IIR-SNN in obtaining low latency solutions for SNN-based RL,
we next apply the IIR SNN-DQN framework to Atari pong environment.

####  A.5.2 Results on Atari pong

Atari pong is a two-dimensional gym environment that simulates table tennis.
Here, the agent steps through the environment by observing frames of the game
(reshaped to 84X84 pixels), interacts with the environment with 6 possible
actions, and receives feedback in the form of the change in the game score.
For our experiments, we first train an ANN based deep Q network (DQN), where
we use the same DQN proposed in [45] with 3 convolution layers and 2 fully
connected layers. The first convolution layer has 32 8X8 filters with stride
4. The second convolution layer has 64 4X4 with stride 2. The third
convolution layer has 64 3X3 filters with stride 1. The fully connected layer
has 512 neurons. The number of neurons in the final layer for any game depends
on the number of valid actions for that game, which in this case is 6.
Training is performed with Adam optimizer with learning rate 0.00001, batch
size 128, discount factor($\gamma$) 0.99 and replay buffer size 100000.
Results of our experiments are shown in Fig. 6. Rewards obtained during ANN-
DQN training are depicted in Fig. 6 (a). As mentioned in the discussion of RL-
SNN in section 5 of the main manuscript, ANN-DQN achieves reward of
19.7$\pm$1.1. The training dynamics using IIR-SNN DQN with T5, T3 and T1 are
shown in Fig. 6 (b), (c), (d) respectively. Reward and efficiency analysis of
these networks compared to ANN-DQN is given in section 5 of the main
manuscript. Additionally, here we compare the performance of IIR-SNN to
converted SNNs as shown in Fig. 6 (e). Note, these SNNs do not undergo any
training in SNN domain, rather they are converted from corresponding ANN-DQNs
and used for inference. Reward obtained the converted SNN with 100 timesteps
is 19.4$\pm$1.3, so converted SNN-DQNs (SNN-conv DQNs) perform comparably to
ANN-DQNs as also reported in [44], however the bottleneck is they require
$\sim$100 timesteps for high performance. Using IIR-SNN, we obtain T5 SNN-DQNs
with comparable performance to their ANN counterparts, but with considerably
lower compute cost (5.22X). We have reported the spike rates for T1 SNN-DQN in
Fig. 3 (c). For comparison purposes, we also consider the layerwise spike rate
for the converted SNN-DQN as shown in Fig. 6 (f), of the main text. In this
case, the average spike rate is 2.92, which leads to 1.75X higher energy
efficiency for the SNN-conv DQN (T100) compared to ANN-DQN. As a result, IIR-
SNN DQN (T5) provides 2.98X improvement in energy efficiency over SNN-conv
DQNs as proposed in [44], while achieving comparable performance.


#  Cordial Digraphs††thanks: AMS Classification number: 05C20, 05C38, 05C78
††thanks: Key words and phrases: Friendly labeling, cordial labeling, cordial
digraph.

LeRoy B. Beasley
Clock Tower Plaza, Ste 317
550 North Main St, Box C3
Logan, Utah 84321, U.S.A
<EMAIL_ADDRESS>
###### Abstract

A $(0,1)$-labeling of a set is said to be friendly if the number of elements
of the set labeled 0 and the number labeled 1 differ by at most 1. Let $g$ be
a labeling of the edge set of a graph that is induced by a labeling $f$ of the
vertex set. If both $g$ and $f$ are friendly then $g$ is said to be a cordial
labeling of the graph. We extend this concept to directed graphs and
investigate the cordiality of directed graphs. We show that all directed paths
and all directed cycles are cordial. We also discuss the cordiality of
oriented trees and other digraphs.

##  1 Introduction

Let ${\mathcal{G}}_{n}$ denote the set of all simple undirected graphs on the
vertex set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$. For $G\in{\mathcal{G}}_{n}$, let
$E(G)$ denote the edge set of $G$. In the article “Cordial graphs: A Weaker
Version of Graceful and Harmonious Graphs”, Ibrahim Cahit introduced cordial
graphs. Relative definitions are found in the next section. In this article we
are interested in directed graphs and so, the orientation of an arc is
essential in any investigation. While the induced labelings in undirected
graphs are symmetric, we shall want the arc labelings of our directed graphs
to be asymmetric. The study of cordial graphs has been to identify classes of
graphs that have a friendly labeling that induces a cordial labeling of the
edges. We shall proceed in that fashion for directed graphs.

##  2 Preliminaries

In this article, we will be concerned mainly with digraphs, We let
${\mathcal{D}}_{n}$ denote the set of all simple directed graphs on the vertex
set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$. Further, we shall want no arcs directed
both ways between any pair of vertices, that is our graphs will be digon-free.
Thus we shall let ${\mathcal{T}}_{n}$ denote the set of all subgraphs of a
tournament digraph. Let $D\in{\mathcal{T}}_{n}$, $D=(V,A)$ where $A$ is the
arc set of $D$. Then $D$ has no loops, no digons, and no multiple arcs. An arc
in $D$ directed from vertex $u$ to vertex $v$ will be denoted
$\overrightarrow{uv},\overleftarrow{vu}$ or by the ordered pair $(u,v)$. We
also let ${\mathcal{G}}_{n}$ denote the set of all simple undirected graphs on
the vertex set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$. So all members of
${\mathcal{T}}_{n}$ are orientations of graphs in ${\mathcal{G}}_{n}$.

A $(0,1)$-labeling of a finite set, ${\cal Z}$, is a mapping $f:{\cal
Z}\to\\{0,1\\}$ and is said to be friendly if approximately one half of the
members of ${\cal Z}$ are labeled 0 and the others are labeled 1, that is
$-1\leq|f^{-1}(0)|-|f^{-1}(1)|\leq 1$ where $|{\cal X}|$ denotes the
cardinality of the set ${\cal X}$. If there are an even number of elements in
${\cal Z}$ , then a friendly labeling has the number labeled 1 equal to the
number labeled 0. More generally we define an ${\cal A}$-friendly labeling:

###### Definition 2.1

Let ${\cal A}$ be a finite set. An ${\cal A}$-labeling of the set Z is a
mapping $f:{\cal Z}\to{\cal A}$. The labeling $f$ is ${\cal A}$-friendly if
$-1\leq|f^{-1}(i)|-|f^{-1}(j)|\leq 1$ for any $i,j\in{\cal A}$.

Note that a labeling is A-friendly means that the labels are as nearly evenly
distributed as possible. If the cardinality of Z is a multiple of the
cardinality of A then $|f^{-1}(i)|=|f^{-1}(j)|$ for any $i,j\in{\cal A}$. If
the set A is obvious from the context we just say that $f$ is friendly.

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$, and
let $f$ be a friendly (0,1)-labeling of the vertex set $V$. Given this
friendly vertex labeling $f$, an induced $(0,1)$-labeling of the edge set is a
mapping $g:E\to\\{0,1\\}$ where for an edge $uv,\,g(uv)=\hat{g}(f(u),f(v))$
for some $\hat{g}:\\{0,1\\}\times\\{0,1\\}\to\\{0,1\\}$ and is said to be
cordial if $g$ is also friendly, that is $-1\leq|g^{-1}(0)|-|g^{-1}(1)|\leq
1$. A graph, $G$, is called cordial if there exists a induced cordial labeling
of the edge set of $G$. The induced labeling $g$ is usually
$g(u,v)=\hat{g}(f(u),f(v))=|f(v)-f(u)|$ [1],
$g(u,v)=\hat{g}(f(u),f(v))=f(v)+f(u)$ (in ${\mathbb{Z}}_{2}$) [2], or
$g(u,v)=\hat{g}(f(u),f(v))=f(v)f(u)$ (product cordiality) [3].

In[2], Hovey introduced ${\cal A}$-friendly labelings. A labeling
$f:V(G)\to{\cal A}$ is said to be ${\cal A}$-friendly  if given any
$a,b\in{\cal A}$, $-1\leq|f^{-1}(b)|-|f^{-1}(a)|\leq 1$. If $g$ is an induced
edge labeling and $f$ and $g$ are both ${\cal A}$-friendly Then $g$ is said to
be an ${\cal A}$-cordial labeling and $G$ is said to be ${\cal A}$-cordial.
When ${\cal A}={\mathbb{Z}}_{k}$ we say that $G$ is $k$-cordial. We shall use
this concept with digraphs.

Let $D=(V,A)$ be a directed graph with vertex set $V$ and arc set $A$. Let
$f:V\to\\{0,1\\}$ be a friendly labeling of the vertices of $D$. As for
undirected graphs, an induced labeling of the arc set is a mapping
$g:A\to{\cal X}$ for some set ${\cal X}$ where for an arc
$(u,v)=\overrightarrow{uv},g(u,v)=\hat{g}(f(u),f(v))$ for some
$\hat{g}:\\{0,1\\}\times\\{0,1\\}\to{\cal X}$. As we are dealing with directed
graphs, it would be desirable for the induced labeling to distinguish between
the label of the arc $(u,v)$ and the label of the arc $(v,u)$, otherwise, the
labeling would be an induced labeling of the underlying undirected graph. If
we let ${\cal X}={\mathbb{Z}}_{3}=\\{-1,0,1\\}$ and
$\hat{g}(f(u),f(v))=f(v)-f(u)$, we have an asymmetric labeling. In this case,
if the set of arcs are nearly equally distributed among the three labelings,
we say that the labeling is $(2,3)$-cordial. Formally:

###### Definition 2.2

Let $D\in{\mathcal{T}}_{n}$, $D=(V,A)$. Let $f:V\to\\{0,1\\}$ be a friendly
labeling of the vertex set $V$ of $D$. Let $g:A\to\\{1,0,-1\\}$ be an induced
labeling of the arcs of $D$. If $g$ is friendly, that is, for any
$i,j\in\\{1,0,-1\\}$, $-1\leq|g^{-1}(i)|-|g^{-1}(j)|\leq 1$. such a labeling
is called a $(2,3)$-cordial labeling, and a digraph $D\in{\mathcal{T}}_{n}$
that can possess a $(2,3)$-cordial labeling will be called a $(2,3)$-cordial
digraph.

For any digraph $D$ with $(0,1)$-vertex labeling $f$, and induced
$(0,1,-1)$-arc labeling $g$, let $\Lambda_{f,g}(D)=(\alpha,\beta,\gamma)$
where $\alpha=|g^{-1}(1)|,\beta=|g^{-1}(-1)|,$ and $\gamma=|g^{-1}(0)|$.

Let $D\in{\mathcal{T}}_{n}$ and let $D^{R}$ be the digraph such that every arc
of $D$ is reversed, so that $\overrightarrow{uv}$ is an arc in $D^{R}$ if and
only if $\overrightarrow{vu}$ is an arc in $D$. Let $f$ be a $(0,1)$-labeling
of the vertices of $D$ and let $g(\overrightarrow{uv})=f(v)-f(u)$ so that $g$
is a $(1,-1,0)$-labeling of the arcs of $D$. Let $\overline{f}$ be the
complementary $(0,1)$-labeling of the vertices of $D$, so that
$\overline{f}(v)=0$ if and only if $f(v)=1$. Let $\overline{g}$ be the
corresponding induced arc labeling of $D$,
$\overline{g}(\overrightarrow{uv})=\overline{f}(v)-\overline{f}(u)$.

###### Lemma 2.1

Let $D\in{\mathcal{T}}_{n}$ with vertex labeling $f$ and induced arc labeling
$g$. Let $\Lambda_{f,g}(D)=(\alpha,\beta,\gamma)$. Then

  1. 1.

$\Lambda_{f,g}(D^{R})=(\beta,\alpha,\gamma)$.

  2. 2.

$\Lambda_{\overline{f},\overline{g}}(D)=(\beta,\alpha,\gamma)$, and

  3. 3.

$\Lambda_{\overline{f},\overline{g}}(D^{R})=\Lambda_{f,g}(D).$

Proof. If an arc is labeled 1, -1, 0 respectively then reversing the labeling
of the incident vertices gives a labeling of -1, 1, 0 respectively, If an arc
$\overrightarrow{uv}$ is labeled 1, -1, 0 respectively, then
$\overrightarrow{vu}$ would be labeled -1, 1, 0 respectively.

##  3 (2,3)-Cordial Digraphs.

In this section, we shall use the arc labeling function $g:A\to\\{0,1,-1\\}$
defined by $g(\overrightarrow{v_{i}v_{j}})=g(v_{i},v_{j})=f(v_{j})-f(v_{i})$
where $f$ is a $(0,1)$-labeling of the vertices.

###  3.1 (2,3)-cordial labelings of orientations of small trees

We now give labelings of orientations of small trees to be used in inductive
proofs later.

Let $P_{n}$ be a path of order $n$ (the number of vertices, so that there are
$n-1$ arcs in $P_{n}$). For $n=1$, there is only one directed graph and it is
vacuously (2,3)-cordial. For $n=2$ the only tree is an edge graph and any
orientation is the digraph of an arc, which is (2,3)-cordial if the labelings
of the two vertices are different.

For $n=3$, every tree is a 2-path and so there are only two (non-isomorphic)
orientations. We list them here with (2,3)-cordial labelings:

$0$$1$$0$and$0$$1$$1$$1$$-1$$1$$0$ Figure 1:  $(2,3)$-Cordial labelings of
orientations of 3-paths

For $n=4$ there are two undirected trees with three different (non-isomorphic)
orientations of the 4-path and two non-isomorphic orientations of the star on
4 vertices. Here we give these five oriented trees with (2,3)-cordial
labelings of three of them: See Figures 2 and 3.

$0$$1$$1$$0$$0$$1$$1$$0$and$0$$1$$1$$0$$1$$0$$-1$$1$$0$$-1$$1$$0$$-1$ Figure
2:  $(2,3)$-Cordial labeling of three 4-trees

and Figure 3:  Two 4-trees that are not $(2,3)$-cordial

####  3.1.1 (2,3)-Cordial Stars

Recall that for a friendly labeling $f$ of the vertices we let $g$ be the
induced labeling of the arcs defined by $g(u,v)=f(v)-f(u)$.

Let $S\in{\mathcal{G}}_{n}$ be a star graph with central vertex $v$ and $n-1$
pendant vertices. A natural question is: Is there an orientation of $S$ that
is (2,3)-cordial? Another is: Are all orientations of $S$ (2,3)-cordial? The
answer to the latter question is: Only if $n\leq 3$. The answer to the first
question is more complicated, but is completely answered here.

Let $n\geq 4$. There are six cases to consider: $n$ is even or odd and $n$ is
a multiple of three, one more than a multiple of three or two more than a
multiple of three. Investigating these six cases, we let $k$ and $\ell$ be
positive integers.

Case 1. $n$ is even, $n=2k$. Here there must be $k-1$ pendant vertices labeled
the same as the labeling of the central vertex $v$. Since $n\geq 4$, $k\geq
2$, we have that $\lceil\frac{k}{2}\rceil\leq k-1$. For $g$ to be friendly, we
must have $k-1$ arcs labeled 0, $\lceil\frac{k}{2}\rceil$ arcs labeled either
1 or -1 respectively, and $\lfloor\frac{k}{2}\rfloor$ arcs labeled -1 or 1
respectively.

Subcase a. The number of arcs is $n-1=3\ell$ so that $n=3\ell+1$. For $S$ to
be (2,3)-cordial we must have $k-1=\ell$. But then $2k=n=3\ell+1=3(k-1)+1$ so
that $k=2$ and $n=4$.

Subcase b. The number of arcs is $n-1=3\ell+1$, so that $n=3\ell+2$. For $S$
to be (2,3)-cordial we must have $k-1=\ell+1$ or $k=\ell+2$. Hence
$n=2k=2\ell+4=3\ell+2$, so that, $\ell=2$ , $k=4$ and $n=8$.

Subcase c. The number of arcs is $n-1=3\ell+2$ so that $n=3\ell+3$. For $S$ to
be (2,3)-cordial we must have $k-1=\ell+1$ or $k=\ell+2$. Thus,
$n=2k=2\ell+4=3\ell+3$ so that $\ell=1$ and $n=6$.

Thus, since any orientation of a 2-star is $(2,3)$-cordial, when $n$ is even
we have that $n=2,4,6$ or $8$ only.

Case 2. $n$ is odd, $n=2k+1$. Since for $n=1$ or 3, every orientation of a
1-star or 3-star is $(2,3)$-cordial, we assume that $n\geq 5$ and thus
$\lceil\frac{k}{2}\rceil\leq k-1$. Hence there are $k-1$ pendant vertices
labeled the same as the labeling of the central vertex $v$. So there are $k-1$
arcs labeled 0.

Subcase a. The number of arcs is $n-1=3\ell$ so that $n=3\ell+1$. For $S$ to
be (2,3)-cordial we must have $k-1=\ell$ so that $k=\ell+1$ and hence
$3\ell+1=n=2k+1=2\ell+3$ and hence $\ell=2$ and $n=7$.

Subcase b. The number of arcs is $n-1=3\ell+1$ so that $n=3\ell+2$. For $S$ to
be (2,3)-cordial we must have $k-1=\ell$ or $k=\ell+1$ and $\frac{k}{2}=\ell$
so that $n=5$; or $k-1=\ell+1$ and $k=\ell+2$, so that $n=11$.

Subcase c. The number of arcs is $n-1=3\ell+2$ so that $n=3\ell+3$. For $S$ to
be (2,3)-cordial we must have $k-1=\ell+1$ so $k=\ell+2$. Thus,
$3\ell+3=n=2k+1=2\ell+5$. Hence $l=2$ and $n=9$.

Thus, when $n$ is odd, we have that $n=1,3,5,7,9$ or 11 only.

The above analysis establishes:

###### Lemma 3.1

A star graph has a (2,3)-cordial orientation if and only if $n\leq 11$ and
$n\neq 10$.

####  3.1.2 (2,3)-Cordiality of Directed Cycles and Paths

###### Theorem 3.1

Let $f$ be a $(0,1)$-friendly labeling of $D\in{\mathcal{T}}_{n}$ and $g$ the
induced $(1,0,-1)$-labeling of the arcs of $D$. Then,

  1. 1.

If $D$ is a directed $k$-cycle for $k\geq 3$, then $D$ is (2,3)-cordial.

  2. 2.

If $D$ is any directed path in ${\mathcal{D}}_{n}$, then $D$ is (2,3)-cordial.

  3. 3.

If $n\geq 4$ and $D$ is an out-star or an in-star then $D$ is not
(2,3)-cordial.

Proof. The labeling of an $n$-cycle is shown in Figure 4, where $k=2\ell$ and
$n=3k=6\ell$. The vertex labeling is outside the cycle and the induced edge
labeling is inside the cycle. By deleting $1,2,\dots,5$ vertices, carefully
chosen, one obtains a $(2,3)$-cordial labeling of a cycle of any length. By
deleting one edge, carefully chosen, one obtains a $(2,3)$-cordial labeling of
any directed path. Thus, conclusions 1 and 2 are proven.

If $D$ is an out-star with central vertex $v$, then, if the vertex $v$ is
labeled ”0”, all arcs are labeled either ”0” or ”-1”, while if the vertex $v$
is labeled ”1”, all arcs are labeled either ”0” or ”1” Thus, no labeling is
(2,3)-cordial. A parallel argument holds for an in-star.

$v_{1}$$v_{2}$$v_{3}$$\dots$$v_{2k-2}$$v_{2k-1}$$v_{2k}$$0$$1$$0$$1$$0$$1$$1$$-1$$1$$1$$-1$$1$$v_{3k}$$v_{3k-1}$$\dots$$v_{5\ell+1}$$\dots$$v_{2k+\ell}$$v_{2k+1}$$0$$0$$0$$1$$1$$0$$0$$0$$-1$$0$$0$$0$$n=6\ell=3k,k=2\ell$
Figure 4:  $(2,3)$-Cordial labeling of a cycle

It is easily shown, even though time consuming, that both of the non-
isomorphic tournaments on 3 vertices are (2,3)-cordial while only three of the
four non-isomorphic tournaments on four vertices are cordial; the 4-tournament
with score vector (1,1,1,3) is not (2,3)-cordial.

###### Conjecture 3.2

Given any tree $T\in{\mathcal{G}}_{n}$ with $\Delta(T)\leq 3$ there is an
orientation of $T$ that is $(2,3)$-cordial.

##  4 Paths

###### Lemma 4.1

For $n\leq 9$, every orientation of any path on n vertices is (2,3)-cordial,
except when $n=4$ and the orientation is one of those listed in Figure 5.

Proof. For $n=1$ or $n=2$ the lemma is trivially established. For $n=3$ the
two orientations in Figure 1 (and consequently their reversals) are shown to
be (2,3)-cordial.

For $n=4$, the four orientations of the 4-path that are not in Figure 5 are
shown to be (2,3)-cordial in Figure 6.

For $n=5,6,$ and $7$, see the appendices, There is a (2,3)-cordial labeling of
each orientation of the paths of length 5, 6, and 7.

For $n=8$, append a vertex to the end of each orientation of the path on 7
vertices and obtain two orientations of the 8-path, one with
$\overrightarrow{v_{7}v_{8}}$ and the other with $\overleftarrow{v_{7}v_{8}}$.
By labeling vertex $v_{8}$ with 0 if there are fewer vertices in the labeling
of the orientation of $P_{7}$ labeled 0 than 1 and labeling vertex $v_{8}$ a 1
otherwise we get a $(2,3)$-cordial labeling. Thus, we get a (2,3)cordial
labeling of all 128 orientations of $P_{8}$.

For $n=9$, append a vertex to the end of each orientation of the path on 8
vertices and obtain two orientations of the 9-path, one with
$\overrightarrow{v_{8}v_{9}}$ and the other with $\overleftarrow{v_{8}v_{9}}$.
By choosing appropriately the label of $v_{9}$ one gets a (2,3)-cordial
labeling. This gives a (2,3)-cordial labeling of all 256 orientations of
$P_{9}$.

Note that in the sequel, only vertex labelings are given as the arc labels are
implicit. For example in Figures 5 and 6 we give the 4-paths that are
(2,3)-cordial and the 4-paths that are not (2,3)-cordial.

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0$

$1\longleftarrow 0\longleftarrow 0\longleftarrow 1$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1$

Figure 5:  Labeled orientations of the 4-path that are $(2,3)$-cordial

$*\longrightarrow*\longrightarrow*\longleftarrow*$

$*\longrightarrow*\longleftarrow*\longleftarrow*$

$*\longleftarrow*\longleftarrow*\longrightarrow*$

$*\longleftarrow,*\longrightarrow*\longrightarrow*$

Figure 6:  Orientations of the 4-path that are not $(2,3)$-cordial

###### Conjecture 4.1

Let $P$ be a path in ${\mathcal{G}}_{n}$ of length $n\geq 5$. Then every
orientation of $P$ is (2,3)-cordial.

The author wishes to thank the referee for his valuable suggestions.

## References

  * [1] I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23(1987) 201-208.
  * [2] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183-194.
  * [3] E Salehi, PC-labeling of a graph and its PC-set, Bull. Inst. Comb. Appl., 58(2010) 112-121.

##  5 APPENDIX: Orientations of paths of lengths 5, 6 and 7.

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longrightarrow 0$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longrightarrow 0$

$0\longrightarrow 1\longrightarrow 0\longleftarrow 0\longrightarrow 1$

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longleftarrow 0$

$0\longrightarrow 1\longleftarrow 1\longleftarrow 1\longrightarrow 0$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longleftarrow 0$

$0\longrightarrow 1\longrightarrow 1\longleftarrow 0\longleftarrow 1$

$0\longrightarrow 1\longleftarrow 0\longleftarrow 0\longleftarrow 1$

$1\longleftarrow 0\longrightarrow 0\longrightarrow 1\longrightarrow 0$

$1\longleftarrow 0\longleftarrow 0\longrightarrow 1\longrightarrow 0$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longrightarrow 1$

$1\longleftarrow 0\longrightarrow 0\longrightarrow 0\longleftarrow 1$

$1\longleftarrow 0\longleftarrow 0\longleftarrow 1\longrightarrow 1$

$1\longleftarrow 0\longleftarrow 0\longrightarrow 0\longleftarrow 1$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longleftarrow 1$

$1\longleftarrow 0\longleftarrow 0\longleftarrow 1\longleftarrow 1$

Figure 7:  Orientations of the 5-path

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longrightarrow
0\longrightarrow 1$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longrightarrow
0\longrightarrow 1$

$1\longrightarrow 0\longleftarrow 0\longleftarrow 1\longrightarrow
1\longrightarrow 0$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longrightarrow
1\longrightarrow 0$

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longleftarrow
0\longrightarrow 1$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longleftarrow
0\longrightarrow 1$

$1\longleftarrow 0\longleftarrow 0\longleftarrow 1\longleftarrow
1\longrightarrow 0$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longleftarrow
1\longrightarrow 0$

$0\longrightarrow 1\longrightarrow 0\longleftarrow 0\longrightarrow
1\longrightarrow 1$

$0\longrightarrow 1\longleftarrow 0\longleftarrow 1\longrightarrow
1\longrightarrow 0$

$1\longleftarrow 0\longleftarrow 0\longrightarrow 1\longrightarrow
1\longrightarrow 0$

$1\longleftarrow 0\longrightarrow 1\longrightarrow 1\longrightarrow
0\longrightarrow 0$

$0\longrightarrow 0\longrightarrow 1\longleftarrow 0\longleftarrow
1\longrightarrow 1$

$0\longrightarrow 1\longleftarrow 0\longleftarrow 0\longleftarrow
1\longrightarrow 1$

$1\longleftarrow 1\longleftarrow 0\longrightarrow 0\longleftarrow
1\longrightarrow 0$

$1\longleftarrow 0\longrightarrow 0\longrightarrow 1\longleftarrow
1\longrightarrow 0$

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longrightarrow
0\longleftarrow 1$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longrightarrow
0\longleftarrow 1$

$1\longrightarrow 0\longleftarrow 0\longleftarrow 1\longrightarrow
1\longleftarrow 0$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longrightarrow
1\longleftarrow 0$

$0\longrightarrow 1\longrightarrow 1\longrightarrow 0\longleftarrow
0\longleftarrow 1$

$0\longrightarrow 1\longleftarrow 1\longrightarrow 0\longleftarrow
0\longleftarrow 1$

$1\longleftarrow 0\longleftarrow 0\longleftarrow 1\longleftarrow
1\longleftarrow 0$

$1\longleftarrow 0\longrightarrow 0\longleftarrow 1\longleftarrow
1\longleftarrow 0$

$0\longrightarrow 1\longrightarrow 0\longleftarrow 0\longrightarrow
1\longleftarrow 1$

$0\longrightarrow 1\longleftarrow 0\longleftarrow 1\longrightarrow
1\longleftarrow 1$

$1\longleftarrow 0\longleftarrow 0\longrightarrow 1\longrightarrow
1\longleftarrow 0$

$1\longleftarrow 0\longrightarrow 1\longrightarrow 1\longrightarrow
0\longleftarrow 1$

$0\longrightarrow 0\longrightarrow 1\longleftarrow 0\longleftarrow
1\longleftarrow 1$

$0\longrightarrow 1\longleftarrow 0\longleftarrow 0\longleftarrow
1\longleftarrow 1$

$1\longleftarrow 1\longleftarrow 0\longrightarrow 0\longleftarrow
1\longleftarrow 0$

$1\longleftarrow 0\longrightarrow 0\longrightarrow 1\longleftarrow
1\longleftarrow 0$

Figure 8:  Orientations of the 6-path

$0\rightarrow 1\rightarrow 1\rightarrow 0\rightarrow 0\rightarrow 1\rightarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\rightarrow 0\rightarrow 1\rightarrow
0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\rightarrow 0\rightarrow 1\rightarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\rightarrow 0\rightarrow 1\rightarrow
0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\leftarrow 0\rightarrow 1\rightarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 0\rightarrow 1\rightarrow
0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\leftarrow 0\rightarrow 1\rightarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\leftarrow 0\rightarrow 1\rightarrow 0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\rightarrow 1\rightarrow 0\leftarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\rightarrow 1\rightarrow 0\leftarrow
0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\rightarrow 1\rightarrow 0\leftarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\rightarrow 1\rightarrow 0\leftarrow 0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\leftarrow 1\rightarrow 1\leftarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 1\rightarrow 1\leftarrow 0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\leftarrow 1\rightarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\leftarrow 1\rightarrow 1\leftarrow 0$

$0\rightarrow 1\rightarrow 0\leftarrow 0\rightarrow 1\rightarrow 1\rightarrow
0$

$0\rightarrow 1\leftarrow 0\leftarrow 1\rightarrow 1\rightarrow 0\rightarrow
0$

$0\leftarrow 1\leftarrow 0\rightarrow 0\rightarrow 1\rightarrow 1\rightarrow
0$

$0\leftarrow 0\rightarrow 1\rightarrow 0\rightarrow 1\rightarrow 1\rightarrow
0$

$0\rightarrow 1\rightarrow 1\leftarrow 0\leftarrow 1\rightarrow 1\rightarrow
0$

$0\rightarrow 1\leftarrow 0\leftarrow 0\leftarrow 1\rightarrow 1\rightarrow 0$

$1\leftarrow 0\leftarrow 0\rightarrow 0\leftarrow 1\rightarrow 0\rightarrow 1$

$1\leftarrow 0\rightarrow 0\rightarrow 0\leftarrow 1\rightarrow 0\rightarrow
1$

$0\rightarrow 1\rightarrow 0\leftarrow 1\rightarrow 1\rightarrow 1\leftarrow
0$

$0\rightarrow 0\leftarrow 1\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 0$

$0\leftarrow 0\leftarrow 1\rightarrow 1\rightarrow 0\rightarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 1\rightarrow 0\rightarrow 0\rightarrow 1\leftarrow
0$

$0\rightarrow 1\rightarrow 1\leftarrow 0\leftarrow 1\rightarrow 0\leftarrow 0$

$0\rightarrow 1\leftarrow 0\leftarrow 1\leftarrow 1\rightarrow 0\leftarrow 0$

$1\leftarrow 0\leftarrow 0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 1$

$1\leftarrow 0\rightarrow 0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 1$

$0\rightarrow 0\rightarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\rightarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\rightarrow
0$

$0\leftarrow 0\leftarrow 1\leftarrow 0\rightarrow 1\leftarrow 1\rightarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\rightarrow 1\leftarrow 1\rightarrow 0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\leftarrow 1\leftarrow 0\rightarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 1\leftarrow 0\rightarrow 0$

$0\leftarrow 1\leftarrow 0\leftarrow 1\leftarrow 1\leftarrow 0\rightarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\leftarrow 1\leftarrow 0\rightarrow 0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\rightarrow 0\leftarrow 1\leftarrow
0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\rightarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\rightarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\rightarrow 0\leftarrow 1\leftarrow 0$

$0\rightarrow 1\rightarrow 1\rightarrow 0\leftarrow 0\leftarrow 1\leftarrow 0$

$0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\leftarrow 1\leftarrow 0\leftarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 1\leftarrow 0\leftarrow 0\leftarrow 1\leftarrow 0$

$0\rightarrow 1\rightarrow 0\leftarrow 0\rightarrow 1\leftarrow 1\rightarrow
0$

$0\rightarrow 0\leftarrow 1\leftarrow 0\rightarrow 1\leftarrow 1\rightarrow 0$

$0\leftarrow 1\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 0\rightarrow 0$

$0\leftarrow 1\rightarrow 1\rightarrow 0\rightarrow 1\leftarrow 0\rightarrow
0$

$0\rightarrow 1\rightarrow 1\leftarrow 0\leftarrow 0\leftarrow 1\rightarrow 0$

$0\rightarrow 1\leftarrow 0\leftarrow 0\leftarrow 1\leftarrow 1\rightarrow 0$

$0\leftarrow 1\leftarrow 0\rightarrow 1\leftarrow 1\leftarrow 1\rightarrow 0$

$0\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\leftarrow 0\rightarrow 0$

$0\rightarrow 0\rightarrow 1\leftarrow 1\rightarrow 0\leftarrow 1\leftarrow 0$

$0\rightarrow 1\leftarrow 1\leftarrow 1\rightarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\leftarrow 0$

$0\rightarrow 1\rightarrow 0\leftarrow 0\leftarrow 1\leftarrow 1\leftarrow 0$

$0\rightarrow 0\leftarrow 1\leftarrow 0\leftarrow 1\leftarrow 1\leftarrow 0$

$0\leftarrow 0\leftarrow 1\rightarrow 1\leftarrow 0\leftarrow 1\leftarrow 0$

$0\leftarrow 1\rightarrow 0\rightarrow 1\leftarrow 1\leftarrow 0\leftarrow 0$

Figure 9:  Orientations of the 7-path