Graph-structured data underpin a wide spectrum of modern applications, yet their multiple sensitive attributes are not isolated but deeply coupled with graph topology. This coupling facilitates intersectional privacy leakage through attribute inference attacks (AIAs). Existing AIAs predominantly assume adversaries with two capabilities: (I) access to either auxiliary data sampled from the same distribution as the target or partial training records, and (II) the ability to repeatedly query the victim model. In reality, however, these assumptions are often impractical due to stringent data protection regulations, prohibitive query budgets, and heightened detection risks. Moreover, as prior attacks are designed to infer a single sensitive attribute at a time, they fail to simultaneously recover multiple attributes and thus underestimate overall privacy risks arising from cross-attribute dependencies. More critically, they obscure a systemic blind spot: \textbf{auxiliary graphs alone are sufficient to expose multiple sensitive attributes in the target graph.} This threat persists even under distribution shifts, enabling stealthy offline attacks without any model interactions. To investigate this unexplored vulnerability, we introduce \textbf{Taipan, the first query-free framework for multiple sensitive attribute inference attacks on graphs (G-MSAIAs).} Taipan incorporates \emph{Hierarchical Attack Knowledge Routing} to capture intricate inter-attribute correlations, and \emph{Prompt-guided Attack Prototype Refinement} to mitigate distribution shifts between auxiliary and target graphs. Extensive experiments on diverse real-world graph datasets demonstrate that Taipan consistently achieves strong attack performance across same-, similar-, and out-of-distribution settings, and remains effective under partial label coverage or even rigorous privacy guarantees.
Figures & tables
Attack Name
Attack Target
Attack Participant
Attack Knowledge and Adversary’s Capabilities
Attack Mechanism
Phase
Type
Inference
Model Owner
Attacker
Data Access
Model Access
Model Outputs
FJRMIA [ 13 ]
Training
Tabular
Single
√
√
Full Non-SAs in Training Data Marginal Prior of SAs and Non-SAs Possible Values of SAs and Non-SAs Training Data’s Ground-truth Labels
Black Box
Confusion Matrix Confidence Score
Query-based, Posterior-maximized
CS/LOMIA [ 25 ]
Training
Tabular
Single Parallel
√
√
Full Non-SAs in Training Data Possible Values of SAs and Non-SAs Training Data’s Ground-truth Labels (Auxiliary Data with Same/Similar Dist.)
Black Box
Confidence Score (Label-only)
Query-based, Posterior-maximized (Attack Model Trained)
Sens. Val. Inf. [ 17 ]
Training
Tabular
Single
√
√
Full Non-SAs in Training Data Possible Values of SAs and Non-SAs Auxiliary Graph with Same/Similar Dist. and Similar Shadow Model
White/Black
Confidence Score
Neuron Impt.-exploited Query-based
SDMIA [ 11 ]
Training
Tabular
Single
√
√
Possible Values of SAs and Non-SAs
Black Box
Label-only
Query-based, Attack Model Trained
Disparity Inf. [ 18 ]
Training
Tabular
Single Sequential
√
√
Full Non-SAs in Training Data Possible Values of SAs and Non-SAs
Black Box
Confidence Score
Query-based, Disparity-exploited
TABLE I : Attack Comparison. √ represents “access” or “applicable”, × represents “no access” or “not applicable”. Dist.:Distribution; Impt.: Imputation; SA: Sensitive Attribute; Sim.: Similar; Diff.: Different.
Fig. 1 : The Overview of Taipan for G-MSAIAs. The stacked squares represent multiple sensitive attributes and the green shield indicates the privacy-preserving techniques.
Fig. 2 : Hierarchical Attack Knowledge Routing
Dataset
GNN
Baseline
AA ( ↑ )
AF ( ↑ )
TDA ( ↓ )
TDF ( ↓ )
HD ( ↓ )
SuA ( ↑ )
SD ( ∣↓∣ )
LC ( ↑ )
German
-
FrePr.
54.21
60.25
13.08
58.70
36.33
26.00
-2.28
20.37
GCN
SingP.
66.50
42.50
13.46
88.05
33.27
14.00
0.48
34.36
PreTr.
66.34
73.62
10.45
40.24
20.33
54.00
7.22
42.77
Taipan
70.01
76.10
7.58
31.44
21.33
57.00
9.88
46.35
GraphSAGE
SingP.
69.47
54.72
8.28
55.69
35.20
35.20
-1.80
32.43
PreTr.
69.37
70.49
19.95
53.75
19.67
53.00
6.26
56.15
TABLE II : The Attack Performance of Taipan — Same-distribution Transfer, where the auxiliary and target graphs both come from the same graph dataset without overlapping. Bold: Best result; Underline: Second best result (close to the best).
Stage
Variant
AA ( ↑ )
AF ( ↑ )
TDA ( ↓ )
TDF ( ↓ )
HD ( ↓ )
SuA ( ↑ )
SD ( ∣↓∣ )
LC ( ↑ )
Full
Taipan
70.01
76.10
7.58
31.44
21.33
57.00
9.88
46.35
Pre-training
w.o.hierarchy
64.65
67.35
21.29
54.77
25.33
49.00
5.02
44.99
w.o.pretexts
58.06
71.53
12.84
46.41
25.00
54.00
3.73
39.42
w.o.gating
67.32
70.50
21.71
35.34
28.33
44.00
15.64
51.77
w.o. hier.+pret.
54.72
67.57
11.71
54.35
25.33
55.00
3.19
37.91
w.o. hiery+gate.
63.40
68.38
7.53
52.20
24.67
56.00
3.29
38.08
TABLE III : The Ablation Studies of Taipan for G-MSAIAs
Dataset
GNN
Baseline
AA ( ↑ )
AF ( ↑ )
TDA ( ↓ )
TDF ( ↓ )
HD ( ↓ )
SuA ( ↑ )
SD ( ∣↓∣ )
LC ( ↑ )
Pokec-n to Pokec-z
-
FrePr.
50.63
34.05
2.19
58.62
41.38
18.89
-7.50
5.68
GCN
SingP.
71.37
43.15
35.58
49.14
29.10
34.92
-2.01
33.67
PreTr.
62.22
44.87
24.50
51.88
29.18
34.08
-3.75
37.51
Taipan
64.33
50.61
23.66
41.87
29.83
32.04
2.77
36.14
GraphSAGE
SingP.
73.01
50.77
36.87
48.06
27.27
37.36
-0.77
43.40
PreTr.
64.64
52.16
29.43
42.74
29.21
33.89
-1.80
40.62
TABLE IV : The Attack Performance — Mismatched Similar-distribution and Out-of-distribution Transfers
Fig. 3 : Impact of Adaptation Steps
Fig. 4 : Impacts of Node Degree and Node Homophily
Fig. 5 : Impacts of Label Coverage in Auxiliary Graphs
Defense
ϵ
Dataset
AA ( ↑ )
AF ( ↑ )
TDA ( ↓ )
TDF ( ↓ )
HD ( ↓ )
SuA ( ↑ )
SD ( ∣↓∣ )
LC ( ↑ )
ODC ( ↓ )
DDC ( ↓ )
PrivDPR
0.1
German
52.82
60.38
3.22
55.60
36.33
37.00
12.57
14.79
24.00
9.68
Credit
51.31
79.50
3.25
30.81
27.52
47.87
13.70
6.38
6.43
4.71
Pokec-n
65.81
52.99
18.24
28.75
28.98
36.14
-0.90
36.35
11.56
6.95
Pokec-z
74.39
64.74
34.19
46.95
22.23
46.35
2.69
57.27
33.09
16.93
1.0
German
58.18
64.76
9.15
54.27
27.00
47.00
14.66
23.27
24.00
8.76
Credit
50.83
80.52
1.30
29.09
27.73
46.67
2.02
3.48
6.43
3.92
TABLE V : The Defense against Taipan for G-MSAIAs
Dataset
#Nodes
#Edges
#Attr.
#SAs
Label
Avg. Deg.
Homo.(%)
Imb. Ratio Range
German
1,000
22,242
27
3
Credit Status
44.48
60.86
[1.15-3.68]
Credit
30,000
1,436,858
13
2
Payment Default
95.79
72.55
[1.20-10.17]
Pokec-n
66,569
583,616
266
3
Working Field
16.53
79.79
[1.05-2.65]
Pokec-z
67,796
617,958
277
3
Working Field
19.23
77.05
[1.02-2.77]
TABLE VI : Detailed Graph Statistics. Imb. Ratio: #majority/#minority, where 1 indicates perfect balance.
Fig. 6 : The Attack Task Correlations among Diverse Graph Datasets
Fig. 7 : The Attack Hierarchy of Diverse Graph Datasets
Dataset
GNN
AUC ( ↑ )
ACC ( ↑ )
F1 ( ↑ )
SA1
SA2
SA3
Δ SP ( ↓ )
Δ EO ( ↓ )
Δ SP ( ↓ )
Δ EO ( ↓ )
Δ SP ( ↓ )
Δ EO ( ↓ )
German
GCN
66.62
69.42
79.48
21.37
13.50
17.22
12.50
27.95
22.50
GraphSAGE
75.85
68.93
81.07
3.67
0.50
2.48
0.83
3.73
2.85
GIN
60.12
67.96
80.70
0.47
1.50
2.22
3.33
2.47
1.69
Credit
GCN
71.86
75.22
83.93
0.98
15.73
2.21
13.65
—
—
GraphSAGE
73.40
79.55
87.81
1.50
0.42
1.11
0.74
—
—
TABLE VII : Original Performance across Different Graph Datasets. The red color indicates the commonly used sensitive attribute (SA) for fair or private graph learning, the arrow indicates the direction of better performance and the bold font represents the best results.
Fig. 8 : The tSNE Visualization of Inferred Multiple Sensitive Attributes
Fig. 9 : Joint Confidence Distribution for Multiple Sensitive Attributes
Fig. 10 : Impact of Adaptation Steps on Semantic-based Metrics
Fig. 11 : Impacts of Node Degree and Node Homophily on Attack Accuracy
Sensitive attributes such as age, income, and occupation can be inferred from user-generated content by aggregating indirect cues across many ordinary posts. LLM-based profilers can perform this aggregation automatically and with high accuracy, which makes large-scale personal attribute inference a major privacy threat. Existing LLM-based profilers, however, offer limited insight into which specific posts, concepts, and relationships made an inference possible, which is key to targeted privacy mitigation, i.e., redacting or rewriting only the few posts that actually leak an attribute, rather than perturbing entire histories. We introduce GraphProfiler, an auditable LLM-based profiler that represents each user's post history as a source-linked personal knowledge graph where nodes and edges trace back to the originating post and resolves attribute predictions to cited graph records and source texts. GraphProfiler reaches 86.7% attack success rate on the eight-attribute SynthPAI benchmark, within two points of strong text-only baselines, and 84.6% on PANDORA, while citing supporting evidence for over 98% of predictions. Our controlled ablation experiments provide evidence that the cited posts contribute to attack success, as removing them reduces the attack success rate substantially more than removing an equal number of random posts.
Knowledge Graphs (KGs) are a powerful representation of linked data, offering flexibility, semantic richness, and support for knowledge enrichment and reasoning. They help data owners organize and exploit heterogeneous data to provide insightful services (e.g., recommendations), yet real-world KGs are often incomplete, hiding true facts or missing valuable insights. Knowledge graph embedding techniques are commonly used to infer valuable missing information. However, reasoning over KGs can inadvertently expose sensitive user information, even when such data is not explicitly stored. In this work, we investigate the privacy risks associated with KGE-based reasoning, focusing on attribute inference attacks where adversaries attempt to deduce sensitive user attributes from seemingly non-sensitive outputs. We propose and evaluate a framework that mitigates these privacy risks by applying post processing sanitization techniques to KGE outputs. Preliminary results demonstrate the effectiveness of these attacks on the outputs of KGE models, and explore the trade-off between recommendation quality and privacy protection when applying randomization based approaches, highlighting the need to experiment with more advanced techniques in future work to address this issue.
Yasmine Hayder
PETSCRAFT · LIFO, INSA CVL, Univ. Orléans, Inria, France
Graph unlearning (GU) has emerged as a promising solution to comply with "the right to be forgotten" regulations by enabling the removal of sensitive information upon request. However, this solution is not foolproof. The involvement of multiple parties creates new attack surfaces, and residual traces of deleted data can persist within the unlearned graph neural networks (GNNs). These vulnerabilities can be exploited by attackers to recover the supposedly erased samples, undermining the intended functionality of GU. In this work, we propose GraphToxin, the first full graph reconstruction attack against GU. We show that GraphToxin can recover not only a deleted individual's information and personal links but also sensitive content of their neighbors, thereby posing substantially more detrimental threats than prior membership inference attacks (MIAs). Specifically, we introduce a novel curvature matching module to provide fine-grained guidance for full unlearned graph recovery. We further extend GraphToxin to multiple-node removal under both white-box and black-box settings, showcasing its practical feasibility and potential to cause considerable harm. We highlight the necessity of worst-case analysis and propose a systematic evaluation framework to assess attack performance under both random and worst-case node removal scenarios. Our extensive experiments demonstrate the effectiveness and flexibility of GraphToxin. Notably, current defense mechanisms are largely ineffective against this attack. Additionally, our findings reveal that existing GU verification standards based on MIAs can be misleading: they achieve membership-level protection, while the full unlearned graph remains recoverable through GraphToxin.