一种用于解决子图同构问题的子图特定因子
?
判断两个图是否同构可以从两个方面考虑
- 当两个图的节点的个数不等时:显然,这两个图是不可能同构。
- 当两个图的节点的个数相等时:此时,需根据邻接矩阵的特征值来进行区分。例:两个图的邻接矩阵分别为 A , A ′ ∈ R n × n \text{A},\text{A}'\in \mathbb{R}^{n\times n} A,A′∈Rn×n,如果两个图同构的话,那么 A ′ \text{A}' A′则可以通过矩阵 A \text{A} 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′?}是相同的两个集合。
对于给定的图 G = ( V , A ) \text{G}=(\text{V},\text{A}) G=(V,A), V \text{V} V是节点集合, A \text{A} A是邻接矩阵。我们可以得到用于判断子图是否同构的’子图特定因子(Subgraph-specific Factor)':
F ( G ) = Hash ( ∣ V ∣ , Hash ( Eig(A)) ) \mathcal{F}(G)=\texttt{Hash}(|\text{V}|,\texttt{Hash}(\text{Eig(A))}) F(G)=Hash(∣V∣,Hash(Eig(A)))
其中, ∣ V ∣ |\text{V}| ∣V∣表示节点的数量, Hash \texttt{Hash} Hash为可以将集合映射到实数空间的单设函数。至此,得到的子图特定因子 F ( G ) \mathcal{F}(G) 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]
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!