图结构转文本序列，大模型直接读懂！图推理性能大涨

大语言模型直接理解复杂图结构的新方法来了：

将图（Graph）转换为适合Transformer架构的线性token序列。

belike：

这种最新图线性化方法，反映了自然语言中局部依赖性和全局对齐性两个关键属性，即：

不仅需要保留基于前文上下文预测下一个token的能力（局部依赖性），而且不同图的token序列应该从具有相似特征的token开始或结束（全局对齐性），就像自然语言文本经常以特定词语开头或结尾。

如此一来，在海量文本数据上训练的LLM也能更好地理解图结构中的关系和属性，如节点计数、最大度数计算和图式形状分类等图推理任务都能完成。

具体如何实现？

机器学习工程师Rohan Paul发帖推荐论文并做了个总结。

用多种技术开发了图线性化方法：图中心性（PageRank和度）、图退化（k-core分解）、节点重标记方案 基于节点重要性创建了边排序策略 应用节点重标记以保持全局对齐

作者使用GraphWave合成数据集进行评估，结果表明他们提出的线性化方法相比基线方法取得了更好的性能，特别是基于度中心性和PageRank的方法在多个任务中表现突出。

有网友已经迫不及待集成到RAG中了：

我一直在寻找这方面的论文。

多种基于图论的线性化方法

在具体方法上，图线性化涉及将图的节点和边转换为线性token序列。

研究团队提出了几种基于图论的图线性化方法。

一种是根据图中心性（Graph centrality）对节点进行排序。

这里的中心性可以是节点的度（Degree centrality），即与节点直接相连的边的数量；也可以是更为复杂的PageRank值，它不仅考虑节点的连接数，还考虑连接到它的节点的重要性。

研究人员根据排序结果选择与重要性最高的节点相连的边，并随机排列这些边，然后对下一个重要性节点重复此过程。如果多个节点具有相同的中心性值，则随机选择它们的顺序。

另一种是基于图退化性（Graph degeneracy）的方法，即通过图的核编号（Core Number）来排序节点。

利用k-core分解,将图分解为一系列嵌套的子图。核编号是指节点在图中最高核的编号。通过这种方式，能够捕捉到图中最核心的部分，并将这些信息线性化。

除了基于节点属性的排序，作者们还考虑了直接对边进行排序的方法。

他们将每个图转换为其对应的线图（Linegraph），将原图的每条边转换为线图中的节点，如果原图中两条边相邻，则在线图中对应节点相连。然后，应用与核编号相同的过程来对Linegraph中的节点进行排序。

为了实现全局对齐性，作者还提出了节点重命名策略。

在这个策略中，不同图中具有最高核编号的节点被重新标记为索引0，以此类推。这样做的目的是让LLM能够将节点索引与其重要性属性之间建立一致的联系。

中心性方法总体优于退化性方法

为了测试上述方法的有效性，作者使用GraphWave生成器构建了合成数据集。

首先构造基础图（循环或链式结构），然后附加预定义形状的图案（motifs）。

研究人员选择了五种基本形状（团、星形、扇形、菱形和树），并包含了这些形状的组合，总共生成了3000个图，平均每个图包含32.33个节点和43.72条边。

实验中设计了三个评估任务：

节点计数：要求模型从边列表推断节点数量 最大度计算：确定图中最大节点度数 图案形状分类：给定详细的图案定义，识别图中存在的图案

实验采用了Llama 3 Instruct 8B模型，使用4bit量化版本。为确保输出的确定性和一致性，temperature参数设为1e-3，sampling参数设为1e-1。

包括zero-shot和one-shot两种设置，并与两个基线方法比较：MotifAware基线，保持图生成过程中的默认边序；Random基线，完全随机的边列表排序和节点标签。

结果显示了以下几个重要发现。

首先，在节点计数任务中，所有方法都显示较低的平均误差，但准确率表现各异。基于度中心性和PageRank的方法表现最好，超过了基线方法。

在最大度计算任务中，由于需要更复杂的计算过程，整体性能低于节点计数任务。使用默认节点标签时，度中心性和PageRank方法在one-shot设置下取得最佳效果。

节点重标记策略的效果因任务而异，在节点计数中，除了zero-shot的度中心性方法外，大多导致准确率下降，但在平均误差上通常有改善。

one-shot设置的性能普遍低于zero-shot，这表明示例可能并不总是有助于提高性能。

基于中心性的方法（度中心性和PageRank）总体上优于基于退化性的方法。

参考链接：https://x.com/rohanpaul_ai/status/1863014451827655118论文链接：https://arxiv.org/pdf/2410.19494