Structure features address limitations in GNN expressivity stemming from the inherent inability of message passing to distinguish automorphic nodes. In SGNNs, permutation-equivariant distances \(d(u,i)\)  and \(d(v,i) \, \forall i \in \mathcal {V}_{uv}\)  are used. The three most well known are Zero-One (ZO) encoding [1]}, Double Radius Node Labeling (DRNL) [2]} and Distance Encoding (DE) [2]}.
To solve the automorphic node problem, all that is required is to distinguish \(u\)  and \(v\)  from \(\mathcal {V}_{uv} \setminus \lbrace u,v\rbrace \) , which ZO achieves with binary node labels.
DRNL has \(z_{u}=z_{v}=1\)  and \(z_j=f(d(u,j),d(v,j))>1\) , where \(f: \mathbb {N}^2 \rightarrow \mathbb {N}\)  is a bijective map. Distance Encoding (DE) [4]} generalizes DRNL; each node is encoded with a tuple \(z_j = (d(u,j),d(v, j))\)  (See Figure REF ). Both of these schemes therefore include a unique label for triangles / common neighbors (See Appendix REF  for more details on labeling schemes). The relative performance of ZO, DRNL, DE and no structure features is shown in Figure REF . The use of structure features greatly improves performance and DRNL and DE slightly outperform ZO, with a more pronounced outperformance for the larger Pubmed dataset.
It is important to note that structure features are conditioned on edges and so can not be easily paralellized in the same way that node features usually are in GNNs and must be calculated for each link at both training and inference time. In particular DRNL requires two full traversals of each subgraph, which for regular graphs is \(\mathcal {O}(\mathit {deg}^k)\) , but for complex networks becomes \(O(|\mathcal {E}|)\) .
