目录
简介
提纲
任务
已有的相关工作
新的方法
三个模块
为什么需要图滤波？
实验结果
相关指标对比和消融实验
总结
优势
局限性
未来改进方向
创新
补充（对比表示学习必知的几种训练目标-损失）
Contrastive Loss
Triplet Loss
Lifted Structured Loss
N-pair Loss
NCE
InfoNCE
Soft-Nearest Neighbors Loss
参考
简介随着信息时代的蓬勃发展，产生了大量多视图属性图图数据。随即，也出现许多的多视图聚类方法，但这些方法只利用数据中的多属性信息或者多拓扑图信息，没有完整地利用属性图数据的所有信息。
本期 AI Drive，电子科技大学计算机科学与工程学院硕士生潘尔林，分享其团队在这个问题上取得的新进展，也是他们发表于 NeurIPS 2021 的最新工作：多视图对比图聚类。
在这个工作中，他们提出了一个简单而通用的、多视图的属性图数据聚类方法：多视图对比图聚类。
论文标题：
Multi-view Contrastive Graph Clustering
论文链接：
https://arxiv.org/abs/2110.11842
代码链接：
https://github.com/panern/mcgc
首先介绍研究的目标和要解决的任务：处理属性图数据、多视图属性图的聚类问题。
图数据在现实中大量存在，很多场景下的数据结构都可以表示成为一个图数据（或者网络）。例如，paper 或作者通过引用关系，可以构建出引用网络；用户信息和他们在社交媒体上的关系构成社交网络；知识图谱等也是图数据等。
属性图是图数据的一种（Attributed Graph）。属性图中既包含关系图，同时每个节点拥有自己的属性特征。以社交网络作为属性图的一个例子。每个节点就是一个用户，包含用户的个人档案，也就是自身的社交信息（包括个人兴趣、注册信息、性别年龄等）。不同用户之间存在着 “边”，表示用户之间的社交关系（如转发，关注等）。
以具体的数据来看，节点属性是维度为 N×D 的属性特征矩阵。其中，N 表示节点数量，D 表示属性特征的数量。如表中所示，有 4 个用户，那就是 4 个节点，每个用户各有 4 种属性。关系图一般用邻接矩阵（adjacency matrix）(A)表示。其中如果，用户，也就是节点 i 与 j 之间存在关系，例如社交网络的转发、关注、分享关系等，矩阵中的对应位置值为 1，否则为 0。
更复杂的情况，社交网络中，每个人角色为不同，个人信息也不同。对应的属性图数据中，同一个节点，可能对应多个属性向量。例如图中的节点 13，拥有多个属性特征。而对于同一批数据点，数据点之间的关系也存在多种。不同的关系意味着会有不同的拓扑结构。如图，相同的数据点，至少有两种拓扑结构，对应两个邻接矩阵。简而言之，有多个属性或多个关系图的，就是多视图属性图数据。
图聚类（此处的图聚类指的是将图上的节点聚类，并不是对整个图分类）将图上的节点分成不同集群，每个集群内的点要尽量相似，不同集群间要尽量不同。对于多视图属性图聚类，也是一种图聚类，但其考虑的信息更多，要同时基于给出的多种类型的节点特征和多个关系图的信息，完成图节点聚类任务。
但要要完成多视图属性图聚类任务，就面临两个问题：一是如何聚合多个视图间的一致性信息？因为虽然是不同视图，但都是表示同种事物，其在多个视图中是有共享信息的；二是如何同时处理属性信息和关系图？此外还有追求更高的聚类准确度等要求。
已有的相关工作
相关研究主要介绍多视图聚类和对比学习思想。
多视图聚类，试图挖掘不同视图间的一致性信息。对于单视图，也可以处理多视图数据。例如对每个多视图单独处理，最后取结果最好的视图。在评测性能的时候，取指标的平均值或最优值。但单视图方法没有使用完整地数据，意味着可能会丢失一些重要信息。
多视图数据可以更全面地描述数据，而且多视图的聚类方法的话有很多，不限于提到的这些方法。但大多数方法要么只利用属性信息，要么只用关系图，并不能直接应用在属性图上。例如,只利用邻接矩阵或者学习特征表示方法进行图聚类，不能直接应用在属性图上，因为属性图同时具备以上两种信息。
对于属性图的聚类问题，也有一些好方法，例如基于 GCN 设计的 （MAGCNCheng et al., 2020）和 O2MA（Fan et al., 2020）。
其中，MAGCN 利用图神经网络，重构多视图的特征和共同关系图。简而言之这种方法是利用一张共同的图，通过 GCN 学习得到不同视图的嵌入，最后再重构每个视图的特征和关系图。但其这意味着只能处理一个关系图的属性图数据。
O2MA 通过一些方法选取多个视图中最丰富的视图，再用选取的视图，重构其他视图的特征。被选取的视图，是利用关系图选取的。但其信息最丰富，不代表这个视图能包含所有的重要信息，这样做也可能丢失个别重要信息。其局限性是只能处理有一种属性、多个关系图的属性图数据，不能处理多种属性的图数据。
我们的方法与以上两张方法有所不同，且比较通用。其既能处理多个属性的视图数据，也能处理拥有多个关系的视图数据。
在研究过程中，也利用了对比学习思想。关于对比学习思想，个人认为一是主要区分是与不是，而不是所有像素级的信息。毕竟，分辨比还原要简单，只需要更小的计算代价。举个钞票的例子，分辨钞票要比重新画出它要简单得多。二是要学习更加重要、有效的信息，不用学习无关紧要的信息。
对比学习试图最大化所有正样本之间的相似度，拉近正样本，推远负例。正样本一般是同一实例通过数据增强得到的，不同实例处理得到的为负样本。例如，原图和经过数据增强得到另外的图片，包括改变尺寸、模糊图片、颜色扭曲等处理，得到其他类似图片，这就构成一组正例。来自于不同原始的图片构成的其他图片就是负例。比如下图老虎就是负例。
通过对比损失训练模型，拉近正例之间的距离，将负例推远。
聚类其实是把相似的实例分在同个集群里，而对比学习是拉近正样本（高度相似），推远负例。直观来看，两者有相似之处。有些方法如 Mvgrl（Hassani and Khasahmadi, 2020）和 Completer(Lin et al., 2021)，就考虑使用对比学习来提高聚类的性能。当然这些方法不是纯聚类方法，只是一种特征学习方法。
Mvgrl 将邻接矩阵转化得到的扩散矩阵视为正例。在学习得到的不同图表示间施加对比学习来训练模型。
Completer 寻找正例的方法不一样。它将不同视图之上的同一个样例当作正样本。通过拉进不同视图间同一样例的表示来训练得到更好的模型。
但是回到属性图聚类上，对于属性图中的点，又该怎么取正例呢？
新的方法
-
Graph Filtering（图例波模块）
-
Graph Learning（图学习模块）
-
Graph Contrastive Regularizer（图对比模块）
给定一个属性图数据。V 表示节点的集合，有 N 个节点。E 表示边的种类，X 表示属性特征。
我们的目标函数如下：
我们使用的是滤波后的特征，而不是原始特征。
以下介绍三个模块作用：
-
图滤波模块就用以处理原始数据；
-
图学习模块从多视图中学到一致图；
-
图对比损失用于提高图的质量。
首先因为图上的信号，在相邻点之间是平滑的，意味着在相邻点应该趋于近似值。其次数据经过滤波之后，得到的特征表示有利于聚类或分类。而且图滤波后得到特征，很大程度保留了图的结构信息，同时消除了噪音干扰。
一般来说，处理后的数据越平滑，滤波效果越好。输入数据 X，以下式子可以表示滤波时的平滑度。
其中 L 是拉普拉斯矩阵。得到的值越小，表示平滑度越高。可以看出，当特征值 λ 越小时，平滑度越高。则考虑使用低通滤波器，获得低通滤波后的平滑特征。平滑的特征可以通过解决这样一个优化问题得到：
可以求出函数的封闭解。首先保留封闭解泰勒展开式的第一项，并且考虑更高阶的情况，最后得到一个 m 阶的滤波表达式。
其中的 I 是单位矩阵， X 是原始数据，m 是滤波阶数，S 是可以滤波参数，H 是滤波之后的得到的平滑信号。
本文中：m 一般保留 2（多数数据集 M=2 的效果比较好，不同数据集有差异），s 一般小于 1。
通过滤波前后的 tsne 可视化可以看出，经过 DBLP 滤波之后，特征可分性要增强很多。
图学习模块主要是从滤波之后的平滑数据中学到一个一致图，同时综合多个视图信息。可以通过自表达性质来得到一致图。自表达性质指的是，每个数据点都可以由其他数据点通过组合表达出。
例如在单视图上，目标函数为：
前一项是重构项，S 是得到的组合图。第二项是正则项，一般有多种形式，比较常见的有 L1、L2 范数等。
对于多视图，因为每个视图的作用不同，应该考虑其权重。此处引入权重参数 λ, 用来自适应权重调节不同视图间的权重，最后要学习的 S 是一致的。最后一项是为了自适应求出每个视图的权重。
图聚类是指将图上的节点分成不同集群。其中要求同个集群内的点尽量相似，不同集群内的点尽量不同。对比学习，就试图拉近正样本，推远负例。为此我们使用一个图对比正则项来提高图的聚类亲和性，使图更利于聚类。
对于图像内每个节点和它的 k 近邻视为一个正例对，如图中，灰色节点和他的红色近邻视为正例。最小化图对比正则项试图拉近节点间的距离。通过减少类内差异性，使红色节点更趋向于灰色节点。对于整体的数据而言，更利于后面的聚类。
使用数据集的情况有两种，一是具有多个图的属性图数据，二是有多个属性特征的属性图数据。但理论上来说，通过图滤波和图学习模块，本方法可以处理多图和多属性的属性图数据。Baselines，包括单视图和多视图的方法都，属性图聚类的方法和基于对比学习思想的方法。
得出的结果，相比于单、多视图的方法，此方法确实有性能的提升。
与另两个方法比起来，提升得更多。但提升太多不是说明其他方法不好，因为其他两个方法并不只是单纯的聚类方法，而是表示学习学习方法。去除滤波以后，发现其性能下降了。但要注意一点，各数据对于滤波的敏感性是不同的。
使用完整的数据的话，丢失的信息比较少；但如果只使用单视图或只用信息相对丰富的视图，就可能丢失重要信息。数据上来看，使用完整视图得到的效果是最好的。
1.本文介绍的方法可以快速有效的从原数据获得一种有利于聚类的特征表示，并且保留数据的结构特征（通过图滤波实现）。
2.能同时处理带有多个属性矩阵或者多个关系图的属性图数据（通过图滤波和图学习模块实现）。
3.对于多图数据和多属性数据都取得不错的聚类性能（通过图滤波模块、图学习模块、图对比模块实现）。
1. Large memory：可拓展性不好，占用过大的内存。一是学到的一致图，是 N×N 的矩阵。如果在大型数据中， N 非常大，这时就会占用大量内存。二是滤波，滤波也会进行 N×N 的矩阵计算，也会占用大量内存。
2. Inefficient optimization：因为采用的是逐个更新（梯度更新），S 是 N 乘 N 的。即使 S 是对称的，也要处理一半的数据量，效率较低。得到的结果可能只是局部最优，比如 S=I，因此初始化矩阵的选取比较重要。
1. 首先要减少内存消耗，提高可扩展性。如果 S 还是 N×N 矩阵，对大数据而言不友好。所以考虑采用其他方法。例如选出 m 个代表性的点（锚点），其他的 N 个数据用跟这 m 个点构建的一个关系图表出。例如将 H 替换成 B（B 可以通过 Kmeans 取质心得到，也可以随机采样，或者根据其他方法来选出 m 个点）。但目前用原方法尝试过，结果发现除 DBLP 外，其他性能都下降了很多。
2. 使用其他形式的图对比正则项去拉进相似的样本点。也就是设计一种更加容易优化的正则项。同时在拉近距离时，还可以考虑拉进更高阶的近邻。而且貌似使用更高阶信息或更高阶相似度，配合简单的正则化项，在亚马逊数据集上得到的结果，都比原来使用图对比正则化项还要优越（提升超过将近两个百分点）。
创新1. 我们利用对比学习思想拉进近邻点，用来提高图的聚类亲和力；
2. 我们提出一种通用于多图或者多属性的属性图数据的聚类方法，方法包括了图滤波，图学习和图对比三个模块；
3. 我们的方法在几个基准数据集上取得了很好的聚类性能。
未来可以进一步尝试使用易于优化的其他正则化项来拉进近邻的距离，或者挖掘高阶的相似近邻等。
补充（对比表示学习必知的几种训练目标-损失）对比学习的主要思想就是相似的样本的向量距离要近,不相似的要远.对比学习在有监督/无监督场景下都取得了非常亮眼的成绩,所以是我们炼丹的必备知识.早期的对比学习是只有一个正样本和一个负样本进行对比,最近的训练目标变成了一个batch内多个正/负样本进行训练.
Contrastive Loss有一系列样本{xi},它们的label yi = {1, ..., L}, L类,还有个函数f将样本xi映射成embedding,有着相同yi的样本有着相似的embedding, 因此对比学习loss定义如下:
Triplet loss大家应该并不陌生,最早出现在FaceNet的论文里,这篇论文主要学习人脸表达,需要同一个人在不同角度位置的表达都很相近.
定义一个锚点(anchor) x,有个正例x+和一个负例x-,所以目标函数就是要最小化x和x+的距离,最大化x和x-的距离,定义如下所示:
该loss为了更好的计算效率,充分利用了一个batch内所有pairwise的边.
Dij = || f(xi) - f(xj) ||2, Loss函数定义如下:
红色部分是为了挖掘hard负样本,但是不是很平滑,难收敛,因此可以改为下式:
在负样本同时有多个的时候,{x,x+, x1-, ..., x(N-1)-},包含1个正样本和N-1个负样本,N-pair loss定义如下所示:
NCE本身是统计模型做参数估计的方法,思想就是用罗杰斯特回归来区分数据和噪声.非噪声样本的概率用P表示,噪声样本的概率用q表示,如下所示:
所以NCE的loss函数定义如下:
我们看到NCE loss只对一个正样本和一个噪声样本生效.
InfoNCE受到NCE的启发,InfoNCE使用了交叉熵损失,用在一个正样本和一系列噪声样本上.给定一个上下文环境c,我们可以得到条件概率p(x|c),N-1的负样本直接从概率分布p(x)提取,独立于c. 我们有个样本集合X = {xi},i=1~N, 其中只有一个正样本x_pos, 我们能得到下式
f(x,c)就是模型的打分函数,所以InfoNCE loss优化log loss,如下式:
该loss扩展到包含多个正样本,假设有个batch {xi, yi} i = 1~B, 该loss会有个温度系数控制,如下所示:
温度τ用于调整特征在表示空间中的集中程度。例如，当温度较低时，损失主要是由小距离造成的，而大范围分离的表示不能起到很大作用。
参考NeurIPS 2021 | 简单且通用的多视图对比图聚类方法
对比表示学习必知的几种训练目标
