【注：本文出于知识分享目的转载，如涉及版权问题，请版权所有者尽快联系我们，我们立刻删除并道歉，谢谢理解。】
摘 要：从概率图、组合图、代数图和几何图等模型角度综述模式识别中图结构的描述.分别讲述每一类图模型的图结构构建形式和计算方式，回顾其起源，归纳其历史发展过程，分析其研究现状.其中，着重论述各类图模型描述的不同特点和潜在关系，剖析未来发展方向.引用基于图模型的模式识别发展史上具有代表性的论著，介绍引领方向的研究学者，旨在帮助读者理清图模型的发展脉络，把握其前沿动态.
摘 要：从概率图、组合图、代数图和几何图等模型角度综述模式识别中图结构的描述.分别讲述每一类图模型的图结构构建形式和计算方式，回顾其起源，归纳其历史发展过程，分析其研究现状.其中，着重论述各类图模型描述的不同特点和潜在关系，剖析未来发展方向.引用基于图模型的模式识别发展史上具有代表性的论著，介绍引领方向的研究学者，旨在帮助读者理清图模型的发展脉络，把握其前沿动态.
关键词：图结构描述；模式识别；概率图模型；组合图模型；代数图模型；几何图模型
图，作为节点和连边的集合，能够精确刻画各类具有结构特征的事物，在模式识别领域得到了广泛的研究和应用.图结构既可以抽象地描述事物的过程和进程，又能具体描述数据间的关联关系.在模式识别的不同领域和场景中，图结构具有不同的描述方式.作者将图模型的结构简分为4类，即概率图、组合图、代数图和几何图，分别介绍4类图模型在其对应模式识别问题中的描述方式.
论文内容安排如下：第一节介绍图模型的统一描述；第二至第五节分别介绍4类图模型的描述形式；第六节总结全文.
1 图结构简述
一个图模型是一个节点集合和一个连边集合的综合表达形式.其中，连边集合中的每个元素表示两个相连的节点.连边中的两个节点既可以有序，也可以无序.节点有序时连边为有向连边，节点之间有因果关系，此时图模型为有向图；节点无序时连边为无向连边，节点之间仅有关联性，无因果关系，此时图模型为无向图.
尽管图模型具有上述统一的结构形式，但是在具体的模式识别问题中，图结构的描述各有不同，其学习和计算过程有较大的差异.第二节至第五节将阐述图模型在不同研究方向的描述方法.
2 概率图模型
概率图模型(probabilistic graphical model)的研究工作是机器学习领域近半世纪的研究热点之一.20世纪末，图灵奖得主、美国加州大学伯克利分校(UC Berkley)的Pearl[1]发明了因果模型(causal model)，从哲学和概率视角高屋建瓴地构建了图模式因果关系模型.美国加州大学伯克利分校的Jordan等[2]和美国麻省理工学院(Massachusetts Institute of Technology)的Freeman等[3]学者不断推动的用图模型表示变量概率依赖关系的理论体系，逐渐发展为贝叶斯网络(Bayesian networks)和马尔科夫随机场(Markov random field)两类模型.在贝叶斯网络中，每一个节点代表一个随机变量，节点之间的连边有向，表示随机变量之间的因果依赖关系.随机变量的联合概率分布可根据概率图模型方便写出.如图1中例子所示，根据左图的概率图模型，可以方便地推导出右式的联合概率分布的分解形式.
图1 贝叶斯网络表达联合概率分布分解的示例
与贝叶斯网络不同，马尔科夫随机场的随机变量(即节点)之间仅有关联关系，没有因果关系，因此马尔科夫随机场的图模型节点之间由无向连边连接，其联合概率分布由随机变量组合的势能函数(potential function)的归一化乘积表示.概率图模型的一类推理方式是信念传播法[4](belief propagation).
近期，Hu等[5-6]合作提出了一系列基于概率图模型的机器视觉算法，应用于物体检测和跟踪等各个场景;Xu等[7]运用概率图模型进行网络信息挖掘，均取得了显著成效.
概率图模型的特点是可以通过对场景的理解设计关联关系或因果关系，进而得到图模型，模型可解释度高.概率图模型目前的研究难点是图结构学习和非参数概率图模型学习等问题.
3 组合图模型
组合图模型是一类运用组合优化(combinatorial optimization)方法建模和计算的机器学习模型.组合优化又称为离散优化(discrete optimization)，与连续优化或者将连续优化松弛至离散值等优化方式不同，组合优化直接在离散域求解局部最优，并能在一定程度上保证推理的合理性.最常用的组合优化方法是图割法(graph-cuts)，即最大流/最小割法(Maxflow/Mincut).图割模型除了包括代表变量的节点之外，还引入了源点(source)和汇点(sink)两个辅助节点.变量节点按照关联关系相连，其连边权重表征变量间的关联度.源点和汇点分别与变量节点相连，其连边权重表征变量本身属性.通过最大流/最小割法运算，将图模型分离为与源点连通和与汇点连通的两部分，达到推理的目的.
Boykov[8]是最早将图割模型引入计算机视觉和模式识别的学者之一.他首先将图割模型用于图像前景和背景分割——将每一个节点设为一个像素，将源点设为前景像素标识，将汇点设为背景像素标识，通过最大流/最小割算法进行前景和背景分割，示例如图2所示[8].
图2 基于图割(Graph Cuts)的图像分割示例
图2左图是一幅原始3×3分辨率图像，颜色深浅代表像素不同的灰度值，O和B分别代表前景和背景的种子(已知类标)像素；图2中图是图割模型，其中源点T和汇点S在上下两侧，中间9个节点代表9个像素，通过将9个节点分割为仅与T相连和仅与S相连的两部分，进行图像的背景和前景分割；图2右图是9个像素的分割结果，深色代表像素分割为前景，浅色代表像素分割为背景.
除图像分割外，图割模型也被广泛应用到了立体匹配、光流、目标跟踪等计算机视觉问题中.除了Yuri Boykov之外，在组合图模型研究中处于前沿的课题组包括美国康奈尔大学(Cornell University)的Ramin Zabih研究组和英国牛津大学(Oxford University)的Philip Torr研究组.Kohli等[9]于2011年发表综述文章，总结分析了各类组合图模型的特点.相关文献不断将组合图模型由二阶向高阶推进，提升其数据刻画能力[10-11].
需要指出的是，组合图模型和概率图模型有诸多交叉之处.很多组合图模型仅仅在推理过程中运用组合优化的方法，而在构建图模型时采用概率图模型的理论解释.因此，组合图模型是指在推理过程的图模型.早在20世纪80年代，Geman等[12]就已经观察到概率图模型与组合图模型的共通之处.以Philip Torr为代表的一系列学者一直秉承基于随机马尔科夫场进行建模、基于图割进行求解的设计思想[10-11].微软西雅图研究院Szeliski等[13]通过实验分析比较了图割、信念传播等方法在推理马尔科夫随机场时的各自特点.
组合图模型的特点是可以运用最大流/最小割以及动态规划等经典算法进行高效推理.然而，如何学习先验知识及进行图模型的构建，仍然是模式识别中的组合图模型需要研究的重点问题.
4 代数图模型
代数图(algebraic graph)模型首先将图以矩阵的形式表示，然后通过代数运算进行图模型的学习和推理.图矩阵的每一行和每一列均代表图模型的一个节点，图矩阵元素代表其行、列对应的两个图节点之间的连边权重(即关联关系).对图矩阵进行代数运算的最有效工具之一是美国加利福尼亚大学圣地亚哥分校(UC San Diego)Chung[14]提出的谱图理论(spectral graph theory).在此基础上英国约克大学(University of York)的Hancock[15]研究组和瑞士伯恩大学(University of Bern)的Bunke研究组进行了近40年持续不断的基于代数图模型的模式识别方法的研究.基于代数图模型的模式识别包含图节点、图样本、图匹配3个研究对象，简析如下.
4.1 图节点
一个图模型代表一个样本集合，其中每个图节点代表一个样本，连边代表样本点之间的关联关系.在此基础上，样本集合通过图矩阵进行描述.Wu等[16]最先提出通过对图节点(代表像素点)进行聚类进行图像分割.在此基础上，Shi等[17]提出了基于归一化拉普拉斯图矩阵的归一化割(normalized cuts)、均衡大类和小类权重，形成更稳定的图像分割算法. 归一化割和组合图模型中的图割是两个容易混淆的概念，它们的区别是：归一化割在连续域进行建模，通过连续域的代数方法进行学习和计算；图割在离散域建模，通过组合优化的方法进行推理.受归一化割启发，一系列图矩阵学习方法(如dominant sets[18] 和commute time[19])和图节点核函数矩阵构建方法(如sum-over-paths covariance kernel[20])相继被提出，不断提升图节点分类和聚类的效果.用图节点模型进行图像分割的示例如图3所示[8].
图3 图节点分割算法用于图像分割的示例
图3左图是原始图像，中图是归一化割图像分割结果，右图是dominant sets图像分割结果.
基于图矩阵的学习和推理属于连续优化的范畴，直接在连续域进行代数计算.若将此类连续优化问题松弛至离散域，则亦可以采用组合图模型的方法进行推理，最后以离散结果近似连续结果.目前，图矩阵的设计和分析仍然是模式识别领域的热点之一.
4.2 图样本
模式识别中的每一个样本通常表示为一个属性向量.然而，在模式识别的很多任务中，样本的表示不是向量形式，而是图模型形式.如图4[21]左列中两个分子，分别可以抽象成右列的两个图模型样本.
图4 分子模型抽象为图样本的示例
在样本表示为图模型的情况下，需设计适合图模型样本的分类、聚类和生成等模式识别方法.罗斌等[22]提出了一系列运用谱图理论将图样本嵌入向量空间(即将图样本转化为向量表示)的方法，进而运用面向向量的模式识别方法对图模型样本进行分析和处理.近期，一系列图样本核函数相继出现，代表成果为NIPS会议2008年的最佳学生论文提出的快速子树核函数[23](fast subtree kernels)和ICIAP会议2015年的最佳学生论文提出的基于量子行走的连边匹配核函数[24](an edge-based matching kernel through discrete-time quantum walks).图样本核函数架起了核空间和图样本的桥梁，将核空间分析延伸至图模型核空间.近期，Edwin R Hancock课题组创新性地提出了图样本的生成模型，将生成算法从向量空间拓展至图空间[21].
4.3 图匹配
图匹配主要研究两个图模型节点集合的最优映射关系，即寻找两个图模型之间的对应节点匹配关系.20世纪80年代，日本学者Umeyama等[25]率先提出了运用谱图分析进行图节点匹配.罗斌等[26]提出了运用EM算法寻优进行图匹配，进而完成物体特征点匹配的任务，示例如图5所示[26].
图5 EM图模型节点匹配示例
图5左、中图为同一物体不同角度的两幅图像以及其中提取的两个Delaunay 图模型，右图为用EM图模型节点匹配方法进行物体特征点匹配的结果.
Mario Vento等学者发表两篇综述文章，分析总结了2004年之前[27]和2014年之前[28]的各类图匹配方法.近期，越来越多的机器学习方法和图矩阵构建方法应用于图匹配，匹配精度不断提高，在3D重建、遥感图像配准等领域取得广泛应用.
该节简述了基于代数图模型的各类模式识别方法，主要针对图节点、图样本和图匹配3类研究对象进行了回顾.目前，为了提升数据表达能力，代数图模型正在向超图模型演化，超图节点分析[29]、超图样本聚类[30]以及超图匹配[31]开始逐渐得到广泛关注.
5 几何图模型
网(mesh)作为图模型的一种特殊形式，长期应用于计算机图形学的建模和分析中.网上单独的节点和连边都没有具体含义.然而，网状图结构作为整体覆盖物体表面，进行整体处理和分析，可以得到物体的几何形状和拓扑形态的众多特性.如通过计算覆盖物体表面的网格的离散里奇曲率流(discrete ricci flow)，可以得到原始物体形状向各类曲面的投影，如图6所示[32].
图6 基于网状图结构的物体图形变换示例
图6上行为3种物体形状，下行为3种形状通过离散里奇曲率流计算分别得到的在球面、平面、双曲面的保角共形映射结果.
这个研究领域近期的标志性成果是菲尔兹奖得主丘成桐和他的学生顾险峰共同开创的计算共形几何学(computational conformal geometry)[33-34]，架起了黎曼面理论和计算科学的桥梁.
6 结束语
图论是数学的分支.图论运用于模式识别，产生了一系列推动模式识别领域进步的标志性成果，同时，模式识别中的问题也推动了图论自身的不断进展和完善.作者尝试从概率图、组合图、代数图以及几何图等几个角度阐释图模型在模式识别(尤其是计算机视觉)的各类问题中的描述形式，并尝试论述图论在模式识别领域中的发展历史和研究现状.由于仅限于讨论模式识别问题，因此论文未涉及图论在计算机学科其他方向中的表现形式(如描述离散并行系统的Petri网等).当今模式识别中的图模型研究方兴未艾，在深度学习被广泛应用的今天，如何将各类图模型与深度学习融合，将是图模型新的发展方向.
参考文献：
[1] PEARL J. Causality: models, reasoning, and inference[M]. London: Cambridge University Press, 2000.
[2] JORDAN M， WAINWRIGHT M. Graphical models, exponential families, and variational inference[J]. Foundations and Trends in Machine Learning, 2008, 1 (1/2): 1-305.
[3] FREEMAN W， SUDDERTH E. Signal and image processing with belief propagation[J]. IEEE Signal Processing Magazine, 2008, 25 (2): 114-141.
[4] PEARL J. Reverend Bayes on inference engines: a distributed hierarchical approach[C]// In Proceedings of the Second National Conference on Artificial Intelligence (AAAI),1982: 113-136.
[5] WU B, ZHANF Y, HU B, et al. Constrained clustering and its application to face clustering in videos[C]// In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009: 3507-3514.
[6] WU Z, LEAHY R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15 (11): 1101-1113.
[7] XU Z L, YAN F, QI Y. Bayesian nonparametric models for multiway data analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37 (2): 475-487.
[8] BOYKOV Y, FUNKA-LEA G. Graph cuts and efficient N-D image segmentation[J]. International Journal of Computer Vision, 2006, 70 (2): 109-131.
[9] KOHLI P, LANDICKY L, TORR P. Robust higher order potentials for enforcing label consistency[J]. International Journal of Computer Vision, 2009, 82 (3): 302-324.
[10] FELZENSZWALB P, ZABIH R. Dynamic programming and graph algorithms in computer vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33 (4): 721-740.
[11] WANG P, SHEN C, HENGEL A, et al. Efficient semidefinite branch-and-cut for MAP-MRF inference[J]. International Journal of Computer Vision, 2016, 117 (3): 269-289.
[12] GEMAN S, GERMAN D. Stochastic relaxation, gibbs distribution and the bayesian restoration of images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6 (6): 721-741.
[13] SZELISKI R, ZABIH R, SCHARSTEIN D, et al. A comparative study of energy minimization methods for markov random fields with smoothness-based priors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30 (6): 1068-1080.
[14] CHUNG F R K. Spectral graph theory[C]// CBMS Regional Conference Series in Mathematics,1997： 154-156.
[15] HANCOCK E R, WILSON R C. Pattern analysis with graphs: parallel work at Bern and York[J]. Pattern Recognition Letters， 2012, 33 (7): 833-841.
[16] WU B, LYU S, HU B, et al. Simultaneous clustering and tracklet linking for multi-face tracking in videos[C]// In Proceedings of IEEE International Conference on Computer Vision (ICCV), 2009: 2856-2863.
[17] SHI J, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22 (8): 888-905.
[18] QIU H, HANCOCK E. Clustering and embedding using commute times[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29 (11): 1873-1890.
[19] PAVAN M, PELILLO M. Dominant sets and pairwise clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29 (1): 167-172.
[20] MANTRACH A, YEN L, CALLUT J, et al. The sum-over-paths covariance kernel: a novel covariance measure between nodes of a directed graph[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32 (6): 1112-1126.
[21] HAN L, WILSON R, HANCOCK E. Generative graph prototypes from information theory[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37 (10): 2013-2027.
[22] LUO B, WILSON R, HANCOCK E. Spectral embedding of graphs[J]. Pattern Recognition, 2003, 36 (10): 2213-2230.
[23] SHERVASHIDZE N, BORGWARDT K. Fast subtree kernels on graphs[C]// In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2009: 1660-1668.
[24] BAI L, ZHANG Z, REN P, et al. An edge-based matching kernel through discrete-time quantum walks[C]// In Proceedings of International Conference on Image Analysis and Processing (ICIAP), 2015: 27-38.
[25] UMEYAMA S. An eigendecomposition approach to weighted graph matching problems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10 (5): 695-703.
[26] LUO B, HANCOCK E. Structural graph matching using the EM algorithm and singular value decomposition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23 (10): 1120-1136.
[27] CONTE D, FOGGIA P, SANSONE C, et al. Thirty years of graph matching in pattern recognition[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2004, 18 (3): 265-298.
[28] FOGGIA P, PERCANNELLA G, VENTO M. Graph matching and learning in pattern recognition in the last 10 years[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2014, 28 (1): 461-465.
[29] LIU H, LATECKI L, YAN S. Dense subgraph partition of positive hypergraphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37 (3): 541-554.
[30] REN P, ALEKSIC T, WILSON R, et al. A polynomial characterization of hypergraphs using the Ihara zeta function[J]. Pattern Recognition, 2011, 44 (9): 1941-1957.
[31] PARK S, PARK S, HEBERT M. Fast and scalable approximate spectral matching for higher order graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36 (3): 479-492.
[32] ZENG W, SAMARAS D, GU X. Ricci flow for 3D shape analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32 (4): 662-677.
[33] GU X, YAU S. Computational conformal geometry[M]. Beijing: China Higher Education Press, 2008.
[34] LUI L, ZENG W, YAU S, et al. Shape analysis of planar multiply-connected objects using conformal welding[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36 (7): 1384-1401.
(责任编辑 朱夜明)
A survey of graph structure descriptions in pattern recognition
RENPeng
(College of Information and Control Engineering, China University of Petroleum (East China), Qingdao 266580, China)
Abstract：We reviewed graph structure descriptions from four perspectives, i.e., probabilistic graphical models, combinatorial graph models, algebraic graph models and geometric graph models. For each type of graph models, we first described their construction and computation schemes. We then presented the development progress of each model from its origin to the state of the art, and predicted its possible future direction. We referenced landmark works and pioneering researchers in the literature such that readers may easily follow the state of the art graph models in pattern recognition.
Keywords：graph structure descriptions; pattern recognition; probabilistic graphical models; combinatorial graph models; algebraic graph models; geometric graph models
doi：10.3969/j.issn.1000-2162.2017.01.002
收稿日期：2016-03-16
基金项目：国家自然科学基金资助项目(61671481)；青岛市自主创新计划应用基础研究项目(16-5-1-11-jch)
作者简介：任 鹏(1981-)，男，内蒙古包头人，中国石油大学(华东)教授，硕士生导师，博士.
中图分类号：TP274; G484
文献标志码：A
文章编号：1000-2162(2017)01-0003-07
