# Decentralized Privacy Preservation for Critical Connections in Graphs

Conggai Li, Wei Ni, Ming Ding, , Youyang Qu, ,
Jianjun Chen, David Smith, Wenjie Zhang, , and Thierry Rakotoarivelo  C. Li,
W. Ni, M. Ding, Y. Qu, D. Smith, T. Rakotoarivelo are with the Data 61,
Commonwealth Scientific and Industrial Research Organisation (CSIRO), Sydney,
NSW 2016. E-mail: {conggai.li, wei.ni, ming.ding, youyang.qu, david.smith,
<EMAIL_ADDRESS>
J. Chen is with the Australian Artificial Intelligence Institute, University
of Technology Sydney, Sydney, NSW 2007. Email:
<EMAIL_ADDRESS>
W. Zhang is with the School of Computer Science and Engineering, University of
New South Wales, Sydney, NSW 2052. E-mail<EMAIL_ADDRESS>Manuscript
received; revised.

###### Abstract

Many real-world interconnections among entities can be characterized as
graphs. Collecting local graph information with balanced privacy and data
utility has garnered notable interest recently. This paper delves into the
problem of identifying and protecting critical information of entity
connections for individual participants in a graph based on cohesive subgraph
searches. This problem has not been addressed in the literature. To address
the problem, we propose to extract the critical connections of a queried
vertex using a fortress-like cohesive subgraph model known as $p$-cohesion. A
user’s connections within a fortress are obfuscated when being released, to
protect critical information about the user. Novel merit and penalty score
functions are designed to measure each participant’s critical connections in
the minimal $p$-cohesion, facilitating effective identification of the
connections. We further propose to preserve the privacy of a vertex enquired
by only protecting its critical connections when responding to queries raised
by data collectors. We prove that, under the decentralized differential
privacy (DDP) mechanism, one’s response satisfies $(\varepsilon,\delta)$-DDP
when its critical connections are protected while the rest remains
unperturbed. The effectiveness of our proposed method is demonstrated through
extensive experiments on real-life graph datasets.

###### Index Terms:

Differential privacy, query release, critical connections, $p$-cohesion.

##  1 Introduction

Graphs have been widely used to model relationships among entities, e.g.,
social networks and protein interactions. Connections among entities in graphs
might reveal individual participants’ private information [1, 2]. A serious
privacy concern arises when graphs are probed and queried; e.g., queries, such
as subgraph counting [3], may be raised. Replies to these queries can
adversely affect the privacy of individuals on the graphs, especially in the
face of powerful graph analytic tools, e.g., graph neural networks and graph
convolutional networks, that can be misused to recover the structures of
graphs and excavate private information based on queries, e.g., subgraph
counting queries. Several mechanisms have been proposed to enhance the privacy
of entities involved in a graph and their associated vertices and edges [4].
For example, specific noises can be added to perturb the replies for such
graph analytics [5], with limited success because of several unresolved
issues.

One of the key challenges in privacy-enhanced graph analytics is correctly
identifying critical connections of a vertex that are vulnerable to privacy
leakage, and effectively obfuscating such sensitive information. In many
cases, a cohesive subgraph regarding a vertex captures noteworthy
transactional interactions among the vertex and its peers that are
particularly important to it. A variety of cohesive subgraph models has been
developed in the literature to find core connections from a whole graph, such
as $k$-core [6, 7], $k$-truss [8, 9], clique [10, 11], and $p$-cohesion [12,
13, 14, 15]. Among these, $p$-cohesion provides a fortress-like cohesive
subgraph, which has been shown effective in applications such as modelling the
epidemic’s spread into the finite user group [16, 14, 17]. Given a graph $G$
and a critical number $p\in(0,1)$, the $p$-cohesion refers to a connected
subgraph, in which every vertex has at least a fraction $p$ of its neighbors
within the subgraph [12]. These connections, identified by the critical number
$p$, are called critical connections and can disclose sensitive information
about a user, such as infection status [14], and therefore, should not be
released without proper obfuscation. Users outside the fortress contain less
sensitive information and can be disclosed without compromising the users
within the fortress. The minimal $p$-cohesion of a vertex, an elementary unit
of a $p$-cohesion, is not only cohesive but dense as well, containing the most
critical information/relationship regarding the vertex in the graph.

However, there are no existing solutions specifically designed to protect the
privacy of critical connections. In [5], Extended Local View (ELV) was
proposed as an elementary unit for graph data protection, which only focuses
on the proximity of a vertex enquired and does not capture the critical
connections of the vertex. This technique cannot be directly applied to
protect the privacy of the critical connection. Rigorous qualification and
validation are required.

In this paper, we propose to protect the privacy of a vertex by giving
priority to protecting its critical connections. The critical connections of a
vertex collect the edges forming a dense subgraph centered around the vertex,
and can capture essential interactions between the vertex and others,
potentially containing sensitive information about the vertex. We propose to
identify the critical connections of a vertex as a dense minimal $p$-cohesion
that includes the vertex enquired. To achieve this, we propose new merit and
penalty score functions to identify the minimal $p$-cohesion, i.e., critical
connections, for each vertex. The functions find $p$-cohesions with higher
densities and stronger cohesiveness. To protect the privacy of the identified
critical connections, we formulate a differentially private query release
problem ($k$-clique counting) under the Decentralized Differential Privacy
(DDP) mechanism, where a two-phase framework [5] is applied. We qualify the
use of the $(\varepsilon,\delta)$-DDP for preserving the privacy of targeted
vertices upon query releases on the minimal $p$-cohesions.

Figure 1: Motivating Example

######  Example 1.

Suppose that we have a small social network $G$ with $17$ users, which is
illustrated in Fig. 1. For each user $u_{i}\in G$, the number of neighbors
required in a $p$-cohesion is shown with a grey-filled dotted line square,
when $p=0.5$. User $u_{0}$’s $p$-cohesion $C_{p}$ is enclosed in a dashed
oval, encompassing all relationships. By contrast, $u_{0}$’s critical
relationships (a minimal p-cohesion $MC_{p}$) are marked within a grey-filled
dashed circle—these connections are heavily interconnected. Applying the DDP
mechanism to protect $u_{0}$’s all connections would introduce excessive noise
and deteriorate the data utility. By contrast, protecting $u_{0}$’s
connections with a focus on those critical, i.e., $MC_{p}$, under the same
mechanism can balance data utility and privacy.

Contributions. The main contributions are as follows:

  * •

Identify critical connections. To identify the critical connections, we
propose new score functions to effectively extract minimal $p$-cohesions
(i.e., critical connections) from a graph with different scales. Those score
functions are proposed based on graph density, which is conducive to finding
minimal $p$-cohesions with higher densities and strong cohesiveness.

  * •

Privacy preservation for critical connections in response to queries. To
protect the identified critical connections of a vertex in response to a query
(i.e., $k$-clique counting), we adopt the DDP mechanism and prove that
$(\varepsilon,\delta)$-DDP can be satisfied by only protecting the information
of those identified critical connections.

  * •

Experimental Verification. We conduct comprehensive experiments on real-life
graph datasets. For $k$-clique counting, we demonstrate our proposed framework
provides $(\varepsilon,\delta)$-DDP guarantee to protect the critical
connections of vertices and achieves higher data utility than the ELV-based
solution [5].

The remainder of this paper is as follows. In Section 2, we present the
preliminary knowledge for this paper, followed by problem formulation and
high-level solution in Section 3. The procedure for identifying critical
connections is shown in Section 4, which is the foundation of the
differentially private query release proposed in Section 5. The performance of
the model is evaluated in Section 6. Related studies are reviewed in Section
7. A conclusion is reached in Section 8.

##  2 Preliminary

TABLE I: Summary of Notations

Notation | Definition
---|---
$G$ | An unweighted and undirected graph
$V(G),E(G)$ |  The vertex set and the edge set of the graph $G$
$u$ ($v$) | A vertex in the graph
$n$, $m$ |  Numbers of vertices and edges in $G$
$N(v,G)$ |  The set of adjacent vertices (neighbors) of $v$ in $G$
$\mathcal{F}$ | A subgraph model
$N_{1h}^{v}(G)$ |  The set of $1$-hop neighbors of $v$ in $G$, i.e., $N(v,G)$
$deg(v,G)$ |  The degree of $v$ in $G$, i.e., $deg(v,G)$ = $|N(v,G)|$
$C_{p}(v,G)$ |  A $p$-cohesion containing $v$ in $G$
$MC_{p}(v,G)$ |  A minimal $p$-cohesion containing $v$ in $G$
$d(G)$ |  The density of graph $G$
$\Gamma_{S}(v)$ | The count of shape $S$ containing $v$ in graph $G$
$\Gamma_{S_{in}}(v)$ | The count of shape $S$ containing $v$ that entirely in $MC_{p}(v,G)$
$\Gamma_{S_{out}}(v)$ |  The count of shape $S$ containing $v$ that are partially or entirely outside $MC_{p}(v,G)$, i.e., $\Gamma_{S_{out}}(v)=\Gamma_{S}(v)-\Gamma_{S_{in}}(v)$

Given an undirected and unweighted graph $G=(V,E)$, where $V$ (resp. $E$) is
the set of vertices (resp. edges), we use $n=|V|$ and $m=|E|$ to denote the
number of vertices and edges, respectively. Suppose $N(v,G)$ is the neighbor
of $v$ in $G$, we use $deg(v,G)$ to denote the degree of $v$ in $G$, where
$|N(v,G)|=deg(v,G)$. Let $S$ denote a subgraph of $G$. We use $V(S)$ to
represent the vertices of $S$. When the context is clear, we may omit the
target graph in notations, e.g., using $N(v)$ (resp., $S$) instead of $N(v,G)$
(resp., $V(S)$). Table I summarizes the notations.

$p$-Cohesion. In [15], it is shown that $p$-cohesion is a fortress-like
cohesive subgraph, in which, every vertex has at least a fraction $p$ of its
neighbors in the subgraph, i.e., at most a fraction $(1-p)$ of its neighbors
outside. In other words, a $p$-cohesion can ensure inner cohesiveness.

######  Definition 1.

($p$-Cohesion). Given a graph $G$, a real value $p\in(0,1)$, and a connected
subgraph $S$, if for any vertex $v\in S$ with $deg(v,S)\geq\lceil p\times
deg(v,G)\rceil$, we say $S$ is a $p$-cohesion, denoted by $C_{p}(G)$.

Let $C_{p}(v,G)$ be the $p$-cohesion containing $v$. We use $C_{p}(v)$ instead
of $C_{p}(v,G)$ when the context is clear.

Minimal $p$-cohesion. A subgraph $S$ is a minimal $p$-cohesion if no proper
subgraph $S^{\prime}\subset S$ that qualifies as a $p$-cohesion. For example,
irrespective of the chosen $p$ value, for every vertex in graph $G$, the whole
graph $G$ is a $p$-cohesion but not minimal. Since minimal $p$-cohesion is the
elementary unit of a $p$-cohesion, we concentrate on determining the minimal
$p$-cohesion that includes a specific vertex $v$. For a $p$-cohesion
$C_{p}(v)$, by deleting every redundant vertex in $C_{p}(v)$ except $v$, we
can obtain the minimal $p$-cohesion that includes $v$, denoted by
$MC_{p}(v,G)$. In the following, when we say “the $p$-cohesion containing
$v$”, we mean the minimal one.

######  Definition 2.

(Critical Connection). Given a graph $G$ and a vertex $v$, we say the
connections identified by the minimal $p$-cohesion containing $v$ are $v$’s
critical connections.

Differential Privacy. Differential Privacy (DP) was first introduced by Dwork
et al. [18], and has been widely used in the privacy-enhanced release and
analysis of data.

######  Definition 3.

(DP). A randomization mechanism $\mathcal{M}$ is
$(\varepsilon,\delta)$-differentially private if, for any two neighboring
datasets $D$ and $D^{\prime}$ that differs by one record and for all
$\mathcal{S}\subseteq$ Range$(\mathcal{M})$,

$\Pr[\mathcal{M}(D)\in\mathcal{S}]\leq\Pr[\mathcal{M}(D^{\prime})\in\mathcal{S}]\cdot
e^{\varepsilon}+\delta,$ (1)

where $\varepsilon$ is the privacy budget that controls the strength of
privacy protection, and $\delta\in[0,1]$ denotes a failure probability. When
$\delta=0$, $\mathcal{M}$ is $\varepsilon$-differentially private.

Neighboring Graph. Given a graph $G=(V,E)$ with vertex (resp. edge) set is $V$
(resp. $E$), its neighboring graph $G^{\prime}=(V^{\prime},E^{\prime})$ can be
generated by either adding/removing an isolated vertex in $V$ or by
adding/removing an edge in $E$ [19, 5]. In this paper, we focus on the edge
privacy model, i.e., $V=V^{\prime}$ and $||E|-|E\cap E^{\prime}||=1$.

Neighboring Subgraph. Given a graph $G=(V,E)$, its neighboring graph
$G^{\prime}=(V,E^{\prime})$ and a subgraph model $\mathcal{F}$ (e.g.,
$p$-cohesion). For a vertex $v\in V$, under model $\mathcal{F}$, its subgraph
on $G$ is denoted by $S=\mathcal{F}(v,G)$. The neighboring subgraph
$S^{\prime}$ of $S$ on $G^{\prime}$ is $S^{\prime}=\mathcal{F}(v,G^{\prime})$,
which may be different in both edges and vertices.

Decentralized Differential Privacy (DDP). In a graph, each vertex can release
its own information to non-trusted parties using DDP.

######  Definition 4.

(DDP). Given a vertex set $V=\\{v_{1},v_{2},\dots,v_{n}\\}$ with $n$ nodes, a
subgraph model $\mathcal{F}$, a set of randomization mechanisms
$\\{\mathcal{M}_{i},1\leq i\leq n\\}$ satisfy $(\varepsilon,\delta)$-DDP, if

$\displaystyle
Pr[\mathcal{M}_{1}(\mathcal{F}(v_{1},G))\in\mathcal{S}_{1},\dots,\mathcal{M}_{n}(\mathcal{F}(v_{n},G))\in\mathcal{S}_{n}]\leq$
(2) $\displaystyle
Pr[\mathcal{M}_{1}(\mathcal{F}(v_{1},G^{\prime}))\in\mathcal{S}_{1},\dots,\mathcal{M}_{n}(\mathcal{F}(v_{n},G^{\prime}))\in\mathcal{S}_{n}]\cdot
e^{\varepsilon}\\!+\\!\delta,$

for any two neighboring graphs $G=(V,E)$ and $G^{\prime}=(V,E^{\prime})$ and
for all subsets $\\{\mathcal{S}_{i}\subseteq$ Range$(\mathcal{M}),1\leq i\leq
n\\}$.

######  Definition 5.

(Local Sensitivity under DDP [5]). Given a graph $G=(V,E)$ with $n$ nodes, its
arbitrary neighboring graph is $G^{\prime}=(V,E^{\prime})$, where
$V=\\{v_{1},v_{2},\dots,v_{n}\\}$, a subgraph model $\mathcal{F}$, and a
function $f$, the local sensitivity of $f$ is defined as:

$\displaystyle
LS(f)=\max_{G,G^{\prime}}\sum_{i=1}^{n}|f(\mathcal{F}(v_{i},G))-f(\mathcal{F}(v_{i},G^{\prime}))|$
(3)

where $\mathcal{F}(v_{i},G)$ and $\mathcal{F}(v_{i},G^{\prime})(1\leq i\leq
n)$ are the neighboring subgraphs with respect to $G$ and $G^{\prime}$,
respectively.

##  3 Problem and Approach Overview

We study the differentially private critical connection protection problem in
a graph under the client-server model. Specifically, under the DDP mechanism,
we aim to protect a vertex’s critical connections when responding to queries
(i.e., subgraph counting) raised by data analysts. The subgraph counting is to
count the occurrences of a user-specified shape (or subgraph) $S$ (e.g.,
triangle) containing a target vertex $v$ in graph $G$.

Problem Statement. Given an undirected unweighted graph $G\\!=\\!(V,\\!E)$, a
critical number $p\in(0,1)$, a privacy budget $\varepsilon$, an invalidation
probability $\delta$, a set of randomization mechanisms
$\\{\mathcal{M}_{i},1\\!\leq\\!i\\!\leq\\!n\\}$, and a user-specified shape
$S$; for each vertex $v_{i}\\!\in\\!V$, subgraphs counting under DDP for
critical connections protection is to

  * •

identify $v_{i}$’s critical connections from the minimal $p$-cohesion
containing $v_{i}$. $M\\!C_{p}(v_{i},\\!G)$ denotes the induced subgraph of
$v_{i}$’s critical connections from $G$;

  * •

count the occurrences of $S$ shapes containing $v_{i}$ in
$MC_{p}(v_{i},\\!G)$. $\Gamma_{S_{in}}(v_{i})$ denotes the count;

  * •

perturb the count $\Gamma_{S_{in}}(v_{i})$ using $\mathcal{M}_{i}$. The
perturbed count is denoted by $\Gamma_{S_{in}}^{*}(v_{i})$;

  * •

count the occurrences of $S$ shapes containing $v_{i}$ in the complementary
part of $MC_{p}(v_{i},\\!G)$ in $G$. The count is denoted by
$\Gamma_{S_{out}}(v_{i})$; and

  * •

report the total count
$\Gamma_{S}(v_{i})=\Gamma_{S_{in}}^{*}(v_{i})+\Gamma_{S_{out}}(v_{i})$ to the
data analyst, which ensures ($\varepsilon,\delta$)-DDP.

###  3.1 Overview of Our Approach

We propose the following techniques to solve the problem.

  * •

Identifying critical connections using minimal $p$-cohesions. As mentioned
earlier, $p$-cohesion is an important cohesive subgraph model [15], which can
be used to identify one’s critical connections. The $p$-cohesion forms a
fortress; i.e., the vertices inside a $p$-cohesion are more connected than
those outside. Considering the elegant fortress property of minimal
$p$-cohesion, for a vertex $v_{i}$, we use $v_{i}$’s minimal $p$-cohesion to
identify its critical connections that need to be protected. We prove that our
solution can protect the privacy of the target and its critical connections,
and as a result, can provide better data utilities than the existing ELV-based
solution developed in [5]. More details are shown in Section 4.

  * •

Protecting critical connections identified by minimal $p$-cohesions. We
propose a tailored $(\varepsilon,\delta)$-DDP mechanism, which reduces the
amount of injected noises and improves the data utility by only perturbing the
query results generated from one’s minimal $p$-cohesion and keeping the
following response as it is. For the subgraph counting query problem, the
function $f$ counts the occurrence of such shapes (or subgraphs) $S$
containing a vertex $v_{i}$. Let $MC_{p}(v_{i})$ be a minimal $p$-cohesion of
vertex $v_{i}$, which contains its critical connections and the corresponding
vertices. Let $\Gamma_{S_{in}}(v_{i})$ denote the number of occurrences of $S$
shape containing $v_{i}$ within $MC_{p}(v_{i})$. This implies that both the
vertices and the connections that form $S$ shape are entirely within
$MC_{p}(v_{i})$. Let $\Gamma_{S_{out}}(v_{i})$ denote the number of $S$ shape
that are partially or entirely outside $MC_{p}(v_{i})$, and let
$\Gamma_{S}(v_{i})$ denote the total count of $S$ shape within the entire
graph $G$, we have
$\Gamma_{S}(v_{i})=\Gamma_{S_{in}}(v_{i})+\Gamma_{S_{out}}(v_{i})$.  We only
perturb $\Gamma_{S_{in}}(v_{i})$ in response to the query regarding $v_{i}$,
i.e., reporting
$\Gamma_{S}^{*}(v_{i})=\Gamma_{S_{in}}^{*}(v_{i})+\Gamma_{S_{out}}(v_{i})$ to
the data analyst, where $\Gamma_{S_{in}}^{*}(v_{i})$ gives the perturbed
counts of the user-given shape $S$ in the minimal $p$-cohesion, i.e.,
$\Gamma_{S_{in}}^{*}(v_{i})=\Gamma_{S_{in}}(v_{i})+Lap(\lambda)$. In Section
5, we prove that perturbed response $\Gamma_{S}^{*}(v_{i})$ from $v_{i}$ still
satisfies $(\varepsilon,\delta)$-DDP for given $\varepsilon$ and $\delta$.

##  4 Critical Connection Identification

We identify critical connections with minimal $p$-cohesion. According to
Definition 1, any connected component is a $p$-cohesion, which could be large.
We devise an expand-shrink framework: Given a vertex, we repeatedly expand it
into a $p$-cohesion and then shrink it to its minimal form.

###  4.1 Expand Procedure

Starting from a queried vertex $q$, this procedure finds a $p$-cohesion
subgraph for $q$ in a bottom-up manner. Suppose $V_{p}$ is the vertex set of a
partial $p$-cohesion that includes $q$, we repeatedly expand the vertices in
$V_{p}$ to form a $p$-cohesion.

Algorithm 1 Expand ($G$, $q$, $p$)

Input : $G:$ a graph, $q:$ a queried vertex,

$p:$ a real number in ($0,1$)

Output : a $p$-cohesive subgraph containing $q$

1:$V_{p}:=\\{q\\}$; $\mathcal{Q}:=\emptyset$; $\triangleright$ $\mathcal{Q}$:
maximal priority queue

2:put all $v\in V_{p}$ to $\mathcal{Q}$ with key on $deg(v,G(V_{p}))$

3:$s(u)\leftarrow$ calculate a score for each vertex $u$ within $G$

4:while $\mathcal{Q}\neq\emptyset$ do

5: $u\leftarrow\mathcal{Q}.pop()$; $\mathcal{N}:=\emptyset$; $\triangleright$
$\mathcal{N}$: maximal priority queue

6: put all $w\in N(u,G)-V_{p}$ to $\mathcal{N}$ with key on $s(w)$

7: $b:=\max(\lceil deg(u,G)\times p\rceil-deg(u,G(V_{p})),0)$

8: $T\leftarrow$ top $b$ elements in $\mathcal{N}$; $V_{P}:=V_{P}\cup T$

9: for $w\in T$ do

10: if $deg(w,G(V_{p}))<\lceil deg(w,G)\times p\rceil$ then
$\mathcal{Q}.push(w)$

11: update score $s(v)$ for each $v\in V(G)$

12:Return $G(V_{p})$

Algorithm 1 outlines the Expand procedure for finding a $p$-cohesion
containing query vertex $q$. The set $V_{p}$ records the vertices included to
form a $p$-cohesion, starting initially with $V_{p}=\\{q\\}$ (Line 1). For
each vertex $u\in V_{p}$, it’s necessary to add $|\lceil deg(u,G)\times
p\rceil-deg(u,G(V_{p}))|$ additional vertices to $V_{p}$ to ensure $u$’s
inclusion in a $p$-cohesion. Here, $deg(u,G)$ and $deg(u,G(V_{p}))$ represent
the number of $u$’s neighbors in $V(G)$ and $V_{p}$, respectively. A priority
queue $\mathcal{Q}$ represents vertices within $V_{p}$ that do not yet meet
$p$ constraint (Line 1), ordered by $deg(v,G(V_{p}))$ in a descending order
(Line 2) If two vertices have the same degree, the one with the smaller
identifier is prioritized in $\mathcal{Q}$. For each vertex $u$, we calculate
a score $s(u)$ (Line 3).

In each iteration (Lines 4-11), the vertex $u\in\mathcal{Q}$ with the maximum
$deg(u,G(V_{p}))$ is removed from the queue at Line 5. At Lines 5-6, we
generate a maximal priority queue $\mathcal{N}$ to store the candidates that
can help $u$ to reach the $p$ constraint, i.e., $u$’s neighbors outside
$V_{p}$ (i.e., $N(u,G)-V_{p}$). For each $w\in\mathcal{N}$, its key is the
score $s(w)$ in descending order (Line 6). For two vertices with the same
score $s$, the vertex with a smaller identifier will be placed at the top of
the queue. For the chosen $u$, we add its additional $b$ neighbors to $V_{p}$,
where $b$ is the number of $u$’s neighbors that $u$ needs to meet the $p$
constraint (Line 7). Let $T$ be the top $b$ vertices in $\mathcal{N}$ with the
largest scores (Line 8). At Line 8, all vertices in $T$ are added to $V_{p}$.
For any $w\in T$ that do not satisfy $p$ constraint, we add it to
$\mathcal{Q}$ for further expansion (Lines 9-10). All vertices’ scores are
updated after one-round processing at Line 11. The algorithm will return at
Line 12 if $\mathcal{Q}$ is empty. In other words, $G(V_{p})$ is a
$p$-cohesion.

Time complexity. For $G(V_{p})$, let $\tilde{n}$ and $\tilde{m}$ represent the
number of its vertices and edges, respectively. The number of to-expand
vertices pushed into $\mathcal{Q}$ is $\tilde{n}$ (Line 4). To retrieve value
$b$ for each vertex, we need to visit its neighbors, which requires
$\mathcal{O}(m+n)$. Meanwhile, updating scores $s(\cdot)$ for the neighbors of
$u$ requires $O(deg(u,G)\times log(deg(u,G)))$. Algorithm 1’s time complexity
is $\mathcal{O}(\tilde{n}(m+n))$.

Space complexity. Sets $V_{p}$, $\mathcal{Q}$, $\mathcal{N}$, $s(\cdot)$, and
$deg(\cdot)$ each require $\mathcal{O}(n)$ space. Similarly, $G$ and
$N(\cdot)$ require $\mathcal{O}(m\\!+\\!n)$ space each. Algorithm 1’s space
complexity is $\mathcal{O}(m\\!+\\!n)$.

Score Function. In Algorithm 1, at Lines 6-8, we add $b$ of $u$’s neighbors
with the largest scores to $V_{p}$. We define two new scores: merit and
penalty, since adding one vertex $w\notin V_{p}$ to $V_{p}$ may need to
include more of $w$’s neighbors to help $w$ stay in a $p$-cohesion. A vertex
that can better balance the trade-off between merit and penalty should be
added to $V_{p}$.

Density. As mentioned in Section 3.1, for a queried vertex $q$, we search for
a subgraph containing $q$ with higher density. We first define the concept of
graph density. Given an undirected graph $G=(V,E)$, the density is defined as:

$d(G)=2|E|/(|V|(|V|-1)),$ (4)

where $|V|$ (resp. $|E|$) is the number of vertices (resp. edges) in $G$, and
$0<d(G)\leq 1$. $d(G)=1$ means the graph $G$ is fully connected, i.e., the
graph is the densest.

Given the partial vertex set $V_{p}$ of a $p$-cohesion that includes queried
vertex $q$, let $G(V_{p})$ and $E(G(V_{p}))$ be its induced subgraph and the
corresponding edge set, respectively. We have $E(G(V_{p}))=\\{(u,v)|(u,v)\in
E,u\in V_{p},v\in V_{p}\\}$. Based on Eq. (4), the density of $G(V_{p})$ is
given by:

$d(G(V_{p}))=2|E(G(V_{p})|/(|V_{p}|(|V_{p}|-1)).$ (5)

When adding a vertex $w\notin V_{p}$ to $V_{p}$, the density is:

$d(G(V_{p}\cup\\{w\\}))=\frac{2(|E(G(V_{p}))|+deg(w,G(V_{p})))}{(|V_{p}|+1)|V_{p}|}.$
(6)

By adding a candidate $w$ with larger $deg(w,G(V_{p}))$, the density of the
resulting subgraph can be increased.

Furthermore, we may need to include additional neighbors of $w$ into $V_{p}$
to maintain $p$-cohesion. Let $l$ be the number of neighbors required for $w$
to maintain a $p$-cohesion. We have $l=\max(\lceil deg(w,G)\times p\rceil-
deg(w,G(V_{p})),0)$. Let $N_{c}(w)=\\{o_{1},o_{2},\dots,o_{l}\\}$ ($o_{i}\in
N(w,G-G(V_{p}))\\}$) be $w$’s neighbors (outside $V_{p}$) chosen to be
expanded to $V_{p}$, and $\widetilde{V_{p}}=V_{p}\cup\\{w\\}\cup N_{c}(w)$.
The potential density of $G(\widetilde{V_{p}})$ is:

$\displaystyle
d(G(\widetilde{V_{p}}))\approx\frac{2}{(|V_{p}|+1+l)(|V_{p}|+l)}$ (7)
$\displaystyle\\!\times\\!(|E(G(V_{p}))|\\!+\\!deg(w,G(V_{p}))\\!+\\!\sum_{i=1}^{l}(1+deg(o_{i},G(V_{p})))).$

Generally speaking, the potential density depends primarily on
$d^{\prime}=\frac{deg(w,G(V_{p}))+\sum_{i=1}^{l}1+deg(o_{i},G(V_{p}))}{l(l+1)}$.
A higher $d^{\prime}$ value will result in a higher subgraph density: the
vertex $w$ with larger $deg(w,G(V_{p}))$ and more neighbors in common with $q$
in $V_{p}$ should be chosen. In light of this, we propose the following merit
score.

Merit. The inclusion of a vertex $w\notin V_{p}$ should (i) increase the
density of $G(V_{p})$ and (ii) contribute to the decrease of the number of
$w$’s neighbors $u$ in $V_{p}$ with $deg(u,G(V_{p}))<\lceil deg(u,G)\times
p\rceil$. We define the merit score of $w$ as follows:

$s\\!^{+}\\!(w)\\!=\\!\frac{deg(w\\!,\\!G\\!(\\!V_{p}\\!))}{deg(w\\!,\\!G)}\\!\times\\!\frac{|N_{cn}(w\\!,\\!q\\!,\\!G\\!(\\!V_{p}\\!))|}{deg(w\\!,\\!G)}\\!\times\\!\frac{|N_{ctri}(w\\!,\\!G\\!(\\!V_{p}\\!))|}{deg(w\\!,\\!G)},$
(8)

where $N_{cn}(w,\\!q,\\!G(V_{p}))$ is the common neighbors between $w$ and $q$
in $V_{p}$, and
$N_{cn}(w,q,G(V_{p}))\\!=\\!\\{u|u\\!\in\\!N(q,\\!G(V_{p})),\\!u\\!\in\\!N(w,G(V_{p})),\\!w\\!\notin\\!V_{p}\\}$.
Similarly, $N_{ctri}(w,G(V_{p}))$ is the set of $w$’s neighbor $u$ in $V_{p}$
that do not satisfy the $p$ constraint, i.e.,
$N_{ctri}(w,G(V_{p}))\\!=\\!\\{u|u\\!\in\\!N(w,\\!G(V_{p})),\\!deg(u,\\!G(V_{p}))\\!<\\!\lceil\\!deg(u,G)\\!\times\\!p\\!\rceil\\}$.
The first two parts of $s^{+}(w)$ account for the influence on the $G(V_{p})$
density when adding $w$ to $V_{p}$. The third part of $s^{+}(w)$ is $w$’s
contribution to the increase in the degrees of some vertices within $V_{p}$.
To eliminate the influence of dimension between indicators, we normalize each
part of $s^{+}(w)$ by $deg(w,G)$ in Eq. (8).

Penalty. To expand a vertex $u\\!\in\\!V_{p}$, adding its neighbor
$w\\!\notin\\!V_{p}$ will have A penalty effect: (i) $w$ may need more
neighbors to meet $p$ constraint, and (ii) $d(G(\\!\widetilde{V_{p}}\\!))$ may
be no larger than $d(G(\\!V_{p}\\!))$ if adding both $w$ and its outside
neighbors $N_{c}(w)$. To quantify this effect, we propose the penalty score:

$s^{-}(w)=\frac{\overline{deg}(w,G(V_{p}))}{deg(w,G)}/(\sum_{i=1}^{l}\frac{deg(o_{i},G(V_{p})))}{deg(w,G)}),$
(9)

where
$\overline{deg}(w,\\!G(\\!V_{p}\\!))\\!=\\!\max(0,\\!\lceil\\!deg(w,G)\\!\times\\!p\\!\rceil\\!-\\!deg(w,G(V_{p})))$
is the number of $w$’s neighbors that is required to meet the $p$ constraint,
and $l\\!=\\!\overline{deg}(w,G(V_{p}))$. $o_{i}$ is $w$’s neighbor outside
$V_{p}$ (i.e., $o_{i}\in N(w,\\!G\\!-\\!G(V_{p}))$). Adding $w$ may need more
vertices to be added to $V_{p}$, which may decrease the density. To lessen
this effect, we place $\overline{deg}(w,G(V_{p}))$ at the numerator. Besides,
as shown in Eq. (7), including a vertex $o_{i}$ with larger
$deg(o_{i},G(V_{p}))$ could result in a larger density. To enlarge $o_{i}$’s
effect, we place $deg(o_{i},G(V_{p}))$ at the denominator. We also normalize
each part by $deg(w,G)$.

Considering both merit and penalty, we propose the overall score for each
vertex outside $V_{p}$ as follows:

$s(w)=s^{+}(w)-s^{-}(w).$ (10)

The score $s(\cdot)$ can help to decide which vertex should be added to
$V_{p}$ in Line 6 of Algorithm 1

######  Example 2.

For the graph $G$ in Fig. 1, suppose $q=u_{0}$, in Algorithm 1, $u_{0}$ will
be popped in the first iteration, i.e., $u=u_{0}$ (Line 5). The candidates
will be
$\mathcal{N}\\!=\\!\\{u_{1},\\!u_{2},\\!u_{3},\\!u_{4},\\!u_{5},\\!u_{6}\\}$
(Line 6), and $b=3$. We may first choose $u_{1}$, $u_{5}$, and $u_{6}$ to
$V_{p}$ in Lines 7-8, i.e.,
$V_{p}\\!=\\!\\{u_{0},\\!u_{1},\\!u_{5},\\!u_{6}\\}$. $u_{1}$ will be pushed
into $\mathcal{Q}$ in Lines 9-10 since it does not satisfy $p$ constraint. In
the second iteration, $u_{1}$ will be popped for further process, i.e.,
$u\\!=\\!u_{1}$. The candidates for $u_{1}$ are
$\mathcal{N}\\!=\\!\\{u_{2},\\!u_{4},\\!u_{7},\\!u_{8}\\}$, from which,
$u_{2}$ and $u_{7}$ will be expanded, i.e.,
$V_{p}\\!=\\!\\{u_{0},\\!u_{1},\\!u_{5},\\!u_{6},\\!u_{2},\\!u_{7}\\}$. Since
$u_{1}$’s $b\\!=\\!\max(3-1,\\!0)\\!=\\!2$ and, $u_{2}$, $u_{7}$ are with the
top two largest score in $\mathcal{N}$, i.e.,
$s(u_{2})\\!=\\!s^{+}(u_{2})\\!-\\!s^{-}(u_{2})\\!=\\!\frac{2}{5}\\!-\\!\frac{\frac{3-2}{5}}{\dots}\\!=\\!-\frac{3}{5}$,
$s(u_{7})\\!=\\!\frac{4}{3}$, $s(u_{4})\\!=\\!-\frac{3}{5}$,
$s(u_{8})\\!=\\!-\frac{4}{5}$. $u_{2}$ will be pushed into $\mathcal{Q}$ for
further expernsion in Lines 9-10. In the next two iterations, $u_{3}$ and
$u_{4}$ will be expanded respectively, i.e.,
$V_{p}\\!=\\!\\{u_{0},\\!u_{1},\\!u_{5},\\!u_{6},\\!u_{2},\\!u_{7},\\!u_{3},\\!u_{4}\\}$.
Then $\mathcal{Q}$ will be empty. Algorithm 1 returns the subgraph induced by
$V_{p}\\!=\\!\\{u_{0},\\!u_{1},\\!u_{5},\\!u_{6},\\!u_{2},\\!u_{7},\\!u_{3},\\!u_{4}\\}$.

###  4.2 Shrink Procedure

The expanded $p$-cohesion containing $q$ returned by Algorithm 1 may include
redundant vertices. To further minimize the vertices number in $p$-cohesion
and identify $q$’s close connections, redundancies need to be removed.

Algorithm 2 Shrink ($C_{p}(q,G)$, $q$, $p$)

Input: $C_{p}(q,G):$ a $p$-cohesion of graph $G$ containing $q$,

$q:$ a queried vertex, $p:$ a real value within $(0,1)$

Output : a minimal $p$-cohesive subgraph containing $q$

1:$S\leftarrow C_{p}(G)$;$M_{q}:=\\{q\\}$ $\triangleright$ $M_{q}$: a must
included vertex set

2:$Tag\leftarrow[0]*|V(S)|$; $Tag[q]:=2$;

3:while $0\in Tag$ do

4: for $v\in S$ do

5: if $Tag[v]>0$ then continue

6: $S^{\prime}\leftarrow S$; $Tag^{\prime}\leftarrow Tag$

7: $S\leftarrow S-\\{v\cup E(v)\\}$; $Tag[v]:=1$

8: while $\exists u\in S$ with $deg(u,S)<\lceil deg(u,G)\times p\rceil$ do

9: $S\leftarrow S-\\{u\cup E(u,S)\\}$; $Tag[u]:=1$

10: if $\exists u\in M_{q}~{}\&~{}u\notin S$ then

11: $S\\!\leftarrow\\!S^{\prime}$;
$Tag\\!\leftarrow\\!Tag^{\prime}$;$M_{q}\\!\leftarrow\\!M_{q}\cup\\{v\\}$;
$Tag[v]:=2$

12:Return $S$

Algorithm 2 shows the pseudo-code of Shrink procedure, which finds a minimal
$p$-cohesion that includes the queried vertex $q$. Here, $C_{p}(q,G)$
represents a $p$-cohesion containing $q$, which is obtained from the output of
Algorithm 1. We use $M_{q}$ to record vertices that must be included in a
minimal $p$-cohesion that includes $q$. Initially $M_{p}=\\{q\\}$ (Line 1).
$S$ is a back-up of $C_{p}(q,G)$ (Line 1). The set $Tag$ ensures the deletion
of each selected vertex only once. Initially, all vertices in $S$ have
$Tag[i]=0$ ($1\leq i\leq|V(S)|$), except for the queried vertex $q$
($Tag[q]=2$). $Tag[i]=0$ means the vertex $i$ has not been proceeded,
$Tag[i]=1$ means vertex $i$ has been deleted, and $Tag[i]=2$ (Line 2) means
vertex $i$ must be included in the minimal $p$-cohesion.

We proceed to delete vertex $v\in S$ with $Tag[v]=0$ (Lines 3-11). Sets
$S^{\prime}$ and $Tag^{\prime}$ are used for recovering, since $v$’s removal
may result in the removal of vertices in $M_{q}$ (Lines 10-11). After removing
$v$, its corresponding edges will be removed and its tag will be set as
$Tag[v]=1$ (Line 7). The removal of $v$ may cause the $p$-cohesion violation
for some vertices in $S$, we remove those vertices and their corresponding
edges at Lines 8-9. If $v$’s removal will result in the deletion of any vertex
in $M_{q}$, we will roll back $S$, $Tag$ and put $v$ into $M_{q}$, which means
$v$ cannot be removed and must be included in the minimal $p$-cohesion that
includes $q$ (Lines 10-11). After trying each vertex’s removal, the algorithm
returns the minimal $p$-cohesion that includes $q$.

Time complexity. We use $\tilde{n}$ and $\tilde{m}$ to represent the number of
vertices and edges in $S$, respectively. Visiting every vertex in $S$ and
$Tag$ takes $\mathcal{O}(\tilde{n})$ (Lines 3-4). In then case when a vertex
$v$ is removed in Line 7 or Line 9, its neighbors may breach the $p$
constraint (Line 8). Consequently, each vertex in $S$ is visited once for
removal and each edge is traversed once for degree updating, which needs
$\mathcal{O}(\tilde{m}+\tilde{n})$. The recovery of $S$ and $Tag$ requires
$\mathcal{O}(\tilde{m}+\tilde{n})$ (Line 11). Algorithm 2’s time complexity is
$\mathcal{O}(\tilde{n}^{2}(\tilde{m}+\tilde{n}))$.

Space complexity. Sets $M_{q}$, $Tag$, and $deg(\cdot)$ require
$\mathcal{O}(n)$ space each, while $G$ and $S$ require $\mathcal{O}(m+n)$
space each. Algorithm 2’s space complexity is $\mathcal{O}(m+n)$.

##  5 Differentially Private Query Release Over Critical Connections

###  5.1 Qualification of DDP on Critical Connections

In this section, we prove that by only protecting each participant’s close
connections (identified by the minimal $p$-cohesion), the query response
satisfies $(\varepsilon,\delta)$-DDP. In the following, we focus on the
fundamental problem of DP-based graph data release, i.e., subgraph counting.
Based on the description of $p$-cohesion and minimal $p$-cohesion, not all
connections of a participant are included. We only perturb the subgraph count
within the minimal $p$-cohesions. It is prudent to qualify the validity of DDP
for the subgraph count obtained on minimal $p$-cohesion.

Given graph $G$, let $N_{1h}^{v_{i}}(G)$ be the one-hop neighbors of $v_{i}$
in $G$. Given a vertex $v_{i}\\!\in\\!G$, and its minimal $p$-cohesion
$M\\!C_{p}(v_{i},G)$, we have $N_{1h}^{v_{i}}(M\\!C_{p}(v_{i}))\subseteq
N_{1h}^{v_{i}}(G)$. Given a query function $f$ and a noise scale $\lambda$,
$v_{i}$ reports its perturbed response
$\Gamma_{\\!S}^{*}(v_{i})\\!=\\!\Gamma_{\\!S_{in}}^{*}(v_{i})\\!+\\!\Gamma_{\\!S_{out}}(v_{i})$
to the data collector, where the response generated from its critical
connections in $M\\!C_{p}(v_{i})$ is
$\Gamma_{\\!S_{in}}^{*}(v_{i})\\!=\\!\Gamma_{\\!S_{in}}(v_{i})\\!+\\!Lap(\lambda)$,
$\Gamma_{\\!S_{in}}(\\!v_{i}\\!)\\!=\\!f(M\\!C_{p}(\\!v_{i}\\!))$, and the
response generated from the the complementary part of $M\\!C_{p}(v_{i},\\!G)$
in $G$ is $\Gamma_{S_{out}}$. We show that applying a randomization mechanism
$\mathcal{M}_{i}(M\\!C_{p}(v_{i},G))$ to the query response
$\Gamma_{\\!S}(\\!v_{i}\\!)$ satisfies DDP.

######  Theorem 1.

Given a graph $G$, a vertex $v_{i}$, its minimal $p$-cohesion $MC_{p}(v_{i})$,
and a noise scale $\lambda$, we can assert that
$\Gamma_{S}^{*}(v_{i})=\Gamma_{S_{in}}(v_{i})+Lap(\lambda)+\Gamma_{S_{out}}(v_{i})$
ensures $\frac{LS(\Gamma_{S_{in}})}{\lambda}$-DDP, where $LS(\Gamma_{S_{in}})$
is the maximum local sensitivity of all $\Gamma_{S_{in}}(v_{i}),1\leq i\leq
n$.

###### Proof.

Haipei et al. [5] proved that when considering all connections of $v_{i}$ to
generate a query response, the perturbed response $\Gamma_{S}^{*}(v_{i})$
satisfies $\frac{LS(\Gamma_{S}^{*})}{\lambda}$-DDP.  In this case,
$\Gamma_{S}^{*}(v_{i})=\Gamma_{S_{in}}(v_{i})+Lap(\lambda)+0$ and
$LS(\Gamma_{S})=LS(\Gamma_{S_{in}})$.

For a vertex $v_{i}\in G$, we identify critical connections to be protected
using the minimal $p$-cohesion (i.e., $MC_{p}(v_{i})$), rather than all
connections. According to Definition 1, $deg(v_{i},MC_{p}(v_{i}))\geq\lceil
deg(v_{i},G)\times p\rceil$. We can show that, for different $p$ values, our
results satisfy $\frac{LS(\Gamma_{S_{in}})}{\lambda}$-DDP, as follows.

When $p$ is large enough, i.e.,
$N_{1h}^{v_{i}}(M\\!C_{p}(v_{i}))\\!=\\!N_{1h}^{v_{i}}(G)$, all connections of
$v_{i}$ are in its minimal $p$-cohesion $MC_{p}(v_{i})$, i.e.,
$deg(v_{i},MC_{p}(v_{i}))=deg(v_{i},G)$. The query response from the
complementary part of the minimal $p$-cohesion is
$\Gamma_{S_{out}}(v_{i})\\!=\\!0$ since all connections of $v_{i}$ are
critical with larger $p$ values. Thus,
$\Gamma_{S}^{*}(v_{i})=\Gamma_{S_{in}}(v_{i})+Lap(\lambda)$, satisfying
$\frac{LS(\Gamma_{S_{in}})}{\lambda}$-DDP.

When $p$ is small, i.e., $N_{1h}^{v_{i}}(MC_{p}(v_{i}))\subset
N_{1h}^{v_{i}}(G)$, not all adjacent vertices of $v_{i}$ are included in
$MC_{p}(v_{i})$. According to Definition 1,
$deg(v_{i},MC_{p}(v_{i}))<deg(v_{i},G)$, and
$N_{1h}^{v_{i}}(MC_{p}(v_{i}))\subset N_{1h}^{v_{i}}(G)$. In this case, the
targeted query subgraphs containing $v_{i}$ that situate outside
$MC_{p}(v_{i})$ may not be empty; i.e., $\Gamma_{S_{out}}(v_{i})\\!\geq\\!0$.
The final query response reported by vertex $v_{i}$ is
$\Gamma_{S}^{*}(v_{i})=\Gamma_{S_{in}}(v_{i})+Lap(\lambda)+\Gamma_{S_{out}}(v_{i})$.
Since we do not perturb the response $\Gamma_{S_{out}}$, the response
$\Gamma_{S}^{*}(v_{i})$ is a post-processed version of
$\Gamma_{S_{in}}^{*}(v_{i})$. According to the post-processing composition
property of DP [20], $\Gamma_{S}^{*}(v_{i})$ satisfies
$\frac{LS(\Gamma_{S_{in}})}{\lambda}$-DDP.  ∎

In practice, the local sensitivity of the graph $G$ may not be available and
needs to be estimated based on the feedback of all participants,
$v_{i},\forall i$. We adopt a two-phase framework as in [5] to estimate local
sensitivity, decide noise scale, and perturb responses to subgraph counting
queries. Specifically, Phase-$1$ requires each participant $v_{i}$ to
obfuscate its local sensitivity $LS(\Gamma_{S_{in}}(v_{i}))$, and reports the
obfuscated local sensitivity $\widetilde{LS(\Gamma_{S_{in}}(v_{i}))}$ to the
data collector using ($\varepsilon_{1},\delta_{1}$)-DDP. Then, the data
collector can evaluate the local sensitivity of the entire graph $G$ with
$LS(\Gamma_{S_{in}})\\!=\\!\max_{i=1}^{n}{\widetilde{LS(\Gamma_{S_{in}}(v_{i}))}}$,
which also satisfies ($\varepsilon_{1},\delta_{1}$)-DDP. Here,
$\varepsilon_{1}$ is the privacy budget, and $\delta_{1}$ is the violation
probability, i.e., the probability of privacy protection being violated. In
the case of the Laplace mechanism, $\delta_{1}$ is the probability of
$LS(\Gamma_{S_{in}}(v_{i}))>\widetilde{LS(\Gamma_{S_{in}}(v_{i}))}$, i.e., the
estimated local sensitivity of vertex $v_{i}$ is smaller than the ground truth
$LS(\Gamma_{S_{in}}(v_{i}))$.

In Phase-2, the data collector can decide the noise scale $\lambda$ based on
$LS(\Gamma_{S_{in}})$, and send $\lambda$ to the participants. Then, each
participant obfuscates its subgraph count by injecting Laplace noise
$Lap(\lambda)$ to satisfy ($\varepsilon_{2}$, $\delta_{2}$)-DDP, and reports
the obfuscated subgraph count in response to the subgraph counting queries of
the data collector. The Laplace mechanism [20] is adopted. By definition,
$\lambda=\frac{LS(\Gamma_{S_{in}})}{\varepsilon_{2}}$, and $\delta_{2}$ is the
probability of $\lambda>\frac{LS(\Gamma_{S_{in}})}{\varepsilon_{2}}$; i.e.,
the estimated noise scale of $G$ is smaller than the ground truth, $\lambda$,
and consequently, privacy is violated [5, Lemma 4.1].

######  Theorem 2.

Under the two-phase framework, the response to subgraph counting queries, with
critical connections protected, satisfies
$(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-DDP.

###### Proof.

For illustration convenience, this proof is based on triangle counting. The
key step of counting triangles is to count common neighbors between two
endpoints of a connection. Let $\varphi(v_{i})$ (resp., $\varphi_{in}(v_{i})$)
be $v_{i}$’s maximum common neighbors with others in graph $G$ (resp.,
$MC_{p}(v_{i})$). Let $Y_{i}$ be the random variables drawn from $Lap(\cdot)$
for $v_{i}$. In Phase-$1$, we have
$\varphi_{in}^{*}(v_{i})=\varphi_{in}(v_{i})+Y_{i}$, based on which the noise
scale for Phase-$2$ can be identified, i.e., $\lambda=\max_{v_{i}\in
G}\varphi_{in}^{*}(v_{i})/\varepsilon_{2}$. With at least ($1-\delta_{2}$)
probability, we have $\lambda\geq LS(\Gamma_{S_{in}})/\varepsilon_{2}$, since
$LS(\Gamma_{S_{in}})\leq\max_{v_{i}\in G}\varphi_{in}^{*}(v_{i})$.

We verify that, for any neighboring graphs $G$ and $G^{\prime}$ and for any
subgraph counts set $\Gamma_{S}^{*}$, we have

${\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}|G]\leq
e^{\varepsilon}\cdot{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}|G^{\prime}]+\delta.$
(11)

where $\mathcal{S}_{\lambda}$ (resp., $\mathcal{S}_{\Gamma_{S}}$) is an
arbitrary set of outputs from Phase-$1$ (resp., Phase-$2$).

We use $\mathcal{S}_{\lambda}^{\prime}$ to denote the subset of
$\mathcal{S_{\lambda}}$ that satisfies

$\mathcal{S}_{\lambda}^{\prime}=\\{\lambda|\lambda\in\mathcal{S}_{\lambda}~{}\&~{}\lambda\geq
LS(\Gamma_{S_{in}})/\varepsilon_{2}\\}.$ (12)

We have

$\displaystyle{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}|G]$
(13) $\displaystyle={\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}^{\prime}|G]\\!+\\!{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}\setminus\mathcal{S}_{\lambda}^{\prime}|G]$
$\displaystyle\leq{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}^{\prime}|G]+\delta_{2},$

since Phase-$1$ ensures $\lambda\geq LS(\Gamma_{S_{in}})/\varepsilon_{2}$ with
at least $1-\delta_{2}$ probability. That is, in Phase-$1$, $\lambda$ is
estimated using an $(\varepsilon_{1},\delta_{1})$-DDP. Thus, we have

${\rm Pr}[\lambda\in\mathcal{S}_{\lambda}^{\prime}|G]\leq
e^{\varepsilon_{1}}\cdot{\rm
Pr}[\lambda\in\mathcal{S}_{\lambda}^{\prime}|G^{\prime}]+\delta_{1}.$ (14)

Combining with Eq. (14), we have

$\displaystyle{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}},\lambda\in\mathcal{S}_{\lambda}^{\prime}|G]$
(15) $\displaystyle={\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}}|\lambda\in\mathcal{S}_{\lambda}^{\prime},G]\cdot{\rm
Pr}[\lambda\in\mathcal{S}_{\lambda}^{\prime}|G]$ $\displaystyle\leq{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}}|\lambda\in\mathcal{S}_{\lambda}^{\prime},G]\cdot(e^{\varepsilon_{1}}\cdot{\rm
Pr}[\lambda\in\mathcal{S}_{\lambda}^{\prime}|G^{\prime}]+\delta_{1})$
$\displaystyle\leq e^{\varepsilon_{1}}\cdot{\rm
Pr}[\Gamma_{S}^{*}\in\mathcal{S}_{\Gamma_{S}}|\lambda\in\mathcal{S}_{\lambda}^{\prime},G]\cdot{\rm
Pr}[\lambda\in\mathcal{S}_{\lambda}^{\prime}|G^{\prime}]+\delta_{1}.$

Next, we show: for any $\lambda\geq LS(\Gamma_{S_{in}})/\varepsilon_{2}$ and
any noisy subgraph count set $\chi$,

${\rm Pr}[\Gamma_{S}^{*}=\chi|G]\leq e^{\varepsilon_{2}}\cdot{\rm
Pr}[\Gamma_{S}^{*}=\chi|G^{\prime}],$ (16)

which leads to

${\rm Pr}[\Gamma_{S}^{*}\in
S_{\Gamma_{S}}|\lambda\in\mathcal{S}_{\lambda}^{\prime},G]\leq
e^{\varepsilon_{2}}\cdot{\rm Pr}[\Gamma_{S}^{*}\in
S_{\Gamma_{S}}|\lambda\in\mathcal{S}_{\lambda}^{\prime},G^{\prime}].$ (17)

For vertex $v_{i}$, let $\Gamma_{S}(v_{i})$ and $\Gamma_{S}^{\prime}(v_{i})$
be its triangle numbers in $G$ and $G^{\prime}$, respectively; where
$\Gamma_{S}(v_{i})\\!=\\!\Gamma_{S_{in}}(v_{i})\\!+\\!\Gamma_{S_{out}}(v_{i})$
and
$\Gamma_{S}^{\prime}(v_{i})\\!=\\!\Gamma_{S_{in}}^{\prime}(v_{i})\\!+\\!\Gamma_{S_{out}}(v_{i})$.
We have,

$\displaystyle\frac{{\rm Pr}(\Gamma_{S}^{*}=\chi|\lambda,G)}{{\rm
Pr}(\Gamma_{S}^{*}=\chi|\lambda,G^{\prime})}$ (18)
$\displaystyle\\!=\\!\frac{\frac{1}{2\lambda}{\rm
exp}(-\frac{1}{\lambda}\\!\sum_{i=1}^{n}\\!(|\Gamma_{S}^{*}(v_{i})\\!-\\!\Gamma_{S}(v_{i})|))}{\frac{1}{2\lambda}{\rm
exp}(-\frac{1}{\lambda}\sum_{i=1}^{n}(|\Gamma_{S}^{*}(v_{i})\\!-\\!\Gamma_{S}^{\prime}(v_{i})|))}$
$\displaystyle\\!=\\!\frac{\frac{1}{2\lambda}{\rm
exp}(-\frac{1}{\lambda}\\!\sum_{i=1}^{n}\\!(|\Gamma_{S}^{*}(v_{i})\\!-\\!(\Gamma\\!_{S_{in}}(v_{i})\\!+\\!\Gamma\\!_{S_{out}}(v_{i}))|))}{\frac{1}{2\lambda}{\rm
exp}(-\frac{1}{\lambda}\\!\sum_{i=1}^{n}\\!(|\Gamma_{S}^{*}(v_{i})\\!-\\!(\Gamma_{S_{in}}^{\prime}(v_{i})\\!+\\!\Gamma\\!_{S_{out}}(v_{i}))|))}$
$\displaystyle\\!\leq\\!{\rm
exp}(\frac{1}{\lambda}\\!\sum_{i=1}^{n}|\Gamma_{S_{in}}^{\prime}(v_{i})\\!+\\!\Gamma\\!_{S_{out}}(v_{i})\\!-\\!(\Gamma\\!_{S_{in}}(v_{i})\\!+\\!\Gamma\\!_{S_{out}}(v_{i}))|)$
$\displaystyle\\!\leq\\!{\rm
exp}(LS(\Gamma_{S_{in}})/\lambda)\\!\leq\\!e^{\varepsilon_{2}}.$

Eq. (16) is proved, and the two-phase framework under our setting ensures
$(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-DDP. ∎

###  5.2 Differentially Private Query Release

In this section, we investigate the differentially private query release
problem for a graph: $k$-clique counting. To protect critical connections when
releasing responses, for each vertex, the minimal $p$-cohesion is used to
detect those relationships that need to be protected. In the following, we
show how to protect the critical connections identified by minimal
$p$-cohesion when releasing local $k$-clique counts.

In Theorem 2, we have proved that the two-phase framework for subgraph
counting ensures $(\varepsilon,\delta)$-DDP whenever
$\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon$ and
$\delta_{1}+\delta_{2}\leq\delta$. Let $\widetilde{LS(\Gamma_{S_{in}})}$ be
the estimation of the local sensitivity under the edge privacy model [19],
which should be larger than the true local sensitivity $LS(\Gamma_{S_{in}})$.
The
$\lambda=\frac{\widetilde{LS(\Gamma_{S_{in}})}}{\varepsilon_{2}}\geq\frac{LS(\Gamma_{S_{in}})}{\varepsilon_{2}}$
would be a possible noise scale. In Phase-$2$, each vertex would report the
subgraph number by injecting Laplace noise.

We proceed to estimate $LS(\Gamma_{S_{in}})$, i.e., the local sensitivity for
counting $k$-cliques inside the minimal $p$-cohesions.

$k$-Clique. $k$-Clique is a subgraph with exact $k$ vertices, and any two
distinct vertices in the subgraph are adjacent.

For $k$-cliques counting, under the edge privacy model [19], estimating the
local sensitivity $LS(\Gamma_{S_{in}})$ is to estimate the common neighbors
that inside a minimal $p$-cohesion between the two endpoints of a connection.
For a vertex $v_{i}$, to estimate its $LS(\Gamma_{S_{in}}(v_{i}))$, it should
be one of the endpoints of the updating edge. Updating edge $(v_{i},v_{j})$
will only affect the $k$-cliques containing both $v_{i}$ and $v_{j}$. We use
$\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))$ to denote the common neighbors
between $v_{i}$ and $v_{j}$ in $v_{i}$’s minimal $p$-cohesion. The common
neighbor set is defined as $\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))=\\{u|u\in
N(v_{i},MC_{p}(v_{i}),u\in N(v_{j},MC_{p}(v_{i})),v_{j}\in MC_{p}(v_{i})\\}$.
When updating edge $(v_{i},v_{j})$, the affected number of $k$-cliques
containing $v_{i}$ and $v_{j}$ should be no more than
$\tbinom{\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))}{k-2}$, since those
$k$-cliques consist of $v_{i}$, $v_{j}$ and $k-2$ of their common neighbors.
Each $k$-clique will be reported $k$ times (by each of the vertices in the
$k$-clique), and the estimated local sensitivity should be

$\widetilde{LS(\Gamma_{S_{in}})}=\max_{v_{i}\in G,v_{j}\in
MC_{p}(v_{i}),v_{j}\neq
v_{i}}k\cdot\tbinom{\dot{N}_{cn}^{T}(v_{j},v_{i},MC_{p}(v_{i}))}{k-2},$ (19)

where $\dot{N}_{cn}^{T}(v_{j},v_{i},MC_{p}(v_{i}))$ is the probabilistic upper
bound ([5, Lemma $4.1$]) of $\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))$. For
each $v_{i}\in G$ with some noise scale $\lambda_{c}$ and $\delta_{c}$, we
have

$\displaystyle\dot{N}_{cn}^{T}(v_{j},v_{i},MC_{p}(v_{i})))$
$\displaystyle=\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))$ (20)
$\displaystyle+Lap(\lambda_{c})+\lambda_{c}\cdot\log(\frac{1}{2\delta_{c}}).$

Counting common neighbors of two vertices is time-consuming. For any vertex
$v_{i}\in G$, we have $deg(v_{i},MC_{p}(v_{i}))\geq\max_{v_{j}\in
MC_{p}(v_{i}))}\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))$. The degree of a
vertex can be treated as a loose upper bound for its maximum common neighbors
with others. However, the local sensitivity based on the degree can be too
large, leading to adding excessive noises. Replacing $\max_{v_{j}\in
MC_{p}(v_{i})}\dot{N}_{cn}(v_{j},v_{i},MC_{p}(v_{i}))$ with
$deg(v_{i},MC_{p}(v_{i}))$ for some $v_{i}$ can balance the efficiency and
effectiveness [5]. For $v_{i}\in G$ with some $\lambda_{d}$ and $\delta_{d}$,
we have

$deg^{T}(v_{i}\\!,\\!MC_{p}\\!(\\!v_{i}\\!))\\!=\\!deg(v_{i}\\!,\\!MC_{p}\\!(v_{i}\\!))\\!+\\!Lap(\lambda_{d})+\\!\lambda_{d}\\!\log(\frac{1}{2\delta_{d}}).$
(21)

For vertices with the top $h$ largest $deg^{T}$ values, they would report
“$\min(\max\dot{N}_{cn}^{T}(\cdot),deg^{T}(\cdot))$” [5]. Let $V_{D}$ (resp.
$V_{N}$) be the set of vertices reporting $deg^{T}$ (resp.
$\max\dot{N}_{cn}^{T}$). We have $u_{d}=\max_{v_{i}\in V_{D}}$
$deg^{T}(v_{i},MC_{p}(v_{i}))$ and $u_{n}=\max_{v_{i}\in V_{N},v_{j}\in
MC_{p}(v_{i}),v_{j}\neq v_{i}}\dot{N}_{cn}^{T}(v_{j},v_{i},$ $MC_{p}(v_{i}))$
and $\widetilde{LS(\Gamma_{S_{in}})}=k\cdot\tbinom{\max(u_{d},u_{n})}{k-2}$.
As proved in [5, Lemma $4.2$], with
$\lambda_{d}=\frac{2}{0.5\varepsilon_{1}}$,
$\lambda_{c}=\frac{h}{0.5\varepsilon_{1}}$, and
$\delta_{d}=\delta_{c}=\frac{\delta}{2h+2}$, the following algorithm satisfies
$(\varepsilon_{1},\delta)$-DDP and the returned noise scale
$\lambda=\frac{\widetilde{LS(\Gamma_{S_{in}})}}{\varepsilon_{2}}$ for
Phase-$2$ satisfies $\lambda\geq\frac{LS(\Gamma_{S_{in}})}{\varepsilon_{2}}$.

Algorithm 3 Phase-$1$ on $k$-clique ($G$, $p$, $\varepsilon_{1}$,
$\varepsilon_{2}$, $\delta$, $h$, $k$)

Input : $G:$ a graph, $p:$ a real value in ($0,1$),

$\varepsilon_{1}:$ privacy budget for Phase-$1$,

$\varepsilon_{2}:$ privacy budget for Phase-$2$,

$\delta:$ invalidation probability, $h:$ an int value,

$k:$ the vertices constraint for $k$-clique

Output : noise scale $\lambda$

1:$\lambda_{d}:=\frac{2}{0.5\varepsilon_{1}}$;
$\delta^{\prime}:=\frac{\delta}{2h+2}$;
$\lambda_{c}:=\frac{h}{0.5\varepsilon_{1}}$ $\triangleright$ Server

2:$U\leftarrow\emptyset$; $\mathcal{R}\leftarrow\emptyset$; $\triangleright$
$\mathcal{R}$: a family of $R$

3:for $v\in G$ do

4: $R^{\prime}:=$ Expand $(G,v,p)$ $\triangleright$ Algorithm 1, Client

5: $R:=$ Shrink $(R^{\prime},v,p)$ $\triangleright$ Algorithm 2, Client

6: $\mathcal{R}.push(R)$

7:
$U(v):=deg(v,R)+Lap(\lambda_{d})+\lambda_{d}\cdot\log(\frac{1}{2\delta^{\prime}})$
$\triangleright$ Client

8:put all $v\in G$ into a maximal priority queue $\mathcal{Q}$ with key $U(v)$
$\triangleright$ Server

9:$T\leftarrow$ the top $h$ elements in $\mathcal{Q}$ $\triangleright$ Server

10:for $v\in T$ do

11: $R:=\mathcal{R}(v)$; $cn:=0$

12: for $u\in R$ do $cn:=\max(\dot{N}_{cn}(u,v,R),cn)$ $\triangleright$ Client

13:
$cn^{*}:=cn+Lap(\lambda_{c})+\lambda_{c}\cdot\log(\frac{1}{2\delta^{\prime}})$
$\triangleright$ Client

14: $U(v):=\min(cn^{*},U(v))$ $\triangleright$ Server

15:$\widetilde{LS}:=k\cdot\tbinom{\max_{v\in G}U(v)}{k-2}$ $\triangleright$
Server

16:Return $\lambda=\frac{\widetilde{LS}}{\varepsilon_{2}}$ $\triangleright$
Server

The pseudo-code of Phase-$1$ on $k$-clique counting is given in Algorithm 3.
We use set $U$ (Line 2) to denote the upper bounds for each vertex’s maximum
common neighbors with all others in its minimal $p$-cohesion $MC_{p}(v_{i})$.
By running Algorithm 1 and Algorithm 2, for each vertex $v$, we identify the
minimal $p$-cohesion $R$ containing its critical connections, and then store
it in a family set $\mathcal{R}$ (Lines 4-6). In Line 7, we compute the loose
upper bound based on its degree in $R$. Vertices in $G$ with the first $h$
largest upper bounds, denoted by $T$, report their tight upper bounds (Lines
8-9). For each $v\in T$, we compute its maximum common neighbors with vertices
in its $R$, denoted by $cn$ (Line 12). Its upper bound is the minimal value
between $cn^{*}$ and its loose upper bound $U(v)$ (Lines 13-14). Finally, the
local sensitivity $\widetilde{LS}$ and noise scale $\lambda$ are generated for
Phase-$2$ based on set $U$ (Lines 15-16).

##  6 Evaluation

###  6.1 Experimental Setting

Datasets. We used $9$ real-life graph datasets, as described in Table II. The
Celegans and WIKIVote datasets are from [21] and the remaining ones are from
[22]. The Celegans and Yeast are two biological graphs. Celegans (resp. Yeast)
contains the metabolic reactions (resp. interactions) between two substrates
(resp. proteins). WIKIVote contains all the Wikipedia voting data from the
inception of Wikipedia. USAirport contains the flights between two US
airports. Bitcoin is a user–user trust/distrust network from the Bitcoin Alpha
platform. Gnutella08 contains the connections between two Gnutella hosts from
August $08$, $2022$. HepTh (resp. HepPh) is a co-authorship graph from arXiv,
which contains the collaborations between authors who submit their papers to
High Energy Physics - Theory (resp. Phenomenology). SisterCity contains the
“Sister City” relationships between two cities of the world. Directed edges
are transferred to undirected edges.

TABLE II: Statistics of Datasets Dataset |  Nodes |  Edges |  $d_{avg}$ |  $d_{max}$
---|---|---|---|---
Celegans [21] |  453 |  2,025 |  8.94 |  237
WIKIVote [21] |  889 |  2,914 |  6.56 |  102
USAirport [22] |  1,574 |  17,215 |  21.87 |  314
Yeast [22] |  1,876 |  2,203 |  2.39 |  56
Bitcoin [22] |  3,783 |  14,214 |  7.47 |  511
Gnutella08 [22] |  6,301 |  20,777 |  6.59 |  97
HepTh [22] |  9,875 |  25,973 |  5.26 |  65
SisterCity [22] |  14,274 |  20,573 |  2.88 |  99
HepPh [22] |  34,546 |  420,877 |  24.37 |  846

Algorithms. To the best of our knowledge, no existing work has attempted to
protect the privacy of critical connections of a vertex in a graph. We
implement our algorithms for $p$-cohesion and minimal $p$-cohesion computation
with new score functions and evaluate the effectiveness for privacy
preservation under DDP.

Settings. For $p$-cohesion computation, in our experiments, $p$ ranges from
$0.1$ to $0.8$ with the default value of $0.1$. For privacy protection of
critical connections, we count $k$-cliques under $(\varepsilon,\delta)$-DDP,
utilizing the two-phase framework. Each result is averaged over $100$ runs.
The privacy budget $\varepsilon$ ranges from $1$ to $12$. The default value of
privacy budget $\varepsilon_{1}$ (resp. $\varepsilon_{2}$) for Phase-$1$
(resp. Phase-$2$) is $\varepsilon_{1}=0.1\varepsilon$ (resp.
$\varepsilon_{2}=0.9\varepsilon$). The $h$ (Line 9 of Algorithm 3) varies from
$1$ to $12$. Following the setting in [5, 23], the default value for $\delta$
is $\frac{1}{n}$, where $n$ is the vertices number of the graph. All programs
are implemented in Python on a Linux machine.

(a) All Datasets, $p=0.3$

(b) Gnutella08

(c) HepPh

Figure 2: Density Distribution of Minimal $p$-Cohesions under Different Score
Functions

(a) All Datasets, $p=0.3$

(b) Gnutella08

(c) HepPh

Figure 3: Size Distribution of Minimal $p$-Cohesions under Different Score
Functions

(a) All Datasets, $p=0.3$

(b) USAirport

(c) SisterCity

Figure 4: Density Distribution of Minimal $p$-Cohesion and ELV

(a) All Datasets, $p=0.3$

(b) WIKIVote

(c) Yeast

Figure 5: Size Distribution of Minimal $p$-Cohesion and ELV

###  6.2 Statistical Evaluation for Minimal $p$-Cohesions

####  6.2.1 Minimal $p$-Cohesions with Different Score Functions

For each vertex $v$, we identify its minimal $p$-cohesion with Algorithms 1
and 2. Different score functions (Line 3 of Algorithm 1) result in different
$p$-cohesions and minimal $p$-cohesions. In the following, we show the
performance of Algorithms 1 and 2 in both density and size. $p$-Cohesion
denotes Algorithm 1 running (10) followed by Algorithm 2. $p$-Cohesion∗
replaces (10) in $p$-Cohesion with [15, Eq. (7)].

Density. Fig. 2 reports the graph density distribution of minimal
$p$-cohesions with different score functions. $p$-Cohesion uses Eq. (8) and
Eq. (9), and $p$-Cohesion∗ uses [15, Eqs. (5) & (6)]. Fig. 2 displays the
result over $9$ datasets at $p=0.3$. As expected, the $p$-Cohesion outperforms
$p$-Cohesion∗, because both the merit and penalty consider the advantage and
disadvantage when including a new vertex $w$ to $V_{p}$. For example, on Yeast
and HepTh, all minimal $p$-cohesions returned by $p$-Cohesion are with larger
density than the minimal $p$-cohesions returned by $p$-Cohesion∗. Figs. 2(b)
and 2(c) report the result of two different score functions, with varying
values of p ranging from $0.1$ to $0.8$ for Gnutella08 and HepPh,
respectively. Both figures illustrate the density distributions of the minimal
$p$-cohesions returned by $p$-Cohesion and $p$-Cohesion∗ become similar as $p$
increases, since higher values of $p$ inherently entail a greater number of
vertices within a $p$-cohesion subgraph. Consequently, both $p$-Cohesion and
$p$-Cohesion∗ tend to yield comparable vertex sets. As $p$ reaches large
magnitudes, the results exhibit similarity due to the near-complete inclusion
of the connected component.

Size. We show size distributions of all minimal $p$-cohesions returned by
$p$-Cohesion and $p$-Cohesion∗ in Fig. 3. Fig. 3(a) represents the result for
$9$ datasets at $p=0.3$. On most of the datasets, the minimal $p$-cohesions
returned by $p$-Cohesion have similar sizes to $p$-Cohesion∗. On some graphs,
i.e., Yeast and HepTh, our methods can find much smaller sizes minimal
$p$-cohesions. Figs. 3(b) and 3(c) report the size distributions with the two
different score functions on Gnutella08 and HepPh, respectively. Both figures
show that the sizes of minimal $p$-cohesions returned by the two methods
increase as $p$ grows. This is because a larger value $p$ necessitates a
greater number of vertices in a $p$-cohesion.

####  6.2.2 Minimal $p$-Cohesion v.s. Extended Loccal View

Haipei et al. [5] used ELV as the local view for subgraph counting. But they
could not capture critical connections. We denote the connections identified
by their two-hop ELV [5, Definition $2.2$] as ELV. From the distributions of
density and size, we compare the difference between minimal $p$-cohesion and
ELV. Here, $p$-Cohesion denotes the Algorithm 1 equipped with Eq. (10),
followed by Algorithm 2.

Density. Fig. 4 reports the density distributions comparison between
$p$-Cohesion and ELV. Fig. 4(a) displays the result across $9$ datasets at
$p=0.3$. The $p$-Cohesion significantly outperforms ELV in the subgraph
density because the $p$-Cohesion can identify a subgraph induced by the
critical connections of a vertex. For example, on USAirport, all vertices’
subgraphs returned by $p$-Cohesion have larger densities than ELV. Figs. 4(b)
and 4(c) depict the result of distinct methods, showcasing variations in $p$
values ranging from $0.1$ to $0.8$ for USAirport and SisterCity, respectively.
Both figures illustrate that when $0.1\leq p\leq 0.7$, many vertices’ minimal
$p$-cohesions are with larger density than ELV. The density of $p$-Cohesion
decreases as $p$ increases, as a larger value of $p$ inherently necessitates a
greater number of vertices in a p-cohesion.  However, when $p>0.7$, the
minimal $p$-cohesions of most vertices exhibit lower densities compared to
their ELVs. This is because a large $p$ value results in the retrieval of
nearly the entire graph.

Size. In Fig. 5, we report the size distributions of $p$-Cohesion and ELV.
Fig. 5(a) reports the result over $9$ datasets with $p=0.3$. On all datasets
and all vertices, all minimal $p$-cohesions returned by $p$-Cohesion are with
smaller sizes than ELV. Figs. 5(b) and 5(c) report the size distributions of
the two methods on WIKIVote and Yeast, as $p$ increases from $0.1$ to $0.8$.
Similarly, within both figures, the sizes of minimal $p$-cohesions yielded by
$p$-Cohesion exhibit growth as $p$ increases. This phenomenon arises due to
the greater number of vertices required for a larger $p$ in a $p$-cohesion.
When $p$ is large enough, i.e., $p>0.5$ (resp. $p>0.6$) on WIKIVote (resp.
Yeast), the $p$-Cohesion will return larger subgraphs than ELV since the
minimal $p$-cohesion needs more vertices to meet the $p$ constraint.

(a) $h=1$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(b) $h=1$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

(c) $h=3$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(d) $h=3$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

(e) $h=10$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(f) $h=10$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

Figure 6: $p$ Selection for $3$-Clique Counting on HepTh

(a) $\varepsilon=1$ ($\varepsilon_{1}=0.1$)

(b) $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(c) $\varepsilon=5$ ($\varepsilon_{1}=0.5$)

(d) $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

Figure 7: $h$ Selection for $3$-Clique Counting on Celegans, $p=0.1$

###  6.3 $k$-Clique Counting Under DDP

In this section, we focus on the influence of $h$, $p$, $\varepsilon$, and
$\varepsilon_{1}$ over $k$-clique counting. We use Mean Relative Error (MRE)
to evaluate the performance when releasing responses, based on two different
connection groups, for subgraphs counting queries. We use $p$-Cohesion (resp.
ELV) to denote the method for counting subgraphs, under the
$(\varepsilon,\delta)$-DDP, based on the minimal $p$-cohesions (ELVs). For
subgraph $S$ counting, we have MRE
$=\frac{|\Gamma_{S}^{*}-\Gamma_{S}|}{\Gamma_{S}}$, where $\Gamma_{S}$ is the
real subgraph number and $\Gamma_{S}^{*}$ is the perturbed value regarding
$\Gamma_{S}$. Each MRE reported is averaged over $100$ runs.

####  6.3.1 $3$-Clique Counting

We evaluate our algorithms for $3$-clique counting.

$p$ Selection. Fig. 6 shows the average MRE under the
$(\varepsilon,\delta)$-DDP for $3$-clique counting based on the subgraphs
returned by $p$-Cohesion and ELV on HepTh when $p$ varies from $0.1$ to $0.8$.
We show the results with $h=1,3,10$ and $\varepsilon=3.0,10.0$ for all $p$
values. As expected, when $p<0.7$, the $p$-Cohesion outperforms ELV. The
average MRE of $p$-Cohesion increases when $p$ becomes larger. When $p>0.4$,
the MRE grows slowly because, for almost all the vertices, $p$ is large enough
to include their connections within their corresponding minimal $p$-cohesions.
When $p\geq 0.7$, the ELVs will be subsets of the corresponding minimal
$p$-cohesions. It implies a reasonable $p$ can balance the data utility and
privacy protection.

(a) All Datasets with $h=3$, $\varepsilon=10$ ($\varepsilon_{1}=1$)

(b) $h=1$ ($\varepsilon_{1}=0.1\varepsilon$)

(c) $h=3$ ($\varepsilon_{1}=0.1\varepsilon$)

(d) $h=5$ ($\varepsilon_{1}=0.1\varepsilon$)

(e) $h=10$ ($\varepsilon_{1}=0.1\varepsilon$)

Figure 8: $\varepsilon$ Selection for $3$-Clique Counting on USAirport,
$p=0.1$

$h$ Selection. In Algorithm 3, to balance the efficiency and effectiveness for
noise scale $\lambda$ estimation, $h$ vertices need to report their common
neighbors, instead of degree (Lines 9-14). Fig. 7 reports the upper bound of
the local sensitivity generated by $p$-Cohesion and ELV on Celegans when $h$
varies from $1$ to $12$ with a step size of $1$. We choose $p=0.1$ for the
minimal $p$-cohesions computation. For Phase-$1$, the privacy budget is chosen
as $\varepsilon_{1}=0.1\varepsilon$ for different $\varepsilon$ values. For
different privacy budgets $\varepsilon$, the upper bounds returned by
$p$-Cohesion show similar trends as ELV. When $h=2,3$, the upper bounds are
optimal for almost all $\varepsilon$ values. Compared to ELV, with the
increase of $\varepsilon$, our $p$-Cohesion can find more optimal upper bounds
for $LS(\Gamma_{S})$.

$\varepsilon$ Selection. Fig. 8(a) reports the average MRE returned by
$p$-Cohesion and ELV on all datasets with $p=0.1$, $h=3$, and $\varepsilon=10$
(i.e., $\varepsilon_{1}=1.0$). On all datasets, $p$-Cohesion outperforms ELV.
For example, on SisterCity, the $p$-Cohesion is two orders of magnitude
smaller than ELV in terms of the average MRE. That is because our approach
injects less noise into the real response and estimates tighter local
sensitivity. Fig. 8(b) \- Fig. 8(e) report the average MRE over $p$-Cohesion
and ELV on USAirport when $\varepsilon$ varies from $1$ to $12$ with a step
size of $1$. We choose $p=0.1$ for minimal $p$-cohesions computation. For all
$\varepsilon$, the privacy budget $\varepsilon_{1}$ for Phase-$1$ is chosen as
$\varepsilon_{1}=0.1\varepsilon$. Our $p$-Cohesion shows similar trends as ELV
under all $h$ but reports increasingly better performance in terms of MRE with
$\varepsilon$ growing.

(a) All Datasets with $h=3$, $\varepsilon_{1}=0.5$ ($\varepsilon=5$)

(b) $h=3$, $\varepsilon=5$

(c) $h=5$, $\varepsilon=5$

(d) $h=7$, $\varepsilon=5$

(e) $h=10$, $\varepsilon=5$

Figure 9: $\varepsilon_{1}$ Selection for $3$-Clique Counting on Celegans,
$p=0.1$

$\varepsilon_{1}$ Selection. Fig. 9 depicts the influence of privacy budget
$\varepsilon_{1}$ of Phase-$1$ on MRE. For all $\varepsilon_{1}$, the total
privacy budget is $\varepsilon=5.0$, and we choose $p=0.1$ for the minimal
$p$-cohesion computation. The MREs represent the average values obtained from
$100$ independent tests. Fig. 9(a) shows the average MRE returned by
$p$-Cohesion and ELV on all datasets with $p=0.1$, $h=3$,
$\varepsilon_{1}=0.5$, and $\varepsilon=5.0$. Under the current setting, on
all datasets, our $p$-Cohesion outperforms ELV. Consistent with the previous
result, on SisterCity, the $p$-Cohesion is two orders of magnitude smaller
than ELV in the average MRE. Fig. 9(b) \- Fig. 9(e) report the average MRE
over $p$-Cohesion and ELV on Celegans when $\varepsilon_{1}$ varies from $0.1$
to $4.9$ with a step size of $0.1$. For all $\varepsilon_{1}$, our
$p$-Cohesion outperforms ELV in terms of the average MRE. When
$\varepsilon_{1}<1.5$, the average MRE decreases with the growth of
$\varepsilon_{1}$ since a larger $\varepsilon_{1}$ results in a smaller upper
bound for the local sensitivity $LS(\Gamma_{S})$. The average MRE reaches the
bottom ($\varepsilon_{1}\approx 1.5$), $\varepsilon_{1}$ and $\varepsilon_{2}$
reach the balance point, where $\varepsilon_{2}=\varepsilon-\varepsilon_{1}$.
When $\varepsilon_{1}>1.5$, the average MRE increases as $\varepsilon_{1}$
grows since the balance is broken and more noises are injected.

(a) $h=1$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(b) $h=1$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

(c) $h=3$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(d) $h=3$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

(e) $h=10$, $\varepsilon=3$ ($\varepsilon_{1}=0.3$)

(f) $h=10$, $\varepsilon=10$ ($\varepsilon_{1}=1.0$)

Figure 10: $p$ Selection for $4$-Clique Counting on Bitcoin

(a) All Datasets with $h=3$, $\varepsilon=10$ ($\varepsilon_{1}=1$)

(b) $h=1$ ($\varepsilon_{1}=0.1\varepsilon$)

(c) $h=3$ ($\varepsilon_{1}=0.1\varepsilon$)

(d) $h=5$ ($\varepsilon_{1}=0.1\varepsilon$)

(e) $h=10$ ($\varepsilon_{1}=0.1\varepsilon$)

Figure 11: $\varepsilon$ Selection for $4$-Clique Counting on USAirport,
$p=0.1$

####  6.3.2 $4$-Clique Counting

Under DDP, we study the influence of $p$, and $\varepsilon$ over $4$-clique
counting. In Algorithm 3, at Line 14, the estimated local sensitivity is
controlled by the $k$ value. We use $k=3$ as the building block for $4$-clique
counting, i.e., the $\lambda_{4}$ (resp. $\lambda_{3}$) returned by Algorithm
3 for $k=4$ (resp. $k=3$) is $\lambda_{4}=\frac{\lambda_{3}*4}{3}$. We do not
regenerate $\lambda$ for $4$-clique by Algorithm 3.

$p$ Selection. Fig. 10 reports the average MRE results for $p$-Cohesion and
ELV over $100$ runs on Bitcoin when $p$ varies from $0.1$ to $0.8$. We show
results with $h\\!=\\!1,3,10$ and $\varepsilon\\!=\\!3.0,10.0$ for all $p$
values. When $p<0.8$, the $p$-Cohesion outperforms ELV. The average MRE of
$p$-Cohesion increases when $p$ becomes larger since more noises are injected
into the response. Similar to the result for $3$-clique, when $p>0.4$, the MRE
grows slowly. This is because, for almost all vertices, $p$ is large enough to
include all their connections to the minimal $p$-cohesions. When $p\geq 0.8$,
ELVs will be subsets of the corresponding minimal $p$-cohesions.

$\varepsilon$ Selection. Fig. 11(a) reports average MRE returned by
$p$-Cohesion and ELV on all datasets with $p=0.1$, $h=3$, and $\varepsilon=10$
(i.e., $\varepsilon_{1}=1.0$). On all datasets, our $p$-Cohesion outperforms
ELV. Figs. 11(b) to 11(e) report the average MRE over $p$-Cohesion and ELV on
USAirport when $\varepsilon$ varies from $1$ to $12$. We choose $p=0.1$ for
the minimal $p$-cohesion computation. For all $\varepsilon$, the privacy
budget of Phase-$1$ is $\varepsilon_{1}=0.1\varepsilon$. Our $p$-Cohesion
shows similar trends as ELV under all $h$ values, but better MRE for all
$\varepsilon$ values.

##  7 Background and Related Work

We present related work from perspectives of cohesive subgraph search and
graph analysis with DP.

Cohesive subgraph search. A cohesive subgraph search aims to identify
subgraphs that contain a specific query for a given scenario. Several cohesive
subgraph models have been proposed. A clique is a subgraph with the highest
density, where every pair of vertices is connected [24, 25]. However, due to
the restrictive nature of cliques, some relaxed models have been introduced.
These include the $k$-core model [26, 6, 27], $k$-truss model [28, 29],
$k$-ecc model [30, 31], $p$-cohesive model [15, 12], and others [32, 33, 34].
In [15], minimal $p$-cohesions were detected through an expand-shrink
structure and two relatively intuitive score functions. When including one
vertex in a partial $p$-cohesion, the merit score considers the contribution
of a vertex to increasing the degrees of some vertices in the partial
$p$-cohesion. The penalty score captures the need for extra neighbors outside
the partial $p$-cohesion to meet the $p$ constraint. Using these score
functions, minimal $p$-cohesions captured may not be dense; i.e., more
vertices with fewer mutually connected edges are often captured.

We design new criteria (including a new merit function and a new penalty
function) to effectively identify minimal $p$-cohesions with increased
densities. While adopting the generic expand-shrink framework as in [15], our
new score functions help find minimal $p$-cohesions with much higher density
than the method developed in [15].

Graph analysis with DP. Many recent contributions proposed DP-based solutions
for the release and/or the analysis of graph data [4]. They were based either
on centralized DP (CDP) [35, 36], local DP (LDP) [37, 38, 39], DDP [5], or
relationship local DP (RLDP) [40]. Traditional DP techniques were primarily
designed for centralized settings, where a trusted central entity collects and
analyzes data. However, graph analysis under CDP requires the data holder to
have full information about the graph. Answering questions related to graphs
under LDP requires to collect information from individuals [41], which may
ruin the property (lower the data utility) of the raw graph [38].

To solve this problem, Haipei et al. [5] proposed privacy preservation in the
context of DDP using the ELV. Their approach ensures each participant’s
privacy concerning their connections in its ELV. Yuhan et al. [40] tried to
solve the problem under the RLDP mechanism and using the ELV. However, these
approaches solely focused on the proximity of a queried vertex and did not
capture the critical connections of the vertex within the subgraph. While
adopting the two-phase framework as in [5], our algorithm is different in the
sense that we identify the critical conditions of vertices, which are denser
and more cohesive and often part of the ELVs. We also prioritize the critical
conditions for privacy protection by dedicating the privacy budget to those
connections. As demonstrated experimentally, our approach can offer better
data utility than the existing work with all connections obfuscated, e.g.,
[5].

##  8 Conclusion

In this paper, we investigated the problem of identifying and protecting
critical connections’ information for individual participants on graphs, using
minimal $p$-cohesion. New score functions were proposed to help effectively
search the critical connections. We also analytically qualified the use of the
$(\epsilon,\delta)$-DDP to protect the privacy of the identified critical
connections. Extensive experiments confirmed the effectiveness of the new
score functions, as well as the better trade-off between utility and privacy
compared to the existing ELV-based methods.

## References

  * [1] G. Cormode, D. Srivastava, S. Bhagat, and B. Krishnamurthy, “Class-based graph anonymization for social network data,” _Proc. VLDB Endow._ , vol. 2, no. 1, pp. 766–777, 2009.
  * [2] C. Brandt and J. Leskovec, “Status and friendship: mechanisms of social network evolution,” in _Proc. WWW 2014_ , pp. 229–230.
  * [3] V. T. Chakaravarthy, M. Kapralov, P. Murali, F. Petrini, X. Que, Y. Sabharwal, and B. Schieber, “Subgraph counting: Color coding beyond trees,” in _IPDPS 2016_ , pp. 2–11.
  * [4] Y. Li, M. Purcell, T. Rakotoarivelo, D. Smith, T. Ranbaduge, and K. S. Ng, “Private graph data release: A survey,” _ACM Computing Surveys_ , vol. 55, no. 11, pp. 1–39, 2021.
  * [5] H. Sun, X. Xiao, I. Khalil, Y. Yang, Z. Qin, W. H. Wang, and T. Yu, “Analyzing subgraph statistics from extended local views with decentralized differential privacy,” in _CCS 2019_ , pp. 703–717.
  * [6] S. B. Seidman, “Network structure and minimum degree,” _Social networks_ , vol. 5, no. 3, pp. 269–287, 1983.
  * [7] B. Yang, D. Wen, L. Qin, Y. Zhang, L. Chang, and R. Li, “Index-based optimal algorithm for computing k-cores in large uncertain graphs,” in _ICDE 2019_ , pp. 64–75.
  * [8] F. Zhang, L. Yuan, Y. Zhang, L. Qin, X. Lin, and A. Zhou, “Discovering strong communities with user engagement and tie strength,” in _DASFAA 2018_ , vol. 10827, pp. 425–441.
  * [9] X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu, “Querying k-truss community in large and dynamic graphs,” in _SIGMOD 2014_. , pp. 1311–1322.
  * [10] Y. Fang, R. Cheng, S. Luo, and J. Hu, “Effective community search for large attributed graphs,” _Proc. VLDB Endow._ , vol. 9, no. 12, pp. 1233–1244, 2016.
  * [11] L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang, “Diversified top-k clique search,” _The VLDB Journal_ , vol. 25, no. 2, pp. 171–196, 2016.
  * [12] S. Morris, “Contagion,” _The Review of Economic Studies_ , vol. 67, no. 1, pp. 57–78, 2000.
  * [13] D. J. Watts, “A simple model of global cascades on random networks,” _Proceedings of the National Academy of Sciences_ , vol. 99, no. 9, pp. 5766–5771, 2002.
  * [14] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, “Epidemic processes in complex networks,” _Reviews of modern physics_ , vol. 87, no. 3, p. 925, 2015.
  * [15] C. Li, F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin, “Discovering fortress-like cohesive subgraphs,” _Knowl. Inf. Syst._ , vol. 63, no. 12, pp. 3217–3250, 2021.
  * [16] D. H. Zanette, “Critical behavior of propagation on small-world networks,” _Physical Review E_ , vol. 64, no. 5, p. 050901, 2001.
  * [17] K. Sun, W. Wang, L. Gao, Y. Wang, K. Luo, L. Ren, Z. Zhan, X. Chen, S. Zhao, Y. Huang _et al._ , “Transmission heterogeneities, kinetics, and controllability of sars-cov-2,” _Science_ , vol. 371, no. 6526, p. eabe2424, 2021.
  * [18] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Proc. TCC 2006_ , vol. 3876, pp. 265–284.
  * [19] M. Hay, C. Li, G. Miklau, and D. D. Jensen, “Accurate estimation of the degree distribution of private networks,” in _ICDM 2009_ , pp. 169–178.
  * [20] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Proc. TCC_ , vol. 3876\. Springer, 2006, pp. 265–284.
  * [21] R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in _Proc. AAAI, 2015_.
  * [22] J. Kunegis, “KONECT – The Koblenz Network Collection,” in _Proc. WWW, 2013_ , pp. 1343–1350.
  * [23] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3-4, pp. 211–407, 2014\.
  * [24] M. Danisch, O. Balalau, and M. Sozio, “Listing k-cliques in sparse real-world graphs,” in _Proc. WWW 2018_ , pp. 589–598.
  * [25] S. Mihara, S. Tsugawa, and H. Ohsaki, “Influence maximization problem for unknown social networks,” in _Proc. ASONAM 2015_ , pp. 1539–1546.
  * [26] V. Batagelj and M. Zaversnik, “An o(m) algorithm for cores decomposition of networks,” _CoRR_ , vol. cs.DS/0310049, 2003.
  * [27] L. Dhulipala, Q. C. Liu, S. Raskhodnikova, J. Shi, J. Shun, and S. Yu, “Differential privacy from locally adjustable graph algorithms: k-core decomposition, low out-degree ordering, and densest subgraphs,” in _IEEE FOCS 2022_ , pp. 754–765.
  * [28] J. Cohen, “Trusses: Cohesive subgraphs for social network analysis,” _National security agency technical report_ , vol. 16, no. 3.1, 2008.
  * [29] K. Saito, T. Yamada, and K. Kazama, “Extracting communities from complex networks by the _k_ -dense method,” _IEICE Trans. Fundam. Electron. Commun. Comput. Sci._ , vol. 91-A, no. 11, pp. 3304–3311, 2008.
  * [30] G. K. Manacher, “Algorithmic graph theory (alan gibbons),” _SIAM Rev._ , vol. 31, no. 1, pp. 145–147, 1989.
  * [31] J. Hu, X. Wu, R. Cheng, S. Luo, and Y. Fang, “On minimal steiner maximum-connected subgraph queries,” _IEEE Trans. Knowl. Data Eng._ , vol. 29, no. 11, pp. 2455–2469, 2017.
  * [32] J. Chen, S. Cai, S. Pan, Y. Wang, Q. Lin, M. Zhao, and M. Yin, “Nuqclq: An effective local search algorithm for maximum quasi-clique problem,” in _Proc. AAAI 2021_ , pp. 12 258–12 266.
  * [33] K. Wang, W. Zhang, X. Lin, Y. Zhang, and S. Li, “Discovering hierarchy of bipartite graphs with cohesive subgraphs,” in _ICDE 2022_ , pp. 2291–2305.
  * [34] K. Wang, G. Zhao, W. Zhang, X. Lin, Y. Zhang, Y. He, and C. Li, “Cohesive subgraph discovery over uncertain bipartite graphs,” _IEEE Trans. Knowl. Data Eng._ , 2023.
  * [35] L. Fan, L. Xiong, and V. Sunderam, “Differentially private multi-dimensional time series release for traffic monitoring,” in _Data and Applications Security and Privacy XXVII: 27th Annual IFIP WG 11.3 Conference, DBSec 2013. Proceedings 27_ , pp. 33–48.
  * [36] L. Fan and L. Xiong, “An adaptive approach to real-time aggregate monitoring with differential privacy,” _IEEE Trans. Knowl. Data Eng._ , vol. 26, no. 9, pp. 2094–2106, 2014.
  * [37] G. Cormode, S. Jha, T. Kulkarni, N. Li, D. Srivastava, and T. Wang, “Privacy at scale: Local differential privacy in practice,” in _SIGMOD 2018_ , pp. 1655–1658.
  * [38] Z. Qin, T. Yu, Y. Yang, I. Khalil, X. Xiao, and K. Ren, “Generating synthetic decentralized social graphs with local differential privacy,” in _CCS 2017_ , pp. 425–438.
  * [39] J. Imola, T. Murakami, and K. Chaudhuri, “Communication-efficient triangle counting under local differential privacy,” in _USENIX Security 2022_ , pp. 537–554.
  * [40] Y. Liu, S. Zhao, Y. Liu, D. Zhao, H. Chen, and C. Li, “Collecting triangle counts with edge relationship local differential privacy,” in _ICDE 2022_ , pp. 2008–2020.
  * [41] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. D. Smith, “What can we learn privately?” _SIAM J. Comput._ , vol. 40, no. 3, pp. 793–826, 2011.

|  Conggai Li is a CERC Fellow at Data61, Commonwealth Scientific and
Industrial Research Organisation (CSIRO). She received her Doctoral degree
from the Australian Artificial Intelligence Institute within the Faculty of
Engineering and Information Technology, the University of Technology Sydney,
Australia. She received her M.S. degree and B.S. degree both from Taiyuan
University of Technology, China. Her research interests include graph database
analytics, efficient query algorithms, and differential privacy.
---|---
|  Wei Ni [Fellow, IEEE] received the B.E. and Ph.D. degrees from Fudan
University, Shanghai, China, in 2000 and 2005, respectively. He is a Principal
Research Scientist at CSIRO, Sydney, Australia, and a Conjoint Professor at
the University of New South Wales. He is also an Adjunct Professor at the
University of Technology Sydney and an Honorary Professor at Macquarie
University. His research interests include machine learning, cybersecurity,
network security, and privacy, as well as their applications to 6G/B6G system
efficiency and integrity. Dr. Ni has served as an Editor for IEEE Transactions
on Wireless Communications since 2018, IEEE Transactions on Vehicular
Technology since 2022, and IEEE Transactions on Information Forensics and
Security and IEEE Communications Surveys and Tutorials since 2024. He served
first as the Secretary, then the Vice-Chair and Chair of the IEEE VTS NSW
Chapter from 2015 to 2022, Track Chair for VTC-Spring 2017, Track Co-chair for
IEEE VTC-Spring 2016, Publication Chair for BodyNet 2015, and Student Travel
Grant Chair for WPMC 2014.
---|---
|  Ming Ding [SM’17] received B.S., M.S., the Doctor of Philosophy (Ph.D.)
degrees from Shanghai Jiao Tong University, China, in 2004, 2007, and 2011,
respectively. Currently, he is a Principal Research Scientist at Data61,
CSIRO, in Sydney, NSW, Australia. His research interests include information
technology, data privacy and security, and machine learning and AI. He has
authored more than 200 papers in IEEE journals and conferences, all in
recognized venues, around 20 3GPP standardization contributions, as well as
two books, 21 US patents, and has co-invented another 100+ patents on 4G/5G
technologies. He is an editor of IEEE Transactions on Wireless Communications
and IEEE Communications Surveys and Tutorials. He has served as a guest
editor/co-chair/co-tutor/TPC member for multiple IEEE top-tier
journals/conferences and received several awards for his research work and
professional services, including the prestigious IEEE Signal Processing
Society Best Paper Award in 2022.
---|---
|  Youyang Qu [M’19] is currently a research scientist at CSIRO, Australia. He
received his B.S. degree in 2012 and M.S. degree in 2015 from the Beijing
Institute of Technology, respectively. He received his Ph.D. degree from
Deakin University in 2019. His research interests focus on Machine Learning,
Big Data, IoT, blockchain, and corresponding security and customizable privacy
issues. He has over 70 publications, including high-quality journal and
conference papers such as _IEEE TII_ , _IEEE TSC_ , _ACM Computing Surveys_ ,
_IEEE IOTJ_ , etc. He is active in the research society and has served as an
organizing committee member in SPDE 2020, BigSecuirty 2021, and Tridentcom
2021/2022.
---|---
|  Jianjun Chen is working toward the Ph.D. degree in the Australian
Artificial Intelligence Institute within the Faculty of Engineering and
Information Technology, University of Technology Sydney, Australia. He
received the B.S. degree in software engineering and M.S. degree in computer
science from the Taiyuan University of Technology, China. His research
interests include Federated Learning, Cooperative Perception, and 3D Object
Detection.
---|---
|  David Smith [Member, IEEE] received the B.E. degree from the University of
New South Wales, Sydney, Australia, in 1997, and the M.E. (research) and Ph.D.
degrees from the University of Technology, Sydney, Australia, in 2001 and
2004, respectively. He is currently a Principal Research Scientist with CSIRO.
He has a variety of industry experience in electrical and telecommunications
engineering. He has published over 150 technical refereed papers. His research
interests are data privacy, distributed systems privacy and edge computing
data privacy, distributed machine learning, data privacy for supply chains,
wireless body area networks, game theory for distributed networks, 5G/6G
networks, disaster tolerant networks, and distributed optimization for smart
grid. He has made various contributions to IEEE standardization activity in
personal area networks. He is an Area Editor for IET Smart Grid and has served
on the technical program committees of several leading international
conferences in the fields of communications and networks. He was a recipient
of four conferences of best paper awards.
---|---
|  Wenjie Zhang received the PhD degree in computer science and engineering
from the University of New South Wales, in 2010. She is currently a professor
and ARC Future fellow in the School of Computer Science and Engineering, the
University of New South Wales, Australia. Since 2008, she has published more
than 100 papers in SIGMOD, VLDB, ICDE, TODS, the IEEE Transactions on
Knowledge and Data Engineering, and the VLDB Journal.
---|---
|  Thierry Rakotoarivelo is the group leader of the Information Security and
Privacy group at CSIRO. His research focuses on the design and use of
frameworks for privacy risk assessment, the development of privacy-enhancing
technologies, and the study of trade-offs in responsible use of data in
specific application domains. He led several projects on data privacy in the
Government, EdTech, and Energy sectors, where he designed and delivered novel
technologies in areas such as confidentiality risk quantification or provably
private synthetic data generation. He received his PhD degree from the
University of New South Wales, Australia. His thesis received the Prix Léopold
Escande award from INPT in 2007.
---|---


G. Ganesan 11institutetext: Institute of Mathematical Sciences, HBNI, Chennai
11email<EMAIL_ADDRESS>
# Size of local finite field Kakeya sets

Ghurumuruhan Ganesan 11

###### Abstract

Let $\mathbb{F}$ be a finite field consisting of $q$ elements and let $n\geq
1$ be an integer. In this paper, we study the size of local Kakeya sets with
respect to subsets of $\mathbb{F}^{n}$ and obtain upper and lower bounds for
the minimum size of a (local) Kakeya set with respect to an arbitrary set
${\mathcal{T}}\subseteq\mathbb{F}^{n}.$

###### keywords:

Local Kakeya Sets, Minimum Size, Probabilistic Method

##  1 Introduction

The study of finite field Kakeya sets is of interest from both theoretical and
application perspectives. Letting $\mathbb{F}$ be a finite field containing
$q$ elements and $n\geq 1$ be an integer, Wolff [1] used counting arguments
and planes to estimate that the minimum size of a global Kakeya set covering
all vectors in $\mathbb{F}^{n}$ grows at least as $q^{n/2}.$ Later Dvir [2]
used polynomial methods to obtain sharper bounds (of the form $C\cdot q^{n}$)
on the minimum size of global Kakeya sets and for further improvements in the
multiplicative constant $C,$ we refer to Saraf and Sudan [3].

In this paper, we are interested in studying local Kakeya sets with respect to
_subsets_ of $\mathbb{F}^{n}.$ Specifically, in Theorem 2.1, we obtain upper
and lower bounds for the minimum size of a Kakeya set with respect to a subset
${\mathcal{T}}\subseteq\mathbb{F}^{n}.$

The paper is organized as follows. In Section 2, we describe local Kakeya sets
and state and prove our main result (Theorem 2.1) regarding the minimum size
of a local Kakeya set.

##  2 Local Kakeya sets

Let $\mathbb{F}$ be a finite field containing $q$ elements and for $n\geq 1$
let $\mathbb{F}^{n}$ be the set of all $n-$tuple vectors with entries
belonging to $\mathbb{F}.$

We say that a set ${\mathcal{K}}\subseteq\mathbb{F}^{n}$ is a Kakeya set _with
respect to_ the vector
$\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathbb{F}^{n}$ if there exists
$\mathbf{y}=\mathbf{y}(\mathbf{x})\in\mathbb{F}^{n}$ such that the line

$L(\mathbf{x},\mathbf{y}):=\bigcup_{a\in\mathbb{F}}\\{\mathbf{y}+a\cdot\mathbf{x}\\}\subseteq{\mathcal{K}},$
(2.1)

where $a\cdot\mathbf{x}:=(ax_{1},\ldots,ax_{n}).$ For a set
${\mathcal{T}}\subseteq\mathbb{F}^{n},$ we say that
${\mathcal{K}}\subseteq\mathbb{F}^{n}$ is a Kakeya set with respect to
${\mathcal{T}}$ if ${\mathcal{K}}$ is a Kakeya set with respect to every
vector $\mathbf{x}\in{\mathcal{T}}.$

The following result describes the minimum size of local Kakeya sets.

######  Theorem 2.1.

Let ${\mathcal{T}}\subseteq\mathbb{F}^{n}$ be any set with cardinality
$\\#{\mathcal{T}}$ an integer multiple of $q-1$ and let
$\theta\left({\mathcal{T}}\right)$ be the minimum size of a Kakeya set with
respect to ${\mathcal{T}}.$ We then have that

$q\sqrt{M}+\min\left(0,q-\sqrt{M}\right)\leq\theta\left({\mathcal{T}}\right)\leq
q+q^{n}\left(1-\left(1-\frac{1}{q^{n-1}}\right)^{M-1}\right)$ (2.2)

where $M:=\frac{\\#{\mathcal{T}}}{q-1}.$

For example suppose $M=\epsilon\cdot\left(\frac{q^{n}-1}{q-1}\right)$ for some
$0<\epsilon\leq 1.$ From the lower bound in (2.2), we then get that
$\theta\left({\mathcal{T}}\right)$ grows at least of the order of $q^{n/2}.$
Similarly, using the fact that $1-x\geq e^{-x-x^{2}}$ for
$0<x\leq\frac{1}{2},$ we get that

$\left(1-\frac{1}{q^{n-1}}\right)^{M-1}\geq\exp\left(-\frac{M-1}{q^{n-1}}\left(1+\frac{1}{q^{n-1}}\right)\right)\geq
e^{-\Delta},$

where $\Delta:=\frac{q\epsilon}{q-1}\left(1+\frac{1}{q^{n-1}}\right).$ From
(2.2) we then get that

$\theta\left({\mathcal{T}}\right)\leq q+q^{n}(1-e^{-\Delta}).$

In what follows we prove the lower bound and the upper bound in Theorem 2.1 in
that order.

### Proof of Lower Bound in Theorem 2.1

The proof of the lower bound consists of two steps. In the first step, we
extract a subset ${\mathcal{N}}$ of ${\mathcal{T}}$ containing vectors that
are non-equivalent. In the next step, we then use a high incidence counting
argument similar to Wolff (1999) and estimate the number of vectors in a
Kakeya set ${\mathcal{K}}$ with respect to ${\mathcal{N}}.$

_Step 1_ : Say that vectors $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathbb{F}^{n}$
are _equivalent_ if $\mathbf{x}_{1}=a\cdot\mathbf{x}_{2}$ for some
$a\in\mathbb{F}\setminus\\{0\\}.$ We first extract a subset of vectors in
${\mathcal{T}}$ that are pairwise non-equivalent. Pick a vector
$\mathbf{x}_{1}\in{\mathcal{N}}$ and throw away all the vectors in
${\mathcal{T}},$ that are equivalent to $\mathbf{x}_{1}.$ Next, pick a vector
$\mathbf{x}_{2}$ in the remaining set and again throw away the vectors that
are equivalent to $\mathbf{x}_{2}.$ Since we throw away at most $q-1$ vectors
in each step, after $r$ steps, we are left with a set of size at least
$\\#{\mathcal{T}}-r(q-1).$ Thus the procedure continues for

$M=\frac{\\#{\mathcal{T}}}{q-1}$ (2.3)

steps, assuming henceforth that $M$ is an integer.

Let
${\mathcal{N}}=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{M}\\}\subseteq{\mathcal{T}}$
be a set of size $M$ and let ${\mathcal{K}}$ be a Kakeya set with respect to
${\mathcal{N}},$ of minimum size. By definition (see (2.1)), there are vectors
$\mathbf{y}_{1},\ldots,\mathbf{y}_{M}$ in $\mathbb{F}^{n}$ such that the line
$L(\mathbf{x}_{i},\mathbf{y}_{i})\subseteq{\mathcal{K}}$ for each $1\leq i\leq
M.$ Moreover, since ${\mathcal{K}}$ is of minimum size, we must have that

${\mathcal{K}}=\bigcup_{j=1}^{M}\\{L(\mathbf{x}_{i},\mathbf{y}_{i})\\}.$ (2.4)

_Step 2_ : To estimate the number of distinct vectors in ${\mathcal{K}},$
suppose first that each vector in ${\mathcal{K}}$ belongs to at most $t$ of
the lines in $\\{L(\mathbf{x}_{i},\mathbf{y}_{i})\\}_{1\leq i\leq M}.$ Since
each line $L(\mathbf{x}_{i},\mathbf{y}_{i})$ contains $q$ vectors, we get that
the total number of vectors in ${\mathcal{K}}$ is bounded below by

$\\#{\mathcal{K}}\geq\frac{Mq}{t}.$ (2.5)

Suppose now that there exists a vector $\mathbf{v}$ in ${\mathcal{K}}$ that
belongs to at least $t+1$ lines $L_{1},\ldots,L_{t+1}\subseteq\bigcup_{1\leq
i\leq M}\\{L(\mathbf{x}_{i},\mathbf{y}_{i})\\}.$ Because the vectors
$\\{\mathbf{x}_{i}\\}_{1\leq i\leq M}$ are not equivalent, any two lines
$L(\mathbf{x}_{i},\mathbf{y}_{i})$ and $L(\mathbf{x}_{j},\mathbf{y}_{j})$ must
have at most one point of intersection. To see this is true suppose there were
scalars $a_{1}\neq a_{2}$ and $b_{1}\neq b_{2}$ in $\mathbb{F}$ such that

$\mathbf{y}_{1}+a_{i}\cdot\mathbf{x}_{1}=\mathbf{y}_{2}+b_{i}\cdot\mathbf{x}_{2}\text{
for }i=1,2.$

Subtracting the equations we would then get
$(a_{1}-a_{2})\cdot\mathbf{x}_{1}=(b_{1}-b_{2})\cdot\mathbf{x}_{2},$
contradicting the fact that $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are not
equivalent.

From the above paragraph, we get that any two lines in $\\{L_{i}\\}_{1\leq
i\leq t+1}$ have exactly one point of intersection, the vector $\mathbf{v}.$
Since each line $L_{i}$ contains $q$ vectors, the total number of vectors in
$\\{L_{i}\\}_{1\leq i\leq t+1}$ equals $(q-1)(t+1)+1,$ all of which must be in
${\mathcal{K}}.$ From (2.5) we therefore get that

$\\#{\mathcal{K}}\geq\min\left(\frac{Mq}{t},(q-1)(t+1)+1\right)$

and setting $t=\sqrt{M},$ we get

$\\#{\mathcal{K}}\geq q\sqrt{M}+\min\left(0,q-\sqrt{M}\right).$

From the expression for $M$ in (2.3), we then get (2.2). ∎

### Proof of Upper Bound in Theorem 2.1

We use the probabilistic method. Let
$\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{M}\\}$ be the set of non-equivalent
vectors obtained in Step $1$ in the proof of the lower bound with
$M=\frac{\\#{\mathcal{T}}}{q-1}$ (see (2.3)). Let
$\mathbf{Y}_{1},\ldots,\mathbf{Y}_{M}$ be independently and uniformly randomly
chosen from $\mathbb{F}^{n}$ and for $1\leq i\leq M,$ set

${\mathcal{S}}_{i}:=\bigcup_{j=1}^{i}\\{L\left(\mathbf{x}_{j},\mathbf{Y}_{j}\right)\\},$

where $L(\mathbf{x},\mathbf{y})$ is the line containing the vectors
$\mathbf{x}$ and $\mathbf{y}$ as defined in (2.1).

By construction, the set ${\mathcal{S}}_{M}$ forms a Kakeya set with respect
to ${\mathcal{T}}.$ To estimate the expected size of ${\mathcal{S}}_{M},$ we
use recursion. For $1\leq i\leq M,$ let
$\theta_{i}:=\mathbb{E}\\#{\mathcal{S}}_{i}$ be the expected size of
${\mathcal{S}}_{i}.$ Given ${\mathcal{S}}_{i-1},$ the probability that a
vector chosen from $\mathbb{F}^{n},$ uniformly randomly and independent of
${\mathcal{S}}_{i-1},$ belongs to the set ${\mathcal{S}}_{i-1}$ is given by
$p_{i}:=\frac{{\mathcal{S}}_{i-1}}{q^{n}}.$ Therefore

$\mathbb{E}\\#\left(L\left(\mathbf{x}_{i},\mathbf{Y}_{i}\right)\bigcap{\mathcal{S}}_{i-1}\right)=q\cdot\mathbb{E}\left(\frac{\\#{\mathcal{S}}_{i-1}}{q^{n}}\right)$

and so

$\theta_{i}=\theta_{i-1}+q\left(1-\frac{\theta_{i-1}}{q^{n}}\right)=\theta_{i-1}\left(1-\frac{1}{q^{n-1}}\right)+q.$
(2.6)

Letting $a=1-\frac{1}{q^{n-1}}$ and using (2.6) recursively, we get

$\theta_{i}=a^{i-1}\cdot\theta_{1}+q\cdot(1+a+\ldots+a^{i-2})=a^{i-1}\cdot\theta_{1}+\frac{q(1-a^{i-1})}{1-a}.$

Using $\theta_{1}=q,$ we then get that

$\displaystyle\theta_{M}$ $\displaystyle=$ $\displaystyle a^{M-1}\cdot
q+q^{n}\left(1-\left(1-\frac{1}{q^{n-1}}\right)^{M-1}\right)$
$\displaystyle\leq$ $\displaystyle
q+q^{n}\left(1-\left(1-\frac{1}{q^{n-1}}\right)^{M-1}\right).$

This implies that there exists a Kakeya set with respect to ${\mathcal{T}}$ of
size at most $\theta_{M}.$∎

### Acknowledgement

I thank Professors V. Guruswami, V. Arvind, C. R. Subramanian and the referees
for crucial comments that led to an improvement of the paper. I also thank
IMSc for my fellowships.

## References

  * [1] Wolff, T. : Recent work connected with the Kakeya problem. Prospects in Mathematics (Princeton, NJ), pp. 129–162 (1999).
  * [2] Dvir, Z. : On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society, 22, pp. 1093–1097 (2009).
  * [3] Saraf, S., Sudan, M. : Improved lower bound on the size of Kakeya sets over finite fields. Analysis and PDE, 1, pp. 375–379 (2008).