Mixture of Link Predictors on Graphs

Authors: ma  li
haoyu  han
juanhui  li
harry  shomer
hui  liu
xiaofeng  gao
jiliang  tang
li  ma
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:02:47

Abstract: Link prediction, which aims to forecast unseen connections in graphs, is a fundamental task in graph machine learning. Heuristic methods, leveraging a range of different pairwise measures such as common neighbors and shortest paths, often rival the performance of vanilla Graph Neural Networks (GNNs). Therefore, recent advancements in GNNs for link prediction (GNN4LP) have primarily focused on integrating one or a few types of pairwise information. 
In this work,  we reveal that different node pairs within the same dataset necessitate varied pairwise information for accurate prediction and models that only apply the same pairwise information uniformly could achieve suboptimal performance.
As a result, we propose a simple mixture of experts model Link-MoE for link prediction.  Link-MoE utilizes various GNNs as experts and  strategically selects the appropriate expert for each node pair based on various types of pairwise information. Experimental results across diverse real-world datasets demonstrate substantial performance improvement from Link-MoE. Notably,  Link-Mo achieves a relative improvement of 18.71% on the MRR metric for the Pubmed dataset and 9.59% on the Hits@100 metric for the ogbl-ppa dataset, compared to the best baselines. The code is available at https://github.com/ml-ml/Link-MoE/.

Main paper: 
 introduction: 
 Link prediction (LP) is a central challenge in graph analysis with many real-world applications, such as recommender systems [1, 2] , drug discovery [3] , and knowledge graph completion [4, 5] . Specifically, LP attempts to predict unseen edges in a graph. Unlike node-level tasks where Graph Neural Networks (GNNs) excel in modeling individual node representations [6] , LP demands the use of pairwise node representations to model the existence of a link where vanilla GNNs often fall short [7, 8] . Traditionally, various heuristic methods [9] were used to identify new links by encapsulating the pairwise relationship between two nodes. For instance, the Common Neighbors (CN) heuristic [10] counts the number of shared neighbors between a node pair, postulating that the number of common neighbors can indicate the likelihood of a connection. The Katz index [11] considers the total number of paths between two nodes, assigning a higher weight to those shorter in length. Node feature similarity-based methods [12] assumes that nodes with similar features tend to connect. Despite their simplicity, these heuristic-based methods are still considered as strong baselines in LP tasks.To leverage both the representational power of GNNs and the effectiveness of heuristics, recent GNN4LP works have sought to incorporate pairwise information into GNN frameworks, thereby enhancing their expressiveness for better link prediction. For example, NCN/NCNC [13] exploit the common neighbor information into GNNs. Neo-GNN [14] further incorporates multi-hop neighbor overlap information. SEAL [15] and NBFNet [16] leverage the full and partial labeling trick, respectively, to indict the target node pair, which has been proven to learn heuristic patterns like common neighbors and the Katz index. These GNN4LP methods mark significant progress in link prediction [17] .However, both traditional heuristic approaches and GNN4LP models typically adopt a one-size-fits-all solution, uniformly applying the same strategy to all target node pairs. There are several limitations with this one-size-fits-all solution: (1) Limited Use of Heuristics: These methods utilize only one or a few heuristics. Our preliminary studies in Section 3 have shown that different heuristics tend to complement each other, and employing multiple heuristics within the same dataset can lead to improved link prediction performance. Therefore, methods relying on a single type of heuristic might not be optimal. (2) Uniform Application of Heuristics: In Section 3, we also find that different node pairs within the same dataset often require distinct heuristics for predictions. Consequently, these methods that uniformly apply the same heuristic across all node pairs lack this adaptability, potentially leading to suboptimal performance. These findings underscore the pressing need for an approach that can adaptively apply a range of pairwise information specific to node pairs. Inspired by the superior performance of existing GNN4LP, we delved deeper into understanding different GNN4LP models. Our investigation reveals that these models are highly complementary and they excel under specific conditions, often correlated with particular heuristics. For example, the NCN model tends to perform well in scenarios with a high number of common neighbors. These observations motivate us to ask: can we design a strategy that can simultaneously enjoy the strengths of various GNN4LP models and correspondingly enhance link prediction?In response to this question, we introduce a simple yet remarkably effective mixture of experts model for link prediction -Link-MoE. This model operates by utilizing a range of existing link predictors as experts. A gating function is learned to assign different node pairs to different experts based on various types of pairwise information. Extensive experimental results showcase the surprisingly effective performance of Link-MoE. For instance, it surpasses the best baseline on Pubmed and ogbl-ppa dataset by 18.71% on the MRR and 9.59% on the Hits@100, respectively.2 Related Work 
link prediction: 
 Link prediction aims to predict unseen links in a graph. There are mainly three classes of methods for the link prediction task. An overview of each is given below.Heuristic Methods: Heuristic methods have been traditionally used for link prediction. They attempt to explicitly model the pairwise information between a node pair via hand-crafted measures. Several classes of heuristics exist for link prediction [17] including: local structural proximity, global structural proximity, and feature proximity. Local Structural Proximity (LSP): These method extract the information in the local neighborhood of a node pair. Common Neighbors (CN) [10] , Adamic-Adar (AA) [18] , and Resource Allocation [19] are popular measures that consider the number of shared 1-hop neighbors between the node pair. Global Structural Proximity (GSP): These methods attempt to model the interaction of a node pair by extracting the global graph information. The Shortest Path Distance assumes that a shorter distance between nodes results in a higher likelihood of them connecting. Both Katz Index [11] and Personalized Pagerank (PPR) [20] consider the paths of disparate length that connect both nodes, giving a higher weight to those shorter paths. Feature Proximity (FP): FP measures the similarity of the node features for both nodes in the pair, positing that nodes with similar features are more likely to form edges. Previous work [21, 22] has derived heuristics algorithms to measure the feature proximity.GNN-based Methods: Recent work has looked to move beyond pre-defined heuristic measures and model link prediction through the use of graph neural networks (GNNs). Earlier work [23, 24, 25] has sought to first use a GNN to learn node representations, and the representations for both nodes in a pair are then used to predict whether they link. However, multiple works [7, 8] have shown that node-based representations are unable to properly model link prediction. As such, newer methods, which we refer to as GNN4LP, attempt to learn pairwise representations to facilitate link prediction. Both SEAL [7] and NBFNet [16] condition the GNN aggregation on either both or one of the two nodes in the pair. While expressive, both methods tend to be prohibitively expensive as they require aggregating messages separately for each node pair. Recent methods [14, 13, 26, 27] have attempts to devise more efficient ways of learning pairwise representations by injecting pairwise information in the score function, bypassing the need of customizing the GNN aggregation to each node pair. These methods typically attempt to exploit different structural patterns on the local and global scales. Ensemble Methods: Ensemble-based methods for link prediction primarily fall into two categories: bagging and stacking. Bagging methods create multiple base learners trained on varied data subsets and integrate their predictions for final output [28, 29] . Stacking methods train multiple models on the entire graph and use a meta-model to integrate their predictions ( [30, 31, 32, 33] ). However, these methods directly combine the predictions of base learner without considering the specific patterns and heuristics of base learners.The use of Mixture of Experts (MoE) [34, 35] , which is based on the divide-and-conquer principle to divide problem to different experts, has been explored across various domains [36] . Recent researches mainly focus on the efficiency of leveraging the MoE in the NLP [37, 38] or Computer Vision [39] domains. Chen et al. [40] attribute the success of MoE to the cluster structure of the underlying problem. In the graph domain, GMoE [41] integrates the MoE model with GNNs, enabling nodes to learn from information across different hops. Wu et al. [42] leverage MoE to address the distribution shift issue in GNNs. To the best of our knowledge, Link-MoE represents the first instance of MoE specifically tailored for the link prediction task, showcasing exceptionally effective performance.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: This is discussed in Section K.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminary: 
 In this section, we begin by analyzing the relationship between various heuristics employed in link prediction, aiming to uncover the complex patterns that exist within the same dataset. Subsequently, we explore the relationship between the performance of different GNN4LP models and these heuristics. This exploration aims to identify the most suitable scenarios for each model, thereby enhancing our understanding of how different approaches can be optimally applied in varying link prediction contexts. Before that, we first introduce key notations and experimental settings.Notations and experimental settings. Let G = (V, E) be a graph with n nodes, where V is the node set and E is the edge set. N i denotes the neighborhood node set for node v i . The graph can be denoted as an adjacency matrix A ∈ R n×n , and each node v i may be associated with a d-dimensional feature x i and we use X = [x 1 , . . . , x n ] ⊤ ∈ R n×d to denote the node feature matrix. We conduct analysis on the Cora, Citeseer, Pubmed, ogbl-collab, and ogbl-ppa datasets. We use Hits@K as a metric to measure the ratio of positive samples ranked among the top K against a set of negative samples. The details on each dataset and the evaluation setting can be found in Appendix A. Due to the limited space, we only illustrate partial results in the following subsections. More results can be found in Appendix B.In this subsection, we focus on three vital types of pairwise factors used in link prediction identified by Mao et al. [17] : (a) local structure proximity, (b) global structure proximity, and (c) feature proximity. For each type, we adopt a single widely used heuristic as a representative metric including Common Neighbors (CN) [10] for local structure proximity, Shortest Path (SP) [43] for global structural proximity, and Feature Cosine Similarity (FCS) for feature proximity. We initially evaluate the performance of each heuristic individually and then assess their combinations by simply adding their normalized values. Specifically, we normalize each heuristic value (h) to the range of [0, 1] using h-hmax hmax-hmin , where h max and h min are the maximum and minimum heuristic values in the dataset. One exception is the calculation of SP, where a smaller SP indicates a higher likelihood that two nodes are connected. Therefore, we first calculate 1 SP , and then normalize it in the same way as other heuristics. For this evaluation, we employ Hits@3 as the metric for smaller datasets and Hits@20 for larger OGB datasets. The results for Citeseer and ogbl-collab are illustrated in Figure 1 , with diagonal values representing the individual performance of each heuristic. We can have two observations: (1) combining different heuristics generally enhances overall performance, indicating that reliance on a single heuristic may be inadequate for accurate link prediction; and(2) the performance of each heuristic varies across datasets. For instance, in the Citeseer dataset, FCS and CN exhibit comparable performance. However, in the ogbl-collab dataset, CN significantly outperforms FCS.We further investigate the overlap in correctly predicted sample pairs by each heuristic. We use the Jaccard Coefficient to calculate the overlapping ratio between each pair of heuristics. For the calculation of the Jaccard coefficient, we use the Hits@K metric for each edge. Specifically, we choose Hits@3 for small datasets and Hits@20 for the OGB datasets. We first rank the prediction scores of each method for both positive and negative edges. If the prediction score of a positive edge is in the Top-K, we label this positive edge as 'present' and add it to the correct prediction set. In this way, we can calculate the Jaccard coefficient by comparing the correct prediction sets for each pair of methods. The results for the Citeseer and ogbl-collab datasets are presented in Figure 2 . We observe that the overlapping ratio between certain heuristics is notably low. This implies that the sets of node pairs correctly predicted by different heuristics have a minimal intersection. Therefore, different node pairs require distinct heuristics for accurate prediction even on the same dataset. From the previous analysis, it is enticing to think that simply considering multiple heuristics should result in superior link prediction performance. We test this hypothesis by learning to classify links using multiple popular heuristic methods. For a single link, the individual heuristic scores are concatenated together and passed to an MLP, where the output is then used to classify the link. The full set of heuristic considered can be found in Section 5.1. The results on Citeseer and ogbl-collab can be found in Table 1 .We report the MRR for Citeseer and Hits@50 for ogbl-collab. We find that ensembling multiple heuristics can modestly improve the performance. However, it still noticeably lags behind GNN4LP methods in performance. Based on this observation, we are motivated to investigate whether different GNN4LP models can be used to model a wider variety of links. In this subsection, we move beyond analyzing the performance of only heuristic measures and further consider the capabilities of different GNN4LP methods. To better understand the abilities of different GNN4LP models, we first evaluate the overlapping ratio between different models using the Jaccard Coefficient. We also include the MLP and different heuristics in the analysis. The overlapping ratio of different methods on ogbl-collab dataset is shown in Figure 3 . These results reveal that the overlapping ratios among different GNN4LP models are rel-atively low, suggesting that each model is capable of predicting a unique set of links. Furthermore, different GNN4LP models have varying degrees of overlap with different heuristics. These observations lead us to an intriguing question: Are the unique sets of links correctly predicted by different GNN4LP models related to specific heuristics?To answer this question, we first categorize node pairs into 5 groups based on each heuristic and evaluate the performance of different GNN4LP models within these groups. Additionally, we also include the MLP and GCN in our analysis. The performance of these models across different Common Neighbors (CN) groups for Cora and ogbl-collab is depicted in Figure 4 . The x-axis represents different groups, along with the proportion of node pairs in each group. From the results, we can find that no single model consistently outperforms others across all groups on either dataset. Interestingly, when there are no common neighbors, MLP and GCN tend to excel in both the Cora and ogbl-collab datasets. In situations with a few common neighbors, SEAL shows better performance in the Cora dataset, while BUDDY tends to lead in the ogbl-collab dataset. With an increase in the number of common neighbors, methods that encode CN information, such as NCNC, generally exhibit strong performance. A similar phenomena can be found on other datasets and heuristics in Appendix B. In conclusion, our analysis underscores that accurate link prediction necessitates the use of multiple heuristics. Different node pairs require distinct heuristics for optimal prediction. Furthermore, the overlapping ratio of different GNN4LP models is relatively low. The performance of powerful GNN4LP models is closely tied to the specific heuristics they encode. And there is no single model that can uniformly achieve the best performance across all scenarios. These findings pave us a way to adaptively select the most suitable model for each node pair to achieve better overall performance in link prediction task.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
method: 
 The investigations conducted in Section 3 reveal that various heuristics complement each other for the task on link prediction. This implies that different node pairs may need different heuristics to properly predict the existence of a link. Therefore, one approach to potentially achieve better performance in link prediction is to integrate all these heuristics into a single, unified model. However, as shown in Table 1 , this strategy fails to outperform existing GNN4LP methods. This suggests that these GNN4LP models are already quite effective. Our findings further suggest that different GNN4LP models demonstrate unique strengths in different scenarios, which are related to specific heuristics. Therefore, leveraging these diverse heuristics as a guidance could help identify the most suitable GNN4LP models for specific node pairs. Based on the above intuitions, we aim to design a framework that can harness the unique strengths of each model to enhance the performance of link prediction.To leverage the strengths of various existing models, we introduce a novel mixture-of-experts (MoE) method tailored for link prediction, which we term -Link-MoE. An overview of Link-MoE is depicted in Figure 5 (a). There are two major components: the gating model and the multiple expert models. The gating function can be implemented using any neural network and each expert can be any method used for link prediction. When predicting whether a node pair (i, j) are linked, the gating function utilizes their heuristic information to produce normalized weights for each expert. These weights dictate the level of contribution each expert model has towards the final prediction. Each expert model processes the graph and node pair information, estimating the likelihood of a connection between the two nodes. The individual expert predictions are then aggregated according to the weights assigned by the gating function. The final prediction is made using the sum of the weighted scores, effectively leveraging the strengths of multiple experts to determine the probability of a link. Formally, the prediction of Link-MoE can be expressed as:EQUATIONwhere m denotes the number of expert models incorporated, pairwise node features x ij and structural heuristics s ij serves as the input to the gating function, G(•) represents the gating model function, E o refers to the o-th expert model, and σ is a sigmoid activation function. This configuration makes the Link-MoE remarkably flexible and easily adaptable, allowing for the seamless integration of different expert models as required. We will detail our implementation in the following subsections.As highlighted in our preliminary studies (Section 3), it's evident that different GNN4LP models excel in varying contexts and that their strengths can be indicated by different heuristics. Therefore, we incorporate a broad spectrum of heuristics as inputs to the gating model to leverage these strengths. Specifically we consider CN [10] , AA [18] and RA [19] to model the local structural proximity and Shortest Path, Katz index [11] , and PPR [44] for the global structural proximity. For the feature proximity, to ensure the score is invariant to the ordering of the node pair, we utilize the element-wise product for deriving the feature heuristic of node pair (i, j). This is defined asx ij = x i ⊙ x j . We also use s ij = [s 1 ij , s 2 ij , ..., s k ij ]to represent all the k structural heuristics, and the dimension of each structural heuristics is typically very small. However, the node pair feature heuristic is equal to the input node feature dimension and can span hundreds or even thousands of dimensions. This significant disparity in dimensionality could hinder the model's ability to effectively learn from the structural heuristics. To address this challenge, we design a two-branch gating model, as illustrated in Figure 5(b) . Each branch is a simple MLP. One branch is dedicated to encoding the structural heuristics, while the other focuses on processing the node pair features. After that, these two branches are merged via concatenation. Finally, an MLP with the softmax function is applied to this combined output to generate the final weight predictions. This design ensures a balanced consideration of both structural and feature-based heuristics. Formally, the gating function is defined as follows:EQUATIONwhere f is a MLP and || denotes the concatenation operator.Given the experts chosen in Section 5.1, there are several training strategies used by MoE models to combine them. This includes end-to-end training [42] and the EM algorithm [45] . Given the multiple options, we are then tasked with the question: how do we optimize Link-MoE?In this work, we employ a two-step training strategy, as detailed in Algorithm 1 in Appendix E. Initially, we train each expert individually using their respective optimal hyperparameters and perform inference on the dataset to obtain the prediction scores for each link. Subsequently, we focus on the training of the gating model. Specifically, we adopt the cross entropy to train the gating function:EQUATIONwhere y ij = 1 when a link exists between node v i and v j in the graph, and y ij = 0 otherwise. P and N denote the set of positive/negative links in the graph, respectively.There are several benefits to our two-step training strategy. (1) Efficiency: This approach eliminates the need to load every expert into memory simultaneously, as each expert is trained and infers independently; For time efficiency, tuning the gating model to identify the best hyperparameters is more efficient since it involves training only MLPs.(2) Effectiveness: The two-step training strategy helps to avoid the 'collapse problem' often encountered in MoE models [37] . This issue arises when only a single expert is consistently selected, leading to the under-utilization and inadequate learning of the other experts. By training the experts individually first, we mitigate this risk, ensuring a more balanced and effective utilization of all experts. We compare two-step and end-to-end training strategies in Appendix G.(3) Flexibility: When introducing new experts into the Link-MoE, it's only necessary to train these new experts and the gating model. All previously trained experts can be seamlessly integrated without the need for retraining.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: See https://github.com/ml-ml/Link-MoE/.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
experiments: 
 In this section, we conduct comprehensive experiments to validate the effectiveness of the proposed Link-MoE. Specifically, we aim to address the following research questions: RQ1: How does Link-MoE perform when compared to other baseline models? RQ2: Are the heuristics effective in aiding the selection of experts? RQ3: Can Link-MoE adaptively select suitable experts for different node pairs?Datasets. We evaluate our proposed method on eight datasets including homophilous graphs: Cora, Citeseer, Pubmed [46] , ogbl-ppa, ogbl-collab, and ogbl-citation2 [47] and heterophilic graphs: Chameleon and Squirrel [48] . Please see Appendix A for more details on each dataset.Baselines. We consider a diverse set of baselines include heuristics, embedding methods, GNNs, and GNN4LP methods. This includes: CNs [10] , AA [18] , RA [19] , Shortest Path [43] , Katz [11] , Node2Vec [49] , Matrix Factorization (MF) [50] , MLP, GCN [23] , GAT [51] , SAGE [24] , GAE [25] , SEAL [15] , BUDDY [26] , Neo-GNN [14] , NCN and NCNC [13] , NBFNet [16] , PEG [52] , LP-Former [27] .Additionally, to comprehensively evaluate the proposed Link-MoE, which integrates multiple link predictors, we design two ensemble baseline methods for comparison. The first method, Mean-Ensemble, combines all expert models with uniform weight, ensuring each expert contributes equally to the final prediction. The second method, Global-Ensemble, learns a global weight for each expert that is applied when predicting all node pairs. In this approach, each expert contributes to the final prediction based on the learned global weight for all node pairs, allowing for a differentiated influence of each expert based on their performance. See Appendix A.2 for more details on these two methods. Additionally, we compare our method with two other ensemble methods [30, 31] , with the results provided in Appendix H.Link-MoE Settings. In this study, we incorporate both node features and a variety of different heuristics as input features for the gating model. These heuristics include node degree, CN, AA, RA, Shortest Path, Katz, and Personalized PageRank (PPR) [20] . Furthermore, our approach uses a wide range of experts, including NCN, NCNC, Neo-GNN, BUDDY, MLP, Node2Vec, SEAL, GCN, NBFNet, and PEG. NBFNet and PEG are only used for smaller datasets, as they often run into out-of-memory issues on the larger OGB datasets. For the two baselines, Mean-Ensemble and Global-Ensemble, we use the same experts as with Link-MoE. More setting details are in Appendix A.2.For evaluation, we report several ranking metrics including the Hits@K and Mean Reciprocal Rank (MRR). In the main paper, we report the MRR for Cora, Citeseer, and Pubmed and for OGB we use the evaluation metric used in the original study [47] . Results for other metrics are shown in Appendix C. We present the main results of link prediction for the small datasets and OGB datasets in Table 2 .Reported results are mean and standard deviation over 10 seeds. We use "Improv." to denote the relative improvement of Link-MoE over the second best model. From the table, we can have the following observations:• Link-MoE consistently outperforms all the baselines by a significant margin. For example, it achieves a relative improvement of 18.71% on the MRR metric for the Pubmed dataset and 9.59% on the Hit@100 metric for the ogbl-ppa dataset, compared to the best-performing baseline methods.• While both the Mean-Ensemble and Global-Ensemble methods also incorporate all the experts used in Link-MoE, their performance is generally subpar in most cases. Although the Global-Ensemble, which learns different weights for each expert, usually outperforms the Mean-Ensemble, it still falls short of the performance of single baseline methods in some scenarios. We attribute this to their inability to adaptively apply different experts to specific node pairs, which demonstrates the effectiveness of the gating model in Link-MoE. • We further compare against LPFormer [27] , a recent method that attempts to adaptively customize pairwise information to each node pair, resulting in strong performance. We find that our model is able to considerably outperform LPFormer on all datasets. From this we conclude that Link-MoE is better than LPFormer at customizing the pairwise information to each node pair.Additionally, instead of using all experts, we conducted experiments with only a few experts (i.e., 3 or 4 experts). Furthermore, we also explored a sparse gating strategy [37] , which selectively activates only the Top-K experts for each sample's prediction. The results, presented in Appendix D, demonstrate that these two variants can achieve comparable performance with using all the experts.We further evaluate the proposed Link-MoE on heterophilic graphs, with results in Appendix F indicating that Link-MoE achieves strong performance. Additionally, we assess Link-MoE in the more challenging HeaRT setting [53] , with results in Appendix J further validating its effectiveness. The addition of the gating model enables Link-MoE to significantly surpass both the Mean-Ensemble and Global-Ensemble methods. This improvement underscores the pivotal role of the gating model, which intelligently leverages heuristic information to enhance the overall performance. In this subsection, we delve into the impact of various heuristics utilized by the gating model in Link-MoE. Specifically, there are three types of heuristics: local structure proximity (e.g., CN, AA, RA), global structure proximity (e.g., Shortest Path, Katz), and feature proximity. We design experiments to isolate the effect of specific types of heuristics by including them either individually or in groups.For instance, utilizing only feature proximity is referred to as 'OnlyFeat', combining local and global structure proximities is labeled 'OnlyStruct', employing only local structure proximity is denoted 'OnlyLocalStruct', and using only global structure proximity is marked 'OnlyGlobalStruct'. Additionally, the 'All' is used to indicate leveraging all heuristics. The results on Pubmed and ogbl-ppa datasets are shown in Figure 6 . From the experimental results, several observations can be made: (1) Using only the feature proximity (OnlyFeat) or only the global structural proximity (OnlyGlobalStruct) typically yields lower performance. (2) Combining the local and global structure proximity (OnlyStruct) tends to outperform using either one alone.(3) The effectiveness of feature proximity varies between datasets. On Pubmed, it is beneficial to include it but not on ogbl-ppa. This discrepancy could stem from the relative importance of feature information in each dataset, as suggested by the very poor performance of MLP on ogbl-ppa, whose Hits@100 is only around 0.45. Moreover, we explore different inputs for the gating model, the results are presented in Appendix I, which highlights the rationality of the design of our gating model.In the previous sections, we incorporated all the selected experts in Link-MoE. This subsection aims to explore the impact of each expert's removal on the framework's performance. We conducted experiments on the ogbl-collab and ogbl-ppa datasets, utilizing Hits@50 as the metric for evaluation.The results are presented in Figure 7 , where the x-axis indicates the experts removed for each trial. We observe that the removal of individual experts does not significantly impact the performance of Link-MoE on both the ogbl-collab and ogbl-ppa datasets. This phenomenon suggest that Link-MoE possesses an adaptive capability to compensate for the absence of certain models by effectively utilizing other available experts.In this subsection, we explore the mechanism by which the gating model allocates weights to experts based on the heuristics of different node pairs. Similar to Section 3, we categorize the test node pairs into distinct groups according to different heuristics. Subsequently, for each group, we compute the average weights assigned to each expert by the gating model. The results based on Common Neighbors for ogbl-collab and ogbl-ppa are shown in Figure 8 . We can have some interesting findings:(1): For the ogbl-collab dataset, when the node pair doesn't have common neighbor, the gating model usually assigns a large weight to the MLP model, which aligns the analysis in Section 3 that the MLP can perform well when there is no CN on ogbl-collab. However, For the ogbl-ppa dataset, when there is no common neighbor, the gating model would assign a high weight to NCNC. This preference arises because node features hold less significance in the ogbl-ppa dataset and NCNC can leverage multi-hop common neighbor information.(2): As the number of common neighbors increases, the gating model increasingly allocates more weight to the NCN. This shift reflects the NCN's capability to efficiently capture and utilize common neighbor information.(3): Not every expert model contributes much to the prediction. This selective engagement is attributed to the overlapping capabilities of certain models. For instance, both Neo-GNN and NCNC are capable of exploiting multi-hop information. In such cases, the gating model opts for one over the other to avoid redundancy and optimize prediction efficacy. This phenomenon is also consistent with the results in Section 5.4 that removing one expert doesn't affect the overall performance. The analysis of gating weights on heterophilic datasets can be found in Appendix F.While Link-MoE can successfully leverage heuristics to select appropriate experts for different node pairs, we recognize substantial room for further enhancements. For instance, the observed overlapping ratio between Neo-GNN and NCNC on the ogbl-collab dataset is not very high, as shown in Figure 3 , even if they exploit similar heuristics. But in Link-MoE, Neo-GNN has very low weights on the ogbl-collab dataset. This observation underscores the vast potential for advancing MoE applications in link prediction, a direction we intend to explore in future work.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: See https://github.com/ml-ml/Link-MoE/.Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: See details in Appendix A.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
conclusion: 
 In this study, we explored various heuristics and GNN4LP models for link prediction. Based on the analysis, a novel MoE model Link-MoE is designed to capitalize on the strengths of diverse expert models for link prediction. The extensive experiments underscore the exceptional performance of Link-MoE in link prediction, validating the rationale behind its design. Furthermore, we also showcase the substantial potential of MoE models for link prediction. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: See Section 5.2.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: There was no ethical concerns in either the research process or in potential impacts of our research. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: See Section L. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.Answer: [Yes] Justification: All data and models used in our paper are properly cited and attributed, including their license information (see Table 15 . Also, we release the code for our model at https://github.com/ml-ml/Link-MoE/.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 DatasetsThe statistics for each dataset is shown in Table 3 . We adopt the single fixed train/validation/test split with percentages 85/5/10% for Cora, Citeseer, and Pubmed as used in [53] . For the OGB datasets, we use the fixed splits provided by the OGB benchmark [54] . Note that we omit ogbl-ddi due to observations made by Li et al. [53] showing a weak correlation between validation and test performance. For heterophilic graphs Chameleon and Squirrel, we use the same split ratio as Cora. Training Settings. We use the binary cross entropy loss to train each model. The loss is optimized using the Adam optimizer [55] . At first, we train all of the expert models by using the hyperparameters suggested in this repository * . We then do the inference to obtain the prediction score for each link. Secondly, in order to train Link-MoE, we split the original validation dataset into a new training set and validation set. Thirdly, we train the gating model until it converges and choose the model weights associated with the best validation performance. The rationale for utilizing a portion of the validation set to train the gating model is as follows: Given that each expert model is finely tuned on the training data, there exists a significant disparity between the prediction scores for positive and negative edges within this dataset. Should the original training set be employed to train our gating model, the outcome would be skewed-regardless of the gating model's outputs, predicted scores for positive pairs would invariably remain substantially higher than those for negative pairs. Therefore, to train the gating model effectively, we repurpose the original validation set as our training data, dividing it into new training and validation subsets. Unlike baseline models, which are trained exclusively on the original training set, our method benefits from incorporating a very small validation set compared to the training set into the training process for the gating model, yielding notable performance improvements. Despite this modification, the comparison remains relatively fair.The original validation set is relatively small, so using a portion of it for training does not significantly alter the amount of data available. Thus, the baseline models remain essentially equivalent, even with this adjustment. Moreover, it is common for validation set is to be used for the search of model architectures in neural architecture search. We train both experts and gating models on NVIDIA RTX A6000 GPU with 48GB memory.Training Data Split. In the original datasets, we are given a fixed train, validation and test dataset. These splits are used to train each individual expert. Once each expert model is fully trained, we perform inference on the validation and test sets, thereby obtaining the prediction score for each link. As noted earlier, we split the original validation set into a new training and validation split for training and validating Link-MoE. Note that the original test dataset is still used solely for testing. When splitting the validation set, we use different ratios for different datasets. For ogbl-citation2, ogbl-ppa, ogbl-collab, Citeseer, Chameleon and Squirrel, the ratios are 0.8, and for Cora and Pubmed, the ratios aer 0.9.Hyperparameter Settings. The hyperparameter ranges are shown in Table 4 . Since our gating model has a low complexity, we can efficiently search over a large hyperparameter space on all eight datasets.Evaluation Setting. The evaluation is conducted by ranking each positive sample against a set of negative samples. The same set of negatives are shared among all positive samples with the exception of ogbl-citation2, which customizes 1000 negatives to each positive sample. The set of negative samples are fixed and are taken from Li et al. [53] and Hu et al. [47] for their respective datasets.* https://github.com/Juanhui28/HeaRT/tree/master Mean-Ensemble. After training the experts, we can obtain the prediction score on the test set from each expert. Then we take the mean across all experts to get a final score for link in the test set. The purpose of this model is to ascertain whether naively combining the different experts is itself enough for good performance. More formally, the Mean-Ensemble can be defined as follows:EQUATIONGlobal-Ensemble. For the Global-Ensemble, we learn a weight vector w = [w 1 , w 2 , ..., w m ] to combine the experts which can be defined as follows:EQUATIONNotably, the w is uniform for all node pairs. Therefore, this method is not able to flexibility adjust the weight of different experts to each node pair. Rather, a single weight is used across all samples. The purpose of this method is to test whether it is necessary to customize the weight of the experts to each link as is done in Link-MoE.In this section, we extend the preliminary study (Section 3) with additional results, including model and heuristic overlaps on Cora, Citeseer, Pubmed, and ogbl-ppa datasets. We also analyze the performance of various models across node pair groups categorized by Commen Neighbors (CN), Shortest Path (SP), and Feature Cosine Similarity (FCS).Following Section 3, for the Cora, CiteSeer, PubMed, we use Hits@3. And we use Hits@20 as the metric for ogbl-ppa dataset. The results are shown in Figure 9 and Figure 10 . From the results, we can have the following findings:• For most datasets, the overlapping between different GNN4LP models is not very high, which consistent with the finding in Section 3. • The feature cosine similarity usually has much smaller overlapping with other methods.In this section, we showcase the varied performances of GNN4LP models across groups categorized by shortest path and feature cosine similarity within the Cora and ogbl-collab datasets. The results for these heuristics are depicted in Figure 11 for shortest path groups and in Figure 12 for cosine similarity groups. We have the following observations:• For the Cora dataset, SEAL excels over other models at shorter path lengths, while MLP shows superior performance for longer paths. In the ogbl-collab dataset, BUDDY is effective at shorter distances, whereas Neo-GNN, which integrates multi-hop common neighbor information, performs better as the shortest path (SP) length increases. • For the Cora dataset, the seal excels over other models at smaller feature cosine similarity, while MLP outperforms when the feature cosine similarity is high. For the ogbl-collab dataset, NCNC is effective at low feature cosine similarity, but BUDDY can works well when the feature similarity is high. • Different datasets exhibit distinct patterns, even within the same heuristic groups. There is no single model consistently outperforms others across all groups.These observations further validate the rationale behind employing heuristics as inputs to the gating model, effectively leveraging the strengths of various GNN4LP models.We present additional results of Cora, Citeseer, Pubmed, and OGB datasets in Table 5 , 6, 7, and 8, respectively. We use">24h" to denote methods that require more than 24 hours for either training one epoch or evaluation. OOM indicates that the algorithm requires over 50Gb of GPU memory [53] . Note that LPFormer [27] is omitted from these tables as it doesn't report the results on these additional metrics. The data presented in these tables indicate that Link-MoE consistently achieves the best results in most cases, demonstrating its superior effectiveness in link prediction task. Although it does not always achieve the best performance across all metrics for the Cora and Citeseer datasets, it usually achieves the second or third best results. This slightly diminished performance can likely be We conduct experiments on the ogbl-collab and Pubmed datasets, we limit the activation to the Top-3 experts. And we also conduct experiments using 3 or 4 experts. Specifically, for the ogbl-collab, we use MLP, NCNC, BUDDY (3 experts) and Neo-GNN (4 experts); for the Pubmed datasets, we use NCN, SEAL, NCN (3 experts) and MLP (4 experts). The performance metrics used to evaluate this approach are also Hits@50 for ogbl-collab and MRR for Pubmed. The result are shown in Table 9 . From the results, we can find that only 3 or 4 experts can achieve comparable performance with using all experts. Notably, these results don't use the computationally intensive SEAL for the ogbl-collab datasets. Furthermore, the inclusion of the less effective MLP expert in the Pubmed dataset still results in performance improvement, highlighting the complementary nature of the experts and the effectiveness of the proposed method. From the result, a sparse gating mechanism can also achieve promising performance on both datasets.The full algorithm is detailed in Algorithm 1. Notably, line 1-3 trains the experts individally. Line 4 performs the inference on links to obtain the prediction scores using the obtained experts and get the heuristic features for each link. Line 5-7 updates the gating model using Equation 3.Table 8 : Additional results on OGB datasets(%). Highlighted are the results ranked first, second, and third. We use * to highlight the experts we used in Link-MoE.ogbl-collab ogbl-ppa ogbl-citation2 Hits@20 Hits@100 Hits@20 Hits@50 Hits@20 Hits@50 Hits@100 CN We conduct experiments on two widely used heterophilic graphs, i.e., Chameleon and Squirrel. We follow the same setting with [56] and use the MRR for the evaluation metrics. The results are shown in Table 10 . From the results, we can find the proposed Link-MoE outperforms the baselines by a large margin. These results demonstrate the proposed Link-MoE works well for both the homophilous and heterophilic graphs. We also analyzed the weights generated by the gating mechanism on the two heterophilic graphs.The results are shown in Figure 13 . We observed that feature proximity-based experts, such as MLP and GCN, are rarely employed for both datasets. This is consistent with the characteristics of heterophilic graphs, where connect nodes tend to have dissimilar features. These findings demonstrate the effectiveness of our gating design, as it accurately selects the appropriate experts for different types of graphs. In this section, we explore the end-to-end training of the experts and gating models, as shown in Table 11 and Figure 14 . Our results show that the convergence speed of different experts varies significantly, which often leads to the model collapsing to a single expert. As a result, the performance of end-to-end training is not as good as the proposed Link-MoE. Despite this, it remains an interesting and challenging idea to explore the effective end-to-end training. We compare our methods with two ensemble methods [30, 31] specifically designed for link prediction tasks. Specifically, [30] found that individual link prediction algorithms exhibit a broad diversity of prediction errors on different graphs and utilized a random forest to ensemble various link predictors; Similarly, [31] employs different graph embedding techniques to train multiple link predictors, using the outputs of these predictors as inputs for training a subsequent link predictor. We conduct experiments on ogbl-collab and Pubmed dataset.The evaluation metrics are Hits@50 and MRR for ogbl-collab and Pubmed, respectively. The results, shown in Table 12 , demonstrate that the proposed Link-MoE model significantly outperforms the ensemble-based methods by a large margin. This can be attributed to the dynamic nature of our gating module, which assigns customized weights to each expert for every node pair. We compare our Link-MoE with different gating inputs on ogbl-collab and Pubmed datasets. The evaluation metrics are Hits@50 and MRR for ogbl-collab and Pubmed, respectively. Specifically, we design two different gating inputs.The first one is traditional gating, which only leverages the node features in gating. The results are shown in Table 13 (Traditional Gating). Traditional Gating only results in comparable performance to the best single experts, while our approach yields superior performance. This phenomenon demonstrates the effectiveness and rationality of the designed gating model.To investigate the impact of involving expert model predictions as input to the gating model, we conducted experiments on the ogbl-collab and Pubmed datasets by concatenating the prediction results of experts with the heuristic features. The results are shown in Table 13 (With Experts as Input). We observed that involving the experts' prediction results as additional input did not lead to improvement. In fact, this approach may result in lower performance compared to using heuristics alone. This phenomenon suggests that the outputs of the expert models may not effectively reflect their importance to specific node pairs, highlighting the effectiveness and rationality of using heuristics as the gating input. We conducted additional experiments under the HeaRT setting [53] with OGB datasets, and the results are shown in 14. In the HeaRT setting, hard negative samples are selected for positive samples based on specific heuristics, restricting the negatives to include one of the two nodes from the original positive pair. The results in Table 14 demonstrate that Link-MoE still significantly outperforms the best baseline models, even in this more challenging evaluation scenario.In our current work, we explore various heuristics and GNN4LP models for link prediction and demonstrate the potential of MoE models in this context. The training of the gating model in Link-MoE relies on pre-trained experts and heuristic features generated from the graphs. Although we can select a few experts, training these pre-trained experts remains time-consuming, especially for complex models. Additionally, since real-world graphs come from diverse domains and the graph generation process might be quite different, the heuristics used in this paper might not be comprehensive to other domains. Future work should focus on exploring more heuristics to better accommodate diverse domains.In this paper, we explore the use of a mixture of experts (MoE) model for use in link prediction. We view the impact of this work as positive, as it can help improve performance of link prediction in many real-world applications including drug discovery and recommender systems. In general, we don't envision any specific negative societal consequences of our work. However, it is possible that the choice of experts used in our model may introduce some negative effects that stem from those individual models.The license for each dataset can be found in Table 15 . Justification: See Section 3 and 5.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: The paper proposes an ensemble method for link prediction, where the mixing coefficients are predicted *separately* for each pair of nodes based on a set of heuristic features.
The strengths of the paper are
1. A clear motivation, including detailed and convincing preliminary analyses (`bwf6`, `fyCt`, `758a`, `SDXC`).
2. Strong experimental results (`bwf6`, `fyCt`, `758a`, `SDXC`) and evaluation on standard benchmark datasets (`758a`).
3. The availability of the source code (`bwf6`) and the simplicity of rebuilding the system in the community (`fyCt`), as well as being an intuitive method (`fyCt` - this was mentioned as a weakness, but to me it is a strength).
4. Clear writing (`bwf6`, `fyCt`, `758a`, `SDXC`).

The weaknesses are
1. Its limited technical novelty (`bwf6`, `SDXC`)
2. Its limitation to a single use case, inductive connection prediction (`fyCt`)
3. Its computational complexity (`bwf6`, `SDXC`)
4. The lack of additional analyses, e.g. the number of experts selected or qualitative differences in homophilic vs. heterophilic graphs.
5. Some missing baselines, namely [0] (`SDXC`) - during the rebuttal additional results for [1, 2] were provided instead.
6. The lack of a clear distinction again mixture of experts.

There were discussions with most reviewers, some over several rounds, in which some issues were resolved while others remained controversial. 

[0] Ghasemian, A., Hosseinmardi, H., Galstyan, A., Airoldi, E. M., & Clauset, A. (2020). Stacking models for nearly optimal link prediction in complex networks. Proceedings of the National Academy of Sciences.  
[1] Stacking Models for Nearly Optimal Link Prediction in Complex Networks, PNAS'20  
[2] An Ensemble Model for Link Prediction based on Graph Embedding, Decision Support Systems'22

Reviews: review: paper_summary: paper_summary: This paper presents a mixture of experts model, termed Link-MoE, for link prediction on graphs. Link-MoE individually trains various link prediction models as experts and selects the most appropriate experts for different node pairs. The prediction results from the selected experts are then weighted to produce the final predication. Experiments and analyses validate the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1. This paper presents a straightforward application of the MoE model to the problem of link prediction. Despite its empirical effectiveness, the technical novelty appears limited. The methodological contributions could be enhanced by addressing specific problems associated with MoE models, e.g., the collapse problem, in the context of link prediction. 
2. The experimental evaluation could provide more insights and deeper analyses on important issues, for example,
- How does Link-MoE determine the appropriate number of experts?
- On heterophilic graphs, how the experts selected by Link-MoE differ from those selected on homophiles graphs?
3. The complexity of the proposed method can be high. The nature of using MoE makes the proposed method difficult to scale up.
questions: questions: See weaknesses above.
limitations: limitations: The authors have discussed the limitations in terms of the scalability.
paper_summary: paper_summary: Link prediction in graphs is a fundamental task in graph machine learning and multiple heuristics and ML algorithms have been designed in research to leverage the pairwise and structural information to predict links between nodes. This work takes inspiration from the success of MoE models across various verticals and proposes a new method that outperforms the SoTA baselines on this task on several standard datasets. The authors demonstrate that heuristics and algorithms for LP are very diverse in their capabilities to predict links depending on the node structure and pairwise features (i.e. when one would perform well, the other might not). Due to this little overlap in their abilities the authors propose a dynamically weighted ensemble (MoE) like approach - such that a gating network predicts the weight given to each expert's prediction and the overall value is the weighted sum. 
They also provide a very practical method to train the experts and the gating network achieving SoTA performance beating the second best by significant margins.
strength_weakness: strength_weakness: - The method being used is fairly obvious and intuitive.
- It solves for a very specific task - Link Prediction in an inductive setting only. Not clear to me how it could be leveraged for a transductive setting as well
questions: questions: - Did you face any convergence issues with training the gating network ?
- What happens when you use a graph network which is transductive in nature ? Can that information be leveraged in some manner ?
- In the situations when the graph is a KG on language. Can LLM's outperform this method ?
limitations: limitations: The method is pretty generic and the societal impacts are not discussed in a lot of detail as it wont be different from existing methods.
paper_summary: paper_summary: The paper proposes a mixture of experts model, Link-MoE, for link prediction on graphs. The motivation behind the proposed approach is that different node pairs within the same dataset necessitate varied pairwise information for accurate prediction, while existing methods consider the same pairwise information uniformly across all pairs. To address this, Link-MoE consists of multiple expert models (existing link prediction methods) and a gating model whose goal is to produce importance scores to weight the different expert models according to their contribution towards the final prediction. Experiments on several real-world datasets show that the proposed Link-MoE outperforms existing competing methods, validating the rationale behind its design.
strength_weakness: strength_weakness: W1) The figures are hardly readable sometimes (e.g., Fig. 8), the font size (in the legend) should be increased.

W2) Notation problem: in Eq. 1 the gating function G has only one parameter while in Eq. 2 G takes both x_ij and s_ij. Please uniform it as this may be a little confusing for the reader.

W3) The difference between the proposed Link-MoE and the considered baseline Global-Ensemble should be further discussed in the main paper given the strong similarity between the two approaches. As a suggestion, I recommend the authors to move lines 572-575 to the main paper since it describes the main differences between the two methods, i.e. the importance weight vector is uniform in Global-Ensemble while it is adaptable to the pair in Link-MoE.

W4) To evaluate the effectiveness of the proposed method different metrics are reported for different datasets. 

Minor:
- Eq. 3: final extra parenthesis
- Line 220: “consits” -> “consists”
- Line 234: extra ”the” in “represent the all the”
questions: questions: Q1) Why reporting different metrics for different datasets? As an example, line 155, the authors state that they report MRR for Citeseer and Hits@50 for ogbl-collab. Similarly, in Table 2, different metrics are reported for different datasets. have seen this approach used in other papers on link prediction, but I am not convinced that it is the correct way to proceed because, as shown in the tables in the appendix (e.g., Tables 5-7), the proposed method is not always the best when the evaluation metrics are changed.
limitations: limitations: Yes
paper_summary: paper_summary: This paper proposes an ensemble model of different link prediction methods. The authors find that different node pairs on the graph can form a link due to different pairwise representations, and there is no single link prediction model that can capture all of them. Then the author proposes to combine the outputs of different link prediction models into one ensemble model, weighted by the heuristics information of the node pair. Experiments on graph benchmarks show the improvement brought by ensembling.
strength_weakness: strength_weakness: 1. The novelty of the paper is limited. This study proposes a mixture of existing link prediction models, which brings minor research values to the community. The overall contribution of the paper makes it more like a technical report, rather than a research paper. While this paper has its own value, it is more suitable to be submitted to other venues.

2. The baselines considered in the experiment are not comprehensive. For example, [1], which is an ensemble of link prediction models, is not evaluated as a baseline.

3. The overall computational efficiency of the mixture method is concerning. On each graph, a set of link prediction models needs to be trained first, which typically involves an extensive process of hyperparameter tuning like in NCN [2]. This step can be too costly for most real-world use cases. The idea of MoE, especially conditional computation, is not leveraged at all to reduce the computational cost.

4. The authors can further benchmark the Link-MoE on [3], which introduces more challenging link prediction tasks.

[1] Ghasemian, A., Hosseinmardi, H., Galstyan, A., Airoldi, E. M., & Clauset, A. (2020). Stacking models for nearly optimal link prediction in complex networks. Proceedings of the National Academy of Sciences.

[2] Wang, X., Yang, H., & Zhang, M. (2023). Neural common neighbor with completion for link prediction.

[3] Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., ... & Yin, D. (2024). Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. Advances in Neural Information Processing Systems.
questions: questions: 1. For the gating model, only the heuristics information is considered as the input. However, this can limit the expressiveness of gating models, because the inherent limitation of the heuristics models themselves. Do authors consider involving the expert models as inputs to the gating models?

2. Following up on the question above, is there any ablation study on training the gating model and expert models jointly? It may introduce higher memory consumption, but one can consider remove the computational heavy models like SEAL or NBFNet.
limitations: limitations: See the weakness and question parts.

Comments: title: Response to Reviewer SDXC
Further response to Reviewer SDXC
A friendly reminder
Further response to Reviewer SDXC - Part 2
Further response to Reviewer SDXC - Part 1
Response to the follow-up questions
Follow-up discussion
comment: Dear Reviewer SDXC,
 
I believe that one goal of inviting multiple reviewers for one paper is to provide opinions from various perspectives and mitigate potential bias and unfairness because different people may view things from different angles.  We always believe the professional of reviewers that is why we are eager to submit our papers for pear reviews and feedback. So it is unfair for you to mention that "other reviewers arguing for acceptance may not read the manuscript as carefully or be as familiar with link prediction as I am."
Dear Reviewer SDXC,

Thank you for your further reply. We appreciate your engagement and would like to provide additional clarification:

1. As you pointed out, MoE "achieve better efficiency by routing the prediction to different domain experts.", our Link-MoE benefits from such sparse gating strategy. We have demonstrated that Link-MoE with top-2 gating achieves comparable performance to using all experts. Therefore, we respectfully disagree  that the Link-MoE is very bad at inference time. 

2. We have indeed discussed Link-MoE with sparse gating and presented experimental results in **Section 5.2 and Appendix D of our paper**. However, the sparse gating is a widely used technique in MoE.  We didn't consider the sparse gating as the major contribution of our paper, which is why we included the related results in the Appendix. Instead, the key contributions and novelty of Link-MoE lie in the thorough analysis of the complementary properties of GNN4LP models, the insight that different node pairs benefit from different experts and heuristics, the exploration of the relationship between heuristics and GNN4LP models, the novel gating design, and the resulting strong performance. 

We understand your concern about the importance of time complexity in link prediction. However, Link-MoE can effectively benefit from the sparse gating mechanism commonly used in traditional MoE models. Link-MoE introduces a novel approach to link prediction from a different perspective:  instead of designing new models from scratch, we first focus on understanding the behavior of existing models and then leveraging their strengths for better predictions. We believe this idea can be applied to other tasks and domains.

Best regards,

All authors
Thanks for the detailed responses. In light of the authors' effort to address my concerns, I raised my score to 4 for now, I will explain why I made such a decision:

1. I still have concerns about the scalability of Link-MoE. I agree with the authors' responses above. However, just as the authors suggested, Link-MoE is **potentially** as scalable as other sota individuals. All the discussions about two-stage/offline are hypothetical. No performance/inference time is measured under this setting. What we can see so far is that Link-MoE is good at performance but very bad at inference time.

2. I think Link-MoE will be a much solid study if the main method is the Sparse Gating one. I believe such a design could be much more efficient. An experiment benchmarking time complexity can present how efficient Link-MoE can be. However, the current version of the manuscript and the rebuttal do not include these.

3. After the rebuttal and discussion with the authors, I have a slightly positive view of the paper. However, I also found that other reviewers arguing for acceptance may not read the manuscript as carefully or be as familiar with link prediction as I am. For example, Reviewer fyCt commented that Link-MoE is trained end-to-end, which is in fact a two-stage training. Also, no other reviewer asks questions about time complexity. Even though the "time complexity" question can be an unfair gatekeeping for some studies, it is critical for almost all sota LP methods (BUDDY, NCN, LPFormer) after SEAL. Therefore, I have to make the decision carefully to reflect the actual merit of the paper. I need some time to consider the score and discuss with AC about the situation. I hope the authors understand.
Dear Reviewer SDXC,

Thank you for sharing your additional concerns. We appreciate your thorough review and are happy to provide detailed responses to each of your concerns.

### **1. Offline and Two-stage strategy** 

We would like to clarify your first and second concerns together as below: 

We totally agree with you that the time complexity of LP is $O(N^2)$, making it impractical to apply even simple models to rank all possible edges. Based on our industry experience and collaborations on various link prediction problems, (1) most real-world applications of link prediction no matter whether the inference is offline or online adopt a two-stage strategy; and (2) Models like NCN and BUDDY also cannot be directly applied but utilize this two-stage approach. Therefore, Link-MoE has the potential to be applied just like the individual expert (e.g., NCN or BUDDY) 

**Performance of Link-MoE with the two-stage strategy.** In fact, the HeaRT setting is similar or mimicking the two-stage strategy. As stated in the Section 4.2 of HeaRT paper, *"The key challenge is how to generate a subset of $S(u,a)$. ... This is similar to the concept of candidate generation, which only ranks a subset of candidates that are most likely to be true."* Particularly, in the HeaRT setting, negative samples for each node are first generated based on multiple heuristics, which serves as the first stage to recall a small set of items. Then the evaluated LP method will score this subset which is against the groudtruth to get the metric performance. Therefore, our experimental results under the HeaRT setting, which show that Link-MoE outperforms the best expert by a significant margin on all OGB datasets, can indicate that Link-MoE remains effective even under the two-stage strategy.

### **2. Sparse Gating**

Thank you for emphasizing the importance of sparse gating. We agree that sparse gating is crucial for improving the inference efficiency of Link-MoE.  Actually, we have discussed the sparse gating in the Section 5.2 and Appendix D of our paper. Our experimental results on both the ogbl-collab and Pubmed datasets show that even using top-2 gating can outperform the best expert by a large margin. We are currently running additional experiments with sparse gating and will include more discussions and results in the revision, as you suggested.

### **3. About Inference time**

Regarding the selection of experts, we did not specifically choose certain experts; rather, we included all popular baselines as experts. Besides, we also conducted experiments with fewer experts, as shown in Appendix D of our paper.  For example, on the ogbl-collab dataset, we used MLP, NCNC, BUDDY (3 experts), and Neo-GNN (4 experts).

|  | Best Expert | 3 Experts | 4 Experts | All Experts |
|---|---|---|---|---|
| Hit@50 | 66.13 | 71.25 | 72.75 | 71.32 |

We can find that good performance can still be achieved with 3 or 4 experts without SEAL. Additionally, the Figure 7 in our paper shows that removing any one expert, including SEAL, does not significantly impact performance.

For the Citation2 dataset in both the regular and HeaRT settings, we did not use the Shortest Path heuristic. Besides, for all the ogbl dataset in the HeaRT setting, we didn't use the SEAL as the inference time is slow. We will include these details in the revision.

### **4. HeaRT results**

We have submitted a paper on LP with the HeaRT setting but were asked to using the traditional setting. It could be because the HeaRT paper is published last year, and most of the papers still adopt the traditional setting. Based on this experience, we initially adopt the traditional setting.  The reason why we heavily rely on the HeaRT implantation is the code provided in the HeaRT paper includes implementations for both the traditional and HeaRT settings. 

**We really appreciate your comments and follow-ups. This process indeed helps us demonstrate more advantages of Link-MoE, clarify its potential applications, and think about potential future works of Link-MoE. We will include all these discussions in the revision and we look forward to any further comments or questions you may have.**

Best regards,

All authors
Thank the authors for addressing my questions. I have further concerns regarding the scalability of Link-MoE:

> The training and inference of LP models can both happen offline. 

However, it is not a solid reason that a practical method can trade efficiency for performance gain. One of the most challenging issues of LP tasks is that the potential edges to score is $O(N^2)$. Therefore, even in an offline setting, efficiency is of great concern for any practical LP model.

> Two-stage strategy to recall first and score later.

This is a practical strategy. However, it is unknown whether Link-MoE can still perform well with such a strategy. Most likely, the performance will drop somehow depending on the selected method at the recall stage. On the contrary, experts like NCN or BUDDY can serve as the entire pipeline to score the edges and maintain the performance reported in the paper. Therefore, it is difficult to claim that Link-MoE is still significantly better than the individual experts in the industrial setting. BTW, I have no much worry about the training cost of Link-MoE. But the inference side is of great concern.

> Sparse Gating.

In my opinion, this is what should be implemented for Link-MoE. It can dynamically adjust the computation cost and only run complex LP models when needed. I **strongly encourage** the authors to expand the discussion on this part, including the method description and experiment results. From the experiment so far, it is hard to tell how good this sparsing gate could be compared to other individual methods. If the authors have the chance to revise the paper substantially, this spare gating method should be the major method introduced in the paper, rather than the current one.

> About inference time.

The current Link-MoE includes SEAL as the expert. I wonder why the authors made such a decision, given that SEAL is known to be both expressive and expensive. In [1], SEAL is reported to run for 28 hours on Citation2 for inference only. Then on PPA, the training and testing time will be over 24 hours. However, the paper does not report the Shortest Path on Citation2 because >24h. Didn't that already surpass 24 hours?

> Another minor question

is that I just found both in the code and paper, the authors are aware of the HeaRT setting. Furthermore, the code itself is heavily built on HeaRT. I just wonder why the HeaRT results are not initially included in the main paper since such a more challenging setting can better prove the strength of Link-MoE.

[1] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.
Dear Reviewer SDXC,

We appreciate your thorough review and have provided a detailed response to your concerns. Since the end of the discussion period is approaching, we kindly request your feedback on our response. Your insights are crucial, and we want to ensure that any remaining issues are addressed before the discussion period concludes. Please let us know if there are any further points that need clarification.

Thank you for your time and consideration.

Best regards,

All authors
## 3. The Practical Applicability of Link-MoE.

Some of our authors have ever worked in industry and we have collaborated with industry on various link prediction problems. Based on our experiences, we are glad to discuss the potential practical applicability of Link-MOE from the following two perspectives: 

First, in many practical link prediction applications, both the training and inference are offline.  For example, in friend recommendations in social media, the potential list of friends for a particular user is often pre-computed. Therefore in these applications, Link-MOE is potentially to be applicable. 

Second, there are also many link prediction applications where we indeed need to do online inference such as these session-based recommendations. For these applications, we would like to highlight that Link-MOE is also potentially to be applicable with the following two reasons.  (1) These applications often adopt a two-stage strategy to ensure the efficiency. They will first use a simple method to recall a small subset of items, say $L$. Then they will leverage link prediction algorithm to only score these $L$ items. $L$ is much smaller than the whole set of items which is often hundreds or thousands. That is why sophisticated methods can be applied in these applications.  (2) We acknowledge that during training, Link-MoE requires the training of several experts, which can be computationally intensive. However, the training phase is often conducted offline, meaning that the computational cost during training is less of an immediate concern.

**Regarding the inference, our Link-MoE can also leverage the Sparse Gating to improve the efficiency.** During inference, the gating model first determines the importance of each expert, allowing us to calculate predictions using only the most relevant experts. This selective approach significantly reduces the computational load during inference. Here, we demonstrate the results of Top-2 and Top-3 gating, which only use 2 or 3 experts for each sample during inference.

|  | ogbl-collab | Pubmed |
|---|---|---|
| Best Expert | 66.13 | 44.73 |
| Top-2 Gating | 71.22 | 50.03 |
| Top-3 Gating | 71.94 | 51.13 |
| All Experts | 71.32 | 53.15 |

From the results, using only 2 or 3 experts can achieve performance comparable to using all experts. This demonstrates the potential of using Link-MoE for online inference in real-world applications.

## 4. The HeaRT setting.

We would like to clarify that the statement "Observation 1 in Section 4.3 claims that simpler models actually perform better than complex ones" is not accurate. Observation 1 in the HeaRT paper actually claims that the performance gap between simpler models and GNN4LP models is reduced under the HeaRT setting. However, GNN4LP models still outperform simpler models, as shown in Table 5 of the latest version of the HeaRT paper[8] (v3 version on arXiv).

We have conducted additional experiments under the HeaRT setting with all OGB datasets, and the hit@20 results are shown below. Our findings indicate that Link-MoE still outperforms the best baseline models by a significant margin, even in this more challenging evaluation setting.

|  | ogbl-collab | ogbl-ddi | ogbl-ppa | ogbl-citation2 |
|---|---|---|---|---|
| Best Expert | 23.35 ± 0.73 | 67.19 ± 1.18 | 82.24 ± 0.40 | 53.76 ± 0.20 |
| Link-MoE | 39.58 ± 0.10 | 68.73 ± 0.43 | 88.49 ± 0.56 | 58.04 ± 0.47 |

[1] Ghasemian, Amir, et al. Stacking Models for Nearly Optimal Link Prediction in Complex Networks, PNAS'20

[2] Chen, Yen-Liang, Chen-Hsin Hsiao, and Chia-Chi Wu. "An ensemble model for link prediction based on graph embedding." Decision Support Systems 157 (2022): 113753.

[3] Jacobs, Robert A., et al. "Adaptive mixtures of local experts." Neural computation 3.1 (1991): 79-87.

[4] Jordan, Michael I., and Robert A. Jacobs. "Hierarchical mixtures of experts and the EM algorithm." Neural computation 6.2 (1994): 181-214.

[5] Shahbaba, Babak, and Radford Neal. "Nonlinear models using Dirichlet process mixtures." Journal of Machine Learning Research 10.8 (2009).

[6] Eigen, David, Marc'Aurelio Ranzato, and Ilya Sutskever. "Learning factored representations in a deep mixture of experts." arXiv preprint arXiv:1312.4314 (2013).

[7] Masoudnia, Saeed, and Reza Ebrahimpour. "Mixture of experts: a literature survey." Artificial Intelligence Review 42 (2014): 275-293.

[8] Li, Juanhui, et al. "Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking." Advances in Neural Information Processing Systems 36 (2024).

We hope that we have addressed the concerns in your comments, and please kindly let us know if there is any further concern, and we are happy to clarify.

Best regards,

All authors
Dear Reviewer SDXC,

Thank you for your prompt reply, allowing us the opportunity to further clarify your concerns.

## 1. Difference from Traditional Ensembling Methods

Although Link-MoE leverages different link prediction models, it is not a simple ensembling method. Meanwhile, we respectively disagree "it is not a "surprising" thing to see performance gain by bundling SOTA methods together.".  In fact, traditional ensembling methods often do not outperform the strongest individual base model. To illustrate this, we tested four ensembling methods, including Mean-Ensemble and Global-Ensemble in our paper, as well as two new ensembling methods [1][2]. For all these methods, we used the same base models to ensure a fair comparison. The results are shown below:

|  | ogbl-collab | Pubmed |
|---|---|---|
| Best Expert | 66.13 | 44.73 |
| Mean-Ensemble | 66.82 | 38.54 |
| Global-Ensemble | 67.08 | 37.63 |
| Ensemble [1] | 69.65 | 41.21 |
| Ensemble [2] | 65.11 | 43.92 |
| Traditional gating | 66.59 | 42.15 |
| Link-MoE | 71.32 | 53.10 |

The results indicate that these traditional ensembling methods typically have comparable or even worse performance compared to the best individual expert. This underscore the key contribution to Link-MoE’s success is its ability to assign different node pairs to different experts based on our gating mechanism. The design of this gating mechanism is informed by our preliminary studies, which revealed that different experts excel at different heuristics.

Additionally, we tested the traditional gating in MoE, which uses the same input as the experts. The results show that the performance of 'Traditional Gating' is even worse than the best expert. This highlights that the strength and contribution of Link-MoE lies not in simple ensembling, but in its intelligent and heuristic-informed allocation of node pairs to the most suitable experts.

## 2. The name of MoE

The term "Mixture of Experts" (MoE) is a broad concept that can be traced back to foundational works such as [3][4]. These MoE models follow the divide-and-conquer principle, where the problem space is divided into subspaces, each of which is potentially easier to solve with specialized experts. Many papers [3,4,5,6] have leveraged the MoE framework to improve model performance, as outlined in the survey [7]. In recent years, MoE has gained popularity again due to the introduction of sparse gating mechanisms, which allows for increasing the model parameters while maintaining efficiency. However, the essence of MoE is not limited to parameter efficiency or reduction. The core idea is the strategic use of specialized experts to handle different aspects of the problem. Our Link-MoE model adheres to this divide-and-conquer principle by routing different node pairs to different experts based on the characteristics of the node pairs. Therefore, we believe that Link-MoE can be considered as a MoE model.
Thanks for the extensive efforts in addressing my concerns. However, I still have several major concerns that prevent me from recommending acceptance of the work. As previously discussed in W1 and W3, I am still concerned about the contribution and motivation of Link-MoE. 

1. Link-MoE achieves good performance by ensembling a set of SOTA GNN4LP models. However, this makes the contribution limited because ensembling may be the most well-known method to improve performance. In general, it is not a "surprising" thing to see performance gain by bundling SOTA methods together.

2. The MoE naming is a bit misleading. The author introduces the "MoE" techniques in Link-MoE. However, Link-MoE does not either (1) reduce the parameter size of the entire model; or (2) achieve better efficiency by routing the prediction to different domain experts. 

3. Given that LP is a practical problem, scalability is one of the most crucial aspects to consider when choosing LP methods. However, Link-MoE is computationally expensive in both the training and inference stages. During training, the expert model needs to be trained individually with proper hyperparameter tuning. (This is acknowledged in the Limitation section of the paper). During the inference, Link-MoE will require the link representation from all the expert models. This paradigm makes Link-MoE almost impossible to be deployed in industrial applications. 

If possible, I want to know more about the authors’ comments on the practical applicability of Link-MoE to real-world scenarios.

4. As far as I can see from the paper, the only aspect (research value vs novelty vs insights vs practical usage) that Link-MoE shines on is its superior performance improvement on various benchmarks. However, as [3] points out, HeaRT is a more realistic and personalized evaluation benchmark for LP methods. Since evaluating on HeaRT only requires a small change in the model inference stage (change the random negative edges to hard negative edges in HeaRT) and no need to retrain anything, it is expected that Link-MoE can be evaluated on all datasets in HeaRT, especially those OGB datasets. However, the results are missing from the rebuttal or main experiment. When I revisited HeaRT paper, Observation 1 in Section 4.3 claims that simpler models actually perform better than complex ones. This seems to contradict what is observed in Link-MoE.

In general, I find the paper well-written and the preliminary study part is interesting. However, the major concerns above outweigh the paper's strength. Therefore, I keep my original rating.
Dear Reviewer 758a,

Thank you for your thoughtful responses and your enthusiasm about our work. We are glad to answer your follow-up questions.

**1. Computation of Jaccard Coefficient**

For the calculation of the Jaccard coefficient, we use the Hits@K metric for each edge. Specifically, we choose Hits@3 for small datasets and Hits@20 for the OGB datasets. We first rank the prediction scores of each method for both positive and negative edges. If the prediction score of a positive edge is in the top-K, we label this positive edge as 'present' and add it to the correct prediction set. In this way, we can calculate the Jaccard coefficient by comparing the correct prediction sets for each pair of methods.

Besides, your suggestion that using a threshold is also a feasible way.

**2. Combination of Heuristics**

Regarding the combination of heuristic scores, we did perform the normalization as you suggested. Specifically, we will normalize each Heuristic (H) to the range of [0, 1] using $\frac{H-Min\\_H}{Max\\_H - Min\\_H}$, where $Max\\_H$ and $Min\\_H$ are the maximum and minimum heuristic values in the dataset. One exception is the Shortest Path (SP), where a smaller SP indicates a higher likelihood that two nodes are connected. Therefore, we first calculate $\frac{1}{SP}$, and then normalize $\frac{1}{SP}$ in the same way as other Heuristics.

We will add these details in our revision. Thank you once again for your thoughtful feedback and for helping us improve our work. If you have any further comments or questions, please let us know.

Best regards,

All Authors
I appreciate the detailed responses from the authors (as well as those to other reviewers), which have made me more enthusiastic about this work. I have two follow-up questions:
- I am curious about how you computed the Jaccard coefficient to calculate the overlap ratio between each pair of heuristics (Figures 2 and 3). Did you use a threshold to decide whether a prediction for an edge is ‘present’ or ‘missing’? Otherwise, I cannot see how you counted the number of edges that were correctly predicted or not by a pair of methods.
- Another point of curiosity: In line 129, you state that you assess the combination of a pair of heuristics by simply adding their original values. Does this mean that you did not normalize the scores before adding them? Since some heuristics may have different ranges, this approach might not be appropriate.