【论文标题】Large Language Model-driven Meta-structure Discovery in Heterogeneous Information Network
【论文链接】https://arxiv.org/abs/2402.11518（点击文末“阅读原文”即可跳转阅读）
【代码地址】https://github.com/LinChen-65/ReStruct
导读/INTRO
在社交关系、推荐系统和科学引文等领域的研究中，异质信息网络(Heterogeneous Information Network, HIN) 因其形式的通用性和语义的丰富性而成为重要且热门的研究话题。为从复杂异质图中提取出有效信息以助力下游任务，研究者们提出引入元路径 (Meta-path) 和元结构 (Meta-structure) ，即一些在异质图中反复出现的子图结构，用于捕捉特定的高维语义关系，且作为调制信息在节点之间沿着不同类型的边传播的“模板”。然而，现有研究或者由于高度依赖领域专家知识而难以扩展，或者关注于优化下游性能而忽略了所找到结构的可解释性，均未能很好地解决元结构发现的挑战。
近年来，大语言模型 (LLM) 迅猛发展，展现出强大的自然语言理解和推理能力，因而具备理解HIN丰富语义的重要潜力。基于此，我们创新地提出了一个将基于语义的LLM推理与性能导向的演化算法相结合的元结构自动搜索框架——ReStruct，其中设计了3个各有分工的LLM智能体，将候选元结构转化到自然语言空间，利用LLM的推理能力来评估语义上可行的元结构，通过演化算法保证下游任务性能的稳步提升，从而共同优化元结构的语义可解释性和经验性能。实验表明，在多个异质图数据集上，ReStruct在节点分类和推荐任务中都达到了SOTA性能；同时用户调查显示，ReStruct生成的元结构和自然语言解释明显更易于理解。
该工作已发表于KDD 2024 Research Track (录用率约为20%)。
图1. ReStruct框架示意图
01
基本概念与研究动机
异质信息网络 (HIN)，或简称异质图，是指包含多于一种类型的节点和/或边的图。作为一种数学工具，异质图可以统一且简练地描述多个不同种类的个体之间的复杂交互关系。通过拓扑结构和点边类型的变化，存储丰富的语义信息。
元路径 (Meta-path) 指的是由固定的节点类型和边类型，按照固定的顺序构成的有限序列。以这个序列为模板，可以从原始的HIN中匹配出多条元路径实例 (Instances)，作为特定信息的传递通路，从而评估节点的相似度[1]、训练GNN[2] 等。
为扩展表征范围，研究者进一步提出了元结构(Meta-structure) ，将链式序列拓展为图。研究发现元结构有助于进一步提高 HIN 上的机器学习性能[3]。
图2. 异质图、元路径和元结构示例
早期的研究大多基于人工设计的元结构，这严重依赖领域专家知识，难以扩展。为应对这一挑战，近期几项研究[4-6] 提出使用启发式算法、强化学习等方案来自动化元结构设计，但它们只关注于优化下游性能，而忽略了所找到结构的可解释性，偏离了元结构设计的初衷。为解决上述问题，我们首次利用了LLM的推理能力和强大的自然语言生成能力，设计了新颖的LLM智能体模块，实现元结构的自动生成、评估和解释。
02
基于LLM语义推理的元结构性能预测器
为使LLM能理解并评估候选元结构，我们设计了一个语法转换器，将每个元结构都编码为一个自然语言句子。具体而言，我们首先遍历该元结构，将其分解为从源节点到目标节点的所有可能简单路径，其次将每条简单路径转化为用英文 "THAT" 引导的嵌套定语从句，最后用 "AND" 将多条简单路径得到的从句重新组合，得到最终的编码。
图3. 元结构的自然语言编码
在此基础上，我们构建了一个基于元结构自然语言编码来预测其性能的LLM智能体——Few-shot LLM Predictor。为充分利用从历史轮次中收集到的信息以指导决策，我们维护了一个历史样本池 (即图1中的Performance History Pool)，在每次预测时从中采样一批之前见过的元结构和相应的性能，作为示例注入prompt中。根据这批示例，LLM将预测当前元结构的下游表现p，并为自己的预测估计一个置信度c。直观地理解，这样做的出发点是结构相似性与功能相似性的关联：如果LLM认为当前元结构与某些历史结构高度相似，则倾向于为该预测分配更高的置信度。
图4. 基于LLM的元结构性能预测交互示例
03
结合LLM推理与演化算法的元结构优化
为实现元结构性能的稳步优化，我们设计了基于演化算法的无导数优化框架。在元结构搜索过程中，我们维护一个由N个个体组成的种群，每个个体代表一个元结构。在每一代中，我们首先评估每个元结构在给定下游任务上的性能，然后根据性能，按一定比例淘汰性能较差的元结构，留下性能较好的元结构。幸存的元结构将经历繁衍阶段，且繁衍发生的概率与它们的性能表现成正比，以将种群规模恢复到淘汰之前。这里的淘汰 (Elimination) 和繁衍 (Reproduction) 过程共同起到了自然选择机制的作用，实现了元结构种群平均性能的稳步提升。
在完成一轮淘汰与繁衍后，我们将逐个检查新种群中的元结构个体并进行改进。这里我们设计了第二个LLM智能体—— Similarity-oriented LLM Selector，从一系列候选元结构中做出决策，选择更新方向。该智能体一方面接收来自上一个智能体的性能评估信息，另一方面根据候选元结构评估其语义的合理性，在其中做出必要的权衡。这一步可以看作遗传演化框架下的针对性变异 (Mutation)。经过个体修改后的种群将在下一代开始时进入新一轮的评估、淘汰与繁衍，从而形成一个无导数优化的循环。
图5. 基于LLM的元结构更新决策交互示例
04
LLM驱动的元结构差分解释器
为增强所提框架的用户友好性，我们构造了第三个LLM智能体—— Differential LLM Explainer，针对所发现的元结构，自动生成自然语言文本，解释其优越性能的来源。我们设计了以下包含两个步骤的思路链 (Chain-of-thought) 式的提示过程，以指导LLM智能体辨别有助于提高性能的关键结构属性。
结构理解：对于目标元结构，我们首先通过增/删/修改节点/边连接的方式，采样n个邻居元结构，然后要求LLM通过拆分子结构等方式，提炼出邻居结构与目标结构的异同之处。
性能归因：我们将采样得到的邻居结构在下游任务上进行快速测试，得到它们的性能差异，然后要求LLM结合第1步中总结出的结构差异，定位出对于整体性能具有正向或反向作用的子结构，并形成最终的总结文本。
05
实验结果
我们在Amazon、Yelp、ACM、IMDB等来自不同领域的多个数据集上，测试了所提ReStruct框架在节点分类任务和推荐任务上的性能，并与手动设计元路径[2]、自动搜索元路径[5]、自动搜索元结构[4] 的三类基线模型进行比较。结果显示，ReStruct可以稳定取得比已有模型更优的下游任务表现 (图6)，且该性能提升在prompt的具体构造方式和LLM版本发生变化时依然稳健。
图6. 在推荐和节点分类任务上的实验结果
我们进一步开展了一项用户实验，以评估元结构的可解释性。结果显示，ReStruct发现的元结构被最多用户认为是最可理解的，此用户认同比例相比于表现最好的基线模型[6] 高出了61.8%以上 (图7)。此外，通过我们设计的流程得到的元结构解释文本，也得到一致且显著的正面评价 (77.6±2.8%) (图8)。
图7. 所发现元结构的用户可理解性
图8. 差分解释带来的理解增益
结语/CONCLUSION
该工作首次实现了基于LLM智能体与演化算法融合框架的异质图元结构自动搜索发现，所提方法在推荐、科学引文等常用数据集上取得了最优性能，未来有望扩展到更复杂的生物信息或化学分子网络上，助力AI for Science的研究。
参考文献：
[1] Sun, Yizhou, et al. "Pathsim: Meta path-based top-k similarity search in heterogeneous information networks." VLDB 2011.
[2] Wang, Xiao, et al. "Heterogeneous graph attention network." TheWebConf 2019.
[3] Jiang, He, et al. "Semi-supervised Learning over Heterogeneous Information Networks by Ensemble of Meta-graph Guided Random Walks." IJCAI 2017.
[4] Han, Zhenyu, et al. "Genetic meta-structure search for recommendation on heterogeneous information network." CIKM 2020.
[5] Ning, Wentao, et al. "Automatic meta-path discovery for effective graph-based recommendation." CIKM 2022.
[6] Ding, Yuhui, et al. "Diffmg: Differentiable meta graph search for heterogeneous graph neural networks." KDD 2021.
