# Graph-Level Label-Only Membership Inference Attack Against Graph Neural Networks
## 4 Graph-Level Label-Only Membership Inference Attack
### Attack Methodology
#### 4.2.3 Generation of Perturbed Graphs  
A method for generating perturbed graphs is proposed to distinguish between members and non-members by perturbing the effective (i.e., non-zero) features on the graph, as described in Algorithm 1. Specifically, our method consists of the following steps :  
1. **Identify non-zero features**. Given a target graph \(g_{t}\), its non-zero features are identified. The positions of non-zero features are indicated by \(MM\), which is a boolean matrix with shape \(n\times d\) where the element value true indicates the presence of a non-zero value, while the element value false denotes a zero value (lines 1-2 in Algorithm 1).
2. **Adjust perturbation range**. The perturbation range is initialized from \(r_{min}=0.1\) to \(r_{max}=0.5\). A scaler \(s\) is used to adjust the perturbation range for different datasets. The perturbation range after adjustment is from \(s\times r_{min}\) to \(s\times r_{max}\) (line 3).
3. **Generate perturbed graphs**. Initialize an empty set \(G_{t}\) for storing perturbed graphs (line 4). Then, repeat the following steps (a) to (e) until \(N\) perturbed graphs have been generated (lines 5-12): 1. Create a copy of the input graph \(g_{t}\) as \(g_{t}^{\prime}\) to ensure that the perturbations are applied to \(g_{t}^{\prime}\) without affecting \(g_{t}\) (line 6). 2. Initialize the perturbation matrix (denoted by \(PM\)) as a zero matrix of shape \(n\times d\), where \(n\) and \(d\) represent the number of nodes and the feature dimension of the input graph, respectively. It stores perturbation values, which are calculated as follows (line 7): \[\mathrm{PM}[i][j]=\begin{cases}p_{ij},&\text{if }MM[i][j]=\text{true}\\ 0,&\text{otherwise}\end{cases},\quad\text{where }p\sim\mathcal{U}(r_{\min},r_{ \max})\] (9) where \(p_{ij}\) is a random perturbation value uniformly sampled from the perturbation range that is adjusted by the scaler \(s\). 3. Initialize the operator matrix (denoted by \(OM\)) as a zero matrix of shape \(n\times d\), and store the arithmetic operators at the non-zero feature positions indicated by \(MM\). The arithmetic operators are generated according to the following equation (line 8): \[\mathrm{O}M[i][j]=\begin{cases}2\cdot o_{ij}-1,&\text{if }MM[i][j]=\text{true}\\ 0,&\text{otherwise}\end{cases}\] (10) where \(o_{ij}\) is an integer randomly sampled between 0 and 1. The values of elements of the matrix \(OM\) can only be \(+1\) or \(-1\), representing the addition or subtraction of a perturbation value. 4. Perform element-wise multiplication of perturbation values by their corresponding operators and add them to the features of \(g_{t}^{\prime}\), ensuring that perturbations are added only to non-zero features, while the others remain unchanged (lines 9-10). 5. Finally, add \(g_{t}^{\prime}\) to the set \(G_{t}\), which is the set of perturbed graphs (line 11).  
The perturbations that we perform are irrelevant to the feature types, and our purpose is to distinguish between members and non-members rather than to cause severe model misclassifications or to make the perturbations imperceptible.