Privacy-preserving record linkage (PPRL) technology, crucial for linking records across datasets while maintaining privacy, is susceptible to graph-based re-identification attacks. These attacks compromise privacy and pose significant risks, such as identity theft and financial fraud. This study proposes a zero-relationship encoding scheme that minimizes the linkage between source and encoded records to enhance PPRL systems' resistance to re-identification attacks. Our method's efficacy was validated through simulations on the Titanic and North Carolina Voter Records (NCVR) datasets, demonstrating a substantial reduction in re-identification rates. Security analysis confirms that our zero-relationship encoding effectively preserves privacy against graph-based re-identification threats, improving PPRL technology's security.