Structural Node Embedding Via Role Identification

In reality,there are always inextricable connections between things,and these connections form different networks.Networks are ubiquitous in the real world,so studying the nature of networks will help researchers to gain a thorough understanding of network evolution.Thus we can better model the real world and improve the performance of various real-world tasks.Different attributes of things result in different functions in interactions,which leads to different roles.Nodes performing different functions in the same network or different networks always have different roles,while nodes performing similar functions in the same or different networks always share similar roles.These roles often can be gleaned from the structure of the network.Learning latent representations for the roles of nodes from network topologies is structural role embedding—the main problem this paper focusing on.Learning structural embeddings helps to understand the network and to transfer knowledge across networks.However,most existing structural embedding approaches suffer from high computation and space cost or rely on heuristic feature engineering,making them hard to apply to large networks or generalize across graphs.Here we propose RiWalk,a flexible paradigm for learning structural node representations.It decouples the structural embedding problem into a role identification procedure and a network embedding procedure.Through role identification,rooted kernels with structural dependencies kept are built.Nodes connect with the anchor nodes in similar patterns will be assigned similar identifiers,thus typical network embedding methods can be applied to learn structural embeddings.Through role identification on subgraphs,network embedding methods are better integrated than existing approaches.The decoupling makes the framework more simple and the integration of network embedding makes the framework more efficient.To demonstrate the effectiveness of RiWalk,we develop two different role identification methods named RiWalk-SP and RiWalk-WL,which are corresponding to two different graph kernels——the Shortest-path kernel and the Weisfeiler-Lehman kernel,respectively.For parallelizability and simplicity,we adopt random-walk based network embedding approaches to learn node representations.To avoid subgraph traversing to further reduce complexity,we also provide a faster variation of RiWalk-SP named RiWalk-RWSP,which gathers local structural information from random walks instead of subgraph traversing.In this paper,we also discuss the gaps between typical network embedding and structural embedding and give an example on expressway networks to demonstrate the differences.The result shows that they differ in their assumptions of the smoothness of class label distributions over the network.Experiments on within-network classification tasks show that our proposed algorithms achieve comparable performance with other baselines while being an order of magnitude more efficient.While RiWalk-SP shares similar intuition with our baseline method,by using our proposed paradigm,RiWalkSP learns more robust node representations.Besides,we also conduct across-network role classification tasks.The results show potential of structural embeddings in transfer learning.Besides,we also test the scalability of our framework on random or real-world networks of different sizes or densities.The results show that RiWalk is also scalable,making it capable of capturing structural roles in massive networks.