Friends Who Tell: Guarding Private Attributes in a Graph Network

Each square is a loan applicant who kept their gender private. The attacker looks at that person’s connections who did reveal theirs and guesses the more common answer. Most squares come out filled, meaning the guess was right. Try a bigger or smaller share of users revealing, then switch to Most common answer to see how much the friendships add over guessing “man” for everyone.

The applicants are linked when their records look alike, so a private user’s links mostly point to people of the same gender. With 30 percent revealing, the friends’ vote gets 88.6 percent right on average over ten random splits, against 69 percent for always guessing “man.” Switch to One column: Single for a second leak: in this data set every applicant marked single is a man.

The attacker here uses no model at all: a majority vote over each private node’s disclosed neighbors (ties go to the disclosed majority). Over ten splits at k = 30 percent it scores 88.60 ± 3.08 percent on the 350 private training users, close to the paper’s GCN attacker on this graph (92.17 ± 1.93 percent, Table 2). Homophily alone carries most of the leak. In the German credit graph, 80.5 percent of the 21,742 edges join two applicants of the same gender, against 57.2 percent expected for random pairs.

The bars show how strongly each column of an applicant’s record goes along with being a woman. Single stands out: the original German survey coded marital status and sex together, and no woman in it is coded single. Removing the gender column does not remove gender. The paper calls this attribute dependency.

Pearson correlations of each min-max-scaled feature with s (1 = woman) over all 1,000 applicants, top ten by magnitude. The one-column rule learns, from disclosed users only, which side of the column’s mid-range maps to which gender. Single alone reaches 85.94 ± 1.01 percent over ten splits; 548 applicants are single (all men), and the other 452 are 310 women and 142 men. A least-squares linear probe on all 26 non-sensitive features reaches 83.63 ± 1.99 percent. This is the attribute dependency that DP-GCN’s W₁ and W₂ target.

Each dot is an applicant, placed left or right by an attacker who draws the best straight line through the records of users who revealed their gender. DP-GCN’s idea: find the direction in the data that points toward “woman,” and keep only what is at right angles to it. Press Direction removed with the paper’s direction, and the attacker refits and still separates most women from men. Switch to the correlation direction, a check this page adds, and the straight-line attacker has nothing left.

Think of each applicant’s record as an arrow with 26 parts. Removing a direction means flattening every arrow along one line, the way a shadow flattens a shape against a wall. The paper picks the line that best predicts gender. The attacker then looks for the next-best line in what remains, and on this data set it finds one that works almost as well (81 percent right instead of 84). Flattening along the line where gender and the record vary together leaves the straight-line attacker at 69 percent, the same as guessing “man” every time.

With W₁ = wwᵀ/‖w‖² and W₂ = I − W₁, W₁ᵀW₂ = 0 exactly, which is the end point of the paper’s orthogonality term, and Theorem 2 holds for every applicant (the check under the chart). Removing the least-squares direction w = (X_kᵀX_k)⁻¹X_kᵀs does not remove linear information: the refitted probe moves to another direction and scores 81.46 ± 2.72 percent. Removing the cross-covariance direction Σ(x − x̄)(s − s̄) over disclosed users leaves zero linear correlation with s on those users, so the refitted probe predicts the base rate and scores 69.00 ± 2.01 percent (the scalar case of LEACE, Belrose et al., 2023). The second direction is this page’s addition, not the paper’s.

Press Train and attack to train a model on your device that predicts whether each applicant is a good credit risk, then train an attacker to guess the private users’ gender from what that model uses. A good defense keeps the first number up and pushes the second toward 69 percent. Each run takes a few seconds and uses one of ten random splits of the applicants.

Plain GCN follows the paper’s baseline: the attacker infers the hidden s from the original features (200 epochs), and the classifier trains on the features plus disclosed or inferred s (300 epochs, weights kept at the lowest validation loss). DP-GCN alternates one Adam step each on W₁, W₂, and the GCN per epoch, with the paper’s Table 4 settings, and the attacker then trains on X W₂. The chart tracks how close W₁ and W₂ come to orthogonal: at the paper’s learning rate the normalized ‖W₁ᵀW₂‖ only falls from about 0.20 to 0.15 in 300 epochs.

Settings follow Table 4 (32 hidden units, dropout 0.5, weight decay 10⁻⁵, learning rate 0.001 for θ, W₁, and W₂, 300 training and 200 inference epochs) with a 50/30/20 split and k = 30 percent (Section 5.1). Over ten splits: plain GCN 70.90 ± 2.34 classification, 88.23 ± 3.77 attacker; DP-GCN (α = 1, β = 5, γ = 1, the Section 5.4.3 setting) 71.00 ± 3.67 and 92.34 ± 2.16. The two exact-removal checks show where the leak goes: removing W₁’s direction exactly gives 71.60 ± 2.16 and 90.03 ± 2.04; removing the correlation direction gives 71.35 ± 3.32 and 75.60 ± 3.15. Accuracy holds; the GCN attacker still beats the 69 percent base rate through the graph.

• On all five data sets, the attacker guessed private attributes less often against DP-GCN than against a plain graph network, by between 0.5 and 6.8 percent.
• The prediction task lost little: at most about two percent of accuracy, and almost none on the two social-network data sets.
• On the German credit applicants, the attacker’s success fell from 92 to 87 percent.

• The paper tested DP-GCN on two social networks from Slovakia (Pokec, about 67,000 users each, with region as the private attribute), German credit applicants (gender), people released on bail (race), and credit card holders (age).
• Against a plain graph network, DP-GCN lowered the attacker’s accuracy on every data set, most on Pokec-z (77.35 to 72.06 percent).
• Accuracy on the main task stayed within 1.7 points of the plain network.
• The more users revealed their attribute, the better the attacker did against DP-GCN on most data sets (Figure 6).

• Privacy. DP-GCN has the lowest attacker accuracy of the five models on four of five data sets (Table 2); RGCN edges it on Pokec-n (71.14 against 72.99).
• Utility. Classification accuracy stays within 1.66 points of plain GCN everywhere (Table 1); RGCN beats DP-GCN on Credit defaulter.
• Figure 4. The bars are relative changes, (DP-GCN − baseline) / baseline × 100, not percentage points. All 20 values follow from Tables 1 and 2 to four decimals.
• Hyperparameters. Raising α or β lowers attacker accuracy; raising β also costs classification accuracy; raising γ raises both (Figure 5).
• Inferred attributes. Feeding inferred s to plain GCN changes accuracy by at most 1.6 points (Table 3).

Keeping a box unchecked on a profile does not keep a fact private when the people around you checked it. The paper names that problem for graph neural networks, which power friend suggestions, feeds, and fraud screens, and offers one way for the model’s builder to protect the users who opted out. The demos above also show how hard the problem is: on this data set the friendships alone give away gender almost nine times out of ten.

Most privacy-preserving GNN work assumes the defender knows every user’s sensitive attribute, which defeats the purpose for users who withheld it. DP-GCN works from the disclosed subset only, needs no trusted server or added noise, and costs little accuracy in the paper’s experiments. The authors list nonlinear disentanglement, other GNN architectures, and evolving networks as next steps. The reproduction here adds a design lesson for that work: a defense has to address the graph channel as well as the feature channel, and a feature-space projection should be judged by what a refitted attacker can still recover.

Try it in class

1. Draw ten classmates as dots and connect friends with lines. Have half write a favorite sport on a card; keep the other half secret.
2. For each secret dot, guess the most common sport among its revealed friends. Count how many guesses were right, as a percentage.
3. Now hide one more fact, such as which team jersey students wear. Discuss which facts on a profile travel with the secret, and how removing the secret column alone leaves it exposed.

Notes from building this page

These are the page’s own observations, offered for discussion with the authors.

• Reproduction scope. Only German credit (1,000 nodes) runs in a browser. The plain GCN matches Table 1 (70.90 ± 2.34 here against 72.80 ± 1.79) and comes in under Table 2 (88.23 ± 3.77 against 92.17 ± 1.93). DP-GCN at the stated settings does not lower the attacker’s accuracy here (92.34 ± 2.16 against the paper’s 87.26 ± 3.84). The authors’ tuned α, β, γ per data set and their unpublished code may account for part of the gap.
• Orthogonality is barely reached. With N(0, 1) initialization of two 26 × 26 matrices, Adam at 0.001, and one step per epoch, W₁ and W₂ move at most about 0.3 per entry in 300 epochs, and the normalized ‖W₁ᵀW₂‖ falls only from 0.200 to 0.153. W₂ stays close to a random matrix, and X W₂ keeps nearly all of X’s information. Driving the residual to 10⁻⁵ (20 inner steps at 0.01, or five at 0.05 with β = 10) leaves the attacker at 89.1 to 89.4 percent on split 1.
• Weight-space orthogonality is not linear erasure. W₁ᵀW₂ = 0 removes the column space of W₁ from X W₂, but the least-squares direction is not the direction of linear information: after exact removal, a refitted probe still scores 81.46 percent. Removing the cross-covariance direction instead drops the probe to the base rate and the GCN attacker to 75.60 percent, with no loss of classification accuracy. Theorem 2 (W₁x ⊥ W₂x) holds in both cases, so it does not by itself certify privacy.
• The German credit graph carries gender in its edges. The NIFTY loader builds edges from feature similarity over a column list that includes gender; 80.5 percent of the 21,742 edges are same-gender, and a neighbor vote with no features scores 88.60 percent. No feature transform can close that channel.
• Row and column conventions. Eq. 3 and Algorithm 1 multiply row vectors (X_kW₁, X W₂), while Theorem 2 and Eq. 5 use column vectors (W₁x, W₂x). For the row form the training uses, each user’s two latent vectors are orthogonal when W₁W₂ᵀ = 0; the penalty ‖W₁ᵀW₂‖²_F enforces W₁ᵀW₂ = 0. The two coincide for symmetric W₁ and W₂ (as in the page’s check), not in general.
• Shapes in Eq. 3. W₁ is d × d while S_k holds one attribute per user, so ‖X_kW₁ − S_k‖ needs S_k repeated across d columns (as here) or W₁ of size d × 1. The paper does not say which.
• Classification near the base rate. On German credit, 700 of 1,000 applicants are good risks; every model in Table 1 lands between 70.70 and 72.91 percent, a spread of about one standard deviation, so Table 1 cannot separate the methods there.
• Figure 4 reports relative change. The text’s “reduces the privacy inference accuracy by 5.44%” on Pokec-n is (77.19 − 72.99) / 77.19, a 4.20-point drop.
• Section 5.2 text. The RGCN comparison lists “Credit: 78.78 vs. 79.74,” where RGCN is higher; the sentence says “most datasets,” so the claim stands.