Semantic Refinement with LLMs for Graph Representations

1. Problem Definition

The paper addresses the fundamental challenge of structure–semantics heterogeneity in graph-structured data.

• The Core Issue: Real-world graphs vary significantly in where their predictive signals originate.
  • Semantics-heavy domains: (e.g., citation networks) rely on node attributes (titles, abstracts) for classification, with structure serving as a scaffold.
  • Structure-heavy domains: (e.g., molecular graphs, transportation networks) rely on topological patterns (motifs, connectivity) because semantic attributes are weak or absent.
• The Limitation of Existing Methods: Current approaches are model-centric. They attempt to solve this by designing GNNs with fixed inductive biases (e.g., homophily, locality) or by injecting external biases via auxiliary models/LLMs.
  • Failure Mode: A model with a fixed bias cannot generalize optimally across domains with drastically different signal distributions. If the model's bias (e.g., favoring structure) mismatches the data's reality (e.g., semantics-driven), performance degrades.
• The Gap: Existing LLM-enhanced methods often generate node descriptions without considering the specific graph context or the model's current predictive state, leading to generic refinements that may not align with the task.

2. Methodology: Graph-Exemplar-guided Semantic Refinement (GES)

The authors propose GES, a data-centric framework that treats node semantics as a task-adaptive variable rather than a static input. Instead of changing the model architecture, GES refines the input node descriptions based on the graph's specific structure and the model's behavior.

The pipeline consists of four main stages:

A. Structure-Aware Initial Node Semantics

To unify semantic and structural cues, the framework converts graph topology into natural language:

• For Text-Attributed Graphs: Concatenates original node text with a structural summary.
• For Text-Free Graphs: Generates a structural summary from scratch.
• Structural Features: Computes topological statistics (degree, betweenness, closeness, clustering coefficient, square clustering coefficient) and converts them into percentile ranks to normalize scale. These are verbalized into a concise text summary.

B. Model-Conditioned Memory Construction

A GNN is first trained on the initial descriptions to produce a "predictive state."

• Memory ($B$): Stores a triple for each node $v$: $(d_v, s_v, p_v)$, where:
  • $d_v$: Current textual description.
  • $s_v$: Structural embedding (via struc2vec) capturing topological role.
  • $p_v$: Predictive distribution (softmax output) from the GNN.
• This memory explicitly captures the interaction between semantics, structure, and the model's current confidence.

C. Memory Retrieval (Exemplar Selection)

For each target node, GES retrieves a set of in-graph exemplars ($S_v$) to guide refinement. The retrieval is based on a joint similarity score:
$$S(v, u) = \alpha \cdot \text{sim}_{text}(v, u) + (1-\alpha) \cdot \text{sim}_{struct}(v, u)$$

• Filtering: Candidates are filtered by predictive entropy. Only nodes with low entropy (high confidence) in the current model are selected.
• Adaptability: The trade-off parameter $\alpha$ allows the system to adapt: emphasizing text for citation networks and structure for airport networks.

D. LLM-Guided Semantic Refinement

An LLM acts as a conditional refinement operator:

• Input: The target node's current description + the retrieved exemplar set ($S_v$).
• Task: The LLM is instructed to reweight and compress the description, emphasizing discriminative cues indicated by the exemplars, rather than expanding knowledge.
• Output: A refined description $d'_v$ that is better aligned with the graph's structure-semantics regime.
• Final Step: The refined descriptions are re-encoded, and a final GNN is trained for evaluation.

3. Key Contributions

1. Data-Centric Perspective: Shifts the adaptation burden from the model (inductive bias) to the data (node semantics), treating semantics as dynamic variables responsive to task feedback.
2. Exemplar-Guided Mechanism: Introduces a novel retrieval mechanism that selects in-graph exemplars based on joint semantic-structural similarity and model confidence, ensuring the LLM refines descriptions using reliable, context-aware references.
3. Unified Framework for Heterogeneous Graphs: Successfully handles both text-rich (citation) and text-free (molecular/transport) graphs without architectural changes, demonstrating that the balance between structure and semantics can be managed at the representation level.
4. Theoretical Insight: Provides an analysis showing that GES reduces the variance within class embeddings (prototype alignment), thereby increasing the discriminability gap between classes.

4. Experimental Results

The framework was evaluated on five datasets: Cora, Pubmed (text-attributed) and USA, Europe, Brazil (text-free airport networks).

• Performance Gains:
  • Text-Attributed: GES consistently outperformed strong baselines (including TANS, KEA, TAPE) across GCN, GAT, and MLP backbones. On Cora (low-label), it achieved 82.40% vs. TANS's 80.66%.
  • Text-Free: GES significantly outperformed structural baselines (Node Degree, Eigenvector, Random Walk) and TANS. On the Brazil airport network, it achieved 80.91% (low-label) vs. TANS's 80.61%, and 75.19% (high-label) vs. TANS's 71.60%.
• Low-Label Regime: GES showed the most significant improvements in low-resource settings (e.g., 5-10 labels per class), where input feature quality is critical. It outperformed TANS by an average of +2.16% in these scenarios.
• Domain Adaptation & Transfer:
  • Cross-Graph: In domain adaptation (training on one graph, testing on another without fine-tuning), GES achieved the best results in most transfer directions, particularly for challenging transfers involving the Brazil network.
  • Pretrain-Finetune: In transfer learning between Cora and Pubmed, GES improved accuracy by +3.66% (Cora $\to$ Pubmed) over TANS.
• Ablation Studies:
  • Retrieval Strategy: Joint semantic-structural retrieval outperformed text-only or structure-only retrieval, proving the necessity of the hybrid approach.
  • LLM Robustness: Results remained consistent when swapping GPT-4o-mini for the open-weight Gemma-3-12B, confirming the gains come from the retrieval/refinement mechanism, not just the LLM's capacity.
• Cost: The method incurs a single LLM inference pass per node. While token overhead is non-trivial (e.g., +16.8M tokens for Pubmed), the accuracy gains (up to +3.59% on Brazil) justify the cost in high-stakes or low-resource scenarios.

5. Significance and Conclusion

• Paradigm Shift: The paper challenges the prevailing "model-centric" approach to graph learning. It demonstrates that adapting the input representation to the specific structure-semantics regime of a graph is more effective than trying to build a universal model architecture.
• Practical Impact: GES provides a plug-and-play module that can improve any downstream GNN without retraining the architecture, making it highly versatile for diverse real-world applications ranging from social networks to molecular discovery.
• Limitations: The method requires one LLM pass over all nodes (computational cost) and relies on the quality of the underlying LLM. Future work could explore refining only uncertain nodes to improve scalability.

In summary, GES effectively bridges the gap between structural and semantic graph learning by using a model-conditioned memory to guide LLMs in refining node descriptions, resulting in robust, task-adaptive representations that generalize across diverse graph domains.