西风 来自 凹非寺
新方法让大语言模型直接理解复杂图结构
本文提出了一种新方法，即将图（Graph）转化为适合于Transformer架构的线性token序列。
此项技术展示了自然语言中的两个关键属性：局部依赖性和全局对齐性。这意味着
- 需要保留基于前文上下文预测下一个token的能力（局部依赖性）
- 不同图的token序列应当从具有相似特征的token开始或结束（全局对齐性），类似于自然语言文本中常以特定词语开头或结尾。
通过这种方式，在海量文本数据上训练的LLM能够更好地理解图结构中的关系和属性，从而完成如节点计数、最大度数计算和图式形状分类等图推理任务。
机器学习专家Rohan Paul对相关论文进行了总结并分享了实现细节。
他采用了多种技术开发了图线性化方法，包括：
- 利用图中心性（PageRank和度）进行线性化处理
- 通过边排序策略基于节点重要性进行排序
- 应用节点重标记策略以保持全局对齐性
有些开发者已经开始将其集成到RAG系统中。
具体而言，图线性化过程涉及将图的节点和边转换为线性token序列。
研究团队提出了基于图论的多种图线性化方法。其中一种方法是根据图中心性对节点进行排序，包括节点的度和更复杂的PageRank值。
他们通过选择与重要性最高的节点相连的边，并按照一定规则进行排序，再对下一个重要性节点重复此过程。如果多个节点具有相同的中心性值，则随机选择它们的顺序。
另一种方法是基于图退化性进行线性化处理，即利用图的核编号进行排序。k-core分解技术被用于将图分解为一系列嵌套的子图。通过这种方式，能够捕捉到图中最核心的部分并将其线性化。
他们还创建了线图（Linegraph），将原图的每条边转换为线图中的节点。如果原图中两条边相邻，则在线图中对应节点相连。接着使用与核编号相似的排序方法对线图中的节点进行排序。
他们还设计了特定的评估任务来验证方法的有效性，包括节点计数、最大度计算和图案形状分类等任务。
实验中采用了Llama 3 Instruct 8B模型，并设置了特定的参数以确保输出的确定性和一致性。同时与两个基线方法进行了比较：MotifAware基线保持默认的边序，而Random基线则完全随机排序边列表和节点标签。
实验结果揭示了几个重要发现。在节点计数任务中，所有方法的平均误差较低，但准确率表现各异。基于度中心性和PageRank的方法表现最佳。
在最大度计算任务中，由于需要更复杂的计算过程，整体性能略低。在one-shot设置下，使用默认节点标签的度中心性和PageRank方法取得了最佳效果。
关于节点重标记策略的效果因任务而异。在节点计数任务中，除了zero-shot的度中心性方法外，其他大多数方法导致准确率下降，但在平均误差方面通常有所改善。
实验结果还表明，one-shot设置的性能普遍低于zero-shot设置，这表明示例并不总是有助于提高性能。
总体而言，基于中心性的方法（如度中心性和PageRank）在实验中表现优于基于退化性的方法。