acceptodds
Under review as a conference paper at ICLR 2027

What Neighbors should an LLM See? A Systematic Empirical Study of Graph Neighborhood Serialization

Abstract

Large language models (LLMs) have recently been used to reason over graph-structured data for graph tasks, including Node Classification (NC) and Link Prediction (LP). Since graph neighborhoods are non-sequential and can span multiple hops beyond the LLM's sequence budget, only a subset of the graph context can be serialized. This motivates us to investigate: What neighbors should an LLM see? We present a systematic empirical study of graph neighborhood serialization on both NC and LP tasks across four datasets: Cora, Citeseer, PubMed, and ogbn-arxiv. We compare random selection, structural ranking, semantic similarity, and task-aware signals and show that no universal neighborhood serialization method is dominant. The effectiveness of structural signals varies between datasets and tasks, with random selection performing competitively in some settings. To analyze the effect of class-relevant context, a label-informed Oracle, used only for diagnostics, improved NC performance in all datasets, with the largest improvement on ogbn-arxiv, where accuracy increased from around 76% to 92%. Task-aware signals, however, revealed different task-related limitations: NC class-relevance signals are only approximate, while LP pair-aware signals are exact when available but often sparse. Cross-serialization analysis showed that the models can adapt to their training-serialization distribution, therefore affecting their performance on different test-time serialization sequences. Overall, our study revealed that the effectiveness of neighborhood serialization depends on several factors and features that are both dataset and task-dependent.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Representation Learning, Graph Neighborhood Serialization, Large Language Models (LLMs), Node Classification, Link Prediction

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_YaBnOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies which neighbors an LLM should see when the graph sequence has a fixed size. It keeps the LLaGA interface largely fixed and compares random, structural, semantic, and task-specific neighbor selection. The experiments cover node classification and link prediction on four citation datasets. The paper concludes that no method is always best, random selection is often competitive, and a label-informed Oracle can greatly improve node classification.

Critical strengths
  1. The question is reasonable. Keeping the interface fixed is a useful way to study the effect of neighbor selection.

  2. The paper considers both node classification and link prediction. I also find the experiment that changes the serializer between training and testing useful.

  3. Figure 2 reports CN and CN2 coverage separately for positive and negative pairs. The label-agreement results in Table 8 are also helpful for understanding what information is present in the selected neighborhoods.

Critical weaknesses
  1. Section 3.4 and section 4.4 are almost the same. Please justify why they are so similar.

  2. The paper does not report repeated training runs, variance, or significance tests. Many differences are very small. On ogbn-arxiv, Random scores 0.7635 and PPR scores 0.7636, which is a difference of about five test nodes. The PubMed node classification results are also very close. In addition, Table 7 appears to choose the best serializers from test results, and these choices are used again in the later analyses on the same test set. The authors should use validation results for this choice and report results over multiple seeds.

  3. The budget may not be restrictive enough on Cora, CiteSeer, and PubMed. Their median degrees are only two or three in Table 4, while the first-hop budget is ten. For many nodes, all first-hop neighbors can fit, so the methods may mainly change the order of neighbors. For example, Random, Core, and Degree have exactly the same Cora accuracy in Table 1. The paper should report how often each method actually has to discard neighbors at each hop.

  4. The Oracle uses the target node’s own test label to rank neighbors. This means that information about the answer affects the input sequence. On ogbn-arxiv, accuracy falls from 0.9237 to 0.5454 when an Oracle-trained model receives Random test sequences (Table 9). This is also consistent with the model learning a shortcut from the label-dependent sequence. The Oracle is useful as a diagnostic, but its result should not be treated as an achievable improvement for a usable selector. The structure-trained model reaches only 0.8079 even when it receives Oracle sequences at test time.

Questions for authors

Please see the above weaknesses.

1 comment

We thank the reviewer for the detailed feedback and for acknowledging the value of our systematic analysis and experiments. We address the concerns below.

1- Weakness 1:

Section 3.4 presents the cross-serialization experimental design, while Section 4.4 discusses the findings in relation to RQ4, focusing on the model's sensitivity to changes in serialization between training and testing. We understand the possible confusion and can rewrite these sections to reduce repetition.

2- Weakness 2:

Our goal is not to establish the superiority of individual serializers based on small differences in accuracy, but to investigate how neighborhood serialization affects LLM-based graph learning across datasets and tasks. We can provide standard deviations alongside the reported accuracies to better characterize the variability of our results.

The small differences between several methods are consistent with our main finding that no single serializer is consistently dominant. This observation is particularly important given that our experiments cover four datasets with different sizes, structural characteristics, and levels of homophily. For example, PubMed has high homophily (around 80%), which may partly explain the small differences in accuracy among serializers, as even randomly selected neighbors are likely to share the target node’s class. In contrast, ogbn-arxiv has lower homophily (around 65%) and a highly uneven degree distribution (Table 4). Therefore, structural serializers may favor high-degree hubs that do not necessarily provide class-relevant information, as further illustrated by the label-agreement analysis in Table 8. These observations highlight that effective serialization depends on task-relevant information and dataset characteristics rather than method complexity.

Regarding Table 7, we selected the best-performing serializer within each family for each dataset based on the initial experimental test results to keep subsequent analyses manageable. Our goal was to compare different serialization families rather than individual methods, investigating which types of neighborhood information are most suitable for different tasks and datasets. We understand that selecting representative methods based on the test results may introduce bias, and we will address this limitation in the paper.

3- Weakness 3:

Our experiments cover four datasets with different degree distributions (Table 4), allowing us to examine serialization under varying neighborhood conditions. Although Cora, CiteSeer, and PubMed have relatively low median degrees, our framework uses hierarchical two-hop neighborhoods. As shown in Table 1, second-hop truncation occurs for 81.74% of PubMed, 45.02% of Cora, and 21.16% of CiteSeer neighborhoods. In contrast, ogbn-arxiv has higher neighborhood connectivity, with truncation occurring for 42.90% of first-hop and 90.21% of second-hop neighborhoods. Additionally, selecting first-hop neighbors determines which second-hop nodes become available, affecting the selected serialized context. These results show that our evaluation covers different levels of neighborhood truncation, allowing us to study serialization across datasets with diverse structural characteristics.

Table 1: Neighborhood truncation effect at each hop (K=10).

Dataset      First-hop (%)   Second-hop (%)
-------------------------------------------
PubMed            11.87           81.74
Cora               3.87           45.02
CiteSeer           2.51           21.16
ogbn-arxiv        42.90           90.21

4- Weakness 4:

As explicitly stated in our paper, Oracle is designed as a diagnostic that uses ground-truth labels to assess the availability of class-relevant information in the neighborhood, rather than a deployable serializer. Its purpose is mainly to investigate the potential value of class-relevant context for node classification. The performance gap between Oracle and practical deployed serializers highlights the challenge of identifying such information without access to ground-truth labels. Furthermore, the substantial performance drop when Oracle-trained models are tested on Random sequences reveals a potential trade-off between class-relevant information and robustness to serialization shifts. While Oracle achieves high accuracy under matched training and testing conditions, its strong dependence on label-conditioned sequences makes it sensitive to changes in the input distribution. This suggests that future label-aware selection methods should consider not only class relevance but also robustness across different serialization conditions. These findings support our conclusion that serialization is both an information-selection mechanism and part of the learned graph-to-LLM input distribution.

Reviewer_y3RyOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies how to select relevant neighbors for LLM predictors on graph tasks. It compares different selection strategies for node classification and link prediction. The research question is quite focused: keeping the entire framework unchanged and only varying the node selector. Though it makes some sense, the experiments are too narrow to support a meaningful and generalization conclusion.

Critical strengths

Using LLMs to address graph tasks is trending. At the core of this approach is the composition of the LLM context, i.e., which neighbors to include and how to represent them. This paper provides a focused study on the first part, making a timely and overall useful reseach topic.

Critical weaknesses
  1. The most significant concern is that the experiments are not sufficient to really answer the research question. The title asks "What Neighbors should an LLM See?" However, the paper fixes the LLaGA-based graph-to-LLM interface throughout the experiments, so all subsequent conclusions depend on this specific design. It is unclear how generalizable these conclusions are.

  2. Regarding novelty, the paper is below average. It mostly tests well-established selection criteria, such as semantic/structural similarities. From the results, random selection appears pretty strong in many settings, suggesting limited gains from more advanced strategies. The paper lacks deeper discussion and analysis of the results. It fails to provide some analyses, such as the overlap between contexts generated by different selectors.

  3. The presentation is also flawed. The paper has strong autoresearch cues, with obvious formatting issues (e.g., line 216 and the tables), and did not undergo careful proofreading. The writing is lengthy and lacks natural flow, and contains limited information.

Questions for authors

My questions are mostly mentioned in the weaknesses. To summarize,

  1. why sticking to LLaGA's setting everywhere? Did the authors try other approaches?

  2. what is the mechanism of LLM-based graph solver, in different graph tasks? How does the model utilize the provided context? Is there any deeper analysis such as representation/interpretation analysis?

  3. what are the real findings and insights? The draft lists a lot but I cannot see what the true insights are.

1 comment

We thank the reviewer for their feedback. We would like to clarify the motivation, experimental design, and main insights.

1- Weakness 1 and Question 1:

We adopted the LLaGA-based interface because it preserves the hierarchical structure of multi-hop graph neighborhoods, distinguishing between different-hop neighbors (first-hop, second-hop) while maintaining their structural relationship. Since our goal is to represent the graph neighborhoods as LLM inputs, preserving these relationships is important for capturing the original graph structure, just as preserving word order in text or spatial relationships in images helps retain important information. Additionally, our selection strategies operate independently at each hop, allowing controlled truncation while preserving the original neighborhood hierarchy. In contrast, flattening the neighborhood and selecting nodes globally could introduce bias towards certain nodes, regardless of their hop distance to the target (e.g., nodes with the highest degree only), potentially compromising the representation of the hierarchical relationships and influencing the model’s learning process.
We adopted LLaGA as the graph-to-LLM interface to isolate the effect of different neighborhood selection strategies on LLM-based graph learning, without introducing additional variation from using different interfaces.

2- Question 2:

As described in Section 3.1, the adopted framework converts the graph neighborhoods into a hierarchical sequence of node embeddings, which are then mapped into the LLM input space through a learned projector. For Node classification, the model receives the target node and its selected multi-hop neighborhood to predict its class. For link prediction, the model receives neighborhood information for the two candidate endpoints and predicts whether an edge exists between them. The complete graph-to-LLM interface is illustrated in Figure 3 (Appendix A.1).

The model processes the selected neighborhood embeddings alongside the task instruction. To investigate how the selected context affects the model performance, we evaluate the contribution of neighborhood information through center-only and endpoints-only baselines (Tables1 and 2), analyze the effectiveness of different serialization strategies and their task-dependent behavior (Sections 4.1- 4.3), investigate train-test serialization shifts (Section 4.4), and examine neighborhood availability (Section 4.5). While these analyses provide evidence of how neighborhood selection influences model performance, they do not directly explain the model’s internal representation or reasoning mechanisms, which are currently beyond the scope of this study.

3- Weakness 2 and Question 3:

Our contribution is not introducing a new neighborhood selection algorithm, but a systematic analysis of how different neighborhood contexts affect LLM-based graph learning. Our study covers two graph tasks, four datasets, two LLM backbones, and 10 practical serialization strategies with additional Oracle diagnostics. The results are organized around five research questions in Section 4, with the main findings discussed under each. We summarize the findings as follows:

1- No selection/serialization method universally dominates; structural selection benefits link prediction more consistently than node classification. Random selection remains competitive in some settings, indicating that more advanced selection methods do not consistently yield better predictive performance (RQ1).

2- Class-relevant context can substantially improve node classification performance, as demonstrated by the Oracle diagnostic, which highlights the gap between available class-relevant information and what practical selection strategies can recover (RQ2).

3- Serialization changes the structural characteristics of the selected neighborhoods, but selecting more structurally prominent nodes does not necessarily ensure label agreement or improve node classification performance (RQ2).

4- Pair-aware signals provide informative evidence for link prediction, but their availability is often limited, restricting their effectiveness in improving the overall model performance (RQ3).

5- Models co-adapt to their training-serialization distribution, resulting in sensitivity to train-test serialization shifts, especially for Oracle-trained models. In contrast, structurally trained models exhibit more robust performance under different test serializations (RQ4).

6- Ensuring sufficient neighborhood availability does not guarantee better performance, as the performance remains dataset- and task-dependent (RQ5).

We acknowledge that quantifying the overlap between the neighborhoods selected by different serializers could provide additional insights into their behavior.

4- Weakness 3: We appreciate the reviewer’s feedback. We acknowledge the formatting issues and will carefully revise the manuscript to address these inconsistencies.

Reviewer_2fWFOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

When a graph neighborhood is passed to an LLM, only a limited number of neighbors fit in the input. This paper asks which neighbors should fill those slots. Keeping the LLaGA graph-to-LLM interface fixed, it compares random, structural, text-similarity, class-relevance and common-neighbor selectors, plus a label-informed "Oracle", on four citation graphs. It concludes that no selector dominates, random selection is competitive, the Oracle reveals a large gap on ogbn-arxiv (76% → 92%), and models adapt to whatever serialization they were trained on.

Critical strengths
  • A clean single-variable design. Because nothing else changes, any accuracy difference can be attributed to the selector. This makes the comparison easy to interpret.

  • Informative controls and diagnostics. The no-neighbor rows show how much neighbors matter at all, and the swaps show whether a model depends on the order it was trained on.

Critical weaknesses
  • It is not clear that the experimental setup poses the paper's question. If all of a node's neighbors already fit, the selectors can only change their order, not which neighbors the model sees. How often does K = 10 actually cut any neighbors, and why not use the full neighborhood when it fits easily within 4096 tokens?

  • The evidence that the Oracle measures unused class-relevant context is not strong enough. If the Oracle always puts same-label neighbors first, a model can learn to read the answer from the order. Does the Oracle still help a model that was never trained on Oracle sequences?

Questions for authors
  • For what fraction of targets and anchors does K = 10 actually truncate the neighborhood, on each dataset?
  • Could we have an ablation study on the number of truncated neighborhoods, from a smaller K (e.g. 2-5) to no-truncation reference (the full two-hop neighborhood or a K large enough to cover it)?
1 comment

We thank the reviewer for their feedback and for highlighting the value of our controlled systematic analysis. Below, we address the reviewer’s concerns and provide clarifications regarding the identified weaknesses and questions.

1- Weakness 1 and Question 1:

We clarify that our adopted Graph-to-LLM interface uses a fixed two-hop hierarchical representation with a branching budget K=10, corresponding to 1 (target node) + 10 (first-hop neighbors) + 100 (second-hop neighbors) = 111 node-token positions, with padding when necessary. When neighborhoods exceed K, serialization strategies are used to determine which neighbors to select. We deliberately selected datasets with varying graph structures and degree distributions to capture the extent of truncation on neighborhood selection. While complete 2-hop neighborhoods are generally manageable for PubMed, CiteSeer, and Cora, ogbn-arxiv has substantially larger neighborhoods, with a median of 1,367 and a 90th percentile of 26,217 node tokens, exceeding the input token context limit. Therefore, we adopted a fixed hierarchical neighborhood budget to maintain a consistent graph-to-LLM interface and isolate the effect of neighborhood selection/serialization across different datasets. Most importantly, truncation occurs hierarchically at both hops. Even when a target node has fewer than 10 first-hop neighbors, its first-hop neighbors (anchors) may require truncation at the second hop. To quantify this, we report the percentage of test examples affected by truncation at each hop: Table 1: Neighborhood truncation effect at each hop (K=10).

Dataset      First-hop (%)   Second-hop (%)
-------------------------------------------
PubMed            11.87           81.74
Cora               3.87           45.02
CiteSeer           2.51           21.16
ogbn-arxiv        42.90           90.21

These results confirm that neighborhood selection is relevant, particularly at the second hop, where truncation affects 21.16%-90.21% of neighborhoods across the tested datasets. Therefore, graph neighborhood serialization not only reorders neighbors but also determines which neighborhood information and context are exposed to the LLM.

2- Weakness 2:

The Oracle is explicitly designed as a label-informed diagnostic to evaluate the potential benefit of class-relevant neighborhood selection, rather than a deployable strategy. The big performance improvement achieved by Oracle indicates that it is important to select neighbors that share the same label as the target node (in the Node Classification Task). However, these improvements were not matched by any tested practical serialization method, highlighting the gap in identifying class-relevant neighborhood information. Additionally, the generalization experiments (Tables 9-10) show that models are sensitive to their training serialization method and can co-adapt to their training distribution. On ogbn-arxiv, switching from Oracle during training to Random selection for testing reduced the accuracy from 0.9237% to 0.5454% for Vicuna and from 0.9281% to 0.5548% for Qwen. These findings motivate the future development of label-aware serialization strategies that effectively identify class-relevant neighbors while remaining robust to train-test serialization shifts.

3- Question 2:

We agree that evaluating different branching factors (K) would provide additional insights into how neighborhood size affects model performance. In this study, we fix K=10 to focus on comparing serialization strategies under a fixed neighborhood budget. Our center-only and endpoints-only controls in Tables 1 and 2, respectively, quantify the contribution of neighborhood information, where only the target node/endpoints embeddings are fed to the model with padding. While these controls establish a no-neighborhood baseline, they do not replace a systematic K-ablation. Regarding the no-truncation reference, the full 2-hop neighborhoods can exceed the model’s input token limit, particularly on ogbn-arxiv, making this setting infeasible for all examples.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.