Karger算法的扩展及其在图切割问题中的应用

4602Karger算法的扩展Erik Jenner Enrique Fita Sanmart´ın Fred A.海德堡图像处理德国海德堡大学erik@ejenner.com，{enrique.fita.sanmartin，fred.hamprecht}@ iwr.uni-heidelberg.de摘要最小图割和最小S-T-割问题是计算机科学中组合问题建模的重要基元，包括计算机视觉和机器学习。寻找全局最小割的一些最有效的算法是基于Karger开创性的收缩算法的随机在这里，我们研究是否Karger我们首先证明了Karger算法的广泛的自然推广不能有效地解决s-t-mincut或归一化割问题的最然而，然后，我们提出了一个简单的新算法，种子分割/基于图形的半监督学习，是密切的基础上Karger新算法具有线性渐近运行时间，并产生一个潜在的，可以被解释为后验概率的样本属于一个给定的种子/类。我们澄清其关系的随机步行算法/谐波能量最小化的分布在跨越森林。在来自对图像数据的种子图像分割和基于图的半监督学习的经典问题上，该方法至少与随机游走/谐波能量最小化/高斯过程一样好地执行。1. 介绍最小图割在机器学习问题中的应用已经有很长一段时间了。它们已用于自然语言处理[33]，特别是计算机视觉，例如分割[39，34，2]，恢复[13]和更普遍的能量最小化[21]。如今，它们仍然是许多深度学习管道的重要组成部分，例如分割[41，28，29，25，26]，图像分类[31]，以及最近的神经风格转移[42]。为了找到全局最小割（与第2节中的所有其他术语一起定义），Karger多 亏 了 这 些 随 机 算 法 ， 全 局 mincuts 可 以 比 s-t-mincuts更有效地找到。因此，一个有趣的问题是，在何种程度上随机算法可以应用到其他图切割问题，特别 是 是 否 卡 格 一 个 特 别 重 要 的 切 割 问 题 是 s-t-mincuts。虽然近似它们是可能的，在几乎线性的时间内，边的数量[20，35]，并且也已经使用基于图稀疏化的随机算法进行了研究[1]，但据我们所知，Karger的算法是否可以修改为有效地找到s-t-mincuts仍然是一个悬而未决的问题在第3节中，我们通过证明Karger收缩算法的一大类扩展一般不能精确有效地解决s-t-mincut问题来给出这个问题的定义性答案我们的结果也适用于归一化切割问题[36]，它像s-t-mincut一样，在图像分割中起着重要作用。然而，如果以正确的方式应用，Karger算法的扩展仍然是有用的。 在第4节中，我们展示了Karger算法的直接扩展如何我们将此扩展解释为森林采样方法，并观察其与用于种子图分割的随机步行算法[11]的相似性。在半监督学习中，相同的算法被称为谐波能量最小化[43]或高斯过程，因此相同的观察适用。本文的主要贡献是纯概念性的。尽管如此，在第5节中，我们在两个经典的实验中表明，所提出的算法与随机步行者/谐波能量最小化相比效果良好，这是种子分割/半监督学习。由于我们的方法在一个图上的时间复杂度只有O（m）4603对于m个边，它可以被视为随机步行算法/谐波能量最小化的有效替代方案，同时也给出了概率输出。全局最小割的αw（A，B）≤αmin分区w（A′，B′），（3）’’相关工作最密切相关的工作是典型的切割算法[9]，它使用由Karger算法生成的切割的集合来进行无种子聚类。相比之下，这里描述的方法使用由Karger算法的轻微变化生成的切口在该设置中，存在非常自然的方式来从切割的集合获得分割，以及用于收缩的自然停止点，其对于典型切割是自由参数。（A、B）其中α是大于1的某个正实数。同样的概念当然也可以用来定义一个α-极小s-t-割，它的代价在s-t-极小割的因子α之归一化切割[36]比最小切割目标生成更多的平衡切割，这使得它特别适合图像分割。它最小化w（A，B）w（A，B）2. 背景本文中考虑的所有图都是无向连通的，并且具有非负的边权。我们把这样一个图写成一个顶点集的元组G=（V，E，w）V，边集E和权函数w：E→R≥0。我们用n表示顶点数：=|V|并且边的数量由m：=|E|.我们还将边e ∈ E的权w（e）记为w e，将顶点u，v∈V之间的边的权记为w uv。IΣf不存在边，wuv定义为零。w（A，B）：=a∈A，b∈Bwab是连接两个子集A，BV的边权重之和。图割是图的顶点V的划分分成两个不相交的非空子集A和B，使得V=A∪B。这样的割的割集是一个端点在A和一个端点在B的所有边的集合。割集中所有边的权之和w（A，B）称为权或代价图的切割。我们将在这里描述三个不同的切割问题：全局最小割、s-t-最小割和正规化割。（全局）最小割或者简称为mincut- 以最小的成本进行切割。换句话说，最小割问题由下式给出：argminw（A，B）。（一）分割（A，B）图G的一个s-t-割是将给定的两个顶点s1=t∈V分开的图割.在s-t-mincut问题中，目标是找到具有最小成本的s-t-cut，即ncut（A，B）：=+ ⑷w（A，V）w（B，V）在图的分区（A，B）上。注意由于(def)Σw（A，V）= a∈A，v∈Vwav，这一项计算了内部A的权重为2倍。解决标准化切割问题精确地是NP完全的，但是可以用谱方法来近似解[36]。2.1. 卡格Karger算法是一种用于寻找全局最小图切割的蒙特卡罗算法，这意味着它具有固定的运行时间，但不能保证找到最佳切割。它基于图中边的收缩给定一个图表G=（V，E，w）且两个顶点v1，v2∈V，则得到收缩图G/{v1，v2}如下：1.v1和v2连同它们的所有边被移除，并且添加新的顶点u。2. F或每个边{vi，x}∈E，其中x∈f{v1 ，v2}，添加具有相同权重的新边{u，x}，其中i =1，2。3. 如果u现在有多条边指向同一顶点，则通过添加权重将它们Karger剩下的边定义一个割集。每个边被选择用于收缩，其概率与其权重成比例。精确算法在算法1中描述。当然，该算法并不总是产生最小切割。为了提高成功概率，算法arg min分割（S，T）w（S，T）使得s ∈ S，t ∈ T.（二）运行几次并返回最佳切割这可以通过在运行之间共享计算来加速[18，19]，但这样做不会影响本文中的任何参数，为了方便起见，我们将s-t-图定义为元组（G，s，t）且两个顶点s/=t∈ V。这里我们还提到α-极小割的概念。一个全局割（A，B）是α-极小的，如果它的代价在一个因子所以我们会忽略它Karger的算法在寻找最小切割时很有用的原因46042n算法一：卡格收 缩 算法输入：图形G输出：具有2个顶点的当G有2个以上的顶点时，选择边{u，v}的概率与其权重成正比;G←G/{u，v};returnG;切割的采样将给出- Karger算法在单次运行中以相对高的概率找到最小切割。这意味着多项式次数的运行足以找到具有高概率的最小切割。当从v开始时到达具有标签l的种子，我们也称之为随机游走势。每个顶点都被标记为该概率最高的标签。实际上为每个顶点模拟这样的随机步行者将是棘手的。但是概率prw（vl）可以通过求解包含图的拉普拉斯算子的线性系统来计算[11，43]。这意味着在近似线性时间内找到近似解是可能的。使用快速拉普拉斯求解器[37，22，23，4]的边缘数随机游走也可以解释为森林抽样方法。 我们将生成的集合写成Fs图的森林，其中每棵树跨越给定类别，并且不相交的树一起跨越图。任何这样的森林为每个顶点v定义一个标签。我们可以通过以下方式定义这些森林的Gibbs分布：定理1（[16]）. 用Karger算法找到任何给定mincut的概率至少为。nΣ−1。证明的关键思想是全局最小值的成本p（f）=1YZe∈fwe= 1 w（f）（5）ZQ最小切割仅是所有边权重之和的一小部分，因为总是可能仅切割出vertexΣ的最小割的代价上界为2e∈Ewe 因为收缩概率与在边缘权重的情况下，作为最小割集的一部分的边缘不太可能收缩（至少在我们将表明，定理1的模拟不存在的s-t-mincuts或归一化的削减，甚至广泛的一类扩展的Karger在一些情况下，这些算法需要运行指数次数以获得高成功概率。2.2. 随机游走/谐波能量最小化全局最小切割和归一化切割问题都是无监督的聚类方法：它们仅将图作为输入，而不进行任何注释。相比之下，在种子分割/半监督对于森林f∈Fs，权重为w（fΣ）：=e∈fwe。的配分函数由Z给出：f∈Fsw（f）.它可以[12，7]这是一个很好的例子。从该分布采样的森林指定顶点v到标签l的精确的随机游走概率prw（vl）。3. 不可能结果在 这 一 节 中 ， 我 们 提 出 了 一 个 框 架 ， 大 大generalizes Karger然后，我们表明，从这类算法的两个自然子集的算法不能被用来有效地找到s-t-mincuts或规范化的削减。在算法2中正式描述了一般的收缩算法。像Karger但是收缩概率现在可以取决于任意图属性，而不是与边权重成比例。学习问题，标签是给定的一些顶点，种子目标是为剩余顶点分配拟合标签。此问题可能发生在不同的环境中：在图像分割中，每个顶点对应于一个像素，而在基于图的半监督学习中，每个顶点表示一个样本，并且种子是标记的样本。用于解决种子分割问题的一种方法是随机步行算法[11]，也称为谐波能量最小化[43]或基于图的半监督学习中的高斯过程。为了给某个顶点v选择一个标签，它想象一个从v开始的图上的随机游走者。该随机步行器选择一条边进行遍历，其概率与每一步的边权重成比例。 一旦它到达其中一个种子就停止了。我们写prw（vl）表示随机游走者算法二：一般的压缩算法。当s/t与另一个节点收缩时，新节点成为新的s/t。评分函数W区分不同的收缩算法。输入 ：图G，可选地具有种子s和t（取决于算法）输出：当G有多于2个顶点时的2个顶点的收缩图G的一个←加权邻接矩阵;选择具有与W（e;A，s，t）成比例的概率的边e;G←G/e;returnG;460512221S不任何收缩算法都可以通过指定它分配给具有加权邻接矩阵A和种子索引s和t的图中的边e的得分W（e;A，s，t）来完全定义（其中e是顶点的两个集合{i，j}）。加权邻接矩阵包含边权重，即Aij=wij是顶点i和j之间的权重。Karger算法显然是W（e）= w e的特殊情况，或者更明确地，W（{ i，j } ; A，s，t）= A ij = A ji。 作为另一个例子，我们可以定义Karger算法的以下修改：.0，{i，j}={s，t}不同的s-t-mincuts（标准化切割）。然后必须至少有一个这样的切割是以指数低概率选择的。如果稍微扰动权重以使该切割成为唯一的s-t-mincut（归一化切割），则对其进行采样的概率将保持较低。 这是因为证明;证据oΣt适用于全局最小割的条件是最多有n全局最小切割在任何图，作为-orem1意味着。现在我们来看看第二个不可能性结果，即定义2. 边e的邻域N（e）=W（ {i，j};A，s，t）=.（六）A、否则{u，v} ∈E是G的由相邻的iju和v的孔。 它由顶点集VN（e）：=这种收缩算法，我们称之为s-t -收缩算法，从不收缩连接s和t的边，因此总是对s-t-割进行采样。这是相对容易表明，这个特殊的扩 展Karger的算法发现s-t-mincuts只有非常低的概率在一些图（我们将很快给出一个简单的然而，一般收缩算法的框架还包括总是找到s-t-mincut的选择，例如 .0，e∈ C{x∈V|x是u或v的邻居并且是来自E的所有边的邻居连接该集合中的顶点对。我们把两个邻域N（e1），N（e2）看作是相同的，如果存在一个图同构f：VN（e）→VN（e），如果适用，它也保持s和t，即 f（s）= s，f（t）= t。定义3. 如果分数W（e;A，s，t）可以写成函数W（N（e），G），则一般的收缩算法是局部的。W（e;A，s，t）：=（七）1、否则非正式地说，局部收缩算法作为仅基于边缘和边缘的局部属性的分数。切集C的最佳解。当然，这种特殊的方法是不切实际的，因为计算权重需要已经知道一个s-t-mincut，但它证明了收缩算法原则上可以以高概率找到s-t先验不清楚的是，是否有任何实际的收缩算法可以做到这一点。为了回答这个问题，我们引入了两个自然的和非常一般的压缩算法，我们可以正式证明不可能的结果：连续收缩算法和局部收缩算法。定义1. 连续收缩算法是其得分W是邻接矩阵A的连续函数的一般收缩算法（参见算法2）。直观地说，这意味着图的权重的微小变化仅会导致连续收缩算法的收缩概率的微小变化。由于同样的结果也适用于寻找s-t-mincuts和normalized cuts，我们将它们放在一起：定理2. 对于任何连续收缩算法，都有一个s-t-图族（图），它在其上找到一个s-t-mincut（归一化割），其顶点数的概率仅为指数低定理2的完整证明和所有其他结果可以在补充材料中找到。证明的思想是取一个图，其中有指数多个关于整个图的全局性质。它不能访问依赖于它们在图中的放置的各个边的属性。对于这类算法，我们可以证明与连续收缩算法类似的定理3. 有一类s-t-图（图），任何局部收缩算法在其上找到s-t-mincut（归一化割）的概率仅为指数级低。图1：s-t-收缩算法执行不好的图.粗边具有较高的权重。为了说明证明的思想，考虑图1所示的图。1.一、这个图可以用来证明s-t-收缩算法的定理3（而不是一般的局部收缩算法），如下：如果我们选择46063对于薄边权重为1，对于厚边权重为2，则存在唯一的S-T-Mincut。为了找到这个切口，在所有n-2次收缩中，只有厚边可以收缩但是选择厚边收缩的概率总是只有2。所以总的成功概率是给定割集V = V1∪。. . ∪Vk成不相交的顶点子集尊重种子s，如果s（v）=l=⇒v∈Vl对于所有l∈{1，. . . k}和v∈V.这样的割定义了整个图的标号，如果v∈Vl，则将标号l分配给顶点v。在k=2并且每个种子仅一个种子的特殊情况下，p成功=. 2Σn−23（八）类，这些割是简单的s-t-割，可以被采样使用来自前一节的S-T种子收缩算法（算法3）对此进行了一般化，并生成了与输入种子相关的切割如果我们把图中的图形放大 1表示任意数量的类和每个类的种子的成功概率。顶点的数量呈指数级减少所有局部收缩算法的一般证明（见补充材料）使用了相同的思想，即在s和t之间有许多平行路径的图，其中每一条路径都必须独立地正确收缩。这些路径比图中的路径更复杂。1，并且被选择为使得不可能仅基于局部属性来决定边是否属于s-t- mincut。同样的证明思想意味着局部收缩算法甚至不能以高概率逼近超过某个阈值的s-t推论4. 对于所有局部收缩算法，如果α 2，则定理3中找到图的α-极小s-t-割的概率是指数低<的。阈值2并不意味着什么。它只是来自我们用于证明的特定图，并且该声明可能适用于更大的阈值。注意算法3：带k的种子收缩算法不同的标签。标签为0表示输入：图G=（V，E，w），标签s：V-{0，. . . ，k}输出：具有k个顶点的收缩图收缩具有相同标签的节点之间的所有边;移除具有不同标签的节点之间的边;当G有多于k个顶点时选择边{v1，v2}，其概率与其权重成比例;G←G/{v1，v2};如果v1或v2具有标签，则分配通过合并v1创建的新节点和v2标记;移除具有不同标签的节点之间的边returnG;该结果仅针对s-t-mincut，而不是针对归一化的mincut。削减 由于标准化切割成本总是在[0，2]中，因此证明不像其他定理那样转移。4. 种子收缩算法上一节的结果表明，使用局部或连续收缩算法进行采样切割，然后从以这种方式采样的总体中取出最小切割，不一定会给出最小切割。然而，这个群体可以用在其他方面.在本节中，我们描述了一种用于种子图分割的新方法，该方法可以被解释为计算采样切割的平均值我们还描述了我们的方法和随机步行算法/谐波能量最小化之间的理论相似性。在下一节中，我们将从经验上比较这两种方法。为了使新方法广泛适用，我们首先将上一节的s-t问题设置由一个加权图组成G=（V，E，w）和满射种子函数s：{0，. . . ，k}，其中k是标签的数量，并且0被分配到未标记的节点。对于l ∈ {1，. . . 我们将pcontr（vl）定义为proba-种子收缩算法产生切割的能力其将标签L分配给顶点V。因为该算法是Karger算法对种子分割的非常自然的扩展种子收缩算法可以运行多次，以近似地找到每个顶点v和标签l的概率pcontr（vl）。如果一个艰难的任务被重-如果需要，则可以将每个顶点分配给该概率最高的标签。为了比较Karger潜在的随机步行者的潜力，我们重新解释种子收缩算法作为一个森林抽样方法。在收缩算法的单次运行期间，选择n-k条边进行收缩。这些边形成图的生成k-森林，其中森林的每个分量是该切割的子集V1之一。因此，我们的方法定义了k森林集合Fs上的概率分布，这些k森林将标签 pcontr（vl）是森林样本从该分布将V连接到具有标签L的种子。这让人想起随机walker分布prw这可以被解释为森林相同的概率4607.Σ来自吉布斯分布的pled将v连接到具有标签l的种子。这两种方法之间的唯一区别是它们使用的森林分布。为了理解这种差异的影响，我们将推导出种子收缩算法对给定森林进行采样的概率的表达式。F或边的子集EE，我们定义与来自eq.（12），我们期望收缩分布更强烈地有利于重林因此，Karger势应该高于该标签的prw（vl）还有第二种效果，它是拓扑的。C（E）：=E∪{e∈E|e∪E有循环或包含具有不同标签的种子之间的路径}。（九）性质：C（{e1，. . . ，en-2}）将趋于较大，如果C（{e1，. . . ，en-2}）包含许多边。自1起，. . . ，en−2是一个2-森林，唯一不在该集合中的边是C（E（）正是在来自E（h）的边被收缩之后被移除的边的集合，因为与E（h）中的边形成环的每条边都变成了自环。We写c（E）：=e∈Ewe为权重之和一组边缘的。 则e d的总权重。盖斯雷姆ainΣinΣg收缩后，E的边将是cE\CE.因此概率的收缩边e1，. . . ，en−2，其中精确地，2-森林诱导的割集中的边。因此，这又是一个理由，认为Karger分布比Gibbs分布在实际中如何计算Karger势和随机Walker势存在很大差异。如前所述，可以通过求解线性方程组来精确地与此相反，p（e1，. . . ，en−2）=nY−2w（ei）.（十）计算Karger势似乎是不确定的除了最小的图之外，所有的图都可以使用然而，种子i=1c（E|C（{e1，. . . ，ei−1}））注意分母中的i−1;该项描述了在第i个收缩步骤处的概率，在该点处只有e1，. . . ，ei-1h av e已被承包。对于采样森林f，其组成边缘e1，. . . ，en−2是收缩的，所以总概率为收缩算法可以用于从分布pcontr有效地采样，并且通过多次运行它，可以近似该分布。为了在近似中实现固定精度，种子收缩算法仅需要运行恒定次数，而与图的大小无关因此，我们的分割方法具有运行时复杂性-（2）算法的复杂度为O（m）。p（f）=ΣnY−2w（eσ（i））图表（有关如何实施系统初始收缩的时间复杂度为O（m）σ∈Sn−2i=1cE|C（{eσ（1），. . . ，eσ（i−1）}）材料）。=w（f）ΣnY−2σ∈Sn−2i=1c1.Σ。E|C（{eσ（1），. . . ，eσ（i−1）}）（十一）5. 实验我们比较了新的分割方法，从前一节的随机步行者的图像segmenta-我们可以将该分布与随机步行算法从中采样的2-森林上的Gibbs分布进行比较，任务和半监督学习任务。为了将重点放在比较中的方法上，而不是其余的流水线，我们选择了两个经典的任务和众所周知的，相对简单的流水线来计算边权重。1Yp（f）=Ze∈fΣ1we=Zw（f），（12）我们所有的代码都可以在https://github.com/ejnnr/karger_extensions找到。一些额外的细节，如经验运行时，是补充的一部分其中Z=f∈Fsw（f）. 两个发行版都包含材料。项w（f），但其中Gibbs分布具有分区函数Z独立于森林f，分布收缩算法的求和具有置换求和项，该置换求和项具有对f的附加依赖性。注 意 ， w （ e1 ） ， ...， w （ en−2 ） 都 对 C（{e1，. . . ，en−2}）。因此，具有大边权重的2-森林具有高概率，不仅是因为项w（f），而且还因为等式中的第二项（十一）、这意味着种子分割我们使用Grabcut [34]图像，具有来自[14]的稀疏标签为了从图像中创建图形，我们使用了通常的4-连接拓扑，这意味着每个像素都通过一条边连接到它的四个邻居（或在边界处更少）。我们使用PyTorch实现[32]通过整体嵌套边缘检测[40]获得边缘权重。这4608D↑ARI↑Accc [%]↓VoI收缩0的情况。82 ±0。02九十六。3±0。60的情况。24 ±0。02RW0的情况。82 ±0。02九十六。0±0。60的情况。25 ±0。03流域0的情况。83 ±0。02九十六。2±0。50的情况。24 ±0。02电力WS0的情况。83 ±0。02九十六。2±0。50的情况。24 ±0。02表1：接种分割：Grabcut数据集上的平均调整的Rand指数（ARI）、准确度（Acc）和信息变化（VoI）。RW =随机步行者，功率WS =q=2，p→ ∞时的功率分水岭产生每个像素的强度 gi∈[0，1]（除以最大强度之后），其中较高的值对应于由网络识别的边缘用于边缘权重，然后我们使用报告的误差是数据集平均值的标准误差。我们使用了1000次运行的种子分割算法来近似Karger势，这使得近似误差在比较中可以忽略不计。我们使用调整后的兰德指数（ARI），他们的分类准确性和信息的变化（VOI）的四种方法进行比较。对于ARI和准确性，越高越好，对于VoI，越低越好。仅在未标记的像素上计算所有度量图3示出了所使用的种子、边缘检测网络的输出以及四种方法中的每一种的所得分割的示例，每种方法都处于其最佳β值。结果在大多数情况下非常相似-此处显示的分割已被选择，因为它们明显不同。在第一行中，有许多强边，（功率）分水岭遵循不同的wij=exp.Σ−β（gi+gj）2、（十三）与其他方法相比，边缘更宽在第二排，一些边缘丢失，并且四种方法对这种“泄漏”的响应不同其中β是自由参数。图2显示了β对其中一个Grabcut图像的影响。请注意，对于β的中间值，例如β=5，我们可以看到Karger势比第4节中假设的随机游走势具有更高的除了随机步行者之外，我们还比较了分水岭分割，分水岭分割已用于种子分割[6]和半监督学习[3]。这种分割是由分离种子的最大跨度forest引起的[6]。如果只有一个最大生成森林，则Karger势和收缩算法的输出仅是真实Karger势的近似，但误差非常小，以至于它不会明显影响分段的轮廓。在这里，我们使用来自USPS手写数字数据集的训练集的经典基准数据[15，24]。这些标记为数字从0到9的16×16我们计算了所有图像之间的成对欧几里德距离，并基于这些建立10-最近邻图。再次使用径向基函数计算图权值，随机游走势收敛于该分割为β→ ∞。多个最大跨度森林的更一般情况由功率流域框架[5，30]描述，该框架概括了流域和wij=exp.Σ2−βij一个2，（14）随机步行者该框架有两个参数q和p，q=2时，p→ ∞是β→ ∞的随机游走极限，不需要对最大生成森林的个数作任何假设。当有一个唯一的最大跨越森林，Power Watershed退化为Watershed;特别是，如果所有的边权重都是不同的，情况就是这样。因此，我们将边权重四舍五入为8位，以人为地引入具有相等权重的边，从而使Power Watershed有机会相对于Watershed发光。这导致256个不同的可能边权重，与[5]中完全相同。表1显示了整个Grabcut数据集的结果。对于每种方法，我们分别手动优化β，并且对于Karger势和对于随机游走器，β=20但业绩这两种算法在这个范围内是相对稳定的价值观分水岭算法不依赖于β的值，只要β>0。对于Power Watershed，我们使用β=10（尽管它对β的依赖性非常低）。其中a：=max{i，j}∈Edij，其中dij是欧几里得双tances我们使用不同大小的随机子集作为标记顶点，并留下剩余的顶点进行标记。对于每个大小的标记集，我们采样了20个集。表2示出了在这20个样品上平均的未标记数据的准确度。误差是样本平均值的标准误差。如前所述，为每种方法单独选择β值以使性能最大化（对于随机步行者，β=5;对于收缩方法，β=2在整个过程中，我们使用了随机步行器的scikit-image实现[38]，并对上述边权重进行了轻微调整。结果在所有实验中，基于Karger势的新方法与随机walker /谐波能量最小化方法的性能相当。然而，新方法在具有少量标记顶点的半监督学习设置中具有显著更好的结果。4609图2：Karger势的概率估计，与随机步行者/谐波能量最小化的概率估计相比，对于各种图边权重。图3：Karger型收缩、随机游走/谐波能量最小化和（功率）分水岭之间的一些定性差异。对于每种方法，最佳地选择β监督学习任务：我们已经提出了一种基于收缩的算法，该算法的性能与随机步行器/谐波能量最小化一样好或更好，同时具有与边的数量成线性关系的渐近时间复杂度。表2：基于图的半监督学习：USPS数据集上的准确度（%）。RW =随机游走，幂WS =幂分水岭，其中q=2，p→ ∞6. 结论我们已经证明，连续的或仅使用边的局部性质的收缩算法不能有效地解决s-t-mincut问题或正规化切割问题的最优性。另一方面，我们已经证明了Karger算法的某些扩展未来的工作可能会解决的问题是否contrac- tion算法的基础上的全球性能可以用于解决的s-t-mincut问题，或者我们的结果是否可以扩展到更广泛的一类算法。另一个悬而未决的问题是s-t-收缩算法是否可以在实际发生的图上快速找到s-t-mincuts，而不是我们在不可能性证明中使用的最后，Karger未来的研究可能会对这种分布有更多的了解，例如它是否唯一适合于寻找最小切割，或者吉布斯分布是否会产生类似于Theo-rem1的结果。种子2040100200收缩62. 2 ±1。8七十三。1±1。589岁。0±0。592. 6 ±0。2RW五十三7±1。968岁0 ±1。287岁7 ±0。792. 4 ±0. 3流域五十四3±2。0五十八7±1。974岁3 ±1。0八十0 ±0。94610引用[1] 而ra是A。Benczu' r and Da vid R.卡尔格河近似s-t时间复杂度为O~（n2）。在1996年的STOC一个[2] Y.Y. Boykov和M. P. Jolly N维图像中目标边界区域最优分割的交互式图切割。第八届IEEE计算机视觉国际会议论文集，2001年。一个[3] A. Challa，S.丹达湾S. D. Sagar和L.纳杰曼半监督分类的水棚。IEEE Signal Processing Letters，2019。七个[4] Michael B.放大图片作者：Gary L.作者声明：Jakub W.放大图片作者：Richard Peng，Anup B. Rao和沈晨旭。求解SDD线性方程组的时间接近mlog1/2n在ACM第四十六届年会论文集计算理论，2014年。三个[5] Camille Couprie、Leo Grady、Laurent Najman和HuguesTalbot。功率分水岭：一个统一的基于图的优化框架。IEEE Transactions on Pattern Analysis and MachineIntelligence，2011。七个[6] J. Cousty，G.贝特朗湖Najman和M. Couprie分水岭切割：最小跨度森林和水滴原理。IEEE Transactions onPattern Analysis and Machine Intelligence，2009. 七个[7] Enrique Fita Sanmartin，Sebastian Damrich，and Fred AHamprecht.概率分水岭：对所有生成森林进行采样，以进行种子分割和半监督学习。在神经信息处理系统，2019。三个[8] PawełGawrychowski，Shay Mozes，and Oren Weimann.时间复杂度为O（mlog2n）2019. 一个[9] Y. Gdalyahu，D. Weinshall和M.沃曼视觉中的自组织：图像分割，感知分组和图像数据库组织的随机聚类。IEEE Transactions on Pattern Analysis and MachineIntelligence，2001。二个[10] Mohsen Ghaffari、Krzysztof Nowicki和Mikkel Thorup。通过随机2-out收缩的边缘连接的更快算法。第三十一届ACM-SIAM离散算法研讨会论文集，2020年。一个[11] L.格雷迪图像分割的随机游动。IEEE Transactions onPattern Analysis and Machine Intelligence，2006。第1、3条[12] Leo J. Grady和Jonathan R.波利梅尼 离散微积分Springer London，London，2010. 三个[13] D.M. B.T.格雷格波蒂厄斯和艾伦·瑟霍特。二值图像的精确最大后验估计。皇家统计学会杂志，B辑，1989年。一个[14] Varun Gulshan 、 Carsten Rother 、 Antonio Criminisi 、Andrew Blake和Andrew Zisserman。用于交互式图像分割的测地星凸性。2010年IEEE计算机学会计算机视觉和模式识别会议，2010年。六个[15] J.J.赫尔一种用于手写文本识别研究的数据库。IEEETransactionsonPatternAnalysisandMachineIntelligence，1994。七个[16] David R.卡格RNC中的全局最小割，以及简单最小割算法的其他实现。InProceedings of第四届ACM-SIAM离散算法年会，1993年。第1、3条[17] David R.卡格在接近线性时间内的最小切割ACM杂志，2000年。一个[18] 德维德河卡尔·格尔和克里夫·福特·斯坦因。一个O~（n2）的算法最小削减。第25届ACM计算理论研讨会论文集，1993年。二个[19] David R. Karger和Clifford Stein。最小割问题的一种新解法。ACM杂志，1996年。一、二[20] 乔纳森A。Kelner、Yin Tat Lee、Lorenzo Orecchia和Aaron Sidford。无向图近似最大流的几乎线性时间算法及其多商品推广。在2014年年度ACM-SIAM离散算法研讨会上。2013. 1[21] 诉Kolmogorov和R.扎宾什么样的能量函数可以通过图割最 小 化 ？ IEEE Transactions on Pattern Analysis andMachine Intelligence，2004。一个[22] I. Koutis，G.L. Miller和R.朋求解SDD线性系统的最优性逼近2010年三个[23] I. Koutis，G.L. Miller和R.朋近似-mlogn时间SDD线性系统的求解器。2011年三个[24] 放大图片创作者：Bernhard E.作者：John S.放大图片作者：Donnie Henderson，R. E.作者：Howard，Wayne E.Hubbard，and Lawrence D.杰克 基于反向传播网络的手写数字识别。神经信息处理系统进展。1990. 七个[25] Lei Li，Hongbo Fu，and Chiew-Lan Tai.快速草图分割和标 记 与 深 度 学 习 。 IEEE Computer Graphics andApplications，2019。一个[26] 刘 哲 宋 玉 清 Victor S. Sheng ， Liangmin Wang ， RuiJiang，Xiaolin Zhang，and Deqi Yuan.基于改进U-Net和图割的肝脏CT序列分割专家系统与应用，2019。一个[27] 安东尼奥·莫利纳·洛维特和布莱斯·桑德伦德。近线性时间最小割的一个简单算法2020年在特警队一个[28] Fang Lu，Fa Wu，Peijun Hu，Zhiyi Peng，and DexingKong.通过卷积神经网络和图切割自动3D肝脏定位和分割。International Journal of Computer Assisted Radiologyand Surgery，2017。一个[29] Suvadip Mukherjee、Xiaojie Huang和Roshni R.巴加利亚使用基于图切割的深度学习先验的肺结节分割。2017年IEEE第14届国际生物医学成像研讨会（ISBI 2017），2017年。一个[30] 劳伦特·纳吉曼由于γ-收敛，扩展了功率分水岭SIAMJournal on Imaging Sciences，2017。七个[31] P. Nardelli，D.Jimenez-Carretero，D.Bermejo-Pelaez湾R.Washko，F. N. Rahaghi，M. J. Ledesma-Carbayo和R. 圣何塞就是你的爸爸。肺动脉IEEE Transactions onMedical Imaging，2018。一个[32] 西蒙尼克劳斯一重新实现的HED使用PyTorch。https://github.com/sniklaus/pytorch-hed，2018. 六个4611[33] 彭波和李丽莲。情感教育：基于最小割的主观摘要情感分析。在Proceedings of the 42nd Annual Meeting of theAssociation for Computational Linguistics（ACL-04），2004。一个[34] 卡斯滕·罗瑟弗拉基米尔·科尔莫戈洛夫安德鲁·布莱克。“GrabCut”：使用迭代图切割的交互式前景提取。ACMSIGGRAPH 2004 Papers，2004年。1、6[35] J. 谢尔曼近似线性时间内的近似最大流量2013年一个[36] Jianbo Shi和J.马利克归一化切割和图像分割。IEEETransactionsonPatternAnalysisandMachineIntelligence，2000。一、二[37] Daniel A.Spielman和Shang-Hua Teng。用于图划分、图稀疏化和求解线性系统的近线性第36届ACM计算理论研讨会论文集，2004年。三个[38] 约 翰 尼 斯 ·L. 放 大 图 片 作 者 ： Sco¨ nbe r ge r ，JuanNunez- Iglesias ， Fran c¨ oisBoulogne ， JoshuaD.Warner， NeilYager ， Emmanuelle Gouillart ， and TonyYu.Scikit-image：Python中的图像处理PeerJ，2014. 七个[39] Z. Wu和R.莱希数据聚类的最优图论方法：理论及其在图像分割中的应用IEEE Transactions on Pattern Analysisand Machine Intelligence，1993。一个[40] 谢赛宁、涂卓文整体嵌套边缘检测。2015年IEEE六个[