Source-linked AI summary
Injecting Uncertainty in Graphs for Identity Obfuscation
Paolo Boldi, Francesco Bonchi, Aris Gionis, Tamir Tassa
TL;DR
Publishing social-network graphs raises privacy concerns, while existing approaches perturb edges entirely. The paper publishes uncertain graphs with probabilistic edges, and reports higher utility than standard random-perturbation methods at the same obfuscation level on real-world networks.
Problem
Graph publication raises privacy concerns, motivating anonymization that reduces privacy-breach risk while retaining analytical usefulness.
Source: §1 · p. 2Method
The approach injects uncertainty into edge existence and publishes the resulting graph, allowing edge probabilities between 0 and 1 rather than only full additions or deletions.
Source: §1 · p. 1Results
At the same obfuscation levels, the method maintains higher data utility than existing random-perturbation methods on real-world graphs.
Source: §1 · p. 2, §8 · p. 11Takeaways & Limitations
Finer-grained perturbations can achieve the same obfuscation with smaller data changes, while experiments confirm higher utility on real-world graphs.
Source: §8 · p. 11For shortest-path statistics, the method estimates a lower bound on diameter because exact estimation and repeated heuristic estimation are too inefficient.
Source: §6.3 · p. 8
Abstract
from arXiv · showhide
Data collected nowadays by social-networking applications create fascinating opportunities for building novel services, as well as expanding our understanding about social structures and their dynamics. Unfortunately, publishing social-network graphs is considered an ill-advised practice due to privacy concerns. To alleviate this problem, several anonymization methods have been proposed, aiming at reducing the risk of a privacy breach on the published data, while still allowing to analyze them and draw relevant conclusions. In this paper we introduce a new anonymization approach that is based on injecting uncertainty in social graphs and publishing the resulting uncertain graphs. While existing approaches obfuscate graph data by adding or removing edges entirely, we propose using a finer-grained perturbation that adds or removes edges partially: this way we can achieve the same desired level of obfuscation with smaller changes in the data, thus maintaining higher utility. Our experiments on real-world networks confirm that at the same level of identity obfuscation our method provides higher usefulness than existing randomized methods that publish standard graphs.
1. INTRODUCTION
The paper introduces graph anonymization by publishing uncertain graphs, where edge-existence probabilities permit partial rather than all-or-nothing perturbations. The authors motivate this finer-grained approach as a way to attain obfuscation with smaller data changes while retaining utility, and evaluate its usefulness and analysis efficiency.
1. INTRODUCTION
- Each edge in the published uncertain graph has a probability of existing, allowing partial changes instead of only adding or deleting edges entirely.For example, an existing edge can be assigned probability 0.7 and a previously absent edge probability 0.8.Source: §1 · p. 1
- The method generalizes random perturbation by allowing edge probabilities anywhere in [0, 1], rather than only changing them between 0 and 1.The paper argues this flexibility can achieve the same obfuscation with smaller changes in the data, preserving higher utility.Source: §1 · p. 1
- The paper treats practical use of uncertain graphs as requiring both high utility and efficient computation of graph properties.It identifies prior work on querying and mining uncertain graphs as evidence that useful analysis can be carried out on them.Source: §1 · pp. 1–2
- At the same obfuscation levels, experiments on three large real-world networks find higher data utility than existing random-perturbation methods.The introduction also frames utility as similarity to the original graph in characteristic properties and asks whether those properties can be computed efficiently on uncertain graphs.Source: §1 · p. 2
2. RELATED WORK
Prior graph-anonymization work is grouped into vertex generalization, deterministic edge alteration, and randomized edge alteration. The reviewed methods vary in adversarial knowledge, anonymity measures, and the extent to which graph structure is preserved.
2. RELATED WORK
- Graph anonymization methods are grouped into clustering/generalization, deterministic edge additions or deletions, and randomized edge additions, deletions, or switching.The three categories organize the related work discussed in this section.Source: §2 · p. 2
- Generalization methods cluster vertices and publish aggregate information; variants address vertex attributes, sequential clustering, or masking entity mappings,,,.Another approach with multiple edge types omits sensitive edges and studies their prediction from observed non-sensitive edges.Source: §2 · p. 2
- Deterministic alteration includes making vertices k-degree anonymous through edge additions and deletions, while other work considers stronger structural knowledge such as neighborhoods or the complete graph,,,.In k-degree anonymity, every vertex has at least k − 1 other vertices with the same degree.Source: §2 · p. 2
- Random-perturbation studies report trade-offs between anonymity and structural fidelity, with conclusions depending on datasets and the anonymity measure,,.Hay et al. report that meaningful anonymity required perturbation so large that graph features no longer reflected the original; later work reports structure preservation comparisons and entropy-based evaluations.Source: §2 · p. 2
3. OBFUSCATION BY UNCERTAINTY
The section models an uncertain graph by assigning probabilities to vertex pairs and evaluates identity obfuscation against an adversary who knows a target's vertex property. It defines obfuscation through the entropy of the adversary's induced identity distribution and allows a tolerance fraction of vertices not to meet the threshold.
3. OBFUSCATION BY UNCERTAINTY
- An uncertain graph on the original vertex set assigns each unordered vertex pair an edge probability in [0, 1].The method can restrict uncertainty to a candidate-pair set EC, with other pairs treated as certain non-edges; possible worlds are graphs formed from subsets of EC.Source: §3 · p. 3
- The adversary is assumed to know a property P of the target vertex, such as its degree or neighborhood structure.For each published vertex v and property value ω, Xv(ω) is the probability that v originated from an original vertex with value ω.Source: §3 · p. 3
- The normalized columns of Xv(ω) give Yω(v), the distribution over published vertices for a sought vertex known to have property value ω.Thus, X describes property values associated with a published vertex, while Y describes candidate identities given a property value.Source: §3 · p. 3
- A vertex is k-obfuscated with respect to P when the entropy of its induced YP(v) distribution is at least log2 k.The threshold expresses a desired anonymity level analogous to k-anonymity, based on the adversary's property knowledge.Source: §3 · p. 3
- A (k, ε)-obfuscation requires at least (1 − ε)n original vertices to meet the k-obfuscation threshold for P.The tolerance allows a fraction ε of vertices to fall short; the text notes this fraction can be drawn from a selected subpopulation, such as high-degree vertices in degree obfuscation.Source: §3 · pp. 3–4
- In the Figure 1 example, three of four vertices meet the 3-obfuscation threshold, yielding a (3, 0.25)-obfuscation.The example contrasts the lower entropy for a degree-3 vertex with values at or above log2 3 for the other three vertices.Source: §3 · p. 4
4. QUANTIFYING THE OBFUSCATION
The degree-property obfuscation test computes each vertex’s degree distribution in the uncertain graph, then uses those distributions to assess k-obfuscation. Exact computation takes O(n^2) time per vertex; a normal approximation is available when the sum has many terms.
4. QUANTIFYING THE OBFUSCATION
- For each vertex, the method models incident edges as Bernoulli variables and uses the resulting degree probabilities to form X_v(ω) and test k-obfuscation.Once the full matrix X_v is computed, the distributions over vertices can be derived for each property value.Source: §4 · p. 4
- O(n^2) time suffices to compute a vertex’s degree distribution exactly, using a recurrence that updates probabilities from the previous partial-sum distribution.Each probability in the next partial distribution takes constant time once the previous distribution is available; computing the full distribution takes O(ℓ) time at step ℓ.Source: §4 · p. 4
- Because uncertainty is injected only into candidate pairs, the degree sum includes only candidate edges incident to the vertex, averaging dc terms when the original graph’s average degree is d.Here c is the candidate-edge-set size divided by the original edge count.Source: §4 · p. 4
- When the degree sum has many terms, the method can approximate it with a normal distribution using its mean and variance.The normal approximation is motivated by the Central Limit Theorem.Source: §4 · p. 4
5. INJECTING UNCERTAINTY
The method seeks a (k, ε)-obfuscation while injecting as little uncertainty as possible. It varies edge uncertainty according to vertex uniqueness and searches for a setting that meets the obfuscation target.
5. INJECTING UNCERTAINTY
- The algorithm targets a (k, ε)-obfuscation with minimal injected uncertainty, searching for the smallest feasible uncertainty parameter σ.It doubles an upper bound until a feasible setting is found, then uses binary search and returns the last successful obfuscation.Source: §5 · p. 4, §5.3 · p. 5
5.1 Overview
- Candidate pairs receive probabilities between 0 and 1: existing edges use p(e) = 1 − r_e, while selected non-edges use p(e) = r_e.Smaller σ concentrates perturbations near zero, preserving graph characteristics more, while larger σ provides more obfuscation; a small q-fraction of pairs instead draw r_e uniformly from [0, 1].Source: §5.1 · pp. 4–5
5.2 Uniqueness Scores of Vertices
- The method assigns higher uncertainty to pairs involving vertices with more unique property values, using commonness and its inverse, uniqueness, as relative measures.Commonness is a distance-weighted average over property values, and the method sets θ = σ for these scores.Source: §5.1 · pp. 4–5, §5.2 · p. 5
5.3 The Obfuscation Algorithm
- Each randomized trial builds a candidate set of size c|E|, assigns edge uncertainty in proportion to pair uniqueness, and retains a successful graph with the lowest ε̃.The algorithm excludes the ⌈ε|V|/2⌉ vertices with the largest uniqueness scores from perturbation, samples pairs using vertex uniqueness, and runs t trials; edge probabilities are then set using r_e. The uncertainty parameter is searched by doubling and binary search.Source: §5.3 · pp. 5–6
6. UTILITY OF THE UNCERTAIN GRAPH
The paper describes ways to evaluate uncertain graphs by estimating graph statistics, often through sampling possible worlds. It gives approaches for degree, distance, and clustering measures, with diameter estimation limited to a lower bound.
6.1 Sampling
- Statistics on uncertain graphs are evaluated by expected values over possible worlds, approximated by sampling when direct computation is infeasible.Worlds are sampled according to edge probabilities; for a statistic bounded by a and b, Hoeffding’s inequality provides an error bound for the sample average.Source: §6.1 · pp. 6–7
6.2 Statistics Based on Degree
- Expected linear degree statistics are computed from expected vertex degrees, while nonlinear statistics such as maximal degree are estimated by sampling.Degree distributions are also approximated by averaging their values across sampled worlds; degree variance can be computed exactly, but its formulas have quadratic cost in the number of vertices.Source: §6.2 · p. 7
6.3 Statistics Based on Shortest-path Distance
- Distance-based measures use only path-connected vertex pairs, and sampling is used to compute them; the diameter is reported as a lower bound rather than an estimate of the exact value.HyperANF is used for the first four distance statistics, but its approximate distance distribution yields only SDiamLB, the largest distance with a nonzero estimated count.Source: §6.3 · pp. 7–8
6.4 Clustering Coefficient
- The expected clustering coefficient is estimated by sampling possible worlds, using the statistic’s bounds of 0 and 1 to apply the sampling error guarantee.The coefficient is defined as the number of three-vertex cliques divided by the number of connected triplets.Source: §6.4 · p. 8
7. EXPERIMENTAL ASSESSMENT
The experiments assess obfuscation level, runtime, data utility, and comparisons at matched obfuscation levels across three real-world datasets. The results show that utility depends on the statistic and obfuscation setting, while the proposed method outperforms standard-graph randomized methods in the reported comparisons.
7.1 Parameter Tuning and Running Time
- Larger k or smaller ε required larger σ; increasing c to 3 resolved some upper-bound failures but substantially reduced throughput, which also declined as k rose or ε fell.The experiments used q = 0.01 and c = 2 except for two cases with c = 3.Source: §7.1 · pp. 8–9
7.2 Data Utility
- At k = 20, average statistical error stayed below 15%; as k increased, errors rose to as much as 70.5% at k = 100.The error is the relative absolute difference between the estimated and real statistic values.Source: Table 4 · p. 9, §7.2 · p. 9
- Across 100 sampled possible worlds, statistic estimates were concentrated, with average relative SEM about 3%; SNE and SAD were especially concentrated.The reported dependence on k was weak, and dependence on ε was not shown.Source: §7.2 · p. 9, Table 5 · p. 9
- Pairwise-distance distributions were similar to the original at k = 20, ε = 10−3 but far from it at k = 100, ε = 10−4; degree-frequency means stayed close even in the latter case.Degree variance and clustering coefficient were more affected by error than some other statistics.Source: §7.2 · p. 10, Figure 2 · p. 10, Figure 3 · p. 10
7.3 Comparative Evaluation
- In every reported comparison, uncertainty obfuscation produced better statistic quality than random perturbation or sparsification; one matched case had 5% relative error versus 92% for sparsification.The comparison supports the paper’s claim that finer-grained perturbations can reach the same obfuscation with smaller data changes.Source: Table 6 · p. 11, §7.3 · p. 11
8. CONCLUSIONS AND FUTURE WORK
The paper proposes identity obfuscation by publishing uncertain graphs, enabling the same obfuscation level with smaller data changes. The authors call this an early step and identify extensions and sequential-release risk as open research directions.
8. CONCLUSIONS AND FUTURE WORK
- Uncertainty-based obfuscation spreads noise across edges, achieving the same obfuscation level with smaller changes in real-world graphs.Source: §8 · p. 11
- The authors describe this work as a first step and plan further assessment of the approach’s limits and merits.Source: §8 · p. 11
- Whether the degree-trail attack can re-identify users from sequential releases of probabilistic graphs remains an open research question.Source: §8 · p. 12