Information Loss and Disparate Effects in Network Embeddings¶

会议: NeurIPS 2026
arXiv: 2509.12396
领域: AI 安全
关键词: 网络表示学习, 算法公平性, 随机块模型, 信息损失, 差异化影响

一句话总结¶

本文首次从几何与渐近理论视角解析了无公平性干预的基础网络嵌入算法产生群体差异的内在机制，证明了点积损失在随机块模型上引发的信息损失会导致表征不可逆性，并不对称地过度压缩并致密化小社群与稀疏社群，进而造成下游链接预测任务对弱势群体产生系统性高误差。

研究背景与动机¶

低维网络节点嵌入技术（如 DeepWalk、node2vec、LINE）是图数据挖掘、链接预测和社群发现的核心基石。为了缓解图表示中普遍观察到的群体级误差不平等，大量公平图表示工作相继提出了诸如 FairWalk、Debayes、FairDrop 等公平性干预算法，通过调整重采样策略、增加对抗性正则项或前处理边连接来满足统计均等（Statistical Parity）等公平指标。然而，现有研究绝大多数将关注点聚焦在“如何设计干预算法”上，却始终未能回答一个更基础的理论问题：在没有任何外加干预的情况下，经典网络嵌入基线算法究竟为何会在表征层面自发产生群体间的差异化影响？

与公平性文献平行推进的另一条理论线索揭示了低维内积嵌入的固有表达瓶颈：任意低维欧氏嵌入必然丢失原图信息，且采用子图采样与点积交叉熵损失训练网络嵌入时，即便是极低秩的图元（Graphon）也无法被无损学习，这意味着“默认”训练方式会将大量不同的生成模型映射为完全相同的嵌入表示，即存在严重的不可逆性（Non-Invertibility）。然而，理论界尚不清楚这种不可逆的信息损失究竟遵循何种几何规律，也不清楚它与下游机器学习任务中弱势群体的性能劣化存在何种因果关联。

本文的切入点正是将“表示学习的信息损失理论”与“算法公平性中的群体差异”这两条长期割裂的研究脉络严密联结。作者以兼具同质性（Homophily）与多数/少数社群结构的随机块模型（SBM）为理论对象，完整推导了极小化经验风险时内积核矩阵的渐近极限。本文的核心 idea 是：基础网络嵌入的信息损失由图的密度与同质性精确决定，处于中间状态的非退化图均落入不可逆等价类，且该等价类的收缩几何迫使规模更小、连接更稀疏的社群在嵌入空间中遭受不对称的过度致密化（Over-Densification），直接导致下游基于内积的预测任务将极度虚高的边概率强加给弱势社群。

方法详解¶

整体框架¶

本文考虑对包含 $k$ 个社群的随机块模型 $\mathcal{G} = (P, S)$ 进行表示学习的通用流程。其中 $P \in [0, 1]^{k \times k}$ 为社群间边概率对称矩阵，$S = [s_1, \dots, s_k]$ 为各社群节点占比（$\sum s_i = 1$）。在算法执行中，系统通过均匀顶点子采样（Uniform Vertex Sampling）获得诱导子图，并使用成对交叉熵损失（Pairwise Cross-Entropy Loss）优化节点嵌入向量 $\omega_i \in \mathbb{R}^d$ 的标准内积 $\langle \omega_i, \omega_j \rangle$。根据极限理论，当经验风险极小化收敛时，所有经验内积矩阵均高概率弱收敛至唯一的半正定块常数核矩阵 $K(\mathcal{G})$。

整个分析框架展示了图参数空间 $(P, S)$ 到极限核空间 $K(\mathcal{G})$ 的映射关系，并揭示了不可逆映射在下游链接预测中对小社群/稀疏社群产生不对称误差的传导机制：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入随机块模型 SBM<br/>拓扑参数 (P, S)"] --> B["阶段1：信息损失区域判定<br/>全信息保留 / 维度退化 / 不可逆压缩"]
    B -->|落入中间不可逆区域| C["阶段2：线性等价类形成<br/>一维线段流形 F(K) 与致密化斜率 η"]
    C --> D["阶段3：非对称过度致密化<br/>小规模与稀疏社群被强力压缩致密"]
    D --> E["下游任务偏差放大<br/>内积链接预测隐式选取极大密度图 G*"]

关键设计¶

1. 信息损失三大区域精确刻画：揭示拓扑密度而非社群规模主导表示保真度

针对包含两个社群的 SBM（参数化为 $P = \begin{bmatrix} p & q \\ q & r \end{bmatrix}$，规模占比 $S = (a, 1-a)$，其中 $a \ge 1/2$），作者通过求解带有半正定（PSD）约束的 Karush-Kuhn-Tucker（KKT）优化系统，证明了渐近核矩阵 $K(\mathcal{G})$ 必然为分块常数矩阵： $$K(\mathcal{G}) = \begin{bmatrix} K_1 \mathbf{1}_{an \times an} & K_2 \mathbf{1}_{an \times (1-a)n} \\ K_2 \mathbf{1}_{(1-a)n \times an} & K_3 \mathbf{1}_{(1-a)n \times (1-a)n} \end{bmatrix}$$ 系统在参数空间中完全解耦为互不重叠的三大区域： - 高密度同质区 $\Pi_d$：当且仅当社群内部边概率充分大（$p \ge 1/2, r \ge 1/2$）且满足反向柯西-施瓦茨不等式 $\sigma^{-1}(q)^2 < \sigma^{-1}(p) \sigma^{-1}(r)$ 时，所有 KKT 对偶乘子均为 0，嵌入为完全无损且可逆的，即 $K_1 = \sigma^{-1}(p), K_2 = \sigma^{-1}(q), K_3 = \sigma^{-1}(r)$； - 低密度异质退化区 $\Pi_s$：当且仅当 $p \le 1/2, r \le 1/2$ 且 $(1/2 - q)^2 \le (1/2 - p)(1/2 - r)$ 时，原点 $(0,0,0)$ 是唯一的全局最优解，此时 $K_1 = K_2 = K_3 = 0$，表示空间丢失所有社群结构与拓扑信息； - 中间不可逆压缩区 $\Pi_m$：其余绝大多数现实图均落入此区域。在此区域内，半正定边界约束 $K_2^2 \le K_1 K_3$ 被强制取等，导致社群归属信息得以保留，但拓扑密度信息被大幅压缩。极为关键的是，三大区域的划分边界完全仅由概率值 $(p, q, r)$ 决定，与社群规模大小 $a$ 完全无关。

2. 不可逆嵌入诱导的线性等价类：证明不同稀疏度图共享同一表征

在中间压缩区域 $\Pi_m$ 中，由于约束取等（$K_2 = \mathbb{S}\sqrt{K_1 K_3}$，其中当 $q \le 1/2$ 时符号因子 $\mathbb{S} = +1$，反之 $\mathbb{S} = -1$），信息损失在图空间诱导出了等价类。作者解析证明了所有产生相同核矩阵 $\hat{K} = (K_1, K_2, K_3)$ 的 SBM 集合在 $(p, q, r)$ 空间中构成一条严格的一维直线段： $$F_{\hat{K}} = \left\{ (p, q, r) \in \Pi_m \;\middle|\; p = p_0 + \eta \Delta, \; q = q_0 + \mathbb{S} \Delta, \; r = r_0 + \frac{1}{\eta} \Delta, \; \Delta \in \mathbb{R} \right\}$$ 其中直线在参数空间中的斜率由参数 $\eta$ 唯一确定： $$\eta = \frac{1-a}{a} \sqrt{\frac{K_3}{K_1}} = \sqrt{\frac{\sigma(K_1) - p}{\sigma(K_3) - r}}$$ 每个等价类线段从一个极度稀疏的边界图（$q=0$ 或 $q=1$）一直连续延伸至 $\Pi_d$ 边界上的极大密度图 $\mathcal{G}^\star = (p^\star, q^\star, r^\star) = (\sigma(K_1), \sigma(K_2), \sigma(K_3))$。这意味着一个极其稀疏的网络与一个极其稠密的网络在点积嵌入空间中可以呈现完全相同的表征。

3. 少数与稀疏社群的不对称过度致密化机制：揭开表征公平失衡的根源

当现实中常见的稀疏网络被映射至等价类时，嵌入表征并非对称收缩，而是对不同社群施加了截然不同的“假性致密化速率”。具体而言，多数社群（社群 1，占比 $a \ge 1/2$）的致密化增长速率为 $\eta$，而少数社群（社群 2，占比 $1-a$）的致密化增长速率为 $1/\eta$。分析 $\eta$ 的表达式可知其受两重比率的乘积控制： - 社群规模比 $\frac{1-a}{a} \le 1$：当少数群体人口比例缩小时，该比值急剧下降，驱动 $\eta \to 0$，进而使少数群体的致密化速率 $1/\eta \to \infty$； - 内积与密度比 $\sqrt{K_3 / K_1}$：在同质图中，$K$ 趋向于反映真实密度，当少数群体内部连接更稀疏（$r < p$）时，$K_3 < K_1$，进一步强化了 $\eta$ 的下降。这两种物理效应在现实社交网络中通常高度重叠（小社群往往也是连接稀疏社群）。这从根本上解释了嵌入空间几何上的“挤压现象”：为了在稀疏图的全局交叉熵中降低占比绝大多数的非边惩罚，优化目标更倾向于将小社群紧密压缩进一个狭窄的子空间，从而使其在表示空间中显现出远高于实际的虚假连接强度。

一个完整示例¶

考虑一个具有明显规模差异与稀疏特征的双社群 SBM：多数群体占比 $a = 0.75$，少数群体占比 $1-a = 0.25$；初始图边概率设置为相互解耦的稀疏社群 $p_0 = 0.1, r_0 = 0.1, q_0 = 0$。

在经验风险极小化收敛后，该网络落入不可逆压缩区 $\Pi_m$。由于社群规模差异，规模比因子为 $\frac{1-a}{a} = \frac{0.25}{0.75} = \frac{1}{3} \approx 0.333$。尽管初始图内两社群拥有完全相同的局部密度（$p_0 = r_0 = 0.1$），但优化收敛解使得核矩阵对偶约束强制满足 $\eta = \frac{1}{3}\sqrt{K_3/K_1}$。由于 $q_0 = 0 \le 0.5$，符号因子 $\mathbb{S} = +1$。代入等价类公式： $$p(\Delta) = 0.1 + \eta \Delta, \quad q(\Delta) = \Delta, \quad r(\Delta) = 0.1 + \frac{1}{\eta} \Delta$$ 若 $\eta \approx 0.333$，则少数群体的致密化速率为 $1/\eta \approx 3.0$。当沿等价类向极大密度图 $\mathcal{G}^\star$ 移动（$\Delta > 0$）时，少数群体的内部边概率预测值以 9 倍于多数群体的速度急剧飙升（致密化比率 $d_r \approx 1/\eta^2 \approx 9.0$）。这直观地表明，嵌入算法仅凭规模差异就将少数群体在特征空间中“过度压缩”，使其表征宛如一个内部极其致密的高凝聚度团伙。

损失函数 / 训练策略¶

论文所研究的基础节点嵌入算法遵循成对经验风险极小化（ERM）目标。设输入图为 $G_n = (V, E)$，节点数 $|V| = n$，节点嵌入表示为 $\omega_i \in \mathbb{R}^d$。优化目标函数定义为： $$\mathcal{R}_n(\omega_1, \dots, \omega_n) = \sum_{i \neq j} \Pr((i, j) \in S(G_n) \mid G_n) \ell_{\text{pw}}(\langle \omega_i, \omega_j \rangle, A_{ij})$$ 其中成对交叉熵损失显式展开为： $$\ell_{\text{pw}}(\langle \omega_i, \omega_j \rangle, A_{ij}) = -A_{ij} \log(\sigma(\langle \omega_i, \omega_j \rangle)) - (1 - A_{ij}) \log(1 - \sigma(\langle \omega_i, \omega_j \rangle)) = \log(1 + e^{\langle \omega_i, \omega_j \rangle}) - A_{ij} \langle \omega_i, \omega_j \rangle$$ 根据 Davison & Austern (2023) 建立的广义核渐近收敛理论，当采用采样率为 $\rho$ 的均匀顶点采样时，经验内积矩阵在概率意义下收敛到确定性对称核矩阵 $K$。对于 2-块 SBM，该极限连续优化问题形式化为带有半正定凸锥约束的规划问题： $$\min_{K_1, K_3 \ge 0, K_1 K_3 \ge K_2^2} \rho \left[ a^2 (\log(1 + e^{K_1}) - K_1 p) + (1-a)^2 (\log(1 + e^{K_3}) - K_3 r) + 2a(1-a) (\log(1 + e^{K_2}) - K_2 q) \right]$$ 拉格朗日函数引入对偶乘子 $\mu_1, \mu_2, \mu_3 \ge 0$： $$\mathcal{L}(K, \mu) = \mathcal{R}_n(K) - \mu_1 K_1 - \mu_2 K_3 - \mu_3 (K_1 K_3 - K_2^2)$$ 通过细致的 LICQ 条件校验与极值梯度方向导数分析，解的结构由互补松弛性 $\mu_3 (K_1 K_3 - K_2^2) = 0$ 与非退化边界严格确定，无论嵌入维度 $d$ 多高，所得结论均在渐近意义下普遍成立。

实验关键数据¶

主实验：理论信息损失区域与等价类结构分析¶

论文通过理论推导与数值模拟，精确确立了 2-块及 3-块 SBM 在不同参数配置下的信息损失界限与等价类线性流形特征。

区域类别	代数判定条件	渐近核矩阵解 $K(\mathcal{G})$	信息保留状态	逆映射可逆性
高密度同质区 $\Pi_d$	$p, r \ge \frac{1}{2}$ 且 $\sigma^{-1}(q)^2 < \sigma^{-1}(p)\sigma^{-1}(r)$	$K_1 = \sigma^{-1}(p), K_2 = \sigma^{-1}(q), K_3 = \sigma^{-1}(r)$	拓扑与密度全保留	完全可逆（无损重构）
低密度异质区 $\Pi_s$	$p, r \le \frac{1}{2}$ 且 $(\frac{1}{2}-q)^2 \le (\frac{1}{2}-p)(\frac{1}{2}-r)$	$K_1 = 0, K_2 = 0, K_3 = 0$	全信息完全丢失	完全退化（不可逆）
中间压缩区 $\Pi_m$ (同质)	其余区域且 $q \le \frac{1}{2}$	$K_2 = -\sqrt{K_1 K_3}$，满足式 (2) KKT 条件	社群结构保留，密度部分丢失	诱导一维线性等价类 $F_{\hat{K}}$
中间压缩区 $\Pi_m$ (异质)	其余区域且 $q > \frac{1}{2}$	$K_2 = +\sqrt{K_1 K_3}$，满足式 (2) KKT 条件	社群结构保留，密度部分丢失	诱导一维线性等价类 $F_{\hat{K}}$

在拓展至 3-块 SBM 时，等价类在参数空间中同样呈现出由矩阵 $N$ 引导的直线结构 $P_0 + \Delta N$（满足低秩特性 $N[i,i] N[j,j] \approx N[i,j]^2$），以下为两个典型算例的具体致密化速率与参数边界：

实验场景	社群规模配置 $S$	初始块边概率 $P_0$ 对角线	致密化斜率矩阵 $N$ 对角线 $[N_{11}, N_{22}, N_{33}]$	最大有效位移 $\Delta_{\max}$	致密化规律验证结论
等规模不同密度	$(1/3, 1/3, 1/3)$	$[0.20, 0.30, 0.40]$	$[1.18, 1.03, 0.84]$	$0.386$	最稀疏社群致密化速率最高 ($1.18$ vs $0.84$)
同密度不同规模	$(0.20, 0.30, 0.50)$	$[0.20, 0.20, 0.20]$	$[1.15, 1.01, 0.86]$	$0.441$	最小规模社群致密化速率最高 ($1.15$ vs $0.86$)

真实网络验证：Facebook100 上的非对称致密化与链接预测偏差¶

为证明该理论现象并非合成 SBM 图的特有产物，作者在 Facebook100 真实大学社交网络数据集上测试了基于点积与 Sigmoid 的下游链接预测（$\hat{P}_{ij} = \sigma(\langle \omega_i, \omega_j \rangle)$）。实验选取各大学 2005 届（社群 1）与 2008 届（社群 2）构成的强同质诱导子图，通过 Adam 优化器在 6 维空间训练嵌入，并对比实测致密化比率 $d_r = \frac{P_{\text{learned}}[2,2] - P_{\text{initial}}[2,2]}{P_{\text{learned}}[1,1] - P_{\text{initial}}[1,1]}$ 与理论预测值 $1/\eta^2$：

网络平均边密度分层	覆盖高校网络数	规模/稀疏度偏置主导方向	理论预测致密化比率 $1/\eta^2$ 与实测 $d_r$ 相关性	下游链接预测中少数群体的表征表现
超稀疏网络 ($\text{Density} < 0.01$)	32 所大学	小社群与稀疏社群高度重合	极强正相关 ($R^2 > 0.82$)	边预测概率被成倍虚高，严重违反统计均等
中等稀疏网络 ($0.01 \le \text{Density} < 0.02$)	46 所大学	规模与稀疏效应共同作用	显著正相关 ($R^2 > 0.78$)	较小年级社群内部链接预测出现系统性高假阳率
相对稠密网络 ($0.02 \le \text{Density} < 0.03$)	22 所大学	稀疏差异略微收敛	稳健正相关 ($R^2 > 0.71$)	仍普遍呈现小社群致密化速率显著大于 1 的偏置

关键发现¶

理论预测与真实网络高度吻合：仅依靠原图的三个简单统计量（社群 1 密度、社群 2 密度、跨社群密度）计算出的理论值 $1/\eta^2$，即可在未经任何调优的情况下高度预测 Facebook100 真实网络在嵌入后的相对致密化倍数，证实了理论机制的强健解释力。
链接预测隐式选取极大密度图：经典的内积 Sigmoid 链接预测在数学上等价于在等价类中直接选取了边界处的极大密度图 $\mathcal{G}^\star = \sigma(K)$。这直接导致下游预测不仅无法还原原图的稀疏性，反而将不可逆性带来的虚假边权重全部强加给少数/稀疏社群。
重新审视历史公平性基线：如 FairWalk 等经典文献中展示的 baseline 结果中，少数群体（37% 人口）预测出的边密度高达多数群体的两倍以上，本文为这一长期被忽视的经验异常提供了闭环的数学机理解释。

亮点与洞察¶

跳出干预看本质：以往公平图学习工作盲目堆叠正则化技巧与采样对抗，本文退回原点，首次证明群体不公平是经典点积损失在稀疏同质图上进行 ERM 优化时数学几何特性的自然副产物。
不可逆等价类的精妙解析构造：将复杂的矩阵极值分析转化为一维线性流形，精确导出了由规模比与内积比控制的致密化斜率参数 $\eta$，具有极高的理论优雅性。
下游算法的“隐式图选择”警示：指出任何下游算法在使用网络表征时，都在不知不觉中为不可逆等价类中的候选图做出主观裁决，启示后续研究在设计图重构与链接预测时必须针对等价类做显式归一化或先验校准。

局限与展望¶

生成模型假设的理想化：论文核心理论建立在标准随机块模型（SBM）上，未完全覆盖具有重尾度分布的度校正随机块模型（DCSBM）或连续图元（Graphons）。
表征架构仅限单向量内积：分析针对单节点点积嵌入，未涵盖 Word-Context 双向量表示（如带负采样的 SGNS）或图神经网络（GNN）多层消息传递架构。
未来方向：作者指出后续研究可将等价类分析拓展至基于随机游走采样（DeepWalk、node2vec）的平稳分布核，并探索不定内积（Indefinite Inner Product）对消除非对称致密化的理论潜力。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将图嵌入的渐近不可逆理论与算法公平性相联结，理论推导极具突破性。
实验充分度: ⭐⭐⭐⭐ 包含严格闭式证明、高维数值仿真及 Facebook100 真实网络实证，论据链条扎实完备。
写作质量: ⭐⭐⭐⭐⭐ 数学表达严密优雅，直觉机制与推导步骤层层递进，深入浅出。
价值: ⭐⭐⭐⭐⭐ 为图表示学习的固有偏差提供了基础性理论解释，对未来图基础模型与公平算法设计具有深远指导意义。

区域类别	代数判定条件	渐近核矩阵解 \(K(\mathcal{G})\)	信息保留状态	逆映射可逆性
高密度同质区 \(\Pi_d\)	\(p, r \ge \frac{1}{2}\) 且 \(\sigma^{-1}(q)^2 < \sigma^{-1}(p)\sigma^{-1}(r)\)	\(K_1 = \sigma^{-1}(p), K_2 = \sigma^{-1}(q), K_3 = \sigma^{-1}(r)\)	拓扑与密度全保留	完全可逆（无损重构）
低密度异质区 \(\Pi_s\)	\(p, r \le \frac{1}{2}\) 且 \((\frac{1}{2}-q)^2 \le (\frac{1}{2}-p)(\frac{1}{2}-r)\)	\(K_1 = 0, K_2 = 0, K_3 = 0\)	全信息完全丢失	完全退化（不可逆）
中间压缩区 \(\Pi_m\) (同质)	其余区域且 \(q \le \frac{1}{2}\)	\(K_2 = -\sqrt{K_1 K_3}\)，满足式 (2) KKT 条件	社群结构保留，密度部分丢失	诱导一维线性等价类 \(F_{\hat{K}}\)
中间压缩区 \(\Pi_m\) (异质)	其余区域且 \(q > \frac{1}{2}\)	\(K_2 = +\sqrt{K_1 K_3}\)，满足式 (2) KKT 条件	社群结构保留，密度部分丢失	诱导一维线性等价类 \(F_{\hat{K}}\)

实验场景	社群规模配置 \(S\)	初始块边概率 \(P_0\) 对角线	致密化斜率矩阵 \(N\) 对角线 \([N_{11}, N_{22}, N_{33}]\)	最大有效位移 \(\Delta_{\max}\)	致密化规律验证结论
等规模不同密度	\((1/3, 1/3, 1/3)\)	\([0.20, 0.30, 0.40]\)	\([1.18, 1.03, 0.84]\)	\(0.386\)	最稀疏社群致密化速率最高 (\(1.18\) vs \(0.84\))
同密度不同规模	\((0.20, 0.30, 0.50)\)	\([0.20, 0.20, 0.20]\)	\([1.15, 1.01, 0.86]\)	\(0.441\)	最小规模社群致密化速率最高 (\(1.15\) vs \(0.86\))

网络平均边密度分层	覆盖高校网络数	规模/稀疏度偏置主导方向	理论预测致密化比率 \(1/\eta^2\) 与实测 \(d_r\) 相关性	下游链接预测中少数群体的表征表现
超稀疏网络 (\(\text{Density} < 0.01\))	32 所大学	小社群与稀疏社群高度重合	极强正相关 (\(R^2 > 0.82\))	边预测概率被成倍虚高，严重违反统计均等
中等稀疏网络 (\(0.01 \le \text{Density} < 0.02\))	46 所大学	规模与稀疏效应共同作用	显著正相关 (\(R^2 > 0.78\))	较小年级社群内部链接预测出现系统性高假阳率
相对稠密网络 (\(0.02 \le \text{Density} < 0.03\))	22 所大学	稀疏差异略微收敛	稳健正相关 (\(R^2 > 0.71\))	仍普遍呈现小社群致密化速率显著大于 1 的偏置