Just for Life.

明月更几时

0%

基于Metis的大规模图融合算法实现

发表于 更新于
本文字数： 9k 阅读时长 ≈ 8 分钟

这是我第一次开发如此大规模的程序，论文的作者也提供了算法的C语言还是C++版本的软件来？我记不清了。但对于我们来说，Metis只是图划分的上游任务，且不需要完整的Metis算法，只是需要它融合图的一部分，而不需要它的图划分阶段。下游任务必须要用python来处理，考虑到数据结构和数据类型对接的方便性，因此我们考虑使用python来复现Metis算法。还有一点，使用别人的软件，万一结果不好怎么办？万一自己想改算法怎么办？现存的库都是直接返回划分结果，但我们只想融合，自己开发还是灵活。

简介

还有一点是，python第三方库的Metis模块是使用networkx开发的，它的底层是python，在处理超大规模图数据时肯定效率不够高，因此我们选用底层为C++的graph-tool重新开发。

  • 考虑到看官体验，没有结合代码一起写。但建议结合代码一起看，不然各种数据结构用来用去、调来调去很容易眩晕。
  • 开发程序的过程中，使用了大量数据结构的使用和程序的设计技巧，经过精心打磨，使用了桶排序、哈系、队列、列表、字典等结构的花式操作来降低算法时间和空间复杂度，一点点的将$O(n^2)$的程序降低到$O(n\log n)$在降到$O(n)$。如果不是非要用Metis算法来融合图和抱着必死的决心一定要读懂代码，请谨慎观看本文。
  • 这不是我一个人的功劳，还要感谢我聪明的师姐和我一起开发。整体而言，对开发出来的程序表示满意。
  • 文末给出我对大规模图划分的一点想法，欢迎探讨。

程序地址：https://github.com/muyuuuu/Metis
论文地址：http://glaros.dtc.umn.edu/gkhome/node/1186

最后，将我们的算法和目前的第三方库metis与pymetis进行对比，我们实现的性能能吊打metis包，与pymetis还有些差距，文末给出性能对比。

第一次协作开发

图融合思想

原始的图记为$G_0$，融合一次得到一个规模相对较小的图$G_1$，一直融合到$G_n$为止。停止融合的条件由自己设定，比如我设置的是，当图节点的数量少于$\sqrt{n}$时停止迭代，$n$为$G_0$中节点的数量。一个两万节点的图，融合结果如下：

99个节点：
7个节点：

参数约定与注意事项

  • 在原图中，每个节点的权重$\eta$为1，此处不考虑赋权图。
  • $m$表示原始图中边的数量，$n$表示原始图中节点的数量。
  • 注意：本次处理大规模图数据，切勿使用复杂度很高的程序，千万不要暴力破解。合理使用数据结构降低复杂度，以及善用迭代器和生成器，写出来的程序也要防止炸内存。

边处理

边融合：如果两个节点只通过一条边相邻，那么将这两个节点融合在一起，时间复杂度为$O(m)$。

实现思路：此时创建一个向量M和visited（python用列表实现），如果两个节点$u$和$v$相互匹配，则M[u]=v, M[v]=u。如果没有匹配的节点，则$M(u)=u$。融合后的每一个点赋予权重$\eta$，如$u,v$权重为1，融合成了$a$，那么$a$的权重就是2。记录权重的原因是：防止所有节点融合到一个节点，导致后期的图中某个节点的权重过大，划分不均衡。

visited长度为$n$，全部初始化为False，如果一个节点被融合，那么值为True。

返回参数为向量M和visited，用于表示节点的融合关系以及点是否被融合。使用列表的原因是：字典浪费内存，且本次任务中，没有节点的插入、删除和查找，列表性能更高一些。

防止划分不均

为防止融合后的图出现节点分布不均匀的现象，即出现幂律图（有的节点权重$\eta$很大，有的节点权重$\eta$很小），所以放宽了融合的约束条件。并不是只有相邻节点才能融合到一起，考虑使用节点的二跳信息来融合节点，尽管节点间并没有直接相邻。

叶子节点处理

将度为1的节点视为叶子节点，融合根节点相同的叶子节点，实现的时间复杂度为$O(n)$。根据边融合返回的visited参数，遍历节点，只访问度为1且没有被匹配的节点，将他们放到一个列表中，并将每个节点的父节点添加到字典中，字典的key为父节点，value为孩子节点。

之后遍历字典，如果字典某个key对应的值的数量大于2，说明这个根节点有大于等于两个以上的叶子节点，那么对这个key中对应的叶子节点进行两两融合，将融合关系记录到M中，且更改visited。

双胞胎节点处理

双胞胎节点的定义是：如果节点的度相同，且节点的邻接列表相同，则为双胞胎节点。融合双胞胎节点是最难实现的一个功能，结果看到论文中提示用hash来简化计算，简直神来之笔，实现的时间复杂度为$O(n\log n)$。

这个函数仍然需要读入visited参数，只处理还没有被融合的节点。为降低复杂度，按照度进行桶排序，即将不同度的节点放到对应的桶中，桶的取值范围是$[2,64]$。创建一个字典，key为邻接列表（转为字符串，可哈系），值为这个邻接列表对应的节点，这种结构会大大降低复杂度；相反，key为节点，值为邻接列表的数据结构，程序复杂度会达到$O(n^2)$。在每个桶内，遍历节点，并填充到上述字典中。填充完毕后，遍历字典的值，进行两两融合，将融合关系记录到M中，并更改visited。

如果考虑加速执行，可以考虑多进程（python多线程不适合密集计算）来遍历每个桶，毕竟桶里面的处理都一样。利用到字典、哈系、桶排序来降低复杂度，能想出来的一定有很深的程序设计功底。

亲戚节点处理

亲戚节点的定义与双胞胎节点类似，如果节点的度相同，则视为亲戚节点，进行融合。实现的时间复杂度为$O(n)$。

这个函数也需要读入visited参数，只处理还没有被融合的节点。遍历visited列表，记录没有被访问的节点的度，将节点的度作为key，值为节点。融合方法和上面的就一样了，将融合关系记录到M中。

图收缩

在利用二跳信息对节点处理后，可以达到70%到90%的匹配率。

在得到融合关系的列表M后，则开始收缩图的规模，实现的时间复杂度为$O(n)$。创建辅助列表C，如果两个节点$u$和$v$融合到一起，那么C[u]=C[v]，且，在列表C中，只有融合到一起的节点的值相等，不融合到一起的值不相等。

生成C后，按照C中数值的关系，开始获取图的邻接列表。因为值相等表示这些节点融合到一起，所以很容易得到融合后的图的邻接列表adj。比如a,b,c,d,e,f邻接到一起，那么adj[key]={a,b,c,d,e,f}，key是一个自增的变量，表示新图的节点编号，即新图中的key节点由旧图中的a,b,c,d,e,f这几个节点组成。至此，得到了新图和旧图之间的点的对应关系。可以将这个字典保存为json，方便后续处理。

图融合

遍历图收缩返回的数据结构adj，adj中的值对应的所有节点都将视为新图中的一个点，len(adj)就表示新图中节点的数量。

创建一个字典，字典的key是一个元组类型。元组包含两个元素，分别为新图中两个节点的索引，含义是新图中这两个节点之间有边。遍历原始图的边，判断当前边两个点是否进行融合：

  • 如果两个点进行融合，那么这两个顶点在新图上的映射节点相同，则对应边不用考虑，即这两个节点在新图中没有连接边；
  • 若当前边的两个顶点没有进行融合，则按照新旧图的映射关系，将旧图中边上的两个顶点换成映射中新图上顶点，以此作为key，并将边填入字典。这里太绕了，添加部分伪代码进行说明：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 根据原始图和融合后的图节点的映射关系，求出原始图每一个点与新图的映射关系
# index表示原始图节点索引，old_mapping_new[index]表示原图中index节点在新图的索引
for new_ver, old_vers in adj.items():
    for old_ver in old_vers:
        old_mapping_new[old_ver] = new_ver
for edge in edges:
    source, target = edge
    # 取节点的索引
    s_index = graph.vertex_index[source]
    t_index = graph.vertex_index[target]
    # 若当前边的两个顶点没有进行融合
    if old_mapping_new[s_index] != old_mapping_new[t_index]:
        if old_mapping_new[s_index] < old_mapping_new[t_index]:
            new_edges[(old_mapping_new[s_index], old_mapping_new[t_index])] += 1
        else:
            new_edges[(old_mapping_new[t_index], old_mapping_new[s_index])] += 1
# 按照字典中的`key`，将边添加到节点中。
for edge in new_edges.keys():
    new_graph.add_edge(edge[0], edge[1])

之后创建新图的节点，按照字典中的key，将边添加到节点中，就完成了所有工作。

所以整体流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 边融合
M, visited = aggregate.edge_merge(graph, constrain, loop, ver_q)

# 叶子融合
M, visited = aggregate.leaf_merge(graph, M, visited)

# 双胞胎融合
M, visited = aggregate.twin_merge(graph, M, visited)

# 亲戚节点融合
M, visited = aggregate.relative_merge(graph, M, visited)

# 开始收缩
graph, adj = contraction.contract(graph, M)

# 保存旧图与新图之间的映射关系
with open('map/real_data_' + str(loop) + '.json', 'w') as outfile:
    json.dump(adj, outfile, indent=4)

# 开始产生新图
graph = contraction.get_new_graph(graph, adj, M)

# 获取新图的规模
ver_size = utils.get_graph_vertex_num(graph)
edge_size = utils.get_graph_edge_num(graph)

print("当前图节点数是{}，边数是{}".format(ver_size, edge_size), end=', ')

# 小到一定规模就可视化
if ver_size < 200:
    gt.graph_draw(graph, vertex_text=graph.vertex_index, output="output/real_graph_"+str(loop)+".png")

后期处理

别急着走，还没完。在utils.py中写了一个装饰器和log函数，记录每种处理所消耗的时间，以此来检查哪里的程序写的不好；此外，M中True元素的个数除以M的长度，就会得当当前方法的融合率：visited.count(True) / len(visited)。

图融合的重点是：节点是否分不均衡（即一个节点的权重是不是太大，而其他节点权重很小），边割率是不是太高（相邻节点没融合到一起，反而切割了大量的边）。

  • 点平衡率计算：分区中节点最大值 × 分区数 / 原图节点数
  • 边平衡率计算：切割边 / 总边数

本次代码中也进行了相关处理和计算。伪代码如下：

1
2
3
4
5
6
7
8
# 获取新图的一个节点代表旧图的几个节点，是数量
ver_q = performance.get_vertex_map_number(ver_q, adj)
# 获取新图的一个结点代表旧图的哪些节点，是列表
edge_q = performance.get_vertex_map_relation(edge_q, adj)
# 节点平衡率
performance.print_vertex_balance(ver_q, ver_size_list)
# 边割率
performance.print_edge_cut(edge_q, edge_size_list, origin_graph)

我尽力了，但本处的描述过于模糊，建议对照代码进行观看。

在点平衡率的计算中，为降低空间复杂度，使用了队列这种数据结构。设置队列的长度为1，队列中的元素为字典，key为图节点的索引，value为节点权重，是节点的个数。含义是：上次融合图和原图之间节点的对应关系。当本次图融合完成时，传入的adj表示本次图和上次融合图的对应关系。取出队列元素值，即上次融合图和原始图的节点对应关系，按照本次图和上次融合图节点的关系，进行一次套娃，得到本次图中每个节点的权重，并压入队列并return，这样就可以计算点平衡率。

而边平衡率的计算同理，仍然使用队列。每次融合进行一次套娃，得到新图的一个结点(key)代表旧图的哪些节点(value)，(value)是一个列表。然后反转一下这个字典，以原始图节点的索引为key，如果这些点在新图中是一个节点，那么他们的value相同。之后按着边遍历原始图，相邻节点的value不同，则边割率++。

所以我当时是怎么想出来各种结构和算法来实现这些的，感觉好难。

优化

经过测试，能发现Metis算法的优缺点：

  • 优势：能保留节点的中心性。
  • 劣势：节点权重不平衡，边割率太高。

可以看到到处是缺点，这里只给出一种解决方案，毕竟这只是上游任务，没必要太精细。

在融合的时候，点和边的选择顺序是随机的。所以，我们可以限制融合顺序，先融合节点度小的点，在融合度大的点。目前，此方案仅增加在边处理中，其他合并没有增加，但是一个道理。

结论：节点平衡率能下降，比之前好多了，如果还觉得高，其他融合函数也进行融合限制即可。边割率一如既往的高，毕竟初试划分很随机，不能纵观全局，这是导致边割率过高的原因。但降低边割率并不是粗划分的重点。

性能对比

与metis包的性能对比

pip install metis即可。测试数据为一个很小规模的图数据，需要注意的是：我们的算法是图融合的，metis是用来图划分的。 严格意义上来讲没有可比性，但metis这个包的执行结果太让人失望了。

我们的

我们程序的融合部分耗时为0.57秒。

目前第三方的

metis包的官网：
https://metis.readthedocs.io/en/latest/

pip install metis netowrkx==2.3后，实现了两种读取数据的方式，结果直接爆炸，且networkx已经更新到2.5版本，但metis只支持到了2.3。目前第三方支持了两种读取数据的方式，第一种是读入邻接列表，第二种是通过networkx读入数据并转为metis能处理的类型。

首先是networkx读入图数据并转换类型，我按照官方的说明实现了一下：

1
2
3
g = nx.read_adjlist("email-Eu-core.txt", nodetype=int)
metis.networkx_to_metis(g)
(edgecuts, parts) = metis.part_graph(g, 3)

然后直接内存溢出：

我放心不下，就试试手动读入图数据：

1
2
3
4
5
6
7
8
9
10
11
12
def createGraph(filename) :
    G = nx.Graph()
    for line in open(filename) :
        strlist = line.split()
        n1 = int(strlist[0])
        n2 = int(strlist[1])
        G.add_edges_from([(n1, n2)])
    return G

g = createGraph("email-Eu-core.txt")
metis.networkx_to_metis(g)
(edgecuts, parts) = metis.part_graph(g, 3)

直接段错误：

官方还支持读入邻接列表，然后我又实现了一下：

1
2
3
4
5
6
7
8
9
10
11
12
def read_data(filename):
    adj_list = []
    with open(filename, 'r') as f:
        lines = f.readlines()
        for line in lines:
            temp = line.split(' ')
            adj_list.append((int(temp[0]), int(temp[1])))
    return adj_list

adjlist = read_data('email-Eu-core.txt')
g = metis.adjlist_to_metis(adjlist)
(edgecuts, parts) = metis.part_graph(g, 3)

然后还是段错误：

这种东西就没法比了，对面都执行不出来，对比的代码也会放到github上。

与pymetis的对比

按照官网实现一下pymetis(版本：2020.1)的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import pymetis
import time

def read_data(filename):
    adjacency_list = []
    with open(filename, 'r') as f:
        lines = f.readlines()
        for line in lines:
            temp = line.split(' ')
            adjacency_list.append(np.array([int(temp[0]), int(temp[1])]))
    return adjacency_list

adjacency_list = read_data('email-Eu-core.txt')
print(len(adjacency_list))

since = time.time()
n_cuts, membership = pymetis.part_graph(100, adjacency=adjacency_list)
end = time.time()

print(end - since)

程序执行时间在0.35秒到0.5秒之间。虽然我们在叶子节点处理中加入了额外的信息处理，但pymetis执行的时间还包括反粗划分与图划分，所以我们的程序还有较大的改进空间。比如多进程、使用numpy代替list等等，前路漫漫，还需努力。

结语

个人还是比较喜欢这类论文的，将程序设计和理论分析完美融合。不会写程序只会发论文的计算机人我通常认为是在耍流氓，不去写代码而只是高高在上的提所谓的idea，其实根本不知道底层发生了什么。

最后感谢我的师姐，在双胞胎处理、亲戚节点处理、图融合上提出了关键性想法，使得程序圆满开发成功。（她在写代码这方面真的很聪明的！！！）

也许有读者能看出来，这部分代码是为了图划分做准备，但图融合只是图划分的上游任务。关于大规模图划分我想说的：

  • 如果使用传统启发式算法，图融合，图划分，最后反粗划分，这种思路和算法大概率已经烂大街了，无非是一丢丢可有可无的改进。所以边割率、平衡率和速度要远远好于目前的成果才算可以。即使发了论文也不一定有人看，毕竟大家都知道是那套东西。或者说，图划分的算法复杂度更多的取决于分割的算法，融合只是上游任务。
  • 如果使用图神经网络去划分，用哪种图网络是一个问题，GraphSAGE？GAT？此外损失函数如何设计又是一个问题，如何把边割率和平衡率融入到一个函数里，这更像是多目标优化。而且也会牵扯到其他问题，图的节点、边该如何用数字去表示。假设这几个问题都解决了，那么，网络训练又是一个问题，能否收敛？收敛的快不快？图神经网络便无法再用时间复杂度$O(n)$去衡量，毕竟要迭代好几次呢，每次迭代可能也要很久。
  • 我看了近几年论文，在大规模图划分上并没有发现有做的很好的。如果取得了很好的结果或有突破性思路，时间慢一点应该可以被接受。如果效果只是好了一点点但付出了巨大的时间、计算资源的代价，个人认为只具备学术论文价值，但不具备工程实际应用的价值，所以我个人不看好这个方向。
  • 图分割很大程度上是为下游任务提供支持，如生物、化学、交通网络等。其效率比起效果更应该受到重视。但神经网络的训练代价太大，程序消耗过多时间在图分割上，甚至需要GPU反而是本末倒置。传统算法用着CPU都划分完了，且结果也不是很差，神经网络还在那用着2080反向传播，loss还很大，这说不过去。
  • 图的节点、边该如何用数字去表示？关于这一点，已经有不少图嵌入表示的论文了。但那些表示是否适合图划分却不得而知，或者说，需不需要为了图划分而单独的去设计一种图嵌入表示算法。
  • loss的收敛问题。关于这一点，我认为是个坑，或者需要一些数学工具去优化。我尝试过简单的将边割率、平衡率的损失直接相加，结果震荡的很严重。且边割率会受到平衡率的影响，即总体loss在下降，平衡率loss在下降，但边割率的loss却在上升，所以整体loss下降只是因为平衡率loss下降了。我也尝试过分批训练，即前200个epoch训练平衡率，后200个epoch训练边割率，如此轮回，但损失还是震荡或者回升。关于这一点，我并没有很好的想法。学完《工程优化》这门课程后发现这是多目标优化的问题，需要将神经网络的多任务学习变成多目标优化，这个在顶会上已经有不少的论文了，可以借鉴下他人的思路。
  • 如果说使用神经网络算法去完成图划分，时间比启发式算法快，且效果比它还要好。今年的顶会就是您的，这也许会颠覆目前图划分的思想和现有的图划分软件，可惜我目前并没有这个实力和突破性的想法。
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章