LPNL : Scalable Link Prediction with Large Language Models (2024)

Abstract: Exploring the application of large language models (LLMs) to graph learning is an emerging endeavor. However, the vast amount of information inherent in large graphs poses significant challenges to graph learning with LLMs. This work focuses on the link prediction task and introduces **LPNL** (Link Prediction via Natural Language), a framework based on large language models designed for scalable link prediction on large-scale heterogeneous graphs. We design novel prompts for link prediction that articulate graph details in natural language. We propose a two-stage sampling pipeline to extract crucial information from the graphs, and a divide-and-conquer strategy to control the input tokens within predefined limits, addressing the challenge of overwhelming information. We fine-tune a T5 model based on our self-supervised learning designed for link prediction. Extensive experimental results demonstrate that LPNL outperforms multiple advanced baselines in link prediction tasks on large-scale graphs.

## introduction heterogeneous graphs @xcite are commonly employed for modeling complex systems, wherein entities of diverse types interact with each other via various relations. figure 1 shows the heterogeneous nodes and their relationships sourced from the open academic graph (oag) @xcite . link prediction @xcite is a fundamental task in graph learning. however, due to the vast quantity of nodes and edges with their complex structure, addressing the link prediction task on large-scale heterogeneous graphs is challenging. recently, some research @xcite has explored the use of large language models (llms) in graph learning. a popular paradigm of link prediction on graphs with * corresponding author. llms is to transform graph problems and structures into description texts, and then feed the texts to llms to obtain the predictions. however, it remains under explored that how to perform scalable link prediction on large graphs through llms with the input window constraints, which poses serious challenges in capturing distant information and rich semantics. as the number of nodes increases, the text fed into llms grows. consequently, extensive inputs become unfeasible due to token length limitations. in this work, we explore the scalable link prediction with large language models on large-scale heterogeneous graphs. the key challenges can be described as follows: 1) how to fomulate the prompt template for scalable link prediction task. 2) how to find out crucial information on large graphs, enabling llms to capture it within limited inputs. 3) how to address lengthy prompts generated by an excess of candidate neighbors. to tackle the above challenges, we propose lpnl (link prediction via natural language), a large language model based framework for scalable link prediction on largescale graphs. the framework of lpnl is shown in figure 2 . we design novel prompts for link prediction that articulating graph details in natural language. this involves establishing a selective query prompt template, furnishing a description of the link prediction task, and integrating heterogeneous information concerning the source node and candidate neighbors. in dealing with vast amounts of relevant graph information within large graphs, lpnl selects crucial node information from the graph, ensuring that the model focuses more on them. we design a twostage sampling pipeline that utilizes normalized degree-based heterogeneous subgraph sampling and personalized pagerank-based ranking. this approach avoids the interference of superfluous contextual information while ensuring compliance with specified token limitations. with a large number of candidate neighbors, the token length constraints make it challenging to fully describe all candidate neighbor information. to address this issue, we employ a divide-and-conquer method. the original node set is partitioned into multiple sets with smaller size, which are sequentially input into the link prediction pipeline to obtain partial answers. subsequently, we recursively refine the candidate set to predict the final answer. we conduct extensive experiments on the oag and fine-tune the language model t5 @xcite based on our self-supervised learning to serve as the backbone model for lpnl on the oag . the results demonstrate that lpnl significantly outperforms various enhanced gnn-based baselines, achieving an average improvement of 30.52% on hits@1. furthermore, through extensive experimentation, lpnl also exhibits remarkable few-shot capability. unlike traditional models training, lpnl's fine-tuning merely requires simple alignment formatting, enabling swift convergence in predictions. additionally, experiments demonstrate the model's robust knowledge transferability, maintaining consistent performance across various cross-domain tasks. this further emphasizes that lpnl's self-supervised fine-tuning is not confined to fixed graph labels, it can make direct predictions on different graphs without the need for additional learning. ## the lpnl architecture in this section, we introduce the details of our proposed link prediction via natural language, i.e. lpnl, a framework utilizing natural language to solve link prediction task on large-scale heterogeneous graphs. we start with the notation setup, followed by the prompt design, the sampling methods, and our divide-and-conquer and self-supervised strategy with more details. ## discussion from our experiments, we found that describing graphs using natural language does not follow the principle of "more information is better". sampling more nodes can introduce additional information, but it may lead to information redundancy, resulting in a decline in the inferential capabilities of large language models. therefore, the key lies in the setting of the sampling and divide-and-conquer length limits, which should align with the input window size and inferential capabilities of the large language models. while designing prompts, we observe that complex relationships between nodes are challenging to articulate in text, especially in large or dense graphs, potentially leading to redundant contexts. lpnl leverages structural information during the sampling phase and, in the prompt generation, only conveys information about the sampled nodes. this approach aims to minimize context redundancy while maximizing the utilization of graph information. ## conclusion in this paper, we explore, for the first time, the application of large language models to address the link prediction task on large-scale heterogeneous graphs. we introduce lpnl, a large language models based framework for scalable link prediction on large-scale graphs. we design specific prompt templates for the link prediction task and generate the prompts based on anchor nodes obtained through a two-stage sampling approach. these prompts are then input to the large language models for predictions. to tackle the token overload issue arising from an excessive number of candidate neighbors, we employ a divide-and-conquer strategy. empir-ical evaluations demonstrate that lpnl achieves significant improvements compared to gnn baselines, showcasing its robust capability in crossdomain knowledge transfer and few-shot learning scenarios.