Exploiting Cross-Order Patterns and Link Prediction in Higher-Order Networks

Abstract

With the demand to model the relationships among three or more entities, higher-order networks are now more widespread across various domains. Relationships such as multiauthor collaborations, co-appearance of keywords, and copurchases can be naturally modeled as higher-order networks. However, due to (1) computational complexity and (2) insufficient higher-order data, exploring higher-order networks is often limited to order-3 motifs (or triangles). To address these problems, we explore and quantify similarites among various network orders. Our goal is to build relationships between different network orders and to solve higher-order problems using lowerorder information. Similarities between different orders are not comparable directly. Hence, we introduce a set of general crossorder similarities, and a measure: subedge rate. Our experiments on multiple real-world datasets demonstrate that most higherorder networks have considerable consistency as we move from higher-orders to lower-orders. Utilizing this discovery, we develop a new cross-order framework for higher-order link prediction method. These methods can predict higher-order links from lower-order edges, which cannot be attained by current higherorder methods that rely on data from a single order.

BibTeX Copy

@inproceedings{hao2022exploiting,
  title = {Exploiting Cross-Order Patterns and Link Prediction in Higher-Order Networks},
  author = {Hao Tian and Shengmin Jin and Reza Zafarani},
  year = {2022},
  keywords = {conference},
  booktitle = {Proceedings of the IEEE International Conference on Data Mining Workshops (ICDMW)},
  abstract = {With the demand to model the relationships among three or more entities, higher-order networks are now more widespread across various domains. Relationships such as multiauthor collaborations, co-appearance of keywords, and copurchases can be naturally modeled as higher-order networks. However, due to (1) computational complexity and (2) insufficient higher-order data, exploring higher-order networks is often limited to order-3 motifs (or triangles). To address these problems, we explore and quantify similarites among various network orders. Our goal is to build relationships between different network orders and to solve higher-order problems using lowerorder information. Similarities between different orders are not comparable directly. Hence, we introduce a set of general crossorder similarities, and a measure: subedge rate. Our experiments on multiple real-world datasets demonstrate that most higherorder networks have considerable consistency as we move from higher-orders to lower-orders. Utilizing this discovery, we develop a new cross-order framework for higher-order link prediction method. These methods can predict higher-order links from lower-order edges, which cannot be attained by current higherorder methods that rely on data from a single order.},
  pdf = {files/higherOrderICDM.pdf},
}