《Electronics》:Canonical and Compact Representations in Small Language Model Graph Classification
编辑推荐:
小型语言模型(Small Language Models, SLMs)能够对序列化为文本的图进行分类,但图的三个特性使这一转换过程复杂化:图没有固有的顶点顺序,因此一个图会产生多种文本表示;在固定的输入预算下,显式序列化的文本过长;单一序列化仅展示结构的单一视
小型语言模型(Small Language Models, SLMs)能够对序列化为文本的图进行分类,但图的三个特性使这一转换过程复杂化:图没有固有的顶点顺序,因此一个图会产生多种文本表示;在固定的输入预算下,显式序列化的文本过长;单一序列化仅展示结构的单一视图。本研究在统一协议下评估了相应的设计对策。将原始邻接表和边列表与度排序(degree-sorted ordering)、两种精确规范化序列化(exact canonical serializations)、确定性广度优先搜索(Breadth-First Search, BFS)剖面、紧凑的Graph6和NetLSD编码、软提示(soft-prompt)基线以及基于验证加权的晚期融合(late fusion)进行比较。在五个TUDataset基准和三个指令微调的小型语言模型上,精确规范化序列化在15个设置中的14个优于原始邻接表,晚期融合在所有15个设置中均优于该基线。紧凑编码分别将输入缩短了67.7%和42.2%,且两者的平均准确率均超过基线。经多重比较校正的配对分析证实了两种规范化序列化、确定性剖面、度排序、NetLSD和晚期融合的增益。因此,序列化是一个重要的建模决策,而不仅仅是预处理步骤。本研究通过在单一协议下测量准确率、排列鲁棒性、输入长度和预处理成本,为该决策提供了实证基础。
论文解读文章
一、研究背景与问题
图(Graph)是关系型数据的自然表示形式,涵盖分子、蛋白质、社交网络和交互系统等广泛领域。图分类(Graph Classification)作为机器学习中的核心问题,传统上通过图核(Graph Kernels)和图神经网络(Graph Neural Networks, GNNs)加以解决。近年来,语言模型(Language Models, LMs)被探索作为图分类器,其基本思路是将图转换为文本描述并对模型进行微调。这一方向具有吸引力,因为它复用了预训练语言模型的广泛建模能力,但也引入了一个基本的方法论问题:图应如何被书写为文本?
与普通文本不同,图没有内在的节点顺序。两个邻接表可能描述同一个图,但在语言模型看来却截然不同。因此,图即文本(graph-as-text)分类对任意的序列化选择高度敏感。以往研究尝试通过基于排列的训练或节点排序启发式来降低这种敏感性,但这些方法可能增加训练成本,且未能完全解决表示问题。与此同时,实际输入限制和注意力预算使得图序列化的长度和冗余度对小型语言模型(Small Language Models, SLMs)尤为重要。
现有研究虽已表明编码和结构对齐对处理图的语言模型至关重要,但多数研究侧重于通用图推理、节点级任务或图编码器与大型语言模型的对齐。针对监督式整图分类(supervised whole-graph classification)场景,在数据集、划分、骨干网络、微调程序和预测目标均受控的条件下,精确规范化、启发式排序、紧凑编码和连续图提示如何表现,仍缺乏系统的实证回答。本研究正是针对这一空白,将图表示作为实验变量,在统一协议下系统比较多种表示策略。
二、研究内容与核心结论
研究人员在五个TUDataset基准数据集(PROTEINS、MUTAG、BZR、PTC_MR和IMDB-BINARY)上,使用三个指令微调的小型语言模型(Llama-3.2-1B-Instruct、Qwen2.5-1.5B-Instruct和SmolLM2-1.7B-Instruct),系统评估了十种图表示方法。所有实验采用十折交叉验证,数据集划分、提示格式、适应程序和预测目标在所有表示间保持一致。
研究得出以下核心结论:第一,图表示选择对SLM图分类性能具有重大影响,最弱与最强表示之间的准确率差距大于最弱与最强GNN基线之间的差距;第二,按结构标准而非数据集提供的编号对顶点排序,在多数设置中能提升准确率,其中精确规范化序列化在15个设置中的14个优于原始邻接表;第三,紧凑表示(Graph6和NetLSD)在显著缩短输入长度的同时保留了部分准确率增益,揭示了实际的准确率—词元权衡;第四,验证加权晚期融合在三个结构视图上取得最佳聚合性能,是唯一在所有15个设置中均优于邻接基线的表示方法,表明不同结构表示暴露了互补的预测信息。
三、关键技术方法概述
研究人员构建了一套统一的实验框架,涵盖多种图表示策略。原始邻接表和边列表保留数据集提供的顶点标识符作为基线;度排序邻接表按顶点度降序排列并重新编号;Bliss和Pynauty两种精确规范化工具将节点标签作为顶点颜色进行规范化序列化;确定性BFS剖面为每个顶点构建广度优先层并选取字典序最小的根剖面作为表示;Graph6采用Bliss规范顺序生成紧凑无损拓扑编码并附加规范标签序列;NetLSD使用热迹签名(heat-trace signature)构建置换不变的谱描述符,辅以度直方图和标签直方图;软提示基线通过统计向量MLP或GNN生成16个图特定虚拟词元。所有文本表示使用LoRA(Low-Rank Adaptation)适配,软提示变体额外训练提示模块。验证加权晚期融合基于各视图在验证子集上的负对数似然倒数计算权重,在测试时固定使用。
四、研究结果分述
分类性能。 十折交叉验证结果显示,图表示对分类性能有显著影响。原始邻接表从未在15个设置中成为最强表示。晚期融合在每个SLM上均取得最高平均准确率,总体平均准确率为最高,而邻接表基线为最低。三个融合视图(Pynauty、BFS剖面、Bliss)均具有竞争力,其中Pynauty的单视图平均准确率最佳。在重训练的GNN基线中,GIN最强,但最强GNN基线优于原始序列化却劣于所有规范化顶点顺序的显式邻接式序列化。
启发式排序与软提示基线。 度排序邻接表总体平均准确率显著优于原始邻接表,在15个设置中的13个胜出,平均排名介于两种精确规范化序列化之间。这表明规范化收益的很大一部分已由无同构保证的确定性度排序获得,但度排序不提供不变性保证。软提示基线在某些情况下具有竞争力,但未提供最强总体结果,配对分析中两种软提示变体的改进均未获得统计支持。
配对比较。 将15个SLM—数据集设置作为配对观测,晚期融合、度排序邻接表、Bliss、Pynauty、BFS剖面和NetLSD相对于邻接表基线的改进均获得统计支持(经Holm-Bonferroni校正)。晚期融合是唯一在所有15个设置中均改进基线的表示方法,并在9个设置中取得最高准确率。
顶点重标记鲁棒性。 Bliss和Pynauty的审计一致性为完全一致,确认实现产生了字节相同的输出。Graph6的稳定性来自Bliss规范化。NetLSD为置换不变描述符。BFS剖面的翻转率低于报告精度,但其审计一致性仅为经验结果。邻接表、度排序和边列表在重标记下均表现出可测量的预测变化。
晚期融合行为。 三个融合视图在不同设置中各有优势,没有任何单一视图可靠地占优。更强的结果是,即使选择每个设置中测试准确率最高的视图作为神谕(oracle),晚期融合仍在15个设置中的12个胜出。由于融合权重仅从验证数据估计而神谕使用测试准确率,这一比较对融合不利,但仍支持融合优于单视图选择。
准确率—效率权衡。 Graph6将平均词元长度减少67.7%,同时将准确率从基线提升;NetLSD减少42.2%的词元长度并取得更强的准确率增益。两种紧凑表示在准确率—词元权衡中占据不同位置。预处理成本方面,精确规范化在图规模上开销很小,BFS剖面是最昂贵的表示,其成本随图大小增长远快于输入长度。
五、讨论与结论总结
讨论部分指出,图序列化应被视为核心建模决策而非预处理步骤。精确规范化序列化通过减少任意节点顺序变化帮助小型语言模型利用图结构;度排序启发式在不提供不变性的情况下恢复大部分增益,从而区分了稳定排序的收益与形式保证的收益;紧凑表示提供了实际的准确率—词元权衡;验证加权晚期融合表明不同结构表示携带互补的预测信息。研究局限性包括:实证范围限于中小规模基准图;晚期融合增加推理成本;紧凑表示仅涵盖Graph6和NetLSD两种;研究聚焦表示选择而非语言模型架构设计。
结论部分翻译如下:本文研究了图表示如何影响小型语言模型图分类。研究比较了原始邻接表、度排序启发式排序、精确规范化序列化、紧凑图编码、软提示基线和基于三个结构视图的验证加权晚期融合策略。结果表明,表示选择是图即文本学习中的主要因素。精确规范化序列化在15个评估设置中的14个优于原始邻接表序列化,表明减少任意节点顺序变化有助于小型语言模型利用图结构。度排序启发式在不提供不变性的情况下恢复大部分增益,从而区分了稳定排序的收益与形式保证的收益。Graph6和NetLSD等紧凑表示在保留部分准确率增益的同时大幅缩短输入长度,揭示了实际的准确率—词元权衡。对两个精确规范视图和BFS剖面视图的验证加权晚期融合在所评估方法中取得最佳聚合性能,并且是唯一在每个设置中均改进邻接基线的表示方法,表明不同结构表示暴露了互补的预测信息。这些结论适用于所评估的中小图规模范围。总体而言,研究结果表明图序列化应被视为核心建模决策,而不仅仅是预处理步骤。对于小型语言模型,规范化和紧凑图表示提供了简单、模型无关的方式,可在控制输入长度的同时提高图分类准确率。