# Large Language Model-driven Meta-structure Discovery in Heterogeneous Information Network

arXiv: https://arxiv.org/abs/2402.11518 · HTML: https://mlsanity.com/paper/2402.11518/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 18 Feb 2024.

## Builds on (most cited first, 23 of 23)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [EvoPrompt: Connecting LLMs with Evolutionary Algorithms Yields Powerful Prompt Optimizers](https://mlsanity.com/paper/2309.08532/) (2023)
- [Heterogeneous Information Network Embedding for Recommendation](https://mlsanity.com/paper/1711.10730/) (2017)
- [GraphText: Graph Reasoning in Text Space](https://mlsanity.com/paper/2310.01089/) (2023)
- [A Survey of Heterogeneous Information Network Analysis](https://mlsanity.com/paper/1511.04854/) (2015)
- [Graph Foundation Models: Concepts, Opportunities and Challenges](https://mlsanity.com/paper/2310.11829/) (2023)
- [Large Language Model Agent for Hyper-Parameter Optimization](https://mlsanity.com/paper/2402.01881/) (2024)
- [Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks](https://mlsanity.com/paper/2104.07886/) (2021)
- [DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2010.03250/) (2020)
- [Graph Meets LLMs: Towards Large Graph Models](https://mlsanity.com/paper/2308.14522/) (2023)
- [Leveraging Meta-path Contexts for Classification in Heterogeneous Information Networks](https://mlsanity.com/paper/2012.10024/) (2020)
- [Genetic Meta-Structure Search for Recommendation on Heterogeneous Information Network](https://mlsanity.com/paper/2102.10550/) (2021)
- [Adversarial Text Purification: A Large Language Model Approach for Defense](https://mlsanity.com/paper/2402.06655/) (2024)
- [Automatic Meta-Path Discovery for Effective Graph-Based Recommendation](https://mlsanity.com/paper/2112.12845/) (2021)
- [Differentiable Meta Multigraph Search with Partial Message Propagation on Heterogeneous Information Networks](https://mlsanity.com/paper/2211.14752/) (2022)
- [Similarity Modeling on Heterogeneous Networks via Automatic Path Discovery](https://mlsanity.com/paper/1910.01448/) (2019)

## Built on by (most cited first, 16 of 16)

- [AgentSquare: Automatic LLM Agent Search in Modular Design Space](https://mlsanity.com/paper/2410.06153/) (2024)
- [FingerTip 20K: A Benchmark for Proactive and Personalized Mobile LLM Agents](https://mlsanity.com/paper/2507.21071/) (2025)
- [Design Principle Transfer in Neural Architecture Search via Large Language Models](https://mlsanity.com/paper/2408.11330/) (2024)
- [HLM-Cite: Hybrid Language Model Workflow for Text-based Scientific Citation Prediction](https://mlsanity.com/paper/2410.09112/) (2024)
- [AgentSwift: Efficient LLM Agent Design via Value-guided Hierarchical Search](https://mlsanity.com/paper/2506.06017/) (2025)
- [Fate: Fast Edge Inference of Mixture-of-Experts Models via Cross-Layer Gate](https://mlsanity.com/paper/2502.12224/) (2025)
- [Route-and-Reason: Scaling Large Language Model Reasoning with Reinforced Model Router](https://mlsanity.com/paper/2506.05901/) (2025)
- [AgentSociety Challenge: Designing LLM Agents for User Modeling and Recommendation on Web Platforms](https://mlsanity.com/paper/2502.18754/) (2025)
- [HoneyTrap: Deceiving Large Language Model Attackers to Honeypot Traps with Resilient Multi-Agent Defense](https://mlsanity.com/paper/2601.04034/) (2026)
- [SEKI: Self-Evolution and Knowledge Inspiration based Neural Architecture Search via Large Language Models](https://mlsanity.com/paper/2502.20422/) (2025)
- [AGRAG: Advanced Graph-based Retrieval-Augmented Generation for LLMs](https://mlsanity.com/paper/2511.05549/) (2025)
- [Transferrable Surrogates in Expressive Neural Architecture Search Spaces](https://mlsanity.com/paper/2504.12971/) (2025)
- [Token Signature: Predicting Chain-of-Thought Gains with Token Decoding Feature in Large Language Models](https://mlsanity.com/paper/2506.06008/) (2025)
- [Towards Efficient Few-shot Graph Neural Architecture Search via Partitioning Gradient Contribution](https://mlsanity.com/paper/2506.01231/) (2025)
- [CrimeMind: Simulating Urban Crime with Multi-Modal LLM Agents](https://mlsanity.com/paper/2506.05981/) (2025)
- [Grounded Skill Synthesis from Code at Scale for Agentic Intelligence](https://mlsanity.com/paper/2609.05571/) (2026)

## Abstract (arXiv)

Heterogeneous information networks (HIN) have gained increasing popularity in recent years for capturing complex relations between diverse types of nodes. Meta-structures are proposed as a useful tool to identify the important patterns in HINs, but hand-crafted meta-structures pose significant challenges for scaling up, drawing wide research attention towards developing automatic search algorithms. Previous efforts primarily focused on searching for meta-structures with good empirical performance, overlooking the importance of human comprehensibility and generalizability. To address this challenge, we draw inspiration from the emergent reasoning abilities of large language models (LLMs). We propose ReStruct, a meta-structure search framework that integrates LLM reasoning into the evolutionary procedure. ReStruct uses a grammar translator to encode the meta-structures into natural language sentences, and leverages the reasoning power of LLMs to evaluate their semantic feasibility. Besides, ReStruct also employs performance-oriented evolutionary operations. These two competing forces allow ReStruct to jointly optimize the semantic explainability and empirical performance of meta-structures. Furthermore, ReStruct contains a differential LLM explainer to generate and refine natural language explanations for the discovered meta-structures by reasoning through the search history. Experiments on eight representative HIN datasets demonstrate that ReStruct achieves state-of-the-art performance in both recommendation and node classification tasks. Moreover, a survey study involving 73 graduate students shows that the discovered meta-structures and generated explanations by ReStruct are substantially more comprehensible. Our code and questionnaire are available at https://github.com/LinChen-65/ReStruct.