User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Randomized Optimal Transport on a Graph: Framework and New Distance Measures

Primary tabs

download
  • Open access
  • PDF
  • 1.34 M
Guex, Guillaume [UCL] Kivimäki, Ilkka [UCL] Saerens, Marco [UCL]

The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature T) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins). When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a ow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths, and require the inversion of an n x n matrix with n being the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy (T→ 0+) and the solution to the corresponding electrical circuit (T → ∞). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2019
Language Anglais
Journal information "Network Science" - Vol. 7, no. 1, p. 88-122 (2019)
Peer reviewed yes
Publisher Cambridge University Press
issn 2050-1242
e-issn 2050-1250
Publication status Publié
Affiliations UCL - SSH/LouRIM - Louvain Research Institute in Management and Organizations
UCL - SST/ICTM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Keywords Network Science ; Optimal Transportation ; Bag-of-Paths ; Randomized Shortest Paths ; Distances between Nodes ; Link Analysis
Links
  1. Ahuja, Network flows: Theory, algorithms, and applications (1993)
  2. Akamatsu, Markov process and stochastic traffic assignment. Transportation Research B, 30, 369386 (1996)
  3. Alamgir, M. , & von Luxburg, U. (2011). Phase transition in the family of p-resistances. In Advances in neural information processing systems 24: Proceedings of the NIPS ‘11 conference (pp. 379–387).
  4. Bacharach Michael, Estimating Nonnegative Matrices from Marginal Data, 10.2307/2525582
  5. Barabási, Network science (2016)
  6. Bavaud François, Guex Guillaume, Interpolating between Random Walks and Shortest Paths: A Path Functional Approach, Lecture Notes in Computer Science (2012) ISBN:9783642353857 p.68-81, 10.1007/978-3-642-35386-4_6
  7. Brandes Ulrik, Fleischer Daniel, Centrality Measures Based on Current Flow, STACS 2005 (2005) ISBN:9783540249986 p.533-544, 10.1007/978-3-540-31856-9_44
  8. Chebotarev Pavel, A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, 10.1016/j.dam.2010.11.017
  9. Chebotarev Pavel, The walk distances in graphs, 10.1016/j.dam.2012.02.015
  10. Chebotarev Pavel, Studying New Classes of Graph Metrics, Lecture Notes in Computer Science (2013) ISBN:9783642400193 p.207-214, 10.1007/978-3-642-40020-9_21
  11. Cheng Qing-Ming, Yang Hongcang, 10.1090/s0002-9947-05-04023-7
  12. Courty Nicolas, Flamary Remi, Tuia Devis, Rakotomamonjy Alain, Optimal Transport for Domain Adaptation, 10.1109/tpami.2016.2615921
  13. Cover, Elements of information theory (2006)
  14. Cuturi, Advances in neural information processing systems 26: Proceedings of the NIPS ‘13 conference, 2292 (2013)
  15. Dobrushin R. L., Prescribing a System of Random Variables by Conditional Distributions, 10.1137/1115049
  16. Doyle, P. G. , & Snell, J. L. (1984). Random walks and electric networks. The Mathematical Association of America.
  17. Erlander, The gravity model in transportation analysis. Theory and extensions (1990)
  18. Estrada, The structure of complex networks (2012)
  19. Fang S.-C., Rajasekera J. R., Tsao H.-S. J., Entropy Optimization and Mathematical Programming, ISBN:9781461378105, 10.1007/978-1-4615-6131-6
  20. Ferradans Sira, Papadakis Nicolas, Peyré Gabriel, Aujol Jean-François, Regularized Discrete Optimal Transport, 10.1137/130929886
  21. Fouss Francois, Saerens Marco, Shimbo Masashi, Algorithms and Models for Network Data and Link Analysis, ISBN:9781316418321, 10.1017/cbo9781316418321
  22. Françoisse Kevin, Kivimäki Ilkka, Mantrach Amin, Rossi Fabrice, Saerens Marco, A bag-of-paths framework for network data analysis, 10.1016/j.neunet.2017.03.010
  23. Freeman Linton C., A Set of Measures of Centrality Based on Betweenness, 10.2307/3033543
  24. García-Díez, S. , Vandenbussche, E. , & Saerens, M. (2011). A continuous-state version of discrete randomized shortest-paths. In Proceedings of the 50th IEEE international conference on decision and control (IEEE CDC 2011) (pp. 6570–6577).
  25. Graybill, F. (1983). Matrices with applications in statistics. Wadsworth International Group.
  26. Grinstead, C. , & Snell, J. L. (1997). Introduction to probability (2nd ed.). The Mathematical Association of America.
  27. Griva, I. , Nash, S. G. , & Sofer, A. (2009). Linear and nonlinear optimization: Second edition. Society for Industrial and Applied Mathematics (SIAM).
  28. Guex Guillaume, Interpolating between random walks and optimal transportation routes: Flow with multiple sources and targets, 10.1016/j.physa.2015.12.117
  29. Guex, Data science, learning by latent structures, and knowledge discovery, 1564, 101 (2015)
  30. Guex, G. , Emmanouilidis, T. , & Bavaud, F. (2017). Transportation clustering: A regularized version of the optimal transportation problem. (Submitted for publication)
  31. Hara, K. , Suzuki, I. , Shimbo, M. , Kobayashi, K. , Fukumizu, K. , & Radovanovic, M. (2015). Localized centering: Reducing hubness in large-sample data. In Proceedings of the 29th AAAI conference on artificial intelligence (AAAI ‘15) (pp. 26452651).
  32. Hashimoto, Advances in neural information processing systems 28: Proceedings of the NIPS ‘15 conference, 3429 (2015)
  33. Herbster, M. , & Lever, G. (2009). Predicting the labelling of a graph via minimum p-seminorm interpolation. In Proceedings of the 22nd conference on learning theory (COLT ‘09) (pp. 18–21).
  34. Jaynes E. T., Information Theory and Statistical Mechanics, 10.1103/physrev.106.620
  35. Kantorovich, Doklady Akademii Nauk SSSR, 37, 227 (1942)
  36. Kapur, J. N. (1989). Maximum-entropy models in science and engineering. Wiley.
  37. Kapur J. N., Kesavan H. K., Entropy Optimization Principles and Their Applications, Entropy and Energy Dissipation in Water Resources (1992) ISBN:9789401050722 p.3-20, 10.1007/978-94-011-2430-0_1
  38. Kivimäki Ilkka, Lebichot Bertrand, Saramäki Jari, Saerens Marco, Two betweenness centrality measures based on Randomized Shortest Paths, 10.1038/srep19668
  39. Kivimäki Ilkka, Shimbo Masashi, Saerens Marco, Developments in the theory of randomized shortest paths with a comparison of graph node distances, 10.1016/j.physa.2013.09.016
  40. Klein D. J., Randić M., Resistance distance, 10.1007/bf01164627
  41. Kolaczyk Eric D., Statistical Analysis of Network Data, ISBN:9780387881454, 10.1007/978-0-387-88146-1
  42. Kurras, S. (2015). Symmetric iterative proportional fitting. In Proceedings of the 18th international conference on artificial intelligence and statistics (AISTATS) (vol. 38, pp. 526–534).
  43. Semisupervised Classification Through the Bag-of-Paths Group Betweenness, 10.1109/tnnls.2013.2290281
  44. Lebichot Bertrand, Saerens Marco, A bag-of-paths node criticality measure, 10.1016/j.neucom.2017.06.054
  45. Lewis Ted G., Network Science, ISBN:9780470400791, 10.1002/9780470400791
  46. Li Yanhua, Zhang Zhi-Li, Boley Daniel, From Shortest-Path to All-Path: The Routing Continuum Theory and Its Applications, 10.1109/tpds.2013.203
  47. Lougee-Heimer R., The Common Optimization INterface for Operations Research: Promoting open-source software in the operations research community, 10.1147/rd.471.0057
  48. Lü Linyuan, Zhou Tao, Link prediction in complex networks: A survey, 10.1016/j.physa.2010.11.027
  49. Mantrach Amin, Luh Yen, Callut Jerome, Francoisse Kevin, Shimbo Masashi, Saerens Marco, The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph, 10.1109/tpami.2009.78
  50. Mantrach Amin, van Zeebroeck Nicolas, Francq Pascal, Shimbo Masashi, Bersini Hugues, Saerens Marco, Semi-supervised classification and betweenness computation on large, sparse, directed graphs, 10.1016/j.patcog.2010.11.019
  51. Newman M.E. J., A measure of betweenness centrality based on random walks, 10.1016/j.socnet.2004.11.009
  52. Newman Mark, Networks, ISBN:9780199206650, 10.1093/acprof:oso/9780199206650.001.0001
  53. Nguyen, C. H. , & Mamitsuka, H. (2016). New resistance distances with global information on large graphs. In Proceedings of the 19th international conference on artificial intelligence and statistics (AISTATS) (pp. 639–647).
  54. Osborne, An introduction to game theory (2004)
  55. Pukelsheim Friedrich, Biproportional scaling of matrices and the iterative proportional fitting procedure, 10.1007/s10479-013-1468-3
  56. Radovanovic, Journal of Machine Learning Research, 11, 2487 (2010a)
  57. Radovanović Milos, Nanopoulos Alexandros, Ivanović Mirjana, On the existence of obstinate results in vector space models, 10.1145/1835449.1835482
  58. Saerens Marco, Achbany Youssef, Fouss François, Yen Luh, Randomized Shortest-Path Problems: Two Related Models, 10.1162/neco.2009.11-07-643
  59. Silva, T. , & Zhao, L. (2016). Machine learning in complex networks. Springer.
  60. Sinkhorn Richard, Diagonal Equivalence to Matrices with Prescribed Row and Column Sums, 10.2307/2314570
  61. Solomon, J. , Rustamov, R. , Guibas, L. , & Butscher, A. (2014). Wasserstein propagation for semi-supervised learning. In Proceedings of the 31 international conference on machine learning (ICML ‘14) (pp. 306–314).
  62. Sommer Felix, Fouss François, Saerens Marco, Comparison of Graph Node Distances on Clustering Tasks, Artificial Neural Networks and Machine Learning – ICANN 2016 (2016) ISBN:9783319447773 p.192-201, 10.1007/978-3-319-44778-0_23
  63. Sommer Felix, Fouss François, Saerens Marco, Modularity-Driven Kernel k-means for Community Detection, Artificial Neural Networks and Machine Learning – ICANN 2017 (2017) ISBN:9783319686110 p.423-433, 10.1007/978-3-319-68612-7_48
  64. Suzuki, I. , Hara, K. , Shimbo, M. , Matsumoto, Y. , & Saerens, M. (2012). Investigating the effectiveness of Laplacian-based kernels in hub reduction. In Proceedings of the 26th AAAI conference on artificial intelligence (AAAI ‘12) (pp. 1112–1118).
  65. Suzuki, I. , Hara, K. , Shimbo, M. , Saerens, M. , & Fukumizu, K. (2013). Centering similarity measures to reduce hubs. In Proceedings of the international conference on empirical methods in natural language processing (EMNLP 2013) (pp. 613–623).
  66. Link Analysis : An Information Science Approach, ISBN:9780120885534, 10.1108/s1876-0562(2004)04
  67. Tomasev Nenad, Radovanovic Milos, Mladenic Dunja, Ivanovic Mirjana, The Role of Hubness in Clustering High-Dimensional Data, 10.1109/tkde.2013.25
  68. Villani Cédric, Topics in Optimal Transportation, ISBN:9780821833124, 10.1090/gsm/058
  69. Villani, Optimal transport: Old and new (2008)
  70. von Luxburg, Advances in neural information processing systems 23: Proceedings of the NIPS ‘10 conference, 2622 (2010)
  71. von Luxburg, Journal of Machine Learning Research, 15, 1751 (2014)
  72. Wasserman Stanley, Faust Katherine, Social Network Analysis : Methods and Applications, ISBN:9780511815478, 10.1017/cbo9780511815478
  73. Wilson, Entropy in urban and regional modelling (1970)
  74. Yen Luh, Saerens Marco, Mantrach Amin, Shimbo Masashi, A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances, 10.1145/1401890.1401984
  75. Zhang Wei, Zhao Deli, Wang Xiaogang, Agglomerative clustering via maximum incremental path integral, 10.1016/j.patcog.2013.04.013
  76. Zolotarev, Teoriya Veroyatnostei i ee Primeneniya, 28, 264 (1983)
Bibliographic reference Guex, Guillaume ; Kivimäki, Ilkka ; Saerens, Marco. Randomized Optimal Transport on a Graph: Framework and New Distance Measures. In: Network Science, Vol. 7, no. 1, p. 88-122 (2019)
Permanent URL http://hdl.handle.net/2078.1/214327