【ICML2021】基于数据采样的影响力最大化问题

论文链接：https://www.zhuanzhi.ai/paper/3a1e9a5b1d5014aa139465d7afb57410

基于数据采样的优化（Optimization from Samples，OPS）是将机器学习和优化相结合，实现从数据到优化的端到端的性能保证。然而近期的研究指出，虽然从数据到模型的学习过程和基于模型的优化各自能给出较好的理论保证，但是 OPS 在一些情况下是不能达到端到端的理论保证的。

微软亚洲研究院和中国科学院计算技术研究所的研究员们在去年的 ICML 会议上提出了基于结构化数据采样的优化方法（Optimization from Structured Samples, OPSS），通过巧妙地利用采样数据中的结构化信息，将学习和优化更紧密地结合, 从而达到端到端性能的理论保证。

在今年 ICML 会议上发表的本文，沿 OPSS 方向进一步探索，更进一步研究了比较复杂的基于数据采样的影响力最大化问题（Influence Maximization from Samples, IMS）。具体是指：当社交网络未知，只能观察到其上的历史传播数据时，如何选取少数种子结点以达到影响力最大化的传播效果。传统的方式是先从历史传播数据中学习，得到一个传播模型和模型参数，然后在这套模型和参数上运行成熟的基于影响力最大化的算法。但这样的方法会导致在某些情况下，模型及其参数的学习效果不好时，优化的效果也不尽如人意。因此需要对这种传统模式加以改进，在模型参数学习效果不好时仍能找到替代方法，从而达到良好的优化效果。

从端到端来讲，本文的算法可以保证对于任何网络结构和传播参数的组合，都能从传播数据采样中得到影响力最大化的常数近似解，而且该算法不再依赖于最大似然估计，而是通过简单直接的等式推导，使得网络推断可以基于更宽泛的假设从而达到运算速度更快、需要更少数据样本的效果。同时，在解决 IMS 问题的过程中，网络推断（Network Inference）算法也得到了改进。