前言

参考 https://blog.csdn.net/qq_32797059/article/details/93031052

论文链接：https://arxiv.org/abs/1503.05782
http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.72.4127
github：https://github.com/ZhouFengtao/MachineLearning/tree/master/HAP
这篇文章算是超图方面的文章鼻祖，当作综述来看，系统了解一下超图

我们通常将研究对象赋予成对的关系，可以用图来表示。然而，在许多现实问题中，我们感兴趣的对象之间的关系要比两两关系复杂得多。天真地将复杂的关系压缩成两两的关系将不可避免地导致信息的丢失，而这些信息对我们的学习任务是有价值的。因此，使用超图来代替完全表示我们感兴趣的对象之间的复杂关系，从而产生了使用超图学习的问题。本文的主要贡献是将原本适用于无向图的光谱聚类方法推广到超图，并在超图聚类方法的基础上进一步发展了超图的嵌入和转换分类算法。

在数学中，超图是一般图的泛化，超图里的边可以连接任意数量的顶点。一般，超图 $H$ 可以表示为顶点-边对 $H=(X,E)$，其中，$X$ 是所有顶点元素的集合，$E$ 是 $X$ 的非空子集。 如果用 $P(x)$ 表示X所有子集的集合，那么 $E$ 就是 $P(X)$ 的子集，被称作超边或者边。

在图中，边表示一对顶点，超边则表示任意数量顶点的集合。为了研究方便，定义了一种拥有相同基数的超图，称作，$k-uniform$ 超图，$k-uniform$ 超图中的超边连接 $k$ 个节点，故称超边的大小为 $k$。在以上的定义下，$2-uniform$ 超图就是上文提到的图，$3-uniform$ 超图表示无序的三元组的集合。

1. Introduction

图可以是无向的，也可以是有向的。它取决于对象之间的成对关系是否对称。

• 欧氏空间中与核矩阵相关的点集是无向图的一个典型例子。
• 至于有向图，一个著名的例子就是万维网。超链接可以被认为是一个有向边,因为给定任意链接我们当然不能指望这逆的存在,也就是说,基于超链接的关系是不对称的。

在许多现实问题,代表一组复杂的关系对象作为无向图或有向图是不完整的。为了说明这一观点，让我们考虑一个问题，将一组文章分组到不同的主题。对于一篇文章，假设我们所掌握的唯一信息是这篇文章的作者。如果相关文章至少有一个共同作者，可以构造一条边将两个顶点连接在一起的无向图(图1)，然后应用基于无向图的聚类方法，如谱图技术。通过给每条边分配一个权值，这个权值等于共同作者的数量，可以进一步修饰无向图。上面的方法可能听起来很自然，但在它的图表示中，我们显然忽略了同一个人是否联合撰写了三篇或更多文章的信息。这样的信息丢失是意料之外的，因为同一个人写的文章可能属于同一主题，因此这些信息对于我们的分组任务很有用。

解决上述方法中出现的信息丢失问题的一种自然方法是将数据表示为超图。超图是一条边可以连接两个以上的顶点的图。换句话说，一条边是顶点的子集。在下面，我们将统一地把通常的无向图或有向图称为简单图。此外，无需特别说明，图是无向的。很明显，简单图是一种特殊的超图，每条边只包含两个顶点。在前面提到的文章集群问题中，构造一个超图非常简单，顶点表示文章，边表示作者(图1)。每条边包含相应作者的所有文章。更重要的是，我们可以考虑在边缘加上正的权值，如果我们有的话，可以把我们的先验知识编码到作者的作品中。例如，对于一个从事广泛的领域工作的人，我们可以给他对应的边分配一个相对较小的值。因为他的先验知识可能对他文章的归属领域影响较小。

现在我们可以用超图来完整地表示对象之间的复杂关系。然而，一个新的问题出现了。如何划分超图?这是本文中要解决的主要问题。划分简单图的一种强大技术是谱聚类。因此，将光谱聚类技术推广到超图，更具体地推广归一化切割方法。此外，对于简单的图，超图的实值放松规范化的减少则会导致半正定矩阵的特征分解，半正定矩阵的特征分解可以被视为一个所谓的拉普拉斯算子模拟简单的图，因此称之为超图拉普拉斯算子。基于此本为提出基于超图拉普拉斯算子的超图嵌入和转换推理算法。

实际上已经有大量关于超图划分的文献，它产生于各种实际问题，如划分电路网表，聚类数据，图像分割。然而，与目前的工作不同的是，它们通常使用我们在开始讨论的启发式或其他领域启发式将超图转换为简单图，然后应用基于谱聚类的简单图技术。

2. Parameter Settings

用 $V$ 代表一组对象，$E$ 代表超边集合，基于此超图可以表示为 $G=(V,E)$。

因此超边中仅含有两个顶点的图即为简单图，加权的超图意味着对于每一条超边进行加权，叫做超边的权重，加权超图可以表示为 $G=(V,E,w)$。

超图中节点的度的计算方式为 d(v)=∑{e∈E∣v∈e}w(e)d(v)=\sum_{\{e \in E|v \in e\}}w(e)d(v)=∑{e∈E∣v∈e}​w(e)，超图中超边的度的计算方式为 $\delta (e)=|e|$ 将超边当作一个集合，其中 $|\cdot |$ 代表集合的基数。

当定义超边中顶点间的路径关系时如果 $v_1$ 和 $v_k$之间可达则应存在 $v_1,e_1,v_2,e_2,...,e_{k-1},v_k$ ，其中 {vi,vi+1⊆ei},i∈[1,k−1]\{v_i,v_{i+1} \subseteq e_i\},i \in [1,k-1]{vi​,vi+1​⊆ei​},i∈[1,k−1]。如果超图是连同的则超图中的每一对节点之间存在路径，未做特殊强调则认为所有超图是连通的。

超图可以表示为 $|V|\times |E|$ 的矩阵 $H$ 其中元素满足 $h(v,e)=1,v\in e$，这种形式叫做超图的关联矩阵 $H$，则每个节点的度可以表示为 $d(v)={\sum }_{e\in E}w(e)h(v,e)$，每条超边的度可以表示为 $\delta (e)={\sum }_{v\in V}h(v,e)$

在此基础上我们可以定义顶点对角度矩阵 $D_v$ ，超边的对角度矩阵 $D_e$，和超边权重度矩阵 $W$。之后超图的邻接矩阵就可以表示为 $A=HW{H}^T-D_v$

3. Normalized hypergraph cut

很多超图问题可以通过超图分割来解决，超图分割指的是存在一条超图切（Hypergraph Cut）把超图的顶点集分割为两个子集，一个是顶点集 $S$，另一个是其补集 $S^c$ 。

首先定义一个顶点的子集 $S\subset V$，超图的切割定义为 $G=(V,E,w)$ 中 $V$ 被切割成两部分 $S$ 和 $S^c$ ，这样我们可以定义如果一条超边同时与 $S$ 和 $S^c$ 中的顶点相关联，则这条超边被切割。

对于子集 $S$ 而言，我们可以将其超边边界定义为一个超边集： ∂S,∂S:={e∈E∣e∩S≠∅,e∩Sc≠∅}\partial S ,\partial S :=\{e \in E|e\cap S \not = \emptyset,e \cap S^c \not = \emptyset\}∂S,∂S:={e∈E∣e∩S​=∅,e∩Sc​=∅}，并定义 $S$ 的容量 $volS$ 为 $S$ 中顶点的度之和，因此可以表示为 $volS:={\sum }_{v\in S}d(v)$，进而可以得到超边边界的容量表示为 $$vol\partial S:=\sum _{e\in \partial S}w(e)\frac{|e\cap S||e\cap S^c|}{\delta (e)}\text{\hspace{1em}(1)}$$

显然 $vol\partial S=vol\partial S^c=vol(S,S^c)$，所以，我们可以把超边边界的体积看做两个顶点子集之间的连接紧密度，而顶点子集的体积可以看做是子集内部顶点之间的连接紧密程度。类似于普通图的图切问题（Graph Cut），对于超图分割，我们同样试图找到一个超图切。这个超图切将超图分割为两个子集，两个子集之间的连接程度是稀疏的，而子集内部顶点之间连接是紧密的。所以，我们可以将超图分割问题转化为下面的优化问题：利用上面介绍，我们可以将这种自然分割形式化为
$$argminc(S):=vol\partial S(\frac{1}{volS}+\frac{1}{vol{S}^c})=vol(S,S^c)(\frac{1}{volS}+\frac{1}{vol{S}^c})\text{\hspace{1em}(2)}$$

对于简单图来说 $|e\cap S|=|e\cap S^c|=1$ 和 $\delta (e)=2$。在上式中，$vol(S,S^c)$表示超图的两个顶点子集之间的边界的体积，$vol(S)$与$vol(S^c)$分别表示两个顶点子集的体积。根据文献，可以得知超图切的最优化目标与一个瑞利商一致。假设一个列向量$q$，其维度为超边中的顶点的个数，其元素值为：
$$q(v)=\{\begin{array}{ll}+\sqrt{{\eta }_2/{\eta }_1}& v\in S\\ -\sqrt{{\eta }_{!}/{\eta }_2}& v\in S^c\end{array}\text{\hspace{1em}(3)}$$

在上式中，${\eta }_1$ 与 ${\eta }_2$ 分别表示 $vol(S)$ 与 $vol(S^c)$。由上式，可以将超图切的优化目标转化为：
$$argminC(S)=\frac{q^{T}Lq}{q^T\Lambda q}\text{\hspace{1em}(4)}$$

矩阵 $\Lambda$ 是一个对角矩阵，对角线上的元素的值为 $vol(S)$。在上式中，涉及一个图学习中的重要概念——拉普拉斯矩阵。拉普拉斯矩阵是图的一种矩阵表示,是一个对角矩阵，$L=D-W$，$D$ 为图的度矩阵，$W$ 为图的邻接矩阵。更长用到的是拉普拉斯矩阵的标准化表示，即 $D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}$。在超图中，超图的拉普拉斯矩阵可以表示为：
$$L=D_v-HW{D}_e^{-1}{H}^T\text{\hspace{1em}(5)}$$

在上式中，$H$ 表示超图的点边关联矩阵，若顶点 $v_i$ 在超边 $e_j$ 上，则 $H_{i,j}=1$，否则为0。前文假定的向量 $q$ 被认为是超图的切向量。由此可以分析出，超图的最优化切割问题的解转化为了最小化向量 $q$ 的问题，该问题是一个组合优化问题。从数学的角度分析该最优化问题，求解满足条件的最小化向量q就是求解矩阵束 $(L,\Lambda )$ 的最小特征值对应的特征向量。根据文献可知，上述问题的简化解可以从求解下式的最小非负特征值对应的特征向量来得到：

$$\Delta =I-D^{-\frac{1}{2}}H{D}_e^{-1}{D}^{-\frac{1}{2}}\text{\hspace{1em}(6)}$$

在上式中，I是一个单位矩阵，上式的结果就是超图的标准化拉普拉斯矩阵。对于超图分割问题而言，可以进一步的将优化目标函数推导成标准化损失函数，如下所示：

其中，向量 $f$ 就是超图切，如果从图嵌入的角度来思考该优化结果，向量 $f$ 也可以被看成是超图的嵌入。

4. 超图正则化属性预测器(HAP)

4.1 属性超图

对于给定的一个数据集 $X$ 而言，可以通过一个超图 $G=<V,E,W>$ 来描述数据集中样本之间的属性关系。属性（Attribute）即是用来描述每个样本所具有的特性的关键词，如颜色、有没有尾巴等。在超图 $G$ 中，每个样本 $x\in X$ 对应超图中的顶点 $v\in V$。对于超图的超边的构建，将具有同一个属性的样本归到同一条超边里。因为每个样本具有若干个属性，所以一个顶点可以属于多条超边，如果在该数据集中有 $m$ 个属性，那么超图就具有 $m$ 条超边。因为我们通过该超图来描述数据之间的属性关系，所以我们称该超图为属性超图。

假定一个 $n\times m$ 维二值矩阵 $H$ 为该超图的点边关联矩阵，其中矩阵元素的值定义如下：
$$q(v)=\{\begin{array}{ll}h(v,e)=1& v\in e\\ h(v,e)=0& v\ne e\end{array}\text{\hspace{1em}(7)}$$

与前文中提到的超图的构建方式相同，我们定义超边的阶为超边包含的顶点的个数，由上式可以得到：
$$\delta (e)=\sum _{v\in V}h(v,e)\text{\hspace{1em}(8)}$$

超图的顶点的度定义为经过该顶点的所有超边的权重之和，如下：

$$d(e)=\sum _{e\in E|v\in V}w(e)=\sum _{e\in E}h(v,e)w(e)\text{\hspace{1em}(9)}$$

前文中，我们并没有提及超边的权重的定义方式。在超图中，超边的权重的定义方式根据实际情况而选定，在本文中，我们假定超边的权重为超边上任意两个顶点之间的热核距离的平均：

$$w(e)=\frac{1}{\delta (e)(\delta (e)-1)}\sum _{v_i,v_j\in V}{e}^{-\frac{||x_i-x_j|{|}^2}{u}}\text{\hspace{1em}(10)}$$

同时，矩阵 $D_e$、$D_v$、$E$ 分别为 $\delta (e)$、$d(e)$、$w(e)$的对角阵形式。

4.2 超图正则化属性分类器

超图学习在计算机视觉与机器学习上应用时，一般采用标准化超图来描述数据之间多元关联关系，即前文中所提到的 $D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}$。本节中所介绍的超图正则化属性预测器的主要思想来源于基于标准化超图的直推模型，但是与基于标准化超图的直推模型不同的是，超图正则化属性预测器是一个有监督的模型，在对属性预测器进行训练时，构建超图所用到的数据全部为有标签的数据。

前文提到，超图分割的目标是使得不同属性的样本之间的连接程度尽量稀疏，同属性样本之间的样本到的连接程度尽量紧密，换而言之，也就是超图切应该尽量不破坏样本之间的属性关系。同时一个样本具有多个属性，所以，在该算法中，超图正则化属性预测器的最终学习结果是一组切向量 $F=[f_1,f_2.......f_m]$，而不是一个切向量。根据前文中所推导的超图分割的损失函数，可以将属性超图分割的损失函数定义如下：

在上式中，$L_H$ 是描述训练集样本之间的属性关系的标准化超图拉普拉斯矩阵，$F$ 是训练集样本在该超图切下的属性预测值。所以为了达到更佳的属性预测结果，在最小化超图切的同时，还应该进一步的最小化训练集样本的预测属性与真实属性之间的误差，该误差值采用欧氏距离进行描述，即：

$$\Delta (F,G)=\sum _{i=1}^m||f_i-y_i|{|}^2=||F-Y|{|}^2\text{\hspace{1em}(11)}$$

在上式中，矩阵 $Y=[y_1,y_2......y_m]$ 是训练集样本的属性标签矩阵。不难看出，属性标签矩阵可以通过属性超图的点边关联矩阵来构造出来，即 $Y=2H-1$。如果将该约束项添加到HAP算法的损失函数中，可以得到：

在上式中，$\lambda$ 是一个用于权衡超图切损失与分类损失的正参数。通过求解上式，可以得到一组既能满足最优化属性超图分割，又能使得属性的预测结果误差尽量小的切向量。

可以将超图的分割问题看作一个超图嵌入的问题，得到的超图切向量就是超图的一组嵌入向量。所以，属性超图的分割问题就可以被看成是一个特征空间到属性空间的嵌入过程。这样，超图正则化属性预测器的求解问题就可以被转化为求解一个样本特征空间的到属性空间对其的超图嵌入的映射问题。假定样本对应的映射矩阵为 $B$，则对应的映射过程如下:
$$F=X^{T}B$$

与此同时，可以对损失函数添加一个二范式约束，用于避免在求解最优化超图切的过程中产生的过拟合问题。与正参数 $\lambda$ 的作用类似，正参数 $\eta$ 用于控制对二范式约束的惩罚。超图切的损失函数可以进一步被改写为：

拉普拉斯矩阵具有一些特殊的性质，由前文可知拉普拉斯矩阵是一个对称矩阵，同时拉普拉斯矩阵是半正定的。所以，上式损失函数的求解可以转化为一个正则化最小二乘法问题的求解，对投影矩阵求偏导即可求解，求解过程如下：

对于未知属性的图像样本z，可以通过投影矩阵B将其从视觉特征空间投影到属性空间获得其属性值：