Refinery:通过关联浏览对巨大异构网络进行探索 (Refinery: Visual Exploration of Large, Heterogeneous Networks through Associative Browsing)

电子书合集(Electronic Collection)是一种互联网时代常见的数据形式。例如,计算机领域各类会议期刊的论文合集就构成了这样一种数据集。在这类数据中进行导航(navigation)通常需要有不同的策略。关联浏览(Associate Browsing)用来指代一类以特定主题或一般性的知识获取为目的、依据环境线索不断迭代、最终达到目标的探索策略。本文提出了Refinery,一个通过关联浏览对巨大异构网络进行探索的可视化系统。

在介绍Refinery这个可视化系统前,作者首先对已有相关工作进行了回顾,从中总结了支持关联浏览的若干条准则。由于篇幅关系,笔者无法重现回顾过程,而只将各条准则列出:

G1:支持异构、动态合集数据间的导航;
G2:在表示搜索意图(search intent)时,能平衡其简介性与表达力;
G3:能通过与用户的交互迭代更新搜索意图;
G4:通过展示上下文线索来帮助使用者对感知了解数据,从中有所发现。

表1:三类系统对各条准则的支持情况,+,-,♢分别表示支持、不支持以及混合的情况

表1:三类系统对各条准则的支持情况,+,-,♢分别表示支持、不支持以及混合的情况

之后,作者将已有的相关系统分为三类,并依次判断各类系统对这几条准则的支持情况,如表1所示。可以看到已有的系统基本无法支持对异构数据的探索(G1),同时在搜索意图的表达(G2)和上下文信息的呈现(G4)上都有些许不足。

作者根据提出的四条准则,以及对已有系统中的见解,提出了Refinery系统,通过关联浏览对巨大异构网络进行探索。为了展示这个系统的使用,作者假想了如下一个应用场景:

Mae回忆起她最近在参加一个与”ethics”(伦理学)相关的人机交互领域的会议时,有一个十分有趣的演讲。但是Mae已经不记得演讲的题目或者作者了,只记得那篇论文获得了Honorable Mention。她现在想找到那篇论文,并找到相关的可能感兴趣的文章。

图1:Refinery系统的用户界面

图1:Refinery系统的用户界面

图1展示了Refinery的使用界面。Mae首先在搜索框中输入关键字“ethics”,从提示的相关标签中选择“关键字”这一类别下的“ethics”。接着用户继续添加“奖项”下的“Honorable Mention”(图2(a))。

图2:(a)搜索框中允许用户输入任意文本,然后选择项目加入到搜索项中;(b) 侧边栏中显示推荐搜索项目,用户可以对其赞或踩,来调节搜索项。

图2:(a)搜索框中允许用户输入任意文本,然后选择项目加入到搜索项中;(b) 侧边栏中显示推荐搜索项目,用户可以对其赞或踩,来调节搜索项。

Mae输入了搜索词后,侧边栏会显示这些搜索项,同时会有推荐项目展示,它们按类别进行分组,并根据相关性排序。在浏览了“关键字”类别下的项目后,Mae赞(upvote)了”Design”关键字,同时踩(downvote)了关键字“End of Life”“E-Goverment”,因为Mae想到那篇论文并不与他们相关。每当用户通过赞或踩更新搜索选项后,推荐项目的次序也将更新(图2(b))。之后,在图视图中,最相关的一些项目以及它们之间的联系被可视化出来。Mae可以通过移动鼠标到每一个项目上来浏览各自的信息(图1)。Mae单击了“出版物”类别下的“Categorised …”并阅读了其摘要,发现它并不是所要寻找的论文,但是已经十分接近了,于是她将这篇论文添加到了出版物中。在这样做之后,“Session”类别里的“CHI2013: Ethics in HCI”出现在了图里面,她也将其加入到搜索项目中。

图3:列表视图中根据相关性分数对各项目进行排序展示,用户可以通过侧边栏按钮选择隐藏或显示特定类别的项目。

图3:列表视图中根据相关性分数对各项目进行排序展示,用户可以通过侧边栏按钮选择隐藏或显示特定类别的项目。

至此,Mae觉得她已经十分接近所要寻找的论文了,因此她直接切换到列表视图,对所有相关项进行浏览,而这些项目都已经按相关性大小进行了排序。Mae在侧边栏头部按键将“出版物”类别以外的类别都隐藏,只剩下相关的论文。其中的第三篇”Benevolent …“正是她想要寻找的论文。Mae浏览其信息,发现它并没有使用最开始的关键字(ethics),尽管两者十分相关。在这个列表里面,Mae也发现了许多紧密相关的其他论文。

上文描述了使用Refinery进行关联浏览的一次操作流程。接下来,我们来看它的具体技术细节,主要包含两个方面:一是如何对数据进行建模,二是在指定搜索项后,如何从异构网络中找到最相关的项目。

许多对论文合集进行可视化的工作通常会把其当作为带有多属性的同构网络,比如论文引用网络,或者是作者合作网络。但在Refinery中,论文合集被当作了异构网络。其中,能作为结点存在的不仅仅是论文或是作者,会议名称、Session名称、关键字、奖项、联系方式等均可作为结点。结点间如果有关系,则连边,边的权值表示两者关系的紧密程度。作者这里根据经验设置了各类边的权值大小,例如论文——作者边的权值就要大于论文——会议边的全职。

而所谓的搜索过程,实际上是在异构图中选取了若干搜索项对应的结点,然后根据边权距离等因素选取最相关的若干项目。作者这里采用了随机走动(Random Walk)算法。作者首先根据已有的图建立一个概率图,这个概率图中的边和结点均和原图对应,但边的权值表示的是从边的一个顶点到另一顶点的概率,通过图4的公式计算,其中pH表示的是一个”停止“概率。在这个概率图中,我们首先考虑只有一个搜索项(结点)的情况。这个结点自身的相关性设为1,而对于其他节点,我们计算在概率图上从起始结点到达它们的概率,用这个概率表示其相关性分数。这里的计算直接使用随机走动算法即可。当具有多个搜索项时,根据赞和踩的情况,我们将相关性分数相加或相减,得到一个总的相关性分数,就是最终的结果。Refinery中对于随机走动算法在异构网络中的应用也是本文的贡献之一。

图4:概率图中边概率的计算

图4:概率图中边概率的计算

之后,作者通过用户调研的方式来验证Refinery的有效性。共有12名(7女5男)科研人员参与了调研,每个人至少对数据集中的三项会议比较熟悉。参与调研的人首先会接受系统的简单介绍,然后被要求进行15分钟的数据探索,最后被要求填写一张问卷调查,并接受10分钟的采访。问卷结果表明所有参与者都能积极使用系统,而系统所特有的异构搜索项、踩功能等均有广泛的使用。采访中,有许多参与者表明能在数据探索中收到许多有用的推荐项目,这些项目可能之前并没有太多关注,但其实却十分相关。

总起来看,这篇论文的贡献可以分为三点。一、提出了Refinery系统,通过关联浏览对巨大异构网络进行探索;二、总结了针对关联浏览的可视化设计应该考虑四点准则;三、将随机走动算法创新性地推广到了异构网络中相关性的计算。我们可以看到异构网络本身在同构网络的基础上变得更加复杂,但也更能适应于人类思考问题的关联模式,对其的可视化问题仍有许多提升的空间。

[1] Sanjay Kairam, Nathalie Henry Riche, Steven M. Drucker, Roland Fernandez, Jeffrey Heer, “Refinery: Visual Exploration of Large, Heterogeneous Networks through Associative Browsing”, EuroVis 2015: Eurographics Conference on Visualization.

评论关闭。