This is a result of GNN's built-in permutation equivariance, which produces equal representation for any nodes whose enclosing subgraphs (corresponding to the receptive field of the GNN) are isomorphic.More precisely, WL-equivalent, which is a necessary but insufficient condition for isomorphism.
We refer to this phenomenon as the automorphic node problem and define automorphic nodes (denoted \(u \cong v\) ) to be those nodes that are indistinguishable by means of a given \(k\) -layer GNN.
On the other hand,
transductive node embedding methods such as TransE [1]} and DeepWalk [2]}, or matrix factorization [3]} do not suffer from this problem as the embeddings are not permutation equivariant.
