机器学习的一项重要任务是对先验知识的表达和利用,除了类标记和成对约束等监督信息外,样本的空间结构也是先验知识的重要表现形式之一。近年来,得益于其对局部结构的刻画能力以及与经典方法(如正则化技术、核方法、谱图理论)的紧密联系,利用图来逼近数据间的局部流形的方法受到了研究者的大量关注。其中,基于图的半监督学习方法由于能同时利用部分有标记样本和大量无标记样本来提高学习性能,成为机器学习领域的研究热点之一。本文在分析了基于图的半监督学习的发展现状和现存问题的基础上,从图的构造和图的优化两大方面入手,围绕半监督图学习在分类、聚类和降维等典型任务中的应用进行了研究。论文的主要研究工作和创新点如下：1、提出了一个融合局部几何信息与全局判别信息的正则化框架。该框架具有一定的宽泛性,可通过选择不同的损失项和正则化项,推广到其他半监督分类算法的改进。作为该框架的一种具体实现,提出了局部敏感的判别直推学习方法,该方法在正则化框架中同时引入了有助于分类的样本局部结构信息和判别信息,从而最大程度地利用样本内蕴信息,能在每个局部邻域中进一步最大化类间样本的间隔。2、提出了一种利用先验知识来同时指导数据降维和聚类的方法。该方法构造成对约束信息的k-最近邻集并扩充成对约束集,分析成对约束实例包含的信息量并构造权系数矩阵,在加权成对约束信息的指导下求得投影矩阵,通过投影矩阵将样本数据投影到低维空间,使类内各点紧密分布,类间各点分散分布。同时,该方法通过一种新的评价函数对k-均值聚类算法进行了改进,能够在尽量不违反成对约束的情况下优化聚类性能。3、提出了一种基于结构和约束保持的半监督特征选择方法。针对特征排序选择算法在处理高维数据问题时存在的一些不足,通过引入以成对约束形式表现的监督信息,并借助流形学习的思想,提出一种能同时保持样本空间结构和监督信息的半监督特征选择方法。该方法同时考虑样本的局部和非局结构,融合成对约束信息,定义了一种新的特征评价准则——结构约束保持分(SCP Score)。结构约束保持分利用大量的未标记样本来学习样本空间的流形结构,利用少量的成对约束信息来学习样本的类内和类间边缘,所选择的特征子集较好地保持了空间结构信息和类属信息。4、提出了一种基于图随机游走的直推学习模型。首先将以Agent表示的样本点随机映射到格网表示的输出空间中,构成初始空间格局,空间格局随时间演化的过程是一个自组织的马尔可夫过程,它将在有限时间内达到平稳分布,从而求得最佳的标记分布,并从数学上分析了算法的性质。