Enhancing stability of node labeling in directed graphs via strong-ties

Abstract

Ensuring node labeling stability is critical for graph-based learning systems, directly impacting trust evaluation, node classification, and structure-aware inference in complex relational domains. Traditional manual annotation is costly and inconsistent, necessitating automated alternatives such as Large Language Models (LLMs). However, while LLM-assisted annotation improves efficiency, the reliability of node labeling remains a concern due to structural biases, particularly in unsupervised and semi-supervised learning settings. This dissertation systematically investigates the role of strong-tie structures in stabilizing label predictions across different node labeling paradigms, examining their influence on unsupervised trust prediction, defense against poisoning attacks in graph neural networks (GNNs), and LLM-based annotation. First, we analyze how strong-tie structures influence unsupervised trust prediction in decentralized systems and financial networks. Our study reveals that trust annotation propagates preferentially along strong ties, making it susceptible to targeted adversarial manipulations. By strategically modifying a minimal number of edges, an attacker can significantly alter trust/untrust label assignments, exposing vulnerabilities in existing trust prediction frameworks. Our analysis reveals that strong-tie structures are preferentially exploited by adversarial agents. Understanding these patterns provides deeper insight into the structural vulnerabilities of trust prediction systems and offers a basis for evaluating the robustness of different algorithms. Next, we extend our investigation to structural poisoning attacks in semi-supervised learning. Our findings show that poisoning behaviors exhibit clear structural preferences, targeting specific strong-tie patterns to maximize their impact on label propagation. This motivates our proposed Graph Adaptive Neural Network (GANN) framework, which dynamically adjusts propagation mechanisms based on fuzzy-theoretic strong-tie graphs (STiG). By integrating adaptive trust and risk zones, GANN mitigates the spread of adversarial noise while preserving high-confidence label prediction. Through structural decomposition and adaptive validation, our approach significantly strengthens defense mechanisms in poisoned graph environments. Finally, we propose CSA-LLM (Crowd-sourced homophily-ties-based graph annotation via large language models), which utilizes strong-tie graph structures to design LLM prompts that enhance annotation quality. By embedding structural priors in prompt engineering, CSA-LLM improves consistency in automated label generation, offering a scalable alternative to traditional manual annotation. This structured approach not only enhances annotation robustness, but also mitigates the inconsistencies introduced by structure-agnostic token generation, where LLMs generate labels based solely on textual prompts without considering graph topology. This dissertation provides a unified perspective on the impact of strong-tie structures across node labeling paradigms, bridging trust prediction, adversarial resilience, and LLM-assisted annotation. Our findings contribute to the development of attack-aware, structure-informed annotation frameworks, with implications for applications in social network security, financial fraud detection, recommendation systems, and decentralized finance (DeFi).