Abstract
Nodes residing in different parts of a graph can have similar structuralroles within their local network topology. The identification of such rolesprovides key insight into the organization of networks and can be used for avariety of machine learning tasks. However, learning structural representationsof nodes is a challenging problem, and it has typically involved manuallyspecifying and tailoring topological features for each node. In this paper, wedevelop GraphWave, a method that represents each node's network neighborhoodvia a low-dimensional embedding by leveraging heat wavelet diffusion patterns.Instead of training on hand-selected features, GraphWave learns theseembeddings in an unsupervised way. We mathematically prove that nodes withsimilar network neighborhoods will have similar GraphWave embeddings eventhough these nodes may reside in very different parts of the network, and ourmethod scales linearly with the number of edges. Experiments in a variety ofdifferent settings demonstrate GraphWave's real-world potential for capturingstructural roles in networks, and our approach outperforms existingstate-of-the-art baselines in every experiment, by as much as 137%.