 [1]}, [2]}, [3]} convert LP into binary graph classification. For a pair of nodes \(u,v\)  and the enclosing subgraph \(S_{uv}\) , SGNNs produce node representations \(\mathbf {Y}_{uv}\)  and one desires \(R(\mathbf {Y}_{uv})=1\)  if \((u,v) \in \mathcal {E}\)  and zero otherwise.
In order to resolve the automorphic node problem, node features are augmented with structural features [4]} that improve the ability of networks to count substructures [5]}. SGNNs were originally motivated by the strong performance of heuristics on benchmark datasets and attempted to learn generalized heuristics. When the graph is large it is not tractable to learn heuristics over the full graph, but global heuristics can be well approximated from subgraphs that are augmented with structural features with an approximation error that decays exponentially with the number of hops taken to construct the subgraph [2]}.
