作为一种最常用的数据结构之一,图可以用来表示数据对象之间的复杂关系,广泛的应用于许多领域。因为图的这些优势,基于图的图数据分类是图数据挖掘研究领域的一个重要分支。在实际应用中,每个图数据都会同时具有多个标签集。并且通常在需要处理的多标签数据中,都存在着大量冗余的、不相干的特征数据。对这些数据的处理可能会耗费大量时间,并且降低分类性能。因此多标签数据通常应该先进行特征选取,再进行分类。然而,传统分类方法把主要研究方向放在单标签分类(二分类)问题上,它明确或模糊的假设每一个图只有一个标签。对于单标签分类问题,传统特征选取方法可以扩展并用于找出单标签图数据集中的最具价值的子图特征。但是在多标签分类问题上,每一个图拥有多个标签,多个特征子图集需要挖掘,因此传统特征选取算法无法直接用于多标签特征选择。本文算法根据图的多个标签之间存在某种相关联性特点,基于HSIC(HilbertSchmidt Independence Criterion)评估标准,提出了一种用于评估多标签子图特征集有用性的评估标准。主要研究内容如下:(1)针对在现实应用中,训练图集的子图特征数量非常多的问题。为了避免详细列举子图,从而导致算法时间复杂度过高。我们把评估标准加到子图模式挖掘步骤中,设定一个上界值作为约束,通过约束修剪搜索空间。因此,在第四章我们根据图的多个标签之间的关联性提出了一种上界值的计算方法。(2)针对多标签图数据的特点,即一个样本属于多个类别。提出了一种基于HSIC评估标准的多标签图数据特征选取算法,用来评估样本和标签的相关性。随后将这个评估标准加到子图模式挖掘步骤中,在对搜索空间进行遍历的过程中对子图进行评估,达到特征选取的目的。(3)针对提出的多标签特征选择算法,本文提出了一种交替最优化算法解决算法最优化问题。在算法的目标方程中有子图g和标签权重两个变量,但是前人的研究表明并不存在它的全局最优结果。所以本文采用交替最优化算法,先固定变量对g进行优化,选择最优的t个子图。然后固定变量g对进行优化,在选择的子图基础上对子图标签权重进行优化。将本文提出的特征选择算法分别与二分类器SVM和多标分类器Boos Texter结合,在NCI和PTC数据集上与传统的特征选择方法进行实验对比,实验表明本文提出方法在标签预测中具有更高的准确率和更低的错误率。