In this abstract we present our work in progress on embeddings for nodes in graphs representing their structural similarities. Intuitively, the more similar the structural representations of the respective neighbors of two nodes, the more structurally similar they are. An exemplary application is given by the task of identifying the role of each node in the graph, which might for instance correspond to the function of a protein within a protein-protein interaction network. Modeling and developing formal de nitions for concepts such as structural similarity, structural identity and roles remain challenging problems. Existing works either learn embeddings which are not able to appropriately model structural similarity or identify roles based on hand-crafted features rather than learning important features directly from the input graph. Recent work1 proposes a framework for learning a structural embedding vector for each node based on the degree sequences of it's neighbors within a k-hop distance. Two major drawbacks of this approach are the cubic time complexity and the fact that di erent k-hop neighborhoods are considered equally important. Note that in most cases the closer neighbors are considered more important. In contrast, we compute Personalized PageRank (PPR) for each node in the graph and use the resulting vectors as node representations. PPRs are very fast to compute and e ectively capture the probability distribution over the corresponding neighborhoods. The preliminary results in Table 1 prove our intuition: we simply sorted the raw PPR vector of each node and used them as representations. However, the experiments used in1 are of small practical relevance, as they use strongly arti cial datasets. Therefore, we also work on an appropriate evaluation framework.
ppr all removed 30% of edges struc2vec ppr corresp. all :048 :381 :208 :532 :069 :012 :008 :166 :225 corresp. :245 :102 :098 :209 :212 :041 :055 :159 :081 :098 :405 all :149 :136 :229