一、基本信息

论文题目：《Incremental Subgraph Feature Selection for Graph Classification》

发表时间：

论文作者及单位：

论文地址：https://ieeexplore.ieee.org/abstract/document/7588124/authors#authors

 

二、摘要

        图分类是分析具有结构依赖性的数据的重要工具，其中子图通常用作学习功能。在现实中，子图的维数至关重要地依赖于频率支持参数的阈值设置，并且数目可能变得非常大。因此，可以逐步发现子图以形成特征流，并要求底层图形类更有效地从子图特征流中发现具有代表性的子图特征。本文提出了一种基于最大边缘图分类的原始双增量子图特征选择算法。ISF算法构造了一系列既原始又对偶可行的解。每对原始对偶都缩小了对偶间隙，为最优子图特征集提供了更好的解。为了避免ISF算法对短模式子图特征的偏见，我们提出了一种新的增量子图连接特征选择算法（ISJF），通过强制图类连接短模式子图并生成长模式子图特征。我们评估了所提出的模型在合成网络和现实社会网络数据集上的性能。实验结果证明了该方法的有效性。  

 

三、论文主要工作与内容

1 Introduction

        图分类是社会网络和生物数据分析的重要工具，其目的是学习和分类图结构中表示的目标。例如，化合物可以用图形表示，预测化合物在生物测试中的活性是已知的图形分类问题。与特征向量表示的数据分类相比，图形数据分类面临的主要挑战是图形没有现成的特征，因此现有的分类模型不适用。因此，对频繁子图[3]、[4]作为特征进行挖掘，并通过对所选子图的出现情况进行检测，将其转化为特征向量，是目前研究的热点。
实际上，子图的数量关键取决于频繁模式挖掘阈值的设置。如果阈值非常小，子图的维数可能非常大。例如，在社会网络中的级联暴发预测[36]中，每个级联数据记录都可以被视为描述社会网络中信息传播路径的非循环图。在图1中，两个定向网络（分别具有绿色和黄色节点）显示两个级联。虽然两个级联都是从种子节点开始的，但是具有绿色节点的级联传播到大量节点（即标记为爆发的图），而具有黄色节点的级联则保持稳定或可能消亡（即标记为未爆发的图）。然后，图表分类可用于级联暴发预测，以从非暴发级联中识别暴发级联。一般的思路是通过频繁的子图模式挖掘来提取子图作为特征。

当挖掘子图作为特征时，频繁子图的数目对支持参数的设置很敏感。如图2所示，子图特征的维数随频繁模式阈值参数supp的减小呈指数增长，例如，当参数为50时，发现的子图特征数大于8*10^5！

高维或潜在的内部子图特征的现实促使选择少量具有代表性的子图特征。在机器学习中，高维特征是一个常见的挑战，大量的特征选择模型[28]、[9]、[29]被提出以降低数据维数。但是，这些模型无法处理内部子图功能。
文献中提出了子图特征选择[2]、[5]的概念，将子结构挖掘和特征学习结合在图数据中。例如，使用频繁的子结构挖掘方法，如a g-m[3]和gspan[4]来枚举频繁出现的子图模式，每个子图对应一个特征，因此现有的机器学习方法（如svm）可以应用于转换后的特征空间。然而，这些工作只能处理从小图中提取的低维子图特征。例如，最近的一项研究[5]在实验中只使用了4337个子图特性。因此，现有的方法不适用于大图数据，如社会网络级联数据，其中连接的子图数量可能非常大。

在线增量特征选择[6]最近被提出用来从高维特征流中选择特征。例如，最近的一项工作[ 9 ]涉及选择增量特征的信息容差，并提出了一种选择文件上强相关和非冗余特征的方法。然而，该方法也不适用于子图模式挖掘和增量特征选择的挑战错综复杂的增量子图特征。此外，[ 9 ]中的方法假设关于特征空间结构的先验知识是先验已知的，因此可以应用启发式规则。这一强有力的假设在一般的图表和社交网络环境中也不成立。

2、挑战

基于上述观察，我们的研究主要旨在解决以下挑战:
如何从具有高维子图特征的图中建立分类器，以及如何设计有效的算法来快速解决图的分类。特征的高维数量使得现有的分类要么不适用，要么无效。已经提出了许多特征选择模型来通过过滤器、包装器或嵌入方法选择稀疏特征。然而，这些特征选择方法在高维子图特征空间中是不够的。例如，当使用l1正则化时，需要1 TB内存来存储1012个特征的特征系数。
如何连接短模式子图并设计一个更喜欢选择长模式子图特征的特征选择模型。我们观察到，由于频繁子图挖掘算法[ 37 ]，[ 44 ]的向下闭合特性，特征空间由短模式子图支配，即短模式子图特征总是比长模式感兴趣子图更频繁。为了发现隐藏在大量短模式子图下的长模式子图，我们需要系统地设计一种新的特征选择方法。通常，采用频率支持阈值的小值，使得所有候选子图都可以保留在特征空间中。然而，这种方法将不可避免地生成指数数量的短模式子图，这些子图提供了有趣的长模式子图特征。虽然有许多可能的方法来连接短模式子图，但是为了有效的计算，需要建立子图片段之间的连接规则。需要新的约束来强制传统的基于最大边距的图分类器选择长模式子图特征。
如何评估所提出方法的性能？现实世界和合成数据集都需要将所提出的方法与现有方法进行比较。

3、在本文中，我们旨在解决从高维子图特征空间中为最大容限图分类选择区分子图特征的问题(第4.1节)。我们的研究使用原始-对偶子图特征选择来扩展最大容限图分类器，以处理高维增量子图特征，该子图特征选择连续选择原始和对偶可行的子图特征(第4.2节)。由于原始对偶子图特征选择算法收敛速度快，倾向于选择短模式子图，我们进一步提出了一种长模式驱动的子图特征选择模型，用于选择感兴趣的长模式子图(第4.3节)。在实验中，我们在合成数据集和真实数据集上测试这些方法。结果表明，该算法既能解决增量子图特征问题，又能选择有区别的长模式子图特征。
该论文的主要贡献有三个方面:

• 我们研究具有增量子图特征的图分类问题。我们首先提出了一个通用的最大容限图分类器，在此基础上我们提出了一个原始对偶增量子图特征选择算法。增量算法构造了一系列既原始又对偶可行的解。每一对原始对偶缩小了原始对偶的差距，并向最优解提出了更好的解决方案。
• 我们提出了一种新的增量子图连接特征选择算法。ISJF在最大裕度图分类器上添加了一个新的约束，并通过连接短模式子图特征来强制分类器选择长模式子图。
• 算法的性能在四个合成网络和两个真实网络( DBLP图形数据和社交网络级联数据集，共276万个信息级联)上得到验证。结果表明，该增量算法具有早期预测的优点，比现有级联爆发预测模型快400秒以上。

 

四、总结

本文研究具有增量子图特征的图分类。基于子图特征遵循向下闭包的特性，长模式子图特征经常隐藏在短模式子图特征之下的观察，提出了一种挖掘增量子图特征的原始对偶增量子图特征选择算法，以及一种精确长模式子图的子图连接特征选择算法。社交网络中真实世界的级联爆发预测实验验证了所提模型的有效性。