表征学习驱动的多重网络图采样
1.
2.
Representation learning driven multiple graph sampling
1.
2.
通讯作者:
收稿日期: 2022-01-30
基金资助: |
|
Received: 2022-01-30
作者简介 About authors
虞瑞麒(2001—),ORCID:
关键词:
Keywords:
本文引用格式
虞瑞麒, 刘玉华, 沈禧龙, 翟如钰, 张翔, 周志光.
YU Ruiqi, LIU Yuhua, SHEN Xilong, ZHAI Ruyu, ZHANG Xiang, ZHOU Zhiguang.
在实际应用场景中,节点之间的关系可能不止一种,这种具有多种关联关系的节点构成了一组多重网络[3]。例如,同一组社交用户群体分别在使用QQ、微信和微博等不同社交软件,并在不同的社交媒体平台上拥有不同的好友关系,由此产生的多种社交关系网就是典型的多重网络。
传统的图采样算法都是单图采样,即关注如何在一张网络图上通过采样保留其特定的拓扑结构特征,如度分布、聚类系数、平均路径长度等。如果直接将单图采样算法分别应用于多重网络的每一重图,则会令采样得到的节点集不一致,增大图采样结果的存储空间,也会造成采样分析和探索不连贯。如果只对多重网络中的某张图进行采样,然后依据该结果重构其他图的采样网络关系,会造成采样参照的网络图结构特征保持相对较好,而其他图的结构特征极易丢失。因此,传统的图采样算法不适用于多重网络图,不利于多重网络图的联合采样分析。
为解决以上问题,本文提出表征学习驱动的多重网络图采样算法。首先,设计多重网络图表征学习方法,综合考虑多重网络的结构特征,将所有节点投影至二维表征学习空间;其次,利用和改进经典的自适应蓝噪声采样算法,考虑节点密度和网络连通性,从二维表征学习空间中启发式地筛选出部分节点,以实现多重网络图上下文结构特征的同步保持;进一步,开发了一套多重网络图采样可视分析系统,支持用户交互式地探索和评估多重网络图的采样结果,将其与已有采样算法进行对比。基于真实数据的案例分析和量化实验均显示,本文算法在进行多重网络图采样时是有效的,其重要节点、网络连通和社区相似性等多项指标均优于传统的图采样算法。
1 相关工作
1.1 图采样算法
在可视化领域,图采样已广泛应用于大规模复杂网络图的简化表达,通过降低点线交叉重叠引起的视觉混淆,增强用户对网络结构的认知和理解。HU等[7]提出基于图连通性的光谱顶点采样算法,能较好地保持原始网络图的连通性和全局拓扑结构。ZHOU等[8]设计了多目标的自适应蓝噪声采样算法,降低人群移动网络的规模,同时保持空间分布特征和社区结构的一致性。GUO等[9]提出了流采样算法,对大规模迁徙网络进行简化表达,改进和利用核密度模型,提取和展示重要边。ZHAO等[10]提出了小结构保持的图采样算法,尽可能保留原始图中的少数结构,如桥节点、边缘节点和高度节点。ZHOU等[1]基于图表征学习,提出了保持上下文结构特征的采样算法,在保留全局结构的同时有效保持聚类密度等特征。
但以上算法均侧重于解决单一网络的采样问题,关注的是如何提高单图的采样效率或如何保持特定的拓扑结构特征。
1.2 图采样评估
为检验图采样算法的有效性,研究者从结构属性和视觉感知角度出发,设计和提出了多种图采样评估指标。一类是由图的结构属性特征驱动的采样评估。例如,MAYIA等[11]利用节点度分布、聚类质量和网络覆盖度等指标,对几种基于遍历的图采样算法进行了评估。另一类是由用户视觉感知驱动的采样评估。NGUYEN等[12]借助代理图的概念提出了基于形状的视觉质量指标,并对比了不同图采样算法对样本视觉质量的影响。WU等[13]通过用户实验总结了影响图采样视觉感知的多项指标,并进一步探索了传统图采样策略在这些指标上的表现力。ZHANG等[14]提出了一套视觉感知标准,包括聚类的大小、形状和数量等,评估了图采样算法在视觉特征保留上的有效性。
1.3 图表征学习
2 多重网络图采样算法
多重网络图采样算法流程如图1所示,包括融合多重网络图结构特征的表征学习和基于表征学习空间的多重网络图采样。
图1
图1
多重网络图采样算法流程
(a)原始多重网络图 (b)融合多重网络图结构特征的表征学习 (c)多目标的自适应蓝噪声采样 (d)多重网络图采样结果
Fig.1
Flow chart of the multiple graph sampling
2.1 融合多重网络图结构特征的表征学习
其中,dtx 为t与x之间的最短路径。由
由
其中,f (u)表示将节点u映射为向量的函数,Ns(u)表示和u出现在同一条序列样本中的邻近节点集合,即在给定某个节点的条件下,使其所在序列样本集中其他节点出现的概率最大。用Skip-Gram模型训练输入序列样本集,最终得到每个节点的向量化表示。
2.2 基于表征学习空间的多重网络图采样
2.2.1 保持上下文结构特征的采样
基于二维表征学习空间,采用自适应蓝噪声采样算法筛选节点,尽可能保留和覆盖原始多重网络图上下文结构特征,如图1(c)所示。
综上可知,传统的蓝噪声采样算法可较好地覆盖整个数据空间,还可根据节点疏密自适应地调整采样圆盘大小,进而控制采样节点的数量,保证节点密度分布的一致性。
2.2.2 多目标采样优化
基于向量化空间的蓝噪声采样在保持多重网络图上下文结构特征上具有一定优势,但在结构连通性保持上存在明显不足。例如,具有较大中介度的节点(桥节点),在网络连通中很重要,但在泊松盘内随机选择代表性节点时易被忽略。此外,蓝噪声采样过程没有考虑多重网络图的复杂连接关系,使得多重网络图的连通性保持存在较大的不确定性。为此,做以下两点改进以增强多重网络图连通性的同步保持。
(1)增加桥节点被选择的概率。在采样模型中加入中介度分析,计算每一重图所有节点的中介度(即任意两节点间的最短路径经过该点的次数),并做归一化处理。节点u在多重网络图中的综合中介度定义为其在每一重图中的中介度总和。记bet (u)为节点u所处局部区域的连通重要性,即以u为圆心、ra 为半径的圆包含的所有节点的平均综合中介度。对以u为中心的泊松盘的半径进行优化:
图2
(2)考虑多重网络图的同步连通性。虽然在向量化空间中,彼此邻近的节点之间相互连接的可能性较高,但由于采样的随机性,难以保证多重网络图在不同网络结构上连接。因此,当一个泊松盘向外拓展确定另一个泊松盘时,需遍历其周边多个不同的泊松盘,同时考虑其包含的节点与当前泊松盘内代表性节点在多重网络图上的连接关系。如图3所示,中间黑实线圆为当前的采样圆盘,黑圆点为选中的代表性节点。假定当前为3重网络图,在周边预设的多个不同泊松盘(虚线圆)中,三角形节点表示与之前的代表性节点在每一重图上均存在连接关系,图3右侧图例中,三角形后面的每个方框表示其中1重网络图,对号表示在对应网络图上连接,叉号表示不连接。菱形节点表示与代表性节点在其中2重网络图上存在连接,圆形节点表示与代表性节点在其中1重网络图上存在连接。如果周边某个泊松盘包含与上一个代表性节点在所有图(或数量较多的图)上都存在连接关系的节点且节点数量较多,那么这个泊松盘将优先作为下一个采样圆盘。相比于其他采样圆盘,在该圆盘内选择某个代表性节点维持多重网络图同步连通性的概率更大。如图3所示,箭头指向的右侧圆盘包含2个与中心圆盘黑色代表性节点在3重网络上都连接的节点,因此优先选中作为下一个采样盘。
图3
图3
考虑多重网络图连通性的泊松盘遍历
Fig.3
Traversal across different Poisson disks for the retention of multiple graph connection.
3 多重网络图采样可视分析系统
多重网络图采样可视分析系统如图4所示。
图4
3.1 多重网络图数据集
系统内置2套多重网络图数据集(
3.2 采样算法和评估指标
表1 评估指标
Table 1
分类 | 指标 | 说明 |
---|---|---|
节点 | 平均中介度(ABD)[4] | 衡量桥节点保留情况,值越大被保留的桥节点越多,表现越好 |
平均中心性(ACC)[4] | 衡量节点中心性保持情况,与原始图结果越一致越好 | |
连接性 | 平均最短路径长度(APL)[1] | 采样图和原始图的平均最短路径长度,越一致越好 |
连通性(CC)[4] | 统计连通分量的数量,值越大连通性越差 | |
社区结构 | 社区相似性(SC)[1] | 度量采样前后社区结构直方图的分布变化,值越大越好 |
社区结构稳定性(SSC)[1] | 使用互信息度量采样前后社区结构的变化,值越小越好 | |
聚类 | 局部聚类系数(LCC)[1] | 采样图和原始图的局部聚类系数,越一致越好 |
全局聚类系数(GCC)[1] | 采样图和原始图的全局聚类系数,越一致越好 |
3.3 可视化视图和交互
通过图4左上角的控制面板加载多重网络数据集,选择不同的采样算法并设置采样率等参数完成图采样工作。系统提供以下可视化形式帮助用户交互式地探索采样结果,并评估各类采样算法。
3.3.1 网络视图
图4中间。用点线连接式的图布局展示采样前后的多重网络结构。上方并排展示采样图,下方对应展示每一重网络的原始图。系统还支持节点、社区结构和连通分量的高亮等操作,帮助用户自主选择和探索感兴趣的结构。
3.3.2 投影视图
图4右上角。利用散点图将表征学习得到的节点向量在二维空间展示,点与点之间的距离表示节点之间的上下文结构相似性,此外,系统还提供了一套交互工具,可支持高亮采样节点、选择感兴趣的局部区域,为探索多重网络上下文结构特征提供便利。
3.3.3 评估视图
(1)图4左下角。以直方图的形式展示采样前后某些结构特征的分布情况,包括节点中介度、节点中心性、最短路径长度、局部聚类系数和社区节点数量。例如,可通过堆叠的直方图清晰直观地观察采样前后节点中介度的分布变化,从而估计采样后是否保留原始图中中介度较高的节点。
(2)图4右下角。以雷达图的形式展示所有采样算法在各项指标上的表现情况。每个径向轴代表一项度量指标,且与同一类别的指标轴相邻,而指标值由内向外表示从小到大。位于雷达图右上方的径向轴为ABD,沿顺时针方向排列的轴依次为ACC,CC,APL,SSC,SC,GCC和LCC,不同颜色的闭合连线代表不同的采样算法,可帮助用户快速对比和评估不同采样算法的有效性。
4 评 估
4.1 量化实验
表2 各采样算法在MOSS数据集中的评估结果
Table 2
采样算法 | ABD↑ | △ACC↓ | △APL↓ | CC↓ | SC↑ | SSC↓ | △LCC↓ | △GCC↓ |
---|---|---|---|---|---|---|---|---|
Our | 0.046 961 | 0.010 221 | 2.297 159 | 3.380 471 | 0.777 901 | 1.429 352 | 0.005 196 | 0.001 791 |
RN | 0.005 318 | 0.285 930 | 3.272 230 | 35.159 032 | 0.452 875 | 1.517 411 | 0.035 891 | 0.003 874 |
RE | 0.037 784 | 0.039 312 | 2.441 687 | 5.512 265 | 0.684 801 | 1.420 547 | 0.019 482 | 0.000 556 |
TIE | 0.036 419 | 0.051 711 | 2.493 230 | 5.341 204 | 0.682 788 | 1.407 531 | 0.035 130 | 0.001 108 |
SRW | 0.030 404 | 0.057 299 | 2.601 051 | 8.974 027 | 0.626 009 | 1.416 423 | 0.018 509 | 0.001 172 |
RJ | 0.007 105 | 0.270 322 | 3.252 558 | 33.216 703 | 0.443 592 | 1.511 981 | 0.035 891 | 0.003 874 |
ISRW | 0.032 846 | 0.044 754 | 2.360 106 | 5.980 326 | 0.653 282 | 1.405 518 | 0.035 656 | 0.000 194 |
表3 各采样算法在CELE数据集中的评估结果
Table 3
采样算法 | ABD↑ | △ACC↓ | △APL↓ | CC↓ | SC↑ | SSC↓ | △LCC↓ | △GCC↓ |
---|---|---|---|---|---|---|---|---|
Our | 0.043 351 | 0.083 769 | 4.159 635 | 10.173 904 | 0.808 134 | 1.428 093 | 0.162 431 | 0.022 517 |
RN | 0.016 103 | 0.204 642 | 4.346 191 | 18.462 014 | 0.675 309 | 1.470 793 | 0.212 950 | 0.090 168 |
RE | 0.027 193 | 0.158 657 | 4.168 920 | 13.559 312 | 0.710 273 | 1.453 103 | 0.163 088 | 0.050 793 |
TIE | 0.025 415 | 0.176 552 | 4.183 467 | 14.560 231 | 0.707 707 | 1.454 800 | 0.174 652 | 0.012 149 |
SRW | 0.023 110 | 0.163 137 | 4.126 947 | 13.170 032 | 0.725 736 | 1.452 183 | 0.151 335 | 0.026 816 |
RJ | 0.014 913 | 0.201 243 | 4.333 991 | 18.131 796 | 0.687 025 | 1.471 107 | 0.214 303 | 0.065 831 |
ISRW | 0.025 311 | 0.137 640 | 4.149 394 | 12.129 012 | 0.684 757 | 1.440 637 | 0.095 268 | 0.085 155 |
对比MOSS和CELE两套数据集的特点,发现MOSS数据集的节点数量为400,每一重图包含连边的数量均在500左右。而CELE数据集的节点数量为237,但每一重图包含连边的数量均在1 300左右,网络连接关系更为紧密和复杂。由以上量化结果可知,本文算法在面对具有不同结构特点的多重网络数据时,大部分指标更为优秀和稳定,但在某些指标上有所起伏。
分析可知,本文算法注重维持所有网络图的全局结构以及它们之间的关联和互通性,因此当节点连接相对稀疏时(如MOSS数据集),本文算法在APL指标上的优势更明显,但当节点连接普遍紧密时(如CELE数据集),其他算法也能相对较好地保持连通关系,一定程度上弱化了本文算法在该指标上的优势。
此外,本文算法忽略了局部区域之间连接关系的相对强弱,尤其在MOSS数据集中,区域之间的关联强弱变化明显,本文算法在采样后打破了原有节点间的强弱关联关系,从而改变了原有的社区结构稳定性(SSC)和全局聚类系数(GCC)。但在CELE数据集中,节点之间的连接普遍紧实,局部区域之间的连接关系都很强且相对稳定,弥补了本文算法在关系强弱保持上的不足,使得本文算法的这2项指标得到提升。
在实验结果中,只在某1~2项指标上排名第1的ISRW和SRW采样算法,均考虑局部特征,在保持社区结构稳定性和局部聚类系数方面有一定优势。但在更多的全局特征上,如反映重要节点保留的ABD和ACC指标、反映全局社区采样的SC指标和反映连通性的CC指标,本文算法均优于传统的图采样算法,能在更大程度上保留多重网络图的全局特征。
4.2 案例分析
在多重网络图采样可视分析系统中,加载MOSS数据集,将采样率设置为15%。从基于点、边和游走的算法中各选择一种经典的采样算法RN,RE和SRW,将其应用于第一重图,进一步应用于第二和第三重图,得到节点接近中心性分布直方图,如图5所示,从左到右依次为第一、二、三重图的采样结果。在行列相间位置的直方图中,横轴表示节点接近中心性经归一化后的度量值,纵轴表示落在相应区间的节点数量的对数值,从而缩小了柱状图之间的高度差,方便对比。
图5
图5
节点接近中心性分布直方图对比(MOSS)
Fig.5
Comparison of histogram distributions for node closeness centrality (MOSS)
由图5可知,相较传统算法,本文算法获得的采样结果涵盖原有直方图分布区间的范围较广,且采样柱状图的高度和大小比例与原始图更一致。例如,最后一行的RN采样算法效果最差,在每一重图上的深色柱状图较少,与原始网络图的节点接近中心性分布差异较大。而RE和SRW算法形成的直方图分布连续性较差,在中间某1~2段区间出现了缺失(右侧第三重图最明显),在左侧或右侧的空白区间易产生新的直方图,表现极不稳定。结合量化实验可知,本文算法不仅在节点接近中心性上的宏观统计表现最优,而且在每一重图上均能较好地保持分布特征。
图6为本文算法和在量化实验中表现相对较好的ISRW和TIES算法的对比,其中,(a)为在MOSS数据集中每一重图的力导向布局,(b) (c)和(d)依次为本文、ISRW和TIES算法在15%采样率下得到的可视化效果,(c)和(d)均为将对应算法应用于第一重网络,然后将采样结果推广至其他2重图得到的采样结果。所有结果均按第一、二、三重图的顺序从左到右依次展示,每一重图的节点颜色都映射为在该网络结构下的社区分类。
图6
最后利用多重网络图采样可视分析系统加载CELE数据集,将采样率设置为20%。选择RJ算法和TIES算法,并将其应用于第三重网络,进一步探索得到的采样结果在每一重图中的连通情况,见图7。其中,(a)展示了原始的多重网络图布局,(b) (c)和(d)依次为本文、RJ和TIES算法的连通分量高亮可视化效果,其中孤立节点用同一种颜色高亮展示,其余的连通分量用不同颜色的包围盒展示。
图7
由图7(b)知,本文算法在第一重图上表现稍差,出现了10个左右的孤立节点,在第二、三重图上均出现了5个左右的孤立节点,而在每个图中生成的主体连通子图,均能较好地还原初始网络的全局结构和整体特征。相比之下,图7(c)和(d)均在第三重图上表现较好,只有1~2个孤立节点,但在其余2重图上表现较差,除产生10多个孤立节点外,还形成了2~3个规模较大的连通子图,容易破坏用户对网络结构的整体认知。具体原因为RJ和TIES算法均以第三重图为参照进行采样,没有考虑其他重图,因此只有参照图维持了一定的结构特征,无法同时保持多重网络图的结构属性。本文算法能同步保持每一重图的结构关联,因此在多重网络图上的采样表现更稳定。
5 结 论
利用改进的自适应蓝噪声采样算法,从多重网络图表征学习空间中启发式地筛选节点,尽可能地实现多重网络图的特征保持。基于多重网络图采样可视分析系统的案例分析和量化实验均显示了本文算法在多重网络图采样中的有效性。下一步将在规模更大、网络图数量更多的多重网络数据集中进行采样效果实验,以分析和测试本文算法的可拓展性。此外,通过与领域专家密切讨论进一步改进多重网络图采样可视分析系统的视图设计和交互功能,提高系统的实用性。
http://dx.doi.org/10.3785/j.issn.1008-9497.2022.03.001
参考文献
Context-aware sampling of large networks via graph representation learning
[J]. ,
Sampling from large graphs with a reservoir
[C]//
Formation of multiple networks
[C]//
A sample-based approximate ranking method for large graphs
[C]//
Edge-based wedge sampling to estimate triangle counts in very large graphs
[C]//
A community-based sampling method using DPL for online social networks
[J]. ,
Connectivity-based spectral sampling for big complex network visualization
[C]//
Visual abstraction of large scale geospatial origin-destination movement data
[J]. ,
Origin-destination flow data smoothing and mapping
[J]. ,
Preserving minority structures in graph sampling
[J]. ,
Benefits of bias: Towards better characterization of network sampling
[C]//
Proxy graph: Visual quality metrics of big graph sampling
[J]. ,
Evaluation of graph sampling: A visualization perspective
[J]. ,
A visual evaluation study of graph sampling techniques
[J]. ,
Network representation learning: A survey
[J]. ,
Deepwalk: online learning of social representations
[C]//
Node2vec: Scalable feature learning for networks
[C]//
Joint t-SNE for comparable projections of multiple high-dimensional datasets
[J]. ,
Distributed random walks
[J]. ,
/
〈 | 〉 |