Exploiting Spiking Dynamics with Spatial-temporal Feature Normalization in Graph Learning

1 Introduction

Spiking neural network (SNN) is a typical brain-inspired network, which inherits the biological spatio-temporal dynamics mechanisms and rich spiking coding schemes, demonstrating great benefits for mimicking neuroscience-inspired models and performing efficient computation in neuromorphic hardware. Recently SNNs have been successfully applied in a variety of applications, such as image classification, voice recognition, object tracking, neuromorphic perception, etc [Wu et al., 2018; Silva et al., 2017; Cao et al., 2015; Zhu et al., 2020; Haessig et al., 2019]. However, most of published works have mainly focused on processing unstructured information represented in the Euclidean space, such as image, language data, etc [Zhou et al., 2018]. On the other hand, biological spiking neurons with rich coding schemes and spatio-temporal dynamics underlie the foundation of graphic cognitive map in the hippocampal-entorhinal system. It facilitates the organization and assimilation of internal association attributes in structured spatial representations for performing relational memory and advanced cognition [Whittington et al., 2020]. Hence, it is highly expected to explore an effective algorithm for training SNNs involved with topology relations and structural knowledge.

∗Contribute equally, †Corresponding author

Recently, there exists some works of combining SNNs with graphic scenarios, whereas these studies mainly focused on applying graph theory to analyze the features of spiking neuron and network topology [Piekniewski, 2007; Cancan, 2019; Jovanovi´c and Rotter, 2016], or using the features of spiking neurons to solve simple graph-related problems, such as the shortest path problems, clustering problems, minimal spanning tree problems [Sala and Cios, 1999; Hamilton et al., 2020]. More recently, the work [Gu et al., 2020] introduced a graph convolution to pre-process tactile data and trained an SNN classifier. Although they achieved high performance on the classification of sensor data, this method is difficult to accommodate general graph operations and transfer to other scenarios. On the other hand, plenty of GNN models have been developed, such as Graph Convolution Network (GCN) and Graph Attention Network (GAT), and obtained remarkable progress in solving graph-related tasks [Kipf and Welling, 2019; Veliˇckovi´c et al., 2017]. While few works considered the relationship between graph theory and neural dynamics, and most of them suffered from a huge computational overhead when applied in scenarios with large-scale data, potentially limiting practical applications.

To explore the feasibility and advantages of spiking dynamics for handling graph-structured data, here we report a graph SNN framework capable of processing non-Euclidean data with general operations by introducing versatile aggregation methods. To develop such SNN models, two main challenges need to overcome. The first is to reconcile multiple graph convolution operations and spiking dynamics. To this end, we firstly unfold the data flows of binary node features along the temporal dimension and spatial dimension, and propose a general spiking message passing method incorporating graph filter and spiking dynamics in an iterative manner. The second is to ensure the training convergence and performance for graph SNNs. Because of the complex spiking dynamics and diverse graph operations, directly training SNNs on graph is still rarely researched and challenging. Although various normalization techniques have demonstrated their powerful effectiveness for the network convergence [Ioffe and Szegedy, 2015; Ba et al., 2016], it is difficult to apply these techniques directly to graph SNNs especially owning to temporal neuronal dynamics and binary communication mechanism [Zheng et al., 2020]. Therefore, it is necessary to develop a new normalization method suitable for spiking dynamics and graph scenarios. To address this problem, we propose a spatial-temporal feature normalization algorithm (STFN) by normalizing instant membrane potentials corresponding to each node in feature dimension and temporal dimension. In this manner, SNNs can gain a powerful capacity for abstracting hidden features from aggregated signals in a graph. Overall, our contributions are summarized as follows:

• We build a general spike-based modeling framework, referred to as Graph SNNs, to support spike propagation and feature affine transformation by reconciling the graph convolution operation and spiking communication mechanism. The framework is transferable and can accommodate most of graph propagation operations. To our best knowledge, this is the first work to build a general spike-based framework for processing regular graph tasks in gradient-descent paradigm.
• We propose a spatial-temporal feature normalization algorithm (STFN), which can incorporate the temporal neuronal dynamics and coordinate the membrane potential representation with threshold, demonstrating a significant improvement on convergence and performance.
• We instantiate the proposed framework into several models (GC-SNN and GA-SNN) and demonstrate their performance by multiple experiments on the semisupervised node classification tasks. We further evaluate the computation costs and demonstrate high-efficiency benefits which may bring new opportunity to unlock SNNs potentials and facilitate graph-structured applications for neuromorphic hardware.

2 Graph Spiking Neural Networks

We introduce our Graph SNN framework mainly from following four aspects: (1) an approach to accommodate graph convolution operation into spiking computing paradigm; (2) an iterative spiking message passing model and the overall training framework containing two phases; (3) the spatialtemporal feature normalization for facilitate convergence; (4) instantiations of specific spiking graph model.

2.1 Spiking Graph Convolution

Given an attributed graph G = (V, E), V is the set of nodes, and E is the set of edges. Generally, the graph attributes can be described by an adjacent matrix A ∈ RN×N and a node feature matrix X ∈ RN×C = [x1; x2; ...; xN], where each row of X represents the feature vector of each node xi and the adjacent matrix A satisfies Aii = 0. Assume the single node signal is represented as a scalar vector x ∈ RC , the spectral convolution is defined as the multiplication of a filter Fθ = diag(θ) and node signal x as below:

where Fθ is parameterized by θ ∈ RC , U is the eigenvector matrix of Laplacian matrix L = I - D- 1 2 AD- 1 2 = UΛU ⊤. U ⊤x can be regarded as the graph Fourier transform of x, and the diagonal matrix of eigenvalues Λ can be filtered by the function Fθ(Λ). Due to the expensive computation overhead, some work proposed to use approximation and stacked multiple nonlinear layers to circumvent it, which has been applied successfully recently [Kipf and Welling, 2019].

To unify the information flows in spiking dynamics, we encode initial node signals X into binary components { ˜X0, ˜X1, ..., ˜Xt, ..., ˜XT-1}, where T signifies the length of time window. The encoding method can be probabilistic, such as following a Bernoulli distribution or Poisson distribution, and can also be deterministic, such as quantitative approximation or using an encoding layer to generate spikes [Wu et al., 2019]. In this manner, we can transform an attributed graph from its initial state into a spiking expression. We use ˜Hn t to represent the spiking node embedding in the nth layer at time t, and ˜H0 t = ˜Xt (tilde denotes binary variable in spike form). Then the layer-wise spiking graph convolution in spatial-temporal domain can be defined as:

where Gc(A, ˜H) denotes the spiking feature propagation on the topology connection structure, which can be implemented via various propagation methods, such as Chebyshev filter, 1st model, etc. Φ(·) is the non-linear dynamic process related to historical states ˜Hn t-1 . W n ∈ RCn-1×Cn is the layerwise trainable weight parameter matrix, where C n denotes the output dimension of spiking feature in the nth layer and C 0 = C. We use the formula (2) to represent one spiking graph convolution layer. And multi-layer-stacked structure can form a comprehensive spiking dynamics system.

2.2 Iterative SpikingMessage Passing

We adopt the leaky integrate-and-fire (LIF) model as our basic neuron unit, which is computationally tractable and most commonly used, meanwhile maintaining biological fidelity to a certain degree. Its neuronal dynamics can be governed by:

where V (t) denotes the neuronal membrane potential at time t. τ is a time constant and I(t) signifies the pre-synaptic input, which is obtained by the combined action of synaptic weights and pre-neuronal activities or external injecting stimulus. When V (t) exceeds a certain threshold Vth, the neuron emits a spike and resets its membrane potential to Vreset, then starts to accumulate V (t) again in subsequent time steps.

The spiking message passing process includes information propagation step and update step, both of which run for T time steps. Let ˜Ht = [˜h0t ; ˜h1t ; ...; ˜hN-1 t ] ∈ RN×C , for the node v, we provide a universal formulation for its spiking message passing as:

where P(·) represents the spiking message aggregation for neighbouring nodes, which can be implemented by different graph convolution operation Gc(·). U(·) represents the state update via a non-linear dynamic system. N(v) denotes all the neighbors of node v in graph G, and evu denotes the static edge connection between v and u, which can be extended to directed multigraph formalism trivially. Equation (2) is a specific implementation of the above universal expression.

To accommodate the LIF model into the above paradigm, we use Euler method to transform the first-order differential equation of Eq.(3) into an iterative expression. We use a decay factor κ to represent the item (1 - dt τ ) and expand the pre-synaptic input I as ∑j W j Gc(A, ˜Hj t+1 ). Note that here we use graph convolution to realize propagation step P(·), then we obtain the following formulation via incorporating the scaling effect of dt τ into weight item:

Gc(A, ˜Hj t+1 ) denotes the corresponding pre-synaptic aggregated feature and the superscript j denotes pre-synapse index.

By incorporating firing-and-resetting mechanism and assuming Vreset = 0, the update equation can be formulated as:

where n denotes the nth layer and l(n) denotes its corresponding neuron number. W ij represents synaptic weight from jth neuron in pre-layer to ith in post-layer. g(·) is Heaviside step function. In this manner, we convert the implicit differential function into an explicit iterative version, which can describe the message propagation and update process in formula (4) and Figure 1.

Additionally, we find that the computation order of affine transformation and graph convolution can be exchanged when the graph convolution operation is linear (e.g. Gc(A,H) = D- 12AD- 1 2H). Considering that W is quite dense, ˜H is very sparse and binary, the prioritizing calculation for ˜H and W will reduce computation overhead by turning multiplication into addition. In this situation, the process (6) can be re-formulated as:

In this manner, we provide a universal spiking passing framework in iterative manner. By specializing Gc(·), most of proposed graph convolution operations [Kipf and Welling, 2019;

Gilmer et al., 2017; Hamilton et al., 2017] can be incorporated into this compatible model. And this framework is transferable to other graph scenarios.

2.3 Spatial-temporal Feature Normalization

Due to the additional temporal dynamics and event-driven spiking binary representation, traditional normalization techniques cannot be applied to the SNN framework directly. Moreover, on the other hand, the convergence and performance cannot be guaranteed by directly training SNNs on graph tasks. Therefore, it motivates us to propose a spatialtemporal feature normalization (STFN) algorithm specialized for the spiking dynamics on graph scenarios.

Considering the feature map calculation step, let St ∈ RN×C represent the instant outputting membrane potential of all neurons in a layer at time step t (∑l(n) j W n,ij Gc(A, ˜Hn-1,j t ) in formula (6) or ∑l(n) j W n,ij ˜Hn-1,j t in formula (8)). In STFN, the presynaptic inputs will be normalized along the feature dimension C independently for each node. Considering that the temporal effects play a significant role in operating node features transformation in topology space, we simultaneously normalize along the temporal dimension at consecutive time steps. Let Sk,v t represent the kth element in feature vector of a node v. Sk,v t will be normalized by

where ρ is a hyper-parameter optimized in the training process and ϵ is a tiny constant. λk,v and γ k,v are two trainable parameter vectors for node v. E[Sv ] and V ar[Sv ] denote the mean and variance of node v statistically computed over feature dimension and temporal dimension, respectively. Figure 2 depicts the computation process of E[Sv ] and V ar[Sv ], which are defined as follows:

We follow the above schema and find the normalization can facilitate convergence, improve performance in training.

2.4 Graph SNNs Framework

Our framework includes two phases: spiking message passing and readout, wherein the spiking message passing phase is described in Section 2.2. After the T times of iteration for the inference process are finished, the output spiking signals need to be decoded and transformed into high-level representations for downstream tasks. Under the rate coding condition, the readout phase computes the decoded feature vector for the whole graph using readout function R according to

Here, the readout function operates on the set of node states and should be invariant to permutations of the node states in order that Graph SNNs can be invariant to graph isomorphism. Besides, the readout function can be implemented via multiple approaches, such as using a differentiable function or neural network that maps to an output.

As shown in Figure 1, the first phase of our framework contains two unfolding domains, i.e., spatial domain and temporal domain. In the temporal domain, we utilize the encoded binary node spikes as the current node feature at time step t. A sequence of binary information will be processed successively, where the historical information for each neuron plays a key role in spiking dynamics and the decoding for output. In the spatial domain, the spiking features of a batch of nodes will be firstly aggregated via connected edges from one-hop neighbors, where the propagation operation is compatible with multiple proposed methods. Then the aggregated features will be fed into the spiking network module. In each network module, we conduct STFN to normalize the instant outputting membrane potential along the feature and temporal dimension, which ensures the node features of all dimensions follow the distribution N(0, (ρVth)2 ). Each layer possesses the spatial-temporal dynamics for feature abstracting and mapping, and the stacked multi-layer structure will empower SNNs stronger representation capability. The inference procedure is provided in Supplementary Materials.

We take the semi-supervised learning task as example for illustration. With a small subset of node labels available, we evaluate the cross-entropy error over all labeled examples:

where σ(·) denotes softmax function, YL represents the set of node indices possessing labels. Ylr denotes the real labels corresponding to the rth dimension of C L classes. In order to train the Graph SNN models effectively via gradient descent paradigm, we adopt the gradient substitution method in backward path [Wu et al., 2018] and take the rectangular function to approximate the derivative of spike activity.

2.5 Model Instantiating: GC-SNN and GA-SNN

To demonstrate the effectiveness of our framework and normalization technique, we instantiate the framework into specific models by introducing specifically designed propagation methods most used in GNNs: graph convolution aggregator and graph attention mechanism [Kipf and Welling, 2019; Veliˇckovi´c et al., 2017]. In this case, our Graph convolution Spiking Neural Network (GC-SNN) can be formulated as:

where N(i) is the set of neighbors of node i, cij is the product of square root of node degrees (i.e. cij = √| N(i) |√| N(j) |). bn is a trainable bias parameter. Similarly, our Graph Attention Spiking Neural Network (GASNN) can be expressed as:

where fl(·) denotes LeakyReLu(·) function. an is a learnable weight vector and || denotes the concatenation operation. The core idea is to conduct attention mechanism on graph convolution and learn different importance degree α for each node. We exhibit the results of the above models for illustration in the experiment section.

3 Experiments

In this section, We firstly investigate the capability of our models over semi-supervised node classification on three citation datasets to examine their performance. Then we demonstrate the effectiveness of the proposed STFN and provide some analysis visualization for the model efficiency. We provide the experimental configuration details in Supplementary Materials.

3.1 Datasets and Pre-processing

We use three standard citation network benchmark datasetsCora, Pubmed, and Citeseer, where nodes represent paper documents and edges are (undirected) citation links. We summarize the dataset statistics in Supplementary Materials. Note that from bag-of-words model, the features can be represented as binary vectors, which is equipped with similar attributes with spike representation. Here, we take the binary representation as spike vector, and re-organized them as an assembling sequence set w.r.t timing, where each component vector is considered equal at different time step for simplicity. In this manner, the original signals can be processed and treated as spiking signals.

3.2 Performance and Analysis

Basic Performance. For fairness, we take the same settings for GNN models (GCN, GAT) and our SNN models (GCSNN, GA-SNN), and also keep the settings of each dataset same. We report our results for 10 trials in Table 1. The results suggest that even if using binary spiking communication, our SNN models can achieve comparable performance with the SOTA results with a minor gap. It proves the feasibility and powerful capability of spiking mechanism and spatial-temporal dynamics, which can bind diversiform features from different nodes and work well on graph scenarios with few labels.

The Effects of STFN. We further visualize the data distribution in Figure 3(a), which indicates that the STFN can push the feature distribution to follow a larger standard deviation controlled by the threshold. In this case, the normalized membrane potential state can coordinate distribution difference and spike-triggered threshold. We find that this method contributes to the stability of performance via multiple experiments. Additionally, we plot the comparison curves for test accuracy and loss during the training process(Figure 3(b)(c)) on Citeseer. It also indicates that STFN can accelerate convergence, alleviate over-fitting, and significantly improve the performance on semi-supervised learning tasks.

The Effects of TimeWindow. We conduct multiple experiments with different time window lengths. As depicted in Figure 4(a), a longer time window length will benefit for the accuracies progressively, while the dependency on time window length is not prominent. Evidently, our model can still achieve comparable results even with a small time window and training cost.

3.3 Efficiency

As presented in Figure 4(b), because we use the second layer for decoding and determining, the neuron activity density is much higher than that in the first layer. In the overall training process, the highest averaged firing rate is no more than 20%, and the overwhelming majority of neurons fire less than 10% (see Appendix), verifying the prominent sparsity of spike features. More details are provided in Supplementary Materials.

We compare the affine transformation costs of GNN network and SNN network with 2-layer structure on three datasets, respectively. As shown in Figure 4(c), our SNN models have no addition operation and achieve far fewer multiplication operations than GNN models (compression ratio 11.62× ∼ 23.00×). In Table 2, the advantages become more prominent with deeper and larger network structure where the compression ratio become 39.46× ∼ 53.61×. Fundamentally, the spike communication and even-driven computation underlie the efficiency advantage of SNNs. On the one hand, the binary spiking feature can transform the matrix manipulation with dense weights from multiplication into addition, where the energy consumption for addition is less than multiplication on neuromorphic hardware. On the other hand, the event-driven characteristics enable sparse firing and representation for node features, reducing the operation costs by a large margin. Besides, since the spike-based communication and local computation can be fully leveraged by neuromorphic hardware which adopts distributing memory and self-contained computational units in decentralized manycore architecture, our model provides a templet promoting the graphic application for neuromorphic computing.

4 Conclusion

In this work, we report a general SNN framework for graphstructured data with an iterative spiking message passing method. By proposing the STFN method, we incorporate the graph propagation and spiking dynamics into one unified paradigm and reconcile them in a collaborative mode. Our framework is flexible and transferable for various propagation operations and scenarios, and we instantiate it into two specific models for demonstrations: a GC-SNN for graph convolution and a GA-SNN for graph attention. The experimental results on three benchmark datasets demonstrate the model effectiveness and powerful representation capability. More importantly, Graph SNNs possess high-efficiency advantages conducive to the implementation on neuromorphic hardware and applications for graphic scenarios. Overall, this work sheds new light on spiking dynamics research interacted with graphic topology, which may facilitate the understanding for advanced cognitive intelligence.

Acknowledgments

This work was supported by National Key R&D Program of China (2018YFE0200200), National Nature Science Foundation of China (No61836004), Beijing Science and Technology Program (Z191100007519009) and CAAI-Huawei MindSpore Open Fund.