总结
GNN实现子图匹配。利用线图（边变点）让模型训练时将点和边的特征反复映射到对方领域参与训练。
定义
常规符号
Graph, Edge, Vertex,。X, Y表示点标签和边标签 ：\(\mathcal{G}, \mathcal{E}_{\mathcal{G}} \subseteq \mathcal{V}_{\mathcal G} \times \mathcal{V}_{\mathcal{G}}, \mathcal{X}_{\mathcal G}, \mathcal{Y}_{\mathcal G}, \mathcal{V}_{\mathcal G_{S}} \subseteq \mathcal{V}_{\mathcal G}\)
当子图\(\mathcal{G}_S\)完美匹配\(\mathcal{G}\)时：
\(\mathcal{E}_{\mathcal G_{S}} \subseteq \mathcal{E}_{\mathcal G} \cap (\mathcal{V}_{\mathcal G_S} \times \mathcal{V}_{\mathcal{G}_S}), \mathcal{X}_{\mathcal G_S}(v)=\mathcal{X_{\mathcal G}(v)} \forall v \in \mathcal{V}_{\mathcal G_S}, \mathcal{Y}_{\mathcal G_S}(e)=\mathcal{Y_{\mathcal G}(e)} \forall e \in \mathcal{E}_{\mathcal G_S}\)
就是匹配的时候，子图所有边都在大图里，且点和边的标签都能对上。
定义中还涉及线图的概念。线图（line graph）也称作 edge-to-vertex dual graph。简单来说，就是把边转成点。如果两边原本相邻，就把新转出的点相连。换句话说是线的图，也是种边-点对偶转化后的图。
图映射
还有两个图相关映射
- 子图匹配映射(Isomorphisms)：当\(\mathcal{G}_1\)的子图\(\mathcal{G_1}_{S}\)中所有边通过\(f:\mathcal{V}_{\mathcal{G_1}_S} \to \mathcal{V}_{\mathcal{G_2}}\)可以映射成\(\mathcal{V}_{\mathcal{G_2}}\)就认为\(\mathcal{V}_{\mathcal{G_2}}\)是\(\mathcal{V}_{\mathcal{G_1}}\)的子图
- 线图映射(Edge-to-vertex Transforms)：\(g:\mathcal{E}_{\mathcal{G}} \to \mathcal{V}_{\mathcal{H}}\)，并方便起见将\(\mathcal{G}\)映射而来的线图\(\mathcal{H}\)写作\(L(\mathcal{G})\)
同构和 Edge-to-vertex Transforms
- 如果两图同构，则他们的线图也肯定可以相互映射
- 惠特尼同构定理：四点以上连通图的同构图和它的线图的同构图之间存在一一对应关系
- 带有反向连通（变无向图了）有向异构图的同构图和线图的同构图和它的线图的同构之间存在一一对应关系
- 部分反向的连通有向异构图的同构图和它的线图的同构之间存在一一对应关系
Dual Message Passing Neural Networks
可以知道，原始图上找同构等价于在它线图上找同构。这节就是介绍设计的原始图、线图双向传递的模型。这个模型甚至传递扩展到了异构多图上。
- 对于有n个点m条边的有向图来说，\(A_{\mathcal{G}} + A^{\top}_{\mathcal{G}} = D^+_{\mathcal{G}} + D^-_{\mathcal{G}} - B_{\mathcal{G}}B^{\top}_{\mathcal{G}}\)。其中\(B_{\mathcal{G}} \in \mathbb{R}^{n \times m}\)。如果一个点是某条边的终点就为1，如果是起点就为-1，不然就是0。特别的，如果是无向图就会有\(B_{\mathcal{G}}B^{\top}_{\mathcal{G}}=2(D_{\mathcal{G}}-A_{\mathcal{G}})=2L_{\mathcal{G}}\)
- 对于有向图，\(A_{\mathcal{H}}+A^+_{\mathcal{H}}=\hat{B}^{\top}_{\mathcal{G}}\hat{B}_{\mathcal{G}}-2I_m\)。这里的\(\hat{B}_{\mathcal{G}} \in \mathbb{R}^{n \times m}\)中，如果一个点连了一个边就是1。如果是无向图，就会有\(A_{\mathcal H}= \frac{1}{2}\hat{B}^{\top}_{\mathcal G}\hat{B}_{\mathcal G}-I_m\)，同样的还有拉普拉斯矩阵：\(L_{\mathcal H} = D_{\mathcal H}-A_{\mathcal H} = D_{\mathcal H} + I_m - \frac{1}{2}\hat{B}^{\top}_{\mathcal G}\hat{B}_{\mathcal G}\)
最终的卷积网络:
\(h^{(k)} \gets (\theta^{(k)}_0-\theta^{(k)}_1)h^{(k-1)}+\frac{\theta^{(k)}_1}{\lambda_{\mathcal G\max}}B_{\mathcal G}z^{(k-1)}\)
\(z^{(k)} \gets (\gamma^{(k)}_0 - \gamma^{(k)}_1)z^{(k-1)}+\frac{2\gamma^{(k)}_1}{\lambda_{\mathcal H\max}}(D_{\mathcal H}+I_m)z^{(k-1)}-\frac{\gamma^{(k)}_1}{\lambda_{\mathcal H\max}}\hat{B}^{\top}_{\mathcal G}h^{(k-1)}\)
其中\(\theta, \gamma\)都是不断迭代更新的参数，点和边的权重值\(h^{(k)}\in \mathbb{R}^n, z^{(k)}\in \mathbb{R}^m\)是更新完的结果，\(\lambda\)是拉式矩阵最大的特征值，其实就是归到[-1,1]。
分析一下两个式子。其实就是靠B把点和边的权重来回映射，然后不断迭代。
对于异构图
\(H^{(k)}=H^{(k-1)}W^{(k)}_{\theta_0}-(\hat{B}_{\mathcal G} - B_{\mathcal G})Z^{(k-1)}W^{(k)}_{\theta^-_1}+(\hat{B}_{\mathcal G} + B_{\mathcal G})Z^{(k-1)}W^{(k)}_{\theta^+_1}\)
\(Z^{(k)}=Z^{(k-1)}W^{(k)}_{\gamma_0}+2(D_{\mathcal H}+I_m)Z^{(k-1)}(W^{(k)}_{\gamma^-_1}-W^{(k)}_{\gamma^+_1})-(\hat{B}_{\mathcal G} - B_{\mathcal G})^{\top}H^{(k-1)}W^{(k)}_{\gamma^-_1} + (\hat{B}_{\mathcal G} + B_{\mathcal G})^{\top}H^{(k-1)}W^{(k)}_{\gamma^+_1}\)
区别就是把之前的权重扩成了特征值来表征异构信息，再区分进出度（两B相减是出度，相加是入度）
loss
\(\mathcal{J}=\frac{1}{|\mathcal{D}|}\Sigma_{(\mathcal{P, G})\in \mathcal{D}}((\mathcal{c_{P,G}-p_{P,G}})^2+\Sigma_{v \in \mathcal{V_G}}(\mathcal{\omega_{P,v}}-P_{\mathcal{P,v}})^2)\)
c开头是下标第二个在第一个中出现的频率，p是预测结果。
实验
数据集
结果
模型还可以做点分类，要用交叉熵调整loss，不赘述。
标签：Convolutional,线图,Isomorphism,映射,top,2022,mathcal,hat,gamma From： https://www.cnblogs.com/yujianke/p/16719607.html