携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第31天，epubs.siam.org/doi/10.1137…

会议：Proceedings of the 2018 SIAM International Conference on Data Mining (SDM CCF-B)

年度：2018

Abstract

在本文中，我们提出了一种新的框架，称为半监督嵌入在带异常值的属性网络(SEANO)，以学习一种低维向量表示，系统地捕获部分标记属性网络(PLAN)中顶点的拓扑邻近性、属性亲和性和标签相似性

我们的方法被设计为在感应和感应设置下工作，同时明确地减轻来自异常值的噪声影响。

• 在web、文本和图像领域的各种数据集上的实验结果表明，SEANO在转导和归纳设置下的半监督分类方法优于最先进的方法

• 我们还表明，SEANO中的一个参数子集可以被解释为离群值，并且在应用于检测网络离群值时，可以显著优于基线方法

最后，我们介绍了seanoa在具有挑战性的现实环境中的使用——卫星图像的洪水制图，并表明它能够在这项任务中胜过现代遥感算法

1 Introduction

许多应用程序被建模和分析为具有属性的网络，其中

• 顶点表示具有属性的实体
• 边表示实体之间的交互或关系

在许多情况下，我们还可以了解一个带属性网络中一些顶点的标签

这样的网络称为部分标记的属性网络(PLAN)

虽然PLAN包含比普通网络更丰富的信息，但它们也更具有分析的挑战性

鉴于网络嵌入[33,26,8]在纯网络中用于顶点分类[37]和网络可视化[33]等图挖掘任务的巨大成功，研究人员将类似的思想应用于归属网络[12,36,25,14]

然而，在PLAN中嵌入节点有三个关键挑战

1. 如何通过整合PLAN中的异构信息，包括图结构、顶点属性和部分可用标签，来学习网络嵌入?
2. 如何进行归纳嵌入学习，以便在训练阶段为未观察到的顶点生成嵌入?
3. 如何处理PLAN中的异常值，并在嘈杂的环境中学习更稳健的嵌入?

一些工作集中在第一个挑战上——以转导的方式(假设所有顶点在训练期间都是可访问的)捕获拓扑结构、顶点属性和标签信息，用于嵌入学习[25,12,36,14,9]，尽管其中一些不能轻易适应半监督学习设置[12,9]

PLAN中归纳设置的解决方案，支持为看不见的节点生成嵌入，最近才被研究[36,9]

据我们所知，没有以前的工作明确说明了在网络嵌入中异常值的影响

在本文中，我们提出了一种新的方法来同时克服这三个挑战。

具体地，我们设计了一个双输入双输出的深度神经网络来归纳学习顶点嵌入

• 输入层分别依赖于顶点及其邻域的属性，
• 而输出层提供标签和上下文预测

这两个不同的输出层分别构成了我们的模型的监督和非监督组件

通过交替训练PLAN上的两个组件，我们了解到一个统一的嵌入包含了与结构、属性和标签相关的信息

我们还表明，我们的方法可以生成在训练期间不可见的新顶点的高质量嵌入，因此在本质上支持归纳学习

此外，我们的模型明确地说明了在训练过程中的异常点的概念，并能够有效地减轻异常顶点对学习的嵌入的潜在不利影响

我们还揭示了所提出的模型的一个很好的特性，即特定的一组参数可以解释为PLAN中顶点的异常值分数

我们将我们的方法称为带离群值的带属性网络的半监督嵌入(SEANO)

• 我们通过半监督分类对SEANO产生的嵌入质量进行了实证评估，并表明SEANO在转导和归纳设置方面都显著优于最先进的方法
• 此外，我们基于SEANO的输出离群值进行离群值检测，并展示了其相对于网络离群值检测基线方法的优势
• 最后通过洪水制图的实例研究，直观地展示了seano在洪水制图中的应用效果

2 Related Work

Network Embedding

近年来，网络嵌入策略越来越重要

早期的想法包括IsoMap[34]和局部线性嵌入(LLE)[28]，它们利用向量数据的流形结构来计算低维嵌入

最近，由于自然产生的网络数据的出现，其他的网络嵌入方法也被提出[33,26,8]

除了学习同构网络的嵌入，一些研究人员还提出了嵌入属性网络的想法[35,12,11,25,36,14,9]

虽然它们将属性和/或标签信息合并到嵌入中，但大多数是固有的转导，不能生成在训练中看不到的顶点的嵌入

两个例外是用于归纳学习的Planetoid[36]和GraphSAGE[9]

• 然而，Planetoid[36]是专门用于半监督分类的，作为副产品的输出网络嵌入并不捕获所有的信息(从它们的模型体系结构可以看出)。因此，它的嵌入可能不能推广到其他应用程序，如可视化和集群
• 另一方面，GraphSAGE[9]只适用于无监督学习或完全监督学习设置，不能直接用于半监督方式

最后，现有的关于网络嵌入的研究都没有明确说明异常值的影响

我们在表1中总结了所提议的SEANO模型与这些最近的一些努力之间的差异。

Outlier Detection

虽然在不同背景下的离群点检测已经有了大量的工作，但网络数据中的离群点检测直到近年来才被研究

该领域以往的方法多集中在通过图的拓扑特征来检测异常模式，如子图频率[23]、群落结构[5]等

这一领域最近的研究通过合并顶点属性来研究属性网络[27,20,16]

最近只有几个研究尝试使用网络嵌入来发现网络离群值[6,10]

然而，这些努力并不适用于有归属的网络

我们的工作与我们即将讨论的这些工作有些不相关

3 Methodology

3.1 Problem Formulation

我们首先定义了一个部分标记属性网络(PLAN)，并制定了我们的框架，在带有异常值的属性网络(SEANO)上实现半监督嵌入。

定义1.部分标记的属性网络

部分标号属性网络是一个无向图$G=(V，E，X，Y)$，其中：

• $V=\{1，2，\dots ，n\}$是顶点的集合
• E是边的集合
• $X=(x_1，x_2，\dots ，x_n)$是属性信息矩阵；
• $Y=(y_1，y_2，\dots ，y_n)$是V中的顶点的标号，其中大部分是未知的

根据顶点的标签是否已知，我们将顶点分为有标签的顶点$V_L$和未标记的顶点$V_U$

我们还考虑了网络离群点的潜在负面影响

根据其他文献[20]的定义，我们将计划中的网络离群点定义为其属性显著偏离由图结构和顶点标签局部化的上下文的底层属性分布的顶点

平面中的离群值的一个例子是，一个顶点的属性与具有相同标签的密集连接组件中的其他顶点的属性非常不同。

利用计划和网络离群点的概念，我们将嵌入学习问题定义如下

定义2.具有离群点的属性网络中的半监督嵌入

给出一个带有一小部分未知网络离群点的部分标记属性网络$G=(V，E，X，Y)$

我们的目标是为每个顶点i学习一个健壮的低维向量表示$e_i\in R^r$，其中

• $r<<n$
• $e_I$可以联合捕获规划中的属性信息、图结构信息和部分标签信息

3.2 The Proposed Model

我们提出Seano来解决上述问题

Seano的体系结构(如图1所示)由一个具有两个输入层和两个输出层的深层模型组成

通过一系列的非线性映射函数将输入和输出连接起来，将特征转化为一个非线性的潜在空间

如图1所示，两个输入层是顶点$x_i$的属性和其邻域${\overline{x}}_{N_i}$的平均属性

它们经过相同的一组非线性映射函数(L1层)，并通过加权和在嵌入层中聚集

两个输出层铰接在嵌入层上

• 图1中左侧的输出层预测输入顶点的类标签$y_i$
• 而右侧的输出层生成网络输入的上下文

3.2.1 Architecture and Rationale

我们将深模型的第k层表示为HK(Xi)=φ(wkhk−1(Xi)+bk)，其中wk和bk是第k层中的权重和偏差，φ(·)是非线性激活函数。则可以将嵌入层表示为

其中，λi∈[0，1]是与每个顶点i相关联的参数(称为聚集权重)，并且通过模型训练3来学习。我们现在说明如何使用拟议的模型来解决以下三个挑战。

半监督嵌入学习：左输出层作为模型的监督学习部分，因为它预测类别标签，而我们使用标签数据来训练它。右侧输出层预测网络输入的上下文，该上下文来自上下文生成算法，例如随机游走26。因此，该部分被认为是模型中捕捉拓扑结构信息的非监督部分。这两个部分紧密地相互连接，因为它们共享从输入层到嵌入层的第一个L1+1层。此外，属性信息自然被集成到嵌入中，因为它是模型的输入。作为一个整体，Seano通过使用标记数据和未标记数据以半监督学习的方式进行训练，而嵌入层作为输入层和输出层之间的桥梁，必然会融合计划中的所有异质信息。

修正嵌入学习中的离群点：请注意，Seano的输入层包括来自目标节点及其邻域的属性信息。这两个输入源在嵌入层通过基于聚合权重λi的加权和来融合，如公式3.1所示。通过将邻域合并到输入中，SEANO不仅收集用于嵌入学习的额外信息，更重要的是，还平滑了每个单独顶点i产生的噪声。直观地说，如果一个顶点与类似上下文中的其他顶点相比包含异常属性，Seano将天生更依赖于邻域属性，以便提供更好的预测结果。

从而引导模型通过训练学习到更小的权值λi。因此，我们可以通过引入邻域信息和自适应学习聚合权值来缓解网络异常值的负面影响。事实上，正如我们将在第3.2.4节中展示的，学习到的权重λi可以很好地解释为每个顶点i的异常值得分，并进一步用于异常值检测。

归纳嵌入学习:我们指出seano可以很容易地通过观察一个新顶点的属性和邻域来推断它的嵌入。这种推广是可能的，因为顶点i的嵌入ei是用ei = λihl1 (xi)+(1−λi)hl1 (xNi)计算的，它只依赖于xi、xNi和λi。当新顶点i到达时，xi和xNi可以很容易地得到。对于λi，我们可以将其设为一个常数，这取决于新顶点的正规性的先验知识。在本文中，我们对未观察顶点取一个保守的估计并设置λi = 0.5，我们经验地发现这是可行的。这样，我们的模型就可以应用于通过融合异构信息来归纳推断不可见节点的嵌入。

3.2.2 Loss Functions

根据上述定义，softmax层la- bel预测的输入值可表示为hl2 (λihl1 (xi) +(1−λi)hl1 (xNi))，为简便起见，记为hl2⊕l1 (xi, xNi)。同理，softmax层用于上下文预测的输入为hl3⊕l1 (xi, xNi) = hl3 (λihl1 (xi) +(1−λi)hl1 (xNi))

图1左侧所示的深度模型的监督学习组件是规范的多层感知器(MLP)。其损失函数为:

其中p(yi|xi, xNi)是目标标签的可能性，被正式定义为

这里，Y表示可能的标签集合。如图1所示，W(s)是模型监督学习部分中使用的softmax层的权值矩阵

seanoi的无监督学习组件类似于Word2Vec[22]和DeepWalk[26]中使用的方法。我们采用Skip-gram模型[22]来捕捉目标顶点(输入时)和上下文顶点(输出时)之间的关系。对于属性xi的PLAN中的每个节点i，我们生成它的上下文Ci = {vi,1, vi,2，…第六,c}。然后构造损失函数为:

其中p(v ‘ |xi, xNi)是给定顶点及其邻域属性的目标上下文的可能性:

这里W(u)是模型中无监督部分使用的softmax层的权值矩阵。注意，这个公式不同于DeepWalk[26]中的公式，因为预测可能性p(v ‘ |xi, xNi)取决于属性xi和xNi，而不是顶点id。

我们现在讨论如何为每个顶点i生成上下文Ci。我们将一个顶点的上下文分类为网络上下文和标签上下文，扩展了[36]中提出的思想。一个顶点的网络上下文由网络中靠近该顶点的顶点组成，可以通过在网络[26]中截断随机游走生成。顶点i的标签上下文定义为具有相同标签的顶点，可以通过对标签为yi的顶点进行均匀抽样来生成这些顶点。

对于每个顶点i，我们按照算法1所示的步骤生成总共c个上下文顶点。具体来说，对于一个有标签的顶点，我们从短随机游动流中生成c * 3 α标签上下文顶点(行2-3)和c *(1−α)网络上下文顶点(行4)。对于一个没有标签的顶点，我们提取c网络上下文顶点(行6)。为了生成网络上下文，我们基本上遵循与Deepwalk[26]相同的方法。

3.2.3 Model Training

在这一部分，我们讨论了如何共同最小化监督损失Ls和非监督损失Lu。我们首先描述模型中每个部分(有监督和无监督)的优化过程。如前所述，图1左侧的监督单元是标准MLP。我们可以很容易地使用反向传播和梯度下降来训练模型[29]。

对于公式3.4中描述的具有损失函数的无监督分量，由于需要用公式3.5遍历V中的所有顶点来计算∇(log p(V’|xi, xNi)，在大数据集上的效率非常低，因此训练成本可能会相当高。为了解决这一问题，我们采用负采样策略[22]。我们不直接使用公式3.5并查看所有的顶点，而是用Word2Vec[22]中提出的负采样目标来替换它。将其应用于3.4式，得到损失函数for

式中，σ为Sigmoid函数，Vv ‘，neg为负集，随机选取t个负样本。

为了共同减少模型中的监督损失和非监督损失，我们使用了迷你批量随机梯度下降法，并交替更新模型中两个部分的参数。如算法2所示，我们联合训练这两个部分，在监督部分(4-5行)和无监督部分(7-16行)的批大小分别为b1和B2。需要注意的是，这两个分量之间是紧密连接的，因为它们共享神经网络中的第一l1 + 1层(见图1)。因此，监督分量和非监督分量都会更新共享层中的参数。此外，为了将λi限制在[0,1]范围内，我们设置λi = σ(ωi)，并对ωi进行优化。训练模型后，每个节点的嵌入由嵌入层的激活值组成，计算公式为3.1。

3.2.4 Outlier Detection Using SEANO

如图1所示，SEANO从顶点属性xi及其邻域属性xNi获取输入。这两者在经过一系列隐藏层后融合到嵌入层。两个信息源的融合依赖于聚合权值λi，聚合权值是通过模型训练阶段学习到的。在顶点异常的情况下(其属性与同一上下文中的其他顶点非常不同)，SEANO将学会减少来自顶点属性xi的输入，并更多地依赖于邻域属性xNi来执行预测，这是由潜在的损失函数的减少所驱动的。该设计可以消除单个顶点的噪声，自适应提高嵌入的鲁棒性。更重要的是，我们指出权值参数λi可以解释为PLAN中每个顶点i的异常值得分。训练我们的模型后，PLAN中的每个顶点i都有一个权值参数λi，它总是在[0,1]范围内。λi较低的值表明，与大多数顶点相比，顶点i的属性在预测类标签和图上下文方面没有信息。

这是一个强烈的信号，表明它的属性、标签和图结构不符合PLAN中的底层模式。根据这一思想，我们将λ理解为顶点i的异常值。异常值越低，该顶点越有可能是异常值

4 Experiments and Analyses

Datasets

Baseline Methods

4.1 Transductive Learning

在本实验中，我们以转导的方式(测试训练中可访问的数据)在PLAN中进行网络嵌入，并在节点分类任务上评估不同的嵌入方法。我们在前四个数据集以及它们的噪声版本上进行了这个实验。表4报告了所有比较方法在这些数据集上的分类精度。我们强调以下主要意见:

1)顶点属性、图结构、标签信息都有助于提高嵌入质量。随着我们加入更多的信息用于嵌入学习(表4中从上到下)，我们倾向于获得更好的嵌入，这从分类性能的提高可以看出。如果我们将前两组的方法与后两组的方法进行比较，我们可以清楚地观察到显著的性能差距。注意前两组和后两组之间的主要区别是，前者只使用一种或两种类型的信息进行嵌入学习，而后者利用了所有三种类型的信息(顶点属性、图结构和部分可用标签)。这种观察结果在Cora数据集中更为明显，其中SEANO、GCN Node2Vec+ Node2Vec、SVM。

2)为了实现高质量嵌入，需要对异构信息进行系统融合。简单的策略，比如用属性连接网络嵌入，并不总是有效。这可以通过比较Node2Vec+与简单SVM的性能来观察。Node2Vec+与SVM的不同之处在于，它通过连接顶点嵌入来扩展原始顶点属性。然而，我们观察到Node2Vec+在Citeseer、Pubmed和Houston数据集上的表现不如SVM。Node2Vec+相对于Planetoid-T、GCN等更高级的方法性能较差，说明网络结构只有在有原则的纳入时才有助于提高嵌入质量。这证实了联合学习PLAN嵌入的必要性。

3. SEANO生成质量最好的嵌入，并始终优于其他方法的顶点分类。特别是，它始终优于最先进的方法，包括Planetoid-T, CNN-Cheby和GCN。我们认为，性能提升的一个主要原因是，eseano能够纠正嵌入学习阶段网络异常值的不利影响。一个证据是SEANO的性能比它的变体SEANO-0.5和SEANO-1.0更好，这两个变体使用完全相同的神经网络架构，只是固定了聚合权值λi。这表明，基于顶点离群性的自适应聚集权(SEANO)比忽略邻域属性(SEANO-1.0)或均匀合并顶点属性和邻域属性输入信号(SEANO-0.5)的方法具有明显的优势。我们还应该强调，seanoo在应用于有噪声的数据集时，性能下降最小，尤其是与竞争性技术人员(GCN, seanoo -0.5, seanoo -1.0)相比。

4.2 Inductive Embedding Learning

正如我们在第3.2节中讨论的，SEANO也被设计来支持归纳嵌入学习。在这个实验中，我们表明SEANO能够推断出在模型训练期间未观察到的顶点的质量嵌入。归纳学习通常更具挑战性，之前的一些基线不能应用于此设置。为了进行比较，我们采用了Planetoid (Planetoid- i)[36]的归纳变体和最先进的方法GraphSAGE[9]。为了方便参考，我们仍然使用SVM作为基线，但与之前的实验完全相同。为了归纳学习的目的，具有1000个顶点的测试数据集在训练阶段被保留并且不能被访问。其余的实验设置与转导式学习实验类似。表5显示了SEANO与其他方法相比在归纳学习中的表现。

如表5所示，SEANO的性能明显优于其他方法。最大的差距在于Cora和Citeseer数据集，在那里我们分别观察到比第二最佳基线的准确性提高了19%和8%。通过比较表5和表4中seano的性能，我们可以看到seano在归纳学习上的表现几乎相同，只是精度略有下降。这个实验的结果表明，即使没有观察到测试数据集，SEANO仍然能够相当好地学习嵌入，显著优于最先进的技术。

4.3 Outlier Detection using SEANO

除了学习健壮的嵌入计划，这里我们表明seano也有能力通过解释聚集权λi作为异常值得分检测网络异常值。

我们将SEANO标记注入的网络异常点[31]的性能与以下基线进行比较:1)仅属性方法(attro .-only)，它在顶点属性上运行隔离森林[19]来检测异常点。2) Planetoid-T、GCN和SEANO-embed，分别对Planetoid-T、GCN和SEANO-embed生成的网络嵌入采用隔离森林算法。请注意，这些方法生成最佳质量的嵌入，如转导学习实验所示。4) AMEN[27]和ALAD[20]是最先进的属性网络离群点检测算法。我们在上述使用的噪声数据集上运行所有方法，其中5%的异常值是使用自然扰动方案[31]注入的。我们将待检测的异常点数量设为注入的异常点数量，并计算精度。表6展示了不同方法对异常点检测的性能。

我们清楚地看到，SEANO在这个具有挑战性的任务中表现得相当好，其性能可与专门为检测具有属性的网络异常值而设计的最先进的方法相媲美。通过利用模型中的聚集权重，SEANO在Cora∗和Pubmed∗上的性能明显优于最佳基线ALAD(用于属性网络异常值检测)，而在Citeseer∗上的性能略差。考虑到SEANO一开始就不是为网络异常点检测而设计的，这是一个令人印象深刻的性能。SEANO还主导了其他基于嵌入的稻草人(GCN, Planetoid-T,SEANO-embed)，其中许多在这个任务上表现很差。我们猜测，这是因为嵌入将所有信息整合到一个连贯的向量表示中，无法将属性信息(作为离群指标特征)与标签信息和图信息(上下文特征)区分开来[20,18]。

4.4 Case Study: Flood Mapping

现实世界的问题(洪水制图)。为此，我们使用了2016年休斯顿洪水发生后，利用合成孔径雷达立即收集的休斯顿高分辨率卫星图像。有两个来自雷达的原始属性(HH和HV)和另一个代表每个像素的地理海拔。我们检查了SEANO在一个具有挑战性的图像上的可扩展性和有效性。HH和HV测量被物质反射的波的极性，有助于区分水和陆地。目标是进行半监督学习来区分水和土地。我们按照Cour等人[3]提出的方法将图像转换为无向图。图像的每个像素被视为一个顶点，并且在1.5个单位的欧几里得距离内与邻近像素有边。每个顶点的三个属性(HH, HV, elevation)被用作顶点属性。由此产生的PLAN，被称为休斯敦-大，包括3,926,150个顶点和15,692,353条边(在之前的实验中使用了一个被称为休斯敦的低分辨率版本)。地面真实标签(水或土地)由领域专家提供，我们从中抽取100个实例作为标记数据进行训练。

我们在休斯敦上运行了不同的方法——在类似于转导学习实验的设置下(结果见表7)。这里我们包括了来自遥感和计算机视觉社区的专门用于洪水制图和图像分割的基线，以及我们之前分析的前三种算法(SEANO、Planetoid-T和SVM)。Hugfm是一种最先进的卫星图像半监督划定水域的算法(由领域专家监督)[17]。Norm-thr[21]是在遥感领域发展起来的一种基于分裂的现代水体圈定自动阈值方法。Otsu[24]是一种基于聚类的阈值分割方法，广泛应用于计算机视觉和遥感领域。分水岭[2]算法是一种基于标记物的区域生长技术。从表7可以清楚地看出，SEANO在划分洪水泛滥地区方面的表现明显优于基线。同样值得注意的是，许多具有竞争力的基线(如SVM、Planetoid)在低分辨率的休斯顿数据上工作得相当好，但在这种情况下却不那么有效(与表4相比)。最后，我们注意到，在大型城市环境中，即使在统计上有微小(1%)显著提高F1分数，也可以节省大量资金(数十亿美元)，并改善灾后紧急救援工作的优先级[21,17]。

在图2中，我们还将原始数据和SEANO输出的结果可视化。对比图2b的水体划界结果和图2a的原始卫星图像，我们可以观察到SEANO准确地划界了不同形状的水域(如细长的河流)。此外，根据SEANO输出的异常点评分，图2a中的白色圆圈是异常点最多的点。视觉上，与周围的像素相比，大多数异常值都非常明亮和耀眼。为了找出现实中那些异常值是什么，我们将它们与谷歌Maps进行交叉引用。图2c显示了谷歌Maps中与4个代表性异常值相关的区域。图2c的第一行显示了水体中的集装箱和船舶(对应于图2a中的A和B)，而第二行显示了工厂中常见的大型白色圆柱形水箱(通常装有处理过的水)(图2a中的C和D)。我们研究了前80个异常值，发现它们中的大多数都属于这些情况。一个共同的因素是它们包含强反射的金属表面，导致它们与相邻像素相比具有更高的HH和HV值。总而言之，这个案例研究表明，SEANO对于存在异常效应的现实问题是高效的(可以扩展到大问题)和有效的(与最先进的相比)。

5 Conclusions

我们提出了一个半监督归纳学习框架来学习鲁棒嵌入，共同保持图接近性，属性亲和力和标签信息，同时考虑异常值效应（ outlier effects ）

我们将所提出的模型扩展用于检测网络异常点

我们对真实世界数据的实验和洪水制图的案例研究证明了我们的方法在当前技术水平上的有效性

作为未来的工作，我们计划将SEANOto应用于其他类型的网络，如属性超网络和异构信息网络

读后总结

2022/08/11 第一次阅读

本文为略读，只读了个大概

文章是针对带有部分标签的属性网络的嵌入

整个结构如下

含有两个输入和输出

• 一个输入是节点$i$的属性信息$x_i$，另一个输入则是节点$i$邻域节点属性信息的均值
• 通过权值控制二者的比例通过神经网络进行嵌入，得到$e_i$
• 然后再利用嵌入$e_i$得到预测此节点的标签以及其上下文
• 构建损失函数，以此为目标优化，得到最终的稳定嵌入

感觉还是有点启发的，思路还是可以的，如果觉得有启发，之后再研读一遍！

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正