Oct, 2021

Karger算法扩展：为什么在理论上失败，在实践中如何有用

HTML
PDF
TL;DR研究了基于 Karger 收缩算法的随机化算法是否可以成功推广到其他割问题，并提出了一种基于这个算法的简单新算法，用于种子分割/基于图的半监督学习，该算法具有线性渐近运行时并产生可以被解释为后验概率的潜力。
发现论文，激发创造
  • 基于流的局部图聚类算法

    本文介绍了一种名为LocalImprove的算法，应用于设计更好的本地图分区算法，该算法是首个切割改进算法，具有局部性质，可以在更短的时间内运行，同时与Andersen和Lang的全局算法具有相同的理论保证，解决了先前基于随机行走算法的图谱划分局部算法存在的问题。

    Jul, 2013

  • 现代推理技术在结构离散能量最小化问题中的比较研究

    该研究比较了32种现代化的最优化技术在计算机视觉中的应用，结果表明，与之前研究不同，多面体方法与整数规划解决方案在运行时间和解决方案质量方面在大范围的模型类型上具有竞争力。

    Apr, 2014

  • 机器学习的新优化方法

    介绍了优化机器学习问题的几种新方法，包括针对有限和图结构目标的优化方法，其中包括针对固定结构的参数学习、结构学习和同时学习等方法。

    Oct, 2015

  • 来自少样本的贝叶斯估计：社群检测及相关问题

    提出了一种基于低阶多项式、半定规划和张量分解的高效贝叶斯估计问题的元算法，该算法的重点在于尽量紧密（达到添加低阶项的下限），并且通常可以达到统计阈值或猜测的计算阈值。在样本复杂度方面改善了社交网络检测和混合式社交网络模型的恢复保证，并且表明该任务可能需要指数时间。算法的基本策略是计算参数的后验分布的最佳低阶逼近，然后使用一个健壮的张量分解算法从这些近似的后验时刻中恢复参数。

    Sep, 2017

  • 基于同情保守原则的图像分割平衡剪枝算法

    本文提出Compassionately Conservative Balanced (CCB) Cut costs算法，可用于解决图像分割问题，该算法基于NCut目标函数，针对单一分区得分问题提出了一种新的解决方法，并通过BSDS500数据库中的图像测试验证了其在分割准确性和区域大小方面的优越性。

    Mar, 2018

  • 图割总能在Potts模型中找到全局最优解(但有一个陷阱)

    证明 alpha-expansion 算法在 Potts 二元势场的马尔科夫随机场中总是返回全局最优赋值，但有一个要求：只对原问题实例的微小扰动中的一个赋值具有最优性。

    Nov, 2020

  • 半监督分类的图卷积：改进的线性可分性和越界泛化

    该研究探讨了在图形信息存在的情况下，基于图卷积进行数据分类的方法，发现图卷积扩展了数据线性可分的范围，并且在最小化交叉熵损失后，得到的线性分类器具有很好的泛化能力。

    Feb, 2021

  • 高效学习图形进行半监督学习

    本研究提出了一种利用多个数据集学习半监督学习图的算法，最终实现了在已知图或者未知图的情况下提高计算效率。

    Jun, 2023

  • 通过最优输运实现任意尺寸约束的图割

    通过提出一种基于正则化Gromov-Wasserstein问题的加速近端梯度下降算法，我们解决了图切割问题，并实现了稀疏解，相较于经典谱聚类算法，额外的复杂度仅为O(log(n))，但效率更高。

    Feb, 2024

  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间O(1)近似的方法。

    Jun, 2024