• 论文:Origraph: Interactive Network Wrangling
  • 作者:Alex Bigelow, Carolina Nobre, Miriah Meyer, Alexander Lex
  • 发表:VIS 2019 ( Conference Paper)

作者

  1. Alex Bigelow

    • University of Utah (2014-2019 PhD)
    • University of Arizona, Postdoc
    • 兴趣:
      • Graph (network)
      • Visualization authoring
      • Data wrangling

1569217637977

  1. Carolina Nobre

    • University of Utah (2015- PhD)
    • 兴趣:
      • Graph (network)
      • Data wrangling

1569217666036

  1. Miriah Meyer
  • University of Utah (associate prof)
  • 宾大天文系毕业
  • 犹他大学计算机博士
  • 哈佛博后研究员

1569217472666

  1. Alexander Lex
  • 本硕博:Graz University of Technology
  • 哈佛博后研究员(2012-2015)
  • 哈佛医学院访问学者(2011)

1569217477125

介绍

文章的动机是关于数据整理(Data Wrangling)相关的,主要包括三个方面:

  • 数据清洗
  • 数据集的合并
  • 数据变换

但是迄今为止,没有专门应对图数据的数据整理工具。虽然现有一部分进行图建模(graph modeling)的工具,但是他们或是聚焦于创建一个初始图模型,而不是重建该图模型,又或是一种编程语言,学习曲线太过陡峭。

于是作者提出了 Origraph,一种用于图数据建模&重建的工具。他们的贡献点一共有三个:

  1. 提出了一个工具:Origraph
  2. 提出了关于图数据整理相关操作的讨论
  3. 两个复杂网络建模的案例学习(use case)

下面是他们的 fast forward 视频:https://www.youtube.com/watch?v=bxjDvq6kjeo

相关工作

Graph Editing

图编辑的工作一般假设输入的图都是整理好的,相关的工具有如下几种:

  • Cytoscape

  • Gephi

  • Graphviz

Wrangling Tabular Data

  • 商业化软件有:

    • Google Refine (OpenRefine)
    • Data Wrangler (Trifacta Wrangler)
    • Microsoft Excel
  • 与图可视化相关的有:

    • D-Dupe: An Interactive Tool for Entity Resolution in Social Networks

      利用图可视化来检测数据中的潜在重复值(potential duplicates)

      1569218007041

    • Schema Mapper: Visualization of Mappings Between Schemas

      用图可视化来可视化两种不同数据模式之间的映射

      1569218035108

    • GraphCuisine: Interactive Random Graph Generation with Evolutionary Algorithms

      1569218087740

    • NodeXL: 一个 excel 的插件

      1569218095841

编程脚本(Scripting for Graph Wrangling)

  • 编程库

    • NetworkX
    • Mully: An R Package to Create, Modify and Visualize Multilayered Graphs.
  • 图数据库

    • Neo4j
    • OrientDB
    • GraphDB

图建模(Network Modeling)

图建模工具的主要目的是,从表格型数据构建图数据。

  • 商业系统

    • TouchGraph Navigator
    • Centrifuge
  • Orion: A system for modeling, transformation and visualization of multidimensional heterogeneous networks

    Jeffrey Heer 在 2014 年发表于 Information Visualization 的论文,其目的是交互性的提供一个图建模的方法,并且提供了一些图数据的可视化和交互。

    1569218325153

  • Ploceus: Modeling, visualizing, and analyzing tabular data as networks

    Zhicheng Liu, Shamkant B Navathe and John T Stasko 等人在 2014 年发表于 Information Visualization 的论文,与上面的论文类似,也是做图建模的。

    1569218372781

  • Graphiti: Interactive Specification of Attribute-based Edges for Network Modeling and Visualization

    ArjunSrinivasan, Hyunwoo Park, Alex Endert,Rahul C. Basole 等人发表于 VAST2017 年的论文,它的侧重点在于如何构建点与点之间的边。当用户确定用某种关系作为构建边的关系时,会应用于全局。

Graph Operation

作者通过对以往的 survey、工作、系统等总结的一系列任务,以及和领域专家的合作经验等,还进行了一些非正式的任务分析,总结了一套针对图数据整理的操作。作者把这些操作分成了三大类:

  • 模型操作 (modeling operations):引入新的类,以修改图模型、图拓扑结构
  • 个体操作 (item operations):引入/删除个体,以修改图拓扑结构

  • 属性操作 (attribute operations):管理属性/增加新属性

模型操作 (modeling operations)

模型操作主要有以下几种:

  1. 连接/断开 (connecting or disconnecting)

    指定两类节点之间应该通过什么关系连接;

  2. 属性提升 (promoting attributes)

    把某个属性提炼,单独形成节点。下图中就把类型(genre)这个属性提炼出来作为节点。

    1569219069513

  3. 切面 (faceting)

    把某种属性当成类。下图把类型这个属性当成类。

    1569219094243

  4. 点边转化 (converting between nodes and edges)

    把点转化成边,或者把边转化成点。下图把电影节点转化为了边。

    1569219133943

  5. 边投影 (edge projection)

    可以通过某种路径,在两类不相连的节点之间构建边。比如下图通过演员-角色-电影-出品公司的关系,把演员和出品公司连在了一起(黄色边)

    1569219190612

  6. 超节点 (creating supernodes)

    把某些点之间的共同点提炼出来作为一个新的超节点,代表这些点。

    1569219240359

  7. 卷边 (rolling up edges)

    多重边的聚合。

个体操作 (item operations)

个体操作主要有两种:

  • 属性过滤 (filtering by attributes)

    根据属性值,移除特定的节点/边

  • 连通性过滤 (connectivity-based filtering)

    利用网络的连通性来过滤节点/边。ex. 过滤所有没有出演过任何电影的演员,身价却超过 100 万的。

属性操作 (attribute operations)

  • 类内属性推导 (deriving in-class attributes)

    ex. 出生日期,死亡日期 推导出 年纪

  • 连通性相关属性推导 (connectivity-based attribute derivation)

    通过相连的类来推导节点/边的属性

    1569219416375

  • 改变边的方向性 (changing edge directionality)

    有向边的转换,或者把有向边转化为无向边。

系统设计

1569219457269

其中包含三大 View:

  • Network Model View: 展示节点/边之间的关系,

  • Attribute View: 展示节点/边的属性,执行属性相关操作

  • Network Sample View: 展现网络现状的 preview

网络模型视图(Network Model View)

1569219498059

节点用圆形编码,类别用菱形编码,数量用数字表示,边的一节保持水平(保证 label 可读)。

它提供了包括以下几种的操作:

  • 连接/断开 (connecting or disconnecting)
  • 点边转化 (converting between nodes and edges)
  • 边投影 (edge projection)
  • 改变边的方向性 (changing edge directionality)

属性视图 (Attribute View)

1569219601816

提供了很多关于属性的操作,包括:

  • 属性提升 (promoting attributes)
  • 切面 (faceting)
  • 属性过滤 (filtering by attributes)
  • 连通性过滤 (connectivity-based filtering)
  • 类内属性推导 (deriving in-class attributes)
  • 连通性相关属性推导 (connectivity-based attribute derivation)

网络采样视图 (Network Sample View)

用采样后的网络,展示当前状态。其中采用了深度优先采样方法:A Survey and Taxonomy of Graph Sampling。作者对该方法做了一些改进,平衡了不同类之间的采样,用户可以自由选择节点/边作为种子。

操作视图 (Operation Views)

Connection Support Interface

主要用于提供连接操作。

1569219995252

它会计算一个分数,来推荐哪些关系相连可以作为边。

这个分数,会让那种有一对一匹配的关系有更高的分数。当如果两类节点能通过某种关系进行 1 对 1 匹配,没有多也没有少时,这个关系的 score 将会是 2;而如果没有任何的匹配,这种关系的 score 将会是-2。

Path-Based Operations

1569220095085

主要提供以下操作:

  • 边投影 (edge projection)
  • 连通性过滤 (connectivity-based filtering)
  • 连通性相关属性推导 (connectivity-based attribute derivation)


Questions & Discussion: ✉️ panjiacheng@zju.edu.cn