今天小编分享的科学经验：图结构转文本序列，大模型直接读懂！图推理性能大涨，欢迎阅读。
大语言模型直接理解复杂图结构的新方法来了：
将图（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
