Causal Influences over Social Learning Networks¶
作者: Mert Kayaalp, Ali H. Sayed
来源: JMLR
主题: 因果推断
相关性: 5/10
机构绿灯: École Polytechnique Fédérale de Lausanne(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是"网络上的因果推断",其根本科学问题是:在个体(agent)通过社交图相互连接并随时间交互的动态系统中,如何量化"一个个体对另一个体信念的影响"这一因果量,并据此识别高影响力节点。该方向的核心张力在于:网络中的个体行为是内生、相互依赖的(A 影响 B,B 也影响 A),且存在隐藏的共因(如共同的信息源),这使得传统的"干预-观察"因果推断框架(如潜在结果、工具变量)难以直接应用。该方向的成熟度处于"模型驱动、理论推导为主"的阶段——研究者通常先假设一个具体的交互动力学模型(如 DeGroot 模型),再在该模型内部推导因果量的解析表达式,而非从观测数据中非参数地识别因果效应。
发展脉络¶
- 奠基工作:DeGroot 共识模型(1974)。这是整个领域的起点。DeGroot 提出,个体通过反复加权平均邻居的信念来更新自己的信念,最终收敛到共识。这一模型奠定了"信念更新 = 线性动力学"的范式,后续几乎所有工作都在此基础上扩展。本文的 NBSL 模型(式 3-4)正是 DeGroot 模型的"非贝叶斯"扩展——在加权平均之前先进行局部的贝叶斯更新。
- 主要进展:非贝叶斯社会学习(NBSL)与自适应社会学习(ASL)。Jadbabaie et al. (2012)、Nedić et al. (2017)、Lalitha et al. (2018) 将 DeGroot 模型推广到"个体有私有观测、且观测分布未知"的场景,证明了在强连通图下,所有个体的信念会指数收敛到真实假设(truth learning,定理 1)。Bordignon et al. (2021) 进一步引入遗忘机制(式 10-11),使模型能够跟踪环境变化,代价是信念不再收敛到点质量,而是围绕真实假设波动(定理 2)。这一支文献的焦点是收敛性与误差界,而非因果效应。
- 因果推断视角的引入:本文作者指出,已有工作(如 Sridhar et al. 2022; Soni et al. 2019)要么只考虑单步交互,要么依赖 Granger 因果性(预测性工具,对潜在共因不稳健,见 Eichler and Didelez 2010 的批评)。本文的定位是:在 NBSL/ASL 动力学模型内部,用结构因果模型(SCM)的干预框架(do-算子)严格定义并推导"成对因果影响",从而将"影响"从描述性概念(相关性、中心性)提升为可干预的因果量。
- 当前 frontier 与本文位置:当前 frontier 是"从观测数据中学习模型参数,进而估计因果影响"。本文的 GCL 算法(算法 2)正是这一方向的尝试:利用观测到的信念序列和网络拓扑,估计组合矩阵 A 和个体信息度 d(θ),再代入闭式表达式计算因果影响。本文声称这是"首次"将因果推断框架系统性地应用于社会学习动力学(见引言"To the best of our knowledge, this appears to be the first study to do so")。
子线索聚类¶
- 社会学习动力学(正向建模):DeGroot (1974)、Acemoglu et al. (2011)、Jadbabaie et al. (2012)、Nedić et al. (2017)、Lalitha et al. (2018)、Bordignon et al. (2021)。这一簇关注"给定模型,信念如何演化、是否收敛、收敛速度"。本文的定理 1 和 2 直接引用此线索的结论。
- 网络影响力度量(描述性/预测性):Kempe et al. (2003)、Shah and Zaman (2011)、Banerjee et al. (2013)、Dablander and Hinne (2019)、Jain and Sinha (2020)、Shumovskaia et al. (2023)。这一簇用中心性、影响力最大化、Granger 因果等工具度量"谁重要",但缺乏因果解释。本文明确将自身与此线索划清界限(引言第 2 段)。
- 网络干扰下的因果推断:Toulis and Kao (2013)、Sussman and Airoldi (2017)、Agarwal et al. (2022)。这一簇关注"当处理效应通过网络溢出时,如何估计因果效应",但通常假设静态或单轮交互。本文的贡献在于将因果推断扩展到多轮、动态、信念更新的场景。
- 计算复杂性:Hazla et al. (2021) 证明完全贝叶斯社会学习是 NP-hard 的,这为本文采用非贝叶斯近似(NBSL/ASL)提供了合理性论证。
核心问题¶
- 因果影响的定义:如何将"影响"从相关性提升为因果量?本文的答案是:用 SCM 的 do-算子,定义"将个体 m 的信念固定为某值时,个体 k 的渐近信念变化"。
- 因果影响的解析刻画:给定网络拓扑 A 和个体信息度 d(θ),能否得到成对因果影响的闭式表达式?本文的答案是:能,且表达式仅依赖于 A 的块结构(R、r)和 d(θ)。
- 从观测数据估计因果影响:当 A 和 d(θ) 未知时,如何从观测的信念序列中估计它们?本文的 GCL 算法给出了一个基于最小二乘的估计方案,并证明了 O(1/√M) 的误差界(定理 3)。
⚠️ 作者的 framing(这是作者的说法)¶
作者将缺口 frame 成:"已有影响力度量要么是纯拓扑的(中心性),要么是预测性的(Granger),缺乏因果解释;而本文首次在社会学习动力学中,用结构因果模型的干预框架,推导出成对因果影响的闭式表达式,并给出从观测数据估计这些影响的方法。" 作者淡化了以下竞争路线:(i) 网络干扰文献(Sussman and Airoldi 2017 等)已经处理了"干预在网络中传播"的问题,但作者认为它们没有考虑信念更新动力学;(ii) 完全贝叶斯社会学习(Hazla et al. 2021)虽然更"理性",但作者以 NP-hard 为由回避。值得研究者去查的问题:作者声称的"首次"是否成立?网络干扰文献中是否有类似"动态干预效应"的定义?作者对 Granger 因果的批评("不稳健于潜在共因")是否同样适用于本文的模型——本文的 NBSL/ASL 模型是否也假设了无未观测共因?
张力¶
未见明显对立引用。但有一个隐含张力值得注意:NBSL 的定理 1(truth learning)说所有个体最终收敛到真实假设,这意味着在极限意义下,个体间的信念差异消失,因果影响似乎应该趋于零。而本文定义的因果影响(式 15)恰恰是渐近信念的差异,因此它衡量的是"干预导致的稳态差异",而非"干预导致的瞬态影响"。这一张力在文中未明确讨论,但对理解因果影响的含义至关重要。
二、最核心、最简单的例子 / 数学内核¶
第一步:符号、模型、可观测数据¶
符号清单(逐个点名):
| 记号 | 含义 | 类型 |
|---|---|---|
| \(K\) | 网络中智能体(agent)的数量 | 常数 |
| \(\Theta = \{\theta_1, \dots, \theta_H\}\) | 假设空间(有限集,\(H\) 个假设) | 常数 |
| \(\theta^\circ \in \Theta\) | 真实的环境状态(未知) | 参数 |
| \(\xi_{k,i}\) | 智能体 \(k\) 在时间 \(i\) 的私有观测 | 随机变量(观测) |
| \(L_k(\xi \mid \theta)\) | 智能体 \(k\) 在状态 \(\theta\) 下的似然函数 | 已知模型 |
| \(\mu_{k,i}(\theta)\) | 智能体 \(k\) 在时间 \(i\) 对假设 \(\theta\) 的信念(概率) | 随机变量(观测) |
| \(\psi_{k,i}(\theta)\) | 智能体 \(k\) 在时间 \(i\) 的中间信念(贝叶斯更新后) | 随机变量(观测) |
| \(A = [a_{\ell k}]\) | 组合矩阵,\(a_{\ell k}\) 是 \(k\) 对 \(\ell\) 的信任权重 | 参数(待估) |
| \(d_k(\theta)\) | 智能体 \(k\) 的 KL 散度,$d_k(\theta) = D_{KL}(L_k(\cdot | \theta^\circ) | L_k(\cdot |
| \(\lambda_{k,i}(\theta)\) | 对数信念比,\(\lambda_{k,i}(\theta) = \log \frac{\mu_{k,i}(\theta^\circ)}{\mu_{k,i}(\theta)}\) | 随机变量(观测) |
| \(x_{k,i}(\theta)\) | 对数似然比,$x_{k,i}(\theta) = \log \frac{L_k(\xi_{k,i} | \theta^\circ)}{L_k(\xi_{k,i} |
| \(\boldsymbol{\lambda}_i(\theta)\) | 所有智能体的对数信念比向量(\(K \times 1\)) | 随机变量(观测) |
| \(\mathbf{x}_i(\theta)\) | 所有智能体的对数似然比向量(\(K \times 1\)) | 随机变量(观测) |
| \(C_{m \to k}\) | 智能体 \(m\) 对 \(k\) 的因果影响 | 目标 estimand |
| \(\mathbf{C}\) | 因果影响矩阵(\(K \times K\)) | 目标 estimand |
| \(\mu_m\) | 干预中固定的信念向量(\(H \times 1\)) | 干预设定 |
| \(\delta, \beta\) | ASL 模型的遗忘因子和似然权重 | 超参数 |
模型(数据生成机制):
-
NBSL(非贝叶斯社会学习):每个智能体 \(k\) 在时间 \(i\) 先做局部贝叶斯更新(式 3),再与邻居做几何平均(式 4)。在对数信念比空间,这等价于线性动力学:
\[\boldsymbol{\lambda}_i(\theta) = A^T \boldsymbol{\lambda}_{i-1}(\theta) + \mathbf{x}_i(\theta)\]其中 \(A\) 是左随机矩阵(列和为 1),\(x_{k,i}(\theta)\) 的期望为 \(d_k(\theta)\)(若 \(\theta \neq \theta^\circ\))或 \(-d_k(\theta)\)(若 \(\theta = \theta^\circ\))。 -
ASL(自适应社会学习):在 NBSL 基础上引入遗忘因子 \(\delta\),使模型能跟踪环境变化:
\[\boldsymbol{\lambda}_i(\theta) = (1-\delta) A^T \boldsymbol{\lambda}_{i-1}(\theta) + \beta \mathbf{x}_i(\theta)\]
可观测数据:研究者能观测到的是: 1. 所有智能体在每个时间步的信念 \(\{\mu_{k,i}\}_{k=1,\dots,K;\, i=1,\dots,M}\)(或等价地,对数信念比 \(\{\lambda_{k,i}\}\)); 2. 网络拓扑(谁连接谁),由此可构造组合矩阵 \(A\) 的估计 \(\hat{A}\)(例如用平均规则,式 81)。
不可观测 / 潜在量: 1. 真实状态 \(\theta^\circ\)(需要估计,式 80 用多数投票); 2. 每个智能体的私有观测 \(\xi_{k,i}\)(不可观测,但可通过信念更新推断其统计性质); 3. 个体信息度 \(d_k(\theta)\)(需估计,式 82 用时间平均)。
第二步:最小内核¶
核心问题:在一个 \(K=2\) 的简单网络上,智能体 1 和 2 相互连接,各自有私有观测。我们想知道:"如果强行把智能体 1 的信念固定为某个值,智能体 2 的最终信念会变成什么?" 这个"最终信念的变化量"就是因果影响 \(C_{1 \to 2}\)。
最小设定: - \(K=2\),\(H=2\)(两个假设 \(\theta^\circ\) 和 \(\theta'\))。 - 组合矩阵 \(A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}\),其中 \(a_{11} + a_{21} = 1\),\(a_{12} + a_{22} = 1\)(左随机)。 - 智能体 1 的信息度 \(d_1(\theta') > 0\),智能体 2 的信息度 \(d_2(\theta') > 0\)。
干预:\(do(\mu_{1,i} := \mu_1)\),即把智能体 1 的信念永久固定为 \(\mu_1\)。这等价于在对数信念比空间把 \(\lambda_{1,i}\) 固定为 \(\lambda_1 = \log \frac{\mu_1(\theta^\circ)}{\mu_1(\theta')}\)。
NBSL 下的推导: - 干预后,智能体 2 的动力学变为(由式 26 和 35 简化):
为什么这个例子是"内核": 1. 它揭示了因果影响的本质:影响的大小取决于 (i) 智能体 1 在组合矩阵中的权重 \(a_{12}\)(网络拓扑),(ii) 智能体 2 对自身观测的依赖程度 \(1 - a_{22}\)(自循环),(iii) 智能体 1 的信息度 \(d_1\)(信息质量)。三者缺一不可。 2. 它展示了"干预"如何改变动力学:干预不是简单地"把 \(\lambda_1\) 换成常数",而是切断了智能体 1 的更新方程,使其不再受邻居影响。这对应式 23 中 \(\tilde{A}\) 的构造。 3. 它暴露了识别的关键:要计算 \(C_{1 \to 2}\),需要知道 \(A\) 和 \(d(\theta)\)。\(A\) 可以从网络拓扑估计,但 \(d(\theta)\) 需要从观测的信念序列中反推——这正是 GCL 算法的任务。
一般化:对于 \(K > 2\) 的强连通图,同样的逻辑成立,只是 \(\lambda_1\) 的影响通过矩阵 \((I - R^T)^{-1}\) 传播到所有其他节点(式 35)。\(R\) 是 \(A\) 去掉被干预节点后的子矩阵,其谱半径小于 1(因为原图强连通),保证了 \((I - R^T)^{-1}\) 的存在性。这就是为什么"强连通"是定理 1 和 2 的关键假设——它保证了信息的充分混合,也保证了干预影响的有限传播。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在 NBSL 和 ASL 两种社会学习动力学模型下,如何从因果推断的视角(而非相关性或中心性)量化社交网络中成对智能体之间的影响,并据此识别高影响力节点。
- 核心工具/方法:结构因果模型(SCM)的干预框架(do-算子)+ 线性动力学的闭式解。具体地,将"固定某智能体信念"的干预建模为修改组合矩阵 \(A\) 为 \(\tilde{A}\)(式 23),然后利用 Perron-Frobenius 定理和矩阵几何级数,推导出干预前后稳态信念的解析表达式。
- 主要结论:成对因果影响 \(C_{m \to k}\) 有闭式表达式(式 35 和 61),它分解为"直接效应"(通过 \(r\) 和 \(R\) 的几何级数传播)和"间接效应"(通过 \(R\) 的幂次传播);基于此提出 CausalRank 算法,其排序结果与网络中心性(如特征向量中心性)有本质区别,且对"刷粉攻击"(follower inflation)具有鲁棒性。
关键设定与假设¶
| 假设 | 内容 | 统计含义 | 相比已有工作的变化 |
|---|---|---|---|
| A1: 强连通图 | 网络对应的有向图强连通,且至少一个自环 | 保证 Perron 向量 \(v\) 存在且唯一,\((I - R^T)^{-1}\) 有界 | 与 NBSL 文献一致(Nedić et al. 2017),但本文将其用于因果推断而非收敛性分析 |
| A2: 似然函数已知 | 每个智能体知道自己的似然函数 $L_k(\xi | \theta)$ | 保证贝叶斯更新(式 3)是良定义的 |
| A3: 观测独立同分布 | \(\xi_{k,i}\) 在时间上 i.i.d. | 保证 \(x_{k,i}(\theta)\) 的期望为 \(d_k(\theta)\),从而线性动力学的期望可闭式求解 | 与 NBSL 文献一致 |
| A4: 干预是原子的、持久的 | \(do(\mu_{m,i} := \mu_m)\) 对所有 \(i\) 成立 | 将干预建模为修改 \(A\) 的第一行(式 23),而非瞬时的脉冲 | 这是本文的新设定,区别于脉冲干预(impulse intervention)文献 |
| A5: 组合矩阵可估计 | 从观测信念序列可估计 \(A\)(用平均规则或最小二乘) | 使得 GCL 算法可行 | 本文的新贡献,但假设较简单(未考虑 \(A\) 的时变性) |
相比已有工作的变化: - 放宽:本文不要求"无干扰"(no interference)假设——恰恰相反,干扰(即影响)是研究对象。 - 强化:本文要求动力学模型是精确已知的(NBSL 或 ASL),而非从数据中识别。GCL 算法虽然估计参数,但模型结构(线性、几何平均)是预设的。 - 新增:干预的定义(式 23)和因果影响的 estimand(式 15)是本文独有的,已有 NBSL 文献没有定义过"干预"。
主要结果¶
定理 1(NBSL 的 truth learning):引用已有结果,说明无干预时所有智能体信念收敛到真实假设。这是本文的基线:因果影响衡量的是"偏离这个基线的程度"。
定理 2(ASL 的收敛性):引用已有结果,说明 ASL 下信念围绕真实假设波动。这是本文的第二个基线。
定理 3(GCL 的误差界):本文的核心理论贡献。它声称:当组合矩阵估计误差 \(\|E\|\) 和样本数 \(M\) 满足一定条件时,因果影响估计的误差为 \(O(1/\sqrt{M})\)。证明路线(附录 E): 1. 将因果影响估计误差分解为"组合矩阵估计误差"和"信息度估计误差"两部分(式 123)。 2. 利用矩阵摄动理论(\((I - (R+E)^T)^{-1} = (I - R^T)^{-1} + O(\|E\|)\))控制第一部分。 3. 利用大数定律和 i.i.d. 假设控制第二部分(式 130-131)。 4. 关键跳跃点:需要假设 \(E = o(\max\{M^{-3/2}, \delta M^{-1/2}\})\)(式 116),即组合矩阵的估计误差必须随样本量以特定速率收敛。这个条件比单纯要求 \(\|E\| \to 0\) 更强,因为它还限制了 \(\delta\) 的大小——\(\delta\) 太大时,遗忘机制会放大估计误差。
技术技巧点名: - Perron-Frobenius 定理:用于证明 \((I - R^T)^{-1}\) 的存在性和正性(式 35 的推导基础)。 - 矩阵几何级数:\(\sum_{j=1}^\infty (1-\delta)^{j-1}(R^T)^j = (1-\delta)(I - (1-\delta)R^T)^{-1}\),用于将无限时间求和化为闭式矩阵逆(式 61)。 - Schur 补 / 分块矩阵求逆:用于处理 \(\tilde{A}\) 的幂(附录 B)。 - Woodbury 恒等式:用于从 \(A\) 的逆快速恢复 \(R\) 的逆,将 \(O(K^4)\) 降为 \(O(K^3)\)(附录 F)。 - Hölder 不等式 + 矩阵范数:用于证明因果影响估计的 Lipschitz 性质(式 128-129)。
真实例子与应用¶
合成数据实验(第 8 节): - 设置:\(K=11\) 的强连通有向图(图 7),每个智能体的信息度 \(d_k(\theta')\) 按表 1 设定(智能体 5、6 无信息,即 \(d=0\))。 - 验证内容:(i) 因果影响矩阵 \(\mathbf{C}\) 的闭式表达式与蒙特卡洛模拟一致;(ii) CausalRank 排序与 AIR(平均影响)排序的差异;(iii) 对"刷粉攻击"的鲁棒性——向被攻击智能体添加大量无信息 bot(\(d=0\)),观察排序变化。 - 关键结果:CausalRank 对刷粉攻击的鲁棒性显著优于 AIR 和特征向量中心性(图 14)。直觉:CausalRank 衡量的是"信息影响力"而非"连接数量",无信息 bot 虽然增加了连接数,但不传递信息,因此不增加因果影响。
真实数据实验(第 9 节): - 数据:Twitter 上 20 个加密货币相关用户的子网络(图 16),包含 Elon Musk(用户 1)和一个被 Musk 关注的小用户(用户 2)。 - 方法:用 GCL 算法(算法 2)从推文情感分数(作为信念)和关注关系(作为网络拓扑)估计因果影响矩阵。 - 关键结果:用户 1(Musk)对所有其他用户有显著影响,但用户 2 对 Musk 的影响很低——尽管用户 2 被 Musk 关注。直觉:Musk 的信息度高(大量原创内容),用户 2 的信息度低(主要是转发),因此 Musk 对用户 2 的影响大,反之则小。这验证了"因果影响 ≠ 网络中心性"的核心论点。
🔎 结论是否比证明窄¶
是,存在明显的"证明窄于结论"之处:
-
定理 3 的证明依赖强假设,但结论被泛化:定理 3 的证明(附录 E)要求组合矩阵估计误差 \(E = o(\max\{M^{-3/2}, \delta M^{-1/2}\})\)(式 116),且 \(\delta\) 足够小。但论文在摘要和引言中声称 GCL 算法"适用于 NBSL 和 ASL 下的任何干预强度"(式 85 附近),未明确提及这些条件。具体位置:定理 3 陈述(第 7 节)只写了 \(O(1/\sqrt{M})\),而证明中的条件(式 116)被放在附录。读者若不读附录,会误以为误差界无条件成立。
-
因果影响的定义依赖"稳态"概念,但稳态可能不存在:式 15 定义的因果影响基于 \(\mu_{k,\infty}\) 和 \(\tilde{\mu}_{k,\infty}\) 的差。对于 NBSL,定理 1 保证了稳态存在;但对于 ASL,定理 2 只说"依分布收敛",并未保证期望的极限存在。式 13 的期望极限需要额外的均匀可积性条件,论文未讨论。具体位置:式 13 的推导(第 3 节末)直接取了期望的极限,未说明为何可以交换极限和期望。
-
GCL 算法的估计误差只考虑了"参数估计误差",未考虑"模型误设":定理 3 假设数据确实由 NBSL/ASL 模型生成。但真实 Twitter 数据(第 9 节)几乎肯定不满足"线性、时不变、i.i.d. 观测"的假设。论文在结论部分承认"模型可能无法完全描述真实世界",但未给出任何模型误设下的鲁棒性分析。具体位置:第 10 节结论,仅一句"our results may not fully capture the complexity of real-world interactions"。
-
CausalRank 的收敛性未被证明:算法 1 声称输出 Perron 向量 \(q\),但未证明幂迭代(或特征值分解)在因果影响矩阵 \(\mathbf{C}\) 上的收敛性。\(\mathbf{C}\) 是正矩阵(由式 72 和 75 可知),Perron-Frobenius 定理保证了主特征向量的存在性,但论文未讨论 \(\mathbf{C}\) 是否可对角化、主特征值是否唯一等数值分析问题。具体位置:算法 1 第 13 行,直接调用特征值分解,无收敛性讨论。
四、开放问题¶
以下问题均扎根于论文的具体语句,供研究者自行判断价值与可行性:
-
模型误设下的因果影响估计(扎根于第 10 节结论的自我批评):论文假设数据由 NBSL/ASL 精确生成,但真实社交网络存在时变拓扑、非线性更新、异质性智能体。要做什么:在更一般的动力学模型(如带噪声的 DeGroot、非线性意见动力学)下,重新推导因果影响的识别条件。难点:闭式解可能不存在,需要转向非参数或半参数方法。
-
因果影响的统计推断(扎根于定理 3 的误差界):论文只给出了 \(O(1/\sqrt{M})\) 的期望误差界,未给出置信区间或假设检验。要做什么:推导 \(\hat{C}_{m \to k}\) 的渐近分布,构造置信区间。难点:\(\hat{C}_{m \to k}\) 是矩阵函数(涉及 \((I - \hat{R}^T)^{-1}\)),其渐近方差的 Delta method 推导可能繁琐,但可行。
-
干预的时序与强度(扎根于式 23 的"原子、持久"干预假设):论文只考虑"永久固定信念"的干预。要做什么:考虑脉冲干预(只固定一个时间步)、软干预(部分固定)、或干预强度连续变化的情形。难点:脉冲干预下,因果影响可能依赖干预的时间点,需要定义"时间平均"或"累积"影响。
-
CausalRank 的统计性质(扎根于算法 1 的数值分析空白):论文未证明 CausalRank 排序的相合性、稳定性或对 \(\mathbf{C}\) 估计误差的敏感性。要做什么:分析 \(\hat{\mathbf{C}}\) 的扰动如何影响排序结果,给出排序错误的概率上界。难点:排序是离散对象,其敏感性分析需要新的技术工具(如排序的 Hausdorff 距离)。
-
与网络干扰文献的桥接(扎根于引言对网络干扰文献的引用):论文的因果影响定义与 Sussman and Airoldi (2017) 的"网络干扰下的平均处理效应"有何异同?要做什么:将本文的动力学模型嵌入潜在结果框架,比较两种因果 estimand 的差异。难点:潜在结果框架通常假设静态干预,而本文的干预是动态的,需要扩展 SUTVA 假设。
-
高维网络的扩展(扎根于算法 2 的 \(O(K^3)\) 复杂度):当 \(K\) 很大(如百万节点)时,计算 \(\mathbf{C}\) 需要 \(O(K^3)\) 时间,不可行。要做什么:利用稀疏性(\(A\) 是稀疏的)和低秩结构(\(\mathbf{C}\) 可能是低秩的),设计近似算法。难点:\((I - R^T)^{-1}\) 在稀疏 \(R\) 下通常不是稀疏的,需要随机化算法或 Nyström 近似。
提醒:要确认上述问题是否是真 gap,建议去读以下近期文献的引言部分(各约 5 篇):(i) 网络干扰的因果推断(如 arXiv:2210.11355 的后续工作);(ii) 意见动力学的因果分析(如 PNAS 上的相关论文);(iii) 图神经网络的可解释性(涉及节点影响力度量)。如果这些文献的引言都指向同一个未解决问题,那才是值得投入的真 gap。
Maintained by 陈星宇 · Homepage · Source on GitHub