Graph Laplacians and Least Squares on Graphs

Anil N. Hirani, Kaushik Kalyanaraman, Seth Watts

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

There are several classes of operators on graphs to consider in deciding on a collection of building blocks for graph algorithms. One class involves traditional graph operations such as breadth first or depth first search, finding connected components, spanning trees, cliques and other sub graphs, operations for editing graphs and so on. Another class consists of linear algebra operators where the matrices somehow depend on a graph. It is the latter class of operators that this paper addresses. We describe a least squares formulation on graphs that arises naturally in problems of ranking, distributed clock synchronization, social choice, arbitrage detection, and many other applications. The resulting linear systems are analogous to Poisson's equations. We show experimental evidence that some iterative methods that work very well for continuous domains do not perform well on graphs whereas some such methods continue to work well. By studying graph problems that are analogous to discretizations of partial differential equations (PDEs) one can hope to isolate the specific computational obstacles that graph algorithms present due to absence of spatial locality. In contrast, such locality is inherent in PDE problems on continuous domains. There is also evidence that PDE based methods may suggest improvements suitable for implementation on graphs.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages812-821
Number of pages10
ISBN (Electronic)0769555101, 9780769555102
DOIs
StatePublished - Sep 29 2015
Event29th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015 - Hyderabad, India
Duration: May 25 2015May 29 2015

Publication series

NameProceedings - 2015 IEEE 29th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015

Other

Other29th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2015
Country/TerritoryIndia
CityHyderabad
Period5/25/155/29/15

Keywords

  • Calculus
  • Handheld computers
  • Harmonic analysis
  • Laplace equations
  • Linear algebra
  • Linear systems
  • Synchronization

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Graph Laplacians and Least Squares on Graphs'. Together they form a unique fingerprint.

Cite this