Heuristic Methods are Good Teachers to Distill MLPs for Graph Link Prediction Authors affiliated with Snap Inc. served in advisory roles only for this work.
Zongyue Qin, Shichang Zhang, Mingxuan Ju, Tong Zhao, Neil Shah, Yizhou Sun · 2025
Read Heuristic Methods are Good Teachers to Distill MLPs for Graph Link Prediction Authors affiliated with Snap Inc. served in advisory roles only for this work. by Zongyue Qin, Shichang Zhang, Mingxuan Ju, Tong Zhao, Neil Shah, Yizhou Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06193.txt.
Introduction
Zongyue Qin and co-authors present a 2025 arXiv paper on teaching simple neural nets to predict links in graphs. Graph neural networks predict well but cost heavily, so their knowledge is often distilled into plain multilayer perceptrons that skip the graph. The team asked which teacher makes the best student, comparing standard graph networks, link-specialized ones, and plain heuristics like shared neighbors.
Stronger teachers did not always win: students of the specialized model lagged, while cheap heuristic teachers nearly matched graph performance at far lower cost. Their ensemble method blends heuristic signals through a gating step. Across ten datasets it beat earlier distillation routes by about eight percent, training up to three times faster.
Catalog record
| CREATOR | Zongyue Qin, Shichang Zhang, Mingxuan Ju, Tong Zhao, Neil Shah, Yizhou Sun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-06193
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Heuristic Methods are Good Teachers to Distill MLPs for Graph Link Prediction Authors affiliated with Snap Inc. served in advisory roles only for this work. Zongyue Qin, Shichang Zhang, Mingxuan Ju, Tong Zhao, Neil Shah, Yizhou Sun Abstract Link prediction is a crucial graph-learning task with applications including citation prediction and product recommendation. Distilling Graph Neural Networks (GNNs) teachers into Multi-Layer Perceptrons (MLPs) students has emerged as an effective approach to achieve strong performance and reducing computational cost by removing graph dependency. However, existing distillation methods only use standard GNNs and overlook alternative teachers such as specialized model for link prediction (GNN4LP) and heuristic methods (e.g., common neighbors). This paper first explores the impact of different teachers in GNN-to-MLP distillation. Surprisingly, we find that stronger teachers do not always produce stronger students: MLPs distilled from GNN4LP can underperform those distilled from simpler GNNs, while weaker heuristic methods can teach MLPs to near-GNN performance with drastically reduced training costs. Building on these insights, we propose Ensemble Heuristic-Distilled MLPs (EHDM), which eliminates graph dependencies while effectively integrating complementary signals via a gating mechanism. Experiments on ten datasets show an average 7.93% improvement over previous GNN-to-MLP approaches with 1.95-3.32 × \times less training time, indicating EHDM is an efficient and effective link prediction method. 1]University of California Los Angeles Los Angeles, California, USA 2]Harvard University Boston, Massachusetts, USA 3]Snap Inc. Bellevue, Washington, USA 1 Introduction Link prediction is a pivotal task in graph learning, with widespread usage in web applications. It involves estimating the likelihood of a link between two nodes, enabling applications including citation prediction, friend recommendation, knowledge graph completion [ Schlichtkrull et al. 2018 , Nathani et al. 2019 , Vashishth et al. 2019 ] , and item recommendation [ Koren et al. 2009 , Ying et al. 2018 , He et al. 2020 ] . Graph neural networks (GNNs) [ Kipf and Welling 2016a , Hamilton et al. 2017 , Veličković et al. 2017 ] have been widely used for link prediction. This includes standard generic GNNs [ Kipf and Welling 2016b , Davidson et al. 2018 ] , as well as specifically designed GNNs for Link Prediction (GNN4LP) which are augmented with additional structural features [ Zhang and Chen 2018 , Zhang et al. 2021b , Zhu et al. 2021b , Yun et al. 2021 , Wang et al. 2024 , Ma et al. 2024 ] to capture extra link-specific information [ Zhang et al. 2021a ] . However, all of these GNN models suffer from heavy computations in inference time due to their dependency on graphs, which require repeatedly fetching and aggregating neighboring nodes for GNN message passing [ Zhang et al. 2021b ] . Researchers have proposed various methods to accelerate GNN inference. There are pruning [ Zhou et al. 2021 , Chen et al. 2021 ] and quantization [ Zhao et al. 2020 , Tailor et al. 2020 ] methods that accelerate GNN inference to some extent. But the speed-up is limited because they do not resolve the graph dependency issue caused by the message passing. An alternative line of work focuses on distilling knowledge of GNN teachers into Multi-Layer Perceptron (MLP) students [ Zhang et al. 2021b , Tian et al. 2022 , Wu et al. 2023a , Wu et al. 2023b , Wu et al. 2024 , Lu et al. 2024 , Wang et al. 2025 ] . By eliminating graph dependency and expensive neighborhood aggregation, MLPs offer up to 70-273 \times faster inference [ Guo et al. 2023 , Zhang et al. 2021b ] . Meanwhile, GNN-distilled MLPs have been shown to achieve competitive or superior performance compared to GNN teachers in many cases. Advances in GNN-to-MLP distillation focus primarily on node classification with only a few works extending the idea to link prediction. For example, LLP [ Guo et al. 2023 ] distills relational knowledge from standard GNNs to MLPs to achieve better effectiveness for link prediction. Yet, the link-level GNN-to-MLP distillation remains under-explored. Besides, existing GNN-to-MLP works rely majorly on standard GNNs as teachers. In reality, state-of-the-art link prediction models often go beyond standard GNNs. GNN4LP methods, or even classical heuristic methods (e.g., common neighbors) [ Kumar et al. 2020 , Newman 2001 , Murase et al. 2019 , Zhou et al. 2009 ] , were shown to outperform standard GNNs in many scenarios [ Li et al. 2024 ] . This creates an intriguing question: How does the choice of teacher model influence the resulting MLP student’s performance? Moreover, although GNN-to-MLP distillation accelerates inference, it still requires training a GNN teacher, which is itself computationally expensive in large-scale applications. Fine-tuning hyper-parameters for GNNs further inflates this cost. Hence, there is a growing incentive to identify alternative teachers that can distill useful link-level information at lower training cost. In this work, we first explore how different teachers, ranging from standard GNNs to GNN4LP methods and heuristic-based approaches, affect the performance of the distilled MLP student for link prediction. Adopting the LLP framework [ Guo et al. 2023 ] as the distillation pipeline, we have two surprising observations: 1. Good models might not be good teachers. Although GNN4LP models often outperform standard GNNs, the MLPs distilled from GNN4LP can actually underperform those distilled from simpler GNNs. 2. Heuristic methods are good teachers, even when they underperform. Classical heuristics can be effective teacher for MLPs to guide them achieve comparable performance to standard GNNs, even if the heuristic’s performance is worse than the MLP. For the first observation, we attribute it to the limited capacity of MLPs for capturing highly intricate structural patterns that GNN4LP teachers rely on. Taking this insight along with the second observation, we propose to distill MLPs from heuristic teachers, because generating these heuristic scores is often much faster than training a GNN, which will substantially shorten overall training time as well. While heuristic teachers can effectively guide MLPs, each heuristic captures only one type of structural proximity [ Mao et al. 2023 ] , leaving certain positive links unaccounted for. One might try merging heuristics into a single “stronger” teacher, but we find that mixing multiple heuristics can overload the student and hurt its performance. Instead, we take the heuristic-to-MLP distillation one step further to propose a simple yet effective Ensemble Heuristic-Distilled MLPs (EHDM) method that trains one MLP per heuristic, then learns a gater MLP to fuse their predictions at inference time. Our gating mechanism uses only node features, thereby preserving the MLP’s fast, neighbor-free inference. This allows us to harness multiple heuristics’ complementary signals and achieve higher accuracy without reintroducing graph dependencies. To summarize, this work makes the following contributions: • We show that even underperforming heuristic methods can be surprisingly good teachers to MLPs, enabling near-GNN predictive performance while reducing the cost of generating distillation guidance by an order of magnitude. • We propose an effective ensemble method EHDM to combine multiple heuristic-distilled MLPs via a gating mechanism which overcomes the limitations of single heuristics distillation. • Experiments on ten datasets (including three million-scale datasets) show an average of 7.93% performance gain over previous GNN-to-MLP methods [ Guo et al. 2023 ] , while accelerating overall training time by 1.95-3.32 \times . 2 Preliminaries and