U.S. Department of Energy

Pacific Northwest National Laboratory

When Labels Fall Short: Property Graph Simulation via Blending of Network Structure and Vertex Attributes

Publish Date: 
Thursday, September 7, 2017
Property graphs can be used to represent heterogeneous networks with attributed vertices and edges. Given one property graph, simulating another graph with same or greater size with identical statistical properties with respect to the attributes and connectivity is critical for privacy preservation and bench marking purposes. In this work we tackle the problem of capturing the statistical dependence of the edge connectivity on the vertex labels and using the same distribution to regenerate property graphs of the same or expanded size in a scalable manner. However, accurate simulation becomes a challenge when the attributes do not completely explain the network structure. We propose the Property Graph Model (PGM) approach that uses an attribute (or label) augmentation strategy to mitigate the problem and preserve the graph connectivity as measured via degree distribution, vertex label distributions and edge connectivity. Our proposed algorithm is scalable with a linear complexity in the number of edges in the target graph. We illustrate the efficacy of the PGM approach in regenerating and expanding the data sets by leveraging two distinct illustrations.
Visweswara Sathanur A, S Choudhury, CA Joslyn, and S Purohit. 2017. "When Labels Fall Short: Property Graph Simulation via Blending of Network Structure and Vertex Attributes." In ACM CIKM.
| Pacific Northwest National Laboratory