MAGO: Maliciously Secure Subgraph Counting on Decentralized Social Graphs

Subgraph counting aims to count over a large graph subgraphs matching a given shape (e.g., triangle), which plays an important role in various social graph analytics applications such as discovering social roles and characterizing social networks. Subgraph counting over social graphs, however, becomes quite challenging when the social graph to be analyzed is presented in a decentralized manner, where each user only holds a local view. Collecting the local views for subgraph counting-based analytics raises acute privacy concerns, because they capture the sensitive social relationships among individuals. In light of this, we design, implement, and evaluate MAGO, a new system aimed at maliciously secure subgraph counting on decentralized social graphs. MAGO is built from a delicate synergy of insights on graph analytics, lightweight cryptography, and local differential privacy, allowing individual users to securely contribute their local views on a decentralized social graph for a cloud-empowered subgraph counting service. In addition to the protection for data confidentiality, MAGO is also designed to protect against a malicious adversary that might try to tamper with the subgraph counting results. Extensive experiments over real-world social graph datasets demonstrate the practically affordable performance of MAGO for maliciously secure subgraph counting.

Automated summary

Subgraph counting aims to count matching subgraphs of a given shape (e.g., triangle) in a large graph, which is important for social graph analytics applications. However, counting subgraphs in decentralized social graphs is challenging due to privacy concerns. To address this, MAGO is proposed as a system for secure subgraph counting. MAGO combines graph analytics, lightweight cryptography, and local differential privacy to allow users to securely contribute their local views for cloud-based subgraph counting.