Link Prediction on Textual Edge Graphs

## Abstract

Abstract Textual-edge Graphs (TEGs), characterized by rich text annotations on edges, are increasingly significant in network science due to their ability to capture rich contextual information among entities. Existing works have proposed various edge-aware graph neural networks (GNNs) or let language models directly make predictions. However, they often fall short of fully capturing the contextualized semantics on edges and graph topology, respectively. This inadequacy is particularly evident in link prediction tasks that require a comprehensive understanding of graph topology and semantics between nodes. In this paper, we present a novel framework - Link2Doc , designed especially for link prediction on textual-edge graphs. Specifically, we propose to summarize neighborhood information between node pairs as a human-written document to preserve both semantic and topology information. A self-supervised learning model is then utilized to enhance GNN’s text-understanding ability from language models. Empirical evaluations, including link prediction, edge classification, parameter analysis, runtime comparison, and ablation studies, on four real-world datasets demonstrate that Link2Doc achieves generally better performance against existing edge-aware GNNs and pre-trained language models in predicting links on TEGs.

## 1 Introduction

In network science, the prevalence of networks with rich text on edges, also known as Textual-edge Graphs (TEGs) [, ], increasingly become significant, as they encapsulate a wealth of relational and contextual information critical for diverse applications. The text associated with edges in networks can dramatically deepen our understanding of network dynamics and behavior. For instance, in a social media network, when a user responds to another’s post, the reply not only creates a directed edge but also includes specific text that can reveal the sentiment, intent, or relationship strength between the users. Similar cases can also be found in citation networks where text on the edge is the exact reference quote. These examples illustrate how text-rich edges are pivotal in accurately interpreting and leveraging networked data for advanced analytical purposes. In TEGs, link prediction is a unique yet open question due to the complex textual information embedded on edges.

Extensive works have been devoted to studying graphs with rich text, which can be classified into two categories, i.e., Graph Neural Networks (GNN)-based and language model-based. GNN-based works have extensively studied the topology connection between nodes and designed various variants. Specifically, works [, , ] typically compress the text embedded on edges to latent vectors by text encoders (e.g., Word2Vec [] and BERT []), and iteratively merge edge features with/without node features [, ]. The current most advanced edge-aware GNN [] tries to refine the text encoder with the GNN training to obtain better representation, but it still follows the neighbor aggregation way that may not comprehensively consider overall semantics. On the other hand, owing to the strong text understanding ability of Large Language Models (LLMs) [], researchers [, , , ] have directly used language models to solve graph mining tasks on textual graphs by designing various prompts to express or summarize the topology connection into natural language.

While these approaches have advanced the study on text rich graphs, they tend to simplify the diverse text on edges, potentially losing crucial information necessary for tasks such as link prediction, where edge text is key to understanding the relationships within the graph. Both GNN-based and LLM-based methods may fall short of addressing the link prediction on TEGs due to two challenges, respectively.

Figure: Figure 1: An example of textual-edge graphs: two books are connected by citation links. Predicting whether there’ll be a citation between $A$ and $E$ needs to jointly consider both topology and semantic information embedded on nodes and their edges.
Refer to caption: x1.png

Challenge 1: Understand graph topology in language models. For LLM-based approaches, existing works have worked on prompting LLMs by expressing or summarizing graph topology into text, but the graph topology is generally expressed in a linear shape, which may lead to a significant loss of graph-based structural information. For example, as shown in Figure 1, if we summarize the relation between Book $A$ and $E$ as Breadth-first Search, the dependencies along specific paths would be overlooked. This approach would not capture the multi-hop interactions and the rich contextual dependencies among nodes and edges. On the other hand, if we summarize all paths from $A$ to $E$, the same edge, such as the negative reference on edge $C$ to $E$, could appear in several paths. Representing this repeated edge in text multiple times leads to unnecessary duplication and potential noise, complicating the model’s ability to discern the true nature of the relationships. If the graph is too large, potential overflow of the language model’s context window limitation also may emerge.

Challenge 2: Comprehensively consider context information on all connections. For GNN-based methods, predicting links in TEGs requires a comprehensive examination of all potential paths connecting two nodes. Neighborhood aggregation approaches often focus on immediate neighbors and fail to account for the complex interactions that can occur in textual-edge graphs. As shown in Figure 1, there are many multi-hop paths with different intermediate nodes between $A$ and $B$, and each edge is annotated with different contexts, including user descriptions and user comments, describing their complex relations. It’s already hard for existing GNN-based methods to use one latent vector to describe the complex context on edges. Moreover, user’s preferences may also differ from one path to another (i.e., $A\rightarrow C\rightarrow E$ is negative while $A\rightarrow B\rightarrow D\rightarrow E$ is positive), creating a conflicting semantic landscape. However, GNN’s neighbor aggregation would treat these paths uniformly, potentially diluting the sentiment difference in these paths.

Present Work. To effectively make link predictions on TEGs by jointly considering rich semantic information and graph topology, in this paper, we propose a novel network representation learning framework, Link2Doc, that transforms local connections between nodes into a coherent document for better reflecting graph topology along with semantic information. The crafted document further enhances GNNs to make link predictions in a contextualized way. The key contributions are summarized as follows:

- •
Problem. We formulate the problem of link prediction on textual-edge graphs and highlight the unique challenges of learning representations on textual-edge graphs for link prediction.
- •
Method. We propose an integrated framework to jointly consider topology and semantic information in textual-edge graphs, which consists of 1) coherent document composition to summarize local topology information between node pairs in plain language; and 2) a self-supervised learning module to teach graph neural networks language processing ability.
- •
Experiment. We empirically compare our method against existing state-of-the-arts in four real-world datasets. Results have shown our proposed methods can elevate the performance of general GNNs and achieve competitive performance against edge-aware GNNs.

## 2 Related Works

Edge-aware Graph Representation Learning. Earlier research of Graph Neural Networks (GNNs) [, ] tends to only focus on node features. Later on, research on heterogeneous graph representation learning [, , ] began to consider categorical information on edges. In text-attributed graphs, to more comprehensively utilize edge information during the network representation learning, some edge-aware GNNs [, , , ] were proposed to consider edge text by designing various architectures (e.g., attention on edges, node and edge role switch, etc.). The recent state-of-the-art method EdgeFormer [] involved pre-trained language models and proposed to better consider edge text by designing a cross-attention mechanism to merge node and edge representation in Transformer layers. However, these approaches still use the neighborhood aggregation way to obtain graph representation and cannot consider the local connections as a whole unit. Neighborhood aggregation may not always work especially when nodes are dissimilar (as shown in Figure 1) []. Moreover, existing edge-aware GNNs tend to deliberately erase text on nodes and only explore the effect of edge information on various graph-related tasks [], which lacks the flexibility to extend to other text-attributed scenarios.

Language Modeling Augmented Graph Learning. Large language models have been proven to have the ability to interpret graph-structured data [, , ]. In the past year, many works [, , , ] have been proposed to prove LLMs have great potential (and even become state-of-the-art) to classify nodes in text-attributed graphs. However, how LLMs can better assist link prediction in text-attributed graphs is still an under-explored area, let alone the more complicated scenario of edge-attributed graphs that contain rich textual information on both edges and nodes. Existing works [, , , ] have tried to distill implicit knowledge from LLMs to smaller GNN models for text-attributed graph tasks, but they still focus on learning good node embeddings.
In edge-attributed graphs, text on edges cannot be uniformly processed in the same manner as node text, necessitating more specialized techniques that account for the unique semantics and structural roles of edge attributes in enhancing graph-based learning models.

## 3 Link Prediction on Textual-edge Graph

In this section, we begin by introducing key notations and formulating the problem of link prediction on Textual-edge Graphs. We then describe a novel way of constructing a transition document that summarizes the relationship between node pairs for link prediction. Finally, we provide an LLM-enhanced Graph Neural Network framework that learns the local topology and semantic information to retain both efficiency and efficacy.

### 3.1 Problem Formulation

A Textual-edge graph (TEG) is a type of graph in which both nodes and edges contain free-form text descriptions. These descriptions provide detailed, contextual information about the relationships between nodes, enabling a richer representation of relational data than in traditional graphs.

###### Definition 1 (Textual-edge Graphs) .

A TEG $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is an undirected graph, which consists of a set of nodes $V$ and a set of edges $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$. Each node $v_{i}\in\mathcal{V}$ contains a textual description $d_{i}$, and each edge $e_{ij}\in\mathcal{E}$ also associates with free-form texts $d_{ij}$ describing the relation of $(v_{i},v_{j})$.

In this work, we target at the Link Prediction task on TEGs, where we aim to predict the existence (or the label) of edges between pairs of nodes $(v_{i},v_{j})\notin\mathcal{E}$ based on the neighborhood information of $(v_{i},v_{j})$. Due to the rich edge text information, local edges in TEGs can inherently be represented by natural language sentences. For example, the connection $v_{i}\rightarrow e_{ij}\rightarrow v_{i}$ can be represented as “$d_{i}$ is connected to $d_{j}$ via $d_{ij}$”, which directly describes the relation in plain text.

Compared to categorical-edge graphs that have edges labeled with simple, predefined categories, textual-edge graphs feature edges annotated with free-form text, which offer detailed and contextual relationship descriptions. Take Figure 1 again as an example, books are connected by textual edges, where text on edges consists of exact quotations that one book cites another. To predict whether $A$ and $E$ will have a citation link, we not only need to analyze semantics embedded within each edge’s description, but different paths may also depict different semantic meanings due to the varying textual descriptions and types of relationships they represent. As noted in Figure 1, the Red Path contains negative reference from $A$ to $E$, while the Blue Path indicates another group of researchers endorse the research conducted by book $A$.

Challenge. The rich and complex text information on edges makes the link prediction on TEGs not a trivial task, and there are two essential difficulties regulating existing GNN-based and LLM-based methods, respectively. For edge-aware GNN-based methods, directly combine and update each node $v_{i}$’s feature based on its neighbor’s $\mathcal{N}_{v_{i}}(v_{j})$ features as well as features of edges $e_{ij}$. However, neighborhood aggregation would fall short since semantic information carried on each edge $d_{ij}$ needs to be viewed in the context of the whole connections from $s$ to $t$. For LLM-based methods, existing works tend to prompt language models by summarizing graph topology in a linear manner, e.g., “$G_{(s,t)}$ contains $s,v_{1},v_{2},...,v_{n},t$ nodes, $v_{1}$ is connected to $v_{2}$ via $d_{12}$, $v_{2}$ is connected to $v_{4}$ via $d_{24}$, etc.” This way may let LLMs fail to understand how information propagates from $s$ to $t$ and the contextual dependencies among nodes.

Figure: Figure 2: Overall framework of LLM-enhanced link prediction on Textual-edge graphs, where orange and blue nodes in $G_{(s,t)}$ belong to $s$’s and $t$’s local neighborhood (namely $G_{s}$ and $G_{t}$), respectively. Half blue and half orange nodes denote shared nodes between $G_{s}$ and $G_{t}$.
Refer to caption: x2.png

###### Definition 1 (Textual-edge Graphs) .

### 3.2 Overall Architecture

In this work, we introduce Link2Doc, a novel approach that leverages a self-supervised learning scheme to endow GNNs with text comprehension capabilities akin to those of LLMs. Link2Doc is designed to preserve and synergize rich semantic information, topology information, and their interplay within TEGs for link prediction. We propose learning and aligning representations from two complementary perspectives: the text view and the graph view. The text view, termed Text-of-Graph, organizes the text associated with TEG’s nodes in a way that reflects the graph’s topology, forming a structured document that inherently captures logical and relational data. Conversely, the graph view, or Graph-of-Text, transforms the nodes and topology of TEGs into structured graph data. By employing pretrained language models (PLMs), the text view adeptly maintains textual integrity, while the graph view, processed through GNNs, ensures the retention of graph-specific characteristics. Aligning these views allows each representation to enrich the other, fostering a holistic understanding where textual nuances inform graph structures and vice versa.

Specifically, as noted in Figure 2 (a), to reduce the search space and to eliminate the noise from unrelated connections, we propose to formulate a $(s,t)$-transition graph containing all the possible routes through which $s$ could correlate to $t$ for link prediction.

###### Definition 2 (Transition Graph) .

For any pair of two entities $(s,t)$ in the Textual-edge Graph, all paths from $s$ to $t$ collectively form an $(s,t)$-transition graph, which is denoted by $G_{(s,t)}$. We use $n$ and $m$ to denote the number of nodes and edges in $G_{(s,t)}$, respectively. Figure 1 exemplifies an $(s,t)$-transition graph, where $s$ is Book $A$ and $t$ is Book $B$. In practice, the length of paths can be upper-bounded by an integer $K$, which can usually be set as the diameter of the Textual-edge graph.

The transition graph $G_{(s,t)}$, as well as all the text on edges, provide the necessary information needed to understand the relation between $s$ and $t$. Next, as shown in Figure 2(b), we separate two subgraphs: $G_{s}$ and $G_{t}$ from $G_{(s,t)}$ for preserving local neighborhood of $s$ and $t$, respectively. In Figure 2(c), to view the topology and semantic information of $G_{(s,t)}$ in a joint unit, we compose a manageable and coherent document that expresses $G_{(s,t)}$ as a human-written document. Finally, in Figure 2(d), we distill the text processing ability from large language models to graph neural networks for inference scalability while maintaining performance.

###### Definition 2 (Transition Graph) .

### 3.3 Transition Document Construction

In this work, to address the first challenge, we need to summarize local relations in $G_{(s,t)}$ to comprehensively understand the relation between $(s,t)$. Since state-of-the-art LLMs are predominantly trained on human-written documents and books, in this work, we propose a novel way to express $G_{(s,t)}$ as a structured document $d_{(s,t)}$ [], complete with an introduction, sections, subsections, and a conclusion, to let language models better understand the overall semantics between $s$ and $t$ with preserving topology. The overall process is illustrated in Figure 3, and the algorithm is summarized in Appendix 1 due to the space limit.

Figure: Figure 3: Given the transition graph $G_{(s,t)}$, we first split $G_{(s,t)}$ into $G_{s}$ (nodes are marked with orange) corresponding to the local structure of $s$ ($G_{t}$ is omitted due to space limit). Commonly shared nodes are marked with half blue and half orange. We transform the local structure of $G_{s}$ into a paragraph that summarizes hierarchical relation with $s$ being the root. For better visibility, hidden edges are highlighted with orange, and commonly shared nodes are highlighted with blue.
Refer to caption: x3.png

Node-centric Paragraph Composition. For source node $s$ and target node $t$, we first conduct Breadth-first Search (BFS) to extract their respective local structure with depth $L$, i.e., $G_{s}$ and $G_{t}$ from their transition graph $G_{(s,t)}$. As shown in Figure 3, nodes in $G_{(s,t)}$ that belong to $G_{s}$ are marked with orange, and nodes belonging to $G_{t}$ are marked with blue. The structural data (i.e., BFS tree) obtained is transformed into a textual paragraph aimed at both human readability and machine processability. Specifically, taking the BFS tree $G_{s}$ rooted at source node $s$ as an example, $s$ acts as the main subject of the paragraph’s textual summary. We conduct pre-order traversal to go over all nodes in both trees. The first and subsequent levels of BFS neighbors are detailed in separate sections and subsections, akin to a detailed outline:

- 1.
Root: Start with a comprehensive sentence that describes node $s$ and its immediate connections: “[ROOT s] Node $s$ has three connections. $s$ is connected to $v_{1}$ via $d_{s1}$, $s$ is connected to $v_{2}$ via $d_{s2}$, and $s$ is connected to $v_{3}$ via $d_{s3}$’’, where $d_{s1},d_{s2},$ and $d_{s3}$ are textual descriptions on edges $e_{s1},e_{s2}$, and $e_{s3}$.
- 2.
First-hop Neighbors: For each first-hop neighbor of $s$, we provide a section detailing its connections: “[1]. Node $v_{1}$ has two connections. $v_{1}$ is connected to $v_{11}$ via $d_{11}$, and $v_{1}$ is connected to $v_{12}$ via $d_{12}$”; “[2]. Node $v_{2}$ has one connection. $v_{2}$ is connected to $v_{21}$ via $d_{21}$”; and “[3]. Node $v_{3}$ has two connections. $v_{3}$ is connected to $v_{31}$ via $d_{31}$, ...”.
- 3.
Second (and following)-hop Neighbors: Subsections under each first-hop neighbor detail further connections: “[1.1] $v_{11}$ is connected to ...” “[1.2] $v_{12}$ is connected to...”.

This structure is recursively applied up to $L$ levels deep, ensuring each node’s direct connections are thoroughly described, capturing the intricate topology of the graph. The notation “[Section X]” serves as a reference back to earlier parts of the summary where the connected node was initially described, aiding in understanding the network’s connectivity beyond a simple hierarchical structure.

Hidden Edges. In many cases, we may not guarantee the neighborhood surrounding $s$ can form a tree structure. As shown in the transition graph in Figure 3, node $v_{122}$ is not only the child node of $v_{12}$, $v_{122}$ also links back to $v_{1}$ to form a triangle structure. To consider a more holistic view of the node relationships, we add an extra description to the node stating its connection to pre-existing nodes. Specifically, we introduce the hidden edge information of node $v_{122}$ in [Sec. 1.2.2] as “In addition, $v_{122}$ is also linked to [Sec. 1] $v_{1}$ via ...”. By letting each mention of a hidden edge direct back to the respective section “[Section X]”, we aim to ensure clarity and maintain the coherence of the graph’s description.

Transition Graph Document Construction. After generating the individual paragraphs for $s$ and $t$, we then concatenate these into a single document $d_{(s,t)}$. This unified $d_{(s,t)}$ aims to not only present isolated descriptions but also to highlight the interconnected nature of $G_{s}$ and $G_{t}$. In this work, we aim to illuminate the interconnectedness between $G_{s}$ and $G_{t}$ by identifying and highlighting nodes that appear in both $G_{s}$ and $G_{t}$’s local structures. These common nodes are pivotal as they link the context of one paragraph to the other. As shown in Figure 3, the common nodes are marked with half orange and half blue. For each common node, we include a cross-reference in the text where the node is mentioned, which is done by adding a note after the section index. For example, node $v_{122}$ has a section index “[1.2.2]” in $s$’s paragraph, and a section index “[1.2.1]” in $t$’s paragraph. We then add ([Sec. 1.2.1] in Paragraph $t$) after the section index of $v_{121}$ in $s$’s paragraph. We conduct the cross-reference in the other paragraph reversely.

In practice, we keep the depth $L$ to be half of the diameter of the $G_{(s,t)}$ so that $G_{s}$ and $G_{t}$ can each cover their close neighbor information as well as an adequate number of common nodes. We further enhance the document’s coherence by adding an introduction to the start of the document. Finally, the generated $d_{(s,t)}$ can be viewed as a structured document []. More details can be found in Figure 3.

### 3.4 LLM-enhanced Representation Learning for Link Prediction

Even though we can obtain a document $d_{(s,t)}$ summarizing topology and semantic information of $G_{(s,t)}$, scalability still poses a significant challenge for language models to make predictions on large-scale graphs. To conduct large-scale link predictions, we need to compose a large number of documents between node pairs, and many contents in these documents are duplicated (e.g., the transition documents of $(s,t_{1})$ and $(s,t_{2})$ largely overlap if $t_{1}$ and $t_{2}$ are neighbors). Moreover, $G_{(s,t)}$ with a diameter of $4$ can easily reach thousands of nodes in large graphs [], and the number of words in such a document would also exceed the context window limitation of most language models []. However, GNNs are designed to efficiently process graph structures, which motivates us to distill the text-processing ability of LLMs into GNNs, thus addressing the second challenge.

Aligning Topology Representation of $G_{(s,t)}$ with Semantic Information. Although LLMs may not be capable of conducting large-scale link predictions, the implicit knowledge can still be utilized to train GNNs. In this work, we leverage LLMs to generate latent embeddings of $d_{(s,t)}$ as $\tilde{h}_{(s,t)}$ to guide the training of GNNs:

$$ $\displaystyle\tilde{h}_{(s,t)}=f_{LM}\left(d_{(s,t)}\right),\quad\quad h_{(s,t )}=g\left(f_{GNN}(G_{s})\oplus f_{GNN}(G_{t})\right),$ $$

where $\oplus$ denotes embedding concatenation, $f_{LM}(\cdot)$ and $f_{GNN}(\cdot)$ denote the LLM query function and GNNs, respectively. We transform text on nodes and edges with pre-trained language models (e.g., BERT [] or LLaMA models []) and feed these attributes along with adjacency matrix of $G_{s}$ and $G_{t}$ to GNNs. The outputs are then concatenated and transformed into LLM’s embedding space by a projection function $g(\cdot)$ with non-linear transformation. We seed to align the latent embeddings $\tilde{h}_{(s,t)}$ produced by the LLM with the embeddings $h_{(s,t)}$ generated by the GNN:

$$ $\displaystyle\ell_{KD}=-\mathbb{E}\left[\log\frac{\exp\left(\operatorname{sim} (\tilde{h}_{(s,t)},h_{(s,t)})/\tau\right)}{\sum^{K}_{k=1}\exp\left( \operatorname{sim}(h_{(s,t)},h_{(s,k)})/\tau\right)}\right],$ (1) $$

where the objective function is based on temperature-scaled cross-entropy loss (NT-Xent) [] to enforce the agreement between $\tilde{h}_{(s,t)}$ and $h_{(s,t)}$ compared with latent embedding $h_{(s,k)}$ from negative pairs. Furthermore, to calibrate $h_{(s,t)}$ more towards the link prediction (and edge classification) task, we incorporate standard binary cross-entropy loss $\ell_{LP}$ for tuning GNNs. Note that for dealing with highly imbalanced label distribution for edge classification tasks, we use weighted cross-entropy loss (e.g., Focal Loss []) instead.

Finally, the overall objective of the LLM-enhanced Representation Learning for predicting links on edge-attributed graphs is written as $\ell=\lambda_{1}\ell_{KD}+\lambda_{2}\ell_{LP}$, where $\lambda_{1}$ and $\lambda_{2}$ are hyperparameters.

Complexity Analysis. Given the transition graph $G_{(s,t)}$ with the diameter $K$, we use Breadth-first Search (time complexity $O((N+E)/2$) (BFS) with the depth $K/2$ to extract $G_{s}$ and $G_{t}$, respectively. We then use pre-order traversal to obtain the document $d_{(s,t)}$, which leads the total complexity to be $O(N+E+N)$. The time complexity for Pre-trained LMs to process $d_{(s,t)}$ is $O(P^{2})$, where $P$ denotes the number of tokens in $d_{(s,t)}$. Moreover, the GNN module requires $O(|E|\cdot f+N^{2})$, where $f$ denotes the dimension of the embedding on nodes/edges. Overall, The complexity encapsulates the stages of BFS tree construction, document processing with Transformers, and GNN learning, which gives the training time complexity $O(2N+E+P^{2}+|E|\cdot f+N^{2})$. However, during the inference stage, the complexity of our work simply reduces to the complexity of normal GNNs: $O(|E|\cdot f+N^{2})$ as we do not need to construct documents during the inference phase.

## 4 Experiment

We conduct various experiments, including link prediction, edge classification, runtime analysis, and ablation study, to verify the effectiveness of Link2Doc on multiple real-world textual-edge graphs.

### 4.1 Experiment Setup

The focus of the paper is link prediction on textual-edge graphs, which aims at predicting if there will be a strong connection between two specific nodes in the Amazon and Goodreads datasets based on their transition graph. For instance, in GoodRead datasets, we analyze a target user’s reviews of other items or books, as well as the reviews of the target item or book by other users. Our aim is to forecast whether there will be a top-rated link (5-star) between the target user and the target item. We evaluate the performance using the standard metrics: Area Under ROC Curve (AUC) metric and F1 score. We adopt Graph Transformer (GTN) [] as our base GNN for the self-supervised learning module.

Data. We run experiments on four real-world networks: Amazon-Movie [], Amazon-Apps [], GoodReads-Children [], and GoodReads-Crime []. Amazon is a user-item interaction network, with reviews serving as textual content associated with the edges. Goodreads is a reader-book network, that utilizes readers’ comments as textual information within the edges. More specific dataset statistics can be found in the Appendix A.2.

Comparison Methods.
We compare our model with general GNNs, language model integrated GNNs, and large language models. For general GNNs, we select MeanSAGE [], MaxSAGE [], and GIN [], which only use an adjacency matrix as the input. For language model-enhanced GNNs, we utilize Pre-trained LMs, e.g., BERT [], to acquire text representations on edges. Our baselines consist of BERT + Graph Transformer (GTN) [] and BERT + GINEConv []. Furthermore, we also incorporate state-of-the-art edge-aware GNN - Edgeformer [], which is constructed based on graph-enhanced Transformers to combine language modeling into each layer of the Graph transformer. Finally, we adopt state-of-the-art LLMs, i.e., LLaMA-2-13B and GPT-3.5-Turbo by directly translating the transition graph $G_{(s,t)}$ between the node pair $(s,t)$ to natural language as [] do. Note that state-of-the-art language model integrated GNNs, namely EdgeFormer and GINEConv, cannot incorporate text on nodes. For a fair comparison, we present two variants of our method: Link2Doc does not consider node texts, and Link2Doc-NT takes node text into account.

Implementation Details. For general GNNs, the dimensions of the initial node and edge embeddings are set to be 64 and 128 respectively. For language model integrated GNNs, the dimension of the node embeddings is consistent with that of general GNN methods. However, the edge embeddings dimension is $3072$, which is obtained from OpenAI’s embedding model: text-embedding-3-large. Additionally, for the Edgeformer model, we adhere to the same experimental settings as outlined in []. Our model uses Graph Transformer (GTN) as our backbone, where both node and edge embeddings mirror those of language model integrated GNNs. We set $\lambda_{1}=1$ and $\lambda_{2}=2$ respectively. All GNN baseline layers are set to $2$. We use Adam as the optimizer with a learning rate of $1e-5$. The batch size is $1024$. For obtaining the embedding of the generated document, we also incorporate OpenAI’s embedding text-embedding-3-large with dimension $3072$. We run our model and other baselines $10$ times with different random seeds and report AUC and F1 on average.

**Table 1: The performance comparison of Link Prediction on all datasets (the higher the better), where the bests are highlighted with bold, and the second bests are highlighted with underline. Note that $-$ indicates the dataset does not have text on nodes so that Link2Doc-NT cannot be conducted.**
|  | Goodreads-Children | Goodreads-Crime | Amazon-Apps | Amazon-Movie |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | AUC | F1 | AUC | F1 | AUC | F1 | AUC | F1 |
| General GNN |  |  |  |  |  |  |  |  |
| Max-SAGE | 0.870 | 0.637 | 0.858 | 0.624 | 0.727 | 0.571 | 0.706 | 0.527 |
| Mean-SAGE | 0.828 | 0.611 | 0.829 | 0.615 | 0.700 | 0.569 | 0.686 | 0.525 |
| GIN | 0.859 | 0.571 | 0.857 | 0.577 | 0.705 | 0.543 | 0.692 | 0.512 |
| Edge-aware GNN |  |  |  |  |  |  |  |  |
| GTN | 0.880 | 0.654 | 0.863 | 0.640 | 0.728 | 0.572 | 0.742 | 0.539 |
| GINEConv | 0.881 | 0.657 | 0.864 | 0.636 | 0.701 | 0.573 | 0.692 | 0.543 |
| Edgeformer | 0.882 | 0.662 | 0.862 | 0.643 | 0.722 | 0.580 | 0.744 | 0.540 |
| LLMs |  |  |  |  |  |  |  |  |
| LLaMA-2-13B | 0.832 | 0.573 | 0.869 | 0.587 | 0.694 | 0.509 | 0.643 | 0.482 |
| GPT-3.5-Turbo | 0.878 | 0.609 | 0.889 | 0.604 | 0.712 | 0.512 | 0.659 | 0.503 |
| Link2Doc | 0.902 | 0.705 | 0.901 | 0.652 | 0.762 | 0.588 | 0.753 | 0.553 |
| Link2Doc-NT | – | – | – | – | 0.769 | 0.595 | 0.759 | 0.565 |

### 4.2 Results on Link Prediction

As can be seen from Table 1, without considering the text on nodes, Link2Doc can already achieve a generally better performance than other methods. Specifically, Link2Doc outperforms the second best on average $5$% of both AUC and F1 across all datasets. We further draw several observations from the results. 1) There are no clear differences between general GNNs and edge-aware GNNs: both types of GNNs show comparable performance, with edge-aware GNNs having a slight edge but not consistently outperforming general GNNs in all metrics, which implies co-training language models with GNNs still cannot capture the subtle cues on edge texts. For instance, while Edgeformer achieves the second-best AUC on the Goodreads-Children dataset, it doesn’t consistently outperform general GNNs like Max-SAGE across all datasets. 2) Directly summarizing topology and letting LLMs make predictions may not perform well: LLMs, such as LLaMA-2-13B and GPT-3.5-Turbo, tend to underperform compared to specialized GNNs and our proposed Link2Doc. This is evident that state-of-the-art LLMs may not be able to fully understand graph topology from the linear topology summarization, highlighting the advantage of the composed document. 3) Text on nodes can further improve the performance: As can be seen from the table, even though Link2Doc can achieve a generally better performance than other approaches, by considering the text on nodes, Link2Doc-NT can achieve a generally better performance than its no node-text version.

### 4.3 Results on Edge Classification

**Table 2: Comparison on Edge Classification on Amazon-APPs dataset.**
|  | Amazon-APPs |  |
| --- | --- | --- |
| AUC | F1 |  |
| Mean-SAGE | $0.551$ | $0.479$ |
| GINE | $0.573$ | $0.488$ |
| GTN | $0.567$ | $0.503$ |
| Edgeformer | $0.612$ | $0.526$ |
| Link2Doc | 0.626 | 0.541 |

In the task of edge classification, the model is asked to predict the category of each edge based on its associated text and local network structure. There are $5$ categories for edges in the Amazon-APPs dataset (i.e., from 1 star to 5 star). The results of the $5$-class edge-type classification are shown in Table 2. As clearly can be observed in the table, Link2Doc improves the AUC by an average of $5\%$ and the F1 score by $4.2\%$ compared to other models, demonstrating its superior performance in edge classification.

### 4.4 Ablation Study and Parameter Analysis

We further demonstrate the effectiveness of each component in our framework and analyze the importance of different hyper-parameter settings.

Figure: (a) Link Prediction Improvement
Refer to caption: x4.png

Performance Elevation from Transition Document. We first aim to check the general performance elevation brought by the composed transition document $d_{(s,t)}$. We adopt three GNNs with using BERT to obtain embeddings on edges and illustrate whether using the composed $d_{(s,t)}$ as a reference would improve their performance in both link prediction and edge classification tasks. The results on the Amazon-APPs dataset are presented in Figure 4. As can be seen from the figure, the document-augmented GNNs excel in their general version with an average improvement of $5\%$. By summarizing all relations from $s$ to $t$ as a coherent document, language models can give positive feedback on the proposed self-supervised learning module to guide different GNNs in learning.

Figure: Figure 5: The performance on Amazon-APPs.
Refer to caption: x6.png

Hyperparameter Analysis. We then aim to investigate the sensitivity of the key hyperparameter $\lambda_{2}$ and their impact on Link2Doc’s performance. Specifically, since $\lambda_{1}$ controls the basic objective function for link prediction, we fix $\lambda_{1}=1$ and show the link prediction performance on the Amazon-APPs dataset under different $\lambda_{2}$ values (ranging from 0 0 to $5$). As shown in Figure 5, both metrics show consistent results across varying parameter values. By comparing with the second-best methods (highlighted with red dash horizontal lines), Link2Doc with various $\lambda_{2}$ values can achieve overall better results. This demonstrates that our model maintains superior performance across different configurations, highlighting its stability and effectiveness.

### 4.5 Runtime Analysis

**Table 3: Comparison of Inference and Training Times on Goodreads-Children and Goodreads-Crime.**
|  | Children | Crime |
| --- | --- | --- |
| Inference Time (s) |  |  |
| Edgeformer | $1450.67$ | $3307.66$ |
| Link2Doc | $49.35$ | $23$ |
| Training Time (h) |  |  |
| Edgeformer | $12.17$ | $12.65$ |
| Link2Doc | $5.253$ | $7.04$ |

We further illustrate the runtime comparison between our proposed Link2Doc with the state-of-the-art edge-aware GNN - Edgeformer. The comparison table (Table 3) highlights the efficiency of our method, Link2Doc, which significantly outperforms Edgeformer in both inference and training times. For the Goodreads-Children dataset, Link2Doc is approximately 29 times faster in inference and more than twice as fast in training. On the Goodreads-Crime dataset, Link2Doc demonstrates an even greater advantage, being about 144 times faster in inference and almost twice as fast in training. These improvements stem from Link2Doc’s design, which does not require fine-tuning language models; instead, it builds document representations and uses a pre-trained GNN, avoiding the extensive matrix calculations in Edgeformer’s cross-attention design. Consequently, Link2Doc is more scalable and efficient for large-scale link prediction tasks.

## 5 Conclusion

In this work, we study the problem of link prediction on textual-edge graphs, where existing GNN-based and LLM-based methods may fall short of jointly capturing both semantic and topology information to make more accurate link predictions. We present a novel framework Link2Doc that learns and aligns the semantic representation and topology representation by 1) building a structured document to preserve both topology and semantic information; and 2) designing a self-supervised learning module to let GNNs have text understanding ability like LLMs. In the experiment, we analyze the strength of Link2Doc on four real-world datasets, and our method generally outperforms other approaches from multiple aspects, highlighting the performance improvement by bridging language models and GNNs with the structured document.

## Appendix A Supplemental Material

### A.1 Algorithm of Transition Document Composition

Figure: Algorithm 1 Transition Document Composition

We provide the full procedure of producing the document $d_{(i,j)}$ based on the node pair’s transition graph $G_{(s,t)}$ in Algorithm 1. From Line $1$-$2$, we obtain the respective local structure of $s$ and $t$ based on their transition graph $G_{(s,t)}$ by BFS search. From Line $3$-$4$, for both $G_{s}$ and $G_{t}$, we extract hidden edges that are not covered in the BFS tree. In Line $5$, we get the intersection of the node sets $V_{s}$ and $V_{t}$ for recording the cross-paragraph nodes. Next, we initiate the document with the initial prompt and traverse each node in $G_{s}$ and $G_{t}$ to assign document section indices and relations to the document. Finally, we add hidden edges and cross-paragraph references as denoted in Line $12$-$13$.

### A.2 Datasets

The statistics of the four datasets can be found in Table 4.

**Table 4: Dataset Statistics**
| Dataset | # Node | # Edge |
| --- | --- | --- |
| Goodreads-Children | 192,036 | 734,640 |
| Goodreads-Crime | 385,203 | 1,849,236 |
| Amazon-Apps | 100,468 | 752,937 |
| Amazon-Movie | 173,986 | 1,697,533 |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Regarding the experiments, I suggest the authors organize their method and baselines based on the information used: (1) do they use the node feature information? (2) do they use the graph structure information? (3) do they use the edge feature information? 
The current layout makes it hard to compare the proposed method with baselines under a fair setting.

2. Similar to above, for each method, what LM was used to generate the textual embeddings? Since the capabilities of different LMs vary a lot, this information is critical for a fair judgement. 

3. The authors mentioned that the texts were processed with OpenAI's embedding model with d=3072. Is this embedding used only during the contrastive learning process as the output of the text view? What is the input features for the student GNN? 

4. As a paper specific to link prediction, it is weird not to include any GNN4LP baselines like NCN and BUDDY. If this setting is not compatible with GNN4LP methods, please explain the reasons.
soundness: 2
strengths: 1. The question of LP on TEGs is practical.

2. The idea of using (s,t)-transition graph for link prediction is interesting and makes sense to me. 

3. Dstillinig knowledge from teacher LLM to student GNN is a well-established approach with proven effectiveness, which suits the setting of LP on TEGs.
summary: This paper studies link prediction on textual-edge graphs (TEGs). They proposed a framework LINK2DOC, which models TEGs from two perspectives, i.e., the text view (text-of-graph) and the graph view (graph-of-text). Via performing contrastive learning to align the representations produced by the two views, they distill the knowledge from LLMs to GNNs for efficient inference.
weaknesses: 1. I found it difficult to capture the key aspects of the proposed method. The authors may consider reorganizing the manuscript to put more emphasis on the overall pipeline and refer readers to appendix for details. The current version contains a lot of details and seems overwhelming to me.

2. Confusing experimental settings and missing baselines. Please see Questions.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 1
questions: see above
soundness: 1
strengths: 1. The analysis of challenges in LLM-based and GNN-based methods are interesting, supported by real examples in Fig 1.
2. The proposed transition graph provides a clear view of target node pairs, avoiding information over-smoothing when propagating on whole graph.
summary: This paper focuses on Link Prediction on Textual-edge Graphs. For current approaches, the authors challenge LM's ability to understand graph topology, and GNN's ability to consider contextual information on all connections. This paper proposes an integrated framework, Link2Doc, to jointly consider topology and semantic information in TEG, which summarizes semantic relations between nodes in text, and processes topology information with a transition GNN. This paper compares Link2Doc with SOTA methods in 4 datasets and shows some improvements.
weaknesses: 1. Bad representation. The challenges of LLM-based and GNN-based methods are twisted together. Not clearly conveyed in texts and supported by experiments.
2. LM-enhanced GNNs use BERT to extract text representations, while other models use LLaMA-3 and GPT-4o, making comparison unfair. Besides, even though LM-enhanced GNNs use BERT, these models still perform the second best generally, making the improvements of Link2Doc doubtable.
3. The GNN layers are set to 2. The review suspect that, will the proposed challenges and examples still stand in such a shallow graph setting.
4. The compared baselines are not in their best performance, making overall comparison inconvincing.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. In the PROBLEM FORMULATION section, you mention that linearly summarizing graph topology may cause LLMs to struggle with understanding information propagation from s to t and the contextual dependencies among nodes. However, in the ablation study, you only compare the performance differences between the “without document” and “document-augmented” settings. Could you add an ablation study comparing the performance of linearly summarizing graph topology versus using your proposed Transition Document Construction? This would help highlight the specific advantages of the Transition Document Construction approach.
2. In your experiments, the value of K used for K cuts in TGNN is not mentioned. Could you clarify what value of K was used to achieve your reported results?
soundness: 3
strengths: This paper presents an innovative approach to address the shortcomings of existing GNN-based and LLM-based methods in link prediction. The authors effectively highlight the limitations of current methodologies and introduce a novel framework that integrates both graph structure and textual information.
summary: This paper addresses the problem of link prediction on textual-edge graphs, highlighting that existing GNN-based and LLM-based methods often fail to capture both semantic and topological information effectively. To overcome these limitations, the authors propose LINK2DOC, a novel framework that constructs a structured document to preserve this information and employs a Transition Graph Neural Network (TGNN) for enhanced representation learning. Additionally, incorporates a self-supervised learning module that aligns the semantic understanding of TGNN with the capabilities of LLMs. Experiments across five datasets demonstrate that LINK2DOC consistently outperforms existing methods in link prediction accuracy.
weaknesses: One notable limitation is that the paper’s Transition Graph Document Construction approach appears to be similar with the Graph2Text component from the TAGA framework, as introduced in TAGA: Text-Attributed Graph Self-Supervised Learning by Synergizing Graph and Text Mutual Transformations https://arxiv.org/abs/2405.16800. If that is your work, please cite this paper properly, and discuss about the difference between your method with perspective of the algorithm development and complexity?

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. May you demonstrate the cost of using openai models?
2. Could you summarize the whole process (not the document construction) using the format of an algorithm?
3. May this framework be extended to solve other problems like heterophily in node classification by considering the semantics of edges?
soundness: 3
strengths: 1. This paper studies an interesting research question with clear motivation. The example given in Figure 1 well demonstrates the importance of edge semantics in citation networks. 
2. The method proposed in this paper seems sound. 
3. The experimental results are promising.
summary: This paper investigates representation learning at the edge level on a specific type of text-attributed graph where edges carry semantic information. To address the limitations of previous methods in capturing contextualized edge semantics and the graph's topology, they propose Link2Doc. This approach summarizes the semantic and structural information of the neighborhood as a document. They then perform representation learning using a multi-scale Graph Neural Network (GNN) supplemented with an alignment module. This method demonstrates state-of-the-art performance across a variety of edge prediction tasks.
weaknesses: 1. Edges with semantic information have been widely studied in some other areas, like recommendation systems and multi-tabular prediction [1], authors may add some discussions on these related areas. 
2. Despite the promising performance, the methods proposed in this paper have high module complexity. Using LLM to summarize neighbor information is not innovative, and encoding long text can be costly in terms of time and money. In the experiment section, I didn't see any ablation study on the self-supervised learning-based alignment, nor any analysis of the time and money cost of generating embeddings with LLM. Moreover, I think the time comparison between Link2Doc and Edgeformer is not very meaningful, as it's difficult to evaluate the API call time to OpenAI.
3. The modules present in this paper are relevant to [2,3], but they are not discussed in this paper. 
4. In terms of performance comparison, I think parts of the improvement are brought by more powerful text encoders (openai embedding model with more context length), which limits the applicability of this model in real industrial scenarios (like [1]). 

[1] Wang, Minjie, et al. "4DBInfer: A 4D Benchmarking Toolbox for Graph-Centric Predictive Modeling on Relational DBs." arXiv preprint arXiv:2404.18209 (2024).
[2] Wen, Zhihao, and Yuan Fang. "Augmenting low-resource text classification with graph-grounded pre-training and prompting." Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023.
[3] Song, Yunchong, et al. "Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing." arXiv preprint arXiv:2302.01524 (2023).

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. Could labeling bias or annotation errors be affecting the LLM's performance, and would a case study help demonstrate if the LLM predictions are reasonable?
2. Given the similarities between the proposed method and models like CLIP, do you think large-scale pre-training could improve performance, and have you considered exploring the model's potential zero-shot generalization capabilities?
soundness: 3
strengths: 1. LINK2DOC introduces a novel approach to link prediction by converting local graph information into coherent documents, effectively combining both graph topology and rich semantic information on edges. This offers a unique solution to the challenges of learning representations on TEGs.

2. The proposed specialized Transition Graph Neural Network captures multi-scale interactions between target nodes in a stratified manner, improving the model's ability to process complex topological relationships and edge semantics at different levels of granularity.

3. The framework is rigorously tested on four real-world datasets, showing superior performance over general GNNs and competitive results against edge-aware GNNs. The inclusion of link prediction, edge classification, and runtime analysis further demonstrates the robustness and practical applicability of LINK2DOC.
summary: The paper introduces LINK2DOC, a novel framework designed for link prediction on Textual-edge Graphs (TEGs), which are graphs characterized by rich text annotations on edges. The framework aims to address the limitations of existing methods by capturing both the graph topology and the semantic information embedded in the text on the edges. LINK2DOC achieves this by summarizing neighborhood information between node pairs into coherent documents, which preserve both semantic and topological relations. Additionally, it employs a stratified GNN architecture to capture multi-scale interactions between nodes and utilizes a self-supervised learning module to enhance the GNN’s ability to understand and process textual information. Extensive experiments demonstrate that LINK2DOC outperforms existing edge-aware GNNs and language models on multiple real-world datasets.
weaknesses: 1. When consider about the time complexity, the LLM encoder part is not taken into consideration. 
2. Some baseline is lack of consideration. One advantage of the text-attributed graph is that it can be naturally represented as the textual representation. The potential reason why LLMs cannot do well are two-fold. (i) the annotation error or labeling bias. (which I think case study is important to show whether the LLM prediction is reasonable) (ii) out-of-distribution issue. A smaller LM, e.g., sentencebert can achieve better performance
3. For the GNN baseline, GLEM baseline which train both bert and GNN is not taken into consideration[1] 
4. The proposed method shows certain similarity with the clip model, I think the model may benefit more from large-scale pre-training. Moreover, the model may have good zero-shot generalization capability, which I would suggest the author to check more on it. 

[1] Zhao, Jianan, et al. "Learning on Large-scale Text-attributed Graphs via Variational Inference." The Eleventh International Conference on Learning Representations.

Meta-review: Reviewers find that the problem of LP on textual edge graphs is well motivated with solid analysis and example in Figure 1. The transition graph idea is interesting.

However, experimental setup requires further clarification, and the presentation and organization of the paper can be better organized to highlight the key aspects.

Decision: Reject