机器学习是近二十多年来发展起来的一门新兴学科，在当今的人工智能领域占有着举足轻重的地位。其研究目的是设计计算机算法从已有的数据中总结、提取出一定的普适规律，以便对未来的数据进行处理和分析。机器学习是计算机科学、统计学、认知科学等多个领域的交叉学科，并且在公共安全、国防建设、生物医学等方面获得了广泛的应用。　　作为机器学习的一种重要方法，图推断是指基于一个带权图，算法能够给未标记样本直接分配明确的标签，而不是基于已有的已标记样本建立一个普适的决策函数。另外，由于在很多情况下先验知识比较难获得，因此本文主要研究如何直接根据已有数据设计不依赖于先验知识的数据驱动的图推断算法。具体地，本文提出了一系列的迭代或者非迭代的图推断算法，介绍如下：　　在第二章中，提出了一种非迭代算法——“基于变形拉普拉斯矩阵的标签预测”（Label Prediction via Deformed Graph Laplacian，LPDGL）。现有的算法多采用传统的拉普拉斯矩阵去实现成对样本间标签的光滑性，与之不同的是通过在LPDGL中引入变形拉普拉斯矩阵，算法不仅获得了现有的成对样本光滑项，而且还导出了一种全新的局部光滑项。这个局部光滑项通过使用样本的“度”来检测其标签的不确定性，然后给度大的样本施加置信的标签，而给度小的不确定样本分配较弱的标签，进而使设计的算法能够产生比现有典型算法更鲁棒的推断结果。尽管LPDGL最初被设计用来做图推断，但它经过简单的扩展后同样可以处理图归纳问题。　　在第三章中，设计了一种迭代的标签传播算法用于图推断，即“基于菲克定律的标签传播”（Fick’s Law Assisted Propagation，FLAP）。具体来说，FLAP把标签在图上的传播视为实际流体在一个平面上的扩散，进而根据著名的菲克流体定律设计了一种新的标签传播算法。现有的机器学习算法多基于一些启发式的准则，而FLAP则通过一种更“自然”的方式实施标签传播，即一个样本什么时候需要传播多少标签，这些标签需要向哪里传播，都是根据物理定律自然地决定的。因此，FLAP不仅可以产生更准确的传播结果，而且比现有的迭代算法需要更少的计算时间。　　在第四章中，提出了一种新的标签传播框架——“导学与导教”（Teaching-to-Learn and Learning-to-Teach，TLLT）。在这个框架里，本文引入“老师”（即一种指导机器学习的导学算法）去指导标签传播。现有的传播方法都是平等地看待所有未标记样本，而 TLLT认为不同的样本具有不同的分类难度，而且它们的传播需要遵循由易到难的顺序。这样做的好处在于之前学习的简单样本可以降低后续学习复杂样本的难度，进而有利于对这些难的样本实施正确的分类。在每一次传播的过程中，老师要给“学生”（即标签传播算法）指定当前最简单的样本。当学生“学完”这些简单的样本后，老师会从学生那里获取学习反馈以制定合适的下一轮待学习样本。正是由于这种交互式的教与学的过程，所有未标记样本都按照精心制定的合理顺序被传播，因而所设计的方法可以获得比其它方法更好的性能。　　在第五章中，本文将第四章提出的TLLT框架用于显著性检测，以便按照由易到难的顺序决定所有图像区域的显著值。其中每个图像区域的难度由其信息性、个体性、非均匀性及连通性决定。因此，所提出的显著性检测算法能够产生更清晰的显著性图，并在一些典型的公开数据集上获得了优于其它方法的实验结果。