干货！网络推断与数据驱动的影响力最大化问题
点击蓝字
关注我们
AI TIME欢迎每一位AI爱好者的加入！
影响力最大化是指在社交网络中选择少量种子节点，以最大限度地扩大这些种子的影响力，这在过去二十年中已经得到了广泛的研究。在规范环境中，整个社会网络及其扩散参数被作为输入。在本文中，我们考虑更现实的采样设置，其中网络是未知的，并且我们只有一组被动观察级联，记录在每个扩散步骤的激活节点集。我们研究了这些级联样本（IMS）的影响最大化任务，并在种子集分布的温和条件下给出了该任务的常数近似算法。为了达到优化目标，我们还提出了一种新的网络推理方法，即从级联数据中学习扩散参数和网络结构。与以前的解决方案相比，我们的网络推理算法需要较弱的假设，并且不依赖于最大似然估计和凸规划。我们的IMS算法通过允许一个恒定的近似比（即使在扩散参数难以学习时）来增强学习和优化方法，并且我们不需要任何与网络结构或扩散参数相关的假设。
本期AI TIME PhD直播间我们邀请到中科院博士生——张智杰，为我们带来报告分享《网络推断与数据驱动的影响力最大化问题》。
张智杰：
中科院计算所五年级博士生，导师为张家琳研究员。研究兴趣包括组合优化、近似算法、机器学习。最近的研究课题包括次膜优化与影响力最大化。
01
背 景
组合优化领域包含许多非常有趣的问题，比如最大覆盖、集合覆盖、最小/最大割、MST、斯坦纳树，可满足性，背包，箱子包装等。这些问题大都可以定义为下图中统一的形式：
这里我们举一个最大覆盖问题的例子，如下图所示，输入一个二部图，其目标函数是寻找k个左边的点，使得这k个点的邻居尽可能地多。这个目标函数是一个覆盖函数，它在集合S上的取值是其邻居的个数，符合上面定义了组合优化的目标函数形式。
从传统上来讲，目标函数f是已知的，而在大数据时代，目标函数往往是未知的，必须从被动观测的数据中学习。如何学习目标函数也是需要去研究的一个问题，并且有了一整套理论来刻画学习效果的好坏，如下面的两项工作：
但是，我们可以根据用来学习目标函数的数据来优化目标函数吗？下面这项工作提出了一个样本优化模型——OPS，该算法的输入不是目标函数f，而是样本以及其对应的函数值。然后我们要求根据这些样本找到目标函数近似最优解，因为是近似解，因此这个解是常数近似的。在这个工作中，算法只能通过样本被动地知道f(S)的解。
有了上面的理论，一个很自然的方法是先学习目标函数的替代函数，然后去优化这个替代函数。但是这种方法没有理论依据，我们在研究下面两项工作发现，无论样本数据的分布如何，最大覆盖问题无法得到常数近似解。而前人工作已经证明覆盖函数是可学习的，所以说明给定样本数据的函数是可学习的并不意味着是可优化的。
那我们如何避开OPS问题下这种不可近似的结果呢？目前已经有了一些方法去尝试解决这种问题。
02
OPSS 算法
我们提出了Optimization from structured samples（OPSS）方法，假设数据是带结构的，期望从数据中获取更多的信息，从结构化数据中进行优化。通过OPSS，我们希望能得到一个全局最优解。
看下面左图覆盖函数的例子，OPS样本是以样本和函数值作为函数对，而OPSS方法是以样本和其邻居作为函数对。因此在我们的模型中，我们不仅能看到函数值、还能看到覆盖的邻居点是哪些，因此这个样本点是带结构的，给我们的信息更强一些。
另外一个例子是右图的影响力函数，它其实是概率图版本的覆盖函数。影响力函数定义在一个有向图上，这个有向图称为社交网络。图中黄色点是种子集合，表示在初始时携带一些信息，每个点都会以边上定义的概率激活自己的邻居，激活意味着将自己节点的信息传给邻居。影响力函数的目标函数定义为给定初始种子节点
下面是OPSS方法对于不同优化问题的结构化样本定义，
我们所要解决的问题是给定合理的种子集合D，去解决最大覆盖问题和影响力最大化问题。集合D需要满足的假设如下：
03
OPSS算法结果
对于最大覆盖问题的采样方法，OPSS算法的结果如下。在样本分布满足Assumption*下，如果在函数已知时有一个α近似算法，那在OPSS采样模型下就会有一个α/2的近似算法。
下面是我们的方法对于影响力最大化问题的结果。
提
醒
论文链接：
https://arxiv.org/pdf/2106.03403.pdf
点击“阅读原文”，即可观看本场回放
整理：AI Timer
审核：张智杰
直播预告
2月17日 - 3月16日 NeurlPS 专场
近百位NeurlPS一作来分享啦！
记得关注直播信息哦！
往期精彩文章推荐
记得关注我们呀！每天都有新知识！
关于AI TIME
2019年，清华大学人工智能研究院院长张钹院士、唐杰教授和李涓子教授等人联合发起“AI TIME science debate”，希望用辩论的形式，探讨人工智能和人类未来之间的矛盾，探索人工智能领域的未来。
AI TIME是清华大学计算机系一群关注人工智能发展，并有思想情怀的青年学者创办的圈子。AI TIME旨在发扬科学思辨精神，邀请各界人士对人工智能理论、算法、场景、应用的本质问题进行探索，加强思想碰撞，链接全球AI学者、行业专家与爱好者，打造成为全球AI交流与知识分享的聚集地。
我知道你
在看
哦
~
点击 阅读原文 查看回放！