编辑荐读 | 面向组合优化问题的图学习综述

Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇综述精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

DSE精选文章 | 面向组合优化问题的图学习综述

文章介绍

近年来图数据在社交网络、电商、生物信息等领域大量涌现。如何从海量图数据中有效的提取有价值的信息是一个基础性问题。但图数据上的很多分析和处理任务是NP难的组合优化问题。传统方法主要通过精确算法、近似算法和启发式算法进行处理。精确算法虽能求得精确解，但最差情况需要指数时间才能完成。近似算法能在多项式时间内完成，且有近似率的保证，但很多组合优化问题理论上已经证明无法近似。启发式算法虽没有近似率的保证，但由于可以在多项式时间内得到一个较优解，所以得到了广泛应用。

随着最近图学习技术的迅速发展，学术界提出了很多基于图学习的组合优化问题求解方法。基于图学习的组合优化方法也没有近似率的保证，因此也属于启发式算法的范畴。与传统启发式算法不同，基于图学习的组合优化方法无需人工设计算法，而是从海量数据中自动地提取数据中存在的各种特征，利用所提取的特征来训练一个模型，通过模型来预测组合优化问题的解。本文综述了最新的基于图学习的组合优化方法。

欢迎扫码阅读全文

01

基于图学习的组合优化总体框架

基于图学习的组合优化方法通常包含两个阶段。阶段一是学习图的表示向量；阶段二是利用图的表示向量来求解特定的组合优化问题。图1展示了基于图学习的组合优化方法的总体框架。

图1. 基于图学习的组合优化总体框架

阶段一：图表示向量学习

图表示向量学习有两种方式。第一种是图嵌入的方式。该方式割裂了阶段一和阶段二。在学习图表示向量时具有独立的损失函数，且损失函数可以与阶段二待解决的组合优化问题无关。第二种是端到端的方式。该方式打通了阶段一和阶段二。在学习图表示向量时没有独立的损失函数，学习到的图表示向量输入到阶段二，利用阶段二的损失函数的梯度来学习图表示向量。

图嵌入的方式主要分为基于SkipGram模型的方法和基于自编码器的方法。基于SkipGram模型方法的思想是相邻的两个“对象”具有相似的表示向量。不同的工作对“对象”具有不同的定义。一大类是把图的节点当作对象，相邻的节点具有相似的表示向量。另一大类是把图的子图当作对象，相邻的子图具有相似的表示向量。基于自编码器模型的方法首先定义节点间的亲近关系，编码器对图中的节点学习一个表示向量，解码器根据节点的表示向量来重构节点之间的亲近关系。常用的亲近关系包括：一跳邻居、二跳邻居、PageRank和Katz 索引等。

端到端的方式主要分为基于图神经网络的方法和基于自编码器的方法。基于图神经网络的方法通过图上的卷积操作来学习节点的表示向量。目前学术界提出了多种图神经网络模型，包括GCN和GAT等。为了提高学习的效率，还提出了基于采样技术的GraphSAGE和SPAGAN 等图神经网络模型。基于自编码器的方法主要用其编码器来学习图的表示向量，解码器用在阶段二求解组合优化问题。常用的编码器包括RNN和多层自注意力网络等。

总体而言，图嵌入的方式不考虑待求解的组合优化问题，得到的图表示向量可以通用于求解多种组合优化问题，但是对于待求解组合优化问题而言缺少针对性，影响解的质量。端到端的方式针对待求解的组合优化问题有针对性地学习图表示向量，有利于提高解的质量。但目前的图神经网络深度还比较浅，通常结合注意力机制来提高模型的表达能力。

阶段二：组合优化问题求解

组合优化问题求解也有两种方式。第一种是非自回归方式。该方式只进行一次预测，输出图中的每一个节点或边属于组合优化问题的解的概率。节点或边的概率被输入束搜索等启发式算法来得到组合优化问题的解。第二种是自回归方式。该方式进行多次预测，迭代地对部分解进行扩展，每次迭代预测一个节点或边用以对当前部分解进行扩展。

非自回归的方式大多采用分类模型来一次性地预测图中的所有节点或边属于组合优化问题的解的概率。如，对于图的最小点集覆盖问题，预测所有节点属于最小点集覆盖的概率；对于旅行商问题，预测所有节点属于哈密顿路径的概率；对于最大独立集问题，预测所有节点属于最大独立集的概率等。然后利用贪心法、束搜索等算法来得到组合优化问题的解。

自回归的方式主要分为基于自编码器的方法和基于强化学习的方法。自回归的方式迭代式地对部分解进行扩展，每次向部分解中加入一个节点或者一条边。基于自编码器的方法主要用其解码器预测各个点或边加入部分解的概率。概率最大的被加入到部分解。基于强化学习的方法把部分解建模为状态，把待加入的点或边建模为动作，通过离散型强化学习模型来预测待加入部分解的点或边的Q值。Q值最大的被加入到部分解。

总体而言，非自回归的方式因为只需要进行一次预测，计算的效率较高。但是非自回归的方式假设各个点或边属于解的概率是完全独立的。该假设并不符合序列问题（如旅行商问题）的内在性质，因此在序列问题上所得到的解的质量可能低于自回归的方式。并且，非自回归的方式需要组合优化问题的最优解用作分类的类标，但最优解通常需要指数的计算时间。自回归的方式通过序列化归纳偏置在序列问题上具有较好的效果，也无需事先提供组合优化问题的最优解。但自回归方式的学习效率和样本效率还有待提高。

02

展望

本文展望了基于图学习的组合优化问题求解方法的若干前沿研究方向，包括对图的全局信息进行编码，对特定的组合优化问题专门设计深度学习模型，基于图学习的组合优化方法的泛化性问题，与传统的启发式算法进行融合，以及对多个图的支持等。

作者简介

彭云

香港浸会大学计算机科学系

彭云，香港浸会大学计算机科学系研究助理教授，主要研究方向为图数据处理、图学习、可信数据处理等，已在TKDE、ICDE、IJCAI等国际顶级学术会议上发表十余篇论文。多次担任IJCAI、DASFAA等会议的程序委员会委员、ICDE等会议的审稿人等。

徐建良

香港浸会大学计算机科学系

徐建良，香港浸会大学计算机科学系教授。主要研究方向为数据库、区块链、大数据安全及隐私等，已在这些领域的顶级会议和期刊上发表论文200余篇，获WISE 2019最佳论文、CIKM 2020候选最佳论文、MUST 2021最佳论文。担任TKDE、PVLDB等编委，多次担任SIGMOD、VLDB、ICDE等会议的程序委员会委员。

关于本刊

欢迎扫码进入期刊主页

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

点击“阅读原文”，获取本文英文原文！

版权声明

本文由施普林格∙自然北京办公室负责编译。中文内容仅供参考，一切内容以英文原版为准。如需转载，请联系 [e-mail]

© 2021 Springer, part of Springer Nature. 

All Rights Reserved.