Timeline for Efficient algorithm for Wasserstein-1 distance in graph setting
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2017 at 10:48 | vote | accept | JustSomeGuy | ||
| Sep 21, 2017 at 7:14 | comment | added | Benoît Kloeckner | There are two things you can simplify: the computation of distances in the graph (because you only need distances between point at most three edges away), and the computation of Wasserstein costs (since your measures are supported on small sets). | |
| Sep 11, 2017 at 15:30 | comment | added | JustSomeGuy | Ah right, I have actually seen another paper where they assume a lazy walk as well. I'll have to look into it, thanks for the tip! As for your algorithm suggestion, I'm not sure I understand the implication, isn't this a consideration for the calculation of the distances? | |
| Sep 10, 2017 at 6:54 | comment | added | Benoît Kloeckner | With a simple walk, the cube has curvature 0 while a lazy walk has positive curvature, implying many nice propertied. This is all well explained in Ollivier's paper. | |
| Sep 9, 2017 at 16:58 | answer | added | Igor Rivin | timeline score: 1 | |
| Sep 9, 2017 at 16:14 | comment | added | JustSomeGuy | Actually, it does have to do with Ollivier-Ricci curvature! Could you explain why lazy random walks would give better results? | |
| Sep 9, 2017 at 15:56 | answer | added | R W | timeline score: 1 | |
| Sep 9, 2017 at 15:56 | comment | added | Benoît Kloeckner | Also, if by any chance this has to do with Ollivier-Ricci curvature, it often yields better results to consider lazy random walks. | |
| Sep 9, 2017 at 15:54 | comment | added | Benoît Kloeckner | My guess is that in the worst case scenario an exact computation will be very costly. But since the mesures you consider are supported on the neighborhood of a vertex and you restrict to adjacent vertices, for sparse enough graphs things are simpler. The measures are supported on at most $d$ vertices ($d$ the max degree); to compute distances between a neighbor of $x$ and a neighbor of $y$ you have an obvious candidate path (through $x,y$) to avoid testing paths above some length (if the weigths do not have roughly the correct order distance computation might be costly). | |
| Sep 9, 2017 at 15:36 | answer | added | Igor Rivin | timeline score: 1 | |
| Sep 9, 2017 at 14:48 | review | First posts | |||
| Sep 9, 2017 at 16:34 | |||||
| Sep 9, 2017 at 14:47 | history | asked | JustSomeGuy | CC BY-SA 3.0 |