利用图神经网络学习计算同构-技术附录

A 算法与复杂度分析

算法

Alg.1COUNT-GNN模型训练

我们在Alg.1中展示了训练CountGNN的算法。在第1行中，我们初始化所有参数以及目标L。在第3-13行中，我们累加给定训练元组的损失。具体地说，在第4-8行中，我们进行了递归的以边为中心的聚合。在第5-7行中，我们计算每条边的边中心表示。然后，在第9行和第10行中，我们通过分别聚合查询图和输入图的所有包含边中心表示来形成图表示。在行11中，采用计数器模块来预测Gi的同构于Qi的子图的数目.在第12行中，我们累计损失。在第14行中，我们形成了总体目标。最后，在第15行中，我们通过最小化目标L来优化模型。

复杂度分析

以边为中心的聚合增加了计算成本。这里，给定元组 $(Q,G,n)$ ，我们将Count-GNN分成两部分用于复杂度分析，即，边缘中心聚合和查询条件图调制。(1)以边为中心的聚合。设 $Q$ 和 $G$ 的平均度为 $d$ 。在每一个以边为中心的聚合层中，每一条边都将访问它的 $d$ 个相邻边进行聚合，因此复杂度为 $O(\bar{d})$ 。对于总共有 $K$ 层的查询图 $Q$ ，边表示学习的复杂度为 $O(\bar{d}^K \cdot \left | E_{Q} \right |)$ .类似地，输入图 $G$ 的边表示学习的复杂度为 $O(\bar{d}^K \cdot \left | E_{G} \right |)$ .(2)查询条件式图形调制。对于查询图 $Q$ ，图表示的计算涉及复杂度 $O(\left | E_Q \right |)$ .对于输入图 $Q$ ，它首先以复杂度 $O(\left | E_Q \right |)$ ,然后图表示的计算复杂度为 $O(\left | E_G \right |)$ .预测w.r.t.查询图和输入图的计算表示具有 $O(1)$ 的复杂度。总而言之，对元组 $(Q,G,n)$ 的预测具有 $O(\bar{d}^K \cdot \left | E_{Q} \right |+\bar{d}^K\cdot \left | E_{G} \right |+ \left | E_{Q} \right |+2 \left | E_{G} \right |)$

B 证明

我们在主论文的第4.5节中给出了理论结果的证明。

引理1（泛化）

Count-GNN可以简化为以节点为中心的GNN，即，Count-GNN可以看作是后者的推广。

证明

在不失一般性的情况下，我们在这里考虑有向图，其中无向图上的边可以被视为两个方向相反的有向边。我们还假设以节点为中心的GNN的以下通用形式，其中层 $l$ 中的节点嵌入由下式给出：

其中来自前一层中 $u$ 的相邻节点的消息被聚合到 $AGGR(\left \{ \mathbf{h}^{l-1}_{i} | <i,u> \in E \right \})$ ，其进一步与前一层中的目标节点 $u$ 的自信息 $\mathbf{h}^{l-1}_{u}$ 组合。 $\mathbf{W}^l$ 表示层 $l$ 中的权重矩阵，以进一步将来自 $l-1$ 层的聚合消息映射到 $l$ 层中的 $u$ 的新表示。请注意，聚合函数 $AGGR(\cdot)$ 的不同选择将具体化不同的以节点为中心的GNN。

给定Count-GNN的第一层中的有向边 $e = \left \langle u,v \right \rangle$ ，我们连接边及其两个端节点的特征以形成边 $e$ 的初始嵌入，即， $\mathbf{h}_{\left \langle u,v \right \rangle}^0 = \mathbf{x}_u \left \| \mathbf{x}_{\left \langle u,v \right \rangle} \right \|\mathbf{x}_v \in \mathbb{R}^{d_0}$ .为了将CountGNN简化为以节点为中心的GNN，对于每个边 $\left \langle u,v \right \rangle$ ，在第一层中，我们跳过边和结束节点 $v$ 的特征，并且仅采用 $u$ 的特征向量来形成初始嵌入，即， $\mathbf{h}_{\left \langle u,v \right \rangle}^0 = \mathbf{x}_u$ .随后，可以示出，在任何层 $l$ 中，每个边 $e = \left \langle u,v \right \rangle$ 的嵌入，即 $\mathbf{h}_{\left \langle u,v \right \rangle}^l$ ，等价于其起始节点 $u$ 的嵌入，即， $\mathbf{h}_{\left \langle u,v \right \rangle}^l =\mathbf{h}_{ u}^l$ 我们用归纳法证明等价性如下。

首先，我们已经有了基本情况 $\mathbf{h}_{\left \langle u,v \right \rangle}^0 =\mathbf{h}_{ u}^0$ ，因为在以节点为中心的GNN中，节点 $u$ 的初始嵌入 $\mathbf{h}_{ u}^0$ 仅仅是输入特征 $\mathbf{x}_u$ 。我们将其视为第0层。

其次，我们需要展示归纳步骤，即，假设在 $l-1$ 层中， $\mathbf{h}_{\left \langle u,v \right \rangle}^{l-1} =\mathbf{h}_{ u}^{l-1}$ ，我们可以导出 $l$ 层中的 $\mathbf{h}_{\left \langle u,v \right \rangle}^{l} =\mathbf{h}_{ u}^{l}$ 。为了获得 $l$ 层中的边表示 $\mathbf{h}_{\left \langle u,v \right \rangle}^{l}$ 我们首先按照正文中的等式（2）聚合 $\left \langle u,v \right \rangle$ 的相邻边的，其中给定了

$\mathbf{h}^{l-1}_{\left \langle \cdot,u \right \rangle} = AGGR\left ( \left \{ \mathbf{h}^{l-1}_{\left \langle i,u \right \rangle} |\left \langle i,u \right \rangle \in E \right \} \right ) =AGGR\left ( \left \{ \mathbf{h}^{l-1}_{i} |\left \langle i,u \right \rangle \in E \right \} \right )$

我们进一步应用Eq.(1)为了将 $l$ 层中的边表示生成为

$\mathbf{h}_{\left \langle u,v \right \rangle}^l=\sigma(\mathbf{W}^l\mathbf{h}^{l-1}_{\left \langle u,v \right \rangle}+\mathbf{U}^l\mathbf{h}^{l-1}_{\left \langle \cdot ,v \right \rangle}+\mathbf{b}^l) \\\:\!\!\!=\sigma(\mathbf{W}^l\mathbf{h}^{l-1}_{u}+\mathbf{U}^l AGGR(\left \{ \mathbf{h}^{l-1}_{i}|\left \langle i,u \right \rangle \in E \right \})+\mathbf{b}^l)$

通过约束 $\mathbf{W}^l =\mathbf{U}^l$ 并固定 $\mathbf{b}^l = \mathbf{0}$ ，我们有

$\mathbf{h}_{\left \langle u,v \right \rangle}^l=\sigma(\mathbf{W}^l\left ( \mathbf{h}^{l-1}_{u}+ AGGR(\left \{ \mathbf{h}^{l-1}_{i}|\left \langle i,u \right \rangle \in E \right \}) \right ))$

如果我们选择与等式（*）中相同的 $AGGR(\cdot)$ ，我们得到 $\mathbf{h}_{\left \langle u,v \right \rangle}^l=\mathbf{h}_{u}^l$ ，其中 $\mathbf{h}_{u}^l$ 由等式中的以节点为中心的GNN层给出。

由于基本情况和归纳步骤都成立，我们对任何 $l$ 层都有 $\mathbf{h}_{\left \langle u,v \right \rangle}^l=\mathbf{h}_{u}^l$ 。回想一下，如果对于每条边，我们删除边特征并且不拼接其结束节点的特征，则基本情况为真。因此，我们能够将Count-GNN简化为以节点为中心的GNN，这意味着我们可以将Count-GNN视为后者的推广。

定理1（表达性）

Count-GNN比以节点为中心的GNN更强大，这意味着（i）对于任何两个可以由以节点为中心的GNN区分的非同构图，它们也可以由Count-GNN区分;（ii）存在两个可以由Count-GNN区分但不能由以节点为中心的GNN区分的非同构图。

证明

假设以节点为中心的GNN的形式在方程（*）中。陈述（i）直接从引理1得出。因此，我们只需要证明（ii），这是一个存在性陈述，可以通过找到一个例子来证明。

图1：定理1的示例图

图1给出了一个例子，它由两个我们需要区分的非同构图组成。例如，图G1具有三个节点，即，a、B和c，并且每个节点具有其特征向量，例如，节点a具有特征向量[1，0，0]。GNN的表达能力决定了它区分不同图结构的能力。在下文中，我们证明了以节点为中心的GNN无法区分G1和G2，而以边缘为中心的Count-GNN可以区分这两个图。我们假设两个GNN都采用平均聚合器函数来聚合仅使用一个层的相邻节点（或边缘）的嵌入，并且都利用平均读出函数，即，通过对图中的节点（或边）嵌入求平均来生成图表示。为了便于表达，我们应用级联来融合它们，而不是将自信息和聚合的邻近信息相加。

表I：图G1的以节点为中心的嵌入

表II：图G2的以节点为中心的嵌入

在表I和表II中，我们分别说明了在G1和G2上使用以节点为中心的GNN计算节点嵌入和图嵌入。这里的||是连接的符号。例如，为了计算节点a在图G1上的输出嵌入，我们首先找到其邻居嵌入的均值，即，节点B具有[0，1，0]，节点c具有[0，0，1]，并获得[0.0，0.5，0.5]。然后将其与a的自嵌入[1，0，0]连接以获得a的输出嵌入，即，[0.0、0.5、0.5|| 1.0、0.0、0.0]。对两个图中的其他节点也是这样做的。最后，通过取每个图中的节点嵌入的平均值来获得图嵌入。如表I和表II所示，这两个非同构图具有由以节点为中心的GNN产生的相同的图嵌入，这意味着它们不能被以节点为中心的GNN区分。

表III：图G1的边中心嵌入

表IV：图G2的边中心嵌入

在表III和表IV中，我们进一步说明了在两个图上使用CountGNN计算边嵌入和图嵌入。给定一个有向边，我们首先通过将其起始节点和结束节点的特征与其自身的特征连接起来来初始化其嵌入。因为在我们的例子中，边没有输入特征，所以我们在连接中跳过它们（相当于我们也可以填充零）。例如，对于G2中的边 $\left \langle d,e \right \rangle$ ，其初始嵌入是 $\mathbf{h}^0_{\left \langle d,e \right \rangle}=\left [ 1.0,0.0,0.0,0.0,1.0,0.0, \right ]$ ，通过连接 $d$ 的特征向量 $\left [ 1,0,0 \right ]$ 和 $e$ 的特征向量 $\left [ 0,1,0 \right ]$ 。与以节点为中心的GNN类似，给定一个目标边，这里我们首先使用均值聚合器聚合其相邻边以获得相邻嵌入，然后将其与自嵌入进一步连接以获得输出嵌入。同样，我们以图G2上的边 $\left \langle d,e \right \rangle$ 为例。我们首先聚合其入射在节点 $d$ 上的前一条边的嵌入，即 $\left \langle b,d \right \rangle,\left \langle c,d \right \rangle,\left \langle f,d \right \rangle$ 从而获得相邻嵌入 $\left [ 0.00,0.33,0.67,1.00,0.00,0.00 \right ]$ 。因此，在进一步与其初始自嵌入级联之后， $\left \langle d,e \right \rangle$ 的输出边缘嵌入为 $\left [ 0.00,0.33,0.67,1.00,0.00,0.00 || 1.00,0.00,0.00,0.00,1.00,0.00 \right ]$ 。注意，对于没有任何先前边的边，例如，因此，我们用零填充其相邻嵌入， $\left [ 0.0,0.0,0.0,0.0,0.0,0.0\right ]$ 。最后，通过平均每个图中的所有边嵌入来获得图嵌入。从表III和表IV中我们可以观察到，由Count-GNN计算的G1和G2的图嵌入是不同的，这表明这两个图可以由Count-GNN区分开。因此，（ii）中的存在性陈述是有效的，证明可以得出结论。

C 数据集的细节

数据生成

表V：小和大数据生成的参数

我们求助于（Liu et al. 2020）工作中的数据生成器，通过使用相同的参数设置来生成四个数据集（对于MUTAG和OGB-PPA，只有查询图）。在表V中示出了针对SMALL和LARGE的数据生成中的详细设置。特别地，当生成一个查询图或输入图时，我们首先从表V中的对应集合中随机采样大小参数，以约束该图的生成。请注意，对于通常较大的参数大小，数据集LARGE将具有比数据集SMALL更大的单个图形大小，如表1所示

OGB-PPA的图形选择

原始数据集OGBPPA由158，100个图形组成。然而，OGB-PPA中的大部分图与生成的查询图没有同构，这种极端的数据集分布可能会损害基于GNN的模型的训练。因此，我们从原始OGB-PPA中抽取了6,000个图，并确保它们的平均子图同构计数大于10。

实验中二次设置的查询选择

令N和E分别表示节点和有向边的数量;对于数据集SMALL，我们分别随机选择大小为（N3，E3）、（N4，E4）和（N8，E8）的三个查询图;对于数据集LARGE，我们随机选择大小为（N4，E4）、（N8，E8）和（N8，E8）的三个查询图。（N16，E16）;对于数据集MUTAG，我们随机选择三个查询图，大小分别为（N3，E2），（N4，E3）和（N4，E3）。

D 基线的详细信息和设置

我们将Count-GNN与两个主要类别的最先进方法进行比较。

(1)传统的GNN，包括GCN（Kipf和Welling 2017），GAT（Veli Rickkovi 'c等人，2018），GraphSAGE（汉密尔顿，Ying和Leskovec 2017），DPGCNN（Monti等人，2018），GIN（Xu等人，2019）和DiffPool（Ying等人，2018）。它们通常利用以节点为中心的消息传递，然后使用读出函数来获得整个图表示。

GCN（Kipf and Welling 2017）：GCN通常采用基于均值池的以节点为中心的邻域聚合来接收来自相邻节点的消息，以进行节点表示学习。
GAT（Veli Pockovi'c et al. 2018）：GAT还依赖于节点中心的邻域聚合来进行节点表示学习，同时它可以为邻居分配不同的权重来重新加权它们的贡献。
GraphSAGE（汉密尔顿，Ying，and Leskovec 2017）：GraphSAGE与GCN有类似的邻域聚合机制，但它更关注来自节点本身的信息。
DPGCNN（Monti et al. 2018）：DPGCNN也是一个以节点为中心的GNN模型，它采用了与GAT类似的邻域聚合器，同时在计算邻居的权重时也考虑了边拓扑。
GIN（Xu et al. 2019）：GIN采用SUM聚合器来取代GCN中的均值池方法，以聚合来自相邻节点的所有消息，这被证明在捕获图结构方面更强大。
DiffPool（Ying et al. 2018）：DiffPool依赖于GNN框架来进一步构建其特定的聚合机制，通过分层聚类节点来形成全图表示。

(2)基于GNN的同构计数模型，包括（Liu et al. 2020）提出的四种变体，即RGCN-DN、RGCN-Sum、RGIN-DN、RGIN-Sum以及LRP（Zhengdao et al. 2020）和DMPNN-LRP（Liu and Song 2022）。它们是专门设计的GNN，用于子图同构计数，依赖于不同的GNN（例如，RGCN（Schlichtkrull等人，2018）、RGIN（Xu等人，2019）或局部关系池（Zhengdao等人，2020））用于节点表示学习，然后是适合同构匹配的专用读出，例如，DiamNet（Liu et al. 2020）。特别地，两个变体RGCN-DN和RGIN-DN利用DiamNet，而RGCN-Sum和RGIN-Sum利用简单的求和池。基于以前的工作（Liu et al. 2020; Zhengdao et al. 2020），DMPNN（Liu and Song 2022）也通过对偶图利用以边为中心的聚合。与DMPNN相比，DMPNN-LRP（Liu和Song 2022）在双消息传递之后添加了本地关系池，用于节点表示学习。

模型设置

为了获得最佳性能，我们根据文献中提出的设置来调整所有基线的超参数。特别地，对于包括GCN（Kipf和Welling2017）、GAT（Veli Pickovi'c等人，2018）、GraphSAGE（汉密尔顿、Ying和Leskovec，2017）、DPGCNN（Monti等人，2018）、GIN（Xu等人，2019）和DiffPool（Ying等人，2018）的传统GNN模型我们将总层数设置为3，隐藏维数设置为128，并且丢弃率设置为0.2。特别地，对于GAT，我们使用具有4个头的自注意机制;对于GraphSAGE，我们使用均值池作为聚合器;对于DPGCNN，我们在双卷积层上使用4个头，并且每个头的输出维度设置为8。对于DiffPool，我们将连续层中的节点数的比率设置为0.1。对于基于GNN的同构计数模型，我们遵循他们原始论文中的超参数设置，模型可以达到最佳性能。特别地，对于RGCN-SUM、RGCN-DM、RGIN-SUM、RGIN-DM和DMPNN-LRP，我们将层数设置为3，隐藏维度设置为128。

E Count-GNN 的设置

我们对Count-GNN的几个超参数进行了调整，以达到其最佳性能。特别地，我们采用了总共3层的Count-GNN。此外，在SMALL和LARGE数据集上，我们将隐维数设置为24，这是因为Count-GNN即使在低隐维数下也能获得较好的性能，但通常在高维情况下性能更好，也会花费更多的时间。为了在准确性和时间成本之间找到平衡，我们选择了这个适中的维度。在MUTAG上，我们将隐藏标注设定为12。在OGB-PPA上，我们将隐藏维度设置为24。此外，我们还设置了超参数λ，用于对方程中的FilLM因子进行加权。“(9)如0.0001。

F 进一步的实验和分析

除了主要论文中的实验之外，在本节中，我们还将进一步提供实验结果和模型评估分析。

参数灵敏度

我们在SMALL数据集上研究了两个重要超参数的敏感性。

图II：SMALL数据集上的参数敏感性

在图II（a）中，我们增加了边中心聚合的GNN层总数K，以检查其对性能的影响。随着K的增加，MAE和Q误差方面的性能通常会变得更好，只有K = 4时的Q误差例外。这表明了一种现象，即层的增加可以促进对远程结构信息的利用，这可能进一步帮助模型实现对图结构的更清晰的视图。

在图II（b）中，我们显示了参数λ的灵敏度，该参数对等式（九）中的FiLM因子的正则化器进行加权。我们观察到λ对性能相对敏感，并且λ = 0.01可能导致较差的性能。区间[1 e-5，1 e-3]可能是子图同构计数具有上级性能的较好区间。

与不同训练规模的比较

为了评估Count-GNN在不同训练规模下的性能趋势，我们在SMALL数据集上进行了一个实验，将训练三元组的数量从2，000增加到10，000，然后增加到20，000。还采用基线RGIN-SUM（Liu等人，2020）进行比较，它在表（2）的结果中证明是有竞争力的。图III（a）和III（B）分别显示了MAE和Q误差的结果。我们有以下观察结果。首先，在不同训练规模下，Count-GNN模型的性能均优于RGIN-SUM模型。唯一的例外是20 k的MAE和2k的Q误差。这表明，Count-GNN在子图同构计数方面的性能稳定地上级具有不同大小标记数据的基线。只有当标记的数据太少或太多时，其性能才可能被竞争基准所超越。其次，随着训练三元组数量的增加，MAE和Q-误差都有减小的趋势，表明更多的标记数据通常会提高模型性能。

可扩展性研究

我们研究了Count-GNN在OGBPPA数据集上的可扩展性，该数据集包含具有最大平均边数的图形。对于训练和测试，我们首先随机抽取10个查询图。接下来，我们构造五组输入图，每组包含10个大小相似的边数输入图。五组中每个图的平均边数在500到2500之间。我们在图IV中说明了每个组的训练和推理时间（以ms为单位）。请注意，这里报告的时间成本比表2和表3中的数字小得多，因为每组只有10个查询/输入图。训练时间和推理时间都随图中的边数目线性增加。该线性增长表明Count-GNN能够缩放到更大和更密集的图。

图四：可扩展性研究

G其他相关工作

图表示学习

图表示学习（Perozzi，Al-Rfou，and Skiena 2014; Grover and Leskovec 2016; Tang et al. 2015）通常利用图上的子结构采样来表示图结构的局部视图，因此可以进一步使用编码器将节点嵌入到低维表示中，其中图结构被保留。最近，图神经网络（GNNs）（Kipf和Welling 2017;汉密尔顿，Ying和Leskovec 2017; Veli Rickkovi 'c等人2018; Xu et al. 2019）作为一个强大的表示学习方法家族出现，它依赖于邻域聚合的关键算子来递归地传递消息以进行节点表示学习，因此可以同时保存结构和内容信息。

其他相关研究

图相似性搜索（Bai et al. 2019; Li et al. 2019）解决了一个相关但不同的问题，即评估两个图之间的相似性。最近的一些研究（Wang，Yan，and Yang 2019; Wang et al. 2021; Bai et al. 2021）也试图将传统模型和深度学习模型联合起来。子图相似性搜索（Yuan et al. 2012）是另一个类似但不同的任务，其目的是计算目标图是否近似包含查询图。他们中的许多人利用子图编辑距离（SED）来计算目标图和查询图之间的相似性（Bai et al. 2020; Zhang et al. 2021）。然而，由于问题的不同，这两种搜索方法都不能直接用于子图同构计数问题。目标检测（雷德蒙et al. 2016; Zhao et al. 2019）本质上类似于图上的子图同构，是计算机视觉领域的热门话题。然而，由于图和视觉数据之间的不同数据特性，对象检测方法不能应用于解决图上的子图同构计数。另外，GSN（Bouritsas et al. 2020）采用了一种拓扑感知的消息传递方案，其中子结构同构计数被用作结构特征，以增强GNN的表达能力。也就是说，它简单地应用现有的子图同构计数算法，并利用计数作为额外的输入，但不解决子图同构计数本身的问题。