文章导读
面对推荐系统或社交网络中大量缺失的数据，你是否还在依赖传统的低秩假设强行补全？大多数方法仅关注局部相似性，不仅难以捕捉长程关联，更对噪声连接极度敏感，导致恢复结果偏差巨大。西安交大团队最新提出的GSGD算法，通过构建高阶图矩阵彻底打破了这一僵局，首次从非凸优化视角给出了严格的理论保证。在合成与真实数据的双重实测中，它为何能同时实现精度、效率与抗噪性的全面碾压？这个被顶级期刊认可的新方案，究竟如何重新定义了数据补全的边界？
— 内容由好学术AI分析文章内容生成，仅供参考。
在大数据与人工智能深度融合的当下，矩阵补全（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
© 版权声明
本文由分享者转载或发布，内容仅供学习和交流，版权归原文作者所有。如有侵权，请留言联系更正或删除。
相关文章
太贵了吧这也，一个算法发顶刊，我们调参狗泪目😭
之前搞过推荐系统，图结构这块确实头疼，想问下GSGD在稀疏图上表现咋样？
这算法听着挺玄乎，实际用起来真能比现有方法快？