#  On Privacy and Confidentiality of Communications in Organizational Graphs

Masoumeh Shafieinejad  University of WaterlooWaterlooCanada
<EMAIL_ADDRESS>,  Huseyin Inan  Microsoft ResearchRedmondUnited States
<EMAIL_ADDRESS>p ,  Marcello Hasegawa  Microsoft
CorporationRedmondUnited States<EMAIL_ADDRESS>and  Robert Sim
Microsoft ResearchRedmondUnited States<EMAIL_ADDRESS>
###### Abstract.

Machine learned models trained on organizational communication data, such as
emails in an enterprise, carry unique risks of breaching confidentiality, even
if the model is intended only for internal use. This work shows how
confidentiality is distinct from privacy in an enterprise context, and aims to
formulate an approach to preserving confidentiality while leveraging
principles from differential privacy. The goal is to perform machine learning
tasks, such as learning a language model or performing topic analysis, using
interpersonal communications in the organization, while not learning about
confidential information shared in the organization. Works that apply
differential privacy techniques to natural language processing tasks usually
assume independently distributed data, and overlook potential correlation
among the records. Ignoring this correlation results in a fictional promise of
privacy. Naively extending differential privacy techniques to focus on group
privacy instead of record-level privacy is a straightforward approach to
mitigate this issue. This approach, although providing a more realistic
privacy-guarantee, is over-cautious and severely impacts model utility. We
show this gap between these two extreme measures of privacy over two language
tasks, and introduce a middle-ground solution. We propose a model that
captures the correlation in the social network graph, and incorporates this
correlation in the privacy calculations through Pufferfish privacy principles.

##  1\. Introduction

A number of applications in natural language understanding rely on language
models (chen2019gmail, ; adam2020ai, ). To enable such models it is necessary
to process training data that best represents the target application. Such
tasks become especially sensitive in the setting of organizational
communication, where organizations, individuals, or communities may share
secret data, and preserving confidentiality is of utmost importance.
Organizational communication often presents a complex underlying structure of
interactions which is well modeled by a social graph. Data privacy in graphs
and social graphs have been addressed by a number of previous works, for
example (189, ; 134, ; 43, ; kearns2016private, ; gao2017preserving, ;
zhu2017differentially, ; Karwa2014, ), where most of the works based on
differentially private approaches model individuals as nodes and exchanged
messages as edges. These proposed methods provide either node level privacy
guarantees or edge level privacy guarantees. In the context of organizational
communication we define node level guarantees as individual privacy and edge
level guarantees as confidentiality. That is, confidentiality involves
protecting information that is shared between two or more individuals in the
organization. In this work we set aside questions of individual privacy and
examine problems in ensuring confidentiality in organizational communication.
The goal is to enable the production of ML models for an enterprise, without
compromising potentially sensitive business secrets.

A limitation of individual privacy is that in an organizational context, this
approach can produce models with lower than optimal utility. To understand
this, suppose the CEO of a company communicates regularly with messages
addressed to all employees. From the organization’s perspective this
information is public to everyone, and yet a differentially private mechanism
acting at a node level will be forced to mask out the presence of these
messages as they originate from a single node. This would be necessary to
satisfy the requirement that a differentially private model should be
invariant to the presence or absence of any single node.

Instead we consider a model that affords edge-level privacy. In this case the
CEO can broadcast to all employees, and enable this correspondence to be
included in training of the model, since the information is replicated across
many edges, but she can still protect private 1:1 correspondence with her CFO,
for example, thus preserving confidentiality.

However, the situation is not so straightforward. In the case of social
graphs, often the properties of an edge can be inferred by the properties of
other nearby edges. Such a case does not fall under the framework of
differential privacy, where the theoretical guarantees are based on
presence/absence of individual elements, without taking into account any
effect on other elements. One approach to address this problem is via group
differential privacy. Group privacy assumes that all edges in a group of
participants are fully correlated, and queries against the graph must be
invariant to the presence or absence of the entire group. This framing can
significantly impact the accuracy of the model or query by being over-
protective of edge-edge relationships. Furthermore, it requires an explicit
description of what constitutes a group in the organization.

We address the issues presented by edge correlation by employing a generalized
version of differential privacy called Pufferfish (song2017, ). In Pufferfish
a set $\mathcal{S}_{\textnormal{pairs}}\subseteq\mathcal{S}\times\mathcal{S}$
of complementary secret pairs is defined, and privacy is provided by ensuring
the secret pairs are indistinguishable, for any data distribution (capturing
the correlation among the records) known to the adversary. Through this
requirement the correlation problem can be addressed while allowing utility to
be preserved. In addition, the non-independence between edges also affords us
a simple model for confidentiality, namely that information passing between
neighboring edges is more likely to be confidential than information that is
randomly distributed in the social graph. From this perspective, we propose a
privacy model that accounts for information dependence between edges in the
graph and define a notion of what constitutes an edge’s neighborhood. In this
work we are limited to L-Lipschitz queries which are sufficiently broad to
cover for counting and frequency queries.

For the purposes of this work we adapt the _Attribute Disclosure Attack_
defined in (Beigi2020, ):

###### Definition 1.0 (Attribute Disclosure Attack).

Given T=(G,A,B), which is a snapshot of an organization with a social graph
$G=(V,E)$, where $V$ is the set of individuals and $E$ demonstrates the
correspondence between them, correspondent behavior $A$ and attribute
information $B$, the attribute disclosure attack is used to infer the
attributes $a_{e}$ for all $e\in E_{t}$ where $E_{t}$ is a list of targeted
edges. For each $e\in E_{t}$, we have information about the correspondence
between the individuals linked by $e$.

This definition deviates from that proposed in (Beigi2020, ) in that it
focuses on disclosing information about correspondence between users. That is,
the goal of the attack is to leak information about what is communicated along
the edges of the graph.

###  1.1. Contributions

The contributions of this work are as follows, it:

  * •

Presents a complete formulation of _confidentiality_ protection in closed
social networks such as an enterprise or organization, including accounting
for neighborhood correlation,

  * •

Models predicting neighborhood correlations assuming varying degrees of
attacker knowledge,

  * •

Shows the gap between two extreme measures of privacy, record-level privacy
and group privacy, over two language tasks, and

  * •

Provides empirical results of applying our work to statistical query tasks
(Gopi2020, ; xu2013differentially, ) in a real enterprise graph, leaving
extensions to other language modeling tasks for future work.

###  1.2. Related Work

Existing privacy approaches for social graphs use different techniques and
mechanisms (Beigi2020, ). These techniques are categorized into three main
categories: i) grouping-based approaches, ii) edge manipulation algorithms,
and iii) differential-privacy-based techniques. Grouping-based approaches
include $k$-anonymity-based approaches (43, ; 115, ; 189, ; 196, ; 199, ) and
cluster-based techniques (31, ; 70, ; 114, ; 134, ; 174, ). $K$-anonymity is
among the first techniques proposed for protecting the privacy of datasets and
aims to anonymize each user/node in the graph so that it is indistinguishable
from at least $k-1$ other users. Machanacajjhala et al. (Machanavajjhala2007,
) showed that a $k$-anonymous solutions still have severe privacy problems
when the sensitive attributes lack diversity, or when the adversary has access
to background knowledge. Clustering-based approaches group users and edges and
are limited to the applications where only the density and size of the cluster
is revealed, so that individual attributes are protected. Edge manipulation
algorithms utilize edge-based strategies such as random edge adding/deleting
and random edge switching (188, ; 18, ). The edge perturbation algorithm can
use random-walk-based techniques (116, ; 134, ) as well. As the most recent
category, differential privacy provides a strong privacy guarantee that the
risk of user’s privacy leakage does not increase as a result of participating
in a database (52, ). A common way of achieving differential privacy is by
introducing random noise through the Laplace mechanism (for numerical
attributes) or Exponential mechanism (for non-numerical attributes) to the
query answers (52, ).

The differentially private proposals for social graphs fall into two
categories: edge-level differential privacy, and node-level differential
privacy. In edge-level differential privacy (Nissim2007, ; Sala2017, ;
Karwa2014, ; Hay2009, ), the result of the analysis does not change by adding
or removing an edge. Node-level privacy however (Kasiviswanathan2013, ;
Blocki2013, ; Chen2013, ; Raskhodnikova2016, ; Chen2014, ; Ghosh2017, ), is
resilient against adding or removing a node, therefore it is more difficult to
achieve. Note that differential privacy assumes independence among instances
in the dataset. It has been shown that the dependency between instances
affects the robustness of differential privacy guarantees to de-anonymization
(liu2016dependence, ; 92, ). The naive approach to address this issue to use
group-level differential privacy, where the group of dependant records/nodes
are considered as one instance (Chen2014, ; Ghosh2017, ). The transition to
group privacy sacrifices utility even more, and motivates our work. We
investigate privacy for correlated data, as an alternative to group-privacy,
to prevent leakage when the records are not independent (journal-1, ;
song2017, ). To do so, we use Pufferfish privacy (journal-1, ), and propose a
mechanism to achieve this privacy inspired by Song et al.’s work (song2017, ).

##  2\. Preliminaries

In this section, we introduce the notations and provide the definitions for
the concepts used throughout the paper.

###  2.1. Differential Privacy

Differential privacy (DP) is a mathematical framework that offers strong and
robust guarantees at protecting user privacy under the release of a query
function calculated over a statistical database (proceedings-1, ). The main
idea to achieve DP is perturbing the query function by the introduction of
random noise generated according to a carefully chosen distribution. We
formally define the notion of $\epsilon$-differential privacy in the
following:

###### Definition 2.0 ($\epsilon$-Differential Privacy (proceedings-1, )).

A randomized algorithm $\mathcal{M}$ is said to provide
$\epsilon$-differential privacy if for any two databases $D,D^{\prime}$
differing in only a single entry, and for any set
$S\subseteq\textnormal{Range}(M)$,

$\displaystyle\dfrac{\Pr(\mathcal{M}(D)\in S)}{\Pr(\mathcal{M}(D^{\prime})\in
S)}\leq\exp(\epsilon)$

the probability taken over the randomness of the algorithm $\mathcal{M}$.

A typical way to achieve $\epsilon$-differential privacy is to apply the
Laplace mechanism as shown in (proceedings-2, ). The main idea is to apply
noise to the output of a query for the sake of perturbation and the amount of
noise depends on the global sensitivity of the query and the privacy budget
$\epsilon$. Let us first define the global sensitivity.

###### Definition 2.0 (Global sensitivity).

Let $d$ be a positive integer and $\mathcal{D}$ be a collection of datasets.
For any function $f:\mathcal{D}\rightarrow\mathbb{R}^{d}$, the global
sensitivity of f, denoted by $\Delta f$, is defined by

$\displaystyle\Delta f=\max\limits_{D_{1},D_{2}}||f(D_{1})-f(D_{2})||_{1}$

where $D_{1}$ and $D_{2}$ are datasets in $\mathcal{D}$ differing in at most
one element and $||\cdot||_{1}$ denotes the $\ell_{1}$ norm.

###### Theorem 2.3.

Let $d$ be a positive integer and $\mathcal{D}$ be a collection of datasets.
For any $f:\mathcal{D}\rightarrow\mathbb{R}^{d}$, the randomized mechanism
$\mathcal{M}$

$\displaystyle\mathcal{M}(\mathcal{D})=f(\mathcal{D})+\textnormal{Laplace}(0,\Delta
f/\epsilon)$

satisfies $\epsilon$-differential privacy.

Global sensitivity is a bound on the maximum effect of any element in the
dataset, which will be helpful to provide privacy to all elements in the
dataset. Based on this, for a given dataset $D$, a function $f$, and the
privacy parameter $\epsilon$, the Laplace mechanism adds
$\textnormal{Laplace}(0,\lambda)$ noise to the output of $f$ where the
parameter $\lambda$ is determined by both $\Delta f$ and $\epsilon$.

Note that in the definition of $\epsilon$-differential privacy, the guarantee
holds for a single data entry. However, by applying the composability property
of differential privacy (mcsherry09, ), the setting can be extended to
multiple data entries. If the goal is to protect a group, this can be achieved
by setting $\epsilon$ to $\epsilon/k$ for any $k\in\mathbb{N}$ where $k$
represents the size of the group. In this case, all groups of size $k$ are
$\epsilon$-differentially private protected. We summarize this by formally
defining group differential privacy in the following corollary:

###### Corollary 2.4.0 (Group Differential Privacy).

A randomized algorithm $\mathcal{M}$ is said to provide
$\epsilon$-differential privacy for all groups of size $k$ if for any two
databases $D,D^{\prime}$ differing in at most $k$ entries, and for any set
$S\subseteq\textnormal{Range}(M)$,

$\displaystyle\dfrac{\Pr(\mathcal{M}(D)\in S)}{\Pr(\mathcal{M}(D^{\prime})\in
S)}\leq\exp(\epsilon)$

where the probability is taken over the randomness of the algorithm
$\mathcal{M}$. Any $\epsilon/k$-differentially private algorithm is
$\epsilon$-differentially private for all groups of size $k$.

We point out that the scaling of the noise is inversely proportional to the
privacy budget $\epsilon$. Therefore, setting $\epsilon$ to $\epsilon/k$ will
in turn change the noise level from $\Delta f/\epsilon$ to $k\cdot\Delta
f/\epsilon$, which may significantly decrease the utility of the query.
However, this is the price to pay to obtain stronger privacy guarantees with
group differential privacy.

###  2.2. Pufferfish Privacy

Differential privacy provides robust guarantees for a wide range of database
queries. For our scenario, it is useful to consider Pufferfish privacy
(journal-1, ), which is a Bayesian privacy framework providing rigorous
privacy guarantees against many types of attackers. An advantage of the
Pufferfish framework is that a domain expert can develop rigorous privacy
definitions for their data sharing needs without holding an expertise in
privacy. This is achieved by specifying three components in the Pufferfish
privacy framework: a set $\mathcal{S}$ of potential secrets, a set
$\mathcal{S}_{\textnormal{pairs}}\subseteq\mathcal{S}\times\mathcal{S}$ of
discriminative secret pairs, and a collection of data distributions $\Theta$.
The Pufferfish framework provides a rich class of privacy definitions based on
the components specified by a domain expert. We formally define the framework
in the following based on (journal-1, ).

###### Definition 2.0 (Pufferfish Privacy).

A randomized algorithm $\mathcal{M}$ is said to provide $\epsilon$-Pufferfish
privacy for a domain $(\mathcal{S},\mathcal{S}_{\textnormal{pairs}},\Theta)$
if for all distributions $\theta\in\Theta$, for all secret pairs
$(s_{i},s_{j})\in\mathcal{S}_{\textnormal{pairs}}$, and for all possible
outputs $w\in\textnormal{Range}(\mathcal{M})$ it satisfies

$\displaystyle\left\lvert\dfrac{\Pr_{\mathcal{M},\theta}(\mathcal{M}(\mathcal{D})=w|s_{i},\theta)}{\Pr_{\mathcal{M},\theta}(\mathcal{M}(\mathcal{D})=w|s_{j},\theta)}\right\rvert\leq\exp(\epsilon)$

where $\mathcal{D}$ is drawn from the distribution $\theta$ and $s_{i}$ and
$s_{j}$ are such that $\Pr(s_{i}|\theta)\neq 0$ and $\Pr(s_{j}|\theta)\neq 0$.

We note that there is an additional source of randomness in the definition of
Pufferfish privacy. The dataset $\mathcal{D}$ is itself a random variable that
is drawn from a distribution $\theta\in\Theta$.

In words, a domain expert constructs the set $S$ for the potential secrets
that are desired to be hidden (e.g. private data of an individual).
$\mathcal{S}_{\textnormal{pairs}}$ is simply the pair of such potential
secrets that we would like to guarantee are indistinguishable in evaluating
$\mathcal{M}$. Finally, $\Theta$ is a collection of distributions where each
probability distribution $\theta\in\Theta$ corresponds to an attacker to be
protected against. $\Theta$ can be selected based on the fine grain of how
data can be plausibly generated and it also reflects the attackers’ beliefs in
how the data were generated (incorporating any background knowledge and side
information). The whole process gives the domain expert flexibility to
customize privacy to the specific set of secrets and data generation scenarios
that are typical in their domain.

We further point out that Pufferfish privacy provides a general framework in
the sense that it covers $\epsilon$-differential privacy as an instantiation
for a particular choice of domain
$(\mathcal{S},\mathcal{S}_{\textnormal{pairs}},\Theta)$ (see Theorem 6.1 in
(journal-1, )).

###  2.3. Wasserstein Mechanism

While there is no efficient general mechanism that applies to any Pufferfish
instantiation, there are a number of mechanisms for specific Pufferfish
instantiations (journal-1, ; Blowfish, ). For general Pufferfish
instantiation, Song et al. (song2017, ) introduce a mechanism that achieves
Pufferfish privacy, but does not satisfy efficiency in its original form. We
introduce their base mechanism here. Later in Section 4, we present our
adjustments to their mechanism that makes it efficient to utilize for our use
case of enterprise communications.

The main idea of the mechanism in (song2017, ) is similar to the Laplace
mechanism in differential privacy. Instead of adding noise based on the global
sensitivity $\Delta f$ in differential privacy, Song et al. use the
distributions $\Pr(f(\mathcal{D})|s_{i},\theta)$ and
$\Pr(f(\mathcal{D})|s_{j},\theta)$ in the Pufferfish framework, propose a
metric quantifying the worst case distance between these two distributions,
and inject noise proportional to this distance. They find that the
$\infty$-Wasserstein distance is the right choice for this purpose.

###### Definition 2.0 ($\infty$-Wasserstein distance).

Let $\mu$, $\nu$ be two probability distributions on $\mathbb{R}$ and
$\tau(\mu,\nu)$ denote the set of all joint distributions with marginals $\mu$
and $\nu$. The $\infty$-Wasserstein distance between $\mu$ and $\nu$ is
defined as

$\displaystyle
W_{\infty}(\mu,\nu)=\inf\limits_{\gamma\in\tau(\mu,\nu)}\max\limits_{(x,y)\in\textnormal{support}(\gamma)}\mid
x-y\mid.$

Intuitively, $W_{\infty}$ measures the maximal distance that any probability
mass moves while transforming $\mu$ to $\nu$ in the most optimal way possible.
$W_{\infty}$ is related to the well-known Earth Mover’s Distance in that it
accounts for the maximal shift in probability over the domain of $\tau$ but
not the amount of mass in the shift (hitchcock41, ).

Based on the $\infty$-Wasserstein distance, the Wasserstein mechanism
calculates the maximum over $(s_{i},s_{j})\in\mathcal{S}_{\textnormal{pairs}}$
and $\theta\in\Theta$, analogous to $\Delta f$, and applies the Laplace noise
proportional to the maximum $\infty$-Wasserstein distance. It is proven in
(song2017, ) (see Theorem 3.2) that this mechanism yields
$\epsilon$-Pufferfish privacy.

###### Theorem 2.7 (Wasserstein mechanism).

Let $(\mathcal{S},\mathcal{S}_{\textnormal{pairs}},\Theta)$ be a domain. For
any function $f:\mathcal{D}\rightarrow\mathbb{R}$ the randomized mechanism
$\mathcal{M}$

$\displaystyle\mathcal{M}(\mathcal{D})=f(\mathcal{D})+\textnormal{Laplace}(0,W/\epsilon)$

where
$W=\sup_{(s_{i},s_{j})\in\mathcal{S}_{\textnormal{pairs}},\theta\in\Theta}W_{\infty}(\mu_{i\theta},\nu_{j\theta})$
for $\mu_{i,\theta}=\Pr(f(\mathcal{D})|s_{i},\theta)$ and
$\nu_{j,\theta}=\Pr(f(\mathcal{D})|s_{j},\theta)$ satisfies
$\epsilon$-Pufferfish privacy.

###  2.4. Markov Quilt Mechanism

The Wasserstein mechanism can be quite expensive in terms of computational
complexity, as it requires modeling the effects of varying all complementary
secret pairs on the function $f$. (song2017, ) introduces the Markov Quilt
mechanism for the special case where the dependence inside a dataset can be
described by a Bayesian network, which fits to our setting of interest. In the
case where the dependence is most effective in the “local” neighborhood, the
amount of noise can be calibrated with respect to the size of this
neighborhood. To this end, max-influence of a variable $\mathcal{D}_{i}$ on a
set of variables $\mathcal{D}_{A}$ under a distribution class $\Theta$ is
defined as

$e_{\Theta}(\mathcal{D}_{A}|\mathcal{D}_{i})=\sup\limits_{\theta\in\Theta}\max\limits_{a,b\in\mathcal{X}}\max\limits_{d_{A}\in\mathcal{X}^{|\mathcal{D}_{A}|}}\log\frac{\Pr(\mathcal{D}_{A}=d_{A}|\mathcal{D}_{i}=a,\theta)}{\Pr(\mathcal{D}_{A}=d_{A}|\mathcal{D}_{i}=b,\theta)}$

where $\mathcal{X}$ denotes the range of each $\mathcal{D}_{i}$.

In terms of privacy it is an advantage that the dependence stays as “local” as
possible if one can find a large set $\mathcal{D}_{A}$ such that
$\mathcal{D}_{i}$ has low max-influence on $\mathcal{D}_{A}$. Especially if
one can claim certain conditional independence from a variable towards some
part of the dataset it can also simplify the calibration of the noise. The
following notion is helpful to show what is described here.

###### Definition 2.0 (Markov Quilt).

A set of variables $\mathcal{D}_{Q}$ in a dataset is a Markov Quilt for a
variable $\mathcal{D}_{i}$ if there exists a set
$\mathcal{D}_{i}\in\mathcal{D}_{N}$ such that
$\mathcal{D}=\mathcal{D}_{N}\cup\mathcal{D}_{Q}\cup\mathcal{D}_{R}$ and
$\mathcal{D}_{i}$ is conditionally independent from $\mathcal{D}_{R}$ given
$\mathcal{D}_{Q}$, i.e.
$\Pr(\mathcal{D}_{R}|\mathcal{D}_{Q},\mathcal{D}_{i})=\Pr(\mathcal{D}_{R}|\mathcal{D}_{Q})$.

In this formulation (song2017, ) choose the subscripts $N$ and $R$ to
represent “nearby” and “remote” nodes in the Bayesian network, respectively,
with the $Q$ (quilt) nodes separating them and establishing conditional
independence.

Based on this notion (song2017, ) introduces the Markov Quilt mechanism that
protects a variable $\mathcal{D}_{i}$ by adding Laplace noise to a L-Lipschitz
query $f$ with scale parameter $L\times|\mathcal{D}_{N}|/(\epsilon-\delta)$
where $\delta$ is an upper bound on the max-influence of $\mathcal{D}_{i}$ on
$\mathcal{D}_{Q}$. We note that the effect of $\mathcal{D}_{i}$ is obscured
with noise whose amount is based on the cardinality of the local variables
($|\mathcal{D}_{N}|$) and a correction term to account for the effect of the
distant variables ($\delta$). Naturally, the privacy of all variables can be
protected by adding noise with the maximum scale parameter over all variables
$\mathcal{D}_{i}\in\mathcal{D}$. It is shown in (song2017, ) (see Theorem 4.3)
that this mechanism yields $\epsilon$-Pufferfish privacy. It is also proven
that Markov Quilt mechanism satisfies sequential composition (see Theorem 4.4
in (song2017, )).

###### Theorem 2.9 (Markov Quilt Mechanism).

Let $(\mathcal{S},\mathcal{S}_{\textnormal{pairs}},\Theta)$ be a domain. For
any L-Lipschitz function $f$ if each $\mathcal{D}_{i}\in\mathcal{D}$ has the
trivial quilt $\mathcal{D}_{Q}=\emptyset$ (with $\mathcal{D}_{N}=\mathcal{D}$,
$\mathcal{D}_{R}=\emptyset$), then the Markov Quilt Mechanism provides
$\epsilon$-Pufferfish privacy.

##  3\. Problem Definition

Figure 1. A sampled social graph from a real-world organization.

With preliminaries defined, we model the organizational communication through
a graph structure. Figure 1 shows a typical enterprise communication graph.
Having the communication modeled, we then describe the confidentiality
requirements for the model.

###  3.1. Organizational Model

We model the network of organizational communications by a graph with the
following properties:

  * •

The graph displays the communications in the organization.

  * •

Nodes are the individuals of the organization.

  * •

There is an edge between two nodes if one of the nodes communicated with (e.g.
sent an email to) the other one; the graph is not directed.

  * •

Edges may be labeled with a set of zero or more properties. For example, an
edge may be labeled with the token “acquisition” if the correspondents
discussed the topic “acquisition”.

  * •

The target application is to perform queries over the graph to measure
statistics of edge properties.

In principle, “queries over the graph to measure statistics of edge
properties” may imply training a language model or performing similar natural
language tasks over the graph. For the purposes of our work we focus on a
simpler task, which is to safely release a set of edge properties present in
the graph. For language tasks, this can be defined as extracting common
n-grams from correspondence. Other application scenarios have examined popular
item sampling. This problem has been explored in related work like
differentially private set union (DPSU) (Gopi2020, ), and top-$k$ item
selection (durfee-top-k, ).

###  3.2. Confidentiality Requirements

In order to achieve our goal of organizational confidentiality, we impose the
following additional requirements:

  * •

The privacy mechanism should protect edges (provide edge-level privacy),

  * •

the mechanism should account for correlation between neighboring edges,

  * •

the mechanism should protect against changes to edge properties, but not to
changes in graph structure (the graph edges are considered invariant and
public, whereas the properties of the edges are private111For example, an
organization’s leadership structure is usually public knowledge, and
individuals with internal access can usually determine who reports to who and
infer common lines of communication.),

  * •

the graph structure is known to attackers, and

  * •

attackers may have access to a data generation model $\theta$ that can predict
an edge’s properties, given its neighbors’.

Note that the data generation model $\theta$ assumes that neighboring edges
influence one-another but non-neighboring edges don’t. That is, an edge’s
properties are conditionally independent of the rest of the graph, given its
neighbors’ properties. This is equivalent to expressing the graph as a Markov
random field. In practical scenarios, edge correlation may be effective beyond
the neighborhood of an edge. However, we believe our conditional independence
assumption is a reasonable approximation.

The reader will note that this problem framing lends itself well to Pufferfish
privacy: the presence or absence of a property on an edge can be framed as a
pair of complementary secrets $s^{0}_{i}$ and $s^{1}_{i}$ respectively for all
edges $X_{i}$ in the graph. In the Pufferfish instantiation this leads to
having the set of secrets $\mathcal{S}=\\{s^{0}_{i},s^{1}_{i}:\textnormal{for
all edges $i$ in the graph}\\}$, so the status of the corresponding property
of each edge is a secret. The set of secret pairs becomes
$\mathcal{S}_{\textnormal{pairs}}=\\{(s^{0}_{i},s^{1}_{i}):\textnormal{for all
edges $i$ in the graph}\\}$ as we desire that the adversary cannot tell if
each edge has the property of interest or not. Finally, attackers have access
to generating distributions in $\Theta$ describing how properties may be
defined on the graph, and in particular how they may be correlated.

In the following section we describe how we can leverage Pufferfish privacy to
protect edge properties, while accounting for neighborhood correlation, and
subsequently we present empirical results on a language task applied to a
real-world organizational graph.

##  4\. Mechanism Design

We consider the graph representation of the organizational communications,
consisting of nodes for individuals and edges for the correspondences among
them.

###  4.1. Neighborhood model for correlation

In our neighborhood model, we capture the correlation among the _adjacent
edges_ as shown in Figure 2. This is one choice of modeling correlation for
the communication between nodes and one can think of other models such as the
clique model in the flu status over social network example of (song2017, )
where the network is a union of cliques and each clique has a dependency among
its nodes. This may be appealing for the organization communications
considering each group in the organization as a clique. However, in practice
it is seldom the case that every pair of individuals in a particular group has
a communication link between them, and therefore the actual cliques in the
communication graph correspond to only subsets of the groups in the
organization, not capturing the correlation effectively. Furthermore, the set
of maximal cliques in a large graph may be prohibitively expensive to
enumerate and estimate $W_{\infty}$ for each. In our model we instead define
the graph as a union of neighborhoods, where each neighborhood is defined as a
central edge and its adjacent neighbors. Note that the conditional
independence assumption implies that knowledge of the edge properties in the
neighborhood is sufficient to determine the properties of the central edge.

Figure 2. Neighborhood correlation, each edge is correlated with its adjacent
edges. The 23 edge is adjacent to edges 21, 24, 31 and 34. Similarly, edge 57
is adjacent to edges 51, 56, 58, 59, and 76.

A change in an edge’s properties will influence its neighbors. For example, an
edge labeled with the property “acquisition” may imply that neighbors are much
more likely to share this property. If we can model the effect of this change
probabilistically, we can compute the Wasserstein distance between query
distributions, providing a sensitivity measure that accounts for an edge’s
correlation with its neighbors. In the next section we outline our privacy
definition, followed by three proposed models for capturing neighborhood
correlation.

###  4.2. Privacy Definition

We use Pufferfish privacy to design a private mechanism that takes correlation
into account. We start with designing a private mechanism for counting one
property in the graph, and then extend it to all property counts:

  1. (1)

The database is a set of records: $X=\\{X_{1},\cdots,X_{N}\\}$; $X_{i}=0$ or
$X_{i}=1$ corresponding to the events the edge _i_ has the property or
not222Or: whether the property frequency is above a certain threshold or not.,
indicating complementary secrets $s_{i}^{0}$ or $s_{i}^{1}$.

  2. (2)

The Pufferfish parameters:
$(\mathcal{S},\mathcal{S}_{\textnormal{pairs}},\Theta)$: the set of secrets
$\mathcal{S}=\\{s_{i}^{0},s_{i}^{1};i=1,\ldots,n\\}$, the secret pairs to be
indistinguishable
$\mathcal{S}_{\textnormal{pairs}}=\\{(s_{i}^{0},s_{i}^{1}),i=1,\ldots,n\\}$,
and $\Theta$, the set of models describing the correlation. The Pufferfish
privacy guarantee is shown in Equation (1).

(1)
$e^{-\epsilon}\leq\frac{\Pr_{M,\theta}(M(X)=w|s_{i}^{0},\theta)}{\Pr_{M,\theta}(M(X)=w|s_{i}^{1},\theta)}\leq
e^{\epsilon}$

    1. (a)

In the organizational communication $\mathcal{S}$ consists of the binary
values of each $X_{i}$, $i=1,\ldots,n$.

    2. (b)

$\mathcal{S}_{\textnormal{pairs}}$ is what we want the property label to be
indistinguishable from. Since the label is binary,
$\mathcal{S}_{\textnormal{pairs}}$ is $(s_{i}^{0},s_{i}^{1})$, which indicate
the existence or non-existence of an property in an edge.

    3. (c)

$\Theta$: Instead of considering a set of correlations, we focus on the
neighborhood correlation for $\theta\in\Theta$. We use the Markov Quilt
mechanism from (song2017, ) for this model. However, unlike the Markov Quilt
mechanism, we rely on empirical data and measure the exact correlation inside
the quilt.

    4. (d)

Query $f$: Maps the dataset $X$ into a scalar
$f(X)=|i\in\\{1,\ldots,n\\}:X_{i}=1|$, counting the number of edges having the
property of interest.

  3. (3)

Markov Quilt. We adapt the Markov Quilt Mechanism to protect the edges in our
neighborhood model. We assume that each edge $X_{i}$ is correlated to its
adjacent edges $X_{N}$ and has no correlation with the rest of the graph
(neither to $X_{R}$, nor to $X_{Q}$), i.e. $\delta=0$. The
$\textnormal{card}(X_{N})$ translates to the maximum number of adjacent edges
to an edge, i.e. $2\times D_{max}-1$, where $D_{max}$ is the maximum degree of
a node in the graph, and we subtract 1 so as not to double-count the central
edge itself. We note that the application of $2\times D_{max}$ group
differential privacy (Corollary 2.4) would be a baseline for our case.

###  4.3. Correlation Models

In order to assess the Wasserstein distance between neighboring secret pairs
(changing a single property from true to false or vice-versa), we require a
model that can estimate by how much a neighborhood’s labels might change due
to a change in the central edge’s label.

Specifically, we seek to estimate $\Pr(f(X)=w|s_{i},\theta)$. The attacker’s
priors, encoded by $\theta$ indicate to what accuracy the attacker may be able
to estimate the change in $f(X)$ if edge $X_{i}$ changes its label, replacing
$s_{i}^{0}$ with $s_{i}^{1}$ or vice versa. By applying the Markov assumption,
we need only measure the impact of a label change on an edge’s immediate
neighborhood (i.e. its impact on the Markov quilt). Thus, for each of the
correlation models below, $w$ is measured for the local neighborhood and the
rest of the graph is assumed to be constant.

####  4.3.1. Conditional Model

Our first model, namely the Conditional model estimates the probability
$\Pr(f({X})=w|s_{i},\textnormal{deg}(X_{i}),\textnormal{freq}(a))$, where
$\textnormal{deg}(X_{i})$ is the number of edges adjacent to edge $X_{i}$,
$\textnormal{freq}(a)$ is the attacker’s prior on the frequency of property
$a$ (ie their prior estimate of how many edges are labeled with $a$, perhaps
sampled from a public corpus). We construct this model empirically by
bucketizing $\textnormal{deg}(X_{i})$ and $\textnormal{freq}(a)$ on a
logarithmic scale, sampling up to 100 edges per bucket, and building a
histogram describing $\Pr(f({X})=w)$, for discrete intervals of $w$. Note that
since the rest of the graph is invariant to changes in $s_{i}$, we need only
measure this distribution over values of $w$ specific to the edge’s local
neighborhood. This is our highest-fidelity model and represents the most
knowledge we assume an attacker may possess about the graph.

####  4.3.2. Global Model

Our second model, called the Global model ignores $\textnormal{deg}(X_{i})$
and $\textnormal{freq}(a)$ and empirically measures $\Pr(f({X})=w|s_{i}^{j})$
for secrets $s_{i}^{0}$ and $s_{i}^{1}$. The resulting model is a normalized
frequency histogram of how often $f({X})=w$ when the central edge’s property
is set, $s_{i}^{1}$ , and a separate histogram for when it is not set
$s_{i}^{0}$. As in the conditional model, we measure the distribution over the
range of values that $w$ may take over a local neighborhood, assuming the rest
of the graph to be constant.

####  4.3.3. Binomial Model

Finally our third model, which we call the Binomial model, representing the
least amount of attacker knowledge, empirically estimates
$p_{i}=\Pr(s_{j}|s_{i})$, the probability distribution over a randomly
selected adjacent edge’s secrets, given the label of the central edge, and
then estimates $\Pr(f({X})=w|s_{i})$ as a Binomial distribution parameterized
by $p_{i}$ and $\textnormal{deg}(X_{i})$:

$P(f({X})=w|s_{i})=\textnormal{Binomial}(\textnormal{deg}(X_{i}),p_{i})$

That is, for a given edge $X_{i}$ with $\textnormal{deg}(X_{i})$ neighboring
edges, if $X_{i}$’s label is $s_{i}$, then the probability that it has $w$
neighboring edges with a true label is represented by the distribution of
successes over $\textnormal{deg}(X_{i})$ Bernoulli trials with success
probability $p_{i}$. Note that $p_{i}$ is considered a constant over the whole
graph, independent of $\textnormal{deg}(X_{i})$, and is parameterized by the
central edge’s label $s_{i}$.

###  4.4. Measuring $W_{\infty}$

Our correlation models afford a straightforward estimation of the maximal
Wasserstein distance $W=max_{X_{i}\in X}W_{\infty}(X_{i})$. For each
neighborhood in the graph, instantiate distributions $\Pr(f({X})|s_{i}^{0})$
and $\Pr(f({X})|s_{i}^{1})$, and measure $W_{\infty}$. Computationally, this
is equivalent to determining the largest horizontal distance between the two
distributions when they are expressed as cumulative functions, as illustrated
in Figure 3. $W$ is then the maximal $W_{\infty}$ over all edges.

Note that $W$ is bounded above by the largest neighborhood size: flipping a
single edge property may trigger a flip in at most $\textnormal{deg}(X_{i})$
adjacent edges.

Figure 3. Example $W_{\infty}$ determined by differencing cumulative
distributions for the Conditional model.

##  5\. Experiments

We run our experiments on the Avocado corpus(avocado2015, ). In order to
accurately recognize messages sent to multiple recipients, we apply a simple
inference heuristic for identifying organizational mailing lists and their
memberships (enabling, for example, the expansion of “All Employees”,
instantiating an edge from sender to each member of this list. The complete
graph contains 393 nodes (individuals) and 21312 edges representing
correspondence between users. The largest neighborhood in the graph consists
of 1883 edges.

Edges are subsequently labeled with properties. We extract unigrams and bi-
grams from messages passed between edges and set the edge property $X^{a}_{i}$
to “true” for each ngram $a$. Thus an edge with the property “acquisition” set
to true indicates that at least one message passed between the connected nodes
containing the word “acquisition”. Edges with no such property are implicitly
“false” for that property.

$\log(\textit{freq})$ | $\log(\textit{deg})$ | $W_{\infty}$ | $W$
---|---|---|---
0 | 0 | 1.0 | 10.0
0 | 1 | 0.08 | 8.0
0 | 2 | 0.02 | 20.0
0 | 3 | 0.01 | 18.83
1 | 0 | 1.0 | 10.0
1 | 1 | 0.58 | 57.0
1 | 2 | 0.5 | 500.0
1 | 3 | 0.09 | 169.47
2 | 0 | 0.71 | 7.1
2 | 1 | 0.66 | 66.0
2 | 2 | 0.74 | 740.0
2 | 3 | 0.51 | 960.33
3 | 0 | 0.5 | 5.0
3 | 1 | 0.31 | 31
3 | 2 | 0.37 | 370.0
3 | 3 | 0.29 | 546.07
4 | 0 | 0.36 | 3.6
4 | 1 | 0.16 | 16.0
4 | 2 | 0.21 | 210.0
4 | 3 | 0.13 | 244.79
Table 1. Wasserstein metrics for edges with neighborhoods of size deg and
properties with global frequency freq. The boxed row represents the highest
sensitivity.

With edge properties set, we construct the three correlation models, as
described in section 4.3. Table 1 shows the estimated Wasserstein measures for
the various property frequencies and neighborhood size under the Conditional
correlation model. The maximum influence $W_{\infty}$ of a bucket is scaled by
the maximum neighborhood size for the bucket, up to the largest possible
neighborhood in the graph $N_{max}=1883$. That is:

$W=W_{\infty}*\min(N_{\textit{max}},10^{\log(\textit{deg})+1})$

We note several points of interest in Table 1. First, that while the largest
$W$ corresponds to large neighborhoods ($\log(\textit{deg})=3$), it doesn’t
necessarily correspond with high-frequency or low-frequency properties.
Second, we note that the maximal $W$ is roughly equivalent to half the largest
neighborhood, achieving some improved utility over group privacy.

Our second model, the Global model measures $\Pr(f(X)=w|s_{i})$ directly for
secrets $s_{i}^{0}$ and $s_{i}^{1}$. The cumulative distribution functions of
these measures are shown in Figure 5. The maximal Wasserstein measure is the
maximum horizontal distance between these two distributions, or 866.

Finally, the Binomial model represents the two label distributions by
estimating Bernoulli parameters $p_{0}$ and $p_{1}$ for each label
respectively, and measuring the maximal Wasserstein distance between these
distributions
$\Pr(f(X)=w|s_{i}^{j})=\textnormal{Binomial}(\textnormal{deg}(X_{i}),p_{j})$.
Using this approach we emprically measure $p_{0}$ to be 0.0277 and $p_{1}$ to
be 0.2739. These parameters indicate that an adjacent edge is about ten times
more likely to have property $a$ if the central edge has property $a$.

Figure 5 shows the binomial distributions for these Bernoulli parameters, and
again the maximal Wasserstein measure is the maximum horizontal distance
between the curves, or 558. Compared with the Global model, we observe that
choosing a binomial distribution is a relatively poor approximation of the
empirical behavior, but may represent an attacker’s best guess as to how
neighborhoods vary when edge properties change.

Figure 4. Cumulative distributions of $\Pr(f(X)=w|s_{i}^{j})$ for the Global
model, conditioned on secret $s_{i}^{j}$.

Figure 5. Cumulative distributions of $\Pr(f(X)=w)$ assuming binomially
distributed counts for secrets $s_{k}^{j}$ on edges $k$ adjacent to $X_{i}$.

###  5.1. Language Tasks

Description | $W$ | $\lambda$ | yield (%) | RMSE
---|---|---|---|---
Edge-level privacy | 1 | 10.0 | 809200.5 $\pm$ 529.6 (58.2%) | 12.0 $\pm$ 0.02
Node privacy | 1 | 10.0 | 77679.0 $\pm$ 159.4 (5.6%) | 6.4 $\pm$ 0.06
Binomial Model | 558 | 5580.0 | 695823.0 $\pm$ 521.3 (50.1%) | 5577.7 $\pm$ 8.14
Global Model | 866 | 8660.0 | 695316.8 $\pm$ 647.3 (50.0%) | 8665.8 $\pm$ 12.15
Conditional model | 960 | 9600.0 | 695366.3 $\pm$ 561.83 (50.0%) | 9594.2 $\pm$ 12.24
Group privacy | 1883 | 18830.0 | 695195.5 $\pm$ 428.6 (50.0%) | 18833.3 $\pm$ 26.73
Table 2. Experimental results for histogram publication, $\epsilon=100$. We measure yield- the number of positive ngram counts for each of the correlation models, as well as for node-level, edge-level, and group privacy. Description | $W$ | $E[\texttt{yield}]$ | $\sigma$
---|---|---|---
Edge-level privacy | 1 | 24814.9 | 46.3
Node privacy | 1 | 91 | 3.35
Binomial Model | 558 | 228.7 | 5.71
Global Model | 866 | 135 | 6.51
Conditional model | 960 | 116.7 | 7.29
Group privacy | 1883 | 41.9 | 3.11
Table 3. Experimental results for DPSU, $\epsilon=100$. We measure yield- the
number of extracted ngrams for each of the correlation models, as well as for
node-level, edge-level, and group privacy.

We apply the privacy mechanism to two query tasks, histogram release, and
differentially private set union (DPSU) (Gopi2020, ).

####  5.1.1. Histogram release

Our first task involves generating a histogram over edge properties. When edge
properties are ngrams, the task is equivalent to computing the frequencies of
ngrams in the corpus. To limit the sensitivity of the histogram to changes in
a single edge, we limit the contribution of each edge to $c=1000$ distinct
ngrams. The value of $c$ determines the maximum number of ngrams each edge
contributes and we choose the $c$ most common on each edge. Note that for this
task it is assumed that the domain of ngrams is known _a priori_ from a public
source. In practice it is usually necessary to identify these using the
private corpus as well, which we address in the second experiment.

Histogram publication can be accomplished using the Laplace mechanism, adding
Laplace noise with scale parameter $\lambda=cW/\epsilon$, where $c$ is the
per-edge contribution limit, $W$ is the maximal Wasserstein distance
accounting for edge-neighborhood correlation, and $\epsilon$ is the privacy
budget.

For the purposes of this experiment we choose a relatively large
$\epsilon=100$, as the corpus is comparatively small for running effective
privacy mechanisms. It has been noted in other work that privacy mechanisms on
graphs require large values of $\epsilon$, e.g. (Chen2014, ). To measure the
utility of the result, we assess root mean squared error (RMSE) between the
noisy and true histogram, and also indicate the “yield” of the histogram,
measured as the number of ngrams with positive counts (note that some noisy
counts may be negative). Positive counts are necessary for language modeling
tasks such as computing inverse-document-frequency (jones1972statistical, ),
and a large number of negative counts indicates lower utility of the resulting
histogram. Results are reported over ten trials.

Table 2 contains the results for the histogram task. Note that even with a
large epsilon, and a moderate amount of noise, in the best case (edge-level
privacy) only 58% of ngrams have useful counts. However, unlike the
Conditional, Global, or Binomial models this result doesn’t account for
correlation. Note that in the case of group privacy the added noise is
comparable to the total number of edges in the graph.

####  5.1.2. DP Set Union Application

In the histogram publication experiment we noted that it is assumed that the
domain of ngrams is known _a priori_ , an assumption which may not be true.
For instance, real-world language modeling applications may call for
differentially private vocabulary selection. Differentially private set union
(DPSU) aims to identify the union of elements in $k$ input sets (in our
setting, sets of edge properties on $k$ edges). This problem was addressed in
(Gopi2020, ). To account for edge correlation, as in the case of histogram
publication, it is necessary to scale the sensitivity of the property counts
by $cW$, as changing any edge can change as many as $c$ properties and may
influence its neighborhood by a factor as large as $W$. For this experiment we
compare the yield (the number of published n-grams) of the privacy mechanism
over ten independent applications of the mechanism, for each of the three
correlation models. We also provide baseline yield for node-level, edge-level,
and group privacy. We choose $\epsilon=100$ and $c=1000$ as in the previous
experiment.

The results of this experiment are shown in Table 3. As in the previous
experiment, the best result corresponds to edge-level privacy, which neglects
to account for edge-neighborhood correlation. Of the approaches that address
correlation, the binomial model yields the largest set of ngrams. These
experimental results illustrate the challenges associated with differentially
private language modeling tasks. If $\epsilon$ is large, and the number of
private entities numbers in the tens of thousands, the yield of a DP mechanism
can still be very limited. Despite these observations, our results illustrate
how a privacy mechanism can be appropriately modified to account for
neighborhood correlations in the graph, and we believe algorithmic yields can
only improve with larger graphs.

##  6\. Conclusion

Natural language tasks are an area of increasing relevance with recent
advances in language modeling capabilities, and the availability of large
language corpora. In order to train language models targeting organizations,
it is necessary to address latent confidentiality concerns in the data– even
models that are released for internal use may leak information across groups
of users. In this paper we explored the problem of preserving organizational
confidentiality in language tasks, leveraging the Pufferfish privacy
framework, while addressing non-IID data among edges in the organization’s
social network.

We showed how our proposed scheme presents a compromise between two extreme
measures of privacy, record-level differential privacy and group privacy. By
taking record correlation into account, our scheme provides a more meaningful
notion of privacy than record-level differential privacy, while improving the
utility compared to group privacy.

In order to address correlation in the graph, we imposed a Markov assumption
enabling us to locally model the sensitivity of graph queries under changes to
edge properties, and estimated a maximal Wasserstein metric under varying
assumptions about attackers’ priors. To demonstrate our approach we applied
the mechanism to a real-world organizational dataset and measured performance
on a pair of statistical graph query tasks.

Queries over n-grams are only a small part of developing language models from
natural language data, and our work leaves many open questions with respect to
the development of language models with high utility. For example, can the
Wasserstein mechanism be extended to model training tasks, such as the
application of stochastic gradient descent (abadi2016deep, )?

Furthermore, we model correlation up to and including very large neighborhoods
of edges, raising the question of how large neighborhoods in a closed graph
should be treated– is there value in preserving confidentiality within the
organization once neighborhoods reach some critical size? Clearly, we can
derive improved utility if we are not required to protect these groups. Our
future work aims to address these and related questions.

## References

  * [1] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, page 308–318, New York, NY, USA, 2016. Association for Computing Machinery.
  * [2] Martin Adam, Michael Wessel, and Alexander Benlian.  Ai-based chatbots in customer service and their effects on user compliance.  Electronic Markets, pages 1–19, 2020.
  * [3] Michael Backes, Mathias Humbert, Jun Pang, and Yang Zhang.  Walk2friends: Inferring social links from mobility profiles.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 1943–1957, New York, NY, USA, 2017. Association for Computing Machinery.
  * [4] Ghazaleh Beigi and Huan Liu.  A survey on privacy in social media: Identification, mitigation, and applications.  ACM/IMS Trans. Data Sci., 1(1), March 2020.
  * [5] Smriti Bhagat, Graham Cormode, Balachander Krishnamurthy, and Divesh Srivastava.  Class-based graph anonymization for social network data.  2(1):766–777, August 2009.
  * [6] J. Blocki, A. Blum, A. Datta, and O. Sheffet.  Differentially private data analysis of social networks via restricted sensitivity.  In ITCS, page 87–96, 2013.
  * [7] Mia Xu Chen, Benjamin N Lee, Gagan Bansal, Yuan Cao, Shuyuan Zhang, Justin Lu, Jackie Tsay, Yinan Wang, Andrew M Dai, Zhifeng Chen, et al.  Gmail smart compose: Real-time assisted writing.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD’19, page 196–206, New York, NY, USA, 2019. Association for Computing Machinery.
  * [8] Rui Chen, Benjamin C.M.Fung, Philip S.Yu, and Bipin C.Desai.  Correlated network data publication via differential privacy.  The VLDB Journal, 2014.
  * [9] S. Chen and S. Zhou.  Recursive mechanism: Towards node differential privacy and unrestricted joins.  In SIGMOD, page 653–664, 2013.
  * [10] James Cheng, Ada Fu, and Jia Liu.  K-isomorphism: Privacy preserving network publication against structural attacks.  pages 459–470, 01 2010.
  * [11] David Durfee and Ryan Rogers.  Practical differentially private top-k selection with pay-what-you-get composition.  CoRR, abs/1905.04273, 2019.
  * [12] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  In Proceedings of the Third Conference on Theory of Cryptography, page 265–284, 2006.
  * [13] Cynthia Dwork.  Differential privacy: A survey of results.  volume 4978, pages 1–19, 04 2008.
  * [14] Tianchong Gao, Feng Li, Yu Chen, and XuKai Zou.  Preserving local differential privacy in online social networks.  In International Conference on Wireless Algorithms, Systems, and Applications, pages 393–405. Springer, 2017.
  * [15] Arpita Ghosh and Robert Kleinberg.  Inferential privacy guarantees for differentially private mechanisms.  abs/1603.01508, 2018.
  * [16] Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhiand, and Sergey Yekhanin.  Differentially private set union.  ICML, 2020.
  * [17] Michael Hay, Chao Li, Gerome Miklau, and David Jensen.  Accurate estimation of the degree distribution of private networks.  In Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, ICDM ’09, page 169–178, USA, 2009. IEEE Computer Society.
  * [18] Michael Hay, Gerome Miklau, David Jensen, Donald Towsley, and Philipp Weis.  Resisting structural identification in anonymized social networks.  PVLDB, 1:102–114, 08 2008.
  * [19] X. He, A. Machanavajjhala, and B. Ding.  Blowfish privacy: Tuning privacy-utility trade-offs using policies.  SIGMOD ’14, page 1447–1458, New York, NY, USA, 2014. Association for Computing Machinery.
  * [20] F. L. Hitchcock.  The distribution of a product from several sources to numerous localities.  Journal of Mathematics and Physics, 20(1-4):224–230, 1941.
  * [21] Karen Sparck Jones.  A statistical interpretation of term specificity and its application in retrieval.  Journal of documentation, 1972.
  * [22] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev.  Private analysis of graph structure.  ACM Trans. Database Syst., 2014.
  * [23] S.P. Kasiviswanathan, K. Nissim, and S.Raskhodnikova.  Analyzing graphs with node differential privacy.  In TCC, page 81–98, 2013.
  * [24] Michael Kearns, Aaron Roth, Zhiwei Steven Wu, and Grigory Yaroslavtsev.  Private algorithms for the protected in social network search.  Proceedings of the National Academy of Sciences, 113(4):913–918, 2016.
  * [25] D. Kifer and A. Machanavajjhala.  Pufferfish: A framework for mathematical privacy definitions.  Association for Computing Machinery, 1:39, 2014.
  * [26] C. Liu and P. Mittal.  Linkmirage: Enabling privacy-preserving analytics on social relationships.  In NDSS, 2016.
  * [27] Changchang Liu, Supriyo Chakraborty, and Prateek Mittal.  Dependence makes you vulnerable: Differential privacy under dependent tuples.  In NDSS, volume 16, pages 21–24, 2016.
  * [28] Kun Liu and Evimaria Terzi.  Towards identity anonymization on graphs.  In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD ’08, page 93–106, New York, NY, USA, 2008. Association for Computing Machinery.
  * [29] Yushan Liu, Shouling Ji, and Prateek Mittal.  Smartwalk: Enhancing social network security via adaptive random walks.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, page 492–503, New York, NY, USA, 2016. Association for Computing Machinery.
  * [30] Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam.  $l$-diversity: Privacy beyond $k$-anonymity.  ACM Trans. Knowl. Discov. Data, 1(1):3–es, March 2007.
  * [31] F. McSherry and K. Talwar.  In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS), page 94–103, 2007.
  * [32] F. D. McSherry.  Privacy integrated queries: An extensible platform for privacy-preserving data analysis.  In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09, page 19–30, New York, NY, USA, 2009. Association for Computing Machinery.
  * [33] Prateek Mittal, Charalampos Papamanthou, and Dawn Song.  Preserving link privacy in social network based systems.  08 2012.
  * [34] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  Smooth sensitivity and sampling in private data analysis.  In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 75–84, New York, NY, USA, 2007. Association for Computing Machinery.
  * [35] Douglas Oard, William Webber, David Kirsch, and Sergey Golitsynskiy.  Avocado research email collection.  https://catalog.ldc.upenn.edu/LDC2015T03, 2015.
  * [36] S. Raskhodnikova and A. Smith.  Efficient lipschitz extensions for high-dimensional graph statistics and node private degree distributions.  FOCS, 2016.
  * [37] A. Sala, X. Zhao, C. Wilson, H. Zheng, and B.Y. Zhao.  Sharing graphs using differentially private graph models.  In Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference, page 81–98, 2011.
  * [38] S. Song, Y. Wang, and K. Chaudhuri.  Pufferfish privacy mechanisms for correlated data.  In Proceedings of the 2017 ACM International Conference on Management of Data, page 1291–1306, 2017.
  * [39] Brian Thompson and Danfeng Yao.  The union-split algorithm and cluster-based anonymization of social networks.  pages 218–227, 01 2009.
  * [40] Jia Xu, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, Ge Yu, and Marianne Winslett.  Differentially private histogram publication.  The VLDB Journal, 22(6):797–822, 2013.
  * [41] Bin Yang, Issei Sato, and Hiroshi Nakagawa.  Bayesian differential privacy on correlated data.  In SIGMOD, page 747–762, 2015.
  * [42] Xiaowei Ying and Xintao Wu.  Graph generation with prescribed feature constraints.  pages 966–977, 04 2009.
  * [43] Mingxuan Yuan, Lei Chen, and Philip S. Yu.  Personalized privacy protection in social networks.  Proc. VLDB Endow., 4(2):141–150, November 2010.
  * [44] X. Zheng, J. Han, and A. Sun.  A survey of location prediction on twitter.  IEEE Transactions on Knowledge and Data Engineering, 30(9):1652–1671, 2018.
  * [45] X. Zheng, J. Han, and A. Sun.  A survey of location prediction on twitter.  IEEE Transactions on Knowledge and Data Engineering, 30(9):1652–1671, 2018.
  * [46] Tianqing Zhu, Gang Li, Wanlei Zhou, and S Yu Philip.  Differentially private social network data publishing.  In Differential Privacy and Applications, pages 91–105. Springer, 2017.
  * [47] Lei Zou, Lei Chen, and M. Tamer Özsu.  K-automorphism: A general framework for privacy preserving network publication.  Proc. VLDB Endow., 2(1):946–957, August 2009.


# Reverse Markov- and Bernstein-type inequalities for incomplete polynomials

Tamás Erdélyi  Department of Mathematics, Texas A&M University, College
Station, Texas 77843, College Station, Texas 77843  terdelyimath.tamu.edu

(September 14, 2018 )

Let ${\Cal{P}}_{k}$ denote the set of all algebraic polynomials of degree at
most $k$ with real coefficients. Let ${\Cal{P}}_{n,k}$ be the set of all
algebraic polynomials of degree at most $n+k$ having exactly $n+1$ zeros at
$0$. Let

$\|f\|_{A}:=\sup_{x\in A}{|f(x)|}$

for real-valued functions $f$ defined on a set $A\subset{\mathbb{R}}$. Let

$V_{a}^{b}(f):=\int_{a}^{b}{|f^{\prime}(x)|\,dx}$

denote the total variation of a continuously differentiable function $f$ on an
interval $[a,b]$. We prove that there are absolute constants $c_{1}>0$ and
$c_{2}>0$ such that

$c_{1}\frac{n}{k}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}\|_{[0,1]}}{V_{0}^{1}(P)}}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}\|_{[0,1]}}{|P(1)|}}\leq
c_{2}\left(\frac{n}{k}+1\right)$

for all integers $n\geq 1$ and $k\geq 1$. We also prove that there are
absolute constants $c_{1}>0$ and $c_{2}>0$ such that

$c_{1}\left(\frac{n}{k}\right)^{1/2}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}}{V_{0}^{1}(P)}}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}}{|P(1)|}}\leq
c_{2}\left(\frac{n}{k}+1\right)^{1/2}$

for all integers $n\geq 1$ and $k\geq 1$.

reverse Markov- and Bernstein-type inequalities, polynomials with constraints,
polynomials with restricted zeros, incomplete polynomials

††support: 2010 Mathematics Subject Classifications. 41A17 ††dedicatory:
Dedicated to Professor Richard Varga on the occasion of his 90th birthday

## 1\. Introduction and Notation

In April, 2018, A. Eskenazis and P. Ivanisvili [8] asked me if I knew
polynomial inequalities of a certain type. The inequalities they were
interested in looked to me immediately as reverse (or inverse) Markov- and
Bernstein-type inequalities for incomplete polynomials on the interval
$[0,1]$, but I have not been aware of any such inequalities in the literature.
This short paper is a result of an effort to answer the questions raised by A.
Eskenazis and P. Ivanisvili [8]. G.G. Lorentz, M. von Golitschek, and Y.
Makovoz devotes Chapter 3 of their book [12] to incomplete polynomials. E.B.
Saff and R.S. Varga were among the researches having contributed significantly
to this topic. See [17] and [18], for instance. See also [1] written by I.
Borosh, C.K. Chui, and P.W. Smith. Reverse Markov- and Bernstein type
inequalities were first studied by P. Turán [19] and J. Erőd [7] in 1939. The
research on Turán and Erőd type reverses of Markov- and Bernstein-type
inequalities suddenly got a new impulse in 2006 in large part by the work of
Sz. Révész [15], and several paper have been publishes on such inequalities in
recent years, see [5], [6], [9], [10], [11], [13], [14], [16], [20], and [21],
for example.

Let ${\Cal{P}}_{k}$ denote the set of all algebraic polynomials of degree at
most $k$ with real coefficients. Let ${\Cal{P}}_{n,k}$ be the set of all
algebraic polynomials of degree at most $n+k$ having exactly $n+1$ zeros at
$0$. That is, every $P\in{\Cal{P}}_{n,k}$ is of the form

$P(x)=x^{n+1}R(x)\,,\qquad R\in{\Cal{P}}_{k-1}\,.$

Let

$\|f\|_{A}:=\sup_{x\in A}{|f(x)|}$

for real-valued functions $f$ defined on a set $A\subset{\mathbb{R}}$. Let

$V_{a}^{b}(f):=\int_{a}^{b}{|f^{\prime}(x)|\,dx}$

denote the total variation of a continuously differentiable function $f$ on an
interval $[a,b]$.

## 2\. New Results

###### Theorem 2.1

There are absolute constants $c_{1}>0$ and $c_{2}>0$ such that

$c_{1}\frac{n}{k}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}\|_{[0,1]}}{V_{0}^{1}(P)}}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}\|_{[0,1]}}{|P(1)|}}\leq
c_{2}\left(\frac{n}{k}+1\right)$

for all integers $n\geq 1$ and $k\geq 1$. Here $c_{1}=1/12$ is a suitable
choice.

###### Theorem 2.2

There are absolute constants $c_{1}>0$ and $c_{2}>0$ such that

$c_{1}\left(\frac{n}{k}\right)^{1/2}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}}{V_{0}^{1}(P)}}\leq\min_{P\in{\Cal{P}}_{n,k}}{\frac{\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}}{|P(1)|}}\leq
c_{2}\left(\frac{n}{k}+1\right)^{1/2}$

for all integers $n\geq 1$ and $k\geq 1$. Here $c_{1}=1/6$ is a suitable
choice.

## 3\. Lemmas

Our first lemma is a simple consequence of the well known Chebyshev’s
inequality (see p. 235 of [4], for instance) on the growth of polynomials.

###### Lemma 3.1

We have

$|Q(x)|\leq|2x|^{k}\|Q\|_{[-1,1]},\qquad x\in{\mathbb{R}}\setminus(-1,1)\,,$

for every $Q\in{\Cal{P}_{k}}$, $k\geq 0$.

The following lemma follows from Lemma 3.1 by a simple linear transformation.

###### Lemma 3.2

Let $a,b\in{\mathbb{R}}$ and $a<b$. We have

$|Q(x)|\leq\left|\frac{4x-2(a+b)}{b-a}\right|^{k}\|Q\|_{[a,b]}\,,\qquad
x\in{\mathbb{R}}\setminus(a,b)\,,$

for every $Q\in{\Cal{P}_{k}}$, $k\geq 0$.

Our next lemma is a special case of Lemma 3.2.

###### Lemma 3.3

Let $a,b\in{\mathbb{R}}$ and $a<b$. We have

$|Q(x)^{2}(1-x^{2})|\leq\left|\frac{4x-2(a+b)}{b-a}\right|^{2k}\|Q(u)^{2}(1-u^{2})\|_{[a,b]},\qquad
x\in{\mathbb{R}}\setminus(a,b)\,,$

for every $Q\in{\Cal{P}_{k-1}}$, $k\geq 1$.

We will use Lemmas 3.2 and 3.3 to prove our next couple of lemmas.

###### Lemma 3.4

Let $n\geq 1$ and $k\geq 1$ be integers, and let $S(x):=x^{n}R(x)$ with
$R\in{\Cal{P}}_{k}$. We have

$|S(x)|\leq x^{n/2}\|S\|_{[0,1]}\,,\qquad x\in[0,1-10k/n]\,.$

###### Lemma 3.5

Let $n\geq 1$ and $k\geq 1$ be integers, and let
$S(x):=x^{n}Q(x)\sqrt{1-x^{2}}$ with $Q\in{\Cal{P}}_{k-1}$. We have

$|S(x)|\leq x^{n/2}\|S\|_{[0,1]}\,,\qquad x\in[0,1-10k/n]\,.$

To prove the upper bounds in Theorems 2.1 and 2.2 we need the following result
proved in [2].

###### Lemma 3.6

Let $\nu\geq 0$ and $\kappa\geq 1$ be nonnegative integers. There is an
absolute constant $c_{3}>0$ such that

$|P^{\prime}(x)|\leq
c_{3}\left(\frac{(\nu+\kappa)\kappa}{x(1-x)}\right)^{1/2}\|P\|_{[0,1]}\,,\qquad
x\in(0,1)\,,$

for every polynomial $P\in{\Cal{P}}_{\nu+\kappa}$ having at most $\kappa$
zeros in the open disk with diameter $(0,1)$.

Let $k\geq 1$ be an integer. We define

$\alpha_{j}=1+\cos\left(\pi\frac{2j-1}{4k}\right)\,,\qquad j=1,2,\ldots,k\,.$

Let $n=2k+m$, where $m\geq 1$ is an integer. Let
$1>\gamma_{1}>\gamma_{2}>\cdots>\gamma_{k}>0$ be defined by

$\gamma_{j}:=\frac{\alpha_{j}-(1-m/k)}{1+m/k}\,,\qquad j=1,2,\ldots,k\,.$

Let $q_{n}\in{\Cal{P}_{n}}$ be the unique polynomial of the form

$q_{n}(x)=(x+1)^{n-k}\prod_{j=1}^{k}{(x-\rho_{j})}$

equioscillating $k+1$ times on $[-1,1]$ between $-1$ and $1$, that is, there
are

$1=x_{0}>x_{1}>\cdots>x_{k}>-1$

satisfying

$q_{n}(x_{j})=(-1)^{j}=(-1)^{j}\|q_{n}\|_{[-1,1]}\,,\qquad j=0,1,\ldots,k\,.$

To prove the upper bounds in Theorems 2.1 and 2.2 we also need the following
lemma stating a key observation from the proof of Lemma 4 in [2].

###### Lemma 3.7

With notation introduced above we have $\rho_{j}\leq\gamma_{j}$ for each
$j=1,2,\ldots,k$. As a consequence, there is an absolute constant $c_{4}>0$
such that

$\rho_{j}\leq 1-\frac{c_{4}j^{2}}{nk}\,,\qquad j=1,2,\ldots,k\,.$

For our purpose to prove the upper bounds in Theorems 2.1 and 2.2 the
following version of Lemma 3.7 will be convenient for us.

###### Lemma 3.8

Let $1\leq\kappa\leq\nu-1$ be integers. Let $T:=T_{\nu,\kappa}$ be the
Chebyshev polynomial for the Müntz space

$\text{\rm span}\\{x^{\nu},x^{\nu+1},\ldots,x^{\nu+\kappa}\\}$

on $[0,1]$ normalized so that $T(1)=1$. Denote the zeros of $T$ in $(0,1)$ by

$\beta_{1}>\beta_{2}>\cdots>\beta_{\kappa}\,.$

We have

$\beta_{j}\leq 1-\frac{c_{4}j^{2}}{(\nu+\kappa)\kappa}\leq
1-\frac{c_{4}j^{2}}{\nu\kappa}\,,\qquad j=1,2,\ldots,\kappa\,,$

where $c_{4}>0$ is the absolute constant appearing in Lemma 3.7.

In fact, what we need in the proofs of the upper bounds in Theorems 2.1 and
2.2 is the following easy consequence of Lemma 3.8.

###### Lemma 3.9

Let $\kappa\geq 2$ and $20\kappa\leq\nu$ be integers. Let $T:=T_{\nu,\kappa}$
be the Chebyshev polynomial for the Müntz space

$\text{\rm span}\\{x^{\nu},x^{\nu+1},\ldots,x^{\nu+\kappa}\\}$

on $[0,1]$ normalized so that $T(1)=1$. There is an absolute constant
$c_{5}>0$ such that

$\int_{0}^{1}{T(u)^{2}\,du}\geq\frac{c_{5}\kappa}{\nu}\,.$

## 4\. Proofs of the Lemmas

###### Demonstration Proof of Lemma 3.1

Let $T_{k}$ be the $k$-th Chebyshev polynomial defined by

$T_{k}(\cos t)=\cos(kt)\,,\qquad t\in{\mathbb{R}}\,.$

It is well known that

$T_{k}(x)=2^{k-1}\prod_{j=1}^{k}{(x-x_{j})}$

where

$x_{j}=\cos\left(\frac{(2j-1)\pi}{2k}\right)\,,\qquad j=1,2,\ldots,k\,,$

and hence

$1>x_{1}>x_{2}>\cdots>x_{k}>-1\,.$

Using Chebyshev’s inequality (see E.2 on page 235 of [4], for instance) we
have

$\begin{split}|Q(x)|\leq&|T_{k}(x)|\dot{\|}Q\|_{[-1,1]}=\left(2^{k-1}\prod_{j=1}^{k}{|x-x_{j}|}\right)\|Q\|_{[-1,1]}\cr=&\left(2^{k-1}\prod_{j=1}^{k}{|x^{2}-x_{j}^{2}|^{1/2}}\right)\|Q\|_{[-1,1]}\leq|2x|^{k}\|Q\|_{[-1,1]}\cr\end{split}$

for every $Q\in{\Cal{P}_{k}}$ and $x\in{\mathbb{R}}\setminus(-1,1)$. ∎

###### Demonstration Proof of Lemma 3.4

Let $\delta:=k/n\in(0,1)$. Without loss of generality we may assume that
$\|S\|_{[0,1]}=1$. Therefore

$\|R\|_{[1-\delta,1]}\leq(1-\delta)^{-n}\,.$

Combining this with Lemma 3.3 we obtain that if $x\in[0,1-\delta]$, then

$\begin{split}|S(x)|\leq&\,x^{n/2}\cdot|x^{n/2}R(x)|\cr\leq&\,x^{n/2}\cdot
x^{n/2}\cdot\left|\frac{4x-(4-2\delta)}{\delta}\right|^{k}\|R\|_{[1-\delta,1]}\cr\leq&\,x^{n/2}\cdot
x^{n/2}\cdot\left(\frac{4-4x}{\delta}\right)^{k}(1-\delta)^{-n}\cr\leq&\,x^{n/2}\cdot
x^{n/2}\left(\frac{4-4x}{\delta}\right)^{k}(1-\delta)^{-n}=x^{n/2}f(x)\,,\cr\end{split}$

where

$f(x)=x^{n/2}\left(\frac{4-4x}{\delta}\right)^{k}(1-\delta)^{-n}\,.$ $None$

To finish the proof we need to show that $|f(x)|\leq 1$ for every
$x\in[0,1-10k/n]$. If $1-10k/n<0$ there is nothing to prove, so we may assume
that $1-10k/n\geq 0$. The function is clearly nonnegative on $[0,1]$, and by
examining the sign of $f^{\prime}(x)$ it is easy to see that $f$ is increasing
on the interval $[0,n/(n+2k)]$, and hence on $[0,1-2k/n]\subset[0,n/(n+2k)]$
as well. Using (4.1) to estimate the value of $f$ at $x=1-10k/n\geq 0$, we
obtain

$\begin{split}f(x)=&(1-10k/n)^{n/2}40^{k}(1-k/n)^{-n}\leq(1-5k/n)^{n}40^{k}(1-k/n)^{-n}\cr\leq&(1-4k/n)^{n}40^{k}\leq
e^{-4k}40^{k}=\left(\frac{40}{e^{4}}\right)^{k}\leq 1\,,\cr\end{split}$

hence $0\leq f(x)\leq 1$ for every $x\in[0,1-10k/n]$, indeed. ∎

###### Demonstration Proof of Lemma 3.5

Applying Lemma 3.4 with $S\in{\Cal{P}}_{2n}$ defined by $S(x)^{2}=x^{2n}U(x)$,
where $U\in{\Cal{P}}_{2k}$ is defined by $U(x)=Q(x)^{2}(1-x^{2})$, we obtain
the lemma. ∎

###### Demonstration Proof of Lemma 3.9

As before, denote the zeros of $T$ in $(0,1)$ by

$\beta_{1}>\beta_{2}>\cdots>\beta_{\kappa}\,.$

We introduce the points of equioscillation $x_{0}>x_{1}>\cdots>x_{\kappa}$,
that is, $T(x_{j})=(-1)^{j}$ and $\beta_{j}\in(x_{j},x_{j-1})$ for
$j=1,2,\ldots,\kappa$, where $x_{\kappa}\geq 1-10\kappa/\nu\geq 1/2$ follows
from Lemma 3.4 and the assumption $20\kappa\leq\nu$. We define
$y_{j}\in(\beta_{j+1},x_{j})$ by

$T(y_{j})=(-1)^{j}(1/2)\,,\qquad j=1,2,\ldots,\kappa-1\,.$

The Mean Value Theorem and Lemma 3.6 imply that there are a
$\xi_{j}\in(x_{j},y_{j})$ such that

$\begin{split}1/2=&|T(x_{j})-T(y_{j})|=(x_{j}-y_{j})|T^{\prime}(\xi_{j})|\leq(x_{j}-y_{j})c_{3}\left(\frac{(\nu+\kappa)\kappa}{\xi_{j}(1-\xi_{j})}\right)^{1/2}\cr\leq&c_{3}(x_{j}-y_{j})\left(\frac{(\nu+\kappa)\kappa}{(1/2)(1-\beta_{j})}\right)^{1/2}\,,\qquad
j=1,2,\ldots,\kappa-1\,,\cr\end{split}$

and hence

$x_{j}-y_{j}\geq c_{6}\frac{(1-\beta_{j})^{1/2}}{(\nu\kappa)^{1/2}}\,,\qquad
j=1,2,\ldots,\kappa-1\,,$

with an absolute constant $c_{6}>0$. Observe that $|T(x)|\geq 1/2$ on each of
the intervals $[y_{j},x_{j}]$, $j=1,2,\ldots,\kappa-1$, so

$m(\\{x\in[0,1]:|T(x)|\geq
1/2\\})\geq\sum_{j=1}^{\kappa-1}{(x_{j}-y_{j})}\geq\sum_{j=1}^{\kappa-1}{c_{6}\frac{(1-\beta_{j})^{1/2}}{(\nu\kappa)^{1/2}}}\,,$

where $m(A)$ denotes the Lebesgue measure of a set $A\subset{\mathbb{R}}$.
Combining this with Lemma 3.8, we obtain

$m(\\{x\in[0,1]:|T(x)|\geq
1/2\\})\geq\sum_{j=1}^{\kappa-1}{c_{6}\frac{(c_{4}j^{2}/(\nu\kappa))^{1/2}}{(\nu\kappa)^{1/2}}}\geq
c_{7}\sum_{j=1}^{\kappa-1}{\frac{j}{\nu\kappa}}=\frac{c_{5}\kappa}{\nu}$

with some absolute constants $c_{7}>0$ and $c_{5}>0$, and the lemma follows. ∎

## 5\. Proofs of Theorems 2.1 and 2.2.

###### Demonstration Proof of the lower bound in Theorem 2.1

Let $P\in{\Cal{P}}_{n,k}$ be of the form

$P(x)=x^{n+1}R(x)\,,\qquad R\in{\Cal{P}}_{k-1}\,.$

We define

$S(x):=P^{\prime}(x)=x^{n}Q(x)\,,$

where $Q\in{\Cal{P}}_{k-1}$ is defined by

$Q(x)=(n+1)R(x)-xR^{\prime}(x)\,.$

We also define $y:=\max\\{1-10k/n,0\\}\geq 0$. We have

$V_{0}^{1}(P)=\int_{0}^{1}{|P^{\prime}(x)|\,dx}=\int_{0}^{y}{|P^{\prime}(x)|\,dx}+\int_{y}^{1}{|P^{\prime}(x)|\,dx}$
$None$

The first term at the right-hand side of (5.1) can be estimated by Lemma 3.4
as

$\int_{0}^{y}{|P^{\prime}(x)|\,dx}=\int_{0}^{y}{|S(x)|\,dx}\leq\int_{0}^{y}{(x^{n/2}\|S\|_{[0,1]})\,dx}\leq\frac{2}{n}\,\|S\|_{0,1]}i\,,$
$None$

while the second term at the right-hand side of (5.1) can be estimated as

$\int_{y}^{1}{|P^{\prime}(x)|\,dx}=\int_{y}^{1}{|S(x)|\,dx}\leq(1-y)\|S\|_{[0,1]}\leq\frac{10k}{n}\,\|S\|_{[0,1]}\,.$
$None$

Combining (5.1), (5.2), and (5.3) we obtain

$V_{0}^{1}(P)=\int_{0}^{1}{|P^{\prime}(x)|\,dx}\leq\frac{2}{n}\|S\|_{[0,1]}+\frac{10k}{n}\,\|S\|_{[0,1]}\leq\frac{10k+2}{n}\,\|P^{\prime}\|_{[0,1]}\,,$

and the lower bound of Theorem 2.1 follows. ∎

###### Demonstration Proof of the lower bound in Theorem 2.2

We define

$S(x):=P^{\prime}(x)\sqrt{1-x^{2}}=x^{n}Q(x)\sqrt{1-x^{2}}\,,$

where $Q\in{\Cal{P}}_{k-1}$ is defined by

$Q(x)=(n+1)R(x)-xR^{\prime}(x)\,.$

We also define $y:=\max\\{1-10k/n,0\\}\geq 0$, as in the proofs of Theorems
2.1. We have

$V_{0}^{1}(P)=\int_{0}^{1}{|P^{\prime}(x)|\,dx}=\int_{0}^{y}{|P^{\prime}(x)|\,dx}+\int_{y}^{1}{|P^{\prime}(x)|\,dx}\,.$
$None$

The first term at the right-hand side of (5.4) can be estimated by Lemma 3.5
as

$\begin{split}\int_{0}^{y}{|P^{\prime}(x)|\,dx}=&\int_{0}^{y}{|S(x)|(1-x^{2})^{-1/2}\,dx}\cr\leq&\int_{0}^{y}{(x^{n/2}\|S\|_{[0,1]})(1-y^{2})^{-1/2}\,dx}\cr\leq&\frac{2}{n}\,\|S\|_{[0,1]}(1-y)^{-1/2}\leq\frac{2}{n}\,\|S\|_{[0,1]}(10k/n)^{-1/2}\cr\leq&(kn)^{-1/2}\|S\|_{0,1]}\,,\cr\end{split}$
$None$

while the second term at the right-hand side of (5.4) can be estimated as

$\begin{split}\int_{y}^{1}{|P^{\prime}(x)|\,dx}=&\int_{y}^{1}{|S(x)|(1-x^{2})^{-1/2}\,dx}\cr\leq&\|S\|_{[0,1]}\int_{y}^{1}{(1-x^{2})^{-1/2}\,dx}\cr\leq&\|S\|_{[0,1]}\int_{\arccos
y}^{\arccos 1}{\frac{-\cos t}{\cos t}\,dt}=\|S\|_{[0,1]}\int_{0}^{\arccos
y}{\,dt}\cr\leq&(2(1-y))^{1/2}\|S\|_{[0,1]}\leq\left(\frac{20k}{n}\right)^{1/2}\|S\|_{[0,1]}\,.\cr\end{split}$
$None$

In the third line of (5.6) we used the substitution $x=\cos t$, while in the
fourth line (5.6) we used the inequality $\arccos y\leq(2(1-y))^{1/2}$ which
follows from the inequality $\cos\tau\geq 1-\tau^{2}/2$ with $\tau=\arccos y$.
(Note also that (5.5) and (5.6) show that in the sum on the right-hand side of
(5.4) the second term is the dominating one.) Combining (5.4), (5.5), and
(5.6) we obtain

$V_{0}^{1}(P)=\int_{0}^{1}{|P^{\prime}(x)|\,dx}\leq(kn)^{-1/2}\|S\|_{[0,1]}+\left(\frac{20k}{n}\right)^{1/2}\|S\|_{[0,1]}\leq
6(k/n)^{1/2}\|S\|_{[0,1]}\,,$

and the lower bound of Theorem 2.2 follows. ∎

###### Demonstration Proof of the upper bound in Theorem 2.1

If $1\leq k\leq 5$, then the upper bound of the theorem follows by considering
$P\in{\Cal{P}}_{n,k}$ defined by $P(x)=x^{n+1}$. So we can assume that $k\geq
6$. Without loss of generality we may assume that $n=2\nu\geq 0$,
$k=2\kappa+2\geq 6$ are even, and $20\kappa\leq\nu$. Let $T:=T_{\nu,\kappa}$
be the Chebyshev polynomial for the Müntz space

$\text{\rm span}\\{x^{\nu},x^{\nu+1},\ldots,x^{\nu+\kappa}\\}$

on $[0,1]$ normalized so that $T(1)=1$. We define $P\in{\Cal{P}}_{n+k-1}$ of
the form

$P(x)=x^{n+1}Q(x)\,,\qquad Q\in{\Cal{P}}_{k-2}\,,$

by

$P(x)=\int_{0}^{x}{T(u)^{2}\,du}\,.$

Lemma 3.9 implies that

$P(1)=|P(1)|\geq\frac{c_{5}\kappa}{\nu}\,.$ $None$

Observe that

$|P^{\prime}(y)|=T(y)^{2}\leq 1\,,\qquad y\in[0,1]\,,$

and hence

$\|P^{\prime}\|_{[0,1]}\leq 1\,.$ $None$

Combining (5.7) and (5.8) we have

$\frac{\|P^{\prime}\|_{[0,1]}}{|P(1)|}\leq\frac{1}{c_{5}\kappa/\nu}=\frac{1}{c_{5}}\frac{\nu}{\kappa}\leq\frac{c_{8}n}{k}$

with an absolute constant $c_{8}>0$, and the upper bound of Theorem 2.1
follows. ∎

###### Demonstration Proof of the upper bound in Theorem 2.2

If $1\leq k\leq 5$, then the upper bound of the theorem follows by considering
$P\in{\Cal{P}}_{n,k}$ defined by $P(x)=x^{n+1}$. So we can assume that $k\geq
6$. Without loss of generality we may assume that $n=2\nu\geq 0$,
$k=2\kappa+2\geq 6$ are even, and $20\kappa\leq\nu$. We define
$P\in{\Cal{P}}_{n+k-1}$ of the form

$P(z)=x^{n+1}Q(x)\,,\qquad Q\in{\Cal{P}}_{k-2}\,,$

by

$P(x)=\int_{0}^{x}{T(u)^{2}\,du}\,,$

as in the proof of the upper bound in Theorem 2.1. Let $y$ be a number such
that

$|P^{\prime}(y)\sqrt{1-y^{2}}|=\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}\,.$

Lemma 3.5 implies that $y\geq 1-10k/n$, and hence

$\|P^{\prime}(x)\sqrt{1-x^{2}}|\|_{[0,1]}=|P^{\prime}(y)\sqrt{1-y^{2}}|=T(y)^{2}\sqrt{1-y^{2}}\leq\sqrt{1-y^{2}}\leq\left(\frac{20k}{n}\right)^{1/2}\,.$
$None$

Combining (5.7) and (5.9) we have

$\frac{\|P^{\prime}(x)\sqrt{1-x^{2}}\|_{[0,1]}}{|P(1)|}\leq\frac{(20k/n)^{1/2}}{c_{5}k/n}\leq
c_{9}\left(\frac{n}{k}\right)^{1/2}$

with an absolute constant $c_{9}>0$, and the upper bound of Theorem 2.2
follows. ∎

## 6\. Acknowledgement

The author thanks Szilárd Révész for checking the details of the proofs in
this paper and for his suggestions to make the paper more readable.

## References

  * 1 I. Borosh, C.K. Chui, and P.W. Smith, On approximation of $x^{N}$ by incomplete polynomials, J. Approx. Theory 24 (1978), 227–235.
  * 2 P.B. Borwein, Markov’s inequality for polynomials with real zeros, Proc. Amer. Math. Soc. 93 (1985), 43–48.
  * 3 P.B. Borwein and T. Erdélyi, Markov-Bernstein-type inequalities for classes of polynomials with restricted zeros, Constr. Approx. 10 (1994), 411–425.
  * 4 P.B. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, Springer-Verlag, 1995.
  * 5 T. Erdélyi, Inequalities for exponential sums via interpolation and Turán-type reverse Markov inequalities, in: Frontiers in interpolation and approximation, Monographs and Textbooks in Pure and Appl. Math. (Boca Raton) Vol. 282, ed. by N. Govil at al., Chapman & Hall/CRC, 2007, pp. 119–144.
  * 6 T. Erdélyi, D. Hardin, and E.B. Saff, Inverse Bernstein Inequalities and Min-Max-Min Problems on the Unit Circle, Mathematika 61 (2015), no. 3, 581–590.
  * 7 J. Erőd, Bizonyos polinomok maximumának alsó korlátjáról, (in Hungarian)., Mat. Fiz. Lapok 46 (1939), 58–82.
  * 8 A. Eskenazis and P. Ivanisvili, private e-mail communications (2018).
  * 9 P.Yu. Glazyrina and Sz.Gy. Révész, Turán type oscillation inequalities in $L_{q}$ norm on the boundary of convex domains, Math. Inequal. Appl. 20 (2017), no. 1, 149–180.
  * 10 P.Yu. Glazyrina and Sz.Gy. Révész, Turán type converse Markov inequalities in $L_{q}$ on a generalized Erőd class of convex domains, J. Approx. Theory 221 (2017), 62–76.
  * 11 N. Levenberg and E. Poletsky, Reverse Markov inequalities, Ann. Acad. Fenn. 27 (2002), 173–182.
  * 12 G.G. Lorentz, M. von Golitschek, and Y. Makovoz, Constructive Approximation, Advanced Problems, Springer, 1996.
  * 13 G.V. Milovanović D.S. Mitrinović, and Th.M. Rassias, Topics in Polynomials: Extremal Problems, Inequalities, Zeros, World Scientific, 1994.
  * 14 Sz.Gy. Révész, On a paper of Erőd and Turán-Markov inequalities for non-flat convex domains, East J. Approx. 12 (2006), no. 4, 451–467.
  * 15 Sz.Gy. Révész, Turán type reverse Markov inequalities for compact convex sets, J. Approx. Theory 141 (2006), no. 2, 162–173.
  * 16 Sz.Gy. Révész, Tuán-Erőd type converse Markov inequalities for convex domains on the plane, in: Complex analysis and applications’13, Bulgarian Acad. Sci., 2013, pp. 252–281.
  * 17 E.B. Saff and R.S. Varga, The sharpness of Lorentz’s theorem on incomplete polynomials, Trans. Amer. Math. Soc. 249 (1979), 163–186.
  * 18 E.B. Saff and R.S. Varga, On incomplete polynomials. II, Pac. J. Math. 92 (1981), no. 1, 163–186.
  * 19 P. Turán, Über die Ableitung von Polynomen, Comput. Math. 7 (1939), 89–95.
  * 20 W. Xiao and S.P. Zhou, On weighted Turan type inequality, Glas. Mat. Ser. III 34(54) (1999), 197–202.
  * 21 S.P. Zhou, Some remarks on Turán’s inequality III: the completion, Anal. Math. 21 (1995), 313–318.