Graph-LLM Template Injection

Description: A vulnerability exists in the graph encoding architecture of LLaGA (Large Language and Graph Assistant), specifically within the "neighborhood detail template" used to construct node sequences. LLaGA enforces a fixed-shape computational tree for each node; when a target node has fewer neighbors than the required template size (e.g., $k$ children), the system utilizes placeholders to maintain the fixed structure.

Attackers can exploit this design via Node Sequence Template Injection. By manipulating the graph structure (adding edges or nodes), an adversary can force malicious or irrelevant nodes (such as high-degree "supernodes") to be selected by the sampling algorithm to fill these placeholder slots. This injection corrupts the node sequence embedding generated by the linear projector, leading to severe performance degradation and misclassification during both training (poisoning) and inference (evasion). Additionally, the model is vulnerable to imperceptible feature perturbation attacks (Homoglyphs and Reordering control characters) on textual node attributes, which bypass standard structural defenses.

Examples: To reproduce the Supernode Injection (SI) attack against an LLaGA model:

1. Identify Target: Select a target node $u$ in the graph that has a node degree lower than the template size $k$ (e.g., $k=10$).
2. Select Malicious Node: Identify or insert a high-degree "supernode" $v$ within the graph that is not currently in the 1-hop neighborhood of $u$.
3. Structural Manipulation: Modify the graph structure (e.g., via standard evasion techniques like MetaAttack or manual edge insertion) to increase the probability that node $v$ is sampled as a placeholder neighbor for node $u$ during the template construction phase.
4. Execution: Query the LLaGA model for the classification of node $u$. The model constructs the node sequence, injecting node $v$ into the placeholder slot.
5. Observation: The inclusion of the uninformative or adversarial supernode $v$ alters the resulting embedding, causing the LLM to misclassify node $u$.

Note: See "Algorithm 1: Node Sequence Template Injection Attack" in Appendix A.4 of the reference paper for the specific algorithmic implementation.

Impact:

• Model Evasion: Attackers can force misclassification of specific nodes with high success rates. In testing, the Multiple Supernode Injection (MSI) evasion attack reduced accuracy on the Cora dataset from ~0.89 to 0.30.
• Integrity Loss: The vulnerability undermines the reliability of graph-aware LLMs in critical applications such as fraud detection, recommendation systems, and social network analysis.
• Poisoning: If injected during training, these perturbations can permanently degrade the learned projector's ability to generalize.

Affected Systems:

• LLaGA (Large Language and Graph Assistant)
• Graph-aware LLMs utilizing fixed-length node sequence templates with placeholder filling mechanisms.

Mitigation Steps:

• Deploy GaLGuard: Implement the GaLGuard end-to-end defense framework, which combines feature correction and structural purification.
• LLM-based Feature Correction: Utilize an LLM acting as a linguistic validator to detect and correct anomalous patterns in textual node features (e.g., homoglyphs or reordering characters) before they are processed by the graph encoder.
• Graph Purification: Implement a preprocessing step that computes cosine similarity between a node's embedding and its neighbors' embeddings. Prune edges with low similarity to prevent the inclusion of malicious placeholders in the computational tree.
• Global Structural Context: Incorporate a learnable global structural context embedding ($M_{global}$) into the projector and jointly train it with the purified node sequence to improve resilience against structural perturbations.