Graph Isomorphism

• G1그래프와 G2그래프가 구조가 같을때 두 그래프는 isomorphism하다고 말한다(노드들의 순서는 다를 수 있다)

• 두 그래프 인접행렬 A1,A2 노드 feature X1,X2 라고 정의하자. 두 그래프 isomorphic 하기 위해서는 밑에 식을 만족하는 행렬 P가 존재 해야한다.

• 행렬 P를 모든 경우에 대해서 찾는 작업을 한다면 다항시간안에 찾지 못한다 -> NP-Hard

Graph Isomorphism and Representational Capacity

• Isomorphism 테스트는 다양한 그래프의 표현학습들이 얼마나 강력한지 알아 볼수 있다.

• Zg1 Zg2 두 그래프 임베딩이