## 2 Related Works  
Commonly used privacy-preserving methods in social network graph publishing include \(k\)-anonymity, the perturbation of nodes and edges, and differential privacy. **Degree protection. **\(k\)-anonymity ensures that each record or individual in the dataset is indistinguishable from at least \(k-1\) other records or individuals. However, besides protecting users' identity, it is equally important to protect the privacy of users' degrees in social networks. This prevents attackers from using degrees for re-identification attacks. Therefore, it is necessary to ensure the privacy of each node's degree in social networks. Therefore, \(k\)-degree anonymity is further proposed on the basis of \(k\)-anonymity. Specifically, there exist at least \(k-1\) nodes with the same degree to ensure the indistinguishability of node degrees, effectively defending against node degree attacks [17; 18]. Based on this concept, [PERSON] et al. [19] further proposed a fast \(k\)-anonymization method, named FKDA. This method anonymizes the degree sequence of a graph by adding extra edges. [PERSON] et al. [20] further improved this approach by proposing an improved heuristic algorithm. This algorithm works in two stages, including anonymizing degree sequences and achieving \(k\)-anonymous degree sequences. It minimizes the number of edges added to a social network graph to achieve \(k\)-anonymity. However, these methods cannot preserve anonymized graph utility. To balance graph anonymity and utility, [PERSON] et al. [21] proposed the UMGA \(k\)-degree anonymization algorithm. The method first creates a \(k\)-degree anonymous degree sequence, and then modifies edges with low centrality to maintain network integrity, reduce information loss, and enhance graph utility. [PERSON] et al. [22] extended the \(k\)-anonymization based on clustering. The method first clusters nodes according to the connection relationship between nodes and then places nodes with the same degree in the same group, reducing the modifications to the nodes. It performs better in terms of utility preservation. [PERSON] et al. [23] proposed a one-time scan algorithm and reduced the anonymization overhead by creating a tree structure. This approach allows nodes to be grouped based on degree without having to perform anonymization from scratch. In addition, the method improves the utility of anonymized graphs by using participation and minimal path criteria for adding and deleting edges. Building on their previous work [23], [PERSON] et al. [24] proposed the NaFa4 KDA algorithm to further improve the speed of graph modification. This algorithm creates an anonymized degree sequence by clustering nodes and assigning target degrees, and enhances graph anonymity by computing and selecting edges with minimal impact for deletion during the modification process. In the pursuit of user privacy and improved data utility, [PERSON] et al. [25] designed a new degree-anonymized sequence generation algorithm using depth-first search, which reduces the differences between the anonymized graph and the original graph. Overall, \(k\)-degree anonymity effectively extends \(k\)-anonymity by strategically utilizing graph features, including node degrees and edges, through node groupings and edge modifications, thus achieving a balance between privacy protection and data utility in social network graphs. **Neighbor protection. ** Researchers have incorporated more information about the graph structure into the anonymization processes. A typical method is \(k\)-neighborhood anonymity [26; 27], which processes the node neighbors and ensures that each node has at least \(k\) similar neighbors. [PERSON] et al. [28] proposed 1-neighborhood anonymity for the social network graph, meaning that the graph is anonymized so that each node in the graph has at least the same \(k-1\) 1-hop neighbors. However, this scheme requires the continuous addition of fake edges to the nodes of the graph.