一种用于解决子图同构问题的子图特定因子

?

判断两个图是否同构可以从两个方面考虑

1. 当两个图的节点的个数不等时：显然，这两个图是不可能同构。
2. 当两个图的节点的个数相等时：此时，需根据邻接矩阵的特征值来进行区分。例：两个图的邻接矩阵分别为$\text{A},{\text{A}}^{\prime }\in {\mathbb{R}}^{n\times n}$，如果两个图同构的话，那么${\text{A}}^{\prime }$则可以通过矩阵$\text{A}$的行列变换得到，且行列交换不会影响矩阵的特征值，也就是说 Eig(A) = { a 1 , a 2 , . . . , a n } \text{Eig(A)}=\{a_1,a_2,...,a_n\} Eig(A)={a1?,a2?,...,an?}和 Eig ( A ′ ) = { a 1 ′ , a 2 ′ , . . . , a n ′ } \text{Eig}(\text{A}')=\{a'_1,a'_2,...,a'_n\} Eig(A′)={a1′?,a2′?,...,an′?}是相同的两个集合。

对于给定的图$\text{G}=(\text{V},\text{A})$，$\text{V}$是节点集合，$\text{A}$是邻接矩阵。我们可以得到用于判断子图是否同构的’子图特定因子（Subgraph-specific Factor）'：

$$\mathcal{F}(G)=\text{Hash}(|\text{V}|,\text{Hash}(\text{Eig(A))})$$

其中，$|\text{V}|$表示节点的数量，$\text{Hash}$为可以将集合映射到实数空间的单设函数。至此，得到的子图特定因子$\mathcal{F}(G)$可以唯一的表示一个图结构。

如果以上内容对于您的研究工作有帮助，我们将非常感激您可以引用我们的文章：[1].?

1. Chen K., Liu S., Zhu T., et al. Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization[C]. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’23), 237–249. [link]