> I keep wondering how much of this is just degree patterns. Mostly, yes, and that is the annoying part. If you can learn that one endpoint sits in a dense part of the graph and the other sits in a thin one, you already get a stupid amount of mileage, especially when the sensitive relation has a small candidate set. The paper’s own PCA table basically says as much, the first two components are just connectivity and head/tail imbalance wearing different hats. So the headline is less "hidden semantics leak" and more "people keep underestimating how much structure survives edge deletion." The stronger numbers come from the easy regime where the attacker gets to use co-occurring pairs and a decent classifier, which is not some magical privacy break, it's the graph shouting at you through degree and neighborhood overlap.