  Existing graph neural networks (GNNs) largely rely on node embeddings, which
represent a node as a vector by its identity, type, or content. However, graphs
with unlabeled nodes widely exist in real-world applications (e.g., anonymized
social networks). Previous GNNs either assign random labels to nodes (which
introduces artefacts to the GNN) or assign one embedding to all nodes (which
fails to distinguish one node from another). In this paper, we analyze the
limitation of existing approaches in two types of classification tasks, graph
classification and node classification. Inspired by our analysis, we propose
two techniques, Dynamic Labeling and Preferential Dynamic Labeling, that
satisfy desired properties statistically or asymptotically for each type of the
task. Experimental results show that we achieve high performance in various
graph-related tasks.
