Permutation-Routed Dendrites for Long-Horizon Spiking Graph Networks

Spiking neural networks are networks of units that communicate through sparse binary pulses ("spikes"). They are cheap to run on event-driven hardware, but they are hard to train on long sequences: the learning signal shrinks each time it is passed backward through a time step. When these networks are placed on a graph, so that each node is a spiking unit exchanging messages with its neighbours over time, a second and largely unnoticed source of shrinkage appears. The usual way a node combines its neighbours' signals is averaging. Averaging is a contraction: every spatial pattern except the uniform one is damped at every step. Over many steps, only the graph-wide average of the signal can still receive credit from the loss.

We propose to route memory across the graph by permuting it rather than averaging it. Each node keeps a non-leaky "dendritic" memory compartment, a second internal state that holds information while the main state fires and resets. At each time step this compartment is handed to exactly one neighbour, following a schedule of permutations taken from the graph's symmetry group or, for arbitrary graphs, from a colouring of its edges into matchings. A product of permutations is still a permutation. The backward signal through this memory therefore keeps its size exactly, in every spatial pattern, over any horizon, and it costs no multiplications. On symmetric graphs, the Fourier transform over the symmetry group makes this precise: we can predict ahead of time which spatial patterns lose credit under averaging and how fast. That prediction is the analytical spine of the project.

Core Claim

In a recurrent spiking graph network, gradient vanishing depends on the spatial pattern. With an averaging operator $\hat A$ in the temporal recurrence, the backward signal for a graph-frequency mode $j$ is multiplied by roughly $|\lambda_j|$ at each step on top of the neuron's own leak, where $\lambda_j$ is the corresponding eigenvalue of $\hat A$. For a circulant (Cayley) graph on the cyclic group $\mathbb{Z}_n$ with symmetric generator set $S$, these eigenvalues are given exactly by the discrete Fourier transform:

$$\lambda_j = \frac{1}{|S|}\sum_{s \in S} \cos\!\left(\frac{2\pi j s}{n}\right), \qquad j = 0,\dots,n-1,$$

so $|\lambda_j| < 1$ for every mode except the uniform one ($j=0$). Credit for a non-uniform pattern placed $k$ steps in the past decays like $|\lambda_j|^k$, even when the neuron model itself has been repaired. We replace the averaging recurrence with a permuted, non-leaky dendrite:

$$U^D_t = P_{t}\,U^D_{t-1} + W_D X_t - \gamma\, S_{t-1}, \qquad \frac{\partial U^D_t}{\partial U^D_{t-k}} = P_t P_{t-1}\cdots P_{t-k+1}.$$

Here $U^D_t$ is the vector of dendritic potentials across nodes, $P_t$ is the permutation applied at step $t$ (a generator of the symmetry group, or one matching from an edge colouring), $W_D X_t$ is the input current, $S_{t-1}$ the spikes of the somatic compartment, and $\gamma$ a partial-reset strength. The Jacobian product is a permutation, so all of its singular values equal one. Spatial mixing still happens, but through composition over time: a signal from node $u$ reaches node $v$ after the word in the generators that maps $u$ to $v$. It does not happen by blending.

Relation to Prior Work

The neuron-level remedies motivate this proposal and also supply its parts. TC-LIF splits each neuron into a dendrite with no decay and a soma that resets fully, and proves the gradient's infinity-norm stays at or above one. CLIF adds a complementary potential that restores the path cut by hard resets. LRMM builds a four-neuron loop that circulates context without leakage. Rhythm-SNN shortens the backward path by switching neurons off periodically. All four act on a single neuron or a local circuit and say nothing about what the graph operator does to the gradient. We reuse TC-LIF's non-leaky dendrite and add the missing graph-level guarantee.

The closest cross-direction works are spiking graph networks on curved spaces. MSG derives a closed-form manifold gradient, called Differentiation via Manifold, that removes the backward-through-time recursion. GSG trains with Riemannian SGD and likewise avoids backpropagation through time. Both are evaluated on static node classification. Both avoid temporal credit assignment rather than solving it, so they do not address tasks where the input is itself a long sequence on the graph. BT-SNN avoids gradients altogether with random search over connectome-shaped networks. We keep exact gradients and backpropagation through time and change the operator instead.

The algebraic graph literature supplies the analysis tool. The Lovász number of random circulant graphs uses DFT diagonalization of circulant graphs to turn a semidefinite program into decoupled frequency-domain constraints. We use the same diagonalization to split the temporal gradient into independent graph modes. The classifications of tri-Cayley graphs over groups of order pq, cubic bi-Cayley graphs over semidihedral groups, and 4-valent tri-Cayley graphs over cyclic groups give explicit families with several vertex orbits. On these families the "graph Fourier modes" are no longer single sinusoids, which makes them a harder test of the analysis. iGNN shows that graph models trained on small structures can generalize to structures up to six times larger, and we borrow that size-generalization protocol.

DSD constrains our design. It stabilizes long-horizon training by projecting out the dominant singular direction of each layer's gradient, at a cost of about 3% clean accuracy on CIFAR-10. Our analysis predicts a specific failure for this method on averaging spiking graph networks. The dominant direction there is the uniform graph mode, which is exactly the one mode that still carries long-horizon credit, so deflating it should remove what little long-range learning remains.

Research Program

The work has three parts.

The first is analysis. We will linearize the surrogate-gradient backward pass of a two-compartment spiking graph layer on circulant and bi-/tri-Cayley graphs. For circulant graphs we will derive per-mode attenuation in closed form. For multi-orbit Cayley graphs we will derive the corresponding block form using the group's representations. The analysis must also cover two complications. The somatic reset term $\gamma S_{t-1}$ couples back into the dendrite. Firing rates differ across nodes, which breaks exact symmetry. We will bound how far the Jacobian moves from a permutation as a function of $\gamma$ and the surrogate slope.

The second is construction. For Cayley graphs, the permutation schedule cycles through the generators. For arbitrary graphs, we colour the edges with at most one more colour than the maximum degree. Each colour class is a matching, so it defines a permutation that swaps matched pairs and leaves other nodes fixed. Cycling through the colours gives a norm-preserving schedule on any graph, at the cost of losing the exact Fourier analysis. We will compare a fixed schedule with one where the order is learned, relaxed over the colour classes during training and made hard at test time.

The third is measurement. Gradients will be logged per graph mode, task accuracy recorded, and energy estimated with synaptic-operation counts. We follow the literature's convention here and state plainly that these are counts, not chip power measurements.

Baselines

The naive reference point is a vanilla LIF spiking graph network whose temporal recurrence uses the normalized adjacency. A second reference is a model that throws timing away entirely. For that one we quote the spike-count classifiers from The Heidelberg Spiking Data Sets: about 55% on SHD with a linear SVM and about 20% on SSC. Beating the vanilla network shows the problem exists. Beating the count classifier is only a sanity floor.

The strongest competitor on the actual question is the same spiking graph network with the averaging recurrence kept and the neurons replaced by TC-LIF or CLIF. This configuration fixes leak and reset at the neuron, which is the dominant explanation of vanishing in the literature. The proposal claims a residual, graph-level failure that this configuration cannot fix. LRMM circuits placed at each node form a second strong competitor. On PS-MNIST, which has no graph, LRMM reports 96.52% and TC-LIF 95.36%. We will rerun both inside our pipeline rather than quote across pipelines. No reported result was found on Lacuna for TC-LIF or LRMM on SHD or SSC. The comparison numbers available there are an optimized recurrent SNN with augmentation at 83.2%, a baseline recurrent SNN at 71.4%, and an LSTM at 85.7% on SHD; on SSC the baseline recurrent SNN reaches 50.9% and the LSTM 75.0%, all from The Heidelberg Spiking Data Sets.

Where MSG's closed-form gradient can be applied to sequential inputs, we will run it as a representative of the approach that avoids backpropagation through time. A dense recurrent layer with orthogonal initialization will test whether norm preservation alone, without graph symmetry, explains any gain.

For fairness, all models will be matched on parameter count, number of time steps, surrogate function, and training epochs. Each will receive the same hyperparameter search budget, the same number of trials, and five seeds. The key ablation keeps every component fixed and swaps only the permutation for the averaging operator inside the same non-leaky dendrite; this isolates the routing. Further ablations remove the partial reset and compare fixed with learned schedules.

The proposal beats the strongest baseline if two things hold. On the delayed-relay task, accuracy at long delays must stay high where the TC-LIF/CLIF averaging network falls to chance. On SHD and SSC, it must exceed the rerun TC-LIF/CLIF graph networks by more than seed variance and approach the 85.7% and 75.0% LSTM figures at a fraction of the synaptic-operation cost.

Why not just…?

Why not just put TC-LIF or CLIF neurons into an ordinary spiking graph network? This is the main threat. If neuron-level fixes are enough, the graph routing adds nothing. The proposal's analysis says they are not enough. Those fixes act on each node separately and act identically on every graph mode, so the $|\lambda_j|^k$ decay from averaging survives. The relay experiment below tests this directly, because it places the needed information in a non-uniform pattern. If the TC-LIF averaging network solves long delays there, the core claim is wrong and we will report it as such.

Why not just use a learned orthogonal recurrent matrix instead of a permutation? An orthogonal dense recurrence also preserves gradient norm, and on a single small graph it may match us on accuracy. The proposal makes two claims beyond accuracy. The first is efficiency: a permutation costs no multiplications and keeps spike-like routing, whereas a dense matrix costs $n^2$ operations per step. The second is structural generalization: a permutation schedule defined by group generators transfers unchanged to a larger graph of the same family, and a learned dense matrix does not. Accordingly, we test size generalization by training on $\mathbb{Z}_n$ and Cayley graphs with small $n$ and testing on larger $n$, following the protocol of iGNN. If orthogonal recurrence also generalizes, the symmetry contribution shrinks to efficiency alone, and we will say so.

Why not just avoid backpropagation through time, using MSG's closed-form gradient or BT-SNN's random search? MSG's closed form relies on integrating an ODE over a fixed graph with a static input. Its authors leave long-range sequential tasks open, and the file reports no MSG accuracy numbers even on its static benchmarks. Random search as in BT-SNN works for small connectome networks but provides no descent direction as parameter counts grow. We will include MSG wherever its formulation applies to streaming input, and let the relay and SHD results decide the comparison.

Why not just deflate the dominant gradient direction with DSD? DSD addresses sharp curvature, not lost credit. On averaging graph networks, our analysis predicts it removes the uniform mode, which is the only mode still carrying long-horizon signal. We will run DSD on both operators. The prediction is that it hurts long-delay relay accuracy under averaging and is much less harmful under routing, where credit is spread across modes. A different outcome would show our mode analysis is missing something.

Proposed Experiments

The decisive experiment is a delayed relay on Cayley graphs. A spike burst arrives at a source node; after a delay $k$ swept from 10 to 1000 steps, a readout at a different node must report which source fired and what pattern it carried. Graphs come from circulant families on $\mathbb{Z}_n$ and from the bi-/tri-Cayley families cited above. For each model we log gradient norms projected onto each graph mode as a function of $k$ and check them against the predicted $|\lambda_j|^k$ curves. Routing should yield flat curves; averaging should yield curves whose slopes match the eigenvalue formula even with TC-LIF neurons. A mismatch between measured and predicted slopes would mean the linearization misses the reset coupling, and that alone is worth reporting.

The second experiment applies the method to real event data on a fixed sensor graph. SHD and SSC come from a simulated cochlea with frequency-ordered channels. We arrange the channels on a path graph, plus a ring variant, and use the edge-colouring schedule. Baselines and success criteria are as set out above. The third experiment is the size-generalization and DSD-interaction study already described, together with synaptic-operation accounting against the LSTM and the dense orthogonal recurrence.

The idea fails cleanly under either of two outcomes. One is that the TC-LIF averaging network matches routing at long delays on the relay task. The other is that routing helps on relay but not on SHD and SSC, which would mean graph-mode decay is real but irrelevant to tasks people care about. Either outcome is informative, and the per-mode gradient logs will show which explanation applies.