TL;DR
This paper introduces STLSP, a novel framework that combines the structural understanding of Graph Neural Networks (GNNs) with the linguistic capabilities of Large Language Models (LLMs) to predict the sign (positive or negative) of links in signed networks. By transforming graph structures into natural language descriptions, STLSP significantly improves prediction accuracy and reliability, outperforming existing methods by an average of 8.7%.
What Problem Does This Paper Address?
Signed networks are crucial for modeling complex relationships in real-world systems, such as social interactions or user preferences. A key task in this domain is Link Sign Prediction (LSP), which aims to determine whether a link between two entities is positive (e.g., friendship) or negative (e.g., animosity). While existing methods primarily rely on graph structures, they often overlook the rich textual information associated with these links, which can provide vital clues for accurate prediction. Furthermore, directly applying LLMs to graph data is challenging due to their inherent difficulty in processing topological information and potential reliability issues. This paper addresses the gap of effectively integrating both structural and textual information for LSP, while also enhancing the reliability of LLM-based predictions.
Methods
STLSP is built upon three core modules:
- Graph Divider: This module splits the graph data into training and testing sets. It employs an edge-masking strategy that ensures all nodes in the test set are present in the training set to avoid isolated nodes.
- Embedding Trainer: This module leverages structural balance theory to generate node embeddings. This theory posits that triads are balanced if all edges are positive ("friend of a friend is my friend") or if one edge is positive and two are negative ("enemy of my enemy is my friend"). The module trains embeddings by minimizing the distance between positively connected nodes and maximizing the distance between negatively connected nodes, up to a certain threshold. This process transforms structural information into a format that can be clustered. A K-means clustering algorithm is then used to group nodes based on these embeddings.
- LLM Predictor: This module bridges the gap between structural information and LLMs.
- Structural Information Processing: The cluster labels generated in the previous step are converted into natural language descriptions (e.g., "nodes are in the same balanced structure"). This, along with the edge's textual data, forms the contextual input for the LLM.
- Prompt Design: A carefully crafted prompt is designed to guide the LLM. This prompt includes explicit instructions for output format (only "1" or "-1"), the textual description of the edge, and the natural language representation of the structural relationship derived from clustering. A specific weight ratio (7:3) is assigned to balance the influence of structural and textual information.
Datasets
The paper evaluates STLSP on five real-world datasets:
- wiki-rfa
- amazon_software
- amazon_office
- amazon_video
- amazon_crafts
These datasets are split into training and testing sets with an 8:2 ratio, a common configuration for LSP tasks.
Key Insights and Ideas
- Bridging the Modality Gap: The core innovation is transforming graph structural information into natural language representations that LLMs can effectively process. This overcomes a major limitation of LLMs in graph-related tasks.
- Structural Balance Theory as a Foundation: The paper effectively utilizes structural balance theory not just for understanding relationships but also for guiding the generation of meaningful node embeddings that capture positive and negative interactions.
- Enhanced Reliability: By integrating structural information into the LLM's prompt, STLSP significantly improves the reliability of LLM predictions, reducing errors even when the LLM's internal confidence might be low.
- LLM Agnosticism: STLSP demonstrates robustness across various LLMs, including smaller, open-source models like Llama3-7B, suggesting its practical applicability without requiring massive computational resources.
Key Results
- STLSP outperforms state-of-the-art baselines by an average of 8.7% in accuracy across five real-world datasets.
- On the amazon_software dataset, STLSP achieved a 12.4% improvement in accuracy over the best-performing baseline (SDGNN).
- When textual information was removed (STLSP_w/o_text), the accuracy dropped significantly, by up to 48.1% on the amazon_software dataset, highlighting the crucial role of text.
- STLSP shows strong performance across different LLMs, including GPT-40, Gemma-7B, Llama3-7B, and Mistral-7B, indicating its adaptability.
Limitations and Future Work
- Clustering Parameter Sensitivity: The paper notes that STLSP performs well with K=2 or K=3 for clustering, which is influenced by the strength of structural balance theory. However, the optimal K might vary across different datasets.
- Prompt Engineering: While the paper designs a tailored prompt, there's potential for further refinement using more advanced prompt engineering techniques to enhance LLMs' ability to understand and infer signed links.
- Computational Cost: While STLSP works with smaller LLMs, the overall process involving GNNs and LLMs can still be computationally intensive. Future work could focus on optimizing this efficiency.
Summary updated