  While most network embedding techniques model the proximity between nodes in
a network, recently there has been significant interest in structural
embeddings that are based on node equivalences, a notion rooted in sociology:
equivalences or positions are collections of nodes that have similar
roles--i.e., similar functions, ties or interactions with nodes in other
positions--irrespective of their distance or reachability in the network.
Unlike the proximity-based methods that are rigorously evaluated in the
literature, the evaluation of structural embeddings is less mature. It relies
on small synthetic or real networks with labels that are not perfectly defined,
and its connection to sociological equivalences has hitherto been vague and
tenuous. With new node embedding methods being developed at a breakneck pace,
proper evaluation and systematic characterization of existing approaches will
be essential to progress. To fill in this gap, we set out to understand what
types of equivalences structural embeddings capture. We are the first to
contribute rigorous intrinsic and extrinsic evaluation methodology for
structural embeddings, along with carefully-designed, diverse datasets of
varying sizes. We observe a number of different evaluation variables that can
lead to different results (e.g., choice of similarity measure, classifier,
label definitions). We find that degree distributions within nodes' local
neighborhoods can lead to simple yet effective baselines in their own right and
guide the future development of structural embedding. We hope that our findings
can influence the design of further node embedding methods and also pave the
way for more comprehensive and fair evaluation of structural embedding methods.
