Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

Bill Kay; Prasanna Date; Catherine Schuman

doi:10.1145/3381755.3381762

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

Bill Kay, Prasanna Date, Catherine Schuman

Learning Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

26 Scopus citations

Abstract

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore's law era due to its extremely low power usage and inherent parallelism. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.

Original language	English
Title of host publication	Proceedings of the 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020
Publisher	Association for Computing Machinery
ISBN (Electronic)	9781450361231
DOIs	https://doi.org/10.1145/3381755.3381762
State	Published - Mar 17 2020
Event	2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020 - Heidelberg, Germany Duration: Mar 17 2020 → Mar 20 2020

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020
Country/Territory	Germany
City	Heidelberg
Period	03/17/20 → 03/20/20

Funding

Notice: This manuscript has been authored in part by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

Keywords

Graph Algorithms
Longest Shortest Path
Minimum Spanning Trees
Neuromorphic Computing

Access to Document

10.1145/3381755.3381762

Cite this

@inproceedings{ec58f5ba41654080ba43a18cdddba24f,

title = "Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees",

abstract = "Neuromorphic computing is poised to become a promising computing paradigm in the post Moore's law era due to its extremely low power usage and inherent parallelism. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.",

keywords = "Graph Algorithms, Longest Shortest Path, Minimum Spanning Trees, Neuromorphic Computing",

author = "Bill Kay and Prasanna Date and Catherine Schuman",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020 ; Conference date: 17-03-2020 Through 20-03-2020",

year = "2020",

month = mar,

day = "17",

doi = "10.1145/3381755.3381762",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

booktitle = "Proceedings of the 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020",

}

Kay, B, Date, P & Schuman, C 2020, Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees. in Proceedings of the 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020. ACM International Conference Proceeding Series, Association for Computing Machinery, 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020, Heidelberg, Germany, 03/17/20. https://doi.org/10.1145/3381755.3381762

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees. / Kay, Bill; Date, Prasanna; Schuman, Catherine.
Proceedings of the 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020. Association for Computing Machinery, 2020. (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Neuromorphic Graph Algorithms

T2 - 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020

AU - Kay, Bill

AU - Date, Prasanna

AU - Schuman, Catherine

PY - 2020/3/17

Y1 - 2020/3/17

N2 - Neuromorphic computing is poised to become a promising computing paradigm in the post Moore's law era due to its extremely low power usage and inherent parallelism. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.

AB - Neuromorphic computing is poised to become a promising computing paradigm in the post Moore's law era due to its extremely low power usage and inherent parallelism. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.

KW - Graph Algorithms

KW - Longest Shortest Path

KW - Minimum Spanning Trees

KW - Neuromorphic Computing

UR - http://www.scopus.com/inward/record.url?scp=85123042665&partnerID=8YFLogxK

U2 - 10.1145/3381755.3381762

DO - 10.1145/3381755.3381762

M3 - Conference contribution

AN - SCOPUS:85123042665

T3 - ACM International Conference Proceeding Series

BT - Proceedings of the 2020 Annual Neuro-Inspired Computational Elements Workshop, NICE 2020

PB - Association for Computing Machinery

Y2 - 17 March 2020 through 20 March 2020

ER -

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this