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)


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
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

Publication series

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


ConferenceInternational Conference on Artificial Intelligence and Statistics
Abbreviated titleAISTATS
Internet address


  • Graph mining
  • Machine learning
  • Node distance


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

Cite this