Low Mileage, High Fidelity: Evaluating Hypergraph Expansion Methods by Quantifying the Information Loss

摘要

In this paper, we first define information loss that occurs in the hypergraph expansion and then propose a novel framework, named MILEAGE, to evaluate hypergraph expansion methods by measuring their degree of information loss. MILEAGE employs the following four steps: (1) expanding a hypergraph; (2) performing the unsupervised representation learning on the expanded graph; (3) reconstructing a hypergraph based on vector representations obtained; and (4) measuring MILEAGE-score (i.e., mileage) by comparing the reconstructed and the original hypergraphs. To demonstrate the usefulness of MILEAGE, we conduct experiments via downstream tasks on three levels (i.e., node, hyperedge, and hypergraph): node classification, hyperedge prediction, and hypergraph classification on eight real-world hypergraph datasets. Through the extensive experiments, we observe that information loss through hypergraph expansion has a negative impact on downstream tasks and MILEAGE can effectively evaluate hypergraph expansion methods through the information loss and recommend a new method that resolves the problems of existing ones.