Paper Info

Title | ||
---|---|---|

Algorithms for Lipschitz Learning on Graphs |

Abstract | ||
---|---|---|

We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large $p$ of $p$-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time $\widetilde{O} (m n)$. The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform $l_{0}$-regularization on the given values in polynomial time and $l_{1}$-regularization on the initial function values and on graph edge weights in time $\widetilde{O} (m^{3/2})$. |

Year | Venue | DocType |
---|---|---|

2015 | COLT | Journal |

Volume | Citations | PageRank |

abs/1505.00290 | 7 | 0.71 |

References | Authors | |

7 | 4 |

Authors (4 rows)

Cited by (7 rows)

References (7 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Rasmus Kyng | 1 | 56 | 9.00 |

Anup Rao | 2 | 123 | 17.38 |

Sushant Sachdeva | 3 | 171 | 16.90 |

Daniel A. Spielman | 4 | 4257 | 638.57 |