VIGOR: 交互式探索图查询结果(Interactive Visual Exploration of Graph Query Results)

当领域专家需要寻找大图中满足特定条件的子图时,图查询操作是一种重要的方法。比如在金融交易网络,分析者想要发现洗钱行为,可以查询商人和银行家构成的环状网络。尽管有许多工作研究如何构建查询语句、数据库管理、图匹配算法,但是少有工作帮助分析者理解子图的结构以及属性特征。这项工作[1]设计了一个原创可视分析系统,帮助用户探索、理解子图查询的结果。

系统有4个主要视图,Exemplar View, Fusion Graph, Subgraph Embedding, Feature Explorer。4个视图互相联动,帮助用户完成分析流程。

图1 VIGOR系统界面

首先,用户通过Cyper[2]输入希望的查询结果,在Exemplar View(图1-A)中,会可视化查询的子图结果,用户可以通过右击的方式对节点的属性进一步限制,比如限制其中一个作者节点是Shixia Liu。可以看出图1-A查询的是Shixia Liu与其合作者合作发表过两篇论文,且分别发表在vast和kdd会议上的子图。

对于用户的查询,往往存在大量的返回结果。Fusion Graph中(图1-B)通过合并相同节点的方式总结了所有的查询结果,构建了一个Super Graph。通过点击节点可以查看节点的具体信息(图1-D)。

为了帮助用户分析返回子图结果的差异性,Subgraph Embedding中每个点代表一个满足查询条件的子图,对投影结果利用空间聚类的方式得到不同的聚类结果,用户可以选择不同的聚类结果,在Fusion Graph 中进一步分析,并且可以通过打标签的方式标注不同的聚类结果。

在Feature Explore(图1-E)中,用户可以分析比较不同聚类结果的特征,比如所有子图中作者节点论文数量的分布,论文节点随时间的分布等。

构建上述系统的最大挑战在于如何将子图矢量化投影到2D平面,同时能表现出子图的结构特征和节点的属性特征。

图2 子图投影Pipeline

如图2位子图投影的Pipeline。

Feature Extraction。计算每个子图上节点的结构特征,直接从子图上计算这些特征没有意义,因为返回的子图结构完全一致,所以同类别节点的结构特征完全相同。这里的计算方式是在原始的图中计算每个节点的结构特征,包括节点的度数,聚类系数等。对于节点属性特征,不同类型的节点也不相同,比如作者节点计算合作者数量,而对于会议节点计算接收论文的数量。

Vectorize。计算得到每个节点的属性和结构特征后,按照行代表属性,列代表节点的方式排列。

Aggregate to Signature。对于每个属性,计算所有节点值的均值、二、三、四阶矩,这四个属性从大小、波动、对称性、长尾性反应了属性值的分布特征。然后将计算的属性值结果排列成一行,实现矢量化。这样做从整体上比较了子图的差异性,相比直接排列节点的属性值减少了单一节点对于整体的影响。

Reduce & Cluster。矢量化后,每个子图变成了一个高维向量,可以利用高维投影的方式分析子图,用户可以选择不同的投影方式比如PCA,MDS,t-SNE。为了进一步得到聚类结果,这里使用了OPTICS算法对投影结果空间划分。

所以,该系统通过交互式构建查询子图、通过投影总结查询结果、多个视图协同的方式分析子图查询结果,领先已有的分析工具。其采用的投影方式有参考价值。

参考:

[1] Robert Pienta, Fred Hohman, Alex Endert, Acar Tamersoy, Kevin Roundy, Chris Gates, Shamkant Navathe, Duen Horng Chau. VIGOR: Interactive Visual Exploration of Graph Query Results. IEEE Transactions on Visualization and Computer Graphics (VAST’17), 24(1):215-225, 2018.

[2] Cypher: https://neo4j.com/developer/cypher/

 

 

 

 

评论关闭。