Several methods have been proposed to improve GNN expressivity for LP. Most simply, adding unique node IDs immediately makes all structural node representations distinguishable, but at the expense of generalization [1]} and training convergence [2]}. Substructure counts may act as permutation-equivariant approximately unique identifiers [3]}, but they require a precomputation step which may be computationally intractable in the worst case. More successfully, a family of structural features, sometimes referred to as labeling tricks, have recently been proposed that solve the automorphic node problem while still being equivariant and having good generalization [4]}, [5]}, [6]}. However, adding structural features amounts to computing structural node representations that are conditioned on an edge and so can no longer be efficiently computed in parallel.
For the purpose of tractability, state-of-the-art methods for LP restrict computation to subgraphs enclosing a link, transforming link prediction into binary subgraph classification [5]}, [8]}, [9]}. Subgraph GNNs (SGNN) are inspired by the strong performance of LP heuristics compared to more sophisticated techniques and are motivated as an attempt to learn data-driven LP heuristics.
