🤖 machine learning

Learning Peer Influence Probabilities with Linear Contextual Bandits

本文通过引入一个刻画了遗憾最小化与估计误差之间基本权衡的上下文线性老虎机框架，并提出一种不确定性引导算法以实现该频谱上的最优性能，解决了在网络化环境中学习异质同伴影响概率的挑战。

原作者： Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

发布于 2026-06-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一家大型社交俱乐部的经理，这里的会员不断地向朋友分享新闻、产品或创意。你的目标是弄清楚谁在影响谁。爱丽丝（Alice）的推荐是否让鲍勃（Bob）买了一部新手机？查理（Charlie）的发帖是否让戴夫（Dave）去听了一场音乐会？

问题在于，影响力是非常难以捉摸的。有时候人们分享东西是因为他们本身很相似（同质性），而不是因为其中一人真的说服了另一人。如果你只是观察自然发生的情况，你就无法区分“爱丽丝说服了鲍勃”和“爱丽丝与鲍勃恰好喜欢同样的东西”。

为了解决这个问题，这篇论文的作者提出了一种通过主动测试这些影响概率的新方法，就像科学家进行实验一样，而不是仅仅进行观察。

以下是该核心思想的拆解，通过简单的概念进行说明：

1. 两个冲突的目标（“拔河比赛”）

研究人员发现，你无法鱼与熊掌兼得。你陷入了一场拔河比赛，在两个目标之间挣扎：

目标 A：做一个优秀的销售员（最小化遗憾值/Regret）。 你希望把推荐展示给那些现在最有可能说“是”的人。这能实现即时成功最大化。
目标 B：做一个优秀的侦探（最小化估计误差/Estimation Error）。 你希望学习出所有人真实的实际影响概率，甚至是那些很少说“是”的人。为了做到这一点，你必须去测试那些你不确定的人，这意味着你可能会错过一些即时的销售机会。

类比： 想象你是一位试图弄清楚哪些学生能通过考试的老师。

如果你只给那些表现已经很优秀的同学做模拟测试（目标 A），你会立刻获得很高的分数，但你永远无法得知那些表现挣扎的学生是真的掌握了知识，还是仅仅需要更多帮助。
如果你强迫每个学生都参加模拟测试，包括那些通常表现不佳的学生（目标 B），你会得到一张完美的关于谁掌握了什么的地图，但你的班级平均分（你的“遗憾值”）会下降，因为你把时间花在了测试那些并不需要测试的人身上。

论文在数学上证明了：没有任何单一策略能够同时完美地实现这两个目标。 你必须做出选择并寻找平衡。

2. 解决方案：“影响力上下文多臂老虎机”（InfluenceCB）

作者构建了一个名为 InfluenceCB 的智能系统，它就像一个灵活的开关。它允许你通过调节旋钮来决定你更看重成为“销售员”还是“侦探”。

旋钮（参数 $\beta$ ）：
- 如果你将旋钮转向**遗憾值（Regret）*一侧，系统就会表现得像一个谨慎的销售员。它主要向它认为*会说“是”的人展示推荐，以保持较高的即时成功率。
- 如果你将旋钮转向 **RMSE（误差）**一侧，系统就会表现得像一个好奇的侦探。它会故意向那些不确定或表现较低的人展示推荐，以收集更多数据并了解真相，即使这意味着会减少一些即时的“是”的回答。
不确定性测量器： 系统会不断检查：“我对这段友谊有多不确定？”如果不确定性过高，它就会强制进行实验（探索）；如果它很有信心，它就顺其自然（利用）。

3. 他们是如何测试的

他们不仅仅是靠猜测；他们在真实的社交网络数据（如博客、照片分享网站和 Twitter 网络）上运行了模拟实验。他们创建了一个已知“真实”影响概率的虚拟世界，然后让他们的算法尝试去学习。

结果：

旧方法（静态方法）： 这些方法就像是在看一张过去的相片。它们在猜测方面还不错，但无法学习新事物。
标准的多臂老虎机（Standard Bandits）： 这些像是只跟最受欢迎的人说话的销售员。它们能获得良好的即时结果，但对整个网络的理解非常模糊。
他们的算法（InfluenceCB）： 这是最终的赢家。通过调整旋钮，他们可以绘制出一条完美的曲线（称为帕累托前沿/Pareto frontier）。
- 如果客户想要最好的即时结果，InfluenceCB 能在保持学习的同时提供最佳结果。
- 如果客户想要最准确的影响力地图，InfluenceCB 能在获得尚可结果的同时，提供最准确的地图。

4. 核心结论

这篇论文的主要贡献在于证明了学习影响力是一种平衡的艺术。你不能只优化即时利润并期望能学到真相，你也不能在不损害表现的情况下尝试学习一切。

他们的工具 InfluenceCB 为你提供了方向盘。它让你决定在任何给定时刻，你究竟想要多少程度的探索（学习）与利用（获利），从而确保无论你是进行病毒式营销活动，还是仅仅想了解信息如何在社区中传播，都能获得最符合你需求的最佳结果。

简而言之： 他们构建了一个聪明的算法，这个算法知道自己不可能在所有方面都做到完美，因此它让你能够精确选择在某一领域牺牲多少完美度，以换取在另一领域的完美表现。

技术摘要：利用线性上下文多臂老虎机学习同伴影响概率

1. 问题定义

本文研究了在网络化环境中学习**异质同伴影响概率（heterogeneous peer influence probabilities）**的挑战。在社交网络中，用户（接收者）在收到来自另一用户（发送者）的推荐后采取行动的概率，会根据节点属性、边特征以及网络结构而显著变化。

作者将此问题形式化为一个**双目标上下文多臂老虎机（bi-objective contextual multi-armed bandit, CMAB）**问题。该设定涉及一个代理（agent）在 $T$ 轮内与一个有向属性网络 $G=(V, E)$ 进行交互。在每一轮中：

代理观察一组候选边（交互）。
代理选择 $k$ 条边作为干预对象（例如，向特定的一组接收者展示某条帖子）。
代理观察二元奖励（激活：如果接收者采取行动，则为 1；否则为 0）。

核心难点在于平衡两个相互冲突的目标：

最小化累积遗憾（ $Regret_T$ ）： 通过选择具有最高估计影响概率的边来最大化即时奖励（利用/exploitation）。
最小化估计误差（ $RMSE_T$ ）： 准确估计网络中所有边的真实影响概率，包括那些低概率或高不确定性的边（探索/exploration）。

论文指出，标准的在线学习方法要么通过随机探索浪费资源（导致低遗憾保证），要么仅针对奖励进行优化，从而导致低概率边的估计误差较高。相反，静态方法无法将真实的潜在影响与同质性（homophily）等混杂因素区分开来。

2. 方法论：影响上下文老虎机（$InfluenceCB$）

作者提出了 **$InfluenceCB $** 框架，旨在应对遗憾与估计误差之间的权衡。该方法运行在一种线性奖励模型下，其中具有上下文向量$ X $的边的期望奖励为$ E[r] = X^\top \theta^ $，其中$ \theta^$ 是一个未知的参数向量。

关键组件：

不确定性引导的探索：
- 算法使用标准的线性老虎机不确定性度量来计算候选边的估计不确定性： $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$ ，其中 $V_{t-1}$ 是观测特征的正则化协方差矩阵。
- 如果当前候选池中的最大不确定性超过了动态阈值（ $C_t / t^\beta$ ），算法进入探索阶段，选择具有最高不确定性得分的前 $k$ 条边。这确保了对低概率或不确定性高的边进行采样，以改善全局估计。
奖励引导的利用：
- 如果不确定性低于阈值，算法进入利用阶段。
- 它采用标准的线性 CMAB 子程序（例如 CombLinUCB）来选择能够最大化即时预期奖励的边，从而最小化遗憾。
权衡控制：
- 参数 $\beta$ ： 控制权衡的渐近速率。较低的 $\beta$ （如 0.25）优先考虑遗憾最小化，而较高的 $\beta$ （如 0.5）则优先考虑估计准确度（RMSE）。
- 参数 $C_t$ ： 一个基于激活率或不确定性统计数据随时间学习的自适应阈值，允许系统动态调整探索与利用之间的平衡。

3. 理论贡献

论文提供了严谨的理论分析，确立了该问题的基本极限：

权衡的存在性： 作者证明了没有任何单一算法能同时实现累积遗憾和全局估计误差的最优速率。
可实现的速率对： 他们刻画了可实现的帕累托前沿（Pareto frontier）速率。具体而言，对于任何策略 $\pi$ $π$ ，如果遗憾规模为 $O(T^{2\beta})$ $O (T^{2 β})$ ，则 RMSE 必须规模为 $\Omega(T^{-\beta})$ $Ω (T^{- β})$ ，其中 $\beta \in [1/4, 1/2]$ $β \in [1/4, 1/2]$ 。
- 最优遗憾（ $\beta=1/4$ ）意味着次优的 RMSE（ $\Omega(T^{-1/4})$ ）。
- 最优 RMSE（ $\beta=1/2$ ）意味着线性遗憾。
可实现性： 定理 5.1 表明，$InfluenceCB $可以通过调节参数$ \beta$ 来达到帕累托前沿上的任何一点，满足以下界限：
$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$

4. 实验结果

作者在三个源自真实网络的半合成数据集上评估了 $InfluenceCB$：BlogCatalog、Flickr 和 Hateful (Twitter)。真实的影响概率是基于节点和边特征的线性组合通过合成生成的。

基准模型：

静态模型： 随机（Random）、相似度（Similarity）、链路预测（Link Prediction）（包括 Ridge, GraphSAGE, NCNC）以及最先进的推荐系统（ContextGNN）。
在线学习： 基于 SGD 的利用和探索变体。
上下文老虎机： LinUCB、EENet、图神经网络老虎机（GNB）以及 Takemura 等人的组合半老虎机（combinatorial semi-bandit）。

主要发现：

帕累托前沿的扩张： $InfluenceCB$ 扩展了所有基准模型的帕累托前沿。虽然标准的上下文老虎机（如 LinUCB）优化了遗憾，但它们的估计误差较高。静态模型在两个指标上表现均较差。
可调权衡： 通过调整 $\beta$ ，$InfluenceCB$ 可以通过牺牲一定的遗憾来显著降低 RMSE（在 Flickr 上降低约 60%），或者通过略微增加 RMSE 来最小化遗憾（优于 LinUCB 约 5-10%）。
参数敏感性： 参数 $C$ （阈值）显著影响权衡。 $C$ 的自适应学习使得算法能够在无需针对特定应用需求进行手动调优的情况下找到平衡。
鲁棒性： 该方法在不同的网络设置（基于网络的边选择 vs 基于邻居的边选择）下，在排名指标（NDCG@k）和校准误差（ECE）方面保持了竞争力的表现。

5. 重要性与主张

论文声称，它是第一个明确将学习同伴影响概率作为一个独立的双目标问题进行形式化定义的，这区别于那些假设概率已知或作为次要任务的影响力最大化或推荐任务。

理论洞察： 它确立了在网络化老虎机设置中，最小化遗憾和最小化全局估计误差是根本冲突的目标，这一权衡在之前的特定语境下尚未被刻画。
实际效用： 该框架允许从业者根据其应用优先级显式地选择策略。例如，病毒式营销活动可能会优先考虑遗憾（即时销售），而政策审计或扩散模拟则可能优先考虑 RMSE（准确的全局影响图谱）。
局限性与未来工作： 作者指出，他们目前的分析假设了独立的伯努利激活，并且没有对复杂的干扰效应进行建模（例如，来自多个邻居的累积暴露）。建议未来的工作将该框架扩展到非线性设置以及动态或部分观测的网络。

总之，$InfluenceCB$ 提供了一种原则性的机制，用于处理学习准确的影响模型与最大化即时网络干预之间的紧张关系，为网络化决策提供了一个灵活的工具。