Graphlet-based Self-Supervised Model for Topological Network Alignment

Abstract Network alignment aims to find the optimal nodes correspondences across twonetworks leveraging topological and/or attributes information. Existing methods of network alignment belong to two main categories: optimization-based methods and embedding-based methods. Optimization-based methods involvesolving eigen-decomposition of a similarity matrix, solving quadratic assignmentproblem via sub-gradient optimization, or using heuristic-based iterative greedymatch. Whereas the embedding-based methods utilize a cost function to learnnode representation vectors in a latent space followed by efficient node matching.Optimization based methods are more accurate but they are computationally expensive. Embedding-based methods generally exhibit the opposite trend. Inthis paper, we propose SST-Align, which solves the network alignment task byusing a hybrid approach. In the first stage of the hybrid method, SST-Align uses graphlet-count based topology signature of the vertices in an iterative greedymatching method for obtaining an initial alignment. Then in the second stage, theinitial alignment is used as self-supervised labels for learning node embedding by using a siamese neural network on top of graph convolutional networks. Extensive experiments conducted on six real-life graph alignment datasets demonstratethat our proposed method outperforms the current state-of-the-art graph align-ment methods in terms of node mapping accuracy. We then perform experiments on noisy datasets, built through random edge insertion; experimental results show that SST-Align suffers performance degradation in its second stage due to weak initial alignment in the first stage caused by the presence of noise, yet it achieves better alignment results than most other methods. Finally, we extend SST-Align for heterogeneous graphs by introducing a node-type induced tripletloss, and show experimental results on two heterogeneous networks.