引用本文

孙天元, 王永才, 李德英. 图实现算法综述与评测分析. 自动化学报, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561

SUN Tian-Yuan, WANG Yong-Cai, LI De-Ying. A Survey and Evaluation of Graph Realization Algorithms. ACTA AUTOMATICA SINICA, 2020, 46(4): 613-630. doi: 10.16383/j.aas.2018.c170561

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170561

关键词

图实现，网络定位，全局优化，模块拼合，综述，刚性，全局刚性 

摘要

图实现(Graph realization)问题研究基于节点间全部或部分距离关系测量, 在d维空间中计算图的顶点坐标, 使得在所实现图中各节点之间实现距离与测量距离尽可能一致.图实现问题是一个典型的优化问题, 在传感器网络定位、蛋白质结构重建、数据可视化、社交网络分析、机器人同步定位与构图等领域有着广泛应用.图实现的研究同图刚性理论有着紧密的联系, 图的刚性与全局刚性决定图的可实现性.在可实现图中, 现有工作提出几类典型的代表性图实现算法, 包括: 1)基于三边测距类方法; 2)求解距离方程类方法; 3)基于全局优化类方法; 4)基于模块拼合类方法.本文对图实现的刚性理论, 四类图实现算法的设计思想、适用条件、算法流程等进行综述分析, 通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和分析.

文章导读

由于在无线传感器网络定位和蛋白质结构重建等问题中的广泛应用, 图实现(Graph realization)问题在近些年得到了理论界和应用界的关注[1-2].图实现问题可定义为给定包含|V|=n个节点的图模型, 已知部分节点之间的距离测量矩阵{dij}, 需在d维空间中求解图G的实现结果, 即所有顶点V的对应坐标P=(p1,p2,⋯,pn), pi∈Rd, 使得所实现顶点位置间距离同给定距离测量的误差尽可能小的问题, 具体见式(1).

图实现问题是众多应用问题的数学模型.传感器网络定位, 即通过节点之间的距离求解网络中传感器位置是一个典型的图实现问题[1-5].蛋白质结构重建是图实现问题另一个重要应用领域, 目前可通过多种生物及物理技术测得蛋白质中特定节点之间的距离[6-7], 从而利用所测得的距离信息将蛋白质结构在三维空间中重建[8-9].此外, 图实现问题在数据可视化、社交网络分析和机器人同步定位与地图构建等问题中也有应用, 例如数据可视化中图标分布[10], 社交网络分析中隐藏属性的挖掘[11]以及以图优化方式求解机器人同步定位与地图构建问题[12]等.

图实现问题在1979年被Saxe证明即使在一维空间中也是NP完全问题[13], 在多维空间中为NP困难问题[14].但Saxe的证明考虑到所有图的特殊情况.在一般图(Generic graph)中, 即图中顶点坐标在有理数空间中没有整数系数使其线性组合为零的条件下, 在多项式时间内是可解的, 并且一般图在空间中是致密的, 这使得图实现问题引起应用和算法研究的广泛关注.

图实现的主要挑战有两点:

1) 图的唯一实现性问题:在众多应用中, 并不能提供充分的距离测量关系, 在图中边的数量较为稀疏情况下, 可能存在多个实现结果均满足已知的测量, 称为混淆的图实现(Realization ambiguity), 最终结果与真实结果产生偏差[2].为分析图实现的结果唯一性, 现有结果从图实现的刚性(Rigidity)、全局刚性(Global rigidity)、可定位性(Localizability)等方面进行了研究.相关概念介绍如下:刚性(Rigidity):如果一个图的实现G(P), 在顶点邻域U内是可保持图的边长不变的唯一实现, 则称G(P)是刚性的.刚性意味着G(P)不存在可保持顶点间距离关系的连续形变.但刚性并不能保证G(P)是该图唯一的实现, 刚性图可能存在翻转混淆实现(Flipping ambiguity)或弯折混淆实现(Flex ambiguity)的情况, 即保持边距离关系不连续的混淆实现.

全局刚性(Global rigidity)[15]:如果Rd空间的图实现G(P)的坐标是可以保持边长不变情况的唯一实现, 则称G(P)是全局刚性的.二维平面中图的刚性判定方法, 主要包括二维平面中的Pebble game[16]方法, 在高维空间中, 主要包括压力矩阵分析方法等.图的唯一实现性的相关综述可以参考文献[17].

2) 图实现的算法研究:在实际应用中, 测量边通常是稀疏的, 而且距离的测量往往在有噪声的环境下获得, 使得即使图存在唯一的实现结果, 但图实现的结果有很大的误差.如传感器网络定位问题中, 距离测量一般通过信号强度的衰减或信号传播时间来确定, 受到环境影响较大; 而社会网络分析等问题中如何将节点之间的关系映射为欧氏距离也是一个关键问题.当距离的测量值存在一定的误差时, 会影响实现结果的准确性.所以图实现的算法研究, 主要是针对节点间的边的数量有限, 存在测量噪声的情况下, 研究顶点坐标计算的算法.

现有算法主要可以分为4类: 1)基于多边测量的方法, 使用简单的多边测量手段进行节点坐标计算; 2)求解距离方程的方法, 将所有已知距离关系整体考虑求解距离方程组; 3)全局优化的方法, 将距离看作约束, 用优化模型描述坐标求解; 4)基于模块拼接的方法, 将网络划分为多个子模块, 在模块内部局部定位, 再通过全局调整将局部坐标转换到全局坐标.

这些算法有其各自的优势和劣势, 例如多边测量方法计算简单, 但是会产生累积误差; 全局优化方法对噪声敏感; 模块拼接方法需要全局迭代.现有文献中, 仍非常缺乏对这一系列算法的深入比较和分析, 缺少对算法的适应性, 特点的分析和理解.

为了解决此问题, 本文综述和深入比较了图实现的几种代表性算法, 包括三边测量法(Trilateration)[18]、多维尺度标定算法(Multi-dimensional scaling, MDS)[19]、半正定规划方法(Semidefinite programming, SDP)[20]、通用图优化方法(General graph optimization, g2o)[12]、优超函数算法(Scaling by majorizing a complicated function, SMACOF)[21]和几种代表性的模块拼合的方法: AAAP (As-affine-as-possible)[22]、ARAP (As-rigid-as-possible)[22]和ASAP (As-synchronized-as-possible)[23].

本文对算法的设计思想、适用条件、算法流程等进行详细介绍, 并通过实验对比, 结合传感器网络定位这一具体应用, 对所介绍几种算法进行准确性、计算复杂度、可靠性等方面的比较和分析.

图 1  SMACOF算法示意图

图 2  模块拼合示意图

图 3  定位误差统计图

本文比较和分析了图实现的几类代表性算法, 包括三边测量法(Trilateration)、求解距离方程的方法(主要包括多维尺度标定算法(Multi-dimensional scaling, MDS)、半正定规划方法(Semidefinite programming, SDP))、基于全局优化的方法(主要包括通用图优化(General graph optimization, g2o)、优超函数算法(Scaling by majorizing a complicated function, SMACOF)方法)、基于模块拼合的算法(AAAP (As-affine-as-possible)、ARAP (As-rigid-as-possible)和ASAP (As-synchronized-as-possible)).

Trilateration算法和AAAP算法虽然可快速获得计算结果, 但是其实现结果的准确性存在累积误差问题, 基本不应用于实际问题.求解距离方程的两类算法, MDS算法对拓扑结构稠密度要求较高, SDP算法对拓扑结构稠密度十分敏感, 在图中边的数量较为稀疏的情况下, 此类算法的求解结果误差较大.基于全局优化的两类方法, 拥有较高的准确性和较强的鲁棒性, 但是其实现结果的优劣多数情况下取决于其初始结果的选取, 在图实现问题模型的求解过程中, 迭代优化过程仅需要较少的额外计算资源, 在众多实际问题中, 通常会选择全局优化类方法提高实现结果的准确性.基于模块拼合类方法中, ARAP算法和ASAP算法的拥有较高的准确性, 并且对拓扑结构的稠密度以及测距噪声的强度均有较强的鲁棒性, 但是ASAP算法需要占据大量的计算资源, 不适用于大规模的网络结构.

本文的实验结果表明ARAP算法在准确性、计算效率和鲁棒性等方面均表现出良好的性能, 但是此类算法的结果与模块局部实现结果的准确性紧密相关.因此如何判别各个模块局部结果的准确度成为提高现有算法的关键问题.本文在讨论图的唯一性实现问题时简单介绍的刚性理论, 相关的理论结果可以为模块实现结果的准确性提供先验知识, 并且可以通过这些先验知识在拼合过程中对各个模块赋予权重, 进一步提高结果的准确性.此外, 可以根据刚性理论设计更多的模块划分的策略, 获得拥有更加准确的实现结果的模块.刚性理论不仅提供了图结构性质的判别方法, 若将其应用于图实现问题的求解阶段, 可以期望, 将显著提高实现结果的准确性和对稠密度、测距噪声的鲁棒性.

作者简介

孙天元

中国人民大学信息学院硕士研究生. 2015年获得中国人民大学信息学院学士学位.主要研究方向为图实现与虚拟现实. E-mail: suntyruc@163.com

李德英

中国人民大学信息学院计算机科学与技术系教授. 1988年获得华中师范大学数学学士学位, 2004年获得香港城市大学计算机博士学位.主要研究方向为线传感器网络, 社会网络, 算法分析与设计. E-mail: deyingli@ruc.edu.cn

王永才

中国人民大学计算机系副教授. 2001年获得清华大学自动化系学习学位, 2006年获得清华大学自动化系博士学位.主要研究方向为物联网, 机器人, 大数据挖掘与分析, 算法设计与分析.本文通信作者. E-mail: ycw@ruc.edu.cn