如何将简单加权图转换为超图以适配hMETIS超图划分算法

存在成熟的普通加权图到超图的映射技术，常用可直接适配hMETIS的实现方案如下：

• 团扩展映射：最通用的hMETIS适配方案，将普通图中每个顶点的k阶邻域转换为1条超边，邻域范围内所有顶点都归属该超边。原边权重可直接作为超边权重，也可按照邻域重叠度做加权调整。无特殊业务要求的场景下，选择1阶邻域团扩展即可生成完全符合hMETIS输入要求的超图结构，适配性最高。
• 边到超边直接映射：如果你的划分需求不需要保留高阶邻接关系，可直接将普通图的每条边对应为1条二元超边，原边权重直接复用为超边权重。该方案改造成本最低，完全保留原有普通图的权重逻辑，不需要额外做特征计算。
• 属性关联映射：如果你的图节点带有业务属性，可将具有同类属性的节点归入同一个超边，比如节点标签相同、特征向量相似度达标、归属同一业务分组等规则都可作为超边的生成依据，该映射方式生成的超图更贴合业务场景的划分需求。

对接hMETIS时，完成超边映射后只需按要求的.hgr格式输出即可：第一行标注超边总数、顶点总数两个数值，接下来每一行对应一条超边，开头可标注权重值，后面依次列出该超边关联的所有顶点编号。

内容的提问来源于stack exchange，提问作者Aavash Bhandari