summaries: Liquid State Machines (LSM)  circumvents the need for backpropagation and allows the training of recurrent neural networks by local plasticity in the readout weights. Previous studies have shown that optimal performance is achieved near a critical phase transition of the reservoir (the liquid). However, the exact parameters of the critical phase transition in the liquid vary and depend on the input. In this work, the authors present a biologically inspired model that allows self-organization near the critical transition. Here, the authors propose a biologically inspired model in which the liquid self-organizes near the critical point. The model is composed of a reservoir of integrate-and-fire neurons. The synaptic efficacies within have unsupervised spike-time dependent plasticity (STDP). The authors propose an additional dynamical variable akin to the activity of astrocytes in the circuit, which modifies the STDP learning rates. The model self-organizes close to the critical point. The authors train several networks on the MNIST and N-MNIST dataset (a spiking version of MNIST, made for neuromorphic computing). They show that the SLM model with astrocyte-dependent STDP plasticity outperforms other LSM models.

summaries: The authors propose of a way modulating the connections in a liquid state machine (LSM) so that it moves towards the edge of chaos (EOC) to maximize its performance for various tasks. They do this using by introducing an additional "astrocyte" that modulates the parameters of STDP in the neuron model -- specifically the depression term. The authors compare their model to other forms of LSMs.

summaries: This paper extends liquid state machine (LSM) with a biologically inspired astrocyte model (NALSM) to optimize the neuronal dynamics in LSM at the edge-of-chaos, to improve the accuracy and stability of LSMs. With NALSM, the spiking model can maintain a high accuracy without re-tuning parameters for different datasets. Experiments with MNIST and N-MNIST dataset demonstrate that NALSM outperforms classic LSM and other STDP-based LSM approaches, and most existing spiking neuron models including multi-layer SNNs.

summaries: This paper presents a novel type of liquid state machine - neuron-astrocyte liquid state machine (NALSM), which introduces feedback from the network activity to the synaptic plasticity. The proposed mechanism helps to position the liquid (reservoir) layer in the edge-of-chaos dynamics regime, a known key factor to achieve good computational performance. The main contribution of this paper is transforming a biological observation (the role played by astrocytes for modulating the synaptic plasticity) into a novel idea of modulating the liquid activity. It uses feedbacks to obtain edge-of-chaos property in liquid state machine (LSM), and further showing meaningful improvement over the previously proposed LSM-based methods for real-world tasks.

summaries: The paper proposes a new version of LSM by adding a factor intended to mimic a proposed role for astrocytes: modulating STDP. The effect is homeostatic in nature and works to keep the network in a computationally efficient regime. It works. The result is a higher performance on MNIST and N-MNIST data sets.

abstractText: The liquid state machine (LSM) combines low training complexity and biological plausibility, which has made it an attractive machine learning framework for edge and neuromorphic computing paradigms. Originally proposed as a model of brain computation, the LSM tunes its internal weights without backpropagation of gradients, which results in lower performance compared to multi-layer neural networks. Recent findings in neuroscience suggest that astrocytes, a long-neglected non-neuronal brain cell, modulate synaptic plasticity and brain dynamics, tuning brain networks to the vicinity of the computationally optimal critical phase transition between order and chaos. Inspired by this disruptive understanding of how brain networks self-tune, we propose the neuron-astrocyte liquid state machine (NALSM)1 that addresses under-performance through self-organized near-critical dynamics. Similar to its biological counterpart, the astrocyte model integrates neuronal activity and provides global feedback to spike-timing-dependent plasticity (STDP), which self-organizes NALSM dynamics around a critical branching factor that is associated with the edge-of-chaos. We demonstrate that NALSM achieves state-of-the-art accuracy versus comparable LSM methods, without the need for data-specific hand-tuning. With a top accuracy of 97.61% on MNIST, 97.51% on N-MNIST, and 85.84% on Fashion-MNIST, NALSM achieved comparable performance to current fully-connected multi-layer spiking neural networks trained via backpropagation. Our findings suggest that the further development of braininspired machine learning methods has the potential to reach the performance of deep learning, with the added benefits of supporting robust and energy-efficient neuromorphic computing on the edge.

authors:
Jack D. Kendall
Suhas Kumar

title: The building blocks of a brain-inspired computer

venue: Applied Physics Reviews,

authors:
Guangzhi Tang
Neelesh Kumar
Konstantinos P. Michmizos

title: Reinforcement co-learning of deep and spiking neural networks for energy-efficient mapless navigation with neuromorphic hardware

venue: In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),

authors:
Mike Davies
Narayan Srinivasa
Tsung-Han Lin
Gautham Chinya
Yongqiang Cao
Sri Harsha Choday
Georgios Dimou
Prasad Joshi
Nabil Imam
Shweta Jain
Yuyun Liao
Chit-Kwan Lin
Andrew Lines
Ruokun Liu
Deepak Mathaikutty
Steven McCoy
Arnab Paul
Jonathan Tse
Guruguhanathan Venkataramanan
Yi-Hsin Weng
Andreas Wild
Yoonseok Yang
Hong Wang

title: Loihi: A neuromorphic manycore processor with on-chip learning

venue: IEEE Micro,

authors:
Guangzhi Tang
Arpit Shah
Konstantinos P. Michmizos

title: Spiking neural network on neuromorphic hardware for energy-efficient unidimensional slam

venue: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),

authors:
Keyan Cao
Yefan Liu
Gongjie Meng
Qimeng Sun

title: An overview on edge computing research

venue: IEEE Access,

authors:
Jiasi Chen
Xukan Ran

title: Deep learning with edge computing: A review

venue: Proceedings of the IEEE,

authors:
Wolfgang Maass
Thomas Natschläger
Henry Markram

title: Real-time computing without stable states: A new framework for neural computation based on perturbations

venue: Neural Computation,

title: Deep liquid state machines with neural plasticity for video activity recognition

venue: Frontiers in Neuroscience,

authors:
Wachirawit Ponghiran
Gopalakrishnan Srinivasan
Kaushik Roy

title: Reinforcement learning with low-complexity liquid state machines

authors:
Qian Wang
Peng Li

title: D-lsm: Deep liquid state machine with unsupervised recurrent reservoir tuning

venue: In 2016 23rd International Conference on Pattern Recognition (ICPR),

authors:
Shiya Liu
Lingjia Liu
Yang Yi

title: Quantized reservoir computing on edge devices for communication applications

venue: In 2020 IEEE/ACM Symposium on Edge Computing (SEC),

authors:
Shiming Li
Lei Wang
Shiying Wang
Weixia Xu

title: Liquid state machine applications mapping for noc-based neuromorphic platforms

venue: Advanced Computer Architecture,

authors:
Bon Woong Ku
Yu Liu
Yingyezhe Jin
Sandeep Samal
Peng Li
Sung Kyu Lim

title: Design and architectural co-optimization of monolithic 3d liquid state machine-based neuromorphic processor

venue: 55th ACM/ESDA/IEEE Design Automation Conference (DAC),

authors:
Josep L. Rosselló
Miquel L. Alomar
Antoni Morro
Antoni Oliver
Vincent Canals

title: Highdensity liquid-state machine circuitry for time-series forecasting

venue: International Journal of Neural Systems,

authors:
Ismael Balafrej
Jean Rouat

title: P-critical: A reservoir autoregulation plasticity rule for neuromorphic hardware, 2020

authors:
Simon Brodeur
Jean Rouat

title: Regulation toward self-organized criticality in a recurrent spiking neural reservoir

venue: Artificial Neural Networks and Machine Learning – ICANN

authors:
Yingyezhe Jin
Peng Li

title: Ap-stdp: A novel self-organizing mechanism for efficient reservoir computing

venue: In 2016 International Joint Conference on Neural Networks (IJCNN),

authors:
D. Norton
D. Ventura

title: Preparing more effective liquid state machines using hebbian learning

venue: IEEE International Joint Conference on Neural Network Proceedings,

authors:
Robert Legenstein
Wolfgang Maass

title: Edge of chaos and prediction of computational performance for neural circuit models

venue: Neural Networks,

authors:
Nils Bertschinger
Thomas Natschläger

title: Real-time computation at the edge of chaos in recurrent neural networks

title: Computation at the edge of chaos: phase transitions and emergent computation

venue: Physica D: Nonlinear Phenomena,

authors:
Woodrow L. Shew
Hongdian Yang
Shan Yu
Rajarshi Roy
Dietmar Plenz

title: Information capacity and transmission are maximized in balanced cortical networks with neuronal avalanches

venue: Journal of Neuroscience,

authors:
Lucilla de Arcangelis
Hans J. Herrmann

title: Learning as a phenomenon occurring in a critical state

venue: Proceedings of the National Academy of Sciences,

authors:
Osame Kinouchi
Mauro Copelli

title: Optimal dynamical range of excitable networks at criticality

venue: Nature Physics,

authors:
Clayton Haldeman
John M. Beggs

title: Critical branching captures activity in living neural networks and maximizes the number of metastable states

venue: Phys. Rev. Lett.,

authors:
John M. Beggs
Dietmar Plenz

title: Neuronal avalanches in neocortical circuits

authors:
Oren Shriki
Jeff Alstott
Frederick Carver
Tom Holroyd
Richard N.A. Henson
Marie L. Smith
Richard Coppola
Edward Bullmore
Dietmar Plenz

title: Neuronal avalanches in the resting meg of the human brain

title: Emergent complex neural dynamics

title: Synaptic mechanisms for plasticity in neocortex

venue: Annual Review of Neuroscience,

authors:
Nigel Stepp
Dietmar Plenz
Narayan Srinivasa

title: Synaptic plasticity enables adaptive selftuning critical networks

venue: PLOS Computational Biology, 11(1):1–28,

authors:
Friedemann Zenke
Wulfram Gerstner

title: Hebbian plasticity requires compensatory processes on multiple timescales

venue: Philosophical Transactions of the Royal Society B: Biological Sciences,

authors:
Alanna Watt
Niraj Desai

title: Homeostatic plasticity and stdp: keeping a neuron’s cool in a fluctuating world

venue: Frontiers in Synaptic Neuroscience,

authors:
L.F. Abbott
Sacha B. Nelson

title: Synaptic plasticity: taming the beast

venue: Nature Neuroscience,

authors:
Gertrudis Perea
Alfonso Araque

title: Glia modulates synaptic transmission

venue: Brain Research Reviews,

authors:
Xiaoning Han
Michael Chen
Fushun Wang
Martha Windrem
Su Wang
Steven Shanz
Qiwu Xu
Nancy Ann Oberheim
Lane Bekar
Sarah Betstadt

title: Forebrain engraftment by human glial progenitor cells enhances synaptic plasticity and learning in adult mice

venue: Cell Stem Cell,

authors:
Shivendra Tewari
Vladimir Parpura

title: A possible role of astrocytes in contextual memory retrieval: An analysis obtained using a quantitative framework

venue: Frontiers in Computational Neuroscience,

authors:
Marta Navarrete
Alfonso Araque

title: Endocannabinoids potentiate synaptic transmission through stimulation of astrocytes

authors:
Adar Adamsky
Adi Kol
Tirzah Kreisel
Adi Doron
Nofar Ozeri-Engelhard
Talia Melcer
Ron Refaeli
Henrike Horn
Limor Regev
Maya Groysman

title: Astrocytic activation generates de novo neuronal potentiation and memory enhancement

authors:
Francesco Petrelli
Glenn Dallérac
Luca Pucci
Corrado Calì
Tamara Zehnder
Sébastien Sultan
Salvatore Lecca
Andrea Chicca
Andrei Ivanov
Cédric S. Asensio
Vidar Gundersen
Nicolas Toni
Graham William Knott
Fulvio Magara
Jürg Gertsch
Frank Kirchhoff
Nicole Déglon
Bruno Giros
Robert H. Edwards
Jean-Pierre Mothet
Paola Bezzi

title: Dysfunction of homeostatic control of dopamine by astrocytes in the developing prefrontal cortex leads to cognitive impairments

venue: Molecular Psychiatry,

authors:
Tiina Manninen
Ausra Saudargiene
Marja-Leena Linne

title: Astrocyte-mediated spike-timingdependent long-term depression modulates synaptic properties in the developing cortex

venue: PLOS Computational Biology, 16(11):1–29,

authors:
Jérémie Sibille
Ulrike Pannasch
Nathalie Rouach

title: Astroglial potassium clearance contributes to short-term plasticity of synaptically evoked currents at the tripartite synapse

venue: The Journal of Physiology,

authors:
Rogier Min
Thomas Nevian

title: Astrocyte signaling controls spike timing–dependent depression at neocortical synapses

authors:
Alexander Stanley Thrane
Vinita Rangroo Thrane
Douglas Zeppenfeld
Nanhong Lou
Qiwu Xu
Erlend Arnulf Nagelhus
Maiken Nedergaard

title: General anesthesia selectively disrupts astrocyte calcium signaling in the awake mouse cortex

authors:
Jeannine Foley
Tamara Blutstein
SoYoung Lee
Christophe Erneux
Michael M. Halassa
Philip Haydon

title: Astrocytic ip3/ca2+ signaling modulates theta rhythm and rem sleep

venue: Frontiers in Neural Circuits,

authors:
Laura Bojarskaite
Daniel M. Bjørnstad
Klas H. Pettersen
Céline Cunen
Gudmund Horn Hermansen
Knut Sindre Åbjørsbråten
Rolf Sprengel
Koen Vervaeke
Wannan Tang
Rune Enger
Erlend A. Nagelhus

title: Astrocytic ca2+ signaling is reduced during sleep and is involved in the regulation of slow wave sleep

venue: Nature Communications,

authors:
Ashley M. Ingiosi
Christopher R. Hayworth
Daniel O. Harvey
Kristan G. Singletary
Michael J. Rempe
Jonathan P. Wisor
Marcos G. Frank

title: A role for astroglial calcium in mammalian sleep and sleep regulation

venue: Current Biology,

authors:
Enzo Tagliazucchi
Dante R. Chialvo
Michael Siniatchkin
Enrico Amico
Jean-Francois Brichant
Vincent Bonhomme
Quentin Noirhomme
Helmut Laufs
Steven Laureys

title: Largescale signatures of unconsciousness are consistent with a departure from critical dynamics

venue: Journal of The Royal Society Interface,

authors:
Timothy Bellay
Andreas Klaus
Saurav Seshadri
Dietmar Plenz

title: Irregular spiking of pyramidal neurons organizes as scale-invariant neuronal avalanches in the awake state. eLife

authors:
Gerald Hahn
Adrian Ponce-Alvarez
Cyril Monier
Giacomo Benvenuti
Arvind Kumar
Frédéric Chavane
Gustavo Deco
Yves Frégnac

title: Spontaneous cortical activity is transiently poised close to criticality

venue: PLOS Computational Biology, 13(5):1–29,

authors:
Viola Priesemann
Mario Valderrama
Michael Wibral
Michel Le Van Quyen

title: Neuronal avalanches differ from wakefulness to deep sleep – evidence from intracranial depth recordings in humans

venue: PLOS Computational Biology, 9(3):1–14,

authors:
Erik D. Fagerholm
Romy Lorenz
Gregory Scott
Martin Dinov
Peter J. Hellyer
Nazanin Mirzaei
Clare Leeson
David W. Carmichael
David J. Sharp
Woodrow L. Shew
Robert Leech

title: Cascades and cognitive state: focused attention incurs subcritical dynamics

authors:
Vladimir Parpura
Philip G. Haydon

title: Physiological astrocytic calcium levels stimulate glutamate release to modulate adjacent neurons

authors:
Catherine A. Christian
John R. Huguenard

title: Astrocytes potentiate gabaergic transmission in the thalamic reticular nucleus via endozepine signaling

authors:
Sara Mederos
Candela González-Arias
Gertrudis Perea

title: Astrocyte–neuron networks: a multilane highway of signaling for homeostatic brain function

authors:
Eiji Shigetomi
Sandip Patel
Baljit S. Khakh

title: Probing the complexities of astrocyte calcium signaling

venue: Trends in Cell Biology,

authors:
Gertrudis Perea
Mriganka Sur
Alfonso Araque

title: Neuron-glia networks: integral gear of brain function

venue: Frontiers in Cellular Neuroscience,

authors:
Y. Lecun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

authors:
Garrick Orchard
Ajinkya Jayawant
Gregory K. Cohen
Nitish Thakor

title: Converting static image datasets to spiking neuromorphic datasets using saccades

authors:
Han Xiao
Kashif Rasul
Roland Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017

authors:
Abigail Morrison
Markus Diesmann
Wulfram Gerstner

title: Phenomenological models of synaptic plasticity based on spike timing

venue: Biological Cybernetics,

authors:
Wenrui Zhang
Peng Li

title: Information-theoretic intrinsic plasticity for online unsupervised learning in spiking neural networks

authors:
Wolfgang Maass
Robert Legenstein
Nils Bertschinger

title: Methods for estimating the computational power and generalization capability of neural microcircuits

venue: In Proceedings of the 17th International Conference on Neural Information Processing Systems,

authors:
Parami Wijesinghe
Gopalakrishnan Srinivasan
Priyadarshini Panda
Kaushik Roy

title: Analysis of liquid ensembles for enhancing the performance and accuracy of liquid state machines

authors:
Joschka Boedecker
Oliver Obst
Joseph T Lizier
N Michael Mayer
Minoru Asada

title: Information processing in echo state networks at the edge of chaos

venue: Theory Biosci.,

authors:
Andre S. Ribeiro
Stuart A. Kauffman
Jason Lloyd-Price
Björn Samuelsson
Joshua E.S. Socolar

title: Mutual information in random boolean models of regulatory networks

venue: Phys. Rev. E,

authors:
Łukasz Kuśmierz
Shun Ogawa
Taro Toyoizumi

title: Edge of chaos and avalanches in neural networks with heavy-tailed synaptic weight distribution

authors:
C. van Vreeswijk
H. Sompolinsky

title: Chaos in neuronal networks with balanced excitatory and inhibitory activity

title: Two types of asynchronous activity in networks of excitatory and inhibitory spiking neurons

authors:
Kanaka Rajan
L.F. Abbott
Haim Sompolinsky

title: Stimulus-dependent suppression of chaos in recurrent neural networks

authors:
Bin Zhou
Yun-Xia Zuo
Ruo-Tian Jiang

title: Astrocyte morphology: diversity, plasticity, and role in neurological diseases

venue: CNS Neuroscience & Therapeutics,

authors:
Dongcheng Zhao
Yi Zeng
Tielin Zhang
Mengting Shi
Fei fei Zhao

title: Glsnn: A multi-layer spiking neural network based on global feedback alignment and local stdp plasticity

authors:
Arash Samadi
T. Lillicrap
D. Tweed

title: Deep learning with dynamic spiking neurons and fixed feedback weights

authors:
Tielin Zhang
Yi Zeng
Dongcheng Zhao
Bo Xu

title: Brain-inspired balanced tuning for spiking neural networks

venue: In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence,

authors:
Peter Diehl
Matthew Cook

title: Unsupervised learning of digit recognition using spike-timingdependent plasticity

title: Supervised learning based on temporal coding in spiking neural networks

venue: IEEE Transactions on Neural Networks and Learning Systems,

authors:
Maryam Mirsadeghi
Majid Shalchian
Saeed Reza Kheradpisheh
Timothée Masquelier

title: Stidi-bp: Spike time displacement based error backpropagation in multilayer spiking neural

venue: networks. Neurocomputing,

authors:
Jun Haeng Lee
Tobi Delbruck
Michael Pfeiffer

title: Training deep spiking neural networks using backpropagation

authors:
Yujie Wu
Lei Deng
Guoqi Li
Jun Zhu
Luping Shi

title: Spatio-temporal backpropagation for training high-performance spiking neural networks

authors:
Jacques Kaiser
Hesham Mostafa
Emre Neftci

title: Synaptic plasticity dynamics for deep continuous local learning (decolle)

authors:
Qianhui Liu
Haibo Ruan
Dong Xing
H. Tang
Gang Pan

title: Effective aer object classification using segmented probability-maximization learning in spiking neural networks

venue: In AAAI,

authors:
S. Shrestha
G. Orchard

title: Slayer: Spike layer error reassignment in time

venue: In NeurIPS,

authors:
Tielin Zhang
Yi Zeng
Dongcheng Zhao
Mengting Shi

title: A plasticity-centric approach to train the non-differential spiking neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Yunzhe Hao
Xuhui Huang
Meng Dong
Bo Xu

title: A biologically plausible supervised learning method for spiking neural networks using the symmetric stdp rule

authors:
Saeed Reza Kheradpisheh
Maryam Mirsadeghi
Timothée Masquelier

title: BS4NN: binarized spiking neural networks with temporal coding and learning

authors:
Han Ju
Jian-Xin Xu
Edmund Chong
Antonius M.J. VanDongen

title: Effects of synaptic connectivity on liquid state machine performance

authors:
Filip Ponulak
Andrzej Kasiński

title: Supervised learning in spiking neural networks with resume: Sequence learning, classification, and spike shifting

venue: Neural Comput.,

authors:
Robert Urbanczik
Walter Senn

title: A Gradient Learning Rule for the Tempotron

venue: Neural Computation, 21(2):340–352,

authors:
Robert Gütig
Haim Sompolinsky

title: The tempotron: a neuron that learns spike timing–based decisions

authors:
Guangzhi Tang
Ioannis E. Polykretis
Vladimir A. Ivanov
Arpit Shah
Konstantinos P. Michmizos

title: Introducing astrocytes on a neuromorphic processor: Synchronization, local plasticity and edge of chaos

venue: ACM Proceedings of 2019 Neuroinspired Computing Elements (NICE 2019),

authors:
Alex Roxin
Nicolas Brunel
David Hansel
Gianluigi Mongillo
Carl van Vreeswijk

title: On the distribution of firing rates in networks of cortical neurons

authors:
Woodrow L. Shew
Hongdian Yang
Thomas Petermann
Rajarshi Roy
Dietmar Plenz

title: Neuronal avalanches imply maximum dynamic range in cortical networks at criticality

authors:
Friedemann Zenke
Guillaume Hennequin
Wulfram Gerstner

title: Synaptic plasticity in neural networks needs homeostasis with a fast rate detector

venue: PLOS Computational Biology, 9(11):1–14,

authors:
Michael M. Halassa
Philip G. Haydon

title: Integrated brain circuits: astrocytic networks modulate neuronal activity and behavior

venue: Annual Review of Physiology,

title: Neuron-astrocyte interactions: partnership for normal function and disease in the central nervous system

venue: Mayo Clinic Proceedings,

authors:
Dionysia T. Theodosis
Dominique A. Poulain
Stéphane H.R. Oliet

title: Activity-dependent structural and functional plasticity of astrocyte-neuron interactions

venue: Physiological Reviews,

heading: 1 Introduction

text:
With the recent rise of neuromorphic [1–4] and edge computing [5, 6], the liquid state machine (LSM) learning framework [7] has become an attractive alternative [8–11] to deep neural networks owing to its compatibility with energy-efficient neuromorphic hardware [12–14] and inherently low training complexity. Originally proposed as a biologically plausible model of learning, LSMs avoid training via backpropagation by using a sparse, recurrent, spiking neural network (liquid) with fixed synaptic connection weights to project inputs into a high dimensional space from which a single neural layer can learn the correct outputs. Yet, these advantages over deep networks come at the expense of 1) sub-par accuracy and 2) extensive data-specific hand-tuning of liquid weights. Interestingly, these
1Code and data available at https://github.com/combra-lab/NALSM
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
two limitations have been targeted by several studies that tackle one [15, 16] or the other [17, 18], but not both. This has limited the widespread use of LSMs in real-world applications [8]. In that sense, there is an unmet need for a unified, brain-inspired approach that is directly applicable to the emerging neuromorphic and edge computing technologies, facilitating them to go mainstream.
As a general heuristic, LSM accuracy is maximized when LSM dynamics are positioned at the edgeof-chaos [19–21] and specifically in the vicinity of a critical phase transition [22–25] that separates: 1) the sub-critical phase, where network activity decays, and 2) the super-critical (chaotic) phase, where network activity gets exponentially amplified. Strikingly, brain networks have also been found to operate near a critical phase transition [26–28] that is modeled as a branching process [25, 26]. Current LSM tuning methods organize network dynamics at the critical branching factor by adding forward and backward communication channels on top of the liquid [15, 16]. This, however, results in significant increases in training complexity and violates the LSM’s brain-inspired self-organization principles. For example, these methods lack local plasticity rules that are widely observed in the brain and considered a key component for both biological [29] and neuromorphic learning [3, 2, 4]. A particular local learning rule, spike-timing-dependent plasticity (STDP), is known to improve LSM accuracy [17, 18]. Yet, current methods of incorporating STDP into LSMs further exacerbate the limitations of data-specific hand-tuning as they require additional mechanisms to compensate for the STDP-imposed saturation of synaptic weights [17, 30–33]. This signifies the scarcity of LSM tuning methods that are both computationally efficient and data-independent.
A long-neglected non-neuronal cell in the brain, astrocytes, is now known to play key roles in modulating brain networks [34–39], from modifying synaptic plasticity [40–42] to facilitating switching between cognitive states [43–46] that have been linked to a narrow spectrum of dynamics around the critical phase transition [47–51]. The mechanisms that astrocytes use to modulate neurons include the integration of the activity of thousands of synapses into a slow intracellular continuous signal that feeds back to neurons by affecting their synaptic plasticity [52–55, 42]. The unique spatiotemporal attributes [56, 57] identified in astrocytes align well with the brain’s remarkable ability to self-organize its massive and highly recursive networks near criticality. That is why astrocytes present a fascinating possibility of forming a unified feedback modulation mechanism required to improve baseline LSM accuracy while eliminating data-specific hand-tuning.
Here, we propose the neuron-astrocyte liquid state machine (NALSM), where a biologically inspired astrocyte model organized liquid dynamics near a critical phase transition, by modulating STDP. We show that NALSM combined the computational benefits of both STDP and critical branching dynamics by demonstrating its accuracy advantage compared to other LSM methods on two datasets: 1) MNIST [58], and 2) N-MNIST [59]. We demonstrate that, similar to its biological counterpart that handles new and unstructured information with robustness and versatility, NALSM maintains the state-of-the-art LSM performance without re-tuning training parameters for each tested dataset. We also show that a NALSM with a large enough liquid can attain comparable accuracy to fully-connected multi-layer spiking neural networks trained via backpropagation on 1) MNIST [58], 2) N-MNIST [59], as well as 3) Fashion-MNIST [60]. Our results suggest that the under-performance and high training difficulty of current neuromorphic methods can be addressed by harvesting neuroscience knowledge and further translating biological principles to computational mechanisms.

heading: 2 Methods

heading: 2.1 The neuron-astrocyte liquid state machine

text:
To construct the NALSM, we started with a baseline LSM model consisting of 2 layers: 1) a spiking liquid, and 2) a linear output layer. Next, we added STDP to the LSM liquid, forming the LSM+STDP model. We developed a biologically faithful leaky-integrate-and-modulate (LIM) astrocyte model, which we embedded in the LSM+STDP liquid, to form the NALSM. The process is formalized below.
LSM Model We implemented the baseline LSM as a 3-dimensional neural network (liquid) consisting of 1, 000 neurons surrounded by 1-dimensional layers of input and output neurons. Number of input neurons was 784 and 2, 312 for MNIST and N-MNIST, respectively (See Appendix A.1). We used the leaky-integrate-and-fire (LIF) model [3] for input and liquid neurons, modeled as:
dvi dt = − 1 τv vi(t) + ui(t)− θiσi(t) (1)
ui(t) = ∑ j 6=i wij(αu ∗ σj)(t) + bi (2)
where vi is the membrane potential and ui is the synaptic response current of neuron i, θi is the membrane potential threshold, σi(t) = ∑ k δ(t − tki ) is the spike train of neuron i with tki being the time of the k-th spike, wij is the weight connecting neuron j to i, bi is the bias of neuron i, and αu(t) = τ−1u exp(−t/τu)H(t) is the synaptic filter with H(t) being the unit step function (See Appendix A.2). All LIF neurons had a 2 ms absolute refractory period. Liquid neurons were excitatory and inhibitory with 80%/20% ratio. Input neurons did not have an excitatory/inhibitory distinction and had random excitatory and inhibitory connections to liquid neurons. From here on, we will refer to connections between input neurons and liquid neurons as IL connections, inter-liquid connections as LL, and liquid to output connections as LO. In line with [7], we created LL connections using probabilities based on Euclidean distance, D(i, j), between any two neurons i, j:
P (i, j) = C · exp ( − ( D(i, j)
λ
)2) (3)
with closer neurons having higher connection probability. Parameters C and λ set the amplitude and horizontal shift, respectively, of the probability distribution (See Appendix A.3). Density of IL connections was 15%. The output layer was a dense layer consisting of 10 linear neurons.
LSM+STDP Model We added unsupervised, local learning to the LSM model by letting STDP change each LL and IL connection [61], modeled as:
dw dt = A+Tpre ∑ o δ(t− topost)−A−Tpost ∑ i δ(t− tipre) (4)
where A+ = A− = 0.15 are the potentiation/depression learning rates and Tpre/Tpost are the pre/post-synaptic trace variables, modeled as,
τ∗+ dTpre dt = −Tpre + a+ ∑ i δ(t− tipre) (5)
τ∗− dTpost dt = −Tpost + a− ∑ o δ(t− topost) (6)
where a+ = a− = 0.1 are the discrete contributions of each spike to the trace variable, τ∗+ = τ ∗ − = 10 ms are the decay time constants, tipre and t o post are the times of the pre-synaptic and post-synaptic spikes, respectively. We constrained connection weights to: 1) IL: [−3, 3] , 2) excitatory LL: [0, 3], and 3) inhibitory LL: [−3, 0]. We used the same STDP parameters for all models and experiments.
LIM Astrocyte Model We developed the astrocyte model as a leaky integrator with a continuous output value Aastro− , expressed as:
τasto dAastro− dt = −Aastro− + wastro ∑ i∈Nliq δ(t− ti)− wastro ∑ j∈Ninp δ(t− tj) + bastro (7)
where Aastro− directly mapped to A− in equation (4), bastro = A+ adjusted the astrocyte output to the fixed STDP potentiation learning rate, Nliq and Ninp are the sets of liquid and input neurons, respectively, andwastro set astrocyte responsiveness to network activity (See Appendix A.4). Ignoring the decay and bias terms, the astrocyte model computed the difference in the number of spikes produced by liquid neurons and input neurons. Functionally, this is equivalent to computing the ratio of spikes emitted by the liquid over the input neurons:
BFproxy(t) = ∑ i∈Nliq δ(t− ti)∑ j∈Ninp δ(t− tj)
(8)
Specifically, when the liquid produced more spikes than the input neurons, their difference was positive which translated to BFproxy > 1.0, and vice versa. This approach to measure liquid dynamics acted as a network level approximation of the branching factor, σBF , which is normally
evaluated for each neuron (See 2.3.1). We empirically confirmed that BFproxy = 1.0 aligned with the critical branching factor, σBF = 1.0 (Fig. 1 B). Hence, as dynamics became progressively supercritical (σBF > 1.0), BFproxy became greater than 1, which caused the LIM astrocyte to increase STDP depression learning rate above the fixed STDP potentiation learning rate (Aastro− → A− > A+). This caused STDP to decrease the average weight of LL and IL connections, which decreased number of spikes produced by the liquid and made dynamics less super-critical (Fig. 1 B). The reverse occurred as dynamics became progressively sub-critical. As a result of astrocyte modulation, liquid dynamics oscillated between sub-critical and super-critical until eventual stabilization near the critical branching factor (See Appendix A.4).
NALSM Model We completed NALSM by adding the LIM astrocyte to the LSM+STDP model’s liquid (Fig. 1 A). As described above, the LIM astrocyte integrated activity from input and liquid neurons, and continuously controlled the STDP depression learning rate.

heading: 2.2 Training

text: Model training was done in 3 steps: 1) initialization of IL and LL liquid connections, 2) passing all data through the liquid resulting in liquid neuron spike counts, and 3) training the output layer on the spike counts. The steps are further detailed below.

heading: 2.2.1 Liquid initialization

text:
LSM We initialized all IL and LL connections with a single weight value, maintaining originally defined connection signs [62]. Weights were constant during spike count collection.
LSM+STDP We initialized IL and LL connections with STDP by consecutively presenting all the training images to the liquid. Starting with initially maximal connections, 3(−3) for excitatory(inhibitory) connections, we let STDP continuously adjusted weights while presenting the liquid with a randomly ordered series of MNIST training image snapshots, each lasting 20 ms. For N-MNIST, we randomly sampled each 20 ms snapshot from the 0 − 250 ms range, as a way to account for the variability in the temporal dimension (See 2.3). In each case, we used a total of 50, 000 snapshots, each corresponding to a unique training image. We used STDP only for weight initialization. Initialized weights were fixed during spike count collection.
NALSM We used the LSM+STDP weight initialization process with the exception of added STDP modulation by the LIM astrocyte. We used this set of initialized weights as the starting point for each sample in the spike counting phase, during which astrocyte-modulated STDP continued to adjust synaptic weights to compensate for slight deviations in dynamics caused by each input sample’s different level of activity. For each sample, parameters A+ from (4) and bastro from (7) were both initialized to 0.15 and decayed at a rate of 0.99 for the duration of sample input.

heading: 2.2.2 Output layer training

text:
We assembled spike counts by presenting each sample image to the liquid for 250 ms and counting the number of spikes emitted by each liquid neuron for the full duration of input. We used Adam optimizer to batch train the output layer on spike count vectors by minimizing the cross entropy loss with L2-regularization,
L(yi, ŷ) = − 1
m m∑ i=1 yilog(ŷi) + (1− yi)log(1− ŷi) + λreg 2m ||Wout||2F (9)
where m = 250 is the batch size, Wout is the output layer weight matrix, λreg = 5× 10−10 is the regularization hyperparameter, yi and ŷi are the normalized vectors denoting the predicted label and the target label, respectively. Prior to training, we initialized output layer weights/biases to 0.0, and the learning rate to 0.1. We trained the output layer until validation accuracy peaked (up to a maximum of 5, 000 epochs), at which point we evaluated model test accuracy.

heading: 2.3 Experiments

text:
We performed all LSM comparison experiments on MNIST and N-MNIST datasets (See A.1). Using 10 randomly generated networks for each dataset, we trained 1) the baseline LSM model, 2) the LSM+STDP model, 3) the NALSM model (See 2.1), and 4) the LSM+AP-STDP model, a method for incorporating STDP in the LSM liquid [17] (See Appendix A.5). First, we evaluated LSM model accuracy with respect to liquid weight, which ranged in 0.4 − 1.2 for MNIST and 0.8 − 1.35 for N-MNIST. We used a random seed for each training session. Next, we evaluated corresponding network dynamics of each network/weight combination by measuring the liquid’s branching factor on 20 randomly sampled inputs (See 2.3.1). To have comparable results for each network, we trained the remaining models using the same seed that resulted in peak LSM accuracy. For NALSM, we used the same initialization and parameters for all networks and datasets. For LSM+AP-STDP, we hand-tuned STDP control parameters for each network and dataset combination to maximize validation accuracy (See Appendix A.5). Additionally, we trained NALSM on Fashion-MNIST dataset (See A.1) using the same 10 randomly generated networks that we had used for MNIST.
Sparse neuron-astrocyte connectivity We tested NALSM’s accuracy as a function of neuronastrocyte connection density on 3 best performing networks (per dataset). Keeping the proportion of neurons sampled by the astrocyte the same for both input neurons and liquid neurons, we trained NALSM with 10%, 20%, 40%, 60%, and 80% neuron-astrocyte density over 3 seeds for each of 3 networks. Regardless of connection sparseness, all IL/LL connections were modulated by Aastro− (See 2.1)
NALSM with larger liquid sizes We tested NALSM performance for larger liquids. For each size, we trained 3 randomly generated networks, each on a random seed. All parameters and initialization were same as for 1, 000 neuron liquid. For maximum accuracy, we trained NALSM with an 8, 000 neuron liquid. For each dataset, we used 5 randomly generated networks trained on a random seed. Parameter wastro = 0.0075 for all datasets. All other parameters and initialization were as before.

heading: 2.3.1 Branching factor of liquid

text: To evaluate a liquid’s dynamics, we used the network branching factor, σBF , which quantifies network information flow amplification/decay. Liquid dynamics are sub-critical, near-critical and super-critical when σBF < 1.0, σBF ≈ 1.0, and σBF > 1.0. We calculated σBF as done in [30], with offset φ = 0 and time window ∆ = 4 ms as per [26].

heading: 2.3.2 Kernel quality of liquid

text: We evaluated liquid 1) linear separation, and 2) generalization capability using methods from [63]. For the MNIST and N-MNIST test sets, we computed the rank of matrix M assembled from k randomly selected spike count vectors, resulting in shape Nliq × k. We repeated this on 1, 000 shuffles of spike vectors. For linear separation, we used spike counts from model testing phase. For generalization capability, we added noise to input data and evaluated new spike count vectors (See 2.2.2). For MNIST, we added N (0, 125) noise to each pixel value. For N-MNIST, we time-shifted each event by N (0, 10). Taken together across all models and both datasets, we rescaled ranks of each measure to 0− 1 range and subtracted measure 1 from measure 2 as in [63]. Due to negative differences, we again rescaled all differences to 0− 1.

heading: 3 Results

heading: 3.1 Baseline LSM performance

text: We established a benchmark accuracy for the baseline LSM on MNIST and N-MNIST datasets (See 2.3). We acquired our baseline by averaging over 10 randomly generated liquids with 1, 000 neurons (See 2.1). The LSM achieved a top accuracy of 95.44% (95.30± 0.11%) on MNIST, and 95.35% (95.02± 0.15%) on N-MNIST (See 2.2). For MNIST, this was comparable to the previously reported state-of-the-art LSM accuracy [64], using the same sized liquid. Further, LSM accuracy was very sensitive to the liquid’s weight (Fig. 2 A).

heading: 3.2 LSM performance peaked at the critical branching factor

text:
The peak LSM accuracy on each dataset corresponded to a different liquid synaptic weight. Specifically, there were cases where a liquid with weights tuned for maximum accuracy on MNIST, would catastrophically fail on N-MNIST (Fig. 2 A). Also, LSM accuracy on MNIST plateaued for a wider
range of weights than on N-MNIST, which can be attributed to N-MNIST’s greater difficulty caused by its variability over the temporal dimension (See Appendix A.1). Taken together, this indicated that LSM training requires extensive hand-tuning of weights for each specific dataset.
Since critical dynamics are well known to result in near-maximum LSM performance [65, 19–21], dataset-specific hand-tuning can be significantly reduced by replacing accuracy with liquid dynamics as the target output of weight tuning. Indeed, LSM accuracy was near-maximum for both datasets, when the liquid’s branching factor was in 1.0− 1.2 range, or slightly super-critical (Fig. 2 B) (See 2.3.1). This agrees with studies showing that information transfer in finite sized systems peaks at slightly super-critical dynamics [66]. Although each dataset still had different weight ranges corresponding to the critical branching factor, the relationship between liquid dynamics and weight was positive for both datasets (Fig. 2 C). Known to generalize beyond specific datasets [20], this relationship suggested that near-critical dynamics can be organized using STDP, by providing it directional feedback from current liquid dynamics.

heading: 3.3 Astrocyte-modulated plasticity organized liquid dynamics near criticality

text: The LIM astrocyte model stabilized liquid dynamics near the critical branching factor as we presented a continuous stream of samples to the neuron-astrocyte liquid (Fig. 2 B). The NALSM’s slightly super-critical stabilization suggested that liquid dynamics were at the edge-of-chaos. While chaotic activity is known to correspond to super-critical branching dynamics in some cases [25], such correspondence is not guaranteed. Hence, we examined additional network properties that are necessary and indicative of chaotic activity (See Appendix A.6). Specifically, the astrocyte-modulated liquid had coexistence of small and large synaptic weights (Fig. S2), as well as a balance of excitation and inhibition, both of which are necessary for the existence of chaotic network activity [67, 68]. Further supporting a chaotic activity, the neuron-astrocyte liquid spike activity appeared irregular (Fig. S3). We also performed autocorrelation analysis on liquid neuron spike trains, which further suggested the existence of chaotic activity with a correspondence between edge-of-chaos dynamics and critical branching dynamics (Fig. S4) [69, 70] (See Appendix A.6). Given that liquid dynamics were directly approximated by the LIM astrocyte, which directly controlled the STDP depression learning rate (See 2.1), NALSM required no dataset-specific hand-tuning. As a result, we used the same weight initialization and parameters to benchmark NALSM (See 2.3).

heading: 3.4 Benchmarking NALSM performance on MNIST and N-MNIST

text:
On both datasets, NALSM achieved superior performance to comparable LSM models of the same size. Using 1, 000 liquid neurons, NALSM achieved a top accuracy of 96.15% (95.96 ± 0.13%) on MNIST and 96.13% (95.90± 0.16%) on N-MNIST; outperforming LSM model’s top accuracy by 0.71% on MNIST and 0.78% on N-MNIST (Fig. 3 A). We also compared NALSM to a stateof-the-art LSM STDP method, AP-STDP (See 2.3). The LSM+AP-STDP model required more extensive dataset-specific hand-tuning than the baseline LSM due to its additional STDP control parameters (See Appendix A.5). Resulting in top accuracy of 95.62% (95.49± 0.09%) and 95.43% (95.23± 0.16%), the LSM+AP-STDP model was superseded by NALSM by 0.53% and 0.70% on MNIST and N-MNIST, respectively. As a control measure, we also trained a LSM with unregulated STDP (See 2.1). The LSM+STDP model significantly under-performed compared to all other models achieving a top accuracy of 90.52% (89.47± 0.45%) on MNIST and 87.71% (86.80± 0.51%) on N-MNIST. We attributed this under-performance to the LSM+STDP liquid’s excessive super-critical dynamics (Fig. 2 B) which are well known to decrease liquid computational capacity [65, 66].
The NALSM had the most robust accuracy performance across the two datasets out of all the compared LSM models. With no dataset-specific tuning, NALSM’s average accuracy on N-MNIST was lower than the accuracy on MNIST by only −0.05%. This was 5− 50 times less than for the LSM+AP-STDP (−0.26%), LSM (−0.29%), and LSM+STDP (−2.66%) models. We attributed the NALSM’s performance advantage to the improved computational properties of its liquid. For both tested datasets, the NALSM achieved slightly super-critical branching dynamics where baseline LSM performance peaked right before it started to decline with increasing supercritical dynamics (Fig. 2 B). This suggested that NALSM’s performance advantage, compared to a LSM with similar dynamics, was due to the addition of astrocyte-modulated STDP (See 2.1, 2.2.1). While LSM+AP-STDP and LSM+STDP models also had STDP, their lower performance can be explained by their excessively sub-critical and super-critical dynamics, respectively (Fig. 2 B). We further confirmed that NALSM’s increased performance resulted from the improved computational properties of its liquid by measuring each model’s liquid kernel quality. This encompassed both the linear separation and generalization capability of the liquid (See 2.3.2). Higher model accuracy corresponded to higher kernel quality for all 4 models (Fig. 3 B). This is a further indication that near-critical dynamics and astrocyte-modulated STDP contributed to the NALSM’s performance increase.

heading: 3.5 NALSM maintained performance with sparse neuron-astrocyte connectivity

text: The NALSM maintained its accuracy advantage even with neuron-astrocyte connection densities as low as 10% (Fig. 4). In the brain, astrocytes contact only approximately 65% of all synapses in their surroundings [71]. We tested NALSM performance as a function of neuron-astrocyte connection density (See 2.3). The NALSM mean accuracy decreased marginally with increasingly sparse connectivity, while variability in performance was minimal across densities. At 10% connectivity, average NALSM accuracy decreased by 0.36% for MNIST and 0.14% for N-MNIST compared to 100% connection density. In both cases, average NALSM accuracy was still above LSM and LSM+APSTDP average accuracy.

heading: 3.6 Larger liquids increased NALSM accuracy

text: The NALSM accuracy improved with increased liquid size, saturating at approximately 8, 000 neurons (See Appendix A.7). NALSM8000 achieved a top accuracy of 97.61% (97.49± 0.11%) on MNIST, 97.51% (97.42± 0.07%) on N-MNIST, and 85.84% (85.61± 0.18%) on Fashion-MNIST. Compared to previously reported benchmarks on MNIST and Fashion-MNIST, the NALSM8000 outperformed all brain-inspired learning methods that do not use backpropagation of gradients or its approximation through feedback alignment [72, 73], with the exception of [74] for MNIST. While [74] demonstrated that a fully-connected 2-layer spiking network can achieve high accuracy through a combination of biologically-plausible plasticity rules, it is not clear how such an approach would scale to more layers without some form of backpropagation. Conversely, multi-layered LSMs have been shown to work without backpropagation [8, 10]. Further, NALSM8000 used approximately 1/3 (≈ 1, 199, 407 ± 453) of number of trainable(plastic) connections as in [74]. Compared to top accuracies reported for fully-connected multi-layered spiking neural networks trained with backpropagation, the NALSM8000 achieved comparable performance on all datasets; outperforming multiple reported results on MNIST and N-MNIST (Table 1) (See Appendix A.8).

heading: 4 Discussion and Broader Impact

text:
Ironically, LSMs are one of the most brain-like and at the same time one of the most difficult to train learning models. Here, we proposed an astrocyte model that merged critical branching dynamics and STDP into a single liquid, thereby simultaneously improving LSM performance and decreasing data-specific tuning. We showed that the synergy of STDP and near-critical branching dynamics
improved the computational capacity of the liquid, which translated to better than state-of-the-art LSM accuracy on MNIST and N-MNIST, and do so with minimal added computational cost (See Appendix A.9). Our results indicate that, given a large enough liquid, NALSM performance compares to current fully-connected multi-layer spiking neural networks trained via backpropagation.
The reported narrowing of the performance gap between brain-inspired LSM and deep networks suggests that studying the interaction among the brain’s computational principles can help our learning models to reach human-like performance. Indeed, our results demonstrate that the synergy of braininspired astrocyte-modulated STDP and near-critical dynamics resulted in the superior performance of NALSM compared to 1) a LSM with critical dynamics but without STDP, and 2) a LSM with STDP, but without critical dynamics. Aligning with other studies showing that liquid topology impacts LSM accuracy [87], we also showed that a brain-inspired, sparse, 3D-distance-based network architecture can improve the computational capacity of a single liquid. Specifically, our baseline 3D LSM achieved comparable accuracy to the multi-liquid LSM [64], which improved performance of a single dimensionless liquid by partitioning it into multiple liquids. While we demonstrated NALSM performance using only the 3D-distance-based network architecture, our proposed astrocyte modulation method does not depend on network topology and, therefore, is applicable to other types of topology. In fact, our approach is also extendable to multi-liquid architectures and other local plasticity rules that follow STDP’s separation of potentiation and depression components.
The astrocyte-modulated LSM learning framework is also compatible with the emerging neuromorphic hardware. This is because the gradient descent that we used for training the linear output can be replaced by a single-layer spike based learning rule [88–90]. This makes NALSM compatible with neuromorphic hardware, exploiting in full its advantages [91]. For example, our method can leverage even further the energy efficiency of neuromorphic chips, by virtue of its low spiking rates. In line with biological ranges [92], NALSM had spiking rates that ranged from 12 Hz to 37 Hz, depending on the input sample. These rates can be reduced further, by modifying input encoding, since liquid spiking rates are directly adjusted by the astrocyte based on input spiking rates (Fig. 1).
Here, we demonstrated a possible connection between the near-critical branching dynamics of the NALSM liquid and the edge-of-chaos transition (See Appendix A.6). The critical branching transition has been extensively used to model critical dynamics in brain networks [27, 26]. Focusing on the computational benefits of criticality, machine learning has mostly examined network dynamics at the edge-of-chaos transition. Although the presence of one transition does not guarantee the existence of the other, both transitions are well connected to the same result, an improved computational performance [25]. Indeed, the computational performance of systems poised at a critical phase transition has been widely studied both experimentally [22] and theoretically [23], and are wellconnected to both edge-of-chaos [19, 20] and critical branching transitions [25, 15]. Networks operating at near-criticality are believed to have simultaneous access to the computational properties (learning and memory) of both phases, which results in 1) maximizing their information processing capacity [22], 2) optimizing their dynamical range [93, 24], and 3) expanding their number of metastable states [25]. Hence, it is not surprising that the NALSM’s astrocyte imposed near-critical branching dynamics resulted in improved accuracy and generalization capabilities as observed in LSMs with edge-of-chaos dynamics [19, 20], while adding the benefit of a neuromorphic compatibility and self-organized criticality.
Our work shows how insights from modern cellular neuroscience can synergize with neuromorphic computing, and lead to novel intelligent systems, spurring the dialogue between artificial intelligence and brain sciences. Indeed, given that the known neuronal mechanisms are too slow and uncoordinated in the brain to modulate STDP [31, 94, 32], it is an open question how neurons modulate synaptic plasticity. Our demonstration that the distinct temporal and spatial mechanisms of astrocytes may modulate STDP and subsequently regulate network dynamics, questions the neuron as the only processing unit in the brain [95–97]. In that sense, it helps in dismantling the 100-year old dogma that “brain = neurons”, and tackle the absence of astrocytes in both prevailing computational hypotheses on how the brain learns and efforts to translate such knowledge to effective models of intelligence.
By showing how astrocyte-modulated STDP can maximize computational performance near criticality, we aimed to broaden the applicability of the LSM to complex spatio-temporal problems that require integration of data over multiple sources and time-scales, thereby, making LSMs suitable for real-life applications of edge computing. Our so far results suggest that this is a direction worth pursuing.

heading: Acknowledgements

text: This work is supported by the National Center for Medical Rehabilitation Research (NIH/NICHD) K12HD093427 Grant and by the Rutgers Office of Research and Innovation. Any findings, conclusions, and opinions expressed in this material are those of the authors and do not necessarily reflect the views of the NIH or Rutgers University.

title: Increasing Liquid State Machine Performance with Edge-of-Chaos Dynamics Organized by Astrocyte-modulated Plasticity


summaries: The paper studied the problem of imbalanced classification on graphs, by proposing to unify the quantity imbalance and topology imbalance together. The authors develop a label propagation algorithm that locates the topological position of the labeled nodes, and then re-weight nodes to alleviate the imbalanced data distribution. Experimental results on various benchmark datasets show the performance of the proposed model.

summaries: This paper first points out the topology-imbalance problem of node representation learning on graph-structured data. To address the problem (which is denoted as Topology-Imbalance Node Representation Learning, TINL), this paper presents a conflict detection-based metric (named Totoro) based on label propagation algorithm and Personalized PageRank matrix. Then, the authors introduce the ReNode algorithm that considers the Totoro of each node in semi-supervised training of GNN models. The ample experimental results show the superiority of ReNode in addressing the TINL problem.

summaries: The issue of imbalance is a very critical problem in ML, especially in a realistic setting. In general, imbalance is quantitative, but this paper points out topological imbalance as a graph-specific problem. As a solution to topological imbalance, a method of reweighting called ReNode is proposed and its effectiveness is verified.

summaries: The authors concerns the topological imbalance problem in node classification problem. The imbalance caused by  asymmetric topological structure during the semi-supervised learning process. The authors introduces the intuition with classical label propagation problem and extended it to the case of learning GNN. To alleviate the pain of the imbalance issue the author introduced the Node reweighting loss, which puts more effort on learning with nodes that have less distance weighted conflicts.

summaries: Authors study a problem named topology imbalance which is led from the topological difference of labelled nodes in a given graph. It degrades the performance of node classifiers by 'shifting' the decision boundary. The main contributions of this paper are (1) it points out the topology imbalance problem in node classification tasks; (2) it proposes a metric (Totoro) to measure the topology imbalance; (3) it designs an annealing method to reweight samples based on their topological importance; (4) authors provide vast experimental results over multiple scenarios, datasets, and baselines.

abstractText: The class imbalance problem, as an important issue in learning node representations, has drawn increasing attention from the community. Although the imbalance considered by existing studies roots from the unequal quantity of labeled examples in different classes (quantity imbalance), we argue that graph data expose a unique source of imbalance from the asymmetric topological properties of the labeled nodes, i.e., labeled nodes are not equal in terms of their structural role in the graph (topology imbalance). In this work, we first probe the previously unknown topology-imbalance issue, including its characteristics, causes, and threats to semisupervised node classification learning. We then provide a unified view to jointly analyzing the quantityand topologyimbalance issues by considering the node influence shift phenomenon with the Label Propagation algorithm. In light of our analysis, we devise an influence conflict detection–based metric Totoro to measure the degree of graph topology imbalance and propose a model-agnostic method ReNode to address the topology-imbalance issue by re-weighting the influence of labeled nodes adaptively based on their relative positions to class boundaries. Systematic experiments demonstrate the effectiveness and generalizability of our method in relieving topology-imbalance issue and promoting semi-supervised node classification. The further analysis unveils varied sensitivity of different graph neural networks (GNNs) to topology imbalance, which may serve as a new perspective in evaluating GNN architectures.1

authors:
Reid Andersen
Fan R.K. Chung
Kevin J. Lang

title: Local Graph Partitioning using PageRank Vectors

venue: Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006),

authors:
Aleksandar Bojchevski
Johannes Klicpera
Bryan Perozzi
Amol Kapoor
Martin Blais
Benedek Rózemberczki
Michal Lukasik
Stephan Günnemann

title: Scaling Graph Neural Networks with Approximate PageRank

venue: In the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,

authors:
Eliav Buchnik
Edith Cohen

title: Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity

venue: Proc. ACM Meas. Anal. Comput. Syst.,

authors:
Mateusz Buda
Atsuto Maki
Maciej A. Mazurowski

title: A Systematic Study of the Class Imbalance Problem in Convolutional Neural Networks

venue: Neural Networks,

authors:
Kaidi Cao
Colin Wei
Adrien Gaidon
Nikos Aréchiga
Tengyu Ma

title: Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss

venue: In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems

authors:
Nitesh V Chawla
Kevin W Bowyer
Lawrence O Hall
W Philip Kegelmeyer

title: SMOTE: Synthetic Minority Over-sampling Technique

venue: Journal of artificial intelligence research,

authors:
Wei-Lin Chiang
Xuanqing Liu
Si Si
Yang Li
Samy Bengio
Cho-Jui Hsieh

title: Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

venue: In the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,

authors:
Yin Cui
Menglin Jia
Tsung-Yi Lin
Yang Song
Serge J. Belongie

title: Class-Balanced Loss Based on Effective Number of Samples

venue: In IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Michaël Defferrard
Xavier Bresson
Pierre Vandergheynst

title: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

venue: In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems

authors:
Seyda Ertekin
Jian Huang
C Lee Giles

title: Active Learning for Class Imbalance Problem

venue: In the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,

authors:
Mahsa Ghorbani
Anees Kazi
Mahdieh Soleymani Baghshah
Hamid R. Rabiee
Nassir Navab

title: RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data

venue: arXiv preprint:

authors:
Haixiang Guo
Yijing Li
Jennifer Shang
Gu Mingyun
Huang Yuanyue
Gong Bing

title: Learning from Class-Imbalanced Data: Review of Methods and Applications

venue: Expert Syst. Appl.,

authors:
William L. Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive Representation Learning on Large Graphs

venue: In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017,

authors:
Kaveh Hassani
Amir Hosein Khasahmadi

title: Contrastive Multi-View Representation Learning on Graphs

venue: In the 37th International Conference on Machine Learning,

authors:
Haibo He
Edwardo A. Garcia

title: Learning from imbalanced data

venue: IEEE Trans. Knowl. Data Eng.,

authors:
Haibo He
Yang Bai
Edwardo A. Garcia
Shutao Li

title: ADASYN: Adaptive synthetic sampling approach for imbalanced learning

venue: In the International Joint Conference on Neural Networks, IJCNN 2008, part of the IEEE World Congress on Computational Intelligence,

authors:
Chen Huang
Yining Li
Chen Change Loy
Xiaoou Tang

title: Learning Deep Representation for Imbalanced Classification

venue: In the 29th IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised Classification with Graph Convolutional Networks

venue: In the 5th International Conference on Learning Representations,

authors:
Johannes Klicpera
Aleksandar Bojchevski
Stephan Günnemann

title: Predict then Propagate: Graph Neural Networks meet Personalized PageRank

venue: In the 7th International Conference on Learning Representations,

authors:
Miroslav Kubat
Stan Matwin

title: Addressing the Curse of Imbalanced Training Sets: Onesided Selection

venue: In the 14th International Conference on Machine Learning (ICML

authors:
Wei Li
Ruihan Bao
Keiko Harimoto
Deli Chen
Jingjing Xu
Qi Su

title: Modeling the Stock Relation with Graph Network for Overnight Stock Movement Prediction

venue: In the 29th International Joint Conference on Artificial Intelligence,

authors:
Tsung-Yi Lin
Priya Goyal
Ross B. Girshick
Kaiming He
Piotr Dollár

title: Focal Loss for Dense Object Detection

venue: In IEEE International Conference on Computer Vision, ICCV 2017,

authors:
Inderjeet Mani
I Zhang

title: kNN Approach to Unbalanced Data Distributions: A Case Study Involving Information Extraction

venue: In Workshop on Learning from Imbalanced Datasets,

authors:
Julian McAuley
Christopher Targett
Qinfeng Shi
Anton Van Den Hengel

title: Image-based Recommendations on Styles and Substitutes

venue: In the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval,

authors:
Iman Nekooeimehr
Susana K Lai-Yuen

title: Adaptive Semi-unsupervised Weighted Oversampling (A-SUWO) for Imbalanced Datasets

venue: Expert Systems with Applications,

authors:
Sunil Nishad
Shubhangi Agarwal
Arnab Bhattacharya
Sayan Ranu

title: GraphReach: Position- Aware Graph Neural Networks using Reachability Estimations

venue: In the 30th International Joint Conference on Artificial Intelligence IJCAI,

authors:
Lawrence Page
Sergey Brin
Rajeev Motwani
Terry Winograd

title: The PageRank Citation Ranking: Bringing Order to the Web

venue: Technical report, Stanford InfoLab,

authors:
Nikolay G Prokoptsev
AE Alekseenko
Yaroslav Aleksandrovich Kholodov

title: Traffic Flow Speed Prediction on Transportation Graph with Convolutional Neural Networks

venue: Computer research and modeling,

authors:
Zhenyue Qin
Saeed Anwar
Dongwoo Kim
Yang Liu
Pan Ji
Tom Gedeon

title: Position- Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions

authors:
Mengye Ren
Wenyuan Zeng
Bin Yang
Raquel Urtasun

title: Learning to Reweight Examples for Robust Deep Learning

venue: In International Conference on Machine Learning,

authors:
Pengzhen Ren
Yun Xiao
Xiaojun Chang
Po-Yao Huang
Zhihui Li
Xiaojiang Chen
Xin Wang

title: A Survey of Deep Active Learning

authors:
Yu Rong
Wenbing Huang
Tingyang Xu
Junzhou Huang

title: The Truly Deep Graph Convolutional Networks for Node Classification

authors:
Prithviraj Sen
Galileo Namata
Mustafa Bilgic
Lise Getoor
Brian Galligher
Tina Eliassi- Rad

title: Collective Classification in Network Data

venue: AI magazine,

authors:
Oleksandr Shchur
Maximilian Mumme
Aleksandar Bojchevski
Stephan Günnemann

title: Pitfalls of Graph Neural Network Evaluation

authors:
Min Shi
Yufei Tang
Xingquan Zhu
David A. Wilson
Jianxun Liu

title: Multi-Class Imbalanced Graph Convolutional Network Learning

authors:
Shuhao Shi
Kai Qiao
Shuai Yang
L Wang
J Chen
Bin Yan

title: AdaGCN: Adaptive Boosting Algorithm for Graph Convolutional Networks on Imbalanced Node Classification

authors:
Marina Sokol
Konstantin Avrachenkov
Paulo Gonçalves
Alexey Mishenin

title: Generalized Optimization Framework for Graph-based Semi-supervised Learning

venue: In the 12th SIAM International Conference on Data Mining,

title: Two Modifications of CNN

venue: IEEE Transactions on Systems, Man, and Cybernetics,

authors:
Laurens Van der Maaten
Geoffrey Hinton

title: Visualizing Data using t-SNE

venue: Journal of machine learning research,

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio

title: Graph Attention Networks

venue: In 6th International Conference on Learning Representations,

authors:
Hongwei Wang
Jure Leskovec

title: Unifying Graph Convolutional Neural Networks and Label Propagation

authors:
Xinyue Wang
Bo Liu
Siyu Cao
Liping Jing
Jian Yu

title: Important Sampling based Active Learning for Imbalance Classification

venue: Science China Information Sciences,

authors:
Felix Wu
Amauri Souza
Tianyi Zhang
Christopher Fifty
Tao Yu
Kilian Weinberger

title: Simplifying Graph Convolutional Networks

authors:
Zhenqin Wu
Bharath Ramsundar
Evan N Feinberg
Joseph Gomes
Caleb Geniesse
Aneesh S Pappu
Karl Leswing
Vijay Pande

title: MoleculeNet: a Benchmark for Molecular Machine Learning

venue: Chemical science,

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How Powerful are Graph Neural Networks

authors:
Yuzhe Yang
Zhi Xu

title: Rethinking the Value of Labels for Improving Class-Imbalanced Learning

venue: In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems

authors:
Zhilin Yang
William W Cohen
Ruslan Salakhutdinov

title: Revisiting Semi-supervised Learning with Graph Embeddings

venue: In the 33nd International Conference on Machine Learning, ICML 2016,

authors:
Jiaxuan You
Rex Ying
Jure Leskovec

title: Position-aware Graph Neural Networks

venue: In the 36th International Conference on Machine Learning, ICML 2019,

authors:
Tianxiang Zhao
Xiang Zhang
Suhang Wang

title: GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks. In WSDM ’21

venue: The Fourteenth ACM International Conference on Web Search and Data Mining, Virtual Event, Israel, March 8-12,

authors:
Dengyong Zhou
Christopher J.C. Burges

title: Spectral Clustering and Transductive Learning with Multiple Views

venue: In the 24th Annual International Conference on Machine Learning, ICML 2007,

authors:
Jie Zhou
Ganqu Cui
Zhengyan Zhang
Cheng Yang
Zhiyuan Liu
Maosong Sun

title: Graph Neural Networks: A Review of Methods and Applications

venue: AI Open,

heading: 1 Introduction

text:
Graph is a widely-used data structure [51], where the nodes are connected to each other through natural or handcrafted edges. Similar to other data structures, the representation learning for node classification faces the challenge of quantity-imbalance issue, where the labeling size varies among classes and the decision boundaries of trained classifiers are mainly decided by the majority classes [46]. There have been a series of studies [35, 11, 49] handling the Quantity-Imbalance Node Representation Learning (short as QINL). However, different with other data structures, graph-structured data suffers from another aspect of the imbalance problem: the imbalance caused by the asymmetric and uneven topology of labeled nodes, where the decision boundaries are driven by the labeled nodes close to the topological class boundaries (left of Figure 1) thus interfering with the model learning.
Present Work. For the first time, we recognize the Topology-Imbalance Node Representation Learning (short as TINL) as a graph-specific imbalance learning topic, which mainly focus on the
1The code is available at https://github.com/victorchen96/ReNode.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
decision boundaries shift phenomena driven by the topology imbalance in graph and is an essential component for node imbalance learning. Comparing with the well-explored QINL that studies the imbalance caused by the numbers of labeled nodes, TINL explores the imbalance caused by the positions of labeled nodes and owns the following characteristics:
• Ubiquity: Due to the complex connections of the graph nodes, the topology structure of nodes in different categories is naturally asymmetric, which makes TINL an essential characteristic in node representation learning. Hence, it is difficult to construct a completely symmetric labeling set even with an abundant annotation budget.
• Perniciousness: The influence from labeled nodes decays with the topology distance [3]. The asymmetric topology of labeled nodes in different classes and the uneven distribution of labeled nodes in the same class will cause the influence conflict and influence insufficient problems (left of Figure 1) respectively, resulting in a shift of decision boundaries.
• Orthogonality: Quantity-imbalance studies [49, 8, 5] usually treat the labeled nodes of the same class as a whole and devise solutions based on the total numbers of each class, while TINL explores the influence of the unique position of each labeled node on decision boundaries. Thus, TINL is independent of QINL in terms of the object of study.
Exploring TINL is of great importance for node representation learning due to its ubiquity and perniciousness. However, the methods [17, 22] for quantity imbalance can be hardly applied to TINL because of the orthogonality. To remedy the topology-imbalance issue, thus promoting the node classification, we propose a model-agnostic training framework ReNode to re-weight the labeled nodes according to their positions. We devise the conflict detection-based Topology Relative Location (Totoro) metric to leverage the interaction among labeled nodes across the whole graph to locate their structural positions. Based on the Totoro metric, we further increase the training weights of nodes with small conflict that are highly likely to be close to topological class centers to make them play a more pivotal role during training, and vice versa (right of Figure 1). Empirical results of various imbalance scenarios (TINL, QINL, large-scale graph) and multiple graph neural networks (GNNs) demonstrate the effectiveness and generalizability of our method. Besides, we provide the sensitivity to topology imbalance as a new evaluation perspective for different GNN architectures.

heading: 2 Topology-Imbalance Node Representation Learning

heading: 2.1 Notations and Preliminary

text:
In this work, we follow the well-established semi-supervised node classification setting [47, 18] to conduct analyses and experiments. Given an undirected and unweighted graph G = (V ,E,L), where V is the node set represented by the feature matrixX ∈ Rn∗d (n = |V | is the node size and d is the node embedding dimension), E is the edge set which is represented by an adjacency matrix A ∈ Rn∗n, L ⊂ V is the labeled node set and usually we have |L| |V |, the node classification
task is to train a classifier F (usually a GNN) to predict the class label y for the unlabeled node set U = V −L. The training sets for different classes are represented by (C1,C2, · · · ,Ck) and k is the number of classes. The labeling ratio δ = L/V is the proportion of labeled nodes in all nodes. In this work, we focus on TINL in homogeneously-connected graphs and hope to inspire future studies on the critical topology-imbalance issue.

heading: 2.2 Understanding Topology Imbalance via Label Propagation

text:
From Figure 1, we can intuitively perceive the imbalance brought by the positions of labeled nodes; in this part, we further explore the nature of topology imbalance with the well-known Label Propagation [50] algorithm (short as LP) and provide a uniform analysis framework for the comprehensive node imbalance issue. In LP, labels are propagated from the labeled nodes and aggregated along edges, which can also be viewed as a random walk process from labeled nodes. The convergence result Y after repeated propagation is regarded as the nodes soft-labels:
Y = α(I − (1− α)A′)−1Y 0, (1)
where I is the identity matrix, α ∈ (0, 1] is the random walk restart probability,A′ = D− 12AD− 12 is the adjacency matrix normalized by the diagonal degree matrixD, Y 0 is the initial label distribution where labeled nodes are represented by the one-hot vectors. The prediction label for the i-th node is qi = arg maxj Yij . LP is a simple yet successful model [37] and can be unified with GNN models owning the message-passing mechanism [41]. From Figure 2(a), we can empirically find that there is a significant correlation between the results of LP and GCN (T/F indicates prediction is True/False).
The LP prediction q can be viewed as the distribution of the (labeled) node influence [41] (i.e. each node is mostly influenced by which class’s information); hence the boundaries of the node influence can act as an effective reflection for the GNN model decision boundaries considering the high consistency between LP and GNN. Moreover, node influence offers a unified view of TINL and QINL: ideally, the node influence boundaries should be consistent with the true class boundaries, but both the labeled nodes’ numbers (QINL) and positions (TINL) can cause a shift of the node influence boundaries from the true one, resulting in deviation of the model decision boundaries.
Node imbalance issue is composed of topology- and quantity-imbalance. Figure 2 illustrates two examples of node influence boundary shift. In Figure 2(b), when the uniform selection is adopted to generate training set, both the quantity and the topology are imbalanced for model training; then the large class with more total nodes (denotes by blue color) will own stronger influence than the small class with fewer total nodes (denotes by red color) due to the quantity advantage and the node influence boundary is shifted towards the small class. In Figure 2(c), when the quantity-balanced strategy is adopted for sampling training nodes, it will be easier for the small class to has more labeled nodes close to the class boundary and the boundary of the node influence is shifted into the large class. We can find that even when the training set is quantity-balanced, the topology-imbalance issue still exists and hinders the node classification learning. Hence, we can conclude that node imbalance
learning is caused by the joint effect of TINL and QINL. Separately considering TINL or QINL will lead to a one-sided solution to node imbalance learning.

heading: 2.3 Measuring Topology Imbalance by Influence Conflict

text:
Although we have realized that the imbalance of node topology interferes with model learning, how to measure the labeled node’s relative topological position to its class (being far away from or close to the class center) remains the key challenge in handling the topology-imbalance issue due to the complex graph connections and the unknown class labels for most nodes in the graph. As the nodes are homogeneously connected when constructing the graph, even nodes close to the class boundaries own similar characteristics to their neighbors. Thus it is unreliable to leverage the difference between the characteristics of one labeled node and its surrounding subgraphs to locate its topological position. Instead, we propose to utilize the node topology information by considering the node influence conflict across the whole graph and devise the Conflict Detection-based Topology Relative Location metric (Totoro).
Similar to Eq (1), we calculate the Personalized PageRank [27] matrix P to measure node influence distribution from each labeled node:
P = α(I − (1− α)A′)−1. (2)
Node influence conflict denotes topological position. According to related studies [41, 19, 2], P can be viewed as the distribution of influence exerted outward from each node. We assume that if a labeled node v ∈ V encounters strong heterogeneous influence from the other classes’ labeled nodes in the subgraph around node v where node v itself owns great influence, we have the conclusion that node v meets large influence conflict in message passing and it is close to topological class boundaries, and vice versa. Based on this hypothesis, we take the expectation of the influence conflict between the node v and the labeled nodes from other classes when node v randomly walks across the entire graph as a measurement of how topologically close node v is to the center of the class it belongs to. The Totoro value of node v is computed as:
Tv = Ex∼Pv,: [ ∑
j∈[1,k],j 6=yv
1 |Cj | ∑ i∈Cj Pi,x], (3)
where yv is the ground-truth label of node v, Pv indicates the personalized PageRank probability vector for the node v. A larger Totoro value Tv indicates that node v is topologically closer to class boundaries, and vice versa. The normalization item 1/|Cj | is added to make the influence from the different classes comparable when computing conflict.
We visualize the node labels and the Totoro values (scaled to [0, 1]) of labeled nodes in Figure 3(a). We can find that the labeled nodes with smaller Totoro values are farther away from the class boundaries, demonstrating the effectiveness of Totoro in locating the positions of labeled nodes. Besides, we sum
the conflict of all the labeled nodes ∑
b∈L Tv to measure the overall conflict of the dataset, which can be viewed as the metric for the overall topology imbalance given the graph G and the training set L. Figure 3(b) shows that there is a significant negative correlation between the overall conflict and the model performance, which further demonstrates the effectiveness of Totoro in measuring the intensity of topology imbalance at the dataset level.

heading: 2.4 Alleviate Topology Imbalance by Instance-wise Node Re-weighting

text:
In this section, we introduce ReNode, a model-agnostic training weight schedule mechanism to address TINL for general GNN encoder in a plug-and-play manner. Inspired by the analysis in Section 2.2, the ReNode method is devised to promote the training weights of the labeled nodes that are close to the topological class centers, so as to make these nodes play a more active role in model learning, and vice versa. Specifically, we devise a cosine annealing mechanise 2 for the training node weights based on their Totoro values:
wv = wmin + 1
2 (wmax − wmin)(1 + cos(
Rank(Tv)
|L| π)), v ∈ L (4)
wherewv is the modified training weight for the labeled node v, wmin, wmax are the hyper-parameters indicating the lower bound and upper bound of the weight correction factor, Rank(Tv) is the ranking order of Tv from the smallest to the largest. The training loss LT for the quantity-balanced, topologyimbalanced node classification task is computed by the following equations:
LT = − 1 |L| ∑ v∈L wv k∑ c=1 y∗cv log g c v, g = softmax(F(X,A,θ)), (5)
where F denotes any GNN encoder, θ is the parameter of F , gi is the GNN output for node i, y∗i is the gold label for node i in one-hot embedding. By encouraging the positive effects of the labeled nodes near the class topological centers, and reducing the negative effects of those near the topological class boundaries, our ReNode method is expected to minimize the deviation between the node influence boundaries and the true class boundaries, so as to correct the class imbalance caused by the positions of labeled nodes.
ReNode to Jointly Handle TINL and QINL In this part, we introduce the application of the ReNode method in a more general graph imbalance scenario where both the topology- and quantityimbalance issues exist. As analyzed in previous sections, the TINL and QINL are orthogonal problems. Therefore, we propose that our ReNode method based on (labeled) node topology can be seamlessly combined with the existing methods designed for the quantity-imbalance learning. Without loss of generality, we present how our ReNode method can be combined with the vanilla class frequency-based re-weight method [17]. The training loss LQ for the quantity-imbalanced, topology-imbalanced node classification task is formalized in the following equation:
LQ = − 1 |L| ∑ v∈L wv ¯|C| |Cj | k∑ c=1 y∗cv log g c v, (6)
where ¯|C| is the average number of the class training sizes. With this method, the final weight of the labeled node is affected by two perspectives: training examples of the minority classes will have higher weights than that of the majority classes; training examples close to the topological class centers will have higher weights than those are close to the topological class boundaries.
ReNode for Large-scale Graph There are mainly two challenges when applying ReNode to largescale graphs: (1) how to calculate the PageRank matrix, and (2) how to train the GNN model in an inductive setting [13]. In this work, we follow the PPRGo method [2] to implement our method on the large-scale graph, which can decouple the feature learning process from the information transmission process to resolve the dependence on the global graph topology structure and can be carried out much efficiently. Following PPRGo, the Personalized PageRank matrix P̂ and the corresponding training ReNode factor ŵ are generated by the estimation method from Andersen et al. [1] and then P̂ is
2We also try other schedules and the cosine method works best. More details can be found in Appendix B.
directly employed as the aggregation weights from all the other nodes regardless of their topology distance from the current node:
g′ = softmax(P̂F ′(X, θ′)), (7)
where F ′ can be a linear layer or a multi-layer perceptron with parameter θ′. The final training loss for large-scale graph LL follows Eq (5) and (6), and replaces w and g with ŵ and g′.

heading: 3 Experiments

text: In this section, we will first introduce the experimental datasets for both transductive and inductive semi-supervised node classification. Then we introduce the experiments to verify the effectiveness of the proposed ReNode method in three different imbalance situations: (1) TINL only, (2) TINL and QINL, (3) Large-scale Graph.

heading: 3.1 Datasets

text: We adopt two sets of graph datasets to conduct experiments. For the transductive setting [13], we take the widely-used Plantoid paper citation graphs [33] (CORA,CiteSeer, Pubmed) and the Amazon copurchase graphs [24] (Photo,Computers) to verify the effectiveness of our method. For the inductive setting, we conduct experiments on the popular Reddit dataset [13] and the enormous MAG-Scholar dataset (coarse-grain version) [2] which owns millions of nodes and features. For each of these datasets, we repeat experiments on 5 different datasets splittings [34] and we run 3 times for each splitting to reduce the random variance. More details about the datasets and experiment settings are presented in Appendix A.

heading: 3.2 ReNode for the Pure Topology-imbalance Issue

text:
Settings When considering topology-imbalance only, the labeling set takes a balanced setting and the annotation size for each class is all equal to |L|/k. Following the most widely-used semisupervised setting in node classification studies [47, 18], we randomly select 20 nodes in each class for training and 30 nodes per class for validation; all the remaining nodes form the test set. We display the experiment results for the 5 transductive datasets on 6 widely-used GNN models: GCN [18], GAT [40], PPNP [19], GraphSAGE [13] (short as SAGE), ChebGCN [9] (short as CHEB) and SGC [43]. We strictly align the hyperparameters in each group of experiments to show the pure improvement brought by our ReNode method (similarly hereinafter). The training loss LT from section 2.4 is adopted.
Results From Table 1, we can find that our ReNode method can effectively improve the overall performance (Weighted-F1) and the class-balance performance (Macro-F1) for all the 6 experiment GNNs in most cases, which proves the effectiveness and generalizability of our method. Our method considers the graph-specific topology imbalance issue which has been usually neglected in existing methods and conducts a fine-grained and self-adaptive adjustment to the training node weights based on their topological positions. We notice that the improvement for the CiteSeer dataset is less than the other datasets. We analyze the reason lies in that the connectivity of CiteSeer is poor, which makes the conflict detection–based method fail to reflect the node topological position well. To verify the motivation of relieving topology-imbalance, we set training sets with different levels of topologyimbalance to test our method3. Table 2 displays that our ReNode method improves the performance of GNN (GCN) most when the dataset is highly topologically imbalanced, which demonstrates that our method can effectively alleviate topology-imbalance and improve GNN performance.

heading: 3.3 ReNode for the Compound Scene of TINL and QINL

text:
Settings When jointly considering both topology- and quantity-imbalance issues, following existing studies [5, 4], we take the step imbalance setting, in which all the minority classes have the same labeling size ni and all the majority classes have the same labeling size na = ρ ∗ ni. The imbalance ratio ρ denotes the intensity of quantity imbalance which is equal to the ratio of the node size of the most frequent to least frequent class. In this work, the imbalance ratio ρ is set to [5, 10] for each dataset. The fraction of the majority classes is µ, and for all experiments, we set µ = 0.5 and round down the result µ ∗ k. The training loss LQ from section 2.4 is adopted. We implement two groups of baselines for comparison: (1) Popular quantity-imbalance methods for general scenarios: Re-weight [17] (RW), Focal Loss [22] (Focal) and Class Balanced Loss [8] (CB); (2) Graph-specific quantity-imbalance methods: DR-GCN [35], RA-GCN [11] and GraphSMOTE [49]. To jointly handle the topology- and quantity-imbalance issues and demonstrate the orthogonality of them, we combine our ReNode method with these three general quantity-imbalance methods (RW, Focal, CB)4. The backbone model is GCN [18], and the labeling ratio δ is set to 5%.
Results From Table 3 (Macro-F1 is reported here for a fair comparison with these methods designed for class-balance performance), we can find that our ReNode method significantly outperforms both the general and the graph-specific quantity-imbalance methods in most situations by simultaneously alleviating the topology- and quantity-imbalance issues. Even when the training set is severely quantity-imbalanced (ρ=10), our method still effectively alleviates the imbalance issue and promotes model performance well. The performance of the quantity-imbalance methods from the general field (RW, Focal, CB) is on par with or less effective than the graph-specific quantity-imbalance methods (DR-GCN, RA-GCN, G-SMOTE), while the combination of our ReNode method and these general quantity-imbalance methods can surpass the graph-specific quantity-imbalance methods, which demonstrates that the node imbalance learning can be further solved by jointly handling the topology- and quantity-imbalance issues instead of considering the quantity-imbalance issue only.
3The settings of the dataset topology-imbalance levels is shown in Appendix C. 4The three graph-specific methods have special operations for the training loss, which can be hardly combined
with our method.

heading: 3.4 ReNode for Large-scale Graphs

text:
Settings We conduct experiments on the two large-scale datasets: Reddit and MAG-Scholar, to verify the effectiveness of our ReNode method in the inductive setting. We conduct experiments with different labeling sizes (20/50/100 training nodes per class) and imbalance settings (TINL-only, TINL and QINL). The backbone GNN model is PPRGo [2] 5. For QINL, we take the uniform selection to sample training nodes to be consistent with PPRGo. The training loss LL from section 2.4 is adopted. Both baseline and our methods are not combined with any quantity-imbalance method.
Results In Figure 4, we present the experiment results with different labeling sizes and imbalance settings, we can find that our method can effectively promote the performance on the large-scale graphs comparing to the popular PPRGo model across different settings, which demonstrates the applicability of our method for extremely-large graphs. We also notice that our method can bring greater improvement when the labeling size is large. We explain the reason lies in that when the labeling size is large, the positions located by the conflicts among nodes will be more accurate, thus bringing more reasonable weight adjustments. On the other hand, when the labeling ratio is extremely small (especially for the enormous MAG-Scholar graph) and the influence conflict between the labeled nodes is negligible, our method exhibits the cold start problem.

heading: 4 Discussions

heading: 4.1 Evaluating GNNs from the Aspect of Topology-Imbalance Sensitivity

text:
In Figure 5, we evaluate the GNN’s capability for handling topology-imbalance and find that different GNNs present significant difference in the topology-imbalance sensitivity across multiple datasets. The GCN model is susceptible to the topology-imbalance level of the graph and its performance decays greatly when the topology-imbalance increases. On the opposite, the GAT model is less sensitive to the topology-imbalance level and can achieve the best results when the topology-imbalance level is high. The PPNP model can achieve ideal performance when the topology-imbalance level is low, and its performance does not drop as sharply as GCN when the topology-imbalance level is high. We analyze the reason lies in that: (1) the aggregation operation of GCN is equivalent to directly
5We do not implement other inductive backbone GNN models like Cluster-GCN [7] or APPNP [19] due to the low efficiency [2] of them when handling the enormous MAG-Scholar dataset.
averaging neighbor features [45] that lacks the noise filtering mechanism, so it is more sensitive to the topology-imbalance level of the graph; (2) the GAT model can dynamically adjust the aggregation weight from different neighbors, which increases its robustness to the high topology-imbalance situation but hinders the model performance when the graph topology-imbalance level is low and there is less need to filter neighbor information; (3) the infinite convolution mechanism of the PPNP model makes it possible to aggregate the information from distant nodes to enhance its robustness to the graph topology imbalance.
Shchur et al. [34] notice that the performance ranking of GNNs varies with the training set selection. Hence, existing node classification studies [32, 14] usually repeat experiments multiple times with different training sets to reduce this randomness. The results from Figure 5 inspire us that the topology imbalance can partly explain the randomness of GNN performance caused by the training set selection and we can adopt the topology-imbalance sensitivity as a new aspect in evaluating the performance of different GNN architectures.

heading: 4.2 Limitations of Method

text: Although our ReNode method has proven effective in multiple scenarios, we also notice some limitations of it because of the complexity of node imbalance learning. First, the ReNode method is devised for homogeneously-connected graphs (linked nodes are expected to be similar, such as the various datasets in experiments), and it needs a further update for heterogeneously-connected graphs (such as protein networks). Besides, the ReNode method improves less when the graph connectivity is poor (Section 3.2) or the labeling ratio is extremely low (Section 3.3) because in these cases, the conflict level among nodes is low thus the nodes topological positions are insufficiently reflected.

heading: 5 Related Work

text:
Imbalanced classification problems are widespread in real scenarios and have attracted extensive attention from both academia and industry. Most existing studies on this topic focus on the classimbalanced quantity distribution [15], where the model’s inference ability for the majority classes will be significantly better than that of minority classes [12]. The existing methods for solving the quantity-imbalance issue can be roughly divided into methods for the data selection phase and the model training phase. Active learning [31, 10, 42] and Re-sampling [6, 16, 25] are two classical examples designed to construct a quantity-balanced training set . On the other hand, Re-weighting is a simple but effective solution for the model training phase, which adjusts the weights of training samples in different classes based on the labeling sizes [17, 30, 8, 5]. However, directly applying these methods into the graph scene lacks the consideration for the graph-specific topology-imbalance issue. Unlike the re-weight methods which conduct class-lever re-weighting, our ReNode method is a more fine-grained one and assign weights to each node individually.
There have been quantity-imbalance studies (Tomek links [38], NearMiss [23], One-Sided Selection [20]) trying to exclude the negative influence of labeling samples close to class boundaries by measuring the similarity of sample features. However, in the graph scene, the prior knowledge contained in node connections is more reliable than directly calculating the feature similarity. Besides, the number of labeled nodes is quite small in the semi-supervised setting. Thus it is not robust to locate their positions by computing similarity among a small number of nodes and we propose to leverage the influence conflict across the whole graph to locate node position to boundaries.
Graph data structure owns a wide range of applications, such as social media [13], stock exchange [21], shopping [34], medicine [44], transportation [28] and so on. Similar to other data structures, graph node representation learning also suffer from the quantity-imbalance issue [35]. Apart from the universal quantity-balance approaches introduced in Section 5 which can be transferred to the graph scene, there are some graph-specific quantity-imbalance methods recently proposed. DR-GCN [35] propose two types of regularization to tackle quantity imbalance: class-conditioned adversarial training and unlabeled nodes latent distribution constraint. RA-GCN [11] propose to automatically learn to weight the training samples in different classes in an adversarial training manner. AdaGCN Shi et al. [36] propose to leverage the boosting algorithm to handle the quantity-imbalance issue for the node classification task. GraphSMOTE [49] combines the synthetic node generation and the edge generation to up-sample nodes for the minority classes. However, these studies only pay attention to the quantity imbalance and overlook the topology imbalance.
Different from these studies [48, 29, 26] that try to locate the absolute positions for all the nodes by measuring their distance from the selected anchor nodes, our Totoro metric is devised to locate the relative positions to the class boundary for the labeling nodes by considering the influence conflict and can get rid of the dependence on the anchor nodes. Besides, our relative positions can more accurately reflect node class information because we distinguish the information from different classes while existing studies [48, 29] treat all the anchor nodes the same and ignore the class difference.

heading: 6 Conclusion and Future Work

text:
In this work, we recognize the topology-imbalance node representation learning (TINL) as a graphspecific imbalance learning problem that has not been studied so far. We find that the topologyimbalance issue widely exists in graphs and severely hinders the learning of node classification. We unify TINL with the quantity-imbalance node representation learning (QINL) by considering the shift of the node influence boundaries from true class boundaries. To measure the degree of topology imbalance, we devise a conflict detection–based metric Totoro to locate node position, and further propose the ReNode method to adaptively adjust the training weights of labeled nodes based on their topological positions. Extensive empirical results have verified the effectiveness of our method in various settings: TINL-only, both TINL and QINL, and large-scale graph. Besides, we also propose the topology-imbalance sensitivity as a new metric to evaluate GNNs.
Considering the importance of the topology-imbalance issue and the limitations of our approach, advanced methods with stronger theoretical or experimental support are expected in future work. Moreover, since topology imbalance is widespread in graph-related tasks other than node classification, how to measure and solve the topology-imbalance issues in broader graph scopes remains a meaningful challenge for future study.

heading: 7 Acknowledgement

text: We appreciate all the thoughtful and insightful suggestions from reviews. This work was supported in part by a Tencent Research Grant and National Natural Science Foundation of China (No. 61673028). Xu Sun is the corresponding author of this paper.

title: Topology-Imbalance Learning for Semi-Supervised Node Classification