图作为一种结构化的信息表示形式,在模式识别领域中日益得到广泛重视。图嵌入方法结合统计学习理论中向量空间的优势,将图嵌入至一定维数的向量空间,通过向量空间的相似性度量方法搭建了从结构模式识别问题到统计模式识别问题的桥梁。图的编辑距离是一种任意结构和任意标记图之间的非相似性度量,而传统的树搜索算法计算图编辑距离需要指数级的算法复杂度。随着训练样本集规模的增加,直接导致图嵌入时的特征向量的维数大幅上升,产生“维度灾难”,且特征向量中包含了大量冗余和噪声,因此,在确保模式识别的精度前提下,快速的编辑距离计算算法和降低图嵌入维度的原型选择方法设计,是当前图匹配研究领域的研究热点与难点问题之一。本文针对上述两方面的问题进行展开,主要研究工作如下:(1)通过研究与比较现有的基于原型选择的图嵌入方法,设计出一种以编辑距离度量为基础,采用训练样本每一类内聚合和与其他类相远离的策略,构造出较好区分各类的原型图,并通过实验证实了该方法的效能。(2)针对上述策略选取的原型未能考察类内选取的原型对类之间的相互影响,设计出一种改进的采用训练样本每一类的类内和其他类的进行均衡化处理的原型选择方法,实验表明,该方法选出了对分类效果明显的原型集。(3)通过分析传统的树搜索编辑距离算法,它的效率随着图的规模呈指数级增加,采用了一种快速的编辑距离计算算法,设计出一种利用图之间的属性计算定义代价函数。实验结果表明,本文设计的原型选择方法和编辑距离算法可以有效地降低特征向量的维度,并有效改善图嵌入下的模式识别精度。