Scalable Semi-Supervised Classification via Neumann Series

Chen Gong, Keren Fu, Lei Zhou, Jie Yang, Xiangjian He

Research output: Journal PublicationArticlepeer-review

4 Citations (Scopus)


Traditional graph-based semi-supervised learning (GBSSL) algorithms usually scale badly due to the expensive computational burden. The main bottleneck is that they need to compute the inversion of a huge matrix. In order to alleviate this problem, this paper proposes Neumann series approximation (NSA) to explicitly approximate the inversion process required by conventional GBSSL methodologies, which makes them computationally tractable for relatively large datasets. It is proved that the deviation between the approximation and direct inversion is bounded. Using real-world datasets related to handwritten digit recognition, speech recognition and text classification, the experimental results reveal that NSA accelerates the speed significantly without decreasing too much precision. We also empirically show that NSA outperforms other scalable approaches such as Nyström method, Takahashi equation, Lanczos process based SVD and AnchorGraph regularization, in terms of both efficiency and accuracy.

Original languageEnglish
Pages (from-to)187-197
Number of pages11
JournalNeural Processing Letters
Issue number1
Publication statusPublished - 22 Aug 2015
Externally publishedYes


  • Error bound
  • Neumann series
  • Scalability
  • Semi-supervised learning

ASJC Scopus subject areas

  • Software
  • Neuroscience (all)
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Scalable Semi-Supervised Classification via Neumann Series'. Together they form a unique fingerprint.

Cite this