基于勒维几何超图的高阶链接预测启发式方法

《Physica A: Statistical Mechanics and its Applications》：Lévy Geometric Hypergraph heuristics for higher-order link prediction

　　

• 一种匹配范围框架将传播范围与衰减形状分离开来。
• 在十个超图上，传播范围比衰减形状更重要。
• 该结论对从2到12跳的每一个截断长度均成立。
• 集合级共同可达性诊断界定了成对投影损失。
• 解耦的核-LGH指标表明，所选范围跟踪了交互可达性。

**引言**

许多复杂系统并非仅由成对关系构成。科学合作涉及作者团队，生化反应涉及多种反应物，药物以多物质组合形式处方，立法者在委员会中共同发起法案。超图——其中单个超边可以连接任意顶点子集——是此类高阶交互的自然表示[1][2][3][4][5]。一项核心推断任务是高阶链接预测：给定一个观测到的超图，根据候选顶点集作为真实但未观测到的超边的可能性对其进行评分[6][7]。本研究聚焦于缺失超边恢复；时间预测则需要基于带时间戳数据的独立评估。

成对链接预测拥有一套成熟的相似性启发式方法工具箱——共同邻居、Adamic–Adar、资源分配和基于路径的Katz指数——其准确性和可解释性已被研究了两十年[8][9][10][11][12]。基于路径的成员中存在一条共同线索：长度为?的路径的贡献被指数级惩罚，即w(?)=β^?，其中0<β<1，因此两到三跳之外的连通性实际上被丢弃。当这些启发式方法通过团扩展提升为超图时，同样的指数惩罚也被继承了下来。然而，现实中的高阶网络表现出显著的异质性和重尾特征[13][14]：少数枢纽顶点参与非常多超边，超边以突发方式重叠，诱导出的拓扑中既包含密集局部社区，也包含稀疏长程桥接。因此，自然要问：指数惩罚——它积极抑制长路径——是否是正确的归纳偏差，以及在空间异质性很强时，保留长程拓扑信号的重尾惩罚是否可能更可取。

这个问题将链接预测与重尾几何的物理联系了起来。lévy飞行——步长遵循具有幂律尾部的α-稳定分布的随机游走——产生分形、无标度的点云，其中密集簇与长跳跃共存[15][16][17]。plaszczynski等人[18]通过lévy几何图（lgg）将这一几何结构嵌入网络，其度独立于图大小，簇的数量作为连接尺度的逆幂缩放，且从不发生渗流转变。最近提出的lévy几何超图（lgh）[19]将这一构造推广到k-均匀超边，在单个由一个稳定性指数控制的生成模型中捕获了尺度不变碎片化和高阶重叠。在本推广中，该指数分裂为点过程的飞行指数αf和连接规则的核指数αk，我们独立变化这两者。然而，lgh是一个生成结构模型；它对高阶链接预测算法的影响尚未被研究。

在本工作中，我们探究拓扑衰减的哪个属性对高阶链接预测重要，以及网络结构如何决定有用的范围。我们在相同的归一化有效范围下比较严格的指数和幂律剖面，以一跳和均匀随机游走作为显式共享端点。我们进一步比较验证选择的模型选择方法与基于关联矩阵的算子。我们的贡献如下：

1. **一个可解释、无训练的范围自适应族**（第4节）。我们通过对角校正的路径和为候选集评分，并在共同的归一化有效范围网格上比较剖面。基于slem的谱衰减地平线提供了一个独立的操作量以测试结构–范围对应关系。

2. **一个可控的高阶基准**（第5节）。我们将lgh推广为pareto–lévy连接核，其中距离为d的空间邻居以概率∝d^(-(1+αk))连接；硬最近邻规则作为αk→∞的极限恢复。核指数αk不同于点过程的lévy飞行指数αf，两者独立变化：αk控制单个超边的空间范围，而αf控制点集的碎片化。因此，该基准生成了从近同质结构到强异质、长程区域的超网络，为链接预测启发式方法提供了受控的压力测试。

3. **一项比较与稳健性研究**（第7节）。我们使用20个共享外层分割、数据集级配对推断、验证选择的决策阈值、嵌套负池、两个验证选择的模型选择诊断以及关联算子比较。截断长度扫描（l=2–12）测试范围对形状的结论是否依赖于固定的地平线；集合级共同可达性诊断量化了成对聚合的局限性；核-lgh上的二参数解耦网格将基准难度归因于几何还是核。聚焦采样/核敏感性和两个受控生成器刻画了长程传播有帮助的区域。

这些结果共同提供了一个可扩展的诊断框架来选择拓扑范围，以及一个可调基准来识别长程信息何时有帮助。因此，我们的经验结论适用于传递式、无训练、基于投影的启发式方法。学习型和时间预测器超出了本次比较的范围。

**章节片段**

*启发式与学习型链接预测。* 对于成对图，共同邻居、adamic–adar、资源分配[10]和katz[12]等相似性指数仍然是可解释的基线[8][9][11]。学习型高阶预测器包括矩阵/张量分解、嵌入[20]、适配于超边预测的超图神经网络编码器[21][22][23][24]和逻辑模型[25][26]。集合注意力编码器[27]、对抗负采样[28]、时间超图上的归纳式集合游走[29]以及...

**问题与预备知识**

设?=(??,?)为n=|??|个顶点上的超图，其中每个超边e∈?的阶|e|≥2。我们评估传递式缺失超边预测：超边被随机分割为?tr和?te（80%/20%），每个测试顶点必须出现在训练投影中。数据集不提供共同的时间戳字段，因此实验聚焦于缺失超边恢复。

**衰减剖线下的成对路径评分**

两个顶点之间的拓扑相似性是连接它们的游走上的加权总和。在转移矩阵p上，定义成对相似度：

s_uv^(w) = σ_{?=1}^{l} w(?)(p^?)_uv

其中w(?)≥0是衰减剖线，它降低较长游走的权重，l是截断长度。由于p是随机的，p^?的每一行对于每个?都是概率分布，因此剖线w——而非谱半径——控制了长程拓扑贡献多少。为了使比较成为一个干净的受控...

**lgh作为可控基准**

为探究在完全受控条件下预测器如何响应空间异质性，我们使用lévy几何超图[19]作为具有可调重尾指数的生成器。我们保留原始模型的lévy飞行几何，并将其连接规则推广为重尾核。该构造具有两个重尾成分，我们用不同符号表示并独立变化：点过程的飞行指数αf和连接的...

**数据集。** 我们使用来自单纯闭合集合[6]的十个经验高阶数据集，涵盖药物共同给药（dawn、ndc-classes、ndc-substances）、在线讨论线程和问答标签（bars、algebra、tags-ask-ubuntu、tags-math）、立法委员会（house-committees、senate-committees）和共同作者关系（coauth-history）。每个超边是一组节点标识符；我们保留阶≥2的超边。表2总结了数据集。

**子采样与核稳定化。** 该集合从数百到近...

**经验数据上的主要比较**

表3报告了20次分割的auc。幂律和katz的均值为0.8894和0.8891。在主要数据集级别上，它们的均差为0.00030（95%自助置信区间[-0.00009, 0.00067]），精确符号翻转p=0.186，holm校正p=0.371。相对于select(katz, hrw)，幂律的差为0.00009（置信区间[-0.00044, 0.00061]；校正p=0.734）。数据集内20次分割级的差异量化了分区敏感性，不被解释为独立实验。图3显示数据集...

**讨论**

在测试的无训练族内，沿归一化范围轴移动比在同一范围下选择指数或幂律参数化具有更大的经验效果。它们的平均auc差异为0.00030，在数据集级别不显著。select(katz, hrw)也匹配了严格幂律族，而select(one-hop, katz, hrw)表现略好；因此有用的建模决策是可用范围集及其验证，而非支持某一...

**结论**

我们研究了传播范围如何影响保留的缺失超边预测。在20个共享外层分割上，严格幂律和katz剖面以及select(katz, hrw)在数据集级推断下具有实践等效的准确性。将共享的一跳端点添加到模型选择中产生了一个小的诊断增益。关联、预处理、嵌套池和批处理检查保留了范围比函数参数化更重要的核心结论。截断长度也是如此...

**credit作者贡献声明**

bingqiao gu：撰写—审阅与编辑，撰写—初稿，可视化，软件，方法学，形式分析。longqi li：撰写—审阅与编辑，撰写—初稿，软件，方法学，形式分析。zhaoyang bao：撰写—初稿，软件。zhanwei du：撰写—审阅与编辑，资金获取，概念化。dong li：撰写—审阅与编辑，监督，资金获取。

**代码可用性**

预测器、lgh基准生成器和完整评估协议的代码可合理请求向作者索取。复制包包含锁定的主要评估、截断长度扫描、核-lgh解耦网格、使用估计器审计重新评估的合成基准、集合级诊断以及从保存的结果文件重新生成每个图表和表格的脚本。

**利益冲突声明**

作者声明他们没有已知的相互竞争的财务利益或个人关系，这些可能影响本报告中描述的工作。

**致谢**

本工作得到国家自然科学基金（批准号62376136和62076149）和广东省基础与应用基础研究基金（批准号2024a1515011935）的支持。

bingqiao gu | longqi li | zhaoyang bao | zhanwei du | dong li 这个问题将链接预测与重尾几何的物理联系了起来。lévy飞行——步长遵循具有幂律尾部的α-稳定分布的随机游走——产生分形、无标度的点云，其中密集簇与长跳跃共存[15][16][17]。plaszczynski等人[18]通过lévy几何图（lgg）将这一几何结构嵌入网络，其度独立于图大小，簇的数量作为连接尺度的逆幂缩放，且从不发生渗流转变。最近提出的lévy几何超图（lgh）[19]将这一构造推广到k-均匀超边，在单个由一个稳定性指数控制的生成模型中捕获了尺度不变碎片化和高阶重叠。在本推广中，该指数分裂为点过程的飞行指数αf和连接规则的核指数αk，我们独立变化这两者。然而，lgh是一个生成结构模型；它对高阶链接预测算法的影响尚未被研究。 在本工作中，我们探究拓扑衰减的哪个属性对高阶链接预测重要，以及网络结构如何决定有用的范围。我们在相同的归一化有效范围下比较严格的指数和幂律剖面，以一跳和均匀随机游走作为显式共享端点。我们进一步比较验证选择的模型选择方法与基于关联矩阵的算子。我们的贡献如下： 1. **一个可解释、无训练的范围自适应族**（第4节）。我们通过对角校正的路径和为候选集评分，并在共同的归一化有效范围网格上比较剖面。基于slem的谱衰减地平线提供了一个独立的操作量以测试结构–范围对应关系。 2. **一个可控的高阶基准**（第5节）。我们将lgh推广为pareto–lévy连接核，其中距离为d的空间邻居以概率∝d^(-(1+αk))连接；硬最近邻规则作为αk→∞的极限恢复。核指数αk不同于点过程的lévy飞行指数αf，两者独立变化：αk控制单个超边的空间范围，而αf控制点集的碎片化。因此，该基准生成了从近同质结构到强异质、长程区域的超网络，为链接预测启发式方法提供了受控的压力测试。 3. **一项比较与稳健性研究**（第7节）。我们使用20个共享外层分割、数据集级配对推断、验证选择的决策阈值、嵌套负池、两个验证选择的模型选择诊断以及关联算子比较。截断长度扫描（l=2–12）测试范围对形状的结论是否依赖于固定的地平线；集合级共同可达性诊断量化了成对聚合的局限性；核-LGH上的二参数解耦网格将基准难度归因于几何还是核。聚焦采样/核敏感性和两个受控生成器刻画了长程传播有帮助的区域。 这些结果共同提供了一个可扩展的诊断框架来选择拓扑范围，以及一个可调基准来识别长程信息何时有帮助。因此，我们的经验结论适用于传递式、无训练、基于投影的启发式方法。学习型和时间预测器超出了本次比较的范围。 **章节片段** *启发式与学习型链接预测。* 对于成对图，共同邻居、adamic–adar、资源分配[10]和katz[12]等相似性指数仍然是可解释的基线[8][9][11]。学习型高阶预测器包括矩阵 张量分解、嵌入[20]、适配于超边预测的超图神经网络编码器[21][22][23][24]和逻辑模型[25][26]。集合注意力编码器[27]、对抗负采样[28]、时间超图上的归纳式集合游走[29]以及... **问题与预备知识** 设?=(??,?)为N=|??|个顶点上的超图，其中每个超边e∈?的阶|e|≥2。我们评估传递式缺失超边预测：超边被随机分割为?tr和?te（80%/20%），每个测试顶点必须出现在训练投影中。数据集不提供共同的时间戳字段，因此实验聚焦于缺失超边恢复。 **衰减剖线下的成对路径评分** 两个顶点之间的拓扑相似性是连接它们的游走上的加权总和。在转移矩阵p上，定义成对相似度： s_uv^(w)=Σ_{?=1}^{L} w(?)(p^?)_uv 其中w(?)≥0是衰减剖线，它降低较长游走的权重，l是截断长度。由于p是随机的，p^?的每一行对于每个?都是概率分布，因此剖线w——而非谱半径——控制了长程拓扑贡献多少。为了使比较成为一个干净的受控... **lgh作为可控基准** 为探究在完全受控条件下预测器如何响应空间异质性，我们使用lévy几何超图[19]作为具有可调重尾指数的生成器。我们保留原始模型的lévy飞行几何，并将其连接规则推广为重尾核。该构造具有两个重尾成分，我们用不同符号表示并独立变化：点过程的飞行指数αf和连接的... **数据集。** 我们使用来自单纯闭合集合[6]的十个经验高阶数据集，涵盖药物共同给药（dawn、ndc-classes、ndc-substances）、在线讨论线程和问答标签（bars、algebra、tags-ask-ubuntu、tags-math）、立法委员会（house-committees、senate-committees）和共同作者关系（coauth-history）。每个超边是一组节点标识符；我们保留阶≥2的超边。表2总结了数据集。 **子采样与核稳定化。** 该集合从数百到近... **经验数据上的主要比较** 表3报告了20次分割的auc。幂律和katz的均值为0.8894和0.8891。在主要数据集级别上，它们的均差为0.00030（95%自助置信区间[-0.00009, 0.00067]），精确符号翻转p=0.186，Holm校正p=0.371。相对于Select(Katz, hrw)，幂律的差为0.00009（置信区间[-0.00044, 0.00061]；校正p=0.734）。数据集内20次分割级的差异量化了分区敏感性，不被解释为独立实验。图3显示数据集... **讨论** 在测试的无训练族内，沿归一化范围轴移动比在同一范围下选择指数或幂律参数化具有更大的经验效果。它们的平均auc差异为0.00030，在数据集级别不显著。select(katz, hrw)也匹配了严格幂律族，而select(one-hop, katz, hrw)表现略好；因此有用的建模决策是可用范围集及其验证，而非支持某一... **结论** 我们研究了传播范围如何影响保留的缺失超边预测。在20个共享外层分割上，严格幂律和katz剖面以及select(katz, hrw)在数据集级推断下具有实践等效的准确性。将共享的一跳端点添加到模型选择中产生了一个小的诊断增益。关联、预处理、嵌套池和批处理检查保留了范围比函数参数化更重要的核心结论。截断长度也是如此... **credit作者贡献声明** bingqiao gu：撰写—审阅与编辑，撰写—初稿，可视化，软件，方法学，形式分析。longqi li：撰写—审阅与编辑，撰写—初稿，软件，方法学，形式分析。zhaoyang bao：撰写—初稿，软件。zhanwei du：撰写—审阅与编辑，资金获取，概念化。dong li：撰写—审阅与编辑，监督，资金获取。 **代码可用性** 预测器、lgh基准生成器和完整评估协议的代码可合理请求向作者索取。复制包包含锁定的主要评估、截断长度扫描、核-lgh解耦网格、使用估计器审计重新评估的合成基准、集合级诊断以及从保存的结果文件重新生成每个图表和表格的脚本。 **利益冲突声明** 作者声明他们没有已知的相互竞争的财务利益或个人关系，这些可能影响本报告中描述的工作。 **致谢** 本工作得到国家自然科学基金（批准号62376136和62076149）和广东省基础与应用基础研究基金（批准号2024a1515011935）的支持。 bingqiao gu | longqi li | zhaoyang bao | zhanwei du | dong>
这个问题将链接预测与重尾几何的物理联系了起来。lévy飞行——步长遵循具有幂律尾部的α-稳定分布的随机游走——产生分形、无标度的点云，其中密集簇与长跳跃共存[15][16][17]。plaszczynski等人[18]通过lévy几何图（lgg）将这一几何结构嵌入网络，其度独立于图大小，簇的数量作为连接尺度的逆幂缩放，且从不发生渗流转变。最近提出的lévy几何超图（lgh）[19]将这一构造推广到k-均匀超边，在单个由一个稳定性指数控制的生成模型中捕获了尺度不变碎片化和高阶重叠。在本推广中，该指数分裂为点过程的飞行指数αf和连接规则的核指数αk，我们独立变化这两者。然而，lgh是一个生成结构模型；它对高阶链接预测算法的影响尚未被研究。

在本工作中，我们探究拓扑衰减的哪个属性对高阶链接预测重要，以及网络结构如何决定有用的范围。我们在相同的归一化有效范围下比较严格的指数和幂律剖面，以一跳和均匀随机游走作为显式共享端点。我们进一步比较验证选择的模型选择方法与基于关联矩阵的算子。我们的贡献如下：

1. **一个可解释、无训练的范围自适应族**（第4节）。我们通过对角校正的路径和为候选集评分，并在共同的归一化有效范围网格上比较剖面。基于slem的谱衰减地平线提供了一个独立的操作量以测试结构–范围对应关系。

2. **一个可控的高阶基准**（第5节）。我们将lgh推广为pareto–lévy连接核，其中距离为d的空间邻居以概率∝d^(-(1+αk))连接；硬最近邻规则作为αk→∞的极限恢复。核指数αk不同于点过程的lévy飞行指数αf，两者独立变化：αk控制单个超边的空间范围，而αf控制点集的碎片化。因此，该基准生成了从近同质结构到强异质、长程区域的超网络，为链接预测启发式方法提供了受控的压力测试。

3. **一项比较与稳健性研究**（第7节）。我们使用20个共享外层分割、数据集级配对推断、验证选择的决策阈值、嵌套负池、两个验证选择的模型选择诊断以及关联算子比较。截断长度扫描（l=2–12）测试范围对形状的结论是否依赖于固定的地平线；集合级共同可达性诊断量化了成对聚合的局限性；核-lgh上的二参数解耦网格将基准难度归因于几何还是核。聚焦采样/核敏感性和两个受控生成器刻画了长程传播有帮助的区域。

这些结果共同提供了一个可扩展的诊断框架来选择拓扑范围，以及一个可调基准来识别长程信息何时有帮助。因此，我们的经验结论适用于传递式、无训练、基于投影的启发式方法。学习型和时间预测器超出了本次比较的范围。

**章节片段**

*启发式与学习型链接预测。* 对于成对图，共同邻居、adamic–adar、资源分配[10]和katz[12]等相似性指数仍然是可解释的基线[8][9][11]。学习型高阶预测器包括矩阵/张量分解、嵌入[20]、适配于超边预测的超图神经网络编码器[21][22][23][24]和逻辑模型[25][26]。集合注意力编码器[27]、对抗负采样[28]、时间超图上的归纳式集合游走[29]以及...

**问题与预备知识**

设?=(??,?)为n=|??|个顶点上的超图，其中每个超边e∈?的阶|e|≥2。我们评估传递式缺失超边预测：超边被随机分割为?tr和?te（80%/20%），每个测试顶点必须出现在训练投影中。数据集不提供共同的时间戳字段，因此实验聚焦于缺失超边恢复。

**衰减剖线下的成对路径评分**

两个顶点之间的拓扑相似性是连接它们的游走上的加权总和。在转移矩阵p上，定义成对相似度：

s_uv^(w) = σ_{?=1}^{l} w(?)(p^?)_uv

其中w(?)≥0是衰减剖线，它降低较长游走的权重，l是截断长度。由于p是随机的，p^?的每一行对于每个?都是概率分布，因此剖线w——而非谱半径——控制了长程拓扑贡献多少。为了使比较成为一个干净的受控...

**lgh作为可控基准**

为探究在完全受控条件下预测器如何响应空间异质性，我们使用lévy几何超图[19]作为具有可调重尾指数的生成器。我们保留原始模型的lévy飞行几何，并将其连接规则推广为重尾核。该构造具有两个重尾成分，我们用不同符号表示并独立变化：点过程的飞行指数αf和连接的...

**数据集。** 我们使用来自单纯闭合集合[6]的十个经验高阶数据集，涵盖药物共同给药（dawn、ndc-classes、ndc-substances）、在线讨论线程和问答标签（bars、algebra、tags-ask-ubuntu、tags-math）、立法委员会（house-committees、senate-committees）和共同作者关系（coauth-history）。每个超边是一组节点标识符；我们保留阶≥2的超边。表2总结了数据集。

**子采样与核稳定化。** 该集合从数百到近...

**经验数据上的主要比较**

表3报告了20次分割的auc。幂律和katz的均值为0.8894和0.8891。在主要数据集级别上，它们的均差为0.00030（95%自助置信区间[-0.00009, 0.00067]），精确符号翻转p=0.186，holm校正p=0.371。相对于select(katz, hrw)，幂律的差为0.00009（置信区间[-0.00044, 0.00061]；校正p=0.734）。数据集内20次分割级的差异量化了分区敏感性，不被解释为独立实验。图3显示数据集...

**讨论**

在测试的无训练族内，沿归一化范围轴移动比在同一范围下选择指数或幂律参数化具有更大的经验效果。它们的平均auc差异为0.00030，在数据集级别不显著。select(katz, hrw)也匹配了严格幂律族，而select(one-hop, katz, hrw)表现略好；因此有用的建模决策是可用范围集及其验证，而非支持某一...

**结论**

我们研究了传播范围如何影响保留的缺失超边预测。在20个共享外层分割上，严格幂律和katz剖面以及select(katz, hrw)在数据集级推断下具有实践等效的准确性。将共享的一跳端点添加到模型选择中产生了一个小的诊断增益。关联、预处理、嵌套池和批处理检查保留了范围比函数参数化更重要的核心结论。截断长度也是如此...

**credit作者贡献声明**

bingqiao gu：撰写—审阅与编辑，撰写—初稿，可视化，软件，方法学，形式分析。longqi li：撰写—审阅与编辑，撰写—初稿，软件，方法学，形式分析。zhaoyang bao：撰写—初稿，软件。zhanwei du：撰写—审阅与编辑，资金获取，概念化。dong li：撰写—审阅与编辑，监督，资金获取。

**代码可用性**

预测器、lgh基准生成器和完整评估协议的代码可合理请求向作者索取。复制包包含锁定的主要评估、截断长度扫描、核-lgh解耦网格、使用估计器审计重新评估的合成基准、集合级诊断以及从保存的结果文件重新生成每个图表和表格的脚本。

**利益冲突声明**

作者声明他们没有已知的相互竞争的财务利益或个人关系，这些可能影响本报告中描述的工作。

**致谢**

本工作得到国家自然科学基金（批准号62376136和62076149）和广东省基础与应用基础研究基金（批准号2024a1515011935）的支持。

bingqiao gu | longqi li | zhaoyang bao | zhanwei du | dong li>