Abstract
The increasing popularity of graph data, such as social and online communities, has initiated a prolific research area in knowledge discovery and data mining. As more real-world graphs are released publicly, there is growing concern about privacy breaching for the entities involved. An adversary may reveal identities of individuals in a published graph, with the topological structure and/or basic graph properties as background knowledge. Many previous studies addressing such attacks as identity disclosure, however, concentrate on preserving privacy in simple graph data only. In this paper, we consider the identity disclosure problem in weighted graphs. The motivation is that, a weighted graph can introduce much more unique information than its simple version, which makes the disclosure easier. We first formalize a general anonymization model to deal with weight-based attacks. Then two concrete attacks are discussed based on weight properties of a graph, including the sum and the set of adjacent weights for each vertex. We also propose a complete solution for the weight anonymization problem to prevent a graph from both attacks. In addition, we also investigate the impact of the proposed methods on community detection, a very popular application in the graph mining field. Our approaches are efficient and practical, and have been validated by extensive experiments on both synthetic and real-world datasets.
Introduction: The Vulnerability of Weighted Graphs
Most research on graph privacy focuses on "simple" graphs—where edges either exist or they don't. In these cases, attackers often use a node's degree (number of neighbors) as background knowledge to re-identify individuals. However, real-world data is often weighted, representing interaction frequencies, message counts, or traffic volume.
Weights introduce a massive amount of unique information. Even if a node's degree isn't unique, the specific combination of its edge weights likely is. This paper addresses two specific threats:
- Volume Attacks: An adversary knows the total sum of weights for a target node.
- Histogram Attacks: An adversary knows the specific set of weights associated with a node's edges.
The challenge is to perturb these weights to achieve $k$-anonymity—ensuring every node is indistinguishable from at least $k-1$ others—without destroying the graph's utility for data mining, specifically community detection.
Proposed Methodology
The authors propose a general Weight Anonymization (WA) model and a two-step solution:
1. k-Histogram Anonymization
Each node's weight set is treated as a vector in a multi-dimensional space. A recursive heuristic algorithm groups these vectors into clusters of size at least $k$. The weights within each cluster are then modified to a "largest" common vector to ensure indistinguishability among the group members.
2. Weighted Graph Construction (WGC)
Once an anonymized weight set is determined, the graph must be rebuilt. The authors introduce a "sort-then-switch" procedure that uses the graph spectrum (specifically the second smallest eigenvalue, $\lambda_2$, or algebraic connectivity) as a metric for information loss. By minimizing the change in $\lambda_2$, the global structural properties remain intact.
To protect community structure, a Community Preserving (CP) procedure is added. This involves labeling nodes based on their community and "min-cut" sets, ensuring that weight modifications only occur between nodes that share similar structural roles.
Experimental Evaluation
The approach was evaluated using three datasets:
- RandGraph: A synthetic random weighted graph with 2,000 nodes.
- BkFrat: A real-world dataset of interactions among 58 fraternity students.
- NetSci: A co-authorship network of 1,589 scientists.
Key Results
- Attack Success: On the
NetScidataset, while only 0.25% of nodes were unique by degree, 6.48% were unique by weight histogram. In theBkFratdataset, a degree-based attack identified ~22% of nodes, but a histogram attack identified over 98%, proving weights are significantly more identifying than degrees. - Utility Preservation: The proposed HA-WGCS (Histogram Anonymization with Sort-then-Switch) significantly outperformed basic construction methods. In
RandGraph, it reduced the bias in information loss by more than half compared to standard approaches. - Community Stability: The HA-CP method showed much lower "modularity bias" and "intra-group error" than non-community-aware methods, allowing accurate community detection on anonymized data.
Discussion and Insights
The "aha moment" of this research is the empirical proof of how much more vulnerable weighted graphs are compared to their unweighted counterparts. By using the graph's Laplacian spectrum as a proxy for utility, the authors found a way to preserve fundamental structural invariants without checking every possible graph property.
However, the optimal version of histogram anonymization is likely NP-hard, meaning the current solution relies on heuristic approximations. While the "sort-then-switch" method is efficient, it remains a greedy approximation.
Conclusion
This paper provides a robust framework for anonymizing weighted graphs while maintaining their utility for community detection. By addressing both volume and histogram attacks, the proposed methods offer a practical solution for releasing sensitive network data. Future work will explore the impact of random weight modifications on the graph spectrum and investigate effects on other topological structures like path lengths.
Summary updated