Weak Models Can be Good Teachers: A Case Study on Link Prediction with MLPs

Link prediction is a crucial graph-learning task. Distilling Graph Neural Network (GNN) teachers into Multi-Layer Perceptron (MLP) students has emerged as an effective approach to achieve strong performance and reducing computational cost by removing graph dependency in the inference stage, especially in applications such as citation prediction and product recommendation where node features are abundant. However, existing distillation methods only use standard GNNs. Do stronger models such as those specially designed for link prediction (e.g., GNN4LP) lead to better students? Are heuristic-based methods (e.g., common neighbors) bad teachers as they are weak models? This paper first explores the impact of different teachers in MLP distillation. Surprisingly, we find that stronger models 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. We provide both theoretical and empirical analysis to explain this phenomenon, revealing that a teacher is only as good as its teachable knowledge, the portion of its knowledge that can be transferred through the features accessible to the student. Building on these insights, we propose Ensemble Heuristic-Distilled MLPs (EHDM), which eliminates costly GNN training while effectively training complementary MLP predictors via different heuristic teachers. Our extensive experiments show EHDM reduces the total training time by 1.95-3.32$ $ while achieve an average 7.93\ Link prediction is crucial for many web applications (e.g., friend recommendation). Though Graph Neural Networks (GNNs) excel at this task, they impose high computational cost. A promising solution is distilling GNNs into Multi-Layer Perceptrons (MLPs) to remove graph dependency. But most such methods rely on standard GNNs as teachers and overlook other teacher options. In this paper, we first explore how different teacher models, spanning standard GNNs, specialized GNNs for Link Prediction (GNN4LP), and heuristic methods (e.g., common neighbors), affect the accuracy of the distilled MLP. Counterintuitively, we find that stronger teachers do not always produce stronger students: MLPs distilled from GNN4LP can underperform those distilled from simpler GNNs. Conversely, underperforming heuristic methods can guide MLPs to near-GNN performance while drastically reducing training costs. Building on these insights, we propose a simple yet effective Ensemble Heuristic-Distilled MLPs (EHDM). Our design avoids reintroducing graph dependencies while effectively harnessing complementary signals via a gating mechanism. Experiments on ten datasets show an average 7.93\ Graph neural networks (GNNs) have demonstrated strong performance in link prediction but are often computationally expensive, making them impractical for large-scale web applications. Recent work distills GNNs into multi-layer perceptrons (MLPs) to improve inference efficiency while maintaining comparable effectiveness. However, training GNNs as teachers remains computationally expensive, and a bottleneck in large-scale applications. Meanwhile, heuristic methods, although simple to compute, yield surprisingly good performance on some datasets. Besides, they capture proximity in graph structure, offers complementary information to node features. So in this work, we explore the potential of heuristic methods as lightweight teachers for MLP distillation. Surprisingly, experiments across ten real-world datasets, including three large (million-scale) datasets, show generating distillation guidance with heuristic methods is ten times faster than using GNNs. Moreover, heuristic-distilled MLPs achieve comparable or even superior performance to GNN-distilled MLPs, even on datasets where heuristic methods themselves perform poorly. To further enhance effectiveness, we introduce an ensemble method that aggregates the strengths of different heuristic-distilled MLPs, achieving performance comparable to GNNs while maintaining same inference complexity as MLPs. Our findings suggest that heuristic-based distillation is a promising direction for efficient and scalable link prediction in real-world applications.