本期文章将为大家分享飞桨社区开发者肖淙曦、周景博发表于数据挖掘顶会 KDD2023 的论文《Spatial Heterophily Aware Graph Neural Networks》。
肖淙曦
肖淙曦，百度研究院商业智能实验室钻研实习生，中国科学技术大学在读博士生，次要从事时空数据挖掘和图深度学习相干的钻研工作。基于飞桨实现多篇论文，发表于 KDD、AAAI 等计算机顶级学术会议。
周景博
周景博，飞桨开发者高级技术专家（高级 PPDE），现任百度研究院商业智能实验室资深研究员，次要从事数据挖掘和机器学习相干的钻研和利用工作，包含时空大数据、深度几何学习、常识图谱和 AI 辅助药物设计等，PaddleSpatial 技术负责人，基于飞桨实现论文多篇，发表于 KDD、AAAI、TKDE 等计算机顶级会议和期刊上。
背景介绍
近年来，图神经网络（Graph Neural Networks, GNNs）被广泛应用于智能城市计算。思考到城市是一个简单的零碎，城市实体之间存在各种分割，许多钻研工作将城市建模为一个城市图（Urban Graph），其中图上的节点示意某种城市实体，边示意实体间的某种关联，并采纳图神经网络对城市图进行学习，以解决城市中各种上游工作。
然而，与个别的图不同，城市图常常具备空间异配性（Spatial Heterophily），该特点限度了个别图神经网络的性能。首先，图的异配性（Heterophily）和同配性（Homophily）是两个绝对的概念。个别的 GNN 模型假如图数据存在较好的同配性，相邻节点具备类似的特点。而因为不同性能城市实体间的关联简单，城市图往往具备异配性，即相连的节点可能不类似。比方，住宅区和工作场合之前常常存在人口流动关系，但显然这两种区域存在微小差别。个别的同配图神经网络（Homophilic GNNs）趋向于为相邻节点产生类似的示意，可能会疏忽重要的差别信息，限度了其在具备异配性的城市图上的有效性。
在本文中，咱们进一步发现城市图的街坊异配通常还呈现出肯定的空间多样性，咱们称这种特点为空间异配性（Spatial Heterophily）。对个别的异配图，街坊与核心节点具备差别；而在城市图上，位于不同地理位置的街坊，对核心节点的差别散布是不同的，而不是平均的，即差别存在空间多样性（Spatial Diversity）。本文设计了一个空间多样性评分指标（Spatial Diversity Score）来形容城市图的空间异配性。如图 1（a）所示，城市图可能取得较高的得分，阐明图上的街坊差别散布存在空间多样性，即空间异配性。
图 1 空间异配性剖析
即便局部研究者曾经开始钻研图的异配性问题，然而现有的异配图神经网络（Heterophilic GNNs）次要钻研街坊差别无限的异配图，比方假如异配图上仅有两种类型的节点，而不能思考城市图上街坊差别散布的空间多样性。如图 1（b）所示，咱们通过试验比拟了不同 GNN 模型在一系列人工合成图上的性能。当逐步加图空间异配性（得分逐步升高），现有异配图神经网络无奈放弃低劣的性能。所以，设计一个可能解决空间异配性的图神经网络，更好地在城市图上进行示意学习，是非常有意义的。
为解决这一问题，本文提出了一个空间异配性感知图神经网络（Spatial Heterophily Aware Graph Neural Network，SHGNN），模型构造如图 2 所示。该模型的设计受到了地理学第一定律“任何事物都相干，但相近的事物关联更严密”的启发，即在城市中，咱们能察看到空间地位相近的城市实体通常具备类似的特点。基于这一个性，本办法的核心思想是依据空间地位进行邻域划分，将空间相近的街坊分到一组，使得组内街坊与核心节点之间具备相近的差别散布，以够缓解组内街坊异配的多样性。在此基础上，咱们设计可能同时建模差别信息的图学习算法，对每个分组独自解决，分而治之地解决城市图的空间异配性。
在该工作中，咱们基于飞桨实现了模型的搭建与训练。 在输出数据方面，本文应用飞桨的图学习框架 Paddle Graph Learning (PGL) 对城市图进行高效的构建与存储，包含节点之间的连贯关系、节点空间坐标，以及节点间的空间间隔等信息。在模型方面，本文首先联合 PGL 的子图提取接口与消息传递机制，便捷地实现了对不同空间地位的街坊别离进行音讯聚合的操作；接着，基于飞桨的张量矩阵运算，实现了城市图上共性信息和差别信息的交互，加强城市图的示意学习。 基于飞桨动态图框架对模型进行端到端训练后，本办法在不同的上游工作中体现出良好的性能。
办法框架
图 2 空间异配感知的图神经网络
本文提出的空间异配性感知图神经网络次要由两个模块组成，别离为旋转 - 伸缩空间感知邻域聚合（Rotation-Scaling Spatial Aggregation），以及异配感知的空间交互（Heterophily-Sensitive Spatial Interaction）。
旋转 - 伸缩空间感知邻域聚合
旋转 - 伸缩空间感知邻域聚合的首先对街坊节点进行划分，将地位相近的街坊调配到同一个空间组（Spatial Group），使得组内街坊对核心节点具备相近的差别散布，以缓解差别散布的多样性。接着，咱们别离对每个空间组的街坊节点进行特色聚合。该邻域划分和分组聚合，是以分而治之的形式解决空间异配性的根底。
旋转 - 伸缩双视角空间划分
图 3 旋转 - 伸缩双视角空间划分示意图
如图 3（a）和（b）所示，首先从方向维度（Direction View）和间隔维度（Distance View）对每个核心节点四周的天文空间进行划分，产生多个互不相交的子空间，并根据每个街坊节点所处的子空间对其进行分组。其中，咱们在方向维度下将天文空间划分成若干个方向不同的扇区（Sector），在间隔维度下将空间划分成若干个间隔不同的环（Ring）。 咱们基于飞桨实现了上述空间划分函数：首先，利用飞桨 PGL.Graph 类的节点特色、边特色拜访 API 获取节点的空间坐标和节点间的空间间隔，并计算出每个街坊节点所属的扇区和环；接着，基于 PGL.sampling 的 subgraph API 能够便捷地将每个扇区、每个环定义为不同子图，以此实现街坊节点的划分，代码如下所示。
思考到以下非凡状况：局部街坊节点可能散布在两个子空间的边界上，无奈确定属于哪个分组；咱们进一步提出了旋转 - 伸缩多重划分的策略，在方向和间隔维度上都进行多重划分，使得不同的划分之间可能施展互补劣势，如图 3（c）和（d）所示。 在实现上，咱们通过飞桨定义了多组扇区边界的旋转角度，以及多组环边界的间隔区间，屡次调用空间划分函数以实现多重空间划分，代码如下所示。
空间感知的邻域聚合
实现空间划分后，在邻域内进行特色聚合与消息传递。个别的 GNNs 通常应用求和或求均匀的形式进行邻域特色聚合，这将无奈辨别具备不同空间散布的街坊，进而导致具备空间多样性的异配散布被混合到一起，难以解决。与此不同，本办法对每个空间分组内的街坊进行别离聚合（group-wise aggregation），以实现对空间异配性的“分而治之”，该聚合过程如图 2（a）所示。 基于划分好的 PGL 子图构造，咱们能够借助 PGL 的消息传递办法 SEND-RECV 简便地实现每个空间分组内的消息传递与特色聚合。以方向维度下扇区内的街坊聚合为例，代码如下所示。
异配感知的空间交互
在此基础上，异配感知的空间交互模块蕴含两个可学习的核函数（Kernel Function），在城市图上自适应地提取和利用各个空间组到核心节点、以及空间组之间的共性信息（Commonality）和差别信息（Discrepancy）。
共性核函数
思考到不同的空间分组都是核心节点的街坊，利用邻域共性常识（Common Knowledge）或类似特点曾经被宽泛验证有利于图的示意学习。因而，咱们首先设计了一个共性核函数（Commonality Kernel Function）来捕获空间分组之间的共性信息，并利用共性信息加强各个分组的示意，如图 2（b）所示。 以方向维度为例，咱们基于飞桨张量计算，实现了对不同扇区之间的共性进行度量，以及用共性信息对扇区表征进行更新。
差别核函数
除了共性常识以外，对于具备异配性的城市图，建模街坊节点的差别信息更是至关重要的。因而，咱们设计了另一个差别核函数（Discrepancy Kernel Function）来捕获核心节点与空间组，以及各空间组之间的不相似之处，并相似地用差别信息来加强各空间分组表征。以方向维度为例，代码实现如下。
注意力门控机制
在各种的利用场景中，城市图上的不同城市实体可能具备不同水平的空间异配性。所以， 咱们进一步基于飞桨实现了一个注意力门控机制（Attentive Gate），通过端到端的形式自适应地学习共性信息和差别信息对特定工作中节点表征学习的重要性，以对两个重量进行交融。
空间维度交融
最初，咱们通过飞桨定义了一个可学习的比例参数，对方向维度和间隔维度下取得的邻域示意进行交融，并更新核心节点的示意。
在不同利用中，能够采纳不同的损失对网络进行优化以失去节点的最终示意，并用于节点预测工作。
试验
咱们在三个城市工作的三个实在数据集上进行了试验，验证了在城市图上思考空间异配性的重要性，并证实了本办法的有效性。相比个别的同配图神经网络、异配图神经网络、空间图神经网络，本办法能在不同的上游工作中取得更好的性能。
表 1 三个城市工作中的性能比拟
此外，咱们还通过丰盛的融化试验验证了本办法各局部设计的作用，包含从两个空间维度建模空间异配性、采纳旋转 - 伸缩多重划分、以及同时捕获图上的共性与差别信息等。
图 4 融化试验
总结
本文钻研了城市图上独特的空间异配性问题。一方面，咱们设计了一个指标来形容城市图的空间异配性，并剖析其对图神经网络的影响；另一方面，咱们基于飞桨图学习框架实现了一种新的空间异配性感知的图神经网络，可能简便地按空间划分对街坊进行分组解决，分而治之地解决城市图的空间异配问题，并在多个城市工作中获得性能晋升。
相干代码曾经开源在 PaddleSpatial 时空计算平台上。PaddleSpatial 是基于百度飞桨深度学习框架开发的时空大数据计算工具和平台，交融了百度当先的区域分割、时空迁徙学习、工夫序列预测等时空能力，可反对多种时空计算场景的利用。
Paper
https://arxiv.org/abs/2306.12139
Code
https://github.com/PaddlePaddle/PaddleSpatial/tree/main/research/SHGNN