New Resistance Distances with Global Information on Large Graphs

Canh Hao Nguyen, Hiroshi Mamitsuka

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

433 Downloads (Pure)

Abstract

We consider the problem that on large random geometric graphs, random walk-based distances between nodes do not carry global information such as cluster structure. Instead, as the graphs become larger, the distances contain mainly the obsolete information of local density of the nodes. Many distances or similarity measures between nodes on a graph have been proposed but none are both proved to overcome this problem or computationally feasible even for small graphs. We propose new distance functions between nodes for this problem. The idea is to use electrical flows with different energy functions. Our proposed distances are proved analytically to be metrics in $L^p$ spaces, to keep global information, avoiding the problem, and can be computed efficiently for large graphs. Our experiments with synthetic and real data confirmed the theoretical properties and practical performances of our proposed distances.
Original languageEnglish
Title of host publicationProceedings of the 19th International Conference on Artificial Intelligence and Statistics
EditorsArthur Gretton, Christian C. Robert
Pages639-647
Publication statusPublished - May 2016
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Artificial Intelligence and Statistics - Cadiz, Spain
Duration: 9 May 201611 May 2016
Conference number: 19
http://www.aistats.org/aistats2016/

Publication series

NameJMLR: Workshop and Conference Proceedings
PublisherThe MIT Press
Volume51
ISSN (Electronic)1938-7228

Conference

ConferenceInternational Conference on Artificial Intelligence and Statistics
Abbreviated titleAISTATS
CountrySpain
CityCadiz
Period09/05/201611/05/2016
Internet address

Keywords

  • GRAPHS
  • Graph mining
  • Machine learning
  • Node distance

Fingerprint

Dive into the research topics of 'New Resistance Distances with Global Information on Large Graphs'. Together they form a unique fingerprint.

Cite this