Towards Understanding and Evaluating Structural Node (Survey)

Towards Understanding and Evaluating Structural Node

基本信息

博客创建者

金蝉子

作者

JUNCHEN JIN, University of Michigan, USA
MARK HEIMANN, University of Michigan, USA
DI JIN, University of Michigan, USA
DANAI KOUTRA, University of Michigan, USA

标签

structural, node embeddings

摘要

虽然大多数网络嵌入技术对网络中节点之间的邻近性进行建模，但最近人们对基于节点等效性的结构嵌入产生了极大的兴趣，这一概念植根于社会学：等效性或位置是具有相似角色的节点的集合，即相似功能，无论其在网络中的距离或可达性如何，与其他位置的节点的联系或交互。与文献中严格评估的基于邻近性的方法不同，结构嵌入的评估并不成熟。它依赖于小的合成或真实的网络，其标签没有被完美地定义，它与社会学等价性的联系迄今为止是模糊和脆弱的。随着新的节点嵌入方法正在以惊人的速度发展，对现有方法进行适当的评估和系统描述将是取得进展的关键。

为了填补这一空白，我们开始了解结构嵌入捕获的等效类型。我们是第一个为结构嵌入提供严格的内部和外部评估方法，以及精心设计的不同大小的数据集。我们观察到许多不同的评估变量，这些变量可能导致不同的结果（例如，相似性度量的选择、分类器、标签定义）。我们发现，节点局部邻域内的度分布可以导致简单而有效的基线，并指导结构嵌入的未来发展。我们希望我们的结果能够影响进一步节点嵌入方法的设计，并为更全面和公平地评估结构嵌入方法铺平道路。

简介

问题

目前，结构嵌入的评估主要是使用带有标签的人工或真实数据集，做节点分类或者聚类，但是标签的定义和社会学等价性的联系往往是模糊的。对结构嵌入的理解和评价需要有更系统的方法。

贡献

（1）提出了内在的（无下游任务）和外在的的评价方法
（2）使用了多种数据集，重新定义其标签
（3）对之前的方法做了大量的分析

观察

（1）许多因素会影响最终的评价结果，如：相似性度量的选择、分类器、标签定义、指标

​（2）直接使用节点局域邻居 的度分布的方法 能有很好的效果，可以作为基线方法，也能为新方法提供思路

嵌入的评价标准：在嵌入空间中，越接近的节点，其在图中应该越相似（邻近性，等价性）

方法

对比的方法

基于邻近性的:
node2vec–https://arxiv.org/pdf/1607.00653.pdf
LINE–https://arxiv.org/pdf/1503.03578.pdf%C2%A0%E3%80%90WWW

基于结构的:
struc2vec–https://arxiv.org/pdf/1704.03165.pdf
GraphWave–https://arxiv.org/pdf/1710.10321.pdf
xNetMF–https://dl.acm.org/doi/pdf/10.1145/3269206.3271788
SEGK–https://ieeexplore.ieee.org/abstract/document/8869809
role2vec–http://graphrepresentationlearning.com/pubs/role2vec-DLG-KDD.pdf
RiWalk–https://arxiv.org/pdf/1910.06541.pdf
DRNE–https://pengcui.thumedialab.com/papers/NE-RegularEquivalence.pdf
MultiLENS–https://dl.acm.org/doi/pdf/10.1145/3292500.3330992

基于度的 : degree, degree1， degree2（2-hop 邻域内节点在度数上的分布）

三种等价性

结构等价性：两个节点在结构上是等效的，因为它们与相同的节点具有相同的连接（与邻近性相关，因为结构等价的节点，距离不超过2跳，所以基于邻近性的方法能更好的捕捉到该信息）

自同构等价性: 如果存在将一个节点映射到另一个节点的自同构（即同一图中的同构），则两个节点是自同构等价的。

正则等价性: 如果两个节点以相同的方式与等价节点相关，则它们是规则等价的。

四种图的指标

（用来衡量图的一些结构特征）

​ 度，节点连接性的最直接度量

​ PageRank，一种衡量节点重要性的分数, 根据邻居的值递归地计算（递归计算，理论上可以接收全局信息）

​ 介数中心性描述一个节点在多少对节点的最短路径上 （全局信息）

​ 这三种描述中心性，越高的值代表该节点连接良好，结构作用突出

​ 聚类系数描述节点的邻居有多少是相连的（局部信息），衡量邻域的连接稠密度

下游任务

单网络任务：节点分类、节点聚类

​多网络任务：网络对齐，图分类

研究目的

1. 理解

​ 理解结构嵌入能捕捉什么样的结构特征（等价性，图的指标）

2. 评估

​内在的评估–嵌入空间中节点的相似性（距离）& 通过重新定义的标签或网络科学的概念得到节点相似性
外在的评估–使用下游任务的指标来评价

数据集

真实数据集：单网络任务

1. 限制

​ 大多数都使用的air-traffic 图，其节点标签是根据对人流或航班数量，划分为4类

​ 改变：将人流或航班数量进行logarithmic bins划分，其分布满足幂律分布

2. 新数据集

​ （1）用等价性来定义标签

​ （2） 增加的数据集：BlogCatalog, Facebook, ICEWS…

3. 重新定义角色或标签

​ 在内在评估中，利用现有的算法来定义角色（给出邻接矩阵$A$ , 得到基于等价性的相似矩阵$S$ ）:

​ 结构等价性 – CONCOR （可直接划分类别）

​ 自同构等价性 – MAXSIM

​ 正则等价性 – CATREGE

​ （后两种方法，需要再对$S$ 做层次聚类 得到类别）

真实数据集：多网络任务

合成数据集

在上图的基础上，增大了一些数据集

嵌入和结构特征

为了理解，对比的方法能多大程度的捕捉到度或 其他结构信息（e.g. 中心性），进行相关性和预测分析

方法（内在的）

首先： 查看类似的嵌入节点是否具有类似的结构特征
​ （1） 计算图中每个节点的4种图的指标 $p_i(v)$

​ （2） 在嵌入空间中找到 $v$ 的 k-NN （欧氏距离、cosine距离），计算平均值 $\overline{p_{i,kNN}(v)}$

​ （3） 计算 $p_i(v)$和 $\overline{p_{i,kNN}(v)}$ 的Peason correlation（值为1–正线性相关；值为0–非线性相关）

其次：为了更好地理解结构嵌入中的编码程度，我们还完成了一项预测任务。

​ （1） 使用5折交叉验证，应用k-NN 回归，计算节点度的预测值和真实值的误差

​ （2） RMSE（Root Mean Squard Error）作为指标

结果

观察 1

​ 当前的结构节点嵌入很好地捕捉了节点的重要性度量，如度和Page rank，但不太清楚地分辨出由介值和聚类系数给出的连接密度

不同的距离metrics 也会让结果不一样

嵌入和等价性

为了理解，对比的方法能多大程度的捕捉到3种等价性信息，进行内在的和外在的评估

内在评价

嵌入空间中节点相似性 和 由3种等价性定义的相似性的联系

方法

​ 1. 计算每个节点的Kendall rank correlation coefcient （值为1，正相关；值为0，独立）-- 嵌入相似性 和 结构相似性 (通过前面计算等价性的算法得到)

​ 2. 计算不同等价性对应数据集，不同节点的Kendall 系数的均值和方差

结果

观察 2

​（1）结构等价性取决于节点邻近性，事实上结构嵌入不能很好地捕捉到，但自同构等价性不取决于节点的邻近性，结构嵌入可能比保持邻近性嵌入更好地捕捉到。
（2）度分布，在捕捉自同构等价性和正则等价性效果很好

观察 3

​ 节点度，广义上包括其k跳邻域中的分布，可能确实是节点在网络中的结构位置或作用的良好指标

在每个数据集上的结果

观察 4

​没有一种结构嵌入方法被优化以捕捉角色对等的社会学概念。

尽管这些方法能捕捉到某种程度的等价性，但是其表现主要取决于，数据集的等价性类别和方法能捕捉到的等价性类别的对应。

外在评价

有下游任务，标签是由相应方法定义

方法

​ 1. 重新定义节点标签

​ 2. 节点的分类和聚类任务

结果

观察 5

​（1）合成数据集清晰的结构角色是揭示结构嵌入方法之间差异的好方法

（2）在合成数据集上不同方法表现出来的差异更大

（3）内在评估和外在评估都应该做

观察 6

​ 内在评估和合成数据集通常是一种方法在图挖掘任务上性能的良好近似，但不能完全替代真实数据集上的外在评估。

利用结构嵌入挖掘单个网络

实验设置

节点分类任务

数据

​ 所有Table1中的数据集，除了BlogCatalog 和 Facebook, 因为其节点标签没有反映出结构角色

分类器

​ Logistic regression, linear SVM (one-vs-rest )

​ k-NN(k=5)

分类器的影响

方法

​对相同的嵌入，分别采用三种分类器，得到方法在某一数据集上的rank，再求均值和方差（方差大意味着分类器对方法的performance rank影响大）

结果

​ 分类器的种类对方法的performance rank有较大影响，不同的评价指标也会有影响。

标签定义的影响

方法

​ 在机场的三个数据集上，使用原始标签和 logarithmic bins 得到的标签，使用逻辑回归分类，指标为Micro-F1

结果

​ 不同的标签定义对方法的performance rank有较大影响

观察 7

​ 许多与节点嵌入过程无关的因素会影响无监督结构节点嵌入方法在下游图挖掘任务上的明显相对有效性，包括：

• 下游机器学习分类器
• 用于评估性能的指标
• 定义节点标签的方式

更深入的观察

为了探索什么样的节点（e.g. 高度数的）更容易分类正确

方法

​ 将EU air-traffic数据集，根据度数分为三部分：low-deg $[0,Max{D}^{\frac{1}{3}})$ ，medium-deg $[Max{D}^{\frac{1}{3}},Max{D}^{\frac{2}{3}})$ , high-deg $[Max{D}^{\frac{2}{3}},MaxD)$

​ 或者根据participating triangles分为三部分

​ 在每部分数据集，做5折交叉验证

结果

​ 高连接性的节点 最容易分类， 其次是低连接性的 ，最后是中连接性的

​ 不同部分数据集上，方法的performance rank 是一致的

观察 8

​ 与中等嵌入方法相比，当前的结构嵌入方法在区分潜在特征空间中的“极端”网络位置方面最有效

综合比较

我们观察到，嵌入方法没有明显的赢家，特别是当数据集、标签、分类器和度量都可能发生变化时。

一些最好的排名方法是MultiLENS、SEGK和度分布特征的变化

观察 9

​ 当前依赖于节点结构角色的单个网络挖掘任务可以通过基于度的连接性信息的本地聚合来有效解决

[亮点]

本文对当前一些结构嵌入的方法进行了总结和分析，提出了新的嵌入质量的评价方法。提出了许多观察，这些观察有助于我们在结构嵌入这一方面更加辩证的看待相关方法的效果。

[启发]

当前的一些评价方式并不是完美的，如果提出新的评价方式，补足原有方法的缺点，也是一种好的idea。

度信息是图中非常重要和基本的结构信息。

BibTex

@article{jin2021toward,title={Toward understanding and evaluating structural node embeddings},author={Jin, Junchen and Heimann, Mark and Jin, Di and Koutra, Danai},journal={ACM Transactions on Knowledge Discovery from Data (TKDD)},volume={16},number={3},pages={1--32},year={2021},publisher={ACM New York, NY}
}