前言

本文内容为笔者学习Google data Mining Team在NIPS2020上的Workshop的笔记。

该项目主页为Graph Mining & Learning，pdf版的链接为Mining and Learning with Graphs at Scale。

Introduction

什么是图

图是一种表示实体之间的关系的数据。

其中，实体(entity)指的是节点(node)。关系(relationship)指的是边(edge)。

一般而言，图有如下特点：

1. 大量的边
2. 多种类型的边和多种类型的节点
3. 有高度复杂的结构

于是，图可以被用来表示社交网络、交通网络等。

图的种类

一般而言，图可以被划分为两种类别——自然图(Natural graphs)和相似性图(Similarity graphs)。

自然图

自然图中，其边的关系来源于外部的实际情况或数据。换言之，自然图所表示的实体及关系是现实世界中存在的。例如，支付网络中的每一笔交易可以看作是一个边，连接着支付方和接收方；社交网络中，两个人之间的友谊关系也可以表示为一个边；道路网中，道路连接着不同的地点；还有共同点击或共同观看的情况，如果两个项目被同一个人点击或观看，它们之间就可以用一个边来表示。这种图的特点是其边的存在和性质是由现实世界中的关系或交互确定的。

相似性图

与自然图相反，相似性图中的边的关系来自于节点之间的相似度。在这种图中，我们首先有一大堆元数据或数据，然后通过度量数据之间的相似性或距离来为这些数据构建图的结构。例如，如果我们有一组文章，可以基于文章内容的相似度（比如使用关键词的相似性或文章的主题相似性）来连接文章，构成一个图。在这种情况下，边的创建是基于对数据本身特性的分析和计算，而不是基于外部已存在的关系。

注意： 在我们处理相似性图的时候，每个节点原本的元数据(meta-data)我们依然可以使用。对于高维元数据，使用预处理/预计算的方式可以避免许多重复计算，从而节省很多时间。

为什么要用图？

计算抽象概念

所谓"计算抽象概念"，原文"Computation on abstract concepts"，指的是我们可以利用图来处理复杂的事务。举例来讲，社交网络中的人际联系、交通系统中的路线连接、科学研究中的因果关系往往都是很复杂的，而其中的许多数据都可以归纳为实体间的相互作用和联系，也就是图。图是理解和操作这些关系的有力工具。图不仅能帮助我们理解和分析局部（即直接连接的实体间的）信息，而且还能帮助我们抽象这些信息。这意味着我们可以从特定的实例或局部情况中提取出通用模式或原则，通过对局部信息的抽象，图使我们能够从整体数据中提取出有用的全局信息，这可能涉及识别整个网络中的关键节点（比如社交网络中的意见领袖），发现群体结构（比如社区检测），或者理解整体结构如何影响个体行为和系统性能。

###计算多模态数据

许多场景下，我们不得不同时处理多种模态的数据，如视觉的、文本的、语义的信息，这些数据相互关联。通过图，我们可以将多种模态的数据相关联，并进行计算。

全局视角

图的结构可以帮助我们发现数据中的模式、群组或关系，甚至可以量化一些本质上难以直接度量的概念。

以上图为例，对于一张模棱两可的苹果图片，我们可以分别计算其与苹果公司图片簇的相似度和自然苹果图片簇的相似度，从而得出这张苹果图片到底属于哪一个簇。

局部视角

通过对图结构的计算，图可以提供超越单个节点属性描述的信息。具体来讲，对于节点，我们能获得的信息有限。但是通过计算该节点周围的节点和边的信息，我们可以获得更多的信息。

以上图为例，对于单个像素，我们并不知道该像素的意义。但是通过观察该像素周围的像素，我们可以知道该像素来自猫的眼睛。

数据挖掘工具箱(The Graph Mining Toolbox)

此段介绍了Google 数据挖掘团队(Graph Mining Team)开发并使用的工具箱。后文会提及，故略去。

应用案例

垃圾邮件、诈骗和滥用行为检测

对于检测垃圾信息、欺诈和滥用行为中的应用，特别是在信任与安全问题的处理上，Google团队介绍了两种核心思想和方法——基于密度聚类的异常检测和标签传播：

1. 异常检测通过密度聚类：

   统计学上不太可能的密集群集与恶意行为高度相关。这意味着，如果我们在数据的图表示中发现异常密集的节点群集，这些群集很可能表示垃圾信息发送者、欺诈行为或其他类型的滥用行为。通过使用图挖掘工具，可以识别这些不寻常的密集群集，从而检测和防止恶意行为。这对于保持产品如YouTube和广告平台的安全和信任至关重要。

2. 标签传播：

   从已知的恶意行为者（bad actors）开始，利用图的结构识别可能同样存在问题的邻近节点。这种方法的思路是，恶意用户或实体往往在图中彼此靠近或以某种方式相互连接，例如，他们可能共同参与欺诈活动或垃圾信息传播。通过将标签（如“恶意”）从已知的恶意行为者传播到他们的连接节点，可以识别出更多的可疑行为者。这种方法有助于有效地扩大检测范围，发现其他可能未直接被识别为恶意的实体。

提升机器学习模型

1. 关系发现：

   社交网络如何找到“可能认识的人”是通过分析社交图谱实现的。利用图信息可以发现那些不明显的连接，即使这些连接在直接的社交互动中可能不明显，通过图分析，我们可以揭示潜在的联系，比如共同的朋友、兴趣相投或相似的社交路径等。

2. 特征提取：

   
   

   图产生的信号，如群集、个人化页面排名（PPR）向量和图嵌入，对于训练上游的机器学习模型非常有用。这些从图数据中提取的特征可以显著改善机器学习模型的性能，通过提供有关实体间关系的深入信息。在多模态模型中，图数据可以作为另一种模态，与其他数据类型（如文本、图像和声音）一起构成一个更大的整体。这种方法可以使机器学习模型利用更丰富的数据集，从而获得更全面的理解和更准确的预测。

3. 案例应用：

   
   

   以Google Images的“视觉相似图像”功能为例，通过分析图像间的相似性，可以创建一个图，在这个图中，节点代表图像，边代表图像之间的视觉相似度。即使用户没有明确指定搜索条件，也能找到与给定图像视觉上相似的其他图像。

高效计算

1. 资源效率：通信开销

   
   

   在分布式计算系统中，大型数据集需要分割并分布到不同的计算节点上处理，这个过程中产生的通信开销可以通过图分割算法来减少。如在Google Driving Directions（谷歌驾车导航）中应用图分割，可以优化后端处理效率，使道路网络数据处理更加高效。

2. 数据效率和主动学习

   
   

   我们可以利用图来回答像“我的数据集中哪些点最具多样性”这样的查询，这可以驱动主动学习循环。主动学习是一种策略，允许模型请求特定数据点的标注，以最有效地学习和提高性能，尤其适用于标注数据稀缺的情况。基于图的半监督学习适用于数据量少的模型，可以利用少量标注数据和大量未标注数据，通过图的结构来提升学习效果。

Application Stories

利用时空图神经网络为新冠传播建模

基础

深度机器学习模型被描述为学习一个函数$f(x)$，其中$x$是一组精心挑选的特征。模型中的中间状态，也就是嵌入（embeddings），捕捉了在高维空间中特征之间的复杂相互作用。模型通过调整嵌入来最小化损失函数，以此来学习数据中的复杂模式和关系。

深度学习模型能够自动学习和抽象输入数据与输出目标之间的复杂关系，即使这些关系在开始时并不明显或直接。深度机器学习模型之所以强大，是因为它们能够接受任意的输入并学习到所需输出的映射。

深度学习在流行病学中的应用

SIR模型将人群分为三个类别：易感者（Susceptible）、感染者（Infected）和康复者（Recovered），并尝试定义这些类别之间的转换关系。在过去，类别的识别和转换的准确识别是非常困难的任务。

深度学习技术在处理这种复杂的疾病动态和多维数据方面显示出其能力，这些数据是传统的隔间模型（compartmental models）和统计模型难以捕捉的。深度学习能够分析和理解疾病传播的复杂模式，提供比传统方法更精细和动态的疾病传播分析。

COVID建模

流行病学建模依赖于时间和空间，明天的病例数量取决于昨天的病例数量和今天邻居的病例数量，因此这是一个多模态问题。而且，这还是一个图问题。

该团队使用分层图进行建模。

在上面这张图中，每个节点代表一个特定的时间和地点，节点自身的特征为病例数量和内部移动数据。

图被建模为150个层，每层代表一个时间点。在每个层内部的边表示空间属性，这些边的权重表示的是移动距离；而层之间的边表示时间属性，其权重是基于边所连接的节点之间经过的时间（时间越长，权重越低，即反比例关系）。

这样的设计允许模型捕捉到时间上的动态变化（通过时间边）和空间上的联系（通过空间边），从而更好地理解和预测COVID-19的传播模式。

从这个样例中，我们可以看到：图数据的一个主要优势是能够将上下文信息纳入分析中，当分析一个节点时，可以考虑其周围邻接节点作为信息源。

GCNs正是利用了这一点，它通过学习节点及其邻域间的复杂关系，提高了分析和预测的精度和效率。这种方法使得模型不仅仅考虑单个节点的属性，还考虑了节点在图中的位置和周围节点的影响。

隐私计算

在分析用户数据时，隐私是一个基本的关切点，而图数据（如社交网络图、交易图等）也不例外。它提出了两个与图数据隐私相关的应用场景：

1. 利用图挖掘（图聚类）来提升用户隐私： 是否可以通过图挖掘技术，特别是图聚类，来增强用户隐私。其重点是，我们能否利用这些技术来识别和保护用户数据的敏感部分，从而提高隐私保护水平。

2. 保护社交网络应用中的用户隐私： 在社交网络应用中如何保护用户隐私。社交网络图通常包含大量关于个人关系和交互的敏感信息。其重点是，我们如何设计和实施机制来保护这些数据，避免未经授权的访问或滥用，同时允许合法和有益的数据分析和社交互动。

这两个场景反映了图数据隐私保护的双重挑战：一方面需要利用图数据的结构和特性来增强用户隐私保护，另一方面需要确保这些数据不被滥用，保护用户免受隐私侵犯。

隐私计算方面，Google的一项努力是FLoC——群组联合学习（Federated Learning of Cohorts）。

FLoC

FLoC——群组联合学习（Federated Learning of Cohorts）是一种隐私保护的网络广告技术，是Chrome隐私沙盒（Privacy Sandbox）计划的一部分，旨在逐步淘汰第三方cookie的使用。

其基本原理是以用户的浏览历史数据作为输入，通过由许多用户共享的、匿名的cookie替换可识别的第三方cookie，创建了包含至少k个具有相似浏览兴趣用户的FLoC（群组）。通过这种方式，广告商可以针对具有类似兴趣的群组，而不是基于个人用户的具体行为数据进行广告投放。这减少了对个人隐私的侵犯，同时仍然允许广告的个性化定向。

在此项目中，一个重要的问题是如何确认聚类的大小。换言之，在聚类过程中需要确保每个群集达到一个最小的规模，因为在较大的群集中个体更难被单独识别。

经过实验，作者团队表明，Affinity在保持较高的余弦相似度同时，也能确保较高的匿名性。

On-Device Public-Private Graph Model

On-Device Public-Private Graph Model是一种用于推荐系统数据处理和分析模型。其设计意图旨在不泄露用户私人信息的前提下，在用户的个人设备上进行复杂的计算。其关注点在于结合公共数据和私有数据进行运算。

要实现该模型，一个需要回答的问题是"我们能否在不丧失任何隐私的情况下，将所有私人数据和联系人信息保留在用户的设备上，并解决重要的机器学习问题？"。

Google团队给出的方法如下图所示。

用户可以自愿选择哪部分作为私有数据保存在本地，非私有数据则会被上传到云端，构成公有数据供服务器使用。

如上图所示，其工作流程由两个步骤构成：

1. 云端的公有数据发送摘要至个人用户。
2. 个人用户之间可以交换公有数据。

聚类与因果推理

因果推断是统计学的一个分支，试图建立因果之间的联系，其理论在临床试验中有大量应用，如随机试验——临床试验、A/B测试等。

然而，随机试验可能会遇到干扰问题，即一个对象的处理可能影响另一个对象。例如，在教育研究中，如果对一组学生实施了某种教学方法，这种方法不仅可能影响这些学生，还可能影响到他们的老师、同学以及学校的整体教学环境，从而对研究结果造成干扰。

为了尽可能接近“全治疗”和“全对照”的情况，随机试验将对象按簇分配给治疗组或对照组。这是因为，仍以上例为例：如果一个研究想要评估某种教育干预措施的效果，而这种干预措施可能会影响整个班级的学习氛围，那么研究者可能会选择整个班级而不是单个学生作为随机化的单位。这样，一个班级中的所有学生要么都接受干预措施，要么都不接受，这有助于确保干预措施的影响是在班级层面上被评估，从而减少了个体间干扰的问题。

正如上图所示，如果我们将个体作为实验对象，那么实验对象之间会互相影响，其相互影响的数量达10+之多。为了解决此问题，我们以簇作为实验对象。如右图所示，在该样例中，其相互影响的数量仅为4。