💬 NLP

TERGAD: Structure-Aware Text-Enhanced Representations for Graph Anomaly Detection

TERGAD is a novel graph anomaly detection framework that leverages Large Language Models to translate node topological properties into semantic narratives, which are then fused with original attributes via a gated dual-branch autoencoder to effectively identify anomalies arising from inconsistencies between a node's content and its structural role.

Original authors: Wen Shi, Zhe Wang, Huafei Huang, Qing Qing, Ziqi Xu, Qixin Zhang, Xikun Zhang, Renqiang Luo, Feng Xia

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wen Shi, Zhe Wang, Huafei Huang, Qing Qing, Ziqi Xu, Qixin Zhang, Xikun Zhang, Renqiang Luo, Feng Xia

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a security guard trying to spot a spy in a crowded city. In a normal city, you might look for people wearing strange clothes (bad attributes) or people standing in weird spots where no one else stands (bad structure).

But what if the spy is wearing a perfect disguise and standing in a crowd? They look normal on the surface, but their role in the crowd is suspicious. Maybe they are the only person connecting two groups that shouldn't talk to each other, or they are standing in the middle of a tight-knit club while pretending to be an outsider. Traditional security cameras (old computer models) often miss these spies because they only look at the clothes or the map, not the story of how the person fits into the city.

This paper introduces TERGAD, a new security system that solves this problem by using a "super-smart translator" (a Large Language Model, or LLM) to turn the city's map into a story.

Here is how it works, step-by-step:

1. Turning Maps into Stories (The Translator)

Traditional models look at a graph (a network of dots and lines) as just numbers. TERGAD asks a super-smart AI to read the map and write a short, natural language story about every single person in the city.

Instead of: "Node 42 has 1,200 connections and is in the 99th percentile."
The AI writes: "Node 42 is a super-connected hub, standing in the top 1% of the city. It acts as a critical bridge between two neighborhoods and is deeply embedded in a tight-knit community."

By turning cold numbers into a story, the AI can understand the meaning of a person's position, not just the math.

2. The Two-Headed Detective (The Dual-Branch System)

Once the AI has these stories, TERGAD uses a special "two-headed" detective system to find the bad guys:

Head A (The Original Data): This head looks at the person's actual file (their real attributes, like their job or bio).
Head B (The Story): This head looks at the new "story" the AI wrote about their role in the city.

3. The Smart Gatekeeper (The Gated Fusion)

Here is the clever part. Sometimes the story is more important; sometimes the original file is more important.

If a person's file looks normal, but the story says, "This person is a bridge between rival gangs," the system knows to trust the story.
If the story is vague but the file shows a suspicious bank account, the system trusts the file.

TERGAD uses a smart gate that decides, for every single person, how much weight to give the story versus the original file. It blends them together perfectly.

4. The "Reconstruction" Test (Spotting the Spy)

Finally, the system tries to rebuild the city using this blended information.

If the system can easily rebuild a person's profile and their connections, they are likely normal.
If the system struggles to rebuild them (because their story and their file don't match up, or they don't fit the pattern), the system flags them as an anomaly.

Why is this better?

The authors tested this on six real-world networks (like citation networks where papers link to each other, and social networks). They found that:

Old methods (which just look at numbers) often miss spies who are good at hiding in plain sight.
Using the LLM to write stories helped the system understand the context of the connections.
The new system (TERGAD) was consistently better at finding the "spies" than all the other top methods.

A Note on the "Super-Smart Translator"

The paper also tested if you could just ask the LLM to be the security guard directly (without the two-headed system). The result? The LLM alone was terrible at it. It's like giving a brilliant novelist a map and asking them to find a spy without any tools—they get lost in the details. The LLM works best when used as a tool to create better descriptions, which are then fed into a specialized detective system.

In short: TERGAD doesn't just look at the dots and lines; it asks an AI to tell the story of what those dots and lines mean, and then uses that story to catch the anomalies that others miss.

Technical Summary: TERGAD

Problem Statement
Graph Anomaly Detection (GAD) aims to identify atypical nodes, edges, or substructures that deviate from majority patterns. While deep learning approaches have advanced GAD, many real-world graphs suffer from "text-poor" or purely structural characteristics, lacking rich descriptive attributes. Existing text-rich approaches often integrate structural context using raw textual features but neglect the structural context of nodes themselves. This limitation hinders the detection of sophisticated anomalies arising from inconsistencies between a node's inherent content and its topological role (e.g., a node acting as a malicious bridge despite having normal attributes). Furthermore, preliminary studies indicate that vanilla Large Language Models (LLMs) struggle to grasp underlying structural anomalies in a zero-shot setting, significantly lagging behind Graph Convolutional Network (GCN)-based models. The core challenge lies in effectively translating abstract graph topology into semantically rich representations and integrating them with graph learning models without incurring prohibitive computational costs or losing structural fidelity.

Methodology: TERGAD
The authors propose TERGAD (Structure-aware Text-Enhanced Representations for Graph Anomaly Detection), a framework that bridges raw structural information and LLM-based semantic reasoning through a data augmentation pipeline. The methodology consists of four primary phases:

Graph-to-Text Conversion (Semantic Enrichment):
The framework transforms raw graph inputs into node-level natural language descriptions using a structured prompting template. This process encodes global statistics (node/edge counts), degree distributions, high-order topological features (clustering coefficients, k-core numbers, centrality measures), and community structures into fluent, human-interpretable narratives. For example, a node's degree is contextualized relative to global percentiles (e.g., "top 1% of all nodes"), and its role (hub, bridge, peripheral) is explicitly assigned based on heuristic thresholds. Crucially, node indices serve only as persistent identifiers to maintain cross-modal alignment without leaking test-set information.
LLM-Based Semantic Embedding:
The generated natural language descriptions are processed by a pre-trained LLM (specifically BGE-large-en-v1.5) to derive high-level semantic embeddings ( $Z_{LLM}$ ). The authors employ last-token pooling for sentence representation and apply Z-score standardization across all nodes and dimensions to align the statistical distribution of these embeddings with typical preprocessed graph features, ensuring stability in downstream training.
Dual-Branch Gated Autoencoder:
The core architecture is a dual-branch autoencoder that processes two complementary inputs: the original node attributes ( $X$ ) and the LLM-derived semantic embeddings ( $Z_{LLM}$ ).
- Branches: Two parallel Graph Convolutional Network (GCN) branches independently aggregate neighborhood information for the attribute branch and the semantic branch.
- Gated Fusion: A learnable gating mechanism adaptively fuses the latent representations from both branches. The gate ( $G$ ) dynamically determines the contribution of each branch for every node and feature dimension, allowing the model to balance raw structural data with LLM-informed semantic priors based on the specific context of each node.
- Reconstruction: A shared decoder reconstructs both the original node attributes and the graph adjacency matrix from the fused latent representation.
Anomaly Scoring:
The anomaly score for each node is computed based on the integrated reconstruction error. It combines the error in reconstructing the adjacency matrix (structural deviation) and the error in reconstructing the node attributes (attribute deviation), weighted by a hyperparameter $\alpha$ . High scores indicate significant deviations from the learned normal patterns in both observable attributes and LLM-informed semantic expectations.

Key Contributions

Construction of Text-Rich Graphs: The paper introduces a systematic pipeline to transform purely structural graphs into text-rich representations by translating topological metrics into natural language, addressing attribute sparsity.
Semantic-Guided Encoding and Adaptive Fusion: A structured template-based approach encodes topological roles via LLMs, coupled with a gated dual-branch autoencoder. This allows for the selective integration of high-level semantic priors with raw structural data, avoiding premature fusion.
Empirical Validation: Comprehensive experiments on six real-world datasets (Cora, Citeseer, DBLP, ACM, Pubmed, BlogCatalog) demonstrate the framework's effectiveness.

Experimental Results
TERGAD was evaluated against nine state-of-the-art baselines, including reconstruction-based methods (MLPAE, GCNAE, DOMINANT, AnomalyDAE), generative/contrastive models (GAAN, CoLA), and other advanced approaches (GADNR, FIAD, AHFAN).

Performance: TERGAD consistently outperformed all baselines across all six datasets in terms of ROC-AUC and PR-AUC. Notable results include 98.03% ROC-AUC on Pubmed, 97.72% on DBLP, and 95.78% on Citeseer.
Ablation Studies:
- Removing the structured prompting strategy ("w/o Prompt") caused significant performance drops (e.g., ~17% on Cora), validating the necessity of translating topology into role-based natural language.
- Removing the gated fusion mechanism ("w/o Gate") led to suboptimal performance, highlighting the need for adaptive balancing between modalities.
- Fine-grained ablation of prompt components (degree, k-core, centrality, etc.) showed that all structural descriptors contribute positively, with k-core decomposition and centrality measures being particularly critical.
- Different LLMs (Qwen3, nomic-embed) were tested, confirming that while various models work, BGE-large-en-v1.5 provided the best alignment for this task.
- Prompt order analysis revealed that the model is robust to the syntactic ordering of structural facts, though narrative-style prompts outperformed structured profile-style templates.
Efficiency: While LLM embedding generation incurs a one-time preprocessing cost, the training phase of TERGAD is competitive, significantly faster than complex baselines like GAAN and DOMINANT on larger datasets, and maintains reasonable memory usage.

Significance and Claims
The paper claims that TERGAD establishes a vital connection between raw structural information and LLM-based semantic reasoning, effectively empowering structural graph learning. The significance of the work lies in its ability to detect sophisticated anomalies that arise from inconsistencies between a node's content and its topological role—nuances often missed by numerical feature engineering. By demonstrating that LLMs alone cannot reliably detect graph anomalies (as shown in the preliminary zero-shot study) but can serve as powerful semantic augmentation modules when integrated via a gated architecture, the paper proposes a novel perspective for GAD. It validates that transforming abstract topology into descriptive text allows models to leverage the reasoning capabilities of LLMs for structural understanding, leading to robust detection in attribute-poor networks. The framework is presented as a flexible, plug-and-play solution that requires no LLM fine-tuning.