VIGOR-Interactive Visual Exploration of Graph Query Results

作者 Jackie Anxis 日期 2018-01-07
VIGOR-Interactive Visual Exploration of Graph Query Results

贡献点

  1. 基于模板的交互探索。
    • bottom-up sensemaking:自底向上的意会,从一个特定的结果开始,然后放开限制,找到其他相似结果。
    • top-down sensemaking:自顶向下的意会,从一个结构开始,慢慢加入条件,限制结果。
  2. 通过特征感知子图(feature-aware subgraph)结果进行嵌入和聚类。VIGOR提供了一个自顶向下的高层次的结果overview。作者介绍了一个算法,能够根据节点特征和结构化相似度来对结果进行聚类,然后将他们嵌入到一个低维度的表示中。
  3. 一个集成了多个协调视图的系统。多个相互关联的视图。
  4. 真实世界应用,可以发现网络安全的盲点。

界面概览

  1. Exemplar View:用户的图查询结果的语义表示,可以快速过滤(A)
  2. Fusion Graph:一个查询结果子图的导出图(B),能清晰的知道哪些节点频繁出现以及和哪些节点有关系。
  3. Subgraph Embedding view:对所有查询结果做了一个总结,将每一次查询结果都放进一个glyph中,对它们进行聚类。
  4. feature explorer view:结果包含的节点类型分布的一个总结。

核心设计

  • 利用示例:自底向上的探索

    • 可调整的可视化,对类型化的查询输入进行快速错误检查
    • 容易看到,查询结果中,特定的节点有多少
    • 从熟悉的结果开始,放开条件限制,以便找到其他相似答案
    • 一个筛选机制,增加节点值约束,以便快速筛选
  • 自顶向下的探索:

    • 高级概述(子图嵌入)作者将结果表示为一个方形的glyph(区别于节点),以便绘图。将相似的结果聚类成concave hulls。

  • 对结果聚类进行以特征为核心的释义(Feature-centric Sensemaking for Result Clusters)。

    • 通常,分析者只能对一部分潜在特征进行约束来进行查询,而其余特征则可以自由变化经常会形成pattern。特征分布和节点特征分布可以用来比较结果,fusion graph view的结果会被总结为分布图。
  • 对多个视图进行协同工作:主要是说多个视图之间的同步联动。

方法和架构

将子图结果(某种查询结果)如何嵌入成一个2D点,也是一个降维问题。需要以下两点:(1)将整个子图转化成一个高维向量;(2)距离保护降维技术(distance-preserving reduction techniques)

子图嵌入

步骤:

  • 特征抽取:包括拓扑特征跟节点特征。

    特征抽取过程有点类似于《Reducingsnapshots to points: A visual analytics approach to dynamic networkexploration》和《Netsim-ile: A scalable approach to size-independent network similarity》。

    其中,节点特征会在VIGOR系统初始化的时候由用户挑选。

    节点i的egonet的几个重要的结构特征:

    • 节点度数
    • egonet edges(该egonet的内部边)
    • Egonet邻接点(跟该egonet相邻的节点)
    • 聚类系数(也就是密度)
  • 向量化:将共同特征可以合成一个特征

    每个节点现在都有四个结构特征。

    但不同的节点有不同的节点特征,所以之抽取节点之间共同的特征

  • 聚合并标准化到signature:进行标准化

    利用mean,variance,skewness以及kurtosis来对向量制作signature。

  • 降维和聚类:降维并投影到二维平面

    降维:PCA(快速)/MDS/t-SNE,后两者可以自己挑选距离度量函数,这里用了Canberra distance,因为它对靠近0的变化比较敏感。

    聚类:DBSCAN/OPTICS,选取了后者,后者对有不同密度的聚类有更好的表现。