关系在现实世界中无处不在。在机器学习研究领域,数据中有两类关系不容忽视:1)样本之间的关系;2)标记之间的关系。大量研究结果表明,对这两类关系的合理利用对提升训练模型的预测能力至关重要。基于图的方法是关系利用的一类主流范型。这方面的代表性工作获得了国际机器学习领域十年最佳论文奖。经过十余年的研究,基于图的方法已取得了许多成果。然而,其学习性能严重依赖于图的构建。现实任务中,图构建通常难以有效确定,使得学习性能的鲁棒性不佳,有时还会出现性能的损害。本硕士论文围绕提升关系利用的鲁棒性这一重要问题展开研究,主要取得了以下创新成果:第一,针对样本关系利用对图构建敏感的问题,提出了基于大间隔准则的图质量判断方法。该方法将鲁棒样本关系利用这一难题形式化为经典半监督支持向量机框架。优化上给出高效的求解算法。实验结果表明,该方法显著提升样本关系利用的鲁棒性,有效避免传统方法会导致性能退化的现象。本论文还进一步将大间隔准则拓展用于带噪样本关系,提出了高效学习算法,有效防止带噪样本关系对性能的危害。第二,针对标记关系利用对图构建敏感的问题,提出了基于分类器构圈的标记关系利用方法。该方法通过将分类器以圈形式构建,克服了传统学习方法在标记关系利用中分类器次序对性能的严重影响。论文分析了该方法的时间复杂度与传统方法相当,不显著增加计算开销。实验结果表明,该方法显著提升标记关系利用的鲁棒性,有效避免传统标记关系利用方法会导致性能不佳的现象。