Universal Link Predictor By In-Context Learning on Graphs
Authors: Kaiwen Dong
Haitao Mao
Zhichun Guo
Nitesh V Chawla
Venue: Accepted by TMLR ()

Abstract: Link prediction is a crucial task in graph machine learning, where the goal is to infer missing or future links within a graph. Traditional approaches leverage heuristic methods based on widely observed connectivity patterns, offering broad applicability and generalizability without the need for model training. Despite their utility, these methods are limited by their reliance on human-derived heuristics and lack the adaptability of data-driven approaches. Conversely, parametric link predictors excel in automatically learning the connectivity patterns from data and achieving state-of-the-art but fail short to directly transfer across different graphs. Instead, it requires the cost of extensive training and hyperparameter optimization to adapt to the target graph. In this work, we introduce the Universal Link Predictor (UniLP), a novel model that combines the generalizability of heuristic approaches with the pattern learning capabilities of parametric models. UniLP is designed to autonomously identify connectivity patterns across diverse graphs, ready for immediate application to any unseen graph dataset without targeted training. We address the challenge of conflicting connectivity patterns—arising from the unique distributions of different graphs—through the implementation of In-context Learning (ICL). This approach allows UniLP to dynamically adjust to various target graphs based on contextual demonstrations, thereby avoiding negative transfer. Through rigorous experimentation, we demonstrate UniLP's effectiveness in adapting to new, unseen graphs at test time, showcasing its ability to perform comparably or even outperform parametric models that have been finetuned for specific datasets. Our findings highlight UniLP's potential to set a new standard in link prediction, combining the strengths of heuristic and parametric methods in a single, versatile framework.

Published in Transactions on Machine Learning Research (06/2025)
Universal Link Predictor By In-Context Learning on Graphs
Kaiwen Dong University of Notre Dame
kdong2 and. edu
Haitao Mao Michigan State University
halaoomamaau edu
Zhichun Guo University of Notre Dame
zguo5 and. edu
Nitesh V. Chawla
nchowla @nd. edu
University of Notre Dame
Reviewed on OpenReview: https: //:::///pppe openreview. net/ forum? g
Abstract
Link prediction is a crucial task in graph machine learning, where the goal is to infer miss- ing or future links within a graph. Traditional approaches leverage heuristic methods based on widely observed connectivity patterns, offering broad applicability and generalizability without the need for model training. Despite their utility, these methods are limited by their reliance on human-derived heuristics and lack the adaptability of data-driven approaches. Conversely, parametric link predictors excel in automatically learning the connectivity pat- terns from data and achieving state-of-the-art but fail short to directly transfer across differ- ent graphs. Instead, it requires the cost of extensive training and hyperparameter optimiza- lion to adapt to the target. graph. In this work, we introduce the Universal Link Predictor (UniLP), a novel model that combines the generalizability of heuristic approaches with the pattern learning capabilities of parametric models. UniLP designed to autonomously identify connectivity patterns across diverse graphs, ready for immediate application to any unseen graph dataset without targeted training. We address the challenge of conflicting connectivity setterns-arising from the unique distributions of different graphs- the implementation of In-contexi Learning (ICL). This approach allows UniLP to dynami- cally adjust to various target graphs based on contextual demonstrations, thereby avoiding negative transfer. Through rigorous experimentation, we demonstrate UniLP's effectivenoss in adapting to new, unseen graphs at lest time, showcasing its ability to perform comparably or even outperform parametric models that have been finetuned for specific datasets. Our findings highlight UniLP's potential to a new standard in link prediction, combining the strengths of heuristic and parametric methods in single, versatile framework.
1 Introduction
Graph-structured data is ubiquitous across diverse domains, including social networks (Liben-Nowell & Kleinberg 2003), protein-protein interactions (Szklarczyk et al. 2019), movie recommendations (Koren al, 2009), and citation networks (Yang et al. 2016). It encapsulates the complex relationships among entities, serving as a powerful data structure for analytical exploration. At the heart of graph analysis lies the lask of link prediction (LP) (Yang et al. 2015; Dong et al. 2022 Guo et al., 2022), a crucial problem aimed at forccasting missing or future connections within these networks. Over the years, the quest to enhance LP
accuracy has advanced the development of numerous methodologies (Kumar et al. 2020). broadly categorized into two main classes of approaches.

---

Published in Transactions on Machine Learning Research (06/2025)
The first line of works is non- can-paeamttiic heuristics link predictors, including Common Neighbor (CN) LLben-
Nowell & Kleinberg 2003), Preferential Attachment (PA) (Barabási & Albert 1999), Resource Allocation
(RA) (Zhou et al. 2009) and Katz index (Katz 1953). By discovering and abstracting the universal structural
properties underlying different graphs [Barabási & Albert, 1999. Watts & Strogatz 1998; Holland et al.
1983), heuristics methods are developed based on observing the connectivily patterns existing in worl-world
graph datasets. For example, CN assumes the tendency of triadic closure (Easley et al.; 2010), such that a friend's friend is likely be friends in a social network. These heuristics link predictors can be readily applied to any graph dataset with great generalizability. However, this approach relies on predefined heuristics, crafted from human expertise into the graph connectivity. Despite the initial success via capturing one specific connectivity pattern, they fail to capture all the effective structural features in the link prediction, leading to suboplimal performance when applied indiseriminately.
The other line of works is parametric link predictors, which automatically learn the connectivity patterns by fitting the LP models to the target graphs. These parametric methods, especially those Graph Neural Networks (Kipf & Welling 2017 Hamilton et. al.] 2018) for Link Prediction (GNNALP); have dominated the leaderboard of the link prediction tasks (Hu et al. 2021p. Typically, these GNN4LP are provably the most expressive models such that the link representation is permutation-invarian
(Zhang et al. 2021 They can capture more effective structural features compared to the simpler heuristics counterparts. However, their dependency on extensive training for each new graph dataset and the necessity for hyperparameter optimization (Chamberlain et al. 2022 Wang et al. 2023b Dong et al. 2023 present notable challenges for their application across diverse graph environments.
Given that (1) the heuristics methods can be readily applied to any graphs without training based on common connectivity patterns and (2) the parametric model can automatically capture the connectivity patterns by fitting on the graph, a natural question arises:
Can a singular LP model automatically learn and apply the connectivity pattern across new, unseen graphs without the need for direct training?
An affirmative response would not only pioneer a new frontier in graph machine learning but also align with the transformative potential observed in foundation models across text and image processing fields (Brown et al.] 2020; Kirillov et al., 2022)). These models' exceptional generalizability, driven by their capability of transfer learning (Yosinski et al.) 2014), offers a blueprint for the development of a universal LP model capable of broad applicability without explicit fitting.
Present work. In this study, we introduce the Universal Link Predictor (UniLP), novel model designed for immediate application across diverse non-attributed graph environments without the prerequisite of model fitting. Our investigation starts by assessing whether existing LP models possess the capability to transfer connectivity pallern knowledge from one graph to another. Through empirical and theoretical analyses spanning both heuristic and parametric link predictors, we uncover significant challenge: negative transfer (Wang et al.] (021aa) can happen when directly transferring the connoctivity patterns across distinct graph datasets, including both world and synthetic examples. This complexity arises from the inherent diversity and flexibility of graph data, leading to unique connectivity patterns for each graph.
To equip UniLP with the capability to adapt to diverse graphs without the need for training, we are inspired by the concept of In-contexi Learning (ICL) utilized by large language models (LLMs) (Brown el al. 2020). ICT, enables models to adapt to new datasets or tasks through the relevant demonstration examples Wang et al. 2023a). Analogously, for adapting our LP model to a particular graph, we select a collection of in- context links to act as such demonstration examples. These in-context links not only provide a context for link prediction but also aid capturing the unique connectivity pattern inherent to the graph in question. To achieve link representations that are conditioned on the graph's specific connectivity pattern, we employ an attention mechanism (Vaswani et al. 2017 Brody et al. 2022 This mechanism facilitates dynamic
In this study, focus on non-attributed graphs. This choice is informed by previous findings indicating that node attributes have minimal impact on the effectiveness of LP tasks when compared to the structure of the graph. This discussed in detail in Appendix of (Dong et al. 2023).
2

---

Published in Transactions on Machine Learning Research (06/2025)
adjustment of link representations in response to the graph context, enabling the model to accurately reflect the unique connectivity patterns of each graph.
We have curated a diverse collection of graph datasets spanning multiple domains, providing a rich variety of connectivity patterns for benchmarking. Through extensive experiments on these datasets, we demonstrate the seamless applicability of UniLP to novel and unseen graph datasets without requiring dataset-specific fitting. Notably, UniLP, empowered with ICL, exhibits the capability to meet or even exceed the performance levels of LP models that have been pretrained and finetuned for specific target graphs. This achievement underscores UniLP's broad applicability and robust adaptability, establishing groundbreaking approach to link prediction tasks.
In summary, our contributions to the field of link prediction are:
We pioneer in highlighting the challenges of applying a singular LP model across various graph datasets due to conflicting connectivity patterns, finding supported by both empirical evidence and theoretical analysis.
Addressing these challenges, we introduce UniLP, novel LP approach leveraging ICL for dynamic adaptation to new graphs in real-time, thereby eliminating the need for traditional training processes.
The diverse collection of graph datasets we've collected facilitates extensive validation of UniLP's adaptability. Our experiments confirm that UniLP is not only capable of adjusting to any new graph dataset during inference but also achieves competitive performance, marking a significant advancement in link prediction methodologies.
2 Can one model fit all?
Machine learning models perform & task by learning from data. The quest for generalizability in ma- chine learning models has led to significant advancement. in domains such as natural language process- ing (NLP) (Vaswani et al. 2017 Brown et al.) 2020) and computer vision (CV) (Betker et al.) Kirillov ct al. 2023). Foundation models these fields have demonstrated remarkable gencralizability across unscen datasets (Donahue et. al., 2014). primarily due to their training on extensive data, which enables them to learn transferable knowledge.
In the context of LP tasks, the heuristics link predictors can be seen as type of transferable knowledge. These predictors, crafted by manually analyzing common connectivity patterns in real-world graphs, offer insights into the underlying structure of networks. However, the validity of applying these heuristics universally is questioned, especially considering the wide spectrum of graph data. For instance, social networks like Facebook often exhibit community-oriented structure (Newman (2006a). Conversely, networks adhering scale-free power-law distribution (Barabási & Albert 1999), such the World Wide Web, tend favor Preferential Attachment connectivity pattern. Through both empirical and theoretical examination, we aim to explore the challenges posed by the direct application of connectivity patterns from one graph to another. Our findings will reveal that such an approach may lead to negative transfer (Wang et al. 2021a). emphasizing the critical need for adaptable strategies in the face of graph diversity.
2.1 Empirical evaluation on transferability
Our exploration begins with an empirical investigation aimed at understanding the transferability of learned connectivity patterns across diverse graph domains. We curate collection of real-world graphs from varied fields in Table 1 ensuring comprehensive illustrations of different graph types.
To assess the potential of the important connectivity pattern, learned from one graph, to influence the LP performance on another, we incorporate extra graphs into the training phase of the target graph. In other words, this experiment deviates from the standard supervised learning approach by introducing additional training signals from other graphs. If the connectivity patterns from these extra graphs align with or augment the structure of the target graph, the LP model's performance should either remain stable or improve. To
3

---

Published in Transactions on Machine Learning Research (06/2025)
make the experiment tractable, only introduuee one additional graph into the training graph and then make link prediction the target graph. This additional graph is kept. disconnected from the target graph to ensure that the test set remains the same as standard LP tasks. In these experiments, we employ SEAL (Zhang & Chen 2018) as the backbone model for the experiment and adopt Hits@50 as the
performance metrics {Hu et al. 2021
10.0
C.ele
USAir
*
*
*
Additional graph
5.0
PB
*
2.5
NS
*
0.0
CS
-255
Cora
-5.0
Facebook
-7.5
*
10000
C.ele
USAir
PB
NS
CS
Cora
Facebook
Target graph
Figure Performance change of SEAL Zhang & Chen 2018 after training with one additional graph.
denotes statistically significant change.
Results are presented in Figure [ It shows how the LP model's performance is affected by the rotruuctt of additional graph data during training. the heatmap, warm colors represent an improvement in LP performance, while cooler colors denote a performance decrease. The predominance of cooler colors in the healmap reveals that integrating extra graph into training generally results in performance degradation. This observation underscores the potential discordance in the underlying characteristies of different graphs, leading to conflicts between the learned connectivity patterns This phenomenon highlights the inherent challenge in deploying a singular LP model across varions graphs, thus questioning the feasibility of a "one model fits all" approach in the context of LP tasks.
2.2 Conflicting patterns across graphs
In this section, we delve into the theoretical aspects of how the unique characteristics of different graphs can hinder the transfcrability of connectivity patterns. We begin with a formal definition and preliminary discussion of LP.
Preliminary. Consider an undirected graph G (V,E". is the of nodes with size n, which can be indexed as (i) E denotes the observed set of links, which is subset E E* of the complete set of true links Ex CVV X. Here, E encompasses not only the observed links but also potential links that are currently absent may form in the future within the graph G. For any node u E V, (v)) (ul(u, v) E*} denotes the neighbors of node v. The set of k-hop simple paths from node u to v is denoted as T,( v) = {(v1, v2,..., u1) = u, = e and (v,, 1141) E E for E (1....,k kk 1}}. Note that paths only contain distinct nodes. We denote the shortest-path. between a node pair (u, v) as (P(u,
The objective LP tasks to identify the set of unobserved true links E C EE within given graph G. This task diverges from typical binary classification problems, the potential candidates for E

---

Published in Transactions on Machine Learning Research (06/2025)
?
(b)
Figure 2: Two synthetic graphs with different connectivity patterns: (a) Grid lattice graph; (b) Triangular lattice graph.
predetermined: they consist of all node pairs not already included in the observed links V x V\E.. In practical terms, "identifying" E" equates to ranking these unobserved true links higher than false links based their link features Yang et al. 2015 Hu et al. 2021 This ranking process is defined by what we term connectivity patterns
Definition 2.1. Connectivity pattern is an ordered sequence of events w [A1, A2,.... such that p(y 1|A,) 2 pyy 1[A,) for any <.j.
Here, an event A refers to a specific set of conditions met by the link features of a node pair. In LP tasks, connectivity patterns may be determined by human experts using heuristic methods or by training parametric link predictors. For example, in social networks, simple connectivity pattern might be w (CN(u, u) 2 1, (,, v) = 0j, suggesting that pairs of users with common friends are more likely to connect than those without any.
The ability to transfer a connectivity pattern from one graph to another suggests the potential for LP models to be applicable to new, previously unseen graphs. However, a mismatch in the ranking of connectivity patterns between the training and target graphs could lead to inaccuracies, since the model can assign higher scores unlikely links and lower scores to likely ones.
Next, we demonstrate that even structurally similar synthetic graphs can exhibit. different connectivity patterns. We begin by considering two types of lattice graphs: Grid graph, similar to chessboard, where nodes are evenly spaced on 2D grid, each connected to its four nearest neighbors; and Triangular graph, derived from the Grid by adding one diagonal edge within each square unit. Despite their structural similarities, these graphs, Grid and Triangular, display divergent connectivity patterns:
Theorem 2.2. Define A ( 2 1 and As [T, w) 1 as elements of w. The connectivity patterns on Grid and Triangular graphs are distinct. Specifieally: (i) On Grid: w = [A3, A2]; (ii) On Triangular: w = [A2,
The proof is in Appendix C.2 In essence, in Triangular graphs, node pairs two hops away more likely to form a link compared to those three hops away. Conversely, in Grid graphs, despite their structural similarity to Triangular graphs, node pairs two hops away have no likelihood of linking.
This observation of conflicting connectivity patlerns across similar graphs underlines the challenges in knowl- edge transfer for LP tasks. Even slight structural variations in graphs can significantly alter the likelihood of link formation between nodes. Consequently, the task of developing universal link predictor, capable of adapting any graph without specific tuning for its connectivity pattern, is non-trivial endeavor.
We have an in-depth analysis how connectivity patterns differ from relate graph distributions Appendix C.1 where illustatte that graphs with different underlying distribution could have the shared connectivity pattern.
5

---

Published in Transactions on Machine Learning Research (06/2025)
Attention Layer
GNN
q
si
82
$1
22
(b)
Figure 3: Overview of the UniLP framework. (a) For predicting a query link q. we initially sample positive (st) and negative (s") in-context links from the target graph. (b) Both the query link and these in-context links are independently processed through shared subgraph GNN encoder. An attention mechanism then calculates scores based on the similarity between the query link and the in-contexi links. The final repre- sentation of the query link, contextualized by the target graph, is obtained through a weighted summation, which combines the representations of the in-context links with their respective labels.
2.3 Contextualizing Link Prediction
The challenge of conflicting connectivity palterns across different graphs highlights a critical issue: a model trained on one graph may break down when applied another without accommodating the unique charac- tcristics of the target graph. To mitigate this, we suggest paradigm where the model dynamically adapts to the target graph by taking into account its specific characteristics.
This adjustment process involves conditioning the model on the target graph's properties, thereby ensuring that the prediction of link formation, p(1 [)), is influenced not just by the inherent link features but also by the properties of the target graph. We draw inspiration from the concept In-context Learning (ICL) in LLMs (Dai et al., 2022), which enables LLMs to solve tasks with a few demonstration examples. We propose the incorporation of the target graph as contextual element in the link prediction p(1[A, By doing so, the model learns to understand the joint distribution of link features and the graph context, allowing it to adapt to different graphs. In the subsequent section, will delve into the practical implementation of an LP model equipped with ICL capabilitios.
3 Universal Link Predictor
This section outlines our proposed UniLP, designed for elfective application to unseen datasets. UniLP can readily adapt to the connectivity patterns of any new graphs, even though they are not seen during the training phase. UniLP operates by first sampling a set in-context links from the target graph, which are then independently encoded alongside the target link using a shared GNN encoder. An attention mechanism is employed to merge the representations of these in-context links in relation to their interaction with the target link, forming composite representation for the final prediction. The overall framework is in Figure 3
3.1 Query and in-context links
For a given target link g E V V in graph G, we define as the query link. To predict this link basod on the contextual information of G, we start by sampling set of in-contezt links from G. Specifically, we select l node pairs S+ C F positive examples, where S+ = (st s ...,stt ,..,. These pairs have existing

---

Published in Transactions on Machine Learning Research (06/2025)
links between them in G. Similarly, we gather negative examples S { .5..... s V V comprising & node pairs without a link. The combined set 5 UST approximates the overall properties of G and provides a context e for the model to perform LP (p(1[A, c)) using both link features and graph context.
Once we get the query link and the in-context links, we need to obtain the structural representation for them. We start by extracting the ego-subgraph for each of them. An ego-subgraph G((u, v), r, G) for node pair (u, v) is a subgraph induced by all the r-hop neighboring nodes of the nodes u and v on the graph G:
G((u, r) = (Ve,
where V, = (i|SP(i, u) < or SP(i, S r and F, = {(i,5) E F E V.). For simplicity, we denote such an ego-subgraph as G(e) for the node pair e = (u,v) v) when there is no ambiguity. The ego-subgraphs for the query link and the in-context links are (G(e)le E {a) Us+ US-}. US+US-)
Utilizing ego-subgraphs to represent links offers several key advantages over using either individual node pairs or the entire graph. Firstly, an ego-subgraph provides a richer structural context than a mere node pair, encapsulating the local neighborhood structure around the link in question. This approach allows for more detailed and informative representation of the link's local structures. Secondly, ego-subgraphs serve as an effective and computationally efficient approximation of global link features (Zhang & Chen 2018). This is advantageous over the pnoource-intesivee process of encoding the entire graph. Lastly, representations at the subgraph level are inherently more expressive compared to node-level representations (Frasca et al., 2022). This enhanced expressiveness is crucial for capturing the structures of links and performing accurate LPs.
3.2 Encoding sgo-subgsaphs
The ego-subgraphs within the set (G(e)le E (1) US US-}} vary in size, requiring a uniform approach to representation. We employ GNNs to encode these subgraphs into a consistent latent space.
In the absence of node features in non-attributed graphs, typical GNNs (Kipf & Welling, 2017 Hamilton et al. 2018: Xu et al. 2018) require initial input vectors for each node. Common methods like assigning identical or random vectors meet this requirement but lack expressiveness about graph structures (Li et al,
2020 Zhang al., 2021). To address this, we utilize the labeling trick technique, assigning each node in Ge)) positional encoding based on its relative position to the target link (u, v). A proper design of labeling trick can ensure that GNNs are expressive enough to capture the heuristic graph substructures, like Common Neighbor and Shortest Path.
We propose DRNL+, which extends the labeling tricks applied in Double Radius Node Labeling (DRNL) ŞZhang & Chen 2018) and Distance Encoding (DE) (Li et al., (020). In DRNL, nodes i in G(e) are assigned integer labels as follows:
DRNL(i, (u, o)) =1 min(d,, d.) + (d/2)((d/2) + (d%2) - 1].
where d,, :- SP w), d, == SP v), and d =- du + dp. However, DRNL doesn't 't distinguish nodes reachable to only one of the target nodes. Thus, DRNL+ enhances this by using DE to assign tuple of integers:
d0,d)),
if d, 0o
Di (u), =
if d, = do (DRNL(i, u)). 0), otherwise
(0, do);
(1)
After the labeling trick indicates relative positions, we apply the SAGE (Hamilton et al. 2018 with mean aggregation to update node representations (Zeng et al. 2022). The final subgraph representation, he E F for each link e e Us+ US= , is derived by average pooling the representations of all nodes in G(e). We find that mean aggregation and pooling work best for such a universal link predictor, hypothesizing that this approach better accommodates varying graph sizes and node degrees, thereby enhancing model generalizability.

---

Published in Transactions on Machine Learning Research (06/2025)
3.3 Link prediction with context
Once the ego-subgraphs are encoded into latent space, utilize these representations (hale E {u)US+US-} to parameterize our link predictor p(][A,c) c) via an attention mechanism (Vaswani et al. 2017).
The attention scores a between the query link representation hg and cach in-context link representation h2 for E SES+US. UST are calculated using additive attention (Niu et al. 2021 Brody el al. 2022):
0gs = Lea'LeayReLU (W& [b,))
(2)
where p F is learnable vector and W E RF x2F is projection matrix. The concatenation operation is denoted by ||. The normalized attention scores a are obtained as follows:
(as(
0₂ softmax (ax) Emest Us- exp (ae)
(3)
We denote the attention score between the query link and positive in-context link st E S+ as at, and with a negative in-context link as a- Like in Transformer and GAT models (Veličković et al. 2018 Brody et al, 2022,, multi-head attention can also be employed to capture diverse interactions between graph structures.
Remark. The attention scores are pivotal for shaping the query link's representation in the context of the target graph. We intentionally exclude label information from the attention score computation to avoid biasing the model towards easy predictions during training. This approach aligns with "unsupervised" learning strategy, as opposed to "supervised" one, where label information might lead the model to rely excessively on seen patterns, thus turning the attention mechanism into a de facto classifier. This could hinder the model's ability to generalize and adapt. across varying graph structures, increasing the risk of overfitting to specific connectivity patterns not applicable to new, unseen graphs. Our empirical findings support this methodology, demonstrating that keeping the attention computation label-free significantly boosts the model's generalizability.
After the normalized attention scores determined, compute the final reprosentation for the query link This is achieved by applying weighted sum to the representations of the in-context links, using the attention scores as weights. Additionally, we integrate label information into the in-context links' rep- resentations by adding corresponding learnable vectors. Formally, the final representation calculated as follows:
W, h = --EEss a W. (he, +1+)+ + E a2 W, (1,+
(4)
where ,+, E F are learnable vectors for labels, and W. E RF'F a value projection matrix. The representation hy encapsulates both the link features of the query link q and an estimation of the target graph G, and is then input into an MLP classifier to produce the link prediction result:
p(][A,c) = (MLP (h₂)),
(5)
where a (-) denotes sigmoid function.
3.4 Pretraining objective
The pretraining objective for UniLP focuses predicting the query link q based on its features and the context of the graph it is part of. We align this objective with standard binary classification seen in typical parametric link prediction algorithms Zhang & Chen 2018 Chamberlain et al. 2022 Dong et al. 2023). In this setting, the classification label He for an edge is set to 1 if e is among the observed links ES; otherwise, Be is Additionally, we consider a set of pretrain graphs G, with each graph G being a member of this set. The overall pretraining loss is then defined as:
L = EGeg. v (MLP (he) We).
(6)
This loss function is employed across multiple graphs, allowing UniLP learn a generalizable pattern for link prediction across various graph structures.
8

---

Published in Transactions on Machine Learning Research (06/2025)
4 Related work
Link prediction. Traditional LP methods are handcrafted hcuristics designed by obscrving the connectiv-
ity pattern in real-world data. They leverage either the link's local (Liben-Nowell & Kleinberg, 2003 Adamic
& Adar 2003 Zhou et al., 2009 Barabási & Albert 1999) or global information (Katz 1953 Page et al.
1999) to infer the missing links in the graph. OLP (Ghasemian et al. (0200) stacks the houristics link predic- tors as a feature vector and fits a random forest as the classifier. WLNM (Zhang & Chen 2017) is one of the pioneers in training neural network a link predictor. GAE Kiip & Welling 2016), as the first GNN4LP, utilizes GNNs to encode the graph structure into node representation and perform the link prediction task. SEAL (Zhang & Chen 2018; Zhang et al., 2021) points out that a link-level reprosentation is necessary for a successful LP method and proposes the labeling trick to enable GNNs to learn the joint structural representation. GralT. (Teru et al. 2020j extends the idea of the node labeling trick (Zhang et al., 2021) of SEAL to the knowledge graph completion tasks. NBFNet (Zhu et al. 2021 proposes a general framework for performing link prediction based on learnable paths. ELPH (Chamberlain et al.) (2022). NCNC (Wang eet al. 2023b), and MPL.P (Dong et al., 2023) further improve the scalability of GNN4LP and achieve the Slate-of-the-arte various graph benchmarks. On heterogeneous graphs, SLiCE (Wang et al. 2021b) adopts
pretrain-annd-lieetue strategy lo learn contextual node representations for link predictions. Daza et al.) (2021) studies how to perform inductive link prediction over knowledge graphs based on the textual data of nodes.
In-context Learning. The remarkable efficacy of LLMs across broad spectrum of language tasks is significantly attributed their adeptness in ICL (Brown et al. 2020). This capability allows LLMs generalize to new tasks by leveraging demonstration examples, effectively learning the required skills on the fly. Irie et al. (2022) delves into the equivalence between conventional model training and the application of attennionn mechanisms to training samples during inference, suggesting an underlying mechanism of ICL. Further exploration by Dai et al. (0022) posits that ICL facilitates an implicit optimization process guided by in-context examples. While the concept of ICL has been primarily associated with LLMs, Prodigy (Huang et al. 2023) represents an initial attempt to adapt ICL for GNN-based models. Their approach, however, is somewhat constrained by the overlap in pretrain and test datascts, which raises questions about the mothod's transferability across distinct graph domains.
5
Experiments
Tn this section, we conduct extensive experiments to assess the performance of UniLP new unseen datasets.
5.1 Experimental setup
Benchmark datasets. The foundation for our model's training collection of graph datasets spanning
variety of domains. Following (Mao et al. 2023)
have carefully selected graph data from fields
such as biology (Von Mering et al.; 2002 Zhang et al. 2018 Watts & Strogatz 1998). transport (Watts
& Strogatz, 1998 Batagelj & Mrvar 2006), web (Ackland & others 2005 Spring et al. 2002 Adamic &
Glance 2005), academia collaboration (Shchur et al.) 2019 Newnan 2006b), citation (Yang et al. 2016).
and social networks (Rozemberczki et al.) 2021). This diverse selection ensures that we can pretrain and evaluate the LP model based on wide array of connectivily patterns. The details of the curated graph datasets can be found in Table
Baseline Methods. We compare UniLP with both heuristic and GNN-based parametric link predictors.
Heuristic methods include Common Neighbor (CN) Nowell & Kleinberg) 2003), Adamic-Adee in-
dex (AA) (Adamic & Adar 2003), Resource Allocation (RA) (Zhou et al. 2009). Preferential Attachment
(PA) (Barabási & Alberi, 1999), Shortest-Path (SP), and Kalz index (Katz) (Katz 1953). GNN-based
methods include GAE (Kipf & Welling 2016), SEAL Zhang & Chen 2018 ELPH CChmberlain et al,, 2022), NCNC (Wang et al. (202b)), and MPLP (Dong al. (022).. For GAE and NCNC, which require initial node features, we use 32-dimensional all-one vector. All other methods can handle attrrbibb graphs directly.
9

---

Published in Transactions on Machine Learning Research (06/2025)
Table The pretrain datasets and test benchmarks.
Dataset Pretrain
Test
# Nodes
# Edges
Avg. node deg.
Std. node deg.
Max. node deg.
Density
Biology
Ecoli
1805
29320
16.24
48.38
1030
1.809%%
Yeast
2375
23386
9.85
15.5
118
0.82955
Celegans
4296
14.46
12.97
134
9.7734%
Transport
Power
4941
13188
2.67
1.79
19
0.108 1%
USAir
332
4252
12.81
20.13
139
7.7385%
Web
PolBlogs
1490
19025
12.77
20.73
256
1.7150%
Router
5022
12516
2.49
5.29
106
0.0993%
PB
1222
33428
27.36
38.42
351
4.4808%
Collaboration
Physics
34493
495924
14.38
15.57
382
0.0834%
CS
18333
163788
8.93
9.11
136
0.0975%
NS
1589
5484
3.45
3.47
34
0.4347%
Citation
Pubmed
19717
88648
4.5
7.43
171
0.0456%
Citesoer
2.74
3.38
0.1645%
Cora
2708
10556
3.9
5.23
168
0.2880%
Social
Twitch
34118
429113
12.58
35.88
1489
0.0737%
Github
37700
289003
7.67
46.59
6809
0.0407%
Facebook
22470
171002
7.61
15.26
472
0.0677%
Evaluation of UniLP To evaluate UniLP's effectiveness on unseen datasets, we divide our graph data into non-overlapping pretrain and testing sets (see Table [ and pretrain one single model on the combined pretrain datasets. During pretraining, we dynamically sample 40 positive and negative links as in-context links S US- for each query link from the corresponding pretrain datasct. For evaluation, each test dataset is split into 70% 22f/00%//200 /20 for aaaning/validatioon iitiiattioo/estingg. The training set here forms the observed links Fo, while validation and test sets represent unobserved links E". During the inference, positive and negative links as in-context links per test dataset. We report Hits@50 (Hu et al. 2021 as the evaluation metric for LP. More details about the pretraining of UniLP can be found in Appendix A.1
sample k 200
Evaluation of Baselines. Bascline models follow similar evaluation procedures, with adaptations for transfer learning capabilities. We employ two settings: (1) Pretrain Only, where models are trained combined pretrain datasets and then tested on each test dataset, and (2) Pretrain & Finetune, where after pretraining, models are additionally finetuned on each test dataset with 200 sampled positive and negative links for training.
5.2 Primary results
Table presents the performance of UniLP on various unscen graph datasets. The results demonstrate that UniLP outperforms both traditional heuristic methods and standard GNN-based LP models that are pre- trained without specific adaptation, showing significant improvements in 4 out of 7 the benchmark datasets. This performance enhancement suggests that tailoring the LP model to individual graphs can markedly increase its transfer learning capabilities.
Moreover, UniLP achieves comparable or even superior results to GNN-based LP models that undergo finetuning, despite not being explicitly trained on the test data. This highlights the effectiveness of the ICL capability in UniLP, which allows the model to adapt scamlessly specific graph datasets without the need for additional training. By leveraging in-context links provided during the inference phase, UniL.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Link prediction results on test datasets evaluated by Hits@50. The format average score standard deviation. The top three models are colored by First, Second, Third.
Table 2:
Biology C.ele
Transport
Web
Collaboration
Citation
Social Facebook
USAir
PB
NS
CS
Cora
Ave. Rank
Heuristics
CN
12.28
82. 1.57
11.377
14.03
56.84:15.58
33.8540.98
50..0.
11.00
AA
61.07 15.16
86. 86.96-2.2 24
44. 33.30
74.03=1.59
68 22.01.8
33.8510.93
07.80 12
5.71
R.A
62.80+4.84
87.27=1.6 1.89
43.72=2.86
74.03=1.68
68.21
33.85+0.93
68.84
5.57
PA
43.85
77.60
28.93
35.35
6.4910.61
1.332
12.95
13.71
SP
0.00=0.00
0.00++..00
0.00++0.00
80.00=1.11
41.31433..5
52.97+1.58
0.00:10.00
13.14
Katz
58.86
1.86
44.36
18.96
66.3215.50
52.97
60..900.60
6.86
Pretrain Ouly
SEAL
61.28 76
86.00
45.44
84.07
62.82.1168
56.2112.24
54.5711148
5.57
GAE
43.71
76.12
27.56-2.34
15.20=2.14
5.08800.8
21.22+1.53
6.65#20.57
14.14
ELPH
59. 4:550
84. 42.22
43.69
84.2711.43
70.6913.66
56.9111148
61.80.1.44
5,57
NCNC
48.07
25.2222
25.66=1.42
80.07=1.43
31.27+2.25
52.51
19.28=1.58
11.57
MPLP
56.74:5.31
12.94
47.78:2.55
80.33
24.26111.8
46.7112.25
48. 06.10.99
8,86
Pretrain & Finetune
SEAL
44.44
88.49 2
=7.78
84.84
61.54113.08
62.19
58. 70.2.78
3.14
GAE
44.71
74.97
25.92=2.64
18.34
4.95:20.44
25.31
6.11 (.111
14.71
ELPH
60.51 84.52:2..8
43.58
$6.0810.e0
71.1013.48
57.1811.9
63.3 13.31133.3
4.71
NCNC
64.45
85.85+2.46
17.75=6.90
88. 28.25
58.75+5.774
60.00=2
59.32+6693
3.71
MPLP
6..5614.79
85.08
48.01112.9
80. 30.1611.11
50.35:11.01
56.0212.09
56.72+1.20
6.14
Ours
UniLP
45.20:14.40
85.98
48 18.1442.999
89.0912.05
64.5912.65
57.50 4. 65.4912.00
1.86
dynamically adjust its knowledge of conncctivity patterns, demonstrating its potential to deliver robust performance across wide range of unseen graph datasets. In addition, the experimental results on the synthetic Triangular/Grid lattice graphs can be found in Table in the Appendix.
5.3 The inner mechanism of UniLP
Link prediction results on test datasets evaluated by Hits@50 under context perturbation. This table presents the outcomes of link prediction when the context, ie.. in-context links, is deliberately altered. The aim is to analyze how changes in the context inffuence the final prediction accuracy.
Table 3:
Biology
Transport
Web
Collaboration
Citation
Social
C.ele
USAir
PB
NS
CS
Cora
Facebook
UniLP-FlipLabel
0.61
15,81:13.11
0.03=0.03
27.97=4.29
0.60
2.03+0.55
0.32+0.15
52.89
81.91
47.17=3.05
85.60+1.23
47. 20.44
37.62 07.6245.64
22. 22.1746.63
UniLP
65.20=4.40
85.9842.00
48.14
89.09=2.05
64.59
57.50=2.40
65.4942.05
We further explore the capability of our proposed model's ICL facilitate skill learning (Pan al. 2023 Mao
et al. 2024), enabling the model to acquire new skills not encountered during the pretraining phase, guided ICL demonstrations, This investigation focuses the model's performance sensitivity to corrupting in- context links, particularly when those links are presented with incorrect input-label associations. Given that each in-context link consists of an input and its corresponding label, we introduce two perturbation stralegies to assess this sensitivity: FlipLabel: we invert the labels of the in-context links, labeling previously positive links as negative and vice versa. RandomContext Instcad of selecting in-context links from the target graph, we randomly sample them from a graph generated using the Stochastic Block Model (Holland al. 1983)
11

---

Published in Transactions on Machine Learning Research (06/2025)
The outcomes, as shown in Table B reveal that flipping the labels of in-context links significantly degrades the model's performance, rendering it almost ineffective. This finding underscores the model's utilization of ICL for skill learning, specifically in learning new feature-label mappings within a given context (Wei et al. 2023 Min et al., 2022). It highlights the pivotal role of accurate label information in in-context links for the model's I's effective adaptation to the largel graph.
Furthermore, using randomly generated graphs as a source of in-context links also detrimentally affects performance, albeit to varying extents across different datasets. This implics the importance of choosing in-context links that genuinely represent the properties of the target graph. Interestingly the less severe performance decline in some datasets may indicate their inherent community-based graph structures.
Ceel
PB
NS
CS
Facebook
50
90
60
45
60
60
Hits@000
50
35
40
40
30
40
UniP
UniP
25
F7
F7
FT
20
SUP
SUP
SUP
SUP
30
Full
Ful
Full
20
Full
100
200
100
100
400
100
400
300
400
Training Samples
Training Samples
Training Samples
Training Samples
Training Samples
Figure 4: Performance of UniLP with varying quantities of in-context links.
5.4 Effectiveness of in-context links' size
This experiment evaluates how varying the quantity of in-context links affects UniLPPss performance during inference. We experiment with different numbers of in-context links, ranging from 10 to 400, sampled from each test graph. These links are used as context for the model. Additionally, we utilize SEAL the base model and assess its performance under finetuning (FT) and supervised training (SUP) from scratch with varying training sample sizes. For comparison, we also include results from training a SEAL model on the full set of larget graph data (Full), as detailed in Figure
The findings reveal a consistent improvement
UniLP's performance with an increasing number of in- context links. This indicates that our method can more effectively capture the target graph's propertics with additional context. Notably, on four of the lest datasets, UniLP either matches or exceeds the performance of models trained end-to-end be advantageous for LP tasks when properly managed. Furthermore, despite both UniLP and the finetuned models being pretrained on the same datasets and using the same in-context links, UniLP can outperform its finetuned counterparts. This observation suggests that in some cases, utilizing ICL, can be a more effective approach for adapting a pretrained model to a specific target dataset compared to finetuning The trend on the rest of graphs can be found in Figure in Appendix.
the entire graph. This suggests that leveraging more pretraining data
5.5 Visualization of the link representation
We conduct a comparative visualization of link representations learned by a Pretrained Only SEAL model and UniLP. This comparison is shown in Figure 5 The results indicate that naively pretrained model tends to map link representations from various graph datasets into close subspace, potentially leading to indistinguishable link representations across different graphs, even when these graphs exhibit conflicting connectivity patterns.
In contrast, the link representations generated by UniLP, which are conditionod on the context of the target graph, demonstrate a distinct separation between different datasets. This separation indicative of UniLP's effective ICT. capability, which adeptly captures the subtle distributional differences across graphs. By
12

---

Published in Transactions on Machine Learning Research (06/2025)
Pretrain Only
UniLP
(a)
(b)
Figure 5: Visualization of the link representation learned from (a) Pretrain Only SEAL; (b) UniLP. Different
colors indicate different test datasets.
100
80
H0
60
Hits@50
60
40
40
20
Facebook
USAir
TRIANGULAR
C.ele
USAir
PB
NS
Cora
Cora
GRID
0.0
0.2
0.4
0.6
0.8
1.0
Dataset
Pos Label Ratio
(a)
(b)
Figure 6: (a) Impact of Diverse In-Context Link Sets on LP Performance. This figure evaluates the variability in UniLP's performance across different sets of in-context links sampled. (b) Influence of posilive-to-negative in-context link ratios LP performance. The x-axis shows the ratio of positive negative in-context links. A value of 0 indicates that all in-context links negative, while value of indicates that all in-context links are positive.
adjusting the link representations based on the context provided by in-context links, UniLP effectively address the challenge of conflicting connectivity patterns in diverse graph datascts.
5.6 Diversifying context
In our prior analysis, we utilized a fixed set of in-context links sampled from each target graph serve the context. This section delves into the impact of varying these in-context links by employing different
13

---

Published in Transactions on Machine Learning Research (06/2025)
random seeds, aiming to discern the sensitivity of UniLP's performance to the specific selection of in-context links for each target graph. The outcomes of this investigation are shown in Figure 6a
For the Ceele, USAir and PB datasets, the selection of in-context links has a minimal effect on UniLP's performance. However, for the NS and Cora datasets, the choice of in-context links significantly influences performance. The findings reveal that the selection of in-context links indeed affects UniLP's performance across the test datasets to varying extents, highlighting the importance of the selection process for these contextual links in optimizing the model's efficacy. This echoes the findings in the NLP domain, where large language models sensitive to the selection of in-context demonstrations (Zhao et al. 2021 The study on the selection of the in-context links can be an interesting future work.
5.7 Varying positive-to-negatiee ratios of in-context links
In our previous exploration of LP performance, we initially maintain balanced set of positive and negative in-context links for each query link during both pretraining and testing phases. This study delves into the effects of changeing the ratio of positive to negative in-context links, while keeping the total count constant at 200, to assess the impact on IP accuracy. The findings, shown in Figure 6b. reveal several noteworthy observations.
Remarkably, for the majority of graph datasets examined, increasing the proportion of negative sam- Mles-contrayy to intuitive expectations- does not detract from performance and, in some cases, matches the efficacy of a balanced distribution of in-context links. This phenomenon indicates that negative sam- ples are more informative positive ones for leveraging the ICL capabilities of UniLP. Specifically, in the case of the synthetic Grid graph, a higher ratio of negative samples significantly enhances LP performance, given a fixed total number of in-context links. This improvement may stem from the symmetry of positive link structures within the Grid graph, which exhibit a consistent connectivity pattern. The introduction of a greater variely of negative samples seems to enrich the model's learning context, effectively harnessing UniLP's ICL potential to capture more diverse disconnectivity patterns.
An exception to this trend is observed with the Facebook graph dataset, where balance between positive and negative in-context links yields the most favorable outcomes. This suggests that for certain graph types, a balanced approach to in-context link selection optimizes LP performance.
6 Conclusion
In this paper, we introduce the Universal Link Predictor, a novel approach designed to be immediately ap- plicable to any non-attributed graph dataset without the necessity of training or finetuning. Recognizing the issue of conflicting connectivity patterns among diverse graph datasets, we innovatively employ ICL to dy- namically adjust link representations according to the specific properties of the target graph by conditioning on support links as contextual input. Through extensive experimental evaluations, we have demonstrated the effectiveness of our method. Notably, our Universal Link Predictor excels in its ability to adapt seam- lessly to new, unseen graphs, surpassing traditional models that require explicit training. This significant advancement presents promising direction for future research and applications in the field of LP.
Limitations Universal Link Predictor achieves strong link prediction performance unseen graphs with- out training. However, it has two main limitations. First, it operates only on non-attributed graphs, leverag- ing graph structure but ignoring node features. While prior studies reveal that graph structural signals often dominate in the link prediction task, incorporating node attributes can further improve performance. Sec- ond, the method depends on SEAL as the structural encoder, which requires costly subgraph extraction and limits scalability. Although SEAL's latent representations are effective for in-context learning, integrating more efficient structural encoders is a promising direction for future work.
14

---

Published in Transactions on Machine Learning Research (06/2025)
7 Acknowledgements
We would like to thank the anonymous reviewers for their insightful comments and helpful discussions. This work was supported in part by the National Science Foundation, Grant ITE- 2333393.
References
Robert Ackland and others. Mapping the US political blogosphere: Are conservative bloggers more promi- nent? In Blog Downander 2005 Conference, Sydney, 2005.
Lada A. Adamic and Eytan Adar. Friends and neighbors on the Web. Social Networks, 25(3):211- URL https: htpps:///www
230, 2003. ISSN 0378-8733. doi: http:///doooorr///..ooo///////// sciencedirect. com
Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 U.S. election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, LinkKDD '05, pp. 36-43, New York, NY, USA, August 2005. Association for Computing Machinery. ISBN 978-1-59593-21544 10. 10.1145/134271.1112277 URL https://dl acm. ort/ 114..011111111111111111 1134277
doi:
Albert-László Barabási and Réka Albert. Emergence of Scaling in Random Networks. Science, (5439): 509-512, 1999. doi: 10.1126/scienen cccencc.286.5433..65 URL https::/www/ www.:ccccenccccccccc http:///....g/////////////////// 1126/ science 286. 5439.54995000
eprint: https:/ http::/wwwwaateeeeec////////////
Vladimir Batagelj and Andrej Mrvar. Pajek datasets website, 2006. URL http::/vlado.frr fmf uni -iji-lj... lij.ii/ pub/networks/dataa
si/
James Betker, Gabriel Goh, Li Jing, Tim Brooks, Jianfeng Wang, Linjie Li, Long Ouyang, Juntang Zhuang, Joyce Lee, Yufei Guo, Wesam Manassra, Prafulla Dhariwal, Casey Chu, Yunxin Jiao, and Aditya Ramesh. Improving Image Generation with Better Captions. URL sttp:::/app..seennicccccoo.... semanticscholar /rrgg/
SarpusID:244403224
Shaked Brody, Uri Alon, and Eran Yahav. How Attentive are Graph Attention Networks?, Jamuary 2022.
URL http://arxiv. org/abs/ 2200 14491. arXiv:2105.14491 [os].
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krucger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners, July 2020. URL http://arxiv. org hwtgg/bbs/0005... 14165 arXiv:2005.1416: [cs].
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph Neural Networks for Link Prediction with Subgraph Sketching. September 2022. URL https::/opennevvie: http://penrerieeeeeee//rrrrrrra net.formnfid mloqEDAoZQU
Damai Dai, Yutao Sun, Li Dong, Yarn Hao, Shuming Ma, Zhifang Sui, and Furu Wei. Why Can GPT Learn In-Context? Language Models Implicitly Perform Gradient Descent as Mela-Optimiiers, December 2022.
URL https://arxiv.org/aba http://bb/22...111mm/mg 10559v3.
Daniel Daza, Michael Cochez, and Paul Groth. Inductive Entity Representations from Text via Link Predic- tion. In Proceedings of the Web Conference 2021, pp. 798 808, April 2021. doi: 10.1145/3442381.34555 34500141. URL
03496 arXiv:2010.03496 [es].
Jeff Donahuc, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. DeCAF: A Deep Convolutional Activation Feature for Generic Visual Recognition. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the S1st International Conference Machine Learning, volume 32
15

---

Published in Transactions on Machine Learning Research (06/2025)
of Proceedings of Machine Learning Research, pp. 647-655, Bejing, China, June 2014. PMLR. https://proocedding wwwpiiinnss.......eeee
URL
html Issue: 1.
Kaiwen Dong, Yijun Tian, Zhichun Guo, Yang Yang, and Nitesh Chawla. FakeEdge: Alleviate Dataset Shift in Link Prediction. Decomber 2022. URL htttss://openreviekk http://ew...ee.oooooooooooooooo.
Kaiwen Dong, Zhichun Guo, and Nitesh V. Chawla, Pure Message Passing Can Estimate Common Neighbor for Link Prediction, October 2023. URL http://arxiv http://xxii..oor/aaaaa aataaaaas/// 00976 arXiv:2309.0097 [cs].
David Easley, Jon Kleinberg, and others. Nelworks, crowds, and markels: Reasoning aboul. a highly connected world, volume 1. Cambridge university press Cambridge, 2010.
Matthias Fey and Jan E. Lenssen. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and Extend- ing Subgraph GNNs by Rethinking Their Symmetries, June 2022. URL http:://axxivoorgaaat /2066 11140 arXiv:2206.1111 [cs].
Amir Ghasemian, Homa Hosscinmardi, Aram Galstyan, Edoardo M. Airoldi, and Aaron Clausct. Stacking models for nearly optimal link prediction in complex networks. Proceedings of the National Academy of Sciences, 117(38))233933 23400230003330000000 2020. doi: 10.1073/pmas.191145501 URL httpps///ww pnas org/doi/
1914950117
eprint: https:/ https://www.pnas.ot
wwtpp//...73/paaa....oooo 199.1077//paa..11499500000 1914950117.
Zhichun Guo, William Shiao, Shichang Zhang, Yozen Liu, Nitesh Chawla, Ncil Shah, and Tong Zhao. Linkless
Link Prediction via Relational Distillation. arxiv preprinl urXiv:2210.058/ 2022.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning on Large Graphs. 1rXiw:1706.022) fes, statj, September 2018. URL 1706.02216.
02216 arXiv:
Paul Holland, Kathryn B. Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Nelworks, 5:109- 137, 1983. URL /httt::////ppp wwmanticscoolartttt htttss//app.eemaniccccholaaa Drt.hooooarrrg//oousssttt.s 340998455
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv:2005.000: 006677 [es, stat], February 2021. URL
arXiv: 2005.00687.
Qian Huang, Hongyu Ren, Peng Chen, Gregor Krämanc, Daniel Zeng, Percy Liang, and Jure Leskovec. PRODIGY: Enabling In-context Learning Over Graphs. November 2023. URL https://openrevier:
hes/forum?id=pLwWWlle
Kazuki Irie, Róbert Csordás, and Jürgen Schmidhuber. The Dual Form of Neural Networks Revisited: Connecting Test Time Predictions to Training Patterns via Spotlights of Attention, June 2022. URL
http://arxiv.org/. abs///b//222 /tlps//2222000 05798 arXiv:2202.05798 [cs).
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39 43, March 1953. ISSN 1860-0980. doi: B41007/BF0229000 URL httpps://aai..rrr/00100////////
Thomas N. Kipf and Max Welling, Variational Graph Auto-Encoders,, 2016. eprint: 1611.07308.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works. arxiv: 0609002900 [es, stat], February 2017. URL 1609.02907.
02907 arXiv:
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloc Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan Yen Lo, Piotr Dollár, and Ross Girshick. Segment Anything, April 2023. URL http://arii..orraaa///.....00 02643 arXiv:2304.02643 [es].
16

---

Published in Transactions on Machine Learning Research (06/2025)
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-33) 37, 2009. Publisher: IEFE.
Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas. Link prediction tech- niques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applica- hions, 553:124289, September 2020. ISSN 0378-4371. doi: 10.1016/j.physa.200 202. 124289. URL https:
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 4465-4478 Curran Associates, Inc., 2020. URL http://ppooeennggsooorrrsccccppp pdf
David Tiben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, CIKM '03, pp. 556 559, New York, NY, USA, November 2003. Association for Computing Machinery. ISBN 978-1-58113-723-1. doi: 10. 05555/56663.5555
URL http:::/lo..rrg/1001444//4/0/0/0 1tt..1115/95666..00 956972
Haitao Mao, Juanhui Li, Harry Shomer, Bingheng Li, Wenqi Fan, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Revisiting Link Prediction: A Data Perspective, October 2023. URL http://arxiv.orz org/
abs/2310.000 00793 arXiv:2310.00793 [cs].
Haitao Mao, Guangliang Liu, Yao Ma, Rongrong Wang, and Jiliang Tang. A Data Generation Perspective the Mechanism of In- nn-Conexxt Learning, February 2024. URL
arXiv:2402.02213 [cs).
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannanch Hajishirzi, and Luke Zettle- moyer. Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?, October 2022. [cs].
URL http://arxiv http://xxxxiorggabbb////a/aaa wrgg/bs/////// 2202. 12837 arXiv:2202.1283 12833
M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, (03(23):8577-8588) 2006a. doi:
URL httpps///ww. pnas. org/doi/ eprint: https://wwwpppsss.tt hwtp:/ppaa..ooooooo////oooo /ttp:///
0bbs/0..003/pmas..o00 0601660103
Mark EJ Newman. Finding community structure in networks using the cigenvectors of matricos. Physical review E, 74(3):036104, 2006b. Publisher: APS.
Zhaoyang Niu, Guoqiang Zhong, and Hui Yu. A review on the attention mechanism of deep learning. Newrocompuling, 452:48- 62, September 2021. ISSN 0925-2312. doi: 10. n0.10166j..euccmm.202 20..000.1..00..... URL
com/ htt.://cw...........oo......aaaa
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank Citation Ranking Bringing Order to the Web. In The Web Conference, 1999. URL https://apl semanticscoolar. oorg
(o:10s3D:15085033
Jane Pan, Tianyu Gao, Howard Chen, and Danqi Chen. What In- Learning 'Learns' In- Context: Disentangling Task Recognition and Task Learning, May 2023. URT. httt:tttt///axiv.coo 2305. /355 09731
arXiv:2305.0973 [cs].
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Jour- nal of Complez Networks, enabb44, May 2021. ISSN 2051-1329. doi: 10.1093 htt/////cmmee//ab/leee URL https:://at..ooreeeeeeeee 1003///mmet//cabb//00 http:///caaa011//0444441///000/0
eprint: httpe://baaeeeiiccop..ommmmmommp
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph
Neural Network Evaluation, June 2019. URL stat].
01888 arXiv:1811.055 11.10566888111111111 [cs,
17

---

Published in Transactions on Machine Learning Research (06/2025)
Neil Spring, Ratul Mahajan, and David Wetherall. Measuring ISP topologies with Rocketfuel. ACM SIG- COMM Computer Communicatioo Review, 22(4):133-1455 2002. Publisher: ACM New York, NY, USA.
Damian Szklarezyk, Annika L. Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta-Cepas, Milan Simonovic, Nadezhda T. Doncheva, John H. Morris, Peer Bork, Lars J. Jensen, and Christian von Mering. STRING vl1: protein-protein association networks with increased coverage, supporting functional discovery in genome-wiee wide experimental datasets. Nucleic Acids Research, 47(D1))D607-DD) DD113, January 2019. ISSN 1362-4962. doi: 10.1093/nar /aa//aal///g//
Komal K. Teru, Etienne G. Denis, and William L. Hamilton. Inductive relation prodiction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of ICML 20, pp. 9448 9457. JMLR.org, July 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Newral Informalion Processing Sys- tems, volume 30. Curran Associates, Inc., 2017. URL https://paaerr.utss..//ppppppppp ptppcc//p/ppaaee//////aaaaal B55a2246444a31110500c444444 Abst:aataaaabtttttt...a.a
nips.
Petar Veličković, Guillom Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. arxiv: 1710.10003 fcs, stat), February 2018. URL
1710. 10903
arXiv: 1710.10903.
Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stanley Fields, and Peer Bork. Comparative assessment of large-scale data sets of protein protein interactions. Nature, 417 (6887):399-44)) 403, 2002. Publisher: Nature Publishing Group.
Lean Wang, Lei Li, Damai Dai, Deli Chen, Hao Zhou, Fandong Meng, Jie Zhou, and Xu Sun. Label Words are Anchors: An Information Flow Perspective for Understanding In-Context Learning, December 2023a.
URL http://arxiv org/ arg/abs/2305. 2305. 14160 arXiv:2305.14161 [cs].
Liyuan Wang, Mingtian Zhang, Zhongfan Jia, Qian Li, Chenglong Bao, Kaisheng Ma, Jun Zhu, and Yi Zhong. AFEC: Active Forgetting of Negative Transfer in Continual Learning, November 2021a. URL
http://arxil: http//aww....rrab//aaaaaa abggabs//110//000 12187 MxXiv:2110.21182 [cs].
Ping Wang, Khushbu Agarwal, Colby Ham, Sutanay Choudhury, and Chandan K. Reddy. Supervipe Tearning of Contextual Fmbeddings for Link Prediction Heterogeneous Networks, March 2021b. URL www//b///////aoooooo/oooeee aaaaaaaa/2000 11192 arXiv:2007.11192 [cs].
http://arxiv. org/
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural Common Neighbor with Completion for Link Prediction, February 2023b. URL http::/tt.tt...o// hangg//ba//aan abtpab///./0000030/23
ar arXiv:2302.00690 [es].
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'sold networks Nature, 393: 440 442, 1998. URL https://api semanticscholar. http://o.......rrooruuusss/.....
Jerry Wei, Jason Wei, Yi Tay, Dustin Tran, Albert Webson, Yifeng Lu, Xinyun Chen, Hanxiao Liu, Da Huang, Denny Zhou, and Tengyu Ma. Larger language models do in-context learning differently, March 2023. URL SURLhttp::///
arXiv:2303.083: 038446 [es].
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? CoRR, abs/18 abs/1810.00826, 2018. URL http::://axxv.orgg/// http://as/1110..0000 00826 arXiv: 1810.00826.
Yang Yang, Ryan N. Lichtenwalter, and Nitesh V. Chawla. Evaluating link prediction methods. Knowl- edge and Information Systems, 45(3):751-782, December 2015. ISSN 0219-3116. doi: 10.1007/
s10115-014-0789-00 URL http::///aa.aoo///0.0000///055s
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp- 40-48. PMLR, 2016.
18

---

Published in Transactions on Machine Learning Research (06/2025)
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Proceedings of the 27th International Conference Newral Information Processing Systems Volume 2, NIPS14, pp. 3320 3328, Cambridge, MA, USA, December 2014. MIT Press.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Raigopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the Depth and Scope of Graph Neural Networks, January 2022. URL http:// /ttp:///axxivv/ wttp://orgg/bbbaaaaeeaeee 07858 arXiv:2201008558 [cs].
Muhan Zhang and Yixin Chen. Weisfeiler-Lehmaee Neural Machine for Link Prediction. In Proceedlings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 575-583, Halifax NS Canada, August 2017. ACM. ISBN 978-14400-448874. doi: 01114453007963.30000 https://dl. acm. wwt...org//o//1.11155555330 1ttp///1...11////99999/ 3097996
URL
Muhan Zhang and Yixin Chen. Link Prodiction Based on Graph Neural Networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnell (eds.), Advances in Neural Information
Processing Systems, volume 31. Curran Associates, Inc., 2018. URL pttpss//ppooceedings htt.eeeddinn..nuuisss..oo Pacetr-aappr.ppp
Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chon. Beyond link prodiction: Predicting hyperlinks in adjacency space. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling Trick: A Theory of Using Graph Ncural Networks for Multi-Node Representation Learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 9061-9073. Curran Associates, Inc., 2021. URL https://proceedding neurips. cttppprz/ccppp///////////pp Learning, pp. 12697-12706. PMLR, July 2021. URT. .
Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate Before Use: Improving Few- shot Performance of Language Models. In Proceedings of the 38th International Conference on Machine
mlr wttp:///mmm.......rr/ss///3///// ppress/v139/hha2222
html ISSN: 2640-3498.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physicul Journal B, (4)):6223 630, 2009. Publisher: Springer.
Zhaocheng Zhu, Zuobai Zhang, Louis- Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34, 2021.
A Experimental details
Triangular
Grid
80
90
99.2
75
85
55
99.0
70
H115850
800
50
65
45
98.6
60
70
UnLP
40
98.4
55
65
35
SUP
98.2
SUP
50
60
Full
Full
100
200
300
400
100
200
300
400
100
200
300
400
100
200
300
400
Training Samples
Training Samples
# Training Samples
# Training Samples
Figure 7: Performance of UniLP with varying quantities of in-context links on the rest of graph datasets.
19

---

Published in Transactions on Machine Learning Research (06/2025)
A.1 Pretraining the Models
We pretrain UniLP on the datasets listed in Table employing approach by sampling equal number of non-connected node pairs (V x E\) negalive samples to match the count of observed links ((E)) in each graph. The pretraining follows a standard binary classification framework.
For prodicting cach query link, we sample 40 positive and negative links as in-context links (5+ US from the respective pretrain dataset. This setup ensures variability: different query links from the same dataset or the same query link across training batches may be paired with different in-context links. However, during testing, the set of in-context links for each test dataset remains constant. This training methodology serves multiple purposes: it enhances UniLP's generalization capabilities by exposing it to broad range of in-context links and optimizes GPU memory usage by selecting a manageable yet diverse set of in-context links during pretraining.
The pretraining phase incorporates an early stopping criterion based on performance across a merged vali- dation set, which comprises 200 links from the validation set of each test dataset. This approach will stop UniLP's optimization once reaches optimal performance on this merged validation set, ensuring efficiency and preventing overfitting.
A.2 Software and hardware details
We implement UniLP in Pytorch Geometric framework Fey & Lenssen 2019 We conduct our experiments on a Linux system equipped with an NVIDIA A100 GPU with 80GB memory.
Supplementary experiments
B.1 Synthetic graphs
Table 4: Link prediction results on synthetic Triangular /rrd lattice graphs evaluated by Hits@50. The format average score standard deviation. The top three models are colored by First, Second, Third.
Triangular
Grid
Heuristics
CN
73.58
0.0011..0
AA
73.58=0.81
0.00=0.00
RA
70.58
0.0011..0
PA
2.000
0.00+4.00
SP
97.91 200.6
86.04.1.11
Katz
90.08
56.79 36.79
SEAL
Supervised Pretrained Only Pretrain & Finetune
99.29+a 28
79.45+1.00
08.81
61.481...7
98. 08.35.1..55
78. 10.70
Ours
UniLP
98.73=0.44
77.39+1.95
with outcomes presented in Table 4 These findings demonstrate that UniLP matches the performance of both models that are fully trained on the entire graph and those that undergo explicit finetuning. This performance underscores the efficacy of UniLP's ICL. capability, affirming ability to dynamically adapt synthetic graph environments and learn connectivity patterns directly from in-context links without the need for additional training finetuning.
We deployed our pretrained UniLP on the synthetic graph from Figure 2a 2b
20

---

Published in Transactions on Machine Learning Research (06/2025)
Table 5: Link prediction results on OGB datasets.
OGBL-Collab Hits@50
OGBL-Citation2
MRR
Heuristics
CN
61.37
51.47
AA
64.17
51.89
RA
64.00
51.98
Pretrain Only
SEAL
45.44
80.10
GAE
10.29
8.02
ELPHI
56.70
15.03
NCNC
58.32
20.76
MPLP
49.33
45.57
Pretrain & Finetune
SEAL
56.12
81.35
GAE
18.92
9.06
ELPHI
58.47
20.36
NCNC
60.25
24.79
MPLP
55.08
47.13
Ours
UniLP
61.09
83.29
B.2 OGB datasets
We also evaluate UniLP on the OGB (Hu et al. 2021 specifically on Collab and Citation2 The results are
shown in Table 5 UniLP achieves better performance compared to all the Pretrain (& Finetune) methods on two large-scale data, demonstrating its adaptability to new graphs without training on their connectivity patterns at all.
B.3 Empirical analysis of conflicting patterns
Theorem provides a theoretical analysis of the conflicting connectivity patterns Grid and Triangular graphs. In practical link prediction tasks, portion of edges often missing or yet to form. To test whether the conflicting patterns persist under such conditions, we conduct an empirical analysis by removing edges from the synthetic graphs.
Following the same setup as in Scction 5 we randomly remove 30% of the edges from both the Grid and Triangular graphs. We then estimate p(y = 1 1242) and p(y = 1 Aa) empirically for each graph. The results, presented in Table D. show that the two graphs continue to exhibit different connectivity patterns, despite their structural similarity. This supports the conclusion that the conflicting patterns identified in theory also hold under more realistic conditions.
Table 6: Empirical analysis for Theorem 2.2 under realistic conditions.
Triangular
Grid
ply 1/42)
0.318440.0013
0.0000=2..o0mo
ply 1/4s)
0.1656+0.000mf
0. 0.2036=0.00077
When evaluating SEAL and UniLP Citation2, sample the test to 1% get unbiased estiamte of
their performance, following (Zhang et 2021 http://////////ttt/c//c///////e/ http:://ssttttteeeeeeeeeeeeettes ogbl-citation2
21

---

Published in Transactions on Machine Learning Research (06/2025)
C Theoretical analysis
C.1 More discussions about the connectivity patterns
In the initial definition (Definition 2.1 connectivity patterns are characterized as ordered sequences of events that are satisfied by the features of links. This concept indicates that if two graphs exhibit. identical connectivity patterns, an LP model trained on one graph could theoretically be applied to the other without retraining. The rationale behind this rooted in the LP task's core objective: to prioritize true links over false ones through ranking. Hence, consistent ranking mechanism across different graphs allows for the heuristic-based link predictor to be effectively utilized for LPP tasks across those graphs.
It might be tempting to equate connectivity patterns directly with graph distributions; however, this is misconception. Graphs can share identical connectivity patterns yet differ significantly in their under- lying distributions. An illustrative example is provided by graphs generated through the Stochastic Block Model (Holland et al., 1983) with distinct parameters, which may still present identical connectivity patterns as long as their intra-block edge probabilities are higher than those between blocks.
Consequently, despite real-world graphs often exhibiting varied underlying distributions reflected such node degrees, graph sizes, and densities the question of whether singular, common connectivity pattern exists across diverse graphs remains non-trivial. This inquiry forms the theoretical foundation for our Universal Link Predictor model, challenging us to explore the feasibility of applying one singular link prediction methodology a world of inherently distinct graph structures.
distributions-rreeeeeeed in aspects
C.2 Proof for Theorem 2.2
We first restate the theorem and proceed with the proof:
Define A₂ = [w, u)] 2 and A3 = (z, v) 2 as elements of w. The connectivity patterns on Grid and Triangular graphs are distinct. Specifically:
(i) On Grid: [Aa, A2]: (fi) On Triangular: [Ag, As].
Proof. In a Grid graph, the probability a connection given a 2-hop simple path, p(y 1|A2), can be expressed as píy=1.Ag) The absence of any 2-hop connected node pairs (u, v) E implies p(y = 1, A2) = 0, p(As)
leading to ply A22 0.
Considering the symmetric nature of nodes in a synthetic Grid graph, select an arbitrary node as an anchor. Identifying nodes with a 3-hop simple path to this anchor reveals that:
ply = 1|As) = p(y 1,
4
p(As)
16
4
This calculation confirms the connectivity sequence on Grid as w = [Ag, Ag].
Conversely, in a Triangular graph, the probabilitics given 2-hop and a 3-hop simple path are calculated as:
p(y = 1/A2) ply = 12)
6
p(A2)
18
3'
puu = 1|43) = p(y = 1,)
6
p(Aa)
36
6'
Thus, establishing the comnectivity sequence for Triangular as = [A2, which is in direct contrast to that of Grid graphs, highlighting the inherent difference in their connectivity patterns.
22


Reviews:
[{"review_id": "HNzO8DqBY0", "reviewer": "Reviewer_ZQjd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1.\tThe paper introduces a principled integration of ICL into graph machine learning for link prediction, drawing a compelling parallel to recent advances in NLP where LLMs leverage ICL for generalization.\n\n2.\tThe proposed model, UniLP, outperforms pretrained link prediction frameworks across various datasets and settings, demonstrating generalization ability without task-specific fine-tuning.\n\n3.\tThe study addresses the important and timely problem of generalizing link prediction models to entirely unseen graphs, a direction of significant practical relevance and theoretical interest.\n\n**Weaknesses**\n\n1.\tThe method samples a large number of in-context links (up to 400 per query), which may incur substantial computational overhead, especially on large-scale graphs. I strongly recommend that the authors report the pretraining time and evaluation time of UniLP in comparison with standard baselines, including GNN-based models such as SEAL and heuristic models like RA.\n\n2.\tThe model’s performance appears sensitive to the quality and composition of in-context links. Evaluating this sensitivity by sampling in-context links with different random seeds could provide a clearer understanding of its robustness and the variance in performance due to context selection.\n\n3.\tIn the theoretical section, the proof for Theorem 2.2 requires revision. First, the proof is located in Appendix C.2, not in the section labeled “2.2” as currently stated. Second, the proof assumes that all edges—except for the target edge—are not missing, which deviates from typical link prediction scenarios where a subset of edges are randomly removed. I recommend that the authors provide an additional proof or discussion under a more realistic setting, such as random edge deletion at a fixed proportion.\n\n4.\tThe paper omits several important baselines that combine heuristic and learning-based methods, which are relevant to the goal of improving generalization. Notably: [1] propose a method that incorporates topological features using persistent homology, which can be seen as a form of structural heuristic combined with learning. [2] present a general GNN framework that unifies traditional algorithms with neural message passing, which could potentially generalize to unseen graphs as well.\n\n5. Currently, the pretraining and test graphs used in the experiments are from the same domain or category (e.g., social networks, citation networks, or collaboration networks). It would be significantly more compelling to evaluate UniLP under cross-domain generalization, such as pretraining on social networks and testing on biological graphs. This would test the model’s ability to handle more diverse structural and statistical properties, and better reflect real-world deployment scenarios.\n\n6. there is a line of work on inductive relation prediction [3, 2], where models are trained on some graphs and validated on totally unseen graphs, often within the same domain (e.g., knowledge graphs). This setting closely resembles the problem setup in this paper. The authors are encouraged to discuss the similarities and differences between the proposed setting and inductive relation prediction settings, especially in terms of generalization objectives, assumptions, and modeling strategies.\n\n[1] Yan et al. \"Link prediction with persistent homology: An interactive view.\" ICML 2021.\n\n[2] Zhu et al. \"Neural bellman-ford networks: A general graph neural network framework for link prediction.\" NeurIPS 2021.\n\n[3] Teru et al. \"Inductive relation prediction by subgraph reasoning.\" ICML 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents UniLP, a framework for universal link prediction on non-attributed graphs via in-context learning (ICL). Unlike conventional heuristic and parametric approaches, UniLP is designed to generalize across diverse graph datasets without the need for graph-specific training or fine-tuning. The model leverages contextually sampled support links from a target graph to dynamically adjust its link prediction behavior using an attention-based mechanism, allowing it to align with the graph’s unique connectivity pattern.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pkjiWkNPXE", "reviewer": "Reviewer_1AU4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The motivation and the principle of the method, in my opinion, are reasonable. In particular, using ICL to improve the generalization power of prediction models is a promising solution, which has been demonstrated in NLP tasks. I think it has the potential in the link prediction task as well.\n\n2) The organization of the paper is reasonable and clear, and the analytic part in section 2 is interesting. Although having some typos, the writing is clear to some extent.\n\nWeaknesses:\n\n1) In section 2, I think the empirical transferability experiment and the theoretical analysis are highly relevant to the homogeneity and the heterogeneity of graphs, which should be analyzed in depth. For example, in Figure 1, besides showing the change of model performance, the homogeneity scores of different graphs (i.e., the proportion of the edges whose nodes have the same label) should be provided as well. I believe the scores are correlated with the performance changes.\n\n2) For the proposed method, the length of contextual graph sequences, the proportion of positive/negative graphs, and the generation strategies of the contextual graphs are key factors impacting the model performance. However, I did not see detailed analytic experiments or ablation studies on these factors. In fact, I believe that the model performance would be much better if the authors could have analyzed the factors and found better model configurations.\n\n3) Some strong baselines using ICL or SSL are missed, e.g., the references shown below. I wonder if there are any difficulties in comparing the proposed method with them.\n\n[1] Wang, Ping, et al. \"Self-supervised learning of contextual embeddings for link prediction in heterogeneous networks.\" Proceedings of the web conference 2021.\n\n[2] Daza, Daniel, Michael Cochez, and Paul Groth. \"Inductive entity representations from text via link prediction.\" Proceedings of the Web Conference 2021. \n\n[3] Huang, Qian, et al. \"Prodigy: Enabling in-context learning over graphs.\" Advances in Neural Information Processing Systems 36 (2023): 16302-16317.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this submission, the authors propose a new link prediction method based on in-context learning, which makes an attempt to bridge the gap between heuristic approaches and learning-based parametric prediction models.\n\nThe proposed work first demonstrates that different graphs may have conflicting connectivity patterns, and adapting models to the graphs with conflicting patterns often leads to performance degradation. The authors solve this problem by in-context learning, predicting the links of target graphs based on the positive and negative examples plugged into the learned model. \n\nFinally, experiments show that the proposed method achieves competitive performance, obtaining top-3 link prediction accuracy in most testing datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The analytic content in section 2 can be more solid and convincing. Pls add more analysis on the relation between the graph nodes' homogeneity and the link prediction's transferability.\n\n2) More analytic experiments and ablation studies should be added for the proposed method.\n\n3) More relevant baselines should be introduced. The differences between the proposed method and the baselines should be provided, in both the related work section and the experimental part.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b7XERFFf1f", "reviewer": "Reviewer_bRwi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The paper is carefully written and most parts are clear. The proposed method / model is precisely defined and experiments are illustrated with sufficient data in appropriate forms. \n+ The idea of integrating ICL in link prediction / graph learning is interesting. It has been observed that simple heuristics methods may perform very well on link prediction tasks, making it an intriguing question how to efficiently combine heuristic methods with more expensive GNNs. \n+ The authors have conducted rich experiments to showcase the advantages of UniLP. \n\nWeaknesses\n- I am not sure how the proposed method can integrate non-parametric heuristic methods. It seems the major novelty lies in the introduction of ICL positives/negatives, where these ICL samples are encoded via GNNs. The non-parametric heuristics are not part of the model, and the ICL also may not be able to express the simple human-tailored heuristics.\n- One main concern of the proposed model is in its computation cost. GNN-based link prediction is already expensive to compute. With the additional ICL samples, it becomes much more expensive. To predict 1 candidate link, we basically need to run GNN through all positive / negative \"context\" links. The authors may consider adding a discussion on how to make UniLP efficient / scalable. e.g., maybe some subgraph-based GNN models like [1] can reduce computation cost by more efficient sampling. \n- For experiments, most benchmark datasets are quite old and of small scale. This makes the gains less convincing. It would be better to include results of modern benchmarks like OGB [2]\n- It is not intuitive what are the additional information brought by the ICL examples. Since positives / negatives are randomly sampled, they mostly provide global graph information. However, it is arguable that local graph / neighbor information may dominate in many link prediction tasks. In addition, standard GNNs may already encode much \"context\" information -- if we understand \"context\" for a pair of nodes as the surrounding subgraph neighborhood. \n\n-----\n\n[1] Decoupling the Depth and Scope of Graph Neural Networks. In NeurIPS 2021. https://arxiv.org/abs/2201.07858\n\n[2] Open Graph Benchmark. https://ogb.stanford.edu", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a link prediction framework that augments the traditional GNN-based methods with in-context embeddings. The paper is motivated by unifying the two lines of link prediction works, non-parametric heuristic link predictors and GNN-based link predictors, and tries to combine them via in-context samples from the target graph. Experiments on a diverse set of graph datasets covering multiple different domains show that UniLP outperforms both types of methods above. Detailed ablation studies are conducted to reveal the inner mechanism of UniLP, showing skill learning capabilities from ICL.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Please clarify how non-parametric heuristic methods are related with GNN-based UniLP. What's the relationship between non-parametric heuristic methods and ICL?\n* Please discuss the computation complexity. Do we need more efficient subgraph GNNs to handle the overhead from ICL samples?\n* Please explain what unique information can be brought by ICL samples. Why such information cannot be captured by local subgraphs?", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)