除了用于Google地图的ETA预测,GNN还可以做什么?

除了用于Google地图的ETA预测,GNN还可以做什么?

  • 发布时间:2021-09-20 07:00
  • 访问量:

【概要描述】近年来,新兴起的图神经网络在很多应用领域都取得了非常出色的表现,如今年用于Google 地图的到达时间估计,在纽约、洛杉矶、东京、新加坡等国际大都市都获得了很大的提升,该结果对其他地区也具有通用性。

除了用于Google地图的ETA预测,GNN还可以做什么?

【概要描述】近年来,新兴起的图神经网络在很多应用领域都取得了非常出色的表现,如今年用于Google 地图的到达时间估计,在纽约、洛杉矶、东京、新加坡等国际大都市都获得了很大的提升,该结果对其他地区也具有通用性。

  • 分类:研究院
  • 作者:壁仞科技研究院
  • 来源:
  • 发布时间:2021-09-20 07:00
  • 访问量:
详情

摘要

 

近年来,新兴起的图神经网络在很多应用领域都取得了非常出色的表现,如今年用于Google 地图的到达时间估计(Estimated Time of Arrival,ETA),在纽约、洛杉矶、东京、新加坡等国际大都市都获得了很大的提升,该结果对其他地区也具有通用性[1]。图神经网络以图结构为核心组成部分,这与结构因果模型有着相似的结构形式。鉴于此,DeepMind最新的研究工作[2]以图神经网络为网络结构,设计了一种基于图神经网络的变分图自编码器,用于近似Pearl因果层次结构中的因果计算问题。与以往用因果推断思想提升深度学习性能不同的是,该研究工作在图神经结构与结构因果模型之间建立了转换机制,为Pearl因果层次结构中的因果计算提供了一种新型计算方法和思路,是深度学习在因果推断领域应用的一项开创性的尝试性工作。

 

结构因果模型(SCM)

 

结构因果模型(Structural Causal Model,SCM)用于描述现实世界关联特征及其相互作用,是一种能够形式化表述数据背后因果假设的方法。结构因果模型含有两个变量集以及一组函数

 

 

即函数根据模型中其他变量的值给变量赋值。若存在于的定义域中,则变量是变量的直接原因。中的变量称为外生变量,属于模型的外部,不必解释其变化的原因。中的变量为内生变量,模型中的每一个内生变量都至少有一个外生变量作为直接原因。

 

图1:SCM实例和Pearl Causal Hierarchy

 

每一个结构因果模型都对应一个图模型中的每个变量都表示为一个节点,对于变量,如果的定义域中含有变量,那么在中,会有一条从的有向边。同时,通过实例化外生变量,也可以生成包含所有内生变量的数据,因此SCM也是一种数据生成模型。在SCM中,可以回答Pearl因果层次结构(Pearl Causal Hierarchy,PCH)关于基于观察数据(L1)、干预(L2)以及反事实(L3)三个层次的因果计算, 如图1所示。在PCH因果计算中,其核心思想是需要解决干预(L2)的问题,这是回答反事实问题(L3)的基础。在SCM中,干预主要体现在do-演算操作,即将干预变量强制设置为某一固定值,使得干预变量不会随其他变量影响。下面以一个例子来说明do-演算在SCM中的计算过程。

Example:考虑饮食(D)对血压(B)的影响,表示高纤维的饮食习惯,表示高血压,假设给定的SCM为M,外生变量,内生变量以及函数

 

 

其中⊕是XOR逻辑操作,该SCM相对应的图结构如图2所示。

 

图2:Example的图结构

 

此外,因为所有变量都取二元值,因此我们也可以枚举推演出其真值表,如表1所示。 

 

表1:Example的真值表

 

现在我们对变量D进行干预,设置为,那么根据表1我们可以计算的概率,就是将表1中所有蓝色行的数字求和,即

 

 

图结构是SCM模型的一个重要组成部分,能直观地表达变量之间的交互信息。但是在实际问题中,这种交互关系的确定往往严重依赖于领域专家知识,无可避免地引入了人为误差。个人认为,GNN作为深度学习方法的衍生体,能有效地近似任何函数,是模拟SCM中概率分布的一个可行方法。

 

基于SCM的图神经网络干预

 

Do-演算也可在图上以更直观的方式呈现。当对变量进行干预时,意味着削弱了该变量响应其他变量而变化的自然趋势。在SCM对应的图结构表示上,就需要删除指向该变量的所有边,如图3中右边红色锤子对应的边。

 

 

图3:干预变量Y的图结构表示

 

按照上述思想,文[2]对GNN也定义了类似的干预操作,主要体现在GNN的消息传递(message-passing)中。在标准的GNN信息聚合操作中,图中节点通过聚合其父节点的信息完成当前节点的信息更新,如式(2)所示。但是在干预的GNN中,如果当前节点为干预变量,则忽略其父节点的信息(将替换为),如式(3)所示。

 

 

干预变分图自编码器

 

在上述图神经网络(Graph Neural Networks, GNN)的do-演算基础上,文[2]定义了用于近似PCH因果推断的干预变分图自编码器(Interventional Variational Graph Auto-Encoder, iVGAE),如图4所示。

 

图4:iVGAE结构图

 

乍一看,图4上部分描述的是标准变分图自编码器模型结构。但为了能近似SCM在L2层次的因果推断,文[2]将编码器函数、解码器函数都设计为以给定SCM为图结构的GNN的聚合函数。在进行L2层次因果推理时,根据给定的查询变量和干预变量,动态地对图结构进行do-演算调整,即忽略/不计算来自干预变量的父节点的信息,而模型的输出可近似成该干预变量下的概率分布,即完成L2层次的因果计算。在训练iVGAE,主要采用了变分方法,其中目标函数也需要考虑干预变量。

 

思考

 

与以往用因果推断改进深度学习方法效果不同的是,文[2]侧重于用基于GNN的深度学习来完成SCM中的PCH因果计算,侧重于基于观察数据(L1)、干预的推断(L2)。由于图神经网络与SCM都是基于图结构,一种简单、直接的方法就是在给定SCM图结构上,设计一种合适参数转化机制,以确保SCM和深度学习模型表达同个分布,这也是文[2]的主要设计思路。同时,文[2]也指出,SCM需要对每个变量都定义各自相应的映射函数。相反的,在iVGAE中,可以找到单个共享聚合函数,用于聚合图中所有节点的消息。然而将单个聚合函数转换成多个结构方程的优化过程是异常困难,而这也是实现反事实推理需要解决的问题,这也是文[2]没有考虑L3层次推理的一个原因。

虽然文[2]、[3]都试图在SCM与深度学习之间建立联系,目前主要侧重于将深度学习看成一种近似方法来完成PCH中的因果计算。当然,对PCH因果计算的支持是实现因果推断的重要内容,也可以看成深度学习在因果表达上迈出了重要的一步。不同方法有不同程度的兼容性,如文[2]不支持L3层次的计算。这些研究也引出了更深层次的问题,如基于神经网络的因果计算优势体现在哪里,例如,推理计算是否更高效?文中尚未提供明确的答案。

除了近似分布,也有将深度学习用于因果发现中的研究工作,如文[4]中提出了连续优化(continuous optimization)的思想,重新定义了因果图发现的一种求解方式。与其在图空间进行搜索,转化为寻找一个包含图结构的邻接矩阵的函数,从而可以使用深度学习方法进行梯度下降求解。当然,这与文[2]有着不同的研究目标。不可否认,如何使得深度学习和因果推断相得益彰,是一个非常值得探索的方向,相信在不久的将来两者能碰触更多的火花。

最后,个人觉得文[2]的亮点在于采用现流行的GNN模型来模拟SCM的数据生成机制,虽然这种数据生成过程是一种黑盒子方法(这也是深度学习广为争议的一个特征),但如果仅从数据模拟效果的角度来看,未尝不可?

 

由于水平有限,文中存在不足的地方,请各位读者批评指正,也欢迎大家参与我们的讨论。

 

参考文献

 

[1] Austin Derrow-Pinion,  Jennifer She,  David Wong, et al. ETA Predictionwith Graph Neural Networks in Google Maps 2021

[2] Matej Zecevi,Devendra Singh Dhami, Petar Velickovi,Kristian Kersting. Relating Graph Neural Networks to Structural Causal Models 2021

[3] Kevin Xia, Kai-Zhan Lee, Yoshua Bengio, Elias Bareinboim. The Causal-Neural Connection: Expressiveness, Learnability, and inference 2021 

[4] Xun Zheng, Bryon Aragam, Pradeep Ravikumar, Eric P Xing. Dags with no tears: continuous optimization for structure learning 2018 

近期文章

流体力学与物理导引神经网络

流体力学与物理导引神经网络

现代科学中众多复杂的关键应用依赖着对流体运动的精确预测。然而,由于流体力学方程数值求解的复杂性,基于传统数值方法的高分辨率长周期数值模拟运算量大且难以保证数值稳定性。本文将深入介绍PINN方法在流体计算中的应用并分析其与传统数值方法的差别。
2021-10-25
物理导引神经网络方法分析

物理导引神经网络方法分析

随着GPU能力的提升,支撑深度学习的软硬件生态得到了快速发展。通过深度学习来解决科学计算问题成了一种趋势,其中用深度学习来求解偏微分方程的方法也逐渐兴起。尤其引人注意的是一种称为物理导引神经网络的方法,其为科学计算领域注入了新的活力。
2021-10-18

联系我们

这是描述信息

招贤纳士

公众号二维码
这是描述信息

 版权所有   ©   上海壁仞科技有限公司   |    沪ICP备19047354号