机器学习已在很多现实任务中取得了成功。成功背后往往依赖于充分的标注数据。然而,在现实任务中,标记数据的获取困难,数据产生的速度远大于数据标注的速度。不依赖充分标记数据的机器学习框架——半监督学习更为贴近现实任务,但其建模也更加困难。标记传播是半监督学习的主流范式,基于流型假设(同属一个流型的数据具有相同的标记),利用数据内在图结构信息,使数据标记在未标记数据中进行有效传播。虽然标记传播已经得到很多的研究,然而,还存在两个主要的瓶颈问题。其一是标记传播的计算效率问题。标记传播涉及到图结构的矩阵操作,计算和存储开销居高不下,难以适应大型图结构数据;其二是标记传播的性能保障问题。标记传播对图结构的选取敏感,选取不当造成性能不稳乃至严重下降,难以适于可靠性要求高的应用场景。本论文围绕着两个问题,主要取得了如下新进展:1.针对标记传播的计算效率问题,提出高效可扩展的随机标记传播算法SLP。该算法将标记传播目标函数分解为数据节点的损失函数之和,从而可以桥接现有高效随机优化算法的优势加以求解。理论上保证SLP的收敛性和逼近能力。实验上SLP在百万个点,千万条边的图结构上比现有方法加速了5倍以上。值得一提的是,本文方法可以灵活地吸收随机优化算法的新进展不断优化改进。2.针对标记传播的性能保障问题,提出安全图构建算法Sagraph。该算法仅利用数据分布中的稠密区域来构建图结构,可以有效地避免有风险的未标记数据及其图结构。算法采用集成学习的思路,对多个基图进行权值优化。实验结果表明,Sagraph有效提升图构建的安全性,并可解释基图对安全图的影响。除此之外,还在此基础上完成了安全半监督学习的综述。