Struc۲vec+k: Structural Graph Embedding with Layer Aggregation

Abstract

Graph representation learning aims to extract embedding vectors for graph nodes, such that similar nodes have close vectors in the embedding space. Existing methods often measure node similarity based on their common neighbors, which may overlook nodes with similar structures in different parts of the graph. We want to capture the structural similarity of nodes that are not adjacent in the graph. To this end, we propose struc2vec+k, a new method that extends the basic struc2vec method. The basic method considers two nodes to be structurally similar if their nodes in the first, second, third, and subsequent layers are similar. The proposed method also takes into account the connection between layers, and aggregates the information of two consecutive layers. For instance, for the second layer, the information of the first- and second-layer nodes are aggregated. This aggregation is based on the inter-layer connections. The aggregation can be done up to the k -th layer, which explains the name of the method. We show that the proposed method achieves good accuracy in numerical experiments.