A Mixed Strategy of Higher-Order Structure for Link Prediction Problem on Bipartite Graphs

Chao Li, Qiming Yang, Bowen Pang, Tiance Chen, Qian Cheng and Jiaomin Liu
Additional contact information
Chao Li: School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China
Qiming Yang: LMIB and School of Mathematical Sciences, Beihang University, Beijing 536002, China
Bowen Pang: LMIB and School of Mathematical Sciences, Beihang University, Beijing 536002, China
Tiance Chen: LMIB and School of Mathematical Sciences, Beihang University, Beijing 536002, China
Qian Cheng: LMIB and School of Mathematical Sciences, Beihang University, Beijing 536002, China
Jiaomin Liu: School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China

Mathematics, 2021, vol. 9, issue 24, 1-13

Abstract: Link prediction tasks have an extremely high research value in both academic and commercial fields. As a special case, link prediction in bipartite graphs has been receiving more and more attention thanks to the great success of the recommender system in the application field, such as product recommendation in E-commerce and movie recommendation in video sites. However, the difference between bipartite and unipartite graphs makes some methods designed for the latter inapplicable to the former, so it is quite important to study link prediction methods specifically for bipartite graphs. In this paper, with the aim of better measuring the similarity between two nodes in a bipartite graph and improving link prediction performance based on that, we propose a motif-based similarity index specifically for application on bipartite graphs. Our index can be regarded as a high-order evaluation of a graph’s local structure, which concerns mainly two kinds of typical 4-motifs related to bipartite graphs. After constructing our index, we integrate it into a commonly used method to measure the connection potential between every unconnected node pair. Some of the node pairs are originally unconnected, and the others are those we select deliberately to delete their edges for subsequent testing. We make experiments on six public network datasets and the results imply that the mixture of our index with the traditional method can obtain better prediction performance w.r.t. precision , recall and AUC in most cases. This is a strong proof of the effectiveness of our exploration on motifs structure. Also, our work points out an interesting direction for key graph structure exploration in the field of link prediction.

Keywords: link prediction; bipartite graph; motifs; recommender system (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/24/3195/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/24/3195/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:24:p:3195-:d:699994

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().