Research map / Graph learning / Graph algorithms and clustering
Scalable Sobolev IPM for Probability Measures on a Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a weighted-L^p regularization of the Sobolev IPM on graphs yielding a closed-form, metric, negative-definite distance computable in linear time in the number of edges, and uses it to build positive definite kernels for document classification and TDA.
Problem
Sobolev IPM between probability measures on a graph has no efficient algorithm for computation, which limits practical and large-scale use.
Approach
Relates the Sobolev norm to a weighted L^p norm of the graph derivative with weight 1+lambda(Lambda(x)), constrains critics in that weighted ball instead, which gives a closed-form IPM (a sum over edges of beta_e |mu(gamma_e)-nu(gamma_e)|^p) that is equivalent to the original Sobolev IPM and to Sobolev transport.
Key results
- Regularized Sobolev IPM kernel Gram matrices on the Orbit dataset took under 34 minutes for all exponents p=1, 1.5, 2, versus more than 39 hours for the OT kernel.
- The regularized Sobolev IPM is proven to be a metric equivalent to the original Sobolev IPM up to constants c1, c2 depending on the graph length measure.
- For tree graphs, the regularized Sobolev IPM with p=1 equals the 1-Wasserstein distance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use regularized Sobolev IPM kernels instead of the OT kernel | Orbit kernel Gram matrix computation · Orbit, G_Log/G_Sqrt | computation time: more than 39 hours -> less than 34 minutes | Helped |
| Use regularized Sobolev IPM kernels | document classification and TDA · TWITTER, RECIPE, CLASSIC, AMAZON, Orbit, MPEG7 | classification performance | Helped |
| Increase the number of slices | sliced regularized Sobolev IPM · Document classification and TDA, G_Log | classification performance | Helped |
| Increase the number of slices | sliced regularized Sobolev IPM · Document classification and TDA, G_Log | computation time | Hurt |
| Use the positive-definite TW kernel instead of the empirically indefinite OT kernel | kernelized SVM · RECIPE | classification performance | Hurt |
| Use the positive-definite TW kernel instead of the empirically indefinite OT kernel | kernelized SVM · CLASSIC and AMAZON, G_Log/G_Sqrt | classification performance | Helped |
Surprising findings
- The OT kernel is empirically indefinite and needed diagonal regularization of its Gram matrix to be used in SVM.
Limitations
- Closed-form and metric properties hold for measures supported on nodes of the graph and the length measure; general settings need the Sobolev geometry assumptions.
- Exact relation to p-Wasserstein distance for p>1 is open.
- Experiments are described as preliminary evidence of advantages.
Experimental setup
Datasets: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Benchmarks: TWITTER RECIPE CLASSIC AMAZON Orbit MPEG7
Metrics: SVM classification accuracy kernel matrix computation time
Baselines: optimal transport on graph Sobolev transport kernels tree-Wasserstein kernel OT kernel
Builds on: Sobolev transport Sobolev GAN integral probability metrics tree-Wasserstein distance
Closest papers by meaning
- Hierarchical Integral Probability Metrics: A distance on random probability measures with low sample complexity (ICML 2024 · similarity 0.86)
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.86)
- An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph (NeurIPS 2025 · similarity 0.85)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.84)
- The optimality of kernel classifiers in Sobolev space (ICLR 2024 · similarity 0.84)
- Sobolev Regularized MMD Gradient Flow (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.