There are two related reasons why MPNNs tend to be poor link predictors.
Firstly, due to the equivalence of message passing to the Weisfeiler-Leman (WL) graph isomorphism test [1]}, [2]}, standard MPNNs are provably incapable of counting triangles [3]} and consequently of counting Common Neighbors or computing one-hop or two-hop LP heuristics such as AA or RA.
Secondly, GNN-based LP approaches combine permutation-equivariant structural node representations (obtained by message passing on the graph) and a readout function that maps from two node representations to a link probability.
However, generating link representations as a function of equivariant node representations encounters the problem that all nodes \(u\)  in the same orbit induced by the graph automorphism group have equal representations. Therefore, the link probability
\(p(u,v)\)  is the same for all \(u\)  in the orbit independent of e.g. the graph distance \(d(u,v)\)  (Figure REF ).
 [4]}.
<FIGURE>