Kernel-based embeddings for large graphs with centrality constraints

Brian Baingana, Georgios B. Giannakis

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

Abstract

Complex phenomena involving pairwise interactions in natural and man-made settings can be well-represented by networks. Besides statistical and computational analyses on such networks, visualization plays a crucial role towards effectively conveying 'at-a-glance' structural properties such as node hierarchy. However, most graph embedding algorithms developed for network visualization are ill-equipped to cope with the sheer volume of data generated by modern networks that encompass online social interactions, the Internet, or the world-wide web. Motivated by the emergence of nonlinear manifold learning approaches for dimensionality reduction, this paper puts forth a novel scheme for embedding graphs using kernel matrices defined on graphs. In particular, a kernelized version of local linear embedding is devised for computation of reconstruction weights. Unlike contemporary approaches, the developed embedding algorithm entails low-cost, parallelizable, and closed-form updates that can easily scale to big network data. Furthermore, it turns out that inclusion of embedding constraints to emphasize centrality structure can be accomplished at minimal extra computational cost. Experimental results on Watts-Strogatz small-world networks demonstrate the efficacy of the novel approach.

Original languageEnglish (US)
Title of host publication2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1901-1905
Number of pages5
ISBN (Electronic)9781467369978
DOIs
StatePublished - Aug 4 2015
Event40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Brisbane, Australia
Duration: Apr 19 2014Apr 24 2014

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2015-August
ISSN (Print)1520-6149

Other

Other40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015
CountryAustralia
CityBrisbane
Period4/19/144/24/14

Keywords

  • Graph embedding
  • coordinate descent
  • local linear embedding
  • network visualization

Fingerprint Dive into the research topics of 'Kernel-based embeddings for large graphs with centrality constraints'. Together they form a unique fingerprint.

Cite this