New Resistance Distances with Global Information on Large Graphs

Canh Hao Nguyen, Hiroshi Mamitsuka
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:639-647, 2016.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-nguyen16a, title = {New Resistance Distances with Global Information on Large Graphs}, author = {Nguyen, Canh Hao and Mamitsuka, Hiroshi}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {639--647}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/nguyen16a.pdf}, url = {https://proceedings.mlr.press/v51/nguyen16a.html}, 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.} }
Endnote
%0 Conference Paper %T New Resistance Distances with Global Information on Large Graphs %A Canh Hao Nguyen %A Hiroshi Mamitsuka %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-nguyen16a %I PMLR %P 639--647 %U https://proceedings.mlr.press/v51/nguyen16a.html %V 51 %X 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.
RIS
TY - CPAPER TI - New Resistance Distances with Global Information on Large Graphs AU - Canh Hao Nguyen AU - Hiroshi Mamitsuka BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-nguyen16a PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 639 EP - 647 L1 - http://proceedings.mlr.press/v51/nguyen16a.pdf UR - https://proceedings.mlr.press/v51/nguyen16a.html AB - 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. ER -
APA
Nguyen, C.H. & Mamitsuka, H.. (2016). New Resistance Distances with Global Information on Large Graphs. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:639-647 Available from https://proceedings.mlr.press/v51/nguyen16a.html.

Related Material