Large Language Model-driven Meta-structure Discovery in Heterogeneous
  Information Network
Lin Chen Fengli Xu Nian Li Zhenyu Han Meng Wang Yong Li Pan Hui
Heterogeneous information networks (HIN) have gained increasing popularity
for being able to capture complex relations between nodes of diverse types.
Meta-structure was proposed to identify important patterns of relations on HIN,
which has been proven effective for extracting rich semantic information and
facilitating graph neural networks to learn expressive representations.
However, hand-crafted meta-structures pose challenges for scaling up, which
draws wide research attention for developing automatic meta-structure search
algorithms. Previous efforts concentrate on searching for meta-structures with
good empirical prediction performance, overlooking explainability. Thus, they
often produce meta-structures prone to overfitting and incomprehensible to
humans. To address this, we draw inspiration from the emergent reasoning
abilities of large language models (LLMs). We propose a novel REasoning
meta-STRUCTure search (ReStruct) framework that integrates LLM reasoning into
the evolutionary procedure. ReStruct uses a grammar translator to encode
meta-structures into natural language sentences, and leverages the reasoning
power of LLMs to evaluate semantically feasible meta-structures. ReStruct also
employs performance-oriented evolutionary operations. These two competing
forces jointly optimize for semantic explainability and empirical performance
of meta-structures. We also design a differential LLM explainer that can
produce natural language explanations for the discovered meta-structures, and
refine the explanation by reasoning through the search history. Experiments on
five datasets demonstrate ReStruct achieve SOTA performance in node
classification and link recommendation tasks. Additionally, a survey study
involving 73 graduate students shows that the meta-structures and natural
language explanations generated by ReStruct are substantially more
comprehensible.