携手创造，共同成长！这是我参加「日新方案 8 月更文挑战」的第32天，点击查看活动概况

前言

Hello！ 十分感谢您阅览海轰的文章，倘若文中有过错的地方，欢迎您指出～ 自我介绍 ଘ(੭ᵕ)੭ 昵称：海轰 标签：程序猿｜C++选手｜学生 简介：因C言语结识编程，随后转入核算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。 学习经验：厚实基础 + 多做笔记 + 多敲代码 + 多考虑 + 学好英语！ 唯有努力

知其然 知其所以然！

本文仅记载自己感兴趣的内容

简介

原文链接：It’s Who You Know: Graph Mining Using Recursive Structural Features

会议：Acm Sigkdd International Conference on Knowledge Discovery & Data Mining （CCF-A）

年度：2012

ABSTRACT

给出一个图，咱们怎么为节点提取好的特征呢？

例如

• 假定两个来自同一范畴的大图，咱们怎么运用其间一个图中的信息来进行另一个图的分类(即，对图进行跨网络分类或搬迁学习)？
• 此外，假如其间一个图是匿名的，咱们怎么运用其间一个图中的信息来撤销另一个图的匿名化？

在一切这类图发掘使命中，要害的一步是找到有用的节点特征

咱们提出了一种递归特征提取算法ReFeX，该算法递归地结合部分特征(依据节点)和邻域特征(依据网络)，并输出区域特征–捕捉“行为”信息

咱们演示了怎么在网络内和跨网络的分类和去匿名化使命中运用这些强壮的区域功用，而不依赖同源性或类别标签的可用性

咱们的作业奉献如下：

• (A)refex是可扩展的
• (B)它是有用的，可以在大图中捕获区域(“行为”)信息

咱们报导了在超越1M条边的不同域的实在图上的试验，其间REFEX在网络分类和去匿名化等典型的图发掘使命上优于竞争对手

1. INTRODUCTION

为给定图的结点提取有用特征是许多数据发掘使命的要害进程，如孤立点检测(即具有奇怪特征组合的结点)，或在同一范畴的不同图之间进行发掘

例如，给定来自不同日期或不同企业网络的IP通讯图，咱们是否可以在某一天(比方说星期一)练习一个分类器，并在另一天(比方说周四)运用相同的分类器来精确猜想流量，而不在后者的图上加任何标签？

这儿的要害进程是从每个节点中提取有用的、可传递的特征，以最好地捕捉节点特征，以便对节点(或边)进行区别和分类

下面是另一个比方：给出一个匿名的交际网络(比方Twitter的Who-FollowsWho图)和一个非匿名化的通讯图(比方Twitter的Who-提及-Who图)，咱们能找到有助于去匿名化(或从头辨认)交际网络中的人的节点特征吗？

---

在这儿，咱们提出了一种新的解决方案，REFEX(递归特征提取)来解决这些图发掘使命

REFEX递归地组合本地(依据节点)特征和邻域(依据egonet)特征，并输出捕捉“行为”信息的区域特征

local (node-based) features with neighborhood (egonet-based) features

这些区域特征标明给定节点所衔接的节点的类型(例如，衔接到有钱人)，而不是那些节点的身份(例如，衔接到比尔盖茨)-即，在不同图表的发掘中，您在类型等级上知道的人是重要的

在实证研讨中，咱们演示了怎么在内部和跨网络分类和去匿名化使命中运用这些强壮的区域特征–而不依赖同源性或类别标签的可用性

---

因而，该问题的界说如下：

给定一个图G，核算具有以下特点的节点特征矩阵$F$：

• 结构：$F$的结构不应该需求关于节点或链接的附加特点信息。
• 有用：杰出的节点特征应
  • (1)协助咱们猜想节点特点，当这些特点可用时(如咱们接下来评论的IP流量的状况)
  • (2)可跨图传输(例如，当图随时刻变化时)

抱负的功用应该有助于数据发掘使命

典型的使命包含节点分类(在给咱们一些标签之后)，图中节点的去匿名化，以及搬运学习

---

图1供给了(a)ReFeX背面的直觉和(b)其分类精确性的预览

• 在(a)中，咱们展现了IP网络中不同日期的节点的网络，其间节点巨细和边巨细与流量成正比。首要的观点是街坊的特征是有价值的，而且协助咱们描绘中心节点的特征(关于每一列，手动别离符号为‘web’、‘dnsserver’和‘p2p’)
• 图1(b)显现了REFEX(以蓝色条标明)与竞争对手的分类精度-越高越好；REFEX一向胜出

---

咱们的作业奉献如下：

• 新颖的规划：咱们提出了REFEX，这是一种可伸缩的算法，它核算区域特征，捕捉大图上的“行为”信息
• 有用性：REFEX的区域功用在几个图发掘使命中体现杰出，如搬迁学习(跨网络分类)和大型图上的节点去匿名化

2. PROPOSED ALGORITHM

咱们的算法Refex聚合了节点的现有特征值，并运用它们来生成新的递归特征

用于耕种递归特征生成的初始特搜集可以是来自网络的结构信息或来自外部源的特点

在这儿，咱们重视的是只有结构信息可用的使命

咱们将结构特点分为三种类型：

• local
• eGonet
• recursive

部分特征和部分特征一起称为邻域特征，一切这三个特征一起称为区域特征

We separate structural attributes into three types: local,egonet, and recursive features. Local and egonet features together are called neighborhood features, and all three together are calledregional features.

2.1 Neighborhood Features

为递归REFEX进程供给种子的根本特征是本地local和eGonet特征

关于给定的节点，可以快速核算这些值

咱们将这组部分特征和邻域特征称为邻域特征

• local特征本质上都是对节点度的度量。假如图是有向的，则它们包含入度和出度以及总度。关于加权图，它们包含每个部分特征的加权版别。
• 依据节点的EGO网络(也称为，EGonet)。EGet包含节点、其街坊以及这些节点上的导出子图中的任何边。Egonet特征包含egonet内的边数，以及进出egonet的边数。严格地说，后者不在egonet中，但不需求查看非egonet节点就可以核算它们。与部分特征一样，假如边是有向和/或加权的，咱们核算这些特征的有向和/或加权版别

2.2 Recursive Features

咱们广义地将递归特征界说为在节点的街坊之间对特征值进行核算的任何聚集

2.2.1 Generating Recursive Features

目前，Refex收集了两种类型的递归特征：均值和和

作为一个典型的比方，一个递归特征被界说为特征在节点的一切街坊之间的未加权度的平均值

可以聚合的特征不限于邻域特征，乃至不限于结构特征

可以在任何实值特征(包含其他递归特征)上核算聚集

咱们核算一切特征值的平均值和和

此外，假如适用，咱们会别离为传入和传出边核算这些参数

2.2.2 Pruning Recursive Features

显然，或许的递归特征的数量是无限的，而且随着每次递归迭代而呈指数增长

为了削减生成的特征的数量，可以选用各种修剪技能

一个简单的比方是寻觅高度相关的特征对

在本例中，修剪战略是只需两个特征的相关性高于用户界说的阈值，就消除其间一个特征

出于核算原因，refex运用此办法的简化版别

具体地说，特征值经过笔直对数库被映射到小整数，然后REFEX寻觅其值从不超越阈值的不共同的特征对

有关门槛的具体信息，请参阅下面的第2.3节。

首要，每个特征的值被转换成巨细为p的笔直对数箱（ logarithmic bins ）(其间0<p<1)。其进程如下

• 关于特征fif_ifi​，具有最低fif_ifi​值的$p|V|$节点被从头分fif_ifi​值0
• 假如存在相关，则或许需求包含多于$p|V|$个节点
• 接下来，为剩下节点中的p个部分分配fif_ifi​值1，并为之后的其他节点中的p个分配值
• 重复此进程，直到一切fif_ifi​值都被0到logp−1(∣V∣)log_{p^{−1}}(|V|)logp−1​(∣V∣)之间的整数值替换停止(拜见图2)

咱们依据调查到的许多图的性质呈现出幂规律散布来为一切特征挑选对数库[1]

具体地说，对数库总是在具有较大特征值的节点调集中放置最大的辨认力

这是合理的，因为咱们期望可以对咱们有许多观测的活动节点做出更好的猜想，而不是咱们只有几个观测到的节点

一旦一组特征被生成并入库，ReFeX就会寻觅在任何极点上不存在超越阈值s的不共同的特征对

咱们称之为s-friend

---

为了消除冗余特征，咱们结构了一个特征图，它的节点是特征，链接是s-Friend联系

此图的每个衔接组件都替换为单个要素

在或许的状况下，咱们保存“更简单”的特征，即运用较少的递归迭代生成的特征。

假如递归迭代导致没有保存的特征，Refex会暂停并陈述每个从前迭代的保存的特征值

留意，因为在特征图中将它们衔接的递归特征，在迭代k中保存的特征或许不被保存在迭代k+1中

在这种状况下，咱们依然记载和输出特征，因为它在某些迭代中被保存

2.3 Parameters

参数p的取值介于0和1之间，包含0和1

• 将p添加到太挨近1会削减垃圾箱 （ bins ） 的数量，并添加有用的修剪攻击性，这或许会导致辨别力的损失
• 将p减小到挨近0可以在剪枝进程中生成许多垃圾箱并保存许多特征，这会明显添加运转时刻

在咱们的试验中，咱们发现p=0.5是一个正确的挑选–每个bin包含剩下节点的下半部分

咱们还发现，只需p的值不在0或1附近，成果对p的值就不灵敏

---

关于s，refex在每次迭代中运用松懈

• 关于小图形(≤100K节点)，REFEX运用s=0进行初始迭代(以生成邻域特征)，这有用地保存了与对数仓值中的另一个特征不彻底共同的任何特征
• 关于较大的图(>100K节点)，假如核算资源不足以生成全集，则可以添加s的初始值，在随后的每次迭代中，REFEX将s加1，这保证了该进程在不超越logp−1(∣V∣)log_{p^{−1}}(|V|)logp−1​(∣V∣)次迭代后将停止，因为任何特征的最大值在该点

2.4 Computational Complexity

设$n$为结点数，$m$为边数，$M$为最大度，$f$为特征数，did_idi​结点i的度

REFEX的核算杂乱度可分为两步：

• (1)邻域特征的核算
• (2)后续每次迭代的核算

关于实在世界的图，邻域特征的核算预计需求$O(N)$

具体内容见引理1

在随后的每次迭代中，refex花费$O(f(m+nf))$时刻，其间$f<<n$

空间需求为$O(m+nf)$

3. FEATURE EFFECTIVENESS ON NETWORK CLASSIFICATION

咱们描绘了运用REFEX的特征进行网络内和跨网络分类的试验

3.1 Data

IP-A和IP-B是在不同的企业网络上相隔大约一年收集的实在网络盯梢数据集。节点是IP地址，链路是IP之间的通讯。IP-A盯梢从第1天的午夜开端，一向继续到第5天的下午12点。IP-B盯梢从第1天的午夜开端，一向继续到第6天的≈5 PM

关于IP-A数据集的第1-4天(IP-A1到IP-A4)，咱们提取了12 PM-1 PM期间的流量咱们不包含第5天，因为盯梢在下午12点结束关于IP-B，咱们仅在第三天从中午12点到下午1点提取流。然后，咱们运用依据负载签名的分类东西来符号一切流。一旦网络流被符号，咱们经过从主机的流中挑选最频频的类别标签来将标签传输到主机。有用载荷分类器可以区别超越15个事务类别(例如，Web、DNS、SMTP、P2P)。但是，因为咱们发现三类(即Web、DNS和P2P)构成了超越90%的符号主机的首要流量类型，因而咱们去掉了一切其他标签，并将重点放在三类分类问题上。表1总结了咱们提取的数据。

3.2 Classifiers

为了测验Refex的特征的猜想才能，咱们运用了Gallagher等人描绘的对数森林模型。[11]。Log森林是一个袋装模型，由一组Logistic回归(LR)分类器组成，其间每个分类器被赋予f个总特征的log(F)+1的子集。在咱们的试验中，咱们运用了500个LR分类器的对数森林。如加拉格尔等人。[11]，咱们发现LogForest的全体功用优于规范Logistic回归。此外，作为基准，咱们包含一个规范的依据同质性的联系街坊分类器：wvRN(加权投票联系街坊的缩写)[23]。WvRN分类器已被证明在一系列使命中具有超卓的功用。咱们比较的量词有

• WnRN+RL-联系街坊模型，运用wvRN和松懈标注进行调集分类
• 邻域-仅运用邻域要素的日志森林模型
• 区域-运用区域特征(即邻域+递归)的对数森林模型

3.3 Feature Effectiveness on Within-Network Classification

3.3.1 Methodology

每个数据集包含一组中心节点，咱们对这些中心节点有根本现实(即，咱们知道实在的类别标签)。在一切状况下，分类器在练习和测验期间都可以拜访整个数据图。3但是，并不是一切的中心节点都被符号。咱们将符号中心节点的份额从10%到90%不等。分类器在一切已符号的中心节点上进行练习，并在一切未符号的中心节点上进行评价

咱们的办法如下。关于每个符号的中心节点份额，咱们运转10次试验并陈述平均功用。关于每个测验和份额符号，咱们挑选一个包含(1.0-份额符号的)%的中心实例的类分层随机样本作为测验集，其他的中心实例成为练习集。请留意，符号为小于0.9(或大于10次试验)的份额意味着单个实例必然会出现在多个测验集中。因为这种堆叠，测验集不能成为独立的。但是，咱们细心挑选测验集，以保证在咱们的试验进程中，咱们数据集中的每个实例都出现在相同数量的测验集中。这可保证每个实例在整体评价中具有相同的权重，而不考虑所符号的份额。标签保存在练习实例上，并从测验实例中移除。咱们对每个分类器运用相同的练习/测验拆分。咱们的试验结构依据开源的Weka体系[28]。咱们完成了自己的网络数据标明和试验代码，它处理将数据拆分成练习和测验集、符号和撤销符号数据以及将网络片段转换为与Weka兼容的形式等使命。咱们依靠Weka完成逻辑回归，并在个人练习/测验试验中衡量分类器的功用。

3.3.2 Results

图3展现了wnRN+RL、邻域和区域分类器在IP-A3数据集的网络内分类使命中的功用。咱们在IPA的每个数据集上重复了这项使命，成果根本相同。网络内分类设置是wvRN等依据同源联系的模型的甜美点。因而，毫不奇怪，wvRN+RL在这项使命中体现杰出，网络中90%的节点都被符号了。但是，随着标签变得更加稀疏，wvRN+RL的功用迅速下降。区域分类器和邻域分类器对符号数据的可用性不那么灵敏，因为它们不依赖符号的街坊来进行精确的分类。因而，当标签数据稀疏时，区域分类器的功用优于wvRN+RL。邻域和区域在功用上的巨大差异标明，递归特征生成进程导致更具体现力的特征，这些特征可以标明仅靠邻域特征无法捕获的重要概念。

3.4 Feature Effectiveness on Across-Network Transfer Learning

3.4.1 Methodology

关于每个试验，练习图都有一切可用的已知标签。测验图彻底没有标签。在测验图中的一切已知根本现实标签上对每个分类器进行评价。咱们对一切数据集运用相同的特搜集。这组功用来自对IP-A1数据集运转REFEX。表2总结了跨网络试验。

3.4.2 Results

图4展现了Neighborhood和Region在一系列跨网络搬迁学习使命上的体现。在这儿，咱们在一个网络上进行练习，其间一切已知的标签都可用，并在彻底没有标签的独自网络上进行测验。考虑到数据集之间类别散布的差异(有时是极点的)，咱们强调了这些使命的难度(拜见表1)。默认分类器的功用是每个使命难度的一个很好的指示器，因为该模型仅依据练习集中最频频的类别进行猜想。咱们还留意到，wnRN+RL不适用于这些使命，因为它依赖于一些已知类标签的可用性来耕种推理进程。

与网络内设置一样，区域分类器在跨网络使命上的全体体现最好，在IP-A的独自几天完成了82%-91%的精确率练习和测验，在IP-A和IP-B的一切天数完成了77%的精确率练习和测验。考虑到IP-A4和其他数据集在类别散布上的极点差异，应用于IP-A4的区域数据的功用特别令人印象深刻(拜见表1)。咱们留意到，区域性的IP-A4培训不太成功。现实上，关于IP-A4的培训和关于IP-B的测验是区域体现逊于街坊的一个案例。但是，功用差异很小(<5%)。终究，并不令人惊奇的是，咱们看到了针对多个不同数据集而不是单个数据集进行培训的优点。具体地说，咱们在一切IP-A数据集上完成了77%的练习，并在IP-B上进行了测验，而咱们看到IP-A在个别天的练习有很大的差异(55%-85%)。

4. FEATURE EFFECTIVENESS ON IDENTITY RESOLUTION

为了演示区域特征捕获节点的有意义和信息量的行为，咱们供给了一组身份解析使命。在每个使命中，咱们核算节点集堆叠的网络对上的一组区域特征。咱们的假定是，节点的特征值在图中将是类似的。咱们提出了一个试验结构，答应咱们对此进行经验测验。在咱们的试验中，咱们将演示当外部非匿名数据可用时，怎么运用该办法对交际网络数据集履行“去匿名化”。

4.1 Problem Statement

关于节点集堆叠，但边集可以是不同的(乃至代表彻底不同类型的观测)的两个图，咱们是否可以仅运用网络结构来将一个网络中的节点映射到另一个网络中的节点？更现实地说，咱们是否可以削减与一个图中的每个节点相相关的熵，相关于它在第二个图中的节点之间或许的同一性？关于给定的办法，咱们将经过核算该办法在找到第二个图中的正确节点之前猜想了多少个“过错”节点来衡量该使命的成功与否。

4.2 Methodology

咱们得到了两个图，GTarget和Greference，以及在这两个图中都存在的vertex vtest。为了测验给定的身份解析战略，咱们答应该战略猜想引用极点<vguess1，vguess2，.。。，vguess k>，直到它正确地猜想到vtest。与该战略相相关的分数是k，即查找节点所需的猜想次数。基线办法是随机猜想；关于此战略，咱们假定预期分数|Vreference|/2。

咱们在试验中测验的战略运用结构特征来核算猜想。咱们给出了(1)部分特征、(2)邻域特征和(3)区域特征的成果。这些特征是运用GTarget上的Refex核算的。然后在Greference上核算相同的特征。关于给定的战略，在特征空间中依照间隔V方针的欧几里得间隔递加的次序生成猜想。咱们的假定是区域得分会比本地或邻里得分低(即更好

为了比较战略的全体功用，咱们核算了两个图中存在的一切极点的调集堆叠的分数。当不能在核算上分析每个节点时，咱们挑选一组极点sTestSoverage，并陈述⊂中节点的一切分数。在这些试验中，咱们挑选Stestby，取V方针中具有最高阶数的1000个极点，并仅保存也在堆叠中的那些极点。

有许多办法可以比较给定测验集上的功用。例如，一切方针实例的平均分数是衡量成功程度的方针，平均分数越低标明功用越好。咱们还可以核算得分低于给定阈值的方针实例的分数；在这儿，分数越大越好。例如，咱们可以陈述得分小于|Vref erence|的1%的方针折点的份额。4

4.3 Data

表3概述了这组试验中运用的数据集。第一个是2008年的两个推特网络，包含一个重视谁的网络和一个说到谁的网络。第二个是短信通讯网络。第三个是为期28天的yahoo即时通讯活动的调集。第四个是在几个不一起刻调查到的两个独立企业网络上的IP流量。咱们在第3.1节中具体介绍了IP网络。

yahoo!IM网络公司。这儿的每个图是从28天的调查中获取的IM事情的调集。5每个节点是一个IM用户，每个链接是给定日期的一个通讯事情。在某些状况下，给定的一对用户在给定的一天内会陈述多个事情；当发生这种状况时，会依据陈述的事情数量为链接赋予权重。

咱们运用第一天的IMS作为GTarget，并核算其他日期(2-28日)的分数作为Greference。这儿的使命是从第一天开端接纳IM用户，并在以后几天找到他。图5显现，关于allGreference图，节点集和边集与GTarget的类似性较低。但是，在大多数状况下，与测验集sTest中的1000个节点有很大的堆叠。

企业网络追寻。咱们将在第3.1节具体描绘这些IP网络。方针图来自IP-A1。共有四个参阅图：IP-A2、IP-A3、IP-A4和IP-B。使命是辨认从一天到第二天或从一个IP网络到下一天的外部IP地址。此使命的一个潜在应用是对隐藏IP地址的网络盯梢进行去匿名化；人们可以调查到非匿名化的企业盯梢并运用结构信息来猜想匿名化IP的身份。

推特上的联系。这个数据集由2008.6年推特上的两个图表组成，一个是由几个种子用户(都是具有经过验证的账户的名人)和抓取几次“重视”链接生成的交际“谁重视谁”网络。另一条是从一年中调查到的实践推文中提取的。调查到推文的用户与交际网络中的用户相同。

为了从tweet构建一个图，咱们生成“提及优先”的边。也就是说，假如用户1的推文包含用户名(例如@user2)，咱们将在网络中添加用户1和用户2之间的链接，但前提是用户2是推文中说到的第一个用户。咱们不包含自我提及。

在本试验中，咱们运用交际网络作为GTarget，提及网络作为Greference。这项使命的成功标明，只需可以从文本中解析用户名，就可以经过运用揭露可用的文本数据来消除交际网络的匿名性。这对已发布的“匿名”交际网络中用户的隐私具有重要影响。

短信。短信数据集由亚洲一家移动电话运营商的短信构建而成。每个节点对应一个手机客户端。参阅图和方针图对在两个不同日期提取的那些节点之间的短消息数量进行编码。咱们还消除了那些活泼度较低的用户对，他们之间只有一次消息交流。

4.4 Feature Effectiveness Results

咱们给出了四个数据集的成果。前三篇文章展现了地域性特征对身份解析的有用性，第四篇文章是关于测验集挑选的实践者的说明。

yahoo!IM网络公司。图6显现了27个参阅图中每一个的平均分数，作为基线战略中预期分数的百分比(回想一下，基线战略平均得分|Vreference|2)。一切依据特征的战略都优于基线战略，但当图表显着不一起，一切战略的功用在周末都会受到影响。整体而言，Neighborhood的预期分数比Local好(低)得多，而Region比Neighborhood略好一些。

图7供给了功用的另一个视图。这儿的每个数据点都显现了得分超越最大或许分数1%的测验节点的分数|Vref erence|。分数越高，功用越好，因为分数散布更挨近最低分数1。同样，在大多数状况下，区域战略的体现优于其他战略。这种改善在周末会有所下降，在一种状况下(第27天)，区域的体现并不比当地的好。

周末的糟糕体现并不出人意料，这让咱们坚信结构特征正在捕捉行为。回想一下图5，周末的活动用户集和调查到的通讯集显着不同。直观地说，这是一个显着的现实，即许多用户在周末的IM通讯方面的行为整体上和在作业日都不同。在这种状况下，区域特征特别简单犯错，因为这些行为变化在递归特征生成进程中会被放大。

企业网络追寻。区域在随着时刻的推移盯梢外部IP地址方面十分有用，如图8所示。它在一切测验中都主导着Local和Neighborhood的功用，即使在调查到GTarget中的通讯一年后，也有超越45%的sTest得分位于或许分数的前1%。请留意，一年后，因为堆叠削减，Stestis显着变小；陈述的成果是|sTest|的一小部分。尽管盯梢是从不同的网络收集的，但公共外部节点(如google.com)将包含在这两个网络中。

在这项使命中，平均分数不共同，在某些状况下，当地的体现优于区域。对分数散布的分析标明，在大多数测验实例中，Region的体现优于Local，但有一小部分测验节点的Region体现十分差(挨近基线)。

推特上的联系。这个试验是“最难的”，因为GTarget和Greference是由不同的进程发生的。GTarget是一个用户重视其他用户的交际网络，而Greference是经过用户在推文中说到彼此而发生的。令人惊奇的是，咱们的办法依然可以很好地解析这儿的一些用户。

在这个试验中，咱们将每种战略应用于几个不同的测验集，而不是只按程度挑选前1000个节点。特别是，咱们在每个笔直对数箱上别离进行了测验(拜见第2.2.2节)。关于超越1000个用户的垃圾桶，咱们统一随机抽样1000个用户。

图9显现了每种战略的预期分数。十个最高度的垃圾桶加在一起，大致对应于按度摆放的前1000个节点。区域性特征在这一范围内的体现优于其他战略，尽管它们的体现在较低程度的垃圾桶中有所下降。

这三种战略在这些图表上的体现都不如在其他数据集上好，但它们依然可以明显降低最活泼用户的熵。例如，第一流别的用户是BarackObama，而Region在该实例上的得分为5(四个过错猜想别离是AddToAny、Mr Tweet、tferriss和the_Real_Shaq)。巴拉克奥巴马在当地和邻里各得了24分。

关于程度最低的节点，一切办法的功用都比基线差。这种削减是意料之中的；较不活泼的节点更难辨认，因为(1)它们可运用的调查行为较少，(2)有更多与它们十分类似的节点。

短信。此数据集用于指出Region的体现不是最好的状况，但也是实践者的说明，当在试验设置之外履行身份解析时，通常会答应改进成果。

图10显现，得分高于|Vreference|1%的节点的功用取决于Stest的元素。当STEST由排名前1000的节点组成时，每种办法在60%−65%的测验节点上的得分都高于1%，区域测验的功用最差。但是，假如答应每种战略经过按特征向量巨细挑选前1000个节点(在该战略的特征空间中)来“手工挑选”测验集，则功用将全面进步。区域性的前进最大，在这种状况下是体现最好的。

经过答应每种战略挑选其测验集，咱们运用了这样一个现实，即高度节点或许没有具有其他较大特征值的低度节点那么共同。但是，作为比较战略的试验，这种办法并不“公平”，因为每个战略的测验实例集是不同的。

咱们测验了其他数据集，以确定在挑选测验节点时，特征幅值是否总是好于度数。尽管这在一般状况下是正确的，但在运用特征起伏时，也存在功用下降的状况。这通常是因为1000个拟议测验节点和Vref erence之间堆叠的巨细不同形成的。

就运转时刻而言，咱们最大的图(Twitter说到的有840K节点和1.4M条边的图)在一个商用处理器上运转了大约5个小时。节点少于100K的图在一小时或更短的时刻内运转。

5. RELATED WORK

图形数据中的特征工程。实图的大局结构特征和部分结构特征现已得到了广泛的研讨。例如，在全球范围内，现已调查到图形直径很小[2]，而且随着时刻的推移而缩小[20]。也有报导称，时变图中的边数与节点数呈超线性增长，遵从幂规律联系[20]。此外，图的主(最大)特征值被证明是作为图的脆弱性度量的信息量[27]。其他地方和社区等级的调查标明，许多图中的度散布遵从幂规律[5，7，17，24]，而且图呈现模块化结构，节点形成组，组内形成组[9，14]。这项作业让咱们挑选了一组邻域特征，然后咱们在这些特征的基础上构建递归特征。

面向数据发掘的特征提取。也有相关的作业，运用图中的特征提取来履行几个数据发掘使命。一项研讨将链接猜想作为有监督的学习问题[21]。它们提取了节点对的拓扑特征，并标明这些特征进步了猜想功用，而且有监督办法的功用优于无监督办法。最近的另一项研讨[16]开发了一个依据图、子图和节点级特征的多层结构来检测时变图中的反常。这些算法依赖于提取图形等级(大局)特征，并随着时刻的推移盯梢这些方针。被辨认为感兴趣或可疑的时刻点被传递到更精密的等级，在那里更杂乱的东西检查节点和社区特征以发现感兴趣的区域并符号反常节点。另一项研讨提取网络特征和形式，以检测加权图中的反常节点[1]。也有关于运用部分和大局结构特征来进步网络分类器的功用的作业[10]。在咱们的作业中，咱们介绍了递归特征提取的办法。成果标明，与非递归特征相比，递归特征在搬迁学习和身份解析等数据发掘使命中具有更好的功用。

另一项相关作业运用频频子图作为图[18，8]的分类和反常检测[26，22]的结构特征。但是，这些办法假定给定图中的节点有标签。另一方面，咱们的特征提取进程运用了图的结构，而不需求任何关于标签可用性的假定。

搬运学习。搬迁学习(即范畴习惯)是近年来一个十分活泼的研讨范畴。代表性的作业包含多标签文本分类[30，13]、跨域情感猜想[4、6、15]、侵略检测[12]、动词论元分类[19]、跨言语分类[25]和跨域联系提取[29]。在一切这些场景中，特征都作为其算法的输入(例如文档的词频)，方针是运用给定的特征来进步方针范畴的功用。在本文中，咱们旨在答复一个正交问题：在将知识从源域搬运到方针域的进程中，什么样的特征是有用的？咱们的案例研讨标明，所提出的递归特征关于跨网络分类和身份解析确实是有用的，特别是当方针域中存在很少或没有标签时，或许类标签之间的同质性不成立时。咱们期望所提出的递归特征对搬迁学习使命具有广泛的适用性。

6. CONCLUSIONS

咱们描绘了一种新的算法REFEX，该算法依据节点的邻域连通性从节点中提取区域特征

这些区域特征依据给定节点所衔接的节点类型来捕获行为，而不是依据这些节点的身份

咱们证明了REFEX在各种图发掘使命中的可伸缩性和有用性，包含网络内和跨网络的分类和身份解析使命

未来的作业包含将ReFeX生成的区域特征用于其他发掘使命，如聚类、反常检测和网络比较。

读后总结

2022/08/14 第一次阅览

refex用于提取图中节点的特征

进程：

• 先核算此节点的邻域特征（local + egonet 特征）
• 然后再递归 聚合其邻域的特征（均值 or 和）
  • 假如本来一个节点特征为[1,2,1,1] 邻域特征为[1,2,3,1]
  • 此时会先判定邻域特征中：若两个特征类似，则只需求保存一个即可，比方开端为1，结尾为1，这两个特征类似度很高，放弃一个，得到[1,2,3]
  • 然后再将其添加至原特征后边，得到[1,2,1,1,1,2,3]
  • 然后再运用logarithmic bins 分箱，放弃一些特征（削减维度）
  • 终究得到[1,2,1,3]（仅为举例）

所以终究得到的节点特征的维度受迭代次数和bin值的影响

• 迭代次数越多 ，维度越高
• bin值越大，维度越高

参阅代码：github.com/benedekroze… 试验得到

本次阅览只了解其办法思想，未对试验进行细心研读

结语

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

期望对您有一点点协助，如有过错欢迎小伙伴指正