文本挖掘、计算生物学、生物信息学和计算化学等领域伴随科学技术的发展产生了大量的图数据,图挖掘方法能够有效地分析和挖掘这些图数据,深入理解其所蕴含有价值的信息。图分类作为图挖掘领域的一个重要研究分支,通过学习已知类别图数据建立分类预测模型,实现对未知类别图数据的自动分类。图相似度度量对图数据的准确分类起着重要的支撑作用,成为图数据分类研究的重点。图相似度度量方法考虑的图信息越多,度量的准确性越高,但时间复杂度也随之增高。如何考虑更多的图信息,提高分类准确性以及降低时间复杂度成为图相似度度量研究的关键。目前图相似度度量方法主要有:随机路径图核、最短路径图核、公共路径图核和W-L子树核,通过计算两个图的公共路径数和公共子树数度量相似度。上述方法度量了顶点标号信息,未考虑顶点与其所有邻接顶点间边的连接关系,时间复杂度在O(n3)到O(n4)之间,且仅度量两个图的相似度。针对以上问题,本文围绕如何提高度量的准确性、降低时间复杂度和对多图相似度度量展开研究,具体工作如下:对两个图进行相似度度量的研究如下:(1)针对公共路径图核方法中初始tickets矩阵的冗余计算问题,提出了一种改进的简化算法。简化算法减少了大量的矩阵相乘和相加运算,能够快速地得到稀疏图和稠密图的初始tickets矩阵。实验表明,简化算法相比于公共路径图核方法,解决了初始tickets矩阵中元素值的冗余计算问题。同时,当图的数据集分类级别较大时,简化算法提高了分类准确性。(2)为了度量更多的边信息、提高图数据分类的准确性,提出了基于垂直维序列和层次序列的图相似度度量算法。这两种算法将图等价地转换为广义树,并将其表示为垂直维序列和层次序列,考虑了顶点的入度和出度信息,体现了顶点与其所有邻接顶点间边的连接关系。实验表明,基于垂直维序列算法,可以保留图的路径信息,并体现图自上而下的垂直结构特性,从而提高图数据分类的准确性;另外,基于层次序列算法全面地反映了图的层次结构特性,并在运行时间上优于其他度量方法。(3)为了度量更多的路径信息,提出了将图转换为多维序列的相似度度量算法。多维序列保留了图中顶点间的指向关系,体现了图中顶点间更多的路径信息,通过计算多维序列的所有公共子序列数和最长公共子序列的长度度量图的相似度。实验表明,与现有图核方法相比,多维序列算法充分度量了图中更多的路径信息,从而具有高的分类准确性。对多图进行相似度度量的研究如下:(4)针对多图相似度度量复杂度高的问题,提出了可以同时度量多图的相似度算法。多图转换为多重序列,并在多维矩阵中计算多重序列的匹配点,同时采用启发式算法计算匹配点上的所有公共子序列数,进而完成多图的相似度度量。通过算法分析和理论证明,提出的算法不仅可以同时度量多图的相似度,且将时间复杂度由O(n~3)降至O(n~2)。