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

西风 发自 凹非寺
量子位 | 公众号 QbitAI

大语言模型直接理解复杂图结构的新方法来了：
将图（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