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

Hypergraphs are typically used for solving downstream tasks in two steps: expanding a hypergraph into a conventional graph, known as the hypergraph expansion, and conducting machine learning methods on the expanded graph. Depending on how hypergraph expansion is performed, certain information of the original hypergraph may be lost, which negatively affects the accuracy of downstream tasks. If the amount of information loss can be measured, one can select the best hypergraph expansion procedure and target a better downstream performance. To this end, we propose a novel framework, named the 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 the 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. We observe that the average and minimum Pearson correlation coefficient between the mileage of expanded graphs and the performance of the downstream task are -0.871 and -0.904, respectively. The results validate 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. CCS CONCEPTS • Computing methodologies → Machine learning.