【传知代码】基于曲率的图重新布线（论文复现）

前言：在图形处置惩罚中，一个至关重要的题目是图形的重新布线，即在不改变图形基本结构的条件下，通过调整节点间的连接关系，使图形具有更好的性质，如更低的复杂度、更高的可视化结果或更强的鲁棒性。传统的图形重新布线方法每每依赖于直观的履历或简单的开导式算法，难以适应复杂多变的应用场景，比年来，基于曲率的图重新布线技能应运而生，为图形优化领域带来了新的曙光。与传统的方法相比，基于曲率的图重新布线技能更加注意图形局部的几何特性，通过盘算节点的曲率来指导重新布线的过程。
  本文所涉及所有资源均在传知代码平台可获取
目次
概述
演示结果
核心代码
写在最后

---

概述

        大部分的图神经网络（Graph Neural Networks GNN）接纳消息传递模式，在这种模式下，节点的特性会在输入的图上举行传递。近期的科学研究揭示，来自迢遥节点的信息丢失确实是影响依赖于长途交互使命的消息传输效率的一个关键因素。这种限定通常被命名为“过度挤压”（Over-squashing）。图中每个结点的k跳邻居数量会随着k的增加而指数级增加，这导致远距离结点的信息很难被压缩到固定大小的结点特性中，从而造成信息的丢失，这是过度挤压的缘故原由，这里参考了一下这篇论文，所在 详细如下：

        这篇文章为我们提供了GNN中的过度挤压征象的详细描述，并探究了它是如何从图表中的瓶颈题目中产生的。因此，本研究提出了一种创新的基于边的组合曲率方法，并成功证实了负曲率边是引发过度挤压题目的根本缘故原由。此外，本文还介绍了一种利用曲率举行图重现布线的战略，旨在减轻过度挤压的题目，如下图所示，上图：曲面上曲率的演变可能会减少瓶颈。下图：本文展示了如安在图上做同样的变乱来提高GNN的性能。蓝色代表负曲率；红色代表正曲率：

接下来对本次论文报告的核默算法举行如下一个简单的讲解：
   1）黎曼几何中的一个天然对象是里奇曲率（Ricci curvature），这是一种决定测地线色散的双线性情势，即从“类似”速率的附近点开始的测地线是否保持平行（欧几里得空间）、收敛（球面空间）或发散（双曲空间）。
  2）算法在每次迭代中都会添加一条边来支持图中最负曲率的边，然后移除最正曲率的边。
  3）要求k∈B1(i),l∈B1(j)k∈B1​(i),l∈B1​(j)是为了确保我们在最负曲率的边i∼ji∼j周围添加额外的3-cycle或4-cycle。这是一个局部修改。
  4）原始输入图和重新布线图之间的图编辑距离以max number of iterations的2倍为界。
  5）temperatureτ>0τ>0决定了添加边的随机程度，τ=∞τ=∞表现总是添加最佳边。
  6）移除曲率最大的边是为了平衡曲率和结点的度的分布。
  7）利用Balanced Forman curvature盘算Ric(i,j)Ric(i,j)
  8）optimal Ric upper-boundC+C+用于防止算法使得曲率分布负偏斜。C+=∞C+=∞表现不移除任何边。
  如下图所示：

演示结果

本次代码支持Cora, Citeseer, Pubmed, Cornell, Texas, Wisconsin 脚本自动下载，如不能请参考geom-gcn ，这里不同数据集的配置文件位于./configs/。运行之前必要修改数据集根目次和输出目次：

1. output_dir: $OUTPUT_DIR$
2. data:
3.   root: $DATA_ROOT$

复制代码

测试集和训练集可以接纳下面的方式举行：

1. # train on train data splits
2. python train.py --config-file configs/*.yaml
3. # test on val and test data splits
4. python eval.py --config-file configs/*.yaml
5. // 或
6. search_dir=configs
7. for file in "$search_dir"/*
8. do
9.     python train.py --config-file $file
10.     python eval.py --config-file $file
11. done

复制代码

运行结果可以参考下面的方式，运行日记、模子权重、重新布线结果生存在$OUTPUT_DIR/$DATASET_NAME/ 测试结果（accuracy）生存在./result.csv：

核心代码

下面这段代码实现了对图数据举行流形学习的过程，此中利用了 Ricci 曲率作为度量距离的方法。详细来说，代码实现了一个基于 Ricci 曲率的图形变形算法，即 SDRF（Spectral Deformation and Ricci Flow）算法，该算法重要包含以下步骤：
   1）将 Pytorch Geometric 中的数据类型 Data 转换为 NetworkX 中的数据类型 DiGraph，方便后续的加边、减边操纵。
  2）获取图的邻接矩阵和边的个数。
  3）进入图的加边、减边循环过程，此中 max_iterations 为最大迭代次数：
  4）将 NetworkX 中的数据类型 DiGraph 转换为 Pytorch Geometric 中的数据类型 Data，并返回。
          此中，BFC 算法是一种盘算曲率的方法，用于盘算 Ricci 曲率矩阵。详细来说，它通过盘算情势曲率宁静衡情势曲率之间的差异来盘算 Ricci 曲率。在算法中，balanced_forman_curvature 函数用于盘算 Ricci 曲率矩阵，balanced_forman_post_delta 函数用于盘算边添加之后对 Ricci 曲率的提拔程度。
SDRF 算法是一种流形学习算法，用于在图数据中盘算距离和相似度。通过迭代加边、减边的方法，SDRF 算法可以将图数据举行形变，从而使得距离和相似度更加符合实际情况，代码如下：
 

1. def sdrf(data, max_iterations=10, remove_edges=True, remove_bound=0.5, tau=1.0, undirected=True):
2.     # 1. 将torch_geometric.data.Data实例转化为networkx.DiGraph实例，方便后续加边、减边操作
3.     G = to_networkx(data)
4.     if undirected:
5.         G = G.to_undirected()
6.    
7.     # 2. 获取图信息（邻接矩阵，边的个数）
8.     edge_index = data.edge_index
9.     if undirected:
10.         edge_index = to_undirected(edge_index)
11.     A = to_dense_adj(remove_self_loops(edge_index)[0])[0]  # 邻接矩阵
12.     A = A.cuda()
13.     N = A.shape[0]  # 边的个数
15.     C = torch.zeros(N, N).cuda()  # 初始化Ricci曲率矩阵，即Ric(i, j)
17.     # 3. 进入图的加边、减边循环过程，其中max_iterations为最大迭代次数
18.     for x in range(max_iterations):
19.         can_add = True
21.         # 3.1 根据BFC算法更新Ricci曲率矩阵
22.         balanced_forman_curvature(A, C=C)
24.         ix_min = C.argmin().item()
25.         x = ix_min // N
26.         y = ix_min % N
28.         # 3.2 计算可加边的候选集candidates
29.         if undirected:
30.             x_neighbors = list(G.neighbors(x)) + [x]
31.             y_neighbors = list(G.neighbors(y)) + [y]
32.         else:
33.             x_neighbors = list(G.successors(x)) + [x]
34.             y_neighbors = list(G.predecessors(y)) + [y]
35.         candidates = []
36.         for i in x_neighbors:
37.             for j in y_neighbors:
38.                 if (i != j) and (not G.has_edge(i, j)):
39.                     candidates.append((i, j))
41.         # 3.3 根据边添加之后对Ricci曲率的提升程度，从候选集中选择边k~l进行添加
42.         if len(candidates):
43.             D = balanced_forman_post_delta(A, x, y, x_neighbors, y_neighbors)
44.             improvements = []
45.             for i, j in candidates:
46.                 improvements.append((D - C[x, y])[x_neighbors.index(i), y_neighbors.index(j)].item())
48.             k, l = candidates[np.random.choice(range(len(candidates)), p=softmax(np.array(improvements), tau=tau))]
49.             G.add_edge(k, l)  # 添加边
50.             if undirected:
51.                 A[k, l] = A[l, k] = 1
52.             else:
53.                 A[k, l] = 1
54.         else:
55.             can_add = False
56.             if not remove_edges:
57.                 break
59.         # 3.4 移除具有最大Ricci曲率的边，其中remove_bound为曲率最大上界
60.         if remove_edges:
61.             ix_max = C.argmax().item()
62.             x = ix_max // N
63.             y = ix_max % N
64.             if C[x, y] > remove_bound:
65.                 G.remove_edge(x, y)  # 移除边
66.                 if undirected:
67.                     A[x, y] = A[y, x] = 0
68.                 else:
69.                     A[x, y] = 0
70.             else:
71.                 if can_add is False:
72.                     break
74.     # 4. 将networkx.DiGraph实例转化为torch_geometric.data.Data实例，返回
75.     return from_networkx(G)

复制代码

写在最后

        在探索图形优化技能的蹊径上，基于曲率的图重新布线技能以其独特的视角和强盛的能力，为我们揭示了图形处置惩罚领域的新可能。通过对节点曲率的准确盘算和合理利用，这一技能不仅能够保持图形的整体结构稳固，更能在细节上精雕细琢，使图形显现出更加平滑、雅观的视觉结果。
        回顾我们所探究的内容，基于曲率的图重新布线技能凭借其先进性和实用性，已经在多个领域显现出了巨大的应用潜力。无论是交际网络分析中的用户关系优化，还是城市规划中的蹊径网络计划，甚至是生物科学中的蛋白质交互图研究，这一技能都为我们提供了全新的解决方案，随着技能的不停进步和应用领域的不停拓展，基于曲率的图重新布线技能将会迎来更加广阔的发展空间。我们可以预见，未来的图形优化将更加注意局部细节的优化和整体结构的稳固性，而基于曲率的图重新布线技能正是这一趋势的引领者。
详细复现过程的项目源码、数据和预训练好的模子可从该文章下方附件获取。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。