## 3 Preliminaries  
**Problem Statement**. Given an undirected and unlabeled graph \(G(V,E)\) and its anonymized form \(G^{*}(V^{*},E^{*})\), it is essential to ensure that any attacker with background knowledge of 1-neighborhood information (i.e., degree or structural information) cannot re-identifify any individual structural information through queries on \(G^{*}\).  
**Definition 1** (Social network graph).: _An undirected, unlabeled graph \(G(V,E)\), where \(V\) represents the set of nodes (users) in the social network, \(E\) represents the set of edges (relationships between users), and each \((v_{i},v_{j})\in E\) represents the edge between \(v_{i}\in V\) and \(v_{j}\in V\)._  
Publishing the original graph \(G\) without proper anonymization can result in significant privacy risks for users. To mitigate these risks, the graph is typically anonymized before publication, with the \(k\)-anonymity method being one of the most widely used approaches.  
**Definition 2** (\(k\)-anonymity).: _Given a graph \(G(V,E)\), the graph is \(k\)-anonymous if for each node \(v\in V\), it is indistinguishable from at least \(k-1\) other nodes._  
\(k\)-anonymity is commonly used to protect users' identities by modifying nodes so that each user is indistinguishable from \(k-1\) other users. However, adversaries may use additional information, such as \(1\)-neighborhood knowledge, to re-identify target nodes. Therefore, it is also necessary to protect the neighborhood information.  
**Definition 3** (\(1\)-neighborhood subgraphs [16]).: _Given a graph \(G(V,E)\), \(g(v)=\langle V(g(v))\), and \(E(g(v))\rangle\) represents the \(1\)-neighborhood subgraph of \(v\) in the graph \(G\), where \(V(g(v))\) represents the nodes connected to \(v\) within \(1\)-hop distance in \(G\), denoted as \(V(g(v))=\{u\mid(u,v)\in E\}\cup\{v\}\); \(E(g(v))\) represents the set of edges between nodes in \(V(g(v))\), denoted as \(E(g(v))=\{(u,v)\mid u,v\in V(g(v))\wedge(u,v)\in E\}\)._  
To address the limitations of \(k\)-anonymity, we introduce \(k\)-neighborhood subgraph anonymity and other anonymity methods.  
**Definition 4** (\(k\)-neighborhood subgraph anonymity).: _A graph \(G(V,E)\) satisfies \(k\)-neighborhood subgraph anonymity if for each node \(v\in V\), there are at least \(k-1\) other nodes in \(V\) that have the same \(1\)-neighborhood subgraph as \(v\)._  
**Definition 5** (Graph isomorphism [33]).: _Given two graphs \(G(V,E)\) and \(G^{*}(V^{*},E^{*})\), where \(|V|=|V^{*}|\), \(G\) and \(G^{*}\) are isomorphic if there exists a bijection \(h\) between \(V\) and \(V^{*}\), \(h:V(G)\to V(G^{*})\), such that \((u,v)\in E\) if and only if \((h(u),h(v))\in E(G^{*})\); then, \(G\) and \(G^{*}\) are isomorphic. It is also said that there exists an isomorphism from \(G\) to \(G^{*}\), or \((u,v)\) is isomorphic to \((h(u),h(v))\)._  
**Definition 6** (Partial isomorphism [35]).: _Given two graphs \(G(V,E)\) and \(G^{*}(V^{*},E^{*})\), and their subgraph structures \(A\) and \(B\), \(G\) and \(G^{*}\) are partially isomorphic if there exists a partial function, which is also a bijective function, \(s:A\to B\), such that the relationship between the nodes in \(A\) is preserved and reflected in \(B\) when a node in \(A\) is mapped to \(B\)._  
**Definition 7** (\(k\)-isomorphism [33]).: _Given a graph \(G(V,E)\), \(G\) satisfies the \(k\)-isomorphism if \(G\) consists of \(k\) disjoint subgraphs, i.e., \(G=\{g_{1},g_{2},\ldots,g_{k}\}\), and these \(k\) subgraphs are isomorphic to each other._