基于概念的GNN模型：解释性与性能并重的图神经网络模型

Dobrik GeorgievUniversity of Cambridgedgg30@cam.ac.ukPietro BarbieroUniversity of Cambridgepb737@cam.ac.ukDmitry KazhdanUniversity of Cambridgedk525@cam.ac.ukPetar Veliˇckovi´cDeepMindpetarv@deepmind.comPietro LiòUniversity of Cambridgepl219@cam.ac.ukPreprint. Under review.+v:mala2255获取更多论文0基于算法概念的可解释推理0摘要0最近关于图神经网络（GNN）模型的研究成功地将GNN应用于经典图算法和组合优化问题。这具有诸多好处，例如在不满足预条件的情况下应用算法，或者在没有足够的训练数据或无法生成训练数据时重用学习模型。不幸的是，这些方法的一个关键障碍是它们缺乏可解释性，因为GNN是无法直接解释的黑盒模型。在这项工作中，我们通过将现有的基于概念的解释方法应用于GNN模型来解决这个限制。我们引入了基于概念的GNN模型，它依赖于对GNN读出机制的修改。通过三个案例研究，我们证明：（i）我们提出的模型能够准确地学习概念，并基于所学概念为每个目标类提取命题公式；（ii）我们的基于概念的GNN模型在性能上与最先进的模型相当；（iii）我们可以推导出全局图概念，而无需明确提供任何关于图级概念的监督。01 引言0图神经网络（GNN）已成功应用于涉及具有不规则结构的数据问题，例如量子化学（Gilmer等，2017），药物发现（Stokes等，2020），社交网络（Pal等，2020）和物理模拟（Battaglia等，2016）。最新的GNN研究领域之一是将GNN应用于经典算法的仿真（Cappart等，2021）。具体而言，这项研究探索了将GNN应用于迭代算法（Veliˇckovi´c等，2020b；Georgiev和Liò，2020），基于指针的数据结构（Veliˇckovi´c等，2020a；Strathmann等，2021）甚至规划任务（Deac等，2020）的应用。重要的是，这些工作表明GNN能够对比训练过程中见过的图形更大的输入图形进行强大的泛化。0不幸的是，在所有上述情况中，这些最先进的GNN模型都是黑盒子，其行为无法直接理解/解释。实际上，这可能导致对这些模型缺乏信任，在诸如医疗保健等安全关键应用中应用和监管这些模型变得具有挑战性。此外，这种缺乏可解释性也使得难以提取这些模型学到的知识，这阻碍了用户更好地理解相应的任务（Adadi和Berrada，2018；Molnar，2020；Doshi-Velez和Kim，2017）。0关于可解释人工智能（XAI）的最新工作引入了一种新型的卷积神经网络（CNN）解释方法，称为基于概念的可解释性（Koh等，2020；Kazhdan等，2020b；Ghorbani等，2019；Kazhdan等，2021）。基于概念的解释方法0arXiv:2107.07493v1[cs.LG]15Jul2021visited nodeedcbafCBGNNCBGNN3321004458248155n12345CBGNNCBGNNabcdeS1 = {a, b, e, c}S2 = {d}42851216mcd = 1CBGNNCBGNN2+v:mala2255获取更多论文0BFS并行着色Kruskal算法0未被访问过 已访问过邻居0v c = 10颜色：0未着色，具有优先级颜色1、2和3，已见颜色4未见0c n = 40MST中的边访问边0轻边访问不同集合中的节点0图1：我们的概念瓶颈图神经网络（CBGNN）方法的概述。重要的是，CBGNN模型可以被训练以提取给定任务的概念信息以及算法规则。我们给出了3个算法的示例，展示了CBGNN如何从输入数据中提取概念，然后使用这些概念计算输出。0提供以人类可理解的单位而不是单个特征、像素或字符（例如，车轮和车门的概念对于汽车的检测很重要）（Kazhdan等，2020b）的模型解释。特别地，概念瓶颈模型（CBMs）的工作依赖于概念，并引入了一种新型的可解释性设计的CNN，它通过两个不同的步骤进行输入处理：从输入计算一组概念，然后从这些概念计算输出标签（Koh等，2020）。0在本文中，我们将CBMs的思想应用于GNN模型，通过引入概念瓶颈图神经网络（CBGNN）。特别地，我们依赖于编码-处理-解码范式（Hamrick等，2018），并在GNN模型的输出之前应用概念瓶颈层-参见图1。通过这样做，我们能够提取步骤级组合优化方法（Veliˇckovi´c等，2020b，a;Deac等，2020; Strathmann等，2021）的步骤更新的更新/终止规则。0重要的是，我们展示了通过依赖于一组合适的概念并对其进行监督，我们能够推导出经典算法（如广度优先搜索（Moore，1959）和Kruskal算法（Kruskal，1956））的规则，以及更高级的启发式算法，如并行图着色（Jones和Plassmann，1993）。此外，我们提出了一种利用节点级概念提取图级规则的方法。我们的评估实验表明，我们提取的所有规则都能够很好地推广到5倍大的图。0总结起来，我们在这项工作中做出以下贡献：0•提出概念瓶颈图神经网络（CBGNN），一种依赖于中间概念处理的新型GNN。据我们所知，这是第一次将概念瓶颈方法应用于GNN。0•使用三个不同的案例研究（BFS，图着色和Kruskal算法）定量评估我们的方法，表明我们的CBGNN方法能够达到与现有最先进方法相当的性能0• 通过演示CBGNN模型使用的概念可以用于提供总结其已学习的启发式规则，定性评估我们的方法02 相关工作0GNN可解释性最近的研究开始探索在GNN的背景下应用XAI技术的应用。例如，Pope等人（2019）；Baldassarre和Azizpour（2019）；Schnake等人30（2020）将用于CNN应用的基于特征重要性的梯度方法（如类激活映射或层级相关性传播）调整为GNN，以识别负责个别预测的最重要的节点/子图。或者，Ying等人（2019）；Vu和Thai（2020）；Luo等人（2020）专注于GNN可解释性独特的更复杂的方法，如基于互信息最大化或特征解释的马尔可夫毯条件概率。重要的是，这些工作侧重于涉及社交网络、化学或药物发现的GNN任务和基准，而不是侧重于组合优化任务，这是本文的重点。此外，这些工作侧重于事后解释预训练的GNN，而我们侧重于构建可解释性设计的GNN模型。最后，这些工作侧重于基于特征重要性的解释方法（即返回输入节点/子图的相对重要性），而我们则依赖基于概念的解释方法。0基于概念的可解释性一系列现有的工作已经探索了应用于CNN模型的各种基于概念的解释方法。例如，Ghorbani等人（2019）；Kazhdan等人（2020b）；Yeh等人（2019）的工作介绍了从预训练的CNN中无监督或半监督方式提取概念的方法。Chen等人（2020）；Koh等人（2020）的工作依赖于概念，以设计可解释的CNN模型，通过两个不同的步骤进行处理：概念提取和标签预测。其他关于概念的工作包括研究概念与解缠结学习之间的关系（Kazhdan等人，2021），以及使用概念处理数据分布转移（Wijaya等人，2021）。重要的是，这些工作仅在CNN的背景下探索概念，而Kazhdan等人（2020a）是唯一一个在RNN模型背景下探索概念的工作。在这项工作中，我们专注于基于概念的GNN可解释性，其中，类似于Koh等人（2020），概念是人为指定的。0GNN的组合优化根据Cappart等人（2021）定义的层次结构，我们的工作属于步骤级方法。我们直接扩展了Veliˇckovi´c等人（2020a，b）的工作，因此我们使用这些工作中提出的模型作为基准。我们不将我们的模型与算法级组合优化方法（Xu等人，2020；Tang等人，2020；Joshi等人，2020）或单元级方法（Yan等人，2020）进行比较，原因如下：算法级方法通常对每个数据样本给出一个输出（而不是每个步骤给出一个输出），但给定算法的规则/不变性来自于迭代的进行方式，使得算法级组合优化不太适用于概念瓶颈。单元级学习侧重于学习计算的原始单元，例如取最大值或合并列表，然后手动组合这些单元-在这个级别上进行解释不会带来很大的好处。据我们所知，只有Veliˇckovi´c等人（2020a）尝试解释GNN预测，使用GNNExplainer（Ying等人，2019）。然而，他们的模型（i）不是设计可解释的，（ii）需要进一步优化才能为单个样本提供局部解释。所有其他先前的工作都以黑盒方式操作，并没有考虑学习模型的可解释性。03 方法论0编码-处理-解码根据Veliˇckovi´c等人（2020b）提出的神经执行“蓝图”，我们通过编码-处理-解码架构（Hamrick等人，2018）对算法进行建模。对于每个算法A，编码器网络fA将算法特定的节点级输入zi编码为潜在空间。然后，使用处理器网络P（通常是GNN）处理这些节点嵌入。处理器以编码后的输入Z(t)={zi}i∈V和图的边索引E作为输入，产生潜在特征H(t)={hi∈R|L|}i∈V，其中|L|是潜在维度的大小。与之前的工作不同，我们通过首先将潜在嵌入通过解码器网络g'A进行处理，该网络为每个节点生成概念C(t)={c(t)i∈(0,1)|C|}，其中|C|是概念的数量。然后，将这些概念通过概念解码器gA传递，以产生节点级输出Y(t)={yi}。0在适用的情况下，我们还利用终止网络TA来决定何时停止。然而，与之前的工作相比，我们观察到，如果我们基于潜在的下一步嵌入（即对执行一次迭代后状态的信念）计算终止概率，训练会更加稳定。此外，我们发现仅使用平均节点嵌入作为TA的输入是不足够的-如果只有一个节点应该告诉我们信息，那么平均化会模糊信号。0+v:mala2255获取更多论文40m bc0m db0m ab0m be0h b0h a0h c0h d h e0h f h' b0c b0概念解码器0y b0节点级输出解码器0节点嵌入0h G0y G0PrediNet0图级输出解码器0图2：我们GNN架构的高级概述：左：（方程1-4）为了产生节点级输出，来自相邻节点（mij）的消息与当前节点表示（h b）相结合，得到更新后的表示（h'b）。然后从更新的表示中提取概念（c b），并从概念中提取节点级输出（yb）。右：（方程5-8）通过PrediNet将节点嵌入传递给获得图级嵌入（h G）。我们直接从潜在状态hG 中提取图级输出yG（在我们的情况下是终止概率）-通过对节点概念进行完全枚举方法提取图级概念。0我们选择使用经过改进的PrediNet（Shanahan等，2020）架构的输出作为是否继续迭代的依据。PrediNet被设计为表示基本命题的合取，因此它（理论上）可以捕捉到终止规则的逻辑偏差。整个过程在图2中概述，并在下面的方程中进行了总结：0z（t）i = f A * x（t）i，h（t-1）i0H（t）= P * Z（t），E *（2）0c（t）i = σ * g' A *0y（t）i = g A * c（t）i *（4）0z'（t）i = f A * y（t）i，h（t）i0H'（t）= P * Z'（t），E *（6）0H（t）= PrediNet（H'（t））（7）0τ（t）= σ * TA *0H（t）=（8）0其中σ是一个逻辑sigmoid函数。当使用T A时，方程1-8会重复执行，如果τ（t）> 0.5。0编码输入的组合以及给定节点的潜在状态，不仅包含关于给定步骤的输出的足够信息，还包括：（i）节点的当前状态和（ii）其邻域中其他节点状态的观察。如果我们的概念被设计来捕捉（i）或（ii）中的某些知识，那么我们可以提取有意义的算法输出解释，而无需提供任何关于算法如何工作的明确信息（定理，不变量等）。0显式关系GNN架构一些图级任务（例如决定终止）可以简化为对所有节点的逻辑公式-对于我们考虑的算法和概念，终止可以简化为存在具有特定属性的节点。（请参见图级规则提取）。我们通过将PrediNet（Shanahan等，2020）调整为图领域来将这种逻辑偏差引入终止网络τ。PrediNet网络架构学习表示基本命题的合取/析取，因此非常适合终止任务。我们在附录A中列出了我们对PrediNet进行适应我们任务的两个小修改。0通过检查概念解码器gA的权重，可以确定算法A的节点级算法规则。为了实现这一点，我们使用了开源软件包logic_explained_networks1（Barbiero等，2021），该软件包实现了从概念瓶颈神经网络（Gori，2017；Ciravegna等，2020）中提取基于逻辑的解释的广泛技术集合。该库的输入包括（i）节点级输出解码器权重，（ii）预测的01 Apache 2.0许可证。0+v:mala2255获取更多论文∀j τ ′j = 1 ⇐⇒ (∃c ∈ Uj. ∀Ii ∈ I. cIi = T (Ii))(10)50从训练数据中提取概念，并生成逻辑公式作为输出（Mendelson，2009）。通过构造，从概念C到输出O学习的概念解码器¯gA≈gA是一个布尔映射。作为任何布尔函数，它可以通过其真值表（Mendelson，2009）转换为逻辑公式的析取范式。概念解码器gA的权重用于选择每个输出任务的最相关概念。为了得到简明的逻辑解释（在我们的实验中，仅在图着色任务中需要许多概念作为输入），我们在损失函数中添加了一个正则化项，最小化概念解码器权重W的L1范数，从而导致W的稀疏配置。稍后，在训练时期t prune，首层权重按概念逐个进行修剪，即删除从最不相关的概念出发的所有权重：0˜ W 1 j =  W  1 j I || W 1 j || 1 ≥ max i  || W  1 i || 1 / 2 ，其中 i =0其中I是指示函数，W1是第一层的权重。有关逻辑提取的更多细节，请参见附录B。0提取算法终止规则在决定是否继续执行时，我们利用了一些图算法在迭代过程中会一直迭代，直到存在具有特定概念组合的节点的事实。由于不清楚我们应该朝着哪种概念组合进行监督，我们在提取终止规则时采用了完全枚举的方法。首先，我们从给定图的每个步骤的训练集中生成一个样本j，形式为（Uj，τ'j）。τ'j是关于我们是否应该继续迭代的真值，Uj ={c'1，...，c'k}是所有唯一概念组合的集合，2表示在执行算法更新状态之后（因此为c'）。给定一组概念索引3 I � P（{1..|C|}）和真值分配T：{1..|C|} →{0，1}，告诉我们哪些概念必须为真/假，我们检查以下条件是否满足：0即如果存在特殊的概念组合，我们应该继续迭代，如果不存在特殊的概念组合，我们应该停止迭代。我们采用暴力方法来寻找I和T，通过优先选择较小的I来打破平局。这种方法的复杂度是指数级的，但是如果概念瓶颈被精心设计，所需的概念数量和/或特殊组合中的概念数量将很小，使计算可行。0更重要的是，如果相同的枚举方法应用于原始节点输入数据，可能不存在I /T组合。例如，BFS任务的每个步骤的节点级输入并不能告诉我们哪些节点访问了邻居（决定终止的关键）。此外，如果我们有更多的输入特征，暴力方法可能无法计算 -组合随着节点特征和概念数量的增加呈指数级增长，而概念是减少这个数量的一种方法。04 实验设置0我们实验的代码可以在https://github.com/HekpoMaH/algorithmic-concepts-reasoning找到。0我们将我们的GNN应用于以下算法：广度优先搜索（BFS），并行着色（Jones和Plassmann，1993），图着色启发式算法和Kruskal的最小生成树（MST）算法（Kruskal，1956）。BFS被建模为一个二分类问题，我们预测一个节点是否被访问，而并行着色则被建模为一个分类任务，任务是确定可能的节点颜色的类别，再加上一个类别表示未着色的节点。Kruskal的算法被建模为两个并行训练的任务，一个是分类任务，选择下一个要考虑的MST边，另一个是帮助我们确定哪些节点属于同一集合的任务。由于原始的Kruskal算法执行|E|步，我们不学习MST任务的终止条件，并坚持固定的步数。我们在附录C中展示了我们如何为所有算法建模输入/输出。02 k 可能因样本而异 3 { a..b } 表示从 a 到 b 的整数集合 4在我们的情况下，这打破了所有的平局，但是，如果有必要，可以通过在真值分配上添加平局破坏，例如选择具有更多真/假值的分配0+v:mala2255获取更多论文60表1：算法及其对应的概念。我们提供了一些样本的真实解释。算法工作方式的视觉示例可见于图1。0算法概念示例的真实解释（未提供给模型）0BFS已访问（hBV）hV N（i）=�y（t）i=1已访问邻居（hV N）�i.¬hBV（i）∧hVN（i）=�τ（t）=10着色0iC（i）∧c 1 S（i）∧¬c 2S（i）=�y（t）i=2已着色（iC），具有优先级（hP）颜色X已见（cXS），X∈{1，..，5}（¬iC（i）∧hP（i）∧c 1 S（i）∧c 2 S（i）∧¬c 3 S（i））=�y（t）i=30Kruskal算法0（lEV（i）∧¬nISS（i）∧¬eIM（i））轻边已访问（lEV）=�y（t）i=1相同集合中的节点（nISS）MST中的边（eIM）（nISS（i）∧¬eIM（i））=�y（t）i=00重要的是，我们实验的所有算法都具有以下两个特性：（i）节点/边的输出是离散的，并且可以用概念来描述；（ii）继续执行可以归结为存在具有特定特征组合的节点。不属于这一类别的经典算法的示例是最短路径算法类：要解释这样的算法，我们需要使用算术（例如最小值、求和）来描述规则 -这是概念无法直接捕捉的。我们将这类算法的解释留待将来的工作。0为了生成我们的概念，我们考虑了算法使用的节点/邻域的属性，但我们没有向模型提供如何使用它们的任何细节。表1提供了我们选择的概念的更多细节和一些示例解释。我们在附录D中概述了如何使用这些概念来解释算法。0数据生成根据神经执行的先前研究（Veliˇckovi´c等，2020b），对于BFS，我们从许多类别生成图形-阶梯，网格，Erd˝os-Rényi（Erd˝os和Rényi，1960），Barabási-Albert（Albert和Barabási，2002），4个社区图，4个洞穴人图和树。对于着色任务，我们将颜色数量限制为5，然后生成所有节点都具有固定度数5的图形。这使得任务既具有挑战性（即有时需要5种颜色），又可行（我们可以生成可用5种颜色着色的图形）。这些任务的训练数据图形大小固定为20，我们使用20、50和100个节点的图形进行测试。对于Kruskal算法，我们重复使用了BFS任务的大多数图形类别，除了最后三个图形是树或不连通的。由于GPU内存限制，对大小为20的图形进行MST训练需要将批次大小减小4倍，并且训练非常耗时。因此，对于MST任务，我们将训练图形的大小减小为8。测试仍然在大小为20、50和100的图形上进行。对于所有任务，我们进行了10:1:1的训练:验证:测试分割。有关数据生成的更多详细信息，请参见附录E。0测试的架构我们决定选择具有最大聚合器的消息传递神经网络（Gilmer等，2017）作为我们处理器（GNN）架构的主要骨架，因为这种类型的GNN与算法执行良好对齐（Veliˇckovi´c等，2020b；Georgiev和Liò，2020；Veliˇckovi´c等，2020a）。然而，由于某些任务（并行着色）的非线性特性和添加的概念瓶颈，我们发现为一些编码器和解码器添加隐藏层而不仅仅将它们建模为仿射投影是有益的。0Kruskal算法由多个步骤组成-屏蔽已访问的边，从未屏蔽的边中找到最小边，并检查两个节点是否在同一集合中，如果不是则合并。该算法的架构遵循图1和图2的主要思想，为了实现它们，我们05在使用多个图类别时，比率在每个类别中保持不变0+v:mala2255获取更多论文70表2：5次运行的并行着色准确率0模型指标 | V  |  = 20 | V  |  = 50 | V  |  = 1000标准平均步骤准确率99.09±0.86% 98.74±0.44% 97.92±1.50% 最后步骤准确率99.25±0.56% 99.17±0.20% 99.13±0.29%终止准确率98.79±0.86% 96.79±1.53% 95.08±2.89%0瓶颈（+L1和修剪）0平均步骤准确率99.71±0.11% 99.23±0.21% 98.92±0.59% 最后步骤准确率99.69±0.13% 99.17±0.23%99.10±0.22% 终止准确率99.61±0.18% 99.02±0.43% 98.59±0.77% 公式平均步骤准确率99.71±0.12%99.24±0.21% 98.93±0.59% 公式最后步骤准确率99.69±0.13% 99.16±0.22% 99.08±0.19%公式终止准确率99.51±0.17% 99.02±0.43% 98.48±0.74% *概念平均步骤准确率99.85±0.05%99.60±0.10% 99.45±0.29% *概念最后步骤准确率99.72±0.07% 99.35±0.23% 99.42±0.09%0将Yan等人（2020）的架构用于前两个步骤，将Veliˇckovi´c等人（2020a）的架构用于第三个步骤。有关更多详细信息，请参见附录F。0实验细节我们使用教师强制（Williams和Zipser，1989）对模型进行训练，训练时使用固定的迭代次数（BFS为500次，并行着色为3000次，Kruskal为100次）。在测试BFS/并行着色时，我们选择验证损失之和最低的模型，而在测试Kruskal时选择最高最后步骤准确率的模型。训练时使用Adam优化器（Kingma和Ba，2015），初始学习率为0.001，批大小为32。我们优化概念、输出和终止（Kruskal除外）预测的损失之和-有关如何定义损失的更多细节，请参见附录G。我们评估在大小为50和100的图上进行强大泛化的能力。标准差是通过5次运行获得的。对于并行着色，我们在第2000次迭代时添加L1正则化和修剪，以获得更高质量的解释，因为在训练过程中可能没有观察到每个（概念、输出）对的组合。有关库、代码和计算细节，请参见附录L。所有超参数都是手动调整的。0我们使用多种指标，例如平均步骤准确率（每步输出的平均准确率），最后步骤准确率（最终算法输出的平均准确率）和终止准确率（预测终止的平均准确率）。类似地，我们定义了概念平均步骤准确率和概念最后步骤准确率，以及公式平均步骤准确率、公式最后步骤准确率和公式终止准确率。后三者是通过将提取的公式应用于预测的概念来预测输出/终止，而不是使用相应的神经网络。背后的动机是，如果我们实现了高概念准确率和高公式准确率，那么这些公式很可能准确地表示了潜在的算法（或数据）。0定性分析我们提供了几个定性实验：（i）我们为C→O任务拟合了一棵决策树（DT）（由于DT在固定大小的节点级特征上工作，因此无法进行C→T任务）。在每个步骤中，我们从所有训练数据节点的ground truth概念和目标类别中获取概念和目标。（ii）我们还绘制了每个概念的概念最后/平均步骤准确率与迭代次数的关系，并对网络发现最困难的概念进行进一步分析。 （iii）我们为每个算法提供了样本目标类别解释。05 结果与讨论0概念准确率从表2和表3以及附录H（带有星号的指标）中可以看出，我们能够以高准确率（99%及以上）学习概念（BFS和并行着色）。结果表明，GNN能够产生高级概念，捕捉节点或邻域信息，对于这些算法任务，学习的概念提取器具有很强的泛化能力-即使对于5倍大的图形，概念准确率也不会下降。0并行算法：BFS和着色对于BFS任务，基线模型和瓶颈模型都表现出与现有技术相当的最佳性能。因此，我们在BFS中呈现结果0+v:mala2255获取更多论文80表3：Kruskal算法在5次运行中的准确率0模型指标|V|=20 |V|=50 |V|=1000标准平均步骤准确率96.75±0.15% 95.41±0.09% 94.68±0.10% 最后步骤准确率93.70±0.33% 90.10±2.80% 86.69±4.28%0瓶颈0平均步骤准确率96.93±0.13% 95.86±0.37% 95.27±0.59% 最后步骤准确率94.00±0.24% 92.20±0.52%91.29±0.86% 公式平均步骤准确率96.79±0.37% 95.77±0.31% 95.25±0.54%公式最后步骤准确率93.70±0.71% 91.92±0.47% 91.15±0.60% *概念平均步骤准确率97.91±0.08%97.21±0.22% 96.80±0.35% *概念最后步骤准确率99.56±0.29% 99.49±0.49% 97.09±0.29%0表4：从学习模型中获得的每个算法的样本解释。cXS表示colorXSeen，nISS是nodesInSameSet，lEV是lighterEdgesVisited，eIM是edgeInMst。0算法 说明 解释0BFS n被访问 hasVisitedNeighbours(n)继续执行 �n.¬hasBeenVisited(n)∧hasVisitedNeighbours(n)0并行着色0n有颜色2（isColored(n)∧¬hasPriority(n)∧c1S(n)∧¬c2S(n))∨0（hasPriority（n）∧c1S（n）∧¬c2S（n）∧¬isColored（n））0n有颜色50（isColored（n）∧¬hasPriority（n）∧c1S（n）0∧c2S(n)∧c3S(n)∧c4S(n))∨0（hasPriority（n）∧c1S（n）∧c2S（n）0∧c3S(n)∧c4S(n)∧¬isColored(n))继续执行 �n.¬isColored(n)0Kruskal算法的e不在MST中（nISS（e）∧¬eIM（e））∨（¬lEV（e）∧¬eIM（e））e在MST中（lEV（e）∧nISS（e）∧eIM（e））∨（lEV（e）∧¬nISS（e）∧¬eIM（e））0附录H中的任务。并行着色任务的结果显示在表2中。除了达到高准确率外，我们的结果还表明：（i）瓶颈对最终模型准确率没有重大影响-原始指标6保持不变或更好，适用于两个算法；（ii）我们能够准确地学习概念；（iii）提取的规则准确-将它们应用于准确预测的概念以产生输出对我们模型的预测准确性没有显著负面影响-基于公式的准确性与原始指标相差不超过5-6%。0定性分析：决策树我们在附录I中展示了每个算法的拟合决策树（DTs）。在所有情况下，DT的逻辑遵循原始算法的逻辑。此外，所有决策树的叶节点都包含来自单个类别的样本，表明概念能够捕捉算法的复杂性。0定性分析：概念学习曲线我们在图3中展示了并行着色的每个概念学习曲线，图4中展示了Kruskal的概念学习曲线：（i）并行着色在几乎所有概念中都存在准确率下降的情况。如果我们仔细观察图3a，我们会注意到它们与hasPriority概念准确率的下降相一致。这种下降也解释了较低的最后步骤概念准确率-在早期改变着色顺序可能会产生完全不同的最终着色。为了证实这一观察结果，我们训练了一个始终提供正确hasPriority值的oracle模型。这个oracle模型几乎达到了完美的概念准确率-我们在附录J中提供了概念学习曲线的绘图；（ii）Kruskal的概念不稳定性仅在开始时存在，但它收敛到了一个稳定的解决方案。edgeInMst概念保持最低的最后步骤准确率的原因是模型的整体最后步骤准确率较低。06 即平均步准确性、最后一步准确性和终止准确性0+v:mala2255获取更多论文90（a）概念平均步准确性0（b）概念最后一步准确性0图3：并行着色算法每个时期的概念准确性。（每50个时期1个点）。cXS是colorXSeen。注意y轴刻度。可以观察到hasPriority概念是表现最差的概念之一。这导致节点按不同的顺序着色，因此与颜色相关的概念在最后一步的概念准确性较低。从5次运行中获得的标准差。0（a）概念平均步准确性0（b）概念最后一步准确性0图4：Kruskal算法在具有20个节点的图上每个时期的概念准确性。（每个时期1个点）。在初始不稳定性之后，概念始终准确。从5次运行中获得的标准差。0定性分析：解释我们在表4中列出了获得的解释示例，并在附录K中呈现了从算法中获得的所有解释。提取的规则表明，概念是提取算法规则准确表示的一种方式。例如，我们可以从并行着色的列出的规则中（重新）推断出，为了获得给定的颜色，该颜色不应该在邻域中出现，并且在该颜色之前出现的颜色已经被看到。0我们还观察到，随着概念数量的增加，如果我们需要更短和更一般的规则，我们需要更多的数据。缓解这个问题的一种方法是L1正则化和修剪-我们还在附录K中进行了消融研究，表明没有正则化规则仍然可用（给出良好的公式准确性），但不太一般。06 结论0我们通过概念瓶颈图神经网络展示了基于概念的图算法推理。通过调查的算法，我们证明了我们可以准确地学习节点级概念而不影响性能。此外，通过检查训练数据和模型权重，我们能够用基于定义的概念的公式解释每个节点级输出类。概念还允许我们对某些图级任务进行无监督的规则提取，例如决定何时终止。提取的规则是可解释的，并且应用它们不会严重影响准确性。0+v:mala2255获取更多论文100参考文献0Adadi, A.和Berrada,M.（2018）。窥探黑盒子：可解释人工智能（XAI）的调查。IEEE接入，6：52138-52160。0Albert, R.和Barabási, A.-L.（2002）。复杂网络的统计力学。现代物理评论，74(1)：47。0Baldassarre, F.和Azizpour,H.（2019）。用于图卷积网络的可解释性技术。arXiv预印本arXiv:1905.13686。0Barbiero, P.，Ciravegna, G.，Georgiev, D.和Giannini,F.（2021）。Lens：用于逻辑解释网络的Python库。arXiv预印本。0Battaglia, P. W., Pascanu, R., Lai, M., Rezende, D. J., and Kavukcuoglu, K. (2016).用于学习对象、关系和物理的交互网络。在Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon,I.,和Garnett,R.（编辑），神经信息处理系统29的进展：2016年神经信息处理系统年会，2016年12月5日至10日，西班牙巴塞罗那，第4502-4510页。0Cappart, Q.，Chételat, D.，Khalil, E.，Lodi, A.，Morris, C.和Veliˇckovi´c,P.（2021）。组合优化和基于图神经网络的推理。arXiv预印本arXiv:2102.09544。0Chen, Z., Bei, Y., and Rudin, C. (2020).用于可解释图像识别的概念漂白。自然机器智能，2(12)：772-782。0Ciravegna, G., Giannini, F., Melacci, S., Maggini, M., and Gori, M. (2020).一种基于约束的学习和解释方法。AAAI，第3658-3665页。0Deac, A., Velickovic, P., Milinkovic, O., Bacon, P., Tang, J., and Nikolic, M. (2020).XLVIN：执行的潜在值迭代网络。CoRR，abs/2010.13146。0Doshi-Velez, F. and Kim, B. (2017).走向可解释机器学习的严格科学。arXiv预印本arXiv:1702.08608。0Erd˝os, P. and Rényi, A. (1960).随机图的演化。《匈牙利科学院数学研究所出版物》，5(1)：17-60。0Galler, B. A. and Fisher, M. J. (1964). 一种改进的等价算法。《ACM通信》，7(5)：301-303。0Georgiev, D. and Liò, P. (2020). 神经二分匹配。图表示学习及更多（GRL+）研讨会。0Ghorbani, A., Wexler, J., Zou, J., and Kim, B. (2019).自动基于概念的解释方法。arXiv预印本arXiv:1902.03129。0Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. (2017).量子化学的神经消息传递。第34届国际机器学习大会论文集，ICML2017，2017年8月6-11日，澳大利亚悉尼，第1263-1272页。0Gori, M. (2017). 机器学习：一种基于约束的方法。Morgan Kaufmann。0Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J., and Battaglia, P. W.(2018). 人类和机器在物理建设中的关系归纳偏见。第40届认知科学学会年会论文集，CogSci2018，2018年7月25-28日，美国威斯康星州麦迪逊。0Jones, M. and Plassmann, P. (1993).并行图着色启发式算法。《SIAM科学计算学报》，14：654-669。0Joshi, C. K., Cappart, Q., Rousseau, L., Laurent, T., and Bresson, X. (2020).学习TSP需要重新思考泛化。CoRR，abs/2006.07054。0Kazhdan, D., Dimanov, B., Jamnik, M., and Liò, P. (2020a).Meme：通过模型提取生成RNN模型解释。arXiv预印本arXiv:2012.06954。0+v:mala2255获取更多论文11+v:mala2255获取更多论文0Kazhdan, D., Dimanov, B., Jamnik, M., Liò, P., and Weller, A. (2020b).现在你看到我（CME）：基于概念的模型提取。arXiv预印本arXiv:2010.13233。0Kazhdan, D., Dimanov, B., Terre, H. A., Jamnik, M., Liò, P., and Weller, A. (2021).解缠绕是否就是你所需要的？比较基于概念和解缠绕方法。arXiv预印本arXiv:2104.06917。0Kingma, D. P. and Ba, J. (2015). Adam：一种随机优化方法。第3届学习表示国际会议，ICLR2015，2015年5月7-9日，美国加利福尼亚州圣地亚哥，会议论文集。0Koh, P. W., Nguyen, T., Tang, Y. S., Mussmann, S., Pierson, E., Kim, B., and Liang, P. (2020).概念瓶颈模型。第37届国际机器学习大会论文集，ICML2020，2020年7月13-18日，虚拟会议，第119卷《机器学习研究论文集》，第5338-5348页。PMLR。0Kruskal,