在大数据与人工智能深度融合的当下，矩阵补全（Matrix Completion）作为机器学习与数据挖掘领域的核心技术，广泛应用于推荐系统、计算机视觉、社交网络分析等场景。传统矩阵补全方法多依赖矩阵自身低秩特性，对数据背后潜在图结构信息的利用存在诸多局限。近日，西安交通大学管理学院智能决策与机器学习研究中心王尧教授与王开东副教授团队在图结构数据补全研究方向取得新进展，提出一种名为“Graph-regularized Scaled Gradient Descent”的非凸优化算法，为解决复杂数据关联下的矩阵补全难题提供了新方案。

随着互联网平台与智能信息系统的快速发展，其产生与积累的大规模数据日益呈现出稀疏且结构缺失的复杂特征。如在电影推荐系统中，用户通常只对少数电影进行评分，平台需要根据有限的评分信息预测用户对其他电影的偏好；在社交网络中，用户之间只建立了部分可观测的关系，系统需要进一步预测潜在的用户连接关系。这类问题通常可以抽象为矩阵补全问题，即在仅观察到部分矩阵数据的情况下恢复完整的数据结构。

电影推荐系统中的图结构示意

而在实际场景中，数据之间往往存在天然的结构关联，如兴趣相似的用户通常表现出相近的评分行为，社交网络中的用户之间也通过关系连接形成复杂的网络结构。这些关联关系通常可以表示为图结构信息。然而，现有多数方法主要依赖图拉普拉斯正则化来利用图结构信息，该方法通常只刻画相邻节点之间的局部相似性，难以捕捉更复杂的长程关联关系。同时，现实网络中往往包含噪声连接或错误边，传统方法对此较为敏感，容易影响恢复效果。此外，相关算法在理论层面普遍缺乏系统的统计与计算复杂度分析，使得算法在何种条件下能够稳定、高效地恢复数据仍缺乏明确的理论保证。

针对上述难题，西安交通大学管理学院智能决策与机器学习研究中心王尧教授与王开东副教授联合博士研究生杨一扬，以及高山行教授、廖貅武教授共同开展相关研究。该研究团队提出了一种名为GSGD（Graph-regularized Scaled Gradient Descent”的非凸优化算法。该方法基于预条件投影梯度下降框架，通过在优化过程中引入图结构信息，实现对缺失数据的高效恢复，并在理论上给出了线性收敛速率和近乎最优样本复杂度的严格保证。

与传统依赖图拉普拉斯正则化的方法不同，该研究通过构建基于图拉普拉斯矩阵逆的高阶图矩阵刻画节点之间的关联关系，从而能够同时利用直接连接信息和图结构中的长程关联，提高对图结构信息的利用效率。在此基础上，研究团队提出了基于预条件投影梯度下降的 GSGD 算法，实现了对图结构信息的高效融合，并在理论上首次从非凸优化视角为图正则化矩阵补全方法建立了统计与计算复杂度的双重保证。一系列合成数据与真实数据实验进一步表明，GSGD 在恢复精度、计算效率以及对噪声边的鲁棒性方面均优于现有主流方法，在推荐系统与社交网络等场景中展现出显著优势与广阔应用前景。

GSGD算法与对比算法在不同采样率的恢复精度对比

该研究成果以“耦合图结构信息的矩阵补全：一种具有理论保证的非凸优化方法”（Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach）为题，在运筹学与管理科学顶级期刊 INFORMS Journal on Computing 在线发表，为大数据时代的数据处理与分析提供有效工具，有助于推动人工智能技术的实际应用落地。王尧教授为论文第一作者，王开东副教授为通讯作者，西安交通大学管理学院为论文第一完成单位与通讯单位。

全文链接：https://pubsonline.informs.org/doi/epdf/10.1287/ijoc.2025.1169