Network Representation Learning Algorithm Based on Complete Subgraph Folding

• Published in: Mathematics (Basel) 2022-02, Vol.10 (4), p.581
• Main Authors: Chen, Dongming, Nie, Mingshuo, Yan, Jiarui, Wang, Dongqi, Gan, Qianqian
• Format: Article
• Language: English
• Subjects: Algorithms; Classification; Clustering; complete subgraph; Data mining; Folding; graph folding; Graph theory; Machine learning; Neighborhoods; network representation learning; Network topologies; Nodes; Representations
• ISSN: 2227-7390; 2227-7390
• DOI: 10.3390/math10040581

Network representation learning is a machine learning method that maps network topology and node information into low-dimensional vector space. Network representation learning enables the reduction of temporal and spatial complexity in the downstream data mining of networks, such as node classification and graph clustering. Existing algorithms commonly ignore the global topological information of the network in network representation learning, leading to information loss. The complete subgraph in the network commonly has a community structure, or it is the component module of the community structure. We believe that the structure of the community serves as the revealed structure in the topology of the network and preserves global information. In this paper, we propose SF-NRL, a network representation learning algorithm based on complete subgraph folding. The algorithm preserves the global topological information of the original network completely, by finding complete subgraphs in the original network and folding them into the super nodes. We employ the network representation learning algorithm to study the node embeddings on the folded network, and then merge the embeddings of the folded network with those of the original network to obtain the final node embeddings. Experiments performed on four real-world networks prove the effectiveness of the SF-NRL algorithm. The proposed algorithm outperforms the baselines in evaluation metrics on community detection and multi-label classification tasks. The proposed algorithm can effectively generalize the global information of the network and provides excellent classification performance.