GIS领域图算法应用初探

发布时间:2022 年 07 月 13 日  文/超图研究院未来GIS实验室 罗强 郑友康
导读:GIS作为现实世界到虚拟世界的映射和分析工具,随着知识图谱等技术的发展,从传统欧式空间表达到非欧空间的拓展已是大势所趋,包括超图在内的各大厂商正在积极布局。整体来看,GIS领域图数据分析方法可以分为传统图计算和图神经网络两个方向。
图(Graph)是一种常见的数据结构,现实世界中有很多任务可以抽象成图问题,如交通路网流量,社交网络,蛋白体结构等,常见的知识图谱本质上也是一种图结构。在算力快速发展的今天,面对大数据时代规模庞大、关系复杂的图数据结构,充分利用图算法,能够最大程度地挖掘信息价值,辅助决策。GIS 作为现实世界到虚拟世界的映射和分析工具,随着知识图谱等技术的发展,从传统欧式空间表达到非欧空间的拓展已是大势所趋,包括超图在内的各大厂商正在积极布局。整体来看,GIS 领域图数据分析方法可以分为传统图计算和图神经网络两个方向,此处结合两个方向对图算法在 GIS 领域的应用场景进行适度探讨,期待未来图算法与 GIS 的深度融合。
 
传统图计算
 
传统图计算可以分为三类:图与路径搜索,中心度分析及社区发现 [1]。图与路径搜索主要用于寻找两地之间的最短路径、网络路由的优化等。中心度分析的典型应用包括寻找知识图谱网络中最有影响力节点,确定通信网络或电力网络中易于受攻击的点等。社区发现典型应用包括城市圈腹地的划分,对商品网络进行聚类分析和从罪犯关系网络中锁定犯罪团伙等。
 
• 图与路径搜索
 
图与路径搜索算法通常从一个节点开始,扩展关系直到目的节点。图搜索算法主要是寻找满足条件的某一路径,而路径搜索算法尝试根据跳数或权重找到最佳路径。
 
常见的最短路径搜索算法有 Dijkstra 算法、Floyd算法、Bellman-Ford 算法、Bellman-Ford 算法及最小生成树 Kruskal 算法。其中 Dijkstra 算法基于贪心策略每次找到离源点最近的一个顶点,确定源点到该点之间的最短路径,检查是否能通过该顶点进行松弛操作,最后得到源点到其他各个顶点之间的最短路径。Floyd 算法是一种动态规划算法,Floyd 算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路 ) 的最短路径问题。Bellman-Ford 算法通过递推迭代方式反复对边集 E 中每条边进行松弛操作,使得源点到其他每个顶点 u ∈ V 的最短路径估计值逐渐逼近其最短距离。Kruskal 算法是基于贪心的思想得到的,把所有的边按照权值先从小到大排列,按照顺序选取每条边,如果这条边的两个端点不属于同一集合,那么就将它们合并,直到所有的点都属于同一个集合为止。
 
 
在 GIS 知识图谱上进行路径规划的场景中,经常会遇到需要计算到达目的地的最佳路径以及关键节点的邻域状态分析。此时,路径搜索算法可以满足这一需求,通过判断单源或多源路径来选择路径搜索算法,以带地理属性的图数据为基础,进行动态邻域迭代求解计算,规划出符合实际的最佳路线,从而为用户提供路径规划信息。
 
• 中心度分析
 
中心度算法用于查找图数据中最具影响力的节点,其衡量的角度有度中心度,中介中心度,聚集中心度等。其中,度中心算法测量图中节点具有的关系数,中介中心度算法测量图中通过节点的最短路径的数量,聚集中心度算法测量图中节点在其群集中的中心位置。
 
在 GIS 知识图谱上查询地理要素 ( 比如商场等地理元素 )重要性的场景中,通过中心度计算分析知识图谱中节点的各种中心度值,进行时空维度的比较分析,可以为用户提供实时的GIS 信息状态查询。
 
• 社区发现
 
图数据由节点集组成,社区内部节点集相互间作用比社区外部节点的相互作用更紧密,社区发现算法用于把图数据划分成若干个内部紧密连接的社区,以便决策者因地制宜进行政策制定。
 
社区发现算法大致分为三个类别,分别是基于局部搜索的图社区发现算法、基于谱分解的图社区发现算法、基于启发式图社区发现算法。基于局部搜索的图社区发现算法主要有 Kernighan-lin 算 法、Newman(FN) 方 法、GuimeraAmaral 方法、louvain 算法,这些算法基于局部优化函数的迭代,不断产生候选解及拓扑动态的更新以生成社区。基于谱分解的图社区发现算法主要有 N-CUT、R-CUT、M-CUT,这些算法主要通过邻接矩阵存储空间结构信息,结合矩阵分解、特征融合等手段实现知识图谱社区发现。基于启发式图社区发现算法主要有 G-N 算法、Maxinum flow communiuties 算法、W-H 算法,算法中的 G-N 算法、Maxinum flow communiuties算法吸纳的是图论中的最大流最小截思想,而 W-H 算法是将图看成电路图,边看成有电阻的线路,不同节点具有不同的电势,利用基尔科夫定律求不同节点的电势,利用阈值分割,将节点进行社区分割。
 
在 GIS 知识图谱上进行城市圈或产业分布等可聚集要素划分的场景中,将空间地理实体与其关系表示成 GIS 知识图谱中的节点与关系对,通过相关社区发现算法,对拓扑空间邻接信息进行深度计算分析,以社区模块度为迭代目标,能较好的实现社区的划分。
 
图神经网络
 
典 型 的 图 神 经 网 络 算 法 包 含 图 卷 积 网 络 (Graph Convolution Networks,GCN)、 图 注 意 力 网 络 (Graph Attention Networks)、图自编码器 (Graph Autoencoders)、图 生 成 网 络 (Graph Generative Networks)、 图 时 空 网 络(Graph Spatial-temporal Networks) 等五个部分 [3]。
 
图卷积网络 (Graph Convolution Networks,GCN) 将卷积运算从栅格图像数据推广到图数据。其核心思想是学习一个函数映射 f,通过映射图中的节点,聚合它自己的特征与它的邻居特征来生成图中节点的新表示。图注意力网络 (Graph Attention Networks) 是一种基于空间的图卷积网络,它的特点是在聚合特征信息时,将注意机制运用到确定图节点邻域的权重上,典型的有采用多头注意力机制的门控注意力网络(GAAN) 和利用循环神经网络模型的图形注意力模型 (GAM)。
 
图自编码器 (Graph Autoencoders) 的目的是利用神经网络结构将图的顶点表示为低维向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入,而解码器用来重建节点的邻域统计信息,其中 DNGR 和 SDNE 仅给出拓扑结构的节点嵌入,而 GAE、ARGA、NetRA、DRNE 用于学习当拓扑信息和节点内容特征都存在时的节点嵌入。图生成网络 (Graph Generative Networks) 的目标是在给定观察图的情况下生成新的图,典型的有将 relational GCN、改进的 GAN 和强化学习(RL)目标集成在一起,以生成具有所需属性的 Molecular Generative Adversarial Networks (MolGAN) 和通过两层循环神经网络的深度图生成模型GraphRNN。图时空网络(Graph Spatial-temporal Networks) 同 时 捕 捉 时 空 图 的 时 空 相 关性, 典 型 的 有 Diffusion Convolutional Recurrent Neural Network(DCRNN),CNN-GCN,Spatial Temporal GCN (ST-GCN),Structural-RNN。
 
在 GIS 交通导流的场景中,经常会遇到如何均衡超出承载能力的交通路网交通流量的问题,而图数据结构天然的适合存储关于路网的数据,以交通路网实时和历史流量为基础训练图神经网络,可以为交管部门提供车速、车流量、方向等 GIS 导流信息。
 
图算法主要的研究对象是利用图的基本理论和特性对客观世界存在的复杂网络关系进行建模和分析,基于图算法的数据分析已经应用在了很多 GIS 场景中。随着 GIS 图数据规模的日益增加,针对图数据的计算效率也变得越发被人们关注,分布式计算、内存计算等解决方案正日益成熟。商业软件方面,以 Neo4j 为代表的一批性能优秀的图数据库提供了丰富的图计算算子,并在工业上得到了广泛应用。地理空间实体和关系天然形成图结构,图算法将为 GIS 信息挖掘从非欧空间角度提供赋能。未来随着知识图谱等领域的发展,图结构联合语义分析将互相促进,辅助用户进行地理信息的全盘把控和精准决策。
 
参考资料
[1] 陈华钧 . 知识图谱导论 [M]. 北京 : 电子工业出版社 ,2021.200-237
[2]https://www.cnblogs.com/end/p/6364345.html
[3]https://blog.csdn.net/zandaoguang/article/details/104132298
 
 
 
 
 
版权所有© 1997-2019 中国科学院地理信息产业发展中心 《超图通讯》编辑部 京ICP备11032883号-6