Evaluating the softmax denominator in the pairwise decoder requires summing over all nodes $v_k \in V$, resulting in $O(|V|)$ complexity per step. For large graphs with millions of nodes, this direct computation is computationally intractable, necessitating approximation techniques like negative sampling.