---
abstract: 'Directly motivated by security-related applications from the Homeland Security Enterprise, we focus on the privacy-preserving analysis of graph data, which provides the crucial capacity to represent rich attributes and relationships. In particular, we discuss two directions, namely privacy-preserving graph generation and federated graph learning, which can jointly enable the collaboration among multiple parties each possessing private graph data. For each direction, we identify both 'quick wins' and 'hard problems'. Towards the end, we demonstrate a user interface that can facilitate model explanation, interpretation, and visualization. We believe that the techniques developed in these directions will significantly enhance the capabilities of the Homeland Security Enterprise to tackle and mitigate the various security risks.'
author:
- 'Dongqi Fu$^\dagger$, Jingrui He$^\dagger$, Hanghang Tong$^\dagger$, and Ross Maciejewski$^\S$'
bibliography:
- 'ref.bib'
title: |
    Privacy-preserving Graph Analytics:\
    Secure Generation and Federated Learning
---

Introduction
============

Nowadays, the Homeland Security Enterprise is facing unprecedented challenges in multiple critical areas, such as identifying and preventing targeted violence and mass attacks, building resilient critical infrastructure, countering human trafficking, etc. Addressing these challenges requires collaborative efforts from all levels of government, the private and nonprofit sectors, and individual citizens. In particular, effective and efficient data collection, sharing, analysis, and sense-making are at the core of many decision making processes in these areas. Due to the distributed, sensitive and/or private nature of the large volume of involved data (e.g., personal identifiable information, images and video from surveillance cameras or body camera), it is thus of great importance to make use of the data while avoiding the sharing and use of sensitive information. In this paper, we focus on graph data, or network data, due to their rich representation capabilities to encode the multi-modality time-evolving attributes for entities (e.g., individuals, locations) as node attributes in the graph, and to encode the various types of relationships among entities via edges.

The main goal of this paper is to focus on privacy-preserving analysis of graphs. In particular, we aim to explore key research questions and privacy-enhancing technologies that target the following two areas: (A1) privacy-preserving techniques for creating, maintaining and linking anonymous identities and profiles; and (A2) multiparty and homomorphic computation to allow for analysis of datasets held by multiple parties without the need to physically combine datasets. The techniques developed for these areas together will enable the collaboration among multiple parties each possessing private graph data.

More specifically, we consider the following two directions for the two areas respectively. For (A1), a promising direction is to generate synthetic graphs in a privacy-preserving manner, such that the generated graphs can be shared with collaborators without revealing sensitive information on either the node level (node-DP) or the edge level (edge-DP). For (A2), a promising direction is to perform federated learning among multiple parties, or clients, such that the central server can build robust, effective and efficient predictive models while preserving the privacy of individual clients. Next, we elaborate on the two directions, including both 'quick wins' and 'hard problems', followed by additional discussions regarding the development of the user interface that could enable subject matter experts to make effective use of the developed techniques.

Privacy-preserving Generation
=============================

Graphs represent complex relational information between entities, such that modeling the graph generation process and then generating many more meaningful graphs could contribute to various applications @DBLP:journals/csur/BonifatiHPS20. However, mimicking the observed graph as much as possible will induce a privacy risk after the generation @DBLP:series/ads/WuYLC10. For example, a node's identity is highly likely to be exposed in the generated social network if its connections are mostly preserved, which means a degree-based node attacker will easily detect a vulnerability in the generated graph with some background knowledge.

Quick Wins
----------

For privacy-preserving static graph generation, current solutions can be roughly classified into two types that can be readily applied. First, the anonymization is directly performed on the observed topology to generate new graph data, such as randomizing the adjacency @DBLP:conf/sdm/YangW08, injecting the connection uncertainty @DBLP:conf/ccs/NguyenIR15, or permutating the connection distribution under the edge-level differential privacy (edge-DP) @DBLP:conf/ccs/QinYYKX017. Second, following the synergy of deep learning and differential privacy @DBLP:conf/ccs/AbadiCGMMT016, deep generative models for graphs are recently proposed under privacy constraints. To be specific, in @DBLP:conf/ijcai/YangWZCS21, the privacy scheme is added to the gradient descent phase of the generation learning process.

Hard Problems
-------------

Most, if not all, of privacy-preserving graph generation methods consider the observed graphs as static. However, in the complex real-world scenarios, the graphs are usually evolving over time @DBLP:conf/kdd/FuZH20 [@DBLP:conf/cikm/FuXLTH20; @DBLP:conf/sigir/FuH21; @DBLP:journals/corr/abs-2107-02168; @DBLP:journals/corr/abs-2203-04928], which brings critical challenges to the current privacy-preserving static graph generation process. To the best of our knowledge, how to generate privacy-preserving temporal graphs largely remains open. For example, (1) unlike the abundant research on static graphs, what kind of time-aware information is sensitive and should be hidden in the generated graph to protect entities' privacy is not clear; (2) even if the sensitive information is determined, the time-aware protection mechanism is not yet available; (3) once the protection mechanism is designed, it can be challenging to maintain the generation utility at the same time with privacy constraints.

Federated Learning with Graphs
==============================

User Interface
==============

Conclusion
==========

In this paper, we discussed privacy-preserving analysis of graph data in two directions, namely secure generation and federated learning. We believe that research efforts dedicated to these directions can lead to significantly enhanced capabilities of the Homeland Security Enterprise for countering the various security risks.

{'source': 'arXiv_out/2207'}