# Formatting Instructions for TMLR
Journal Submissions

Tandis Kyunghyun Cho<EMAIL_ADDRESS>
Department of Computer Science
University of New York Tandis Raia Hadsell<EMAIL_ADDRESS>
DeepMind Tandis Hugo Larochelle<EMAIL_ADDRESS>
Mila, Université de Montréal
Google Research
CIFAR Fellow

###### Abstract

Adversarial attacks on Graph Neural Networks (Gnns) reveal their security
vulnerabilities, limiting their adoption in safety-critical applications.
However, existing attack strategies rely on the knowledge of either the Gnn
model being used or the predictive task being attacked. Is this knowledge
necessary? For example, a graph may be used for multiple downstream tasks
unknown to a practical attacker. It is thus important to test the
vulnerability of Gnns to adversarial perturbations in a model and task
agnostic setting. In this work, we study this problem and show that Gnns
remain vulnerable even when the downstream task and model are unknown. The
proposed algorithm, Tandis (Targeted Attack via Neighborhood DIStortion) shows
that distortion of node neighborhoods is effective in drastically compromising
prediction performance. Although neighborhood distortion is an NP-hard
problem, Tandis designs an effective heuristic through a novel combination of
Graph Isomorphism Network with deep $Q$-learning. Extensive experiments on
real datasets and state-of-the-art models show that, on average, Tandis is up
to $50\%$ more effective than state-of-the-art techniques, while being more
than $1000$ times faster.

##  1 Introduction and Related work

Graph neural networks (Gnns) [hamilton2017graphsage, kipf2017iclr,
iclr2018gat, graphreach, lgnn], have received much success in structural
prediction tasks [graphgen, greed, physics, neuromlr, gcomb]. Consequently,
Gnns have witnessed significant adoption in the industry [pinsage, uber]. It
is therefore imperative to ensure that Gnns are secure and robust to
adversarial attacks. In this work, we investigate this aspect, identify
vulnerabilities, and link them to graph properties that potentially hold the
solution towards making Gnns more secure.

An attack may occur either during training (poisoning) or testing (evasion).
The attack strategy depends on the extent of information access. In the
literature, primarily, three modes of information access has been studied.

  1. 1.

White-box attack (WBA): In a white-box attack [liu2019unified, wang2019acm,
wu2019ijcai, xu2019ijcai], the attacker has access to all information such as
model architecture, model parameters and training hyperparameters.

  2. 2.

Black-box attack (BBA): In a black-box attack [bojchevski2019adversarial,
chang2020restricted, chen2021graphattacker, dai2018adversarial,
gupta2021adversarial, li2020adversarial, ma2020towards, ma2019attacking,
wang2020efficient], the attacker does not have access to the training model
parameters. The attacker can only pose black-box queries on a test sample and
get the model output in return (such as a label or score).

  3. 3.

Grey-box attack (GBA): A grey-box attack is a mix of white-box and black-box
attacks [liu2019unified, sun2020www, wang2019acm, zugner2018adversarial,
zugner_adversarial_2019], where the attacker has partial information of the
training model. The extent of partial information depends on the particular
attack.

In this work, we focus on targeted black-box, evasion attacks
[dai2018adversarial]. Specifically, we consider an input test graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{\mathcal{X}})$, a target node
$t\in\mathcal{V}$ and a budget $\mathcal{B}$. Our goal is to introduce at most
$\mathcal{B}$ edge alterations (additions or deletions) in $\mathcal{G}$ such
that the performance of an unknown Gnn model $\mathcal{M}$ is maximally
reduced on node $t$.

Limitations of Existing Works: Although a black-box attack does not require
any information on the model parameters, they operate under three key
assumptions:

  1. 1.

Task-specific strategy: Most Gnn models are trained for a specific task (e.g.,
node classification) using an appropriately chosen loss function. Existing
techniques for adversarial attacks tailor their strategy towards a specific
prediction task under the assumption that this task is known. Hence, they do
not generalize to unseen tasks. While this assumption acts as an added layer
of security for Gnn models, we ask the question: Is it possible to design
task-agnostic adversarial attacks?

  2. 2.

Knowledge of the Gnn model: Although black-box attacks do not need knowledge
of the model parameters, they often assume the model type. For example, an
attack may be customized for Gcn and, therefore, rendered ineffective if the
training model switches to Locality-aware Gnns [you2019pgnn, graphreach].

  3. 3.

Label-dependent: Several BBA algorithms require knowledge of the ground-truth
data. As an example, an algorithm may require knowledge of node labels to
adversarially attack node classification. These ground truth data is often not
available in public domain. For example, Facebook may tag users based on their
primary interest area. But this information is proprietary.

Contributions: Table 1 summarizes the limitations in existing algorithms for
targeted BBA. In this work, we bridge this gap. Our key contributions are as
follows:

  * •

We formulate the problem of task, model, and label agnostic black-box evasion
attacks on Gnns. The proposed algorithm, Tandis (Targeted Attack via
Neighborhood DIStortion), shows that such attacks are indeed possible.

  * •

Tandis exploits the observation that, regardless of the task or the model-
type, if the neighborhood of a node can be distorted, the downstream
prediction task would be affected. Our analysis shows that budget-constrained
neighborhood distortion is NP-hard. This computational bottleneck is overcome,
by using a Graph Isomorphism Network (Gin) to embed neighborhoods and then
using deep $Q$-learning (DQN) to explore this combinatorial space in an
effective and efficient manner.

  * •

Extensive experiments on real datasets show that, on average, Tandis is up to
$50\%$ more effective than state-of-the-art techniques for BBA evasion attacks
and $1000$ times faster. More importantly, Tandis establishes that task and
model agnosticism do not impart any additional security to Gnns.

Algorithm | Task | Model | Label
---|---|---|---
RL-S2V [dai2018adversarial] |  | ✓ |
GF-Attack [chang2020restricted] | ✓ |  | ✓
Wang et al. [wang2020efficient] |  | ✓ |
Tandis | ✓ | ✓ | ✓

Table 1: Characterization of existing targeted, black-box evasion attacks
based on agnosticism of the features.

##  2 Problem Formulation

We denote a graph as $\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{\mathcal{X}})$
where $\mathcal{V}$ is the set of nodes, $\mathcal{E}$ the set of edges, and
$\bm{\mathcal{X}}$ is the set of attribute vectors corresponding to each node
$v\in\mathcal{V}$. In this paper, we assume $\mathcal{G}$ to be an undirected
graph. Nonetheless, all of the proposed methodologies easily extend to
directed graphs. The distance $sp(v,u)$ between nodes $v$ and $u$ is measured
in the terms of the length of the shortest path from $v$ to $u$. The $k$-hop
neighborhood of a node $v$ is therefore defined as
$\mathcal{N}^{k}_{\mathcal{G}}(v)=\\{u\in\mathcal{V}\mid sp(v,u)\leq k\\}$.

The adjacency matrix of graph $\mathcal{G}$ is denoted as
$\bm{\mathcal{A}}_{\mathcal{G}}$. The distance between two undirected graphs,
$\mathcal{G}=(\mathcal{G},\mathcal{E},\bm{\mathcal{X}})$ and
$\mathcal{G}^{\prime}=(\mathcal{V},\mathcal{E}^{\prime},\bm{\mathcal{X}})$,
with the same node set but different edge set, is defined to be half of the
$L_{1}$ distance between their adjacency matrices:
$d(\mathcal{G},\mathcal{G}^{\prime})=\|\bm{\mathcal{A}}_{\mathcal{G}}-\bm{\mathcal{A}}_{\mathcal{G}^{\prime}}\|/2$.

Given a Gnn model $\mathcal{M}$, its performance on graph $\mathcal{G}$
towards a particular predictive task is quantified using a performance metric
$\mathcal{P}_{\mathcal{M}}(\mathcal{G})$:

$\mathcal{P}^{*}_{\mathcal{M}}(\mathcal{G})=f_{1}\left(\\{\mathcal{P}_{\mathcal{M}}(\mathcal{G},v)\mid
v\in\mathcal{V}\\}\right)\text{ , where }$ (1)
$\mathcal{P}_{\mathcal{M}}(\mathcal{G},v)=f_{2}(\mathbf{z}_{v,\mathcal{G}},\ell_{v})$

The performance metric $\mathcal{P}_{\mathcal{M}}(\mathcal{G},v)$ on node $v$
is a function $f_{2}$ of its embedding $\mathbf{z}_{v,\mathcal{G}}$ and its
ground truth label or score $\ell_{v}$. The overall performance
$\mathcal{P}^{*}_{\mathcal{M}}(\mathcal{G})$ is some aggregation $f_{1}$ over
the performance across all nodes. We will discuss some specific instances in
Section 4.

An adversarial attacker wishes to change $\mathcal{G}$ by performing
$\mathcal{B}$ edge deletions and additions so that the performance on a target
node $t$ is minimized. We assume that the attacker has access to a subset of
nodes $\mathcal{C}\subseteq\mathcal{V}$ and edges may be modified only among
the set $\mathcal{C}\cup\\{t\\}$. Semantically, $\mathcal{C}$ may represent
colluding bots, or vulnerable users who have public profiles instead of
private profiles, etc. Note that we do not explicitly allow node deletions and
additions, since these can be modeled through deletions and additions over the
edges [dai2018adversarial].

######  Problem 1 (Targeted Black-box Evasion Attack)

Given graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{\mathcal{X}})$, a target
node $t$, budget $\mathcal{B}$, and a subset of accessible nodes
$\mathcal{C}\subseteq\mathcal{V}$, perform at most $\mathcal{B}$ edge
additions or deletions from edge space $\\{(u,v)\mid
u,v\in\mathcal{C}\cup\\{t\\}\\}$ to form graph $\mathcal{G}^{*}$ such that

$\mathcal{G}^{*}=\arg\min_{\mathcal{G}^{\prime}:d(\mathcal{G},\mathcal{G}^{\prime})\leq\mathcal{B}}\mathcal{P}_{\mathcal{M}}(\mathcal{G}^{\prime},t)$
(2)

Both the Gnn model $\mathcal{M}$ and performance metric
$\mathcal{P}_{\mathcal{M}}(\mathcal{G}^{\prime},t)$ are unknown to the
attacker. Note that our formulation is easily extensible to a set of target
nodes, where Eq. 2 is aggregated over all targets.

##  3 Tandis: Targeted Attack via Neighborhood DIStortion

Since in the search process for $\mathcal{G}^{*}$, the attacker does not have
access to either the performance metric
$\mathcal{P}^{*}_{\mathcal{M}}(\mathcal{G})$ or the model-type of
$\mathcal{M}$, we need a surrogate function $\phi(\mathcal{G},t)$ in the graph
space, such that if
$distance(\phi(\mathcal{G},t),\phi(\mathcal{G}^{\prime},t))\gg 0$ then
$\mathcal{P}_{\mathcal{M}}(\mathcal{G},t)$ is significantly different from
$\mathcal{P}_{\mathcal{M}}(\mathcal{G}^{\prime},t)$.

###  3.1 Neighbourhood Distortion in Graph Space

To identify $\phi(\mathcal{G},t)$, we first note that there are primarily two
types of Gnns:

$\bullet$ Neighborhood-convolution: Examples of neighborhood convolution based
architectures include Gcn [kipf2017iclr], GraphSage [hamilton2017graphsage],
and Gat [iclr2018gat]. Here, the embedding of a node $v$ is computed through a
convolution operation $\psi$ over its $k$-hop neighborhood, i,e,
$\mathbf{z}_{v,\mathcal{G}}=\psi\left(\mathcal{N}^{k}_{\mathcal{G}}(v)\right)$.
Consequently, nodes with similar neighborhoods have similar embeddings
[xu2019gin, you2019pgnn].

$\bullet$ Locality-aware: In locality-aware Gnns such as P-Gnn [you2019pgnn],
GraphReach [graphreach], DeepWalk [perozzi2014deepwalk], etc., two nodes have
similar embeddings if they are located close to each other in the graph. Many
real-world graphs display small-world and scale-free properties
[albert2002statistical]. Both small-world and scale-free graphs usually have
high clustering coefficients, which indicate that one-hop neighbors share many
other neighbors as well. Thus, nearby nodes have a high likelihood of having
similar neighborhoods.

The above discussion reveals that node embeddings reflect node neighborhoods
in both architectural paradigms. Consequently, the surrogate function
$\phi(\mathcal{G},t)$ may be set to target node $t$’s $k$-hop neighborhood
$\mathcal{N}^{k}_{\mathcal{G}}(t)$. If $\mathcal{N}^{k}_{\mathcal{G}}(t)$ can
be distorted through adversarial edge edits, then it would also perturb the
embedding of $t$, which in turn would affect the performance metric. Towards
that end, we define the notion of neighborhood distortion as follows.

######  Definition 1 (Neighborhood Distortion)

Let $\mathcal{N}^{k}_{\mathcal{G}}(v)$ and
$\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v)$ be the $k$-hop neighborhoods of
$v$ in original graph $\mathcal{G}$ and adversarially perturbed graph
$\mathcal{G}^{\prime}$ respectively. The distortion in $\mathcal{G}^{\prime}$
with respect to a node $v$ is simply the Jaccard distance of their
neighborhoods.

$\delta(v,\mathcal{G},\mathcal{G}^{\prime})=1-\frac{|\mathcal{N}^{k}_{\mathcal{G}}(v)\cap\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v)|}{|\mathcal{N}^{k}_{\mathcal{G}}(v)\cup\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v)|}$
(3)

Problem 1 may now be reduced to the following objective:

$\mathcal{G}^{*}=\arg\max_{\mathcal{G}^{\prime}:d(\mathcal{G},\mathcal{G}^{\prime})\leq\mathcal{B}}{\delta(t,\mathcal{G},\mathcal{G}^{\prime})}$
(4)

where $t$ is the target node. Unfortunately, maximizing
$\delta(t,\mathcal{G},\mathcal{G}^{\prime})$ is NP-hard even for $k=2$.

###### Theorem 1

The problem
$\max_{\mathcal{G}^{\prime}:d(\mathcal{G},\mathcal{G}^{\prime})\leq\mathcal{B}}{\delta(t,\mathcal{G},\mathcal{G}^{\prime})}$
is NP-hard and the objective is non-monotone and non-submodular.

Proof. We reduce the Set Cover problem to our maximization objective. See
Appendix B in the full version for more details [sharma2021task].

Owing to NP-hardness, computing the optimal solution for the problem in Eq. 4
is not feasible. Furthermore, since the objective is neither submodular nor
monotone, even the greedy algorithms that provide $1-1/e$ approximations are
not applicable here [nemhauser1978best]. We, therefore, investigate other
optimization strategies.

Figure 1: Pipeline of Tandis in train and test phase.

###  3.2 A Reinforcement Learning Approach for Neighborhood Distortion

Fig. 1 presents the pipeline of our proposed algorithm Tandis. It proceeds
through three phases.

  1. 1.

Training data generation: We capture a feature-space representation of node
neighborhoods using Graph Isomorphism Network (Gin) [xu2019gin]. This design
choice is motivated by the property that Gin is as powerful as the Weisfeiler-
Lehman graph isomorphism test [xu2019gin]. On the feature space generated by
Gin, we define a neighborhood distortion measure.

  2. 2.

Train phase: We train a deep $Q$-learning network (DQN), to predict the impact
of an edge edit on distortion in the neighborhood embedding space. The
proposed DQN framework captures the combinatorial nature of the problem, and
shares parameters across budgets.

  3. 3.

Test phase: Given an unseen graph, we perform $\mathcal{B}$ forward passes
through the trained DQN in an iterative manner to form the answer set of
$\mathcal{B}$ edge edits.

###  3.3 Training Data Generation

The input to the training phase is a set of tuples of the form $\langle
t,e,\mathscr{M}(\mathcal{G}),\mathscr{M}(\mathcal{G}_{e})\rangle$. Here, $t$
is the target node, $e$ denotes an edge perturbation, and
$\mathscr{M}(\mathcal{G}),\;\mathscr{M}(\mathcal{G}_{e})$ are the Gin
embeddings of the original graph $\mathcal{G}$ and the graph formed following
edge edit $e$, $\mathcal{G}_{e}$, respectively.
$\mathscr{M}(\mathcal{G})=\\{\mathbf{Z}^{\mathcal{G}}_{v}\mid
v\in\mathcal{V}\\}$ contains the Gin embedding of each node in $\mathcal{G}$.
$\mathbf{Z}^{\mathcal{G}}_{v}$ characterizes the $k$-hop neighborhood of node
$v$ in graph $\mathcal{G}$. $t$ is randomly selected. The edge perturbations
are selected using a greedy mechanism, which we detail in Appendix E of the
full version [sharma2021task].

Embeddings via Gin: Gin draws its expressive power by deploying an injective
aggregation function. Specifically, in the initial layer, each node is
characterized by an one-hot vector of dimension $|\mathcal{V}|$, which encodes
the node ID. Subsequently, in each hidden layer $i$, we learn an embedding
through the following transformation.

$\mathbf{h}^{\mathcal{G}}_{v,i}=MLP\left((1+\epsilon^{i})\cdot\mathbf{h}^{\mathcal{G}}_{v,i-1}+\sum_{u\in\mathcal{N}_{\mathcal{G}}^{1}(v)}\mathbf{h}^{\mathcal{G}}_{u,i-1}\right)$
(5)

Here, $\epsilon^{i}$ is a layer-specific learnable parameter. The final
embedding $\mathbf{Z}_{v}^{\mathcal{G}}=\mathbf{h}^{\mathcal{G}}_{v,k}$, where
$k$ is final hidden layer. The embeddings are learned by minimizing the
following unsupervised loss function.

$\displaystyle\mathcal{L}(\mathscr{M}(\mathcal{G}))$
$\displaystyle=-\log\left(P\left(\mathcal{N}_{\mathcal{G}}^{k}(v)\mid\mathbf{Z}_{v}^{\mathcal{G}}\right)\right)\text{,
where }$ (6) $\displaystyle
P\left(\mathcal{N}_{\mathcal{G}}^{k}(v)\mid\mathbf{Z}_{v}^{\mathcal{G}}\right)$
$\displaystyle=\prod_{u\in\mathcal{N}_{\mathcal{G}}^{k}(v)}P\left(u\mid\mathbf{Z}_{v}^{\mathcal{G}}\right)\text{
and }$ (7)
$P\left(u\mid\mathbf{Z}_{v}^{\mathcal{G}}\right)=\frac{exp\left(\mathbf{Z}_{u}^{\mathcal{G}}\cdot\mathbf{Z}_{v}^{\mathcal{G}}\right)}{\sum_{\forall
u^{\prime}\in\mathcal{V}}exp\left(\mathbf{Z}_{u^{\prime}}^{\mathcal{G}}\cdot\mathbf{Z}_{v}^{\mathcal{G}}\right)}$
(8)

For the pseudocode, please refer to Appendix C of sharma2021task.

Distortion in embedding space: We define distortion in the perturbed graph
$\mathcal{G}^{\prime}$ with respect to the original graph $\mathcal{G}$ as
follows:

${\widehat{\delta}(t,\mathcal{G},\mathcal{G}^{\prime})}={d_{o}(t)-d_{p}(t)}$
(9)

Here,
$d_{o}(t)=\frac{1}{\left\lvert\mathcal{N}^{k}_{\mathcal{G}}(t)\right\rvert}\sum_{u\in\mathcal{N}^{k}_{\mathcal{G}}(t)}{\left\lVert\mathbf{Z}_{t}^{\mathcal{G}^{\prime}}-\mathbf{Z}_{u}^{\mathcal{G}^{\prime}}\right\rVert_{2}}$
denotes the mean L2 distance in the perturbed embedding space between target
node $t$ and the nodes in its original unperturbed neighborhood. On the other
hand,
$d_{p}(t)=\frac{1}{\left\lvert\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(t)\right\rvert}\sum_{u\in\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(t)}{\left\lVert\mathbf{Z}_{t}^{\mathcal{G}^{\prime}}-\mathbf{Z}_{u}^{\mathcal{G}^{\prime}}\right\rVert_{2}}$
denotes the same between target node $t$ and the nodes in its perturbed
neighborhood.

In our formulation, if the neighborhood remains unchanged, then
$d_{o}(t)=d_{p}(t)$, and hence distortion is $0$. The distortion will be
maximized if the distance of the target node to the original neighbors become
significantly higher in the perturbed space than the distance to the neighbors
in the perturbed graph. With the above definition of distortion in the
embedded space, the maximization objective in Eq. 4 is approximated as :

$\mathcal{G}^{*}=\arg\max_{\mathcal{G}^{\prime}:d(\mathcal{G},\mathcal{G}^{\prime})\leq\mathcal{B}}{\widehat{\delta}(t,\mathcal{G},\mathcal{G}^{\prime})}$
(10)

This approximation is required due to two reasons: (1) Maximizing Eq. 4 is NP-
hard, and (2) Eq. 4 is not differentiable.

###  3.4 Learning $Q$-function

We optimize Eq. 10 via $Q$-learning [sutton2018reinforcement], which
inherently captures the combinatorial aspect of the problem in a budget-
independent manner. As depicted in Fig. 2, our deep Q-learning framework is an
end-to-end architecture with a sequence of two separate neural components, a
graph neural network (in experiments, we use GCN [kipf2017iclr]) and a
separate Multi-layer Perceptron (MLP) with the corresponding learned parameter
set $\Theta_{Q}$. Given a set of edges $S$ and an edge $e\not\in S$, we
predict the $n$-step reward, $Q_{n}(S,e)$, for including $e$ to the solution
set $S$ via the surrogate function $Q^{\prime}_{n}(S,e;\Theta_{Q})$.

Defining the framework: The $Q$-learning task is defined in terms of state
space, action space, reward, policy, and termination condition.

$\bullet$ State space: The state space characterizes the state of the system
at any time step $i$. Since our goal is to distort the neighborhood of target
node $t$, we define it in terms of its $k$-hop neighborhood
$\mathcal{N}^{k}_{\mathcal{G}_{i}}(t)$. Note that the original graph evolves
at each step through edge edits. $\mathcal{G}_{i}$ denotes the graph at time
step $i$. The representation of state $s_{i}$ is defined as:

$\bm{\mu}_{s_{i}}={\sum_{v\in\mathcal{N}_{\mathcal{G}_{i}}^{k}(t)}}{\bm{\mu}_{v}}$
(11)

where $\bm{\mu}_{v}$ is the embedding of node $v$ learned using a Gnn (Gcn in
our implementation).

$\bullet$ Action: An action, $a_{i}$ at $i$-th step corresponds to adding or
deleting an edge $e=(v,t)$ to the solution set $S_{i-1}$ where the target node
is $t$. The representation of the action $a_{i}$ is:

$\bm{\mu}_{a_{i}}=\pm\;\textsc{Concat}\left(\bm{\mu}_{v},\bm{\mu}_{t}\right),$
(12)

where the sign denotes edge addition ($+$) and deletion ($-$) actions.

$\bullet$ Reward: The immediate ($0$-step) reward of action $a_{i}$ is its
marginal gain in distortion, i.e.,

$r(s_{i},a_{i})=\widehat{\delta}(t,\mathcal{G}_{i},\mathcal{G}_{{i+1}})$ (13)

where $\mathcal{G}_{i+1}$ is the graph formed due to $a_{i}$ on
$\mathcal{G}_{i}$.

$\bullet$ Policy and Termination:  At the $i$-th step, the policy $\pi(e\mid
S_{i-1})$ selects the edge with the highest _predicted_ $n$-step reward, i.e.,
$\arg\max_{e\in C_{t}}Q^{\prime}_{n}(S_{i},e;\Theta_{Q})$, where

$Q^{\prime}_{n}(S_{i},e=(u,t);\Theta_{Q})=\mathbf{w}_{1}^{T}\cdot\sigma(\bm{\mu_{s_{i},a_{i}}}),\\\
\text{where}\,$ (14)
$\bm{\mu_{s_{i},a_{i}}}=\mathbf{W}_{2}\cdot\textsc{Concat}\left(\bm{\mu}_{s_{i}},\bm{\mu}_{a_{i}}\right)$

$\mathbf{w}_{1}$, $\mathbf{W}_{2}$ are learnable weight vector and matrix
respectively. We terminate training after $T$ samples.

Learning the Parameter Set $\Theta_{Q}$:  $\Theta_{Q}$ consists of weight
vector $\mathbf{w}_{1}$, and weight matrices $\mathbf{W}_{2}$, and
$\\{\mathbf{W}^{l}_{GCN}\\}$. While $\mathbf{w}_{1}$ are $\mathbf{W}_{2}$ are
used to compute $Q^{\prime}_{n}(S_{i},e)$, $\mathbf{W}^{l}_{GCN}$ are
parameters of the Gcn for each hidden layer $l\in[1,k]$. $Q$-learning updates
parameters in a single episode via Adam optimizer [adam] minimizing the
squared loss.

$J(\Theta_{Q})=(y-Q^{\prime}_{n}(S_{i},e_{i};\Theta_{Q}))^{2}\\\ \text{, where
}$ $y=\gamma\cdot\max_{e=(u,t),\>u\in
C}\\{Q^{\prime}_{n}(S_{i+n},e;\Theta_{Q})\\}+\sum_{j=0}^{n-1}r(S_{i+j},e_{i+j})$

The _discount factor_ $\gamma$ balances the importance of immediate reward
with the predicted $n$-step future reward [sutton2018reinforcement]. The
pseudocode with additional details is provided in the full version
[sharma2021task].

###  3.5 Test phase

Given an unseen graph $\mathcal{G}$ with budget $\mathcal{B}$, we perform
$\mathcal{B}$ forward passes through the DQN. Each forward pass returns the
edge with the highest predicted long-term reward and updates the state space
representations. Note that the Gin is not used in the test phase. It is only
used for training the DQN. Furthermore, the proposed inference pipeline is
also independent of the test Gnn or the loss function since it directly
attacks the target node neighborhood.

###  3.6 Complexity Analysis

Here, we analyze the running time complexity of Tandis during test phase. The
complexity analysis for the train phase is provided in Appendix F in the full
version [sharma2021task] along with a complete proof of the obtained test-time
complexity.

Test phase involves finding $Q_{n}^{\prime}(S_{i},e)$ by doing a forward pass
on a $k$-layer Gcn followed by an $L$-layer MLP. We ignore the effects of the
number of layers $k$, $L$. Combining the costs from both Gcn and MLP, and the
fact that we make $\mathcal{B}$ forward passes, the total computation
complexity is
$O(\mathcal{B}(|\mathcal{E}|h_{g}+|\mathcal{V}|h_{g}^{2}+|\mathcal{V}|(h_{m}(1+h_{g}))))$.
Since $h_{g}$ and $h_{m}$ may be considered as constants, the complexity with
respect to the input parameters reduces to
$O(\mathcal{B}(\lvert\mathcal{E}\rvert+\lvert\mathcal{V}\rvert))$.

(a) CoRA-Gcn (b) CoRA-GraphSage

(c) CoRA-Gat (d) CoRA-Gnn-Guard

(e) NYC Cab

(f) CiteSeer-Gcn (g) CiteSeer-GraphSage

(h) CiteSeer-Gat

(i) CiteSeer-Gnn-Guard

(j) NYC Cab

Figure 2: Link prediction: Percentage drop in accuracy (DA) in different
models with varying budget in (a-d) CoRA and (e-h) CiteSeer. Higher means
better.

(a) CoRA-Gcn (b) CoRA-GraphSage (c) CoRA-Gat (d) CoRA-Gnn-Guard (e) NYC Cab

(f) CiteSeer-Gcn (g) CiteSeer-GraphSage (h) CiteSeer-Gat (i) CiteSeer-Gnn-
Guard (j) NYC Cab

Figure 3: Pairwise node classification: Percentage drop in accuracy (DA) in
(a-d) CoRA and (e-h) CiteSeer. Higher means better.

Budget | Dataset | CoRA | CiteSeer
---|---|---|---
| Models | Gcn | SAGE | Gat | Guard | P-Gnn | Gcn | SAGE | Gat | Guard | P-Gnn
(unattk) |  | 81.6 | 80.8 | 83.9 | 83.4 | 78.3 | 73.9 | 76.1 | 74.9 | 75.2 | 74.6
$\mathcal{B}=1$ | RL-S2V | 3.4 | 3.8 | 3.8 | 7.4 | 7.9 | 4.6 | 5.7 | 4.0 | 9.9 | 3.3
GF-Attack | 5.0 | 2.9 | 1.7 | 2.5 | 3.3 | 4.9 | 4.9 | 20.8 | 4.3 | 3.7
Tandis | 19.2 | 2.6 | 8.0 | 12.6 | 4.9 | 33.2 | 10.8 | 6.9 | 7.5 | 4.1
$\mathcal{B}=5$ | RL-S2V | 7.6 | 7.9 | 8.8 | 15.3 | 16.6 | 10.2 | 13.8 | 11.1 | 28.6 | 8.0
GF-Attack | 22.6 | 16.8 | 21.5 | 20.6 | 15.1 | 35.5 | 22.0 | 34.7 | 18.0 | 14.8
Tandis | 42.5 | 14.5 | 21.5 | 26.7 | 29.5 | 44.9 | 23.1 | 26.4 | 13.6 | 10.7
$\mathcal{B}=10$ | GF-Attack | 36.3 | 25.2 | 34.6 | 30.0 | 25.0 | 52.8 | 30.0 | 44.8 | 28.4 | 24.9
Tandis | 47.2 | 23.0 | 35.2 | 31.9 | 60.0 | 54.4 | 31.1 | 44.9 | 22.7 | 19.6
$\mathcal{B}=20$ | GF-Attack | 53.6 | 38.0 | 48.3 | 42 | 45.8 | 67.5 | 38.1 | 61.4 | 39.2 | 37.8
Tandis | 58.1 | 40.5 | 53.4 | 42 | 81.1 | 61.2 | 40.6 | 65.4 | 37.1 | 38.7

Table 2: Node Classification: Drop in DA against budget. We denote GraphSage
and Gnn-Guard as SAGE and Guard respectively. “unattk” represents the accuracy
before attack.

##  4 Empirical Evaluation

We evaluate Tandis across three downstream tasks of link prediction (LP), node
classification (NC) and pairwise node classification (PNC) [you2019pgnn,
graphreach]. We provide additional details about the experimental setup in
Appendix G of the full version [sharma2021task]. Our code base is shared in
the supplementary package.

Datasets: We use three standard real-world datasets in our experiments
following [chang2020restricted]: CoRA [mccallum2000automating], CiteSeer and
PubMed [sen2008collective]. For more details, refer Appendix G of the full
version [sharma2021task].

Baselines: We compare with GF-Attack [chang2020restricted], which is the
closest in terms of features except being model-agnostic (for which, we can
exploit transferability of attacks) (Recall Table 1). We also compare with
RL-S2V [dai2018adversarial], which is model-agnostic but not task-agnostic
(limited to node classification). We also include non-neural baselines in the
full version [sharma2021task] such as (i) random perturbations, (ii) degree
centrality, and (iii) greedy.

In this context, bojchevski2019adversarial also attacks GNNs through an idea
based on neighborhood distortion. However, we do not compare against it since
it is a poisoning attack. Poisoning attacks perturb the training data instead
of test data as in our case. Furthermore, when this algorithm is adapted for
evasion attacks, our main baseline GF-Attack [chang2020restricted] outperforms
significantly.

Target models: We test the efficacy our our attacks on five state-of-the-art
Gnn models in our experiments: (1) Gcn [kipf2017iclr], (2) GraphSage
[hamilton2017graphsage], (3) Gat [iclr2018gat], (4) P-Gnn [you2019pgnn], and
(5) Gnn-Guard [zhang2020gnnguard]. The first three are based on neighborhood-
convolution, P-Gnn is locality-aware, and Gnn-Guard is a Gnn model
specifically developed to avert adversarial poisoning attacks.

Parameters: We use a $2$-layer Gin in Tandis to quantify distortion while
training. To train the attack models, we use $10\%$ nodes each for training
and validation and $80\%$ for test. On the test set, we ensure that the class
distribution is balanced by down-sampling the majority class. Other details
regarding the hyperparameters are mentioned in sharma2021task.

Metric: We quantify the attack performance using the percentage change in
accuracy before and after attack, i.e. _Drop-in-Accuracy (DA%)_ , defined as

$DA(\%)=\frac{\text{Original Accuracy}-\text{ Accuracy after
attack}}{\text{Original Accuracy}}\times 100.$ (15)

###  4.1 Impact of Perturbations

In this section, we compare Tandis with relevant baselines on CiteSeer and
CoRA. Since both GF-Attack and RL-S2V fail to scale for higher budgets on
PubMed, we defer the results on PubMed to Section 4.2.

Link Prediction (LP): Fig. 2 evaluates the performance on LP. Tandis
consistently produces better results i.e., higher drop in accuracy, in most
cases. The only exception are Gat and P-Gnn in CiteSeer (Figures 2h, 2j). In
these cases, the drop in accuracy is similar for Tandis and GF-Attack. Another
interesting observation that emerges from this experiment is that the drop in
accuracy in Gnn-Guard is higher than the standard Gnn models. This is
unexpected since Gnn-Guard is specifically designed to avert adversarial
attacks. However, it must be noted that Gnn-Guard was designed to avert
poisoning attacks, whereas Tandis launches an evasion attack. This indicates
that defence mechanisms for poisoning attacks might not transfer to evasion
attacks.
Pairwise Node Classification (PNC): Here, the task is to predict if two nodes
belong to the same class or not. Figure 3 shows that Tandis is better across
all models except in Gat on CiteSeer, where both obtain similar performance.
Node Classification (NC): Table 2 presents the results on NC. Since RL-S2V is
prohibitively slow in inference, we report results till $\mathcal{B}=5$ for
RL-S2V. Tandis outperforms GF-Attack and RL-S2V in majority of the cases.
However, the results in NC are more competitive. Specifically, GF-Attack
outperforms Tandis in a larger number of cases than in LP and PNC. A deeper
analysis reveals that attacking NC is an easier task than LP and PNC. This is
evident from the observed drop in accuracy in NC, which is significantly
higher than in LP and PNC. Consequently, it is harder for one technique to
significantly outshine the other.

Summary: Overall, three key observations emerge from these experiments. First,
it is indeed possible to launch task and model agnostic attacks on Gnn models.
Second, Tandis, on average, produces a drop in accuracy that is more than
$50\%$ (i.e., 1.5 times) higher than GF-Attack. Third, neighborhood distortion
is an effective mechanism to perturb graphs and, hence, potential solutions to
defence strategies may lie in recognizing and deactivating graph links that
significantly distort node neighborhoods.

###  4.2 Impact on PubMed

Efficacy: Consistent with previous results, the impact of Tandis on NC is
higher than in LP and PNC (See Figs. 4a-4c). Furthermore, we note that P-Gnn
and GraphSage are more robust than other models. We are unable to include GF-
Attack in these plots due to its high inference times. Nonetheless, we compare
with GF-Attack and RL-S2V for budget $=1$ in Table 3. As visible, Tandis
obtains the best performance in most of the cases.

| Link Prediction | Pairwise NC
---|---|---
Models | Gcn | SAGE | Gat | Gcn | SAGE | Gat
GF-Attack | 5.6 | 4.4 | 6.4 | 0.2 | 0.6 | 0.4
Tandis | 3.5 | 3.4 | 7.4 | 0.8 | 1.8 | 1.2

(a) LP and PNC

Models | Gcn | SAGE | Gat | P-Gnn | Gnn-Guard
---|---|---|---|---|---
(unattacked) | 86.2 | 86.5 | 87.6 | 86.3 | 83.6
RL-S2V | 2.8 | 2.3 | 2.7 | 2.1 | 5.2
GF-Attack | 36.9 | 3.8 | 36.5 | 3.4 | 11.7
Tandis | 41.6 | 9.7 | 20.9 | 3.5 | 13.7

(b) NC

Table 3: Drop in accuracy (DA) in PubMed at budget $=1$.

(a) NC

(b) LP

(c) PNC

(d) Inference Time

Figure 4: Performance of Tandis in the PubMed dataset (a-c), (d) Inference
times of Tandis (solid lines) and GF-Attack (dashed lines) against budget.

###  4.3 Running Time

Figure 4d compares the inference times of Tandis and the second-best baseline
GF-Attack, i.e. the running time of finding black-box perturbations. We do not
compare with RL-S2V, since it fails to complete running for any
$\mathcal{B}>1$ even after $10$ hours. Tandis (represented by solid lines) is
more than $3$ orders of magnitude faster than GF-Attack for the largest
dataset, PubMed. Also, time taken by Tandis grows at a much lower rate with
the increase in budget than GF-Attack. Furthermore, Tandis requires training
only once per dataset and the entire training procedure takes upto $3$ hours
even for the largest dataset, i.e. PubMed.

###  4.4 Potential Detection Mechanisms

Feature | Correlation (p-value)
---|---
Feature Similarity (fs) | $\mathbf{-0.20^{*}\pm 0.196}$
Degree (dg) | $\mathbf{-0.15^{*}\pm 0.008}$
Local Clustering Coeff. (cc) | $\mathbf{+0.25^{*}\pm 0.004}$

Table 4: Correlation of node properties with neighborhood distortion (∗
indicates $p<0.001$).

Here, we conduct an experiment on CoRA dataset to find correlations between
perturbations chosen by our attacks and the ones chosen according to common
network properties. The aim is to (1) interpret our attacks in graph space and
(2) identify potential ways to catch our evading attack.

In particular, we consider all node pairs of the form $(t,v)$, where $t$ is
the target and $v$ is the node to which an edge may be added or removed. We
characterize each $v$ with several graph level properties such as clustering
coefficient, conductance, etc (See sharma2021task for the complete list).
Corresponding to each property, we create a sorted list $P$ of nodes in
descending order of their property values. Similarly, we create another list
$D$ with nodes that are sorted based on the distortion produced due to
removal/addition of edge $(t,v)$. We next compute the Spearman’s rank
correlation coefficient between $P$ and $D$ and its $p$-value. Properties with
statistically significant correlations may indicate graph-level features that
govern the selection of perturbations by Tandis and thus, effective in
detecting these attacks.

Table 4 presents the properties that are statistically significant. These
results indicate that edges to nodes of high clustering coefficient (cc) lead
to large distortion. This result is not surprising since a node with high cc
short-circuits the target node to a large number of nodes (or removes this
short-circuit in case of edge deletion). The negative correlation with fs is
also intuitive, since low fs with a node indicates that an edge to it injects
a large amount of heterophily. The results for dg is rather surprising, where
a negative correlation indicates that edges to low-degree nodes are more
effective. A deeper analysis reveals that dg is negatively correlated with cc,
which may explain the negative correlation with distortion as well. Note that,
in GF-Attack, it has been shown that perturbing edges with high degree nodes
is not an effective attack strategy. Our study is consistent with that result,
while also indicating that cc is a more effective graph-level parameter.

##  5 Conclusions

Gnns have witnessed widespread usage for several tasks such as node
classification and link prediction. Hence, assessing its robustness to
practical adversarial attacks is important to test their applicability in
security-critical domains. While the literature on adversarial attacks for
Gnns is rich, they are built under the assumption that the attacker has
knowledge of the specific Gnn model used to train and/or the prediction task
being attacked. The key insight in our proposed work is that simply distorting
the neighborhood of the target node leads to an effective attack regardless of
the underlying Gnn model or the prediction task. Hence, hiding the model or
the task information from the attacker is not enough. We also find that such
perturbations are not correlated with simple network properties and may be
hard to detect. Our work thus opens new avenues of research that can focus on
defending and detecting such practical attacks to analyze why such
perturbations should transfer across different tasks and victim models.

#### Broader Impact Statement

In this optional section, TMLR encourages authors to discuss possible
repercussions of their work, notably any potential negative impact that a user
of this research should be aware of. Authors should consult the TMLR Ethics
Guidelines available on the TMLR website for guidance on how to approach this
subject.

#### Author Contributions

If you’d like to, you may include a section for author contributions as is
done in many journals. This is optional and at the discretion of the authors.
Only add this information once your submission is accepted and deanonymized.

#### Acknowledgments

Use unnumbered third level headings for the acknowledgments. All
acknowledgments, including those to funding agencies, go at the end of the
paper. Only add this information once your submission is accepted and
deanonymized.

## Appendix

###  A Attack taxonomy

  * •

Poisoning attacks: In poisoning attacks, the attacker injects adversarial
samples in the training data, so that the accuracy of the predictive task
being modeled is compromised [bojchevski2019adversarial, gupta2021adversarial,
li2020adversarial, liu2019unified, sun2020www, wang2019acm, xu2019ijcai,
zhang2019ijcai, zugner2018adversarial, zugner_adversarial_2019]. Note that
[bojchevski2019adversarial] also addresses attacks on embedding, however we do
not compare it against our method as it is a poisoning attack and one of our
baselines, GF-Attack [chang2020restricted] clearly outperforms this on the ode
classification task.

  * •

Evasion attacks: In evasion attacks, the attacker adversarially modifies the
test graph, so that the accuracy on the test graph is compromised
[chang2020restricted, chen2021graphattacker, dai2018adversarial,
ma2020towards, ma2019attacking, wang2020efficient, wu2019ijcai, xu2019ijcai,
zugner2018adversarial]. A modification may involve addition or deletion of
nodes and edges, or changing node attributes. Note that the trained model
remains unchanged.

Since an evasion attack relies only on the test data, it is comparatively
easier to launch than a poisoning attack. As an example, consider the task of
friend recommendation (link prediction) in a social network such as Facebook.
It is easier for an attacker to infuse bots in Facebook that send friend
requests (edge rewiring) to strategically selected users than getting access
to Facebook’s training model.

###  B Proof of Thm. 1

####  B.1 NP-hardness

We reduce the Set Cover problem to our maximization objective for $k=2$.

######  Definition 2 (Set Cover)

Given a collection of subsets $S=\\{S_{1},\cdots,S_{m}\\}$ from a universe of
items $U=\\{u_{1},\cdots,u_{n}\\}$ and a budget $b$, determine if there exists
a set of $b$ subsets $\mathbb{\mathcal{A}}\subseteq S$ such that
$\cup_{\forall S_{i}\in\mathbb{\mathcal{A}}}S_{i}=U,\;|\mathcal{A}|=b$.

Let $\langle U=\\{u_{1},\cdots,u_{n}\\},S=\\{S_{1},\cdots,S_{m}\\},b\rangle$
be an instance of the Set Cover problem. We map this to an instance of our
problem via constructing a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ as
follows. From $S$ and $U$, we create two sets of nodes $X=\\{x_{i}\mid
S_{i}\in S\\}$ and $Y=\\{y_{j}\mid u_{j}\in U\\}$ respectively. We also add an
additional node $t$ with no edges attached to it. Thus, $\mathcal{V}=X\cup
Y\cup\\{t\\}$. Additionally, if $u_{j}\in S_{i}$, an edge $(x_{i},y_{j})$ is
added to the edge set $\mathcal{E}$. The set of colluding nodes is set to
$\mathcal{C}=X$, budget $\mathcal{B}=r$, and the target node is $t$. In this
construction, if $\mathcal{A}$ is a solution set of the Set Cover instance,
then the corresponding set of edge additions
$B=\\{(t,x_{i})|S_{i}\in\mathcal{A}\\}$ maximizes
$\delta(t,\mathcal{G},\mathcal{G}^{\prime})$. Specifically,
$\mathcal{N}^{2}_{\mathcal{G}}(t)=\emptyset$ since no edges are incident on
it. Thus, maximizing $\delta(t,\mathcal{G},\mathcal{G}^{\prime})$ is
equivalent to maximizing $|\mathcal{N}^{2}_{\mathcal{G}^{\prime}}(t)|$. The
maximum value of $|\mathcal{N}^{2}_{\mathcal{G}^{\prime}}(t)|=b+n$ if and only
if $\mathcal{A}$ is a set cover. $\hfill\square$

####  B.2 Non-montone

We first define $\delta(v,\mathcal{G},\mathcal{G}^{\prime})$ as a set
function:

$\delta(v,\mathcal{G},\mathcal{G}^{\prime}):=f\left(\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v);\mathcal{N}^{k}_{\mathcal{G}}(v)\right)=1-\frac{\left|\mathcal{N}^{k}_{\mathcal{G}}(v)\cap\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v)\right|}{\left|\mathcal{N}^{k}_{\mathcal{G}}(v)\cup\mathcal{N}^{k}_{\mathcal{G}^{\prime}}(v)\right|}$

Hence, the objective can be written as a set function as

$f(A;B)=1-\frac{|A\cap B|}{|A\cup B|}$

Consider a set $S$ and $x\not\in S$. Now, we have two cases:

##### Case (1) $x\in B$:

$f(S\cup\\{x\\};B)-f(S;B)=\frac{|S\cap B|}{|S\cup
B|}-\frac{|(S\cup\\{x\\})\cap B|}{|(S\cup\\{x\\})\cup B|}=\frac{-1}{|S\cup
B|}<0.$

##### Case (2) $x\not\in B$:

$f(S\cup\\{x\\};B)-f(S;B)=\frac{|S\cap B|}{|S\cup
B|}-\frac{|(S\cup\\{x\\})\cap B|}{|(S\cup\\{x\\})\cup B|}=|S\cap
B|\left(\frac{1}{|S\cup B|}-\frac{1}{|S\cup B|+1}\right)>0.$

Hence, $f$ is not monotonic and the sign of its change depends on whether
$x\in B$ or $x\not\in B$. $\hfill\square$

####  B.3 Non-submodular

######  Definition 3 (Submodularity)

A set-function $h$ is submodular if for every sets $X,Y$ such that $X\subseteq
Y$, and for every $e\not\in Y$,

$h(X\cup\\{e\\})-h(X)\geq h(Y\cup\\{e\\})-h(Y).$

Consider $f$ as defined above. We consider two sets $S,T$ such that $S\subset
T$. Let $x\not\in T$ but $x\in B$. Then,
$f(S\cup\\{x\\};B)-f(S;B)=\frac{-1}{|S\cup B|}$, and
$f(T\cup\\{x\\};B)-f(T;B)=\frac{-1}{|T\cup B|}$. Thus,
$(f(S\cup\\{x\\};B)-f(S;B))-(f(T\cup\\{x\\};B)-f(T;B))=\frac{1}{|T\cup
B|}-\frac{1}{|S\cup B|}<0$.

Therefore, the objective $f$ is not submodular. $\hfill\square$

###  C Expressive power of Gin

####  C.1 Pseudo-code of Gin

In Section 3.3, Gin is trained in an unsupervised manner minimizing the loss
given in Equation 6. In particular, we apply negative-sampling
[hamilton2017graphsage] to approximate the following loss function:

$\small\mathcal{L}(\mathscr{M}(\mathcal{G}))=-\log(\sigma(\mathbf{Z}_{u}^{T}\mathbf{Z}_{v}))-\
\mathbb{E}_{v_{n}\sim
P_{n}(v)}\log(\sigma(-\mathbf{Z}_{u}^{T}\mathbf{Z}_{v_{n}}))$ (16)

where $P_{n}(v)$ denotes a distribution of nodes which do not have an edge
with $v$ and $v_{n}$ is negatively sampled from this distribution. $\sigma$
denotes the activation function Sigmoid.

For training, we sample a set of positive and negative random walks and
optimize the total loss in a batch for a fixed number of epochs. Therefore,
$v$ in Equation 16 denotes the nodes in a positive random walk, which is
derived from a random walker. Similarly, $v_{n}$ denotes the nodes in a
negative random walk, i.e., $v_{n}$ is a randomly chosen node in the whole
graph. Algorithm 1 shows the entire process.

Algorithm 1 Training the Gin model $\mathcal{M}_{G}$

0: Number of epochs $N_{e}$, hyperparameters $h_{RW}$ (See App. G.3) for the
Random Walker

0: Learn parameter set $\Theta_{G}$

1: for epoch $i\leftarrow 1$ to $N_{e}$ do

2: $W_{p}\leftarrow$ Sample a batch of positive random walks with $h_{RW}$

3: $W_{n}\leftarrow$ Sample a batch negative random walks by selecting a set
of random nodes

4: Back-propagate the average loss (Equation 16) using $\mathcal{M}_{G}$ on
$W_{p}$ and $W_{n}$

5: return $\Theta_{Q}$

####  C.2 Expressive Power of Gin

In this section, we explain the reasons of why a Gin model would be the most
effective choice in the case of a black-box model. Since our attack must be
model-agnostic, the embedding neighborhood should be such that it can
represent any underlying model’s representation. Gin has been shown to be a
maximally powerful Gnn model. In particular, it has been shown to be as
powerful as a Weisfeiler-Lehman (WL) graph isomorphism test, which assigns
canonical labels such that unique labels guarantee that the two graphs are not
isomorphic. [xu2019gin] shows that injectivity of the neighborhood aggregation
function is a necessary condition for a Gnn to simulate a WL test and give one
such example in Gin. Hence, any underlying black-box Gnn model has less
representation power by aggregating information from their neighbors than a
Gin. This motivates us to use a Gin to model the neighborhood for distortion,
so that we can effectively attack any target black-box model.

In order to further justify our claim, we conduct an ablation study and
compare the performance of our attacks using a Gcn and a Gin as our embedding
model. Both are trained in the same unsupervised manner. Figure 5 compares the
$DA(\%)$ across different budgets when using Gcn embeddings as compared to
when using Gin embeddings for node classification in CoRA dataset. The results
are interesting and show the apparent trade-off in using a theoretically
powerful Gin model to attack common Gnn target models. While Gcn embeddings
are able to transfer the neighborhood better (our method produces more DA,
higher is better) for Gnns that are based on neighborhood convolution, they do
not get transferred well to the locality-aware P-Gnn (Figure 5e).

Hence, this shows that our strategy can be tuned based on the amount of
information that is made available to the attacker. In a completely model-
agnostic setting, it is reasonable to use a powerful Gin model to generate
embeddings. If we know some distinct features about the underlying model, then
it will be more beneficial to use an embedding model that has a similar or
most representative neighborhood aggregation function, so that the knowledge
of neighborhood distortion gets transferred well.

Furthermore, it is worthwhile to note here that if the attacker wishes to
leverage the task-agnosticism, then they might even use an embedding model
trained for that specific task (in which case, the embeddings/representations
would be specially tuned to the attack scenario). Tandis is a generic and
unique framework that allows this kind of tuning according to the available
attack/model information.

(a) CoRA-Gcn (b) CoRA-GraphSage

(c) CoRA-Gat (d) CoRA-Gnn-Guard

(e) CoRA-P-Gnn

Figure 5: Ablation study: Comparison of using Gcn v/s Gin embeddings for
distortion in the Tandis attack for the node classification task in CoRA.
Gin-U represents that Gin is trained in an unsupervised manner.

###  D Rationale behind two GNNs

The Gnns serve different roles. The role of $\bm{\mu}_{v}$ is to effectively
characterize the state-space (Eq. 11) and actions (Eq. 12), and capture the
combinatorial nature of the problem. Hence, the Gcn embeddings $\bm{\mu}_{v}$
are trained end-to-end in the DQN alongwith an MLP to learn the $Q$-function.
On the other hand, Gin embeddings $\mathbf{Z}_{v}$ are trained independently
to characterize neighborhood distortion. Furthermore, while the Gin is trained
in a transductive manner with one-hot encodings of nodes, the Gcn trains in an
inductive manner, where in the initial layer the nodes are characterized by
their feature vectors $\bm{\mathcal{X}}_{v}$ (Recall § 2).

###  E Greedy Selection of Edge Perturbations for Training

Algorithm 2 describes how the Q-function is learned in the RL setup (Section
3.4) of Tandis. In particular, for each node in the training set, we generate
perturbations for $T$ steps following a $\epsilon$-greedy strategy, as noted
in Step 4 (Algorithm 2). Each such perturbation can be represented by a tuple
storing the current state, new state, action, and accumulated rewards (defined
in Section 3.4). This is stored in an “experience replay” memory, from which a
batch of samples is randomly sampled. Finally, this batch is used to
backpropagate the squared loss. We repeat this process for $L$ steps.

Algorithm 2 Learning $Q$-function

0: Trained Gin model $\mathcal{M}$, hyper-parameters $M$, $N$ relayed to
fitted $Q$-learning, number of episodes $L$ and sample size $T$.

0: Learn parameter set $\Theta_{Q}$

1: Initialize experience replay memory $M$ to capacity $N$

2: for episode $e\leftarrow 1$ to $L$ do

3: for step $j\leftarrow 1$ to $T$ do

4: $v_{j}\leftarrow\begin{cases}\text{random node }v\not\in S_{j};\text{ with
probability }\\\ \hskip 91.04881pt\epsilon=\max\\{0.05,0.9^{j}\\}\\\
\text{argmax}_{v\not\in S_{j}}Q^{\prime}_{n}(S_{j},v;\Theta_{Q});\text{
otherwise}\end{cases}$

5: $S_{j+1}\leftarrow S_{j}\cup\\{v_{j}\\}$

6: if $t\geq n$ then

7: Add tuple $(S_{j-n},v_{j-n},\sum_{i=j-n}^{t}r(S_{i},v_{i}),S_{j})$ to $M$

8: Sample random batch $B$ from $M$

9: Update $\Theta_{Q}$ by Adam optimizer for $B$

10: return $\Theta_{Q}$

###  F Complexity Analysis

####  F.1 Train phase

The training complexity consists of two parts – (1) Training the Gin, and (2)
Training the DQN. Gin is trained in an unsupervised manner, following
Algorithm 1. This accounts for a training complexity of $O(N_{e}lh_{g}T_{r})$,
where $N_{e}$ is the no. of epochs, $l$ is the no. of Gin layers, $h_{g}$ is
the hidden dimension of Gin, and $T_{r}$ is the time for random walk
generation. We follow node2vec’s code [grover2016node2vec] to generate random
walk, which accounts for $O(L_{r}/(k_{r}(L_{r}-k_{r})))$, where $L_{r}$ is the
length of the random walks, $k_{r}$ is the no. of samples to generate. The
second part in the analysis is due to DQN, which is trained by following
Algorithm 2. This accounts for
$O(LT|\mathcal{V}|(Bh_{m}h_{gc}+(|\mathcal{E}|h_{gc}+|\mathcal{V}|h_{gc}^{2}))$,
where $L$ is the no. of episodes, $T$ no. of time steps, $B$ batch size,
$|\mathcal{V}|$ no. of nodes, $|\mathcal{E}|$ no. of edges, $h_{m}$ dimension
of MLP, and $h_{gc}$ dimension of GCN layers respectively. $h_{m}$ $h_{gc}$ is
the time for MLP forward pass, and
$(|\mathcal{E}|h_{gc}+|\mathcal{V}|h_{gc}^{2})$ is the time for GCN forward
pass (as derived in the next section).

####  F.2 Test phase

To find $Q_{n}^{\prime}(S_{i},e)$, we do a forward pass on a $k$-layer Gcn
followed by an $L$-layer MLP. We ignore the factors of $k$ and $L$ as their
values are usually small and fixed ($\leq 3$), and assume the average degree
in $\mathcal{G}$ to be $d$.

Gcn: We assume the hidden dimension to be $h_{g}$. Each node draws messages
from their neighbors and performs a mean pool, followed by linear
transformation through weight matrices $\mathbf{W}^{l}_{\textsc{Gcn}}$. These
operations consume $O(d\cdot h_{g})$ and $O(h_{g}^{2})$ respectively. When
performed over all nodes in $\mathcal{G}$, the complexity is
$O(|\mathcal{E}|h_{g}+|\mathcal{V}|h_{g}^{2})$.

MLP: The transformations performed by the MLP is outlined in Eq. 14. The
representation dimensionality of a state and an action are $h_{g}$ (Eq. 11)
and $2h_{g}$ (Eq. 12) respectively. If the hidden dimension in the MLP is
$h_{m}$, then computing $\bm{\mu}_{s_{i},a_{i}}$ in Eq. 14 consumes
$O(h_{g}\cdot h_{m})$. The final conversion to a scalar (predicted long-term
rewards) consumes an additional $O(h_{m})$ cost. This operation is repeated
over each candidate edge since we choose the one with the highest predicted
reward. Hence, the total complexity is $O(|\mathcal{V}|(h_{m}(1+h_{g})))$.

Combining the costs from both Gcn and MLP, and the fact that we make
$\mathcal{B}$ forward passes, the total computation complexity is
$O(\mathcal{B}(|\mathcal{E}|h_{g}+|\mathcal{V}|h_{g}^{2}+|\mathcal{V}|(h_{m}(1+h_{g}))))$.
Since $h_{g}$ and $h_{m}$ are fixed constants, the complexity with respect to
the input parameters reduces to
$O(\mathcal{B}(\lvert\mathcal{E}\rvert+\lvert\mathcal{V}\rvert))$.

###  G Experimental Setup

All experiments are performed on a machine running Intel Xeon G-$6148$ with a
setting of $20$ cores of $2.4$ GHz, one Nvidia $V100$ card with $32$ GB GPU
memory and $192$ GB RAM with Ubuntu 16.04.

####  G.1 Datasets

We use three real-world datasets in our experiments following
[chang2020restricted]: CoRA [mccallum2000automating], CiteSeer and PubMed
[sen2008collective]. These are citation networks where vertices denote
documents with bag-of-words features and edges denote citation links. We
consider only the largest connected component which is consistent with our
baseline setup [chang2020restricted]. The statistics of the datasets are shown
in the Table 5.

Datasets | # Nodes | # Edges | # Node Labels
---|---|---|---
Cora | 2.7K | 5.4K | 7
Citeseer | 3.3K | 4.7K | 6
PubMed | 19K | 44K | 3
Table 5: Datasets used in the experiments.

####  G.2 Tasks

##### Node Classification:

All the target models are trained for the node classification task using
$10\%$ of the nodes each for training and validation. The remaining $80\%$
nodes are used for the testing where each node is separately considered as a
target node for the attack strategies and the average accuracy quantified as
$DA(\%)$ in Equation 15. For the large dataset Pubmed, we consider a randomly
sampled $10\%$ of the nodes out of the test set and we present the average
value after $5$ different runs.

##### Link Prediction:

All the target models are trained using a binary cross entropy loss for this
task using $10\%$ of the positive and negative links each for training and
validation. Note that we ensure down-sampling of the majority class and thus,
ensure that equal number of positive (existing) and negative (non-existing)
links are considered in our training, validation and test sets. We consider a
randomly sampled $30\%$ links for the test set and note the average drop in
accuracy after considering each links separately. Each target link is attacked
by considering one of the end-nodes as the target node on which edges can be
added or deleted. We randomly sample $10\%$ of the test set for the large
dataset Pubmed and note the average value after five different runs.

##### Pairwise node-classification:

The setup is similar to the task of link prediction except for the end-labels
which denote the equality of node pairs’ labels rather than an existence of an
edge between them. Thus, the class distribution is now balanced based on this
label. We follow a $10-10-30$ split here as well and take $10\%$ sample to
target Pubmed.

####  G.3 Parameters

Our framework (Figure 1) needs two trainable models, Gin and DQN. These are
trained separately and have different hyper-parameters as described below.

#####  Gin:

We use a $2$-layer Gin model with hidden dimension of $16$. Here also, we use
$10\%$ each for training and validation. This is trained in an unsupervised
manner. To generate the random walks, we use $p=q=1$ (where $p$ and $q$ denote
the likelihood of return and measure of in-out search respectively
[grover2016node2vec]), a walk length of $20$, a context size of $10$ and do
$10$ walks per node.

#####  DQN:

To train the DQN component, we use Deep Q-learning as noted in the Algorithm
2. Here, the number of episodes $L$ and number of steps $T$ are fixed to be
$100$ and $10$ respectively. Also, $n$ is fixed to be equal to $2$ and thus,
we consider a $2$-step Q-function. To model the DQN, we consider a $2$-layer
Gcn followed by a $2$-layer MLP, both with hidden dimensions of $16$. We use
$40\%$ nodes as targets for the training the DQN out of which the replay
memory is made, following $\epsilon$-greedy steps.

####  G.4 Baselines

#####  RL-S2V:

We use the RL-S2V [dai2018adversarial] in a model-agnostic manner following
the formulation mentioned in GF-Attack [wang2020efficient]. In particular, we
train the Deep Q-network using a surrogate Gcn model and then transfer these
attacks to all our target models (as mentioned in Section 4). Also, note that
the surrogate Gcn is trained differently than the target Gcn model. We train
for $100000$ steps for each dataset and separately for each budget (until $5$
as noted in Table 2).

#####  GF-Attack

[wang2020efficient]: This is the state-of-the-art in the restricted black-box
setting and the only available task-agnostic attack framework. It attacks the
embeddings by perturbing the corresponding graph filters. While the exact
optimization may depend upon the type of black-box model to attack, we can
exploit the transferability of these attacks and make it model-agnostic. We
use the Gcn setting mentioned in [wang2020efficient] to attack each of our
black-box models. For link tasks, we use the same strategy as ours and target
a randomly chosen end-node.

###  H Additional Results

(a) CoRA-Gcn (b) CoRA-GraphSage (c) CoRA-Gat (d) CoRA-Gnn-Guard (e) CiteSeer-
P-Gnn

(f) CiteSeer-Gcn (g) CiteSeer-GraphSage (h) CiteSeer-Gat (i) CiteSeer-Gnn-
Guard (j) CiteSeer-P-Gnn

Figure 6: Comparison of non-neural baselines with Tandis for the node
classification task in CoRA and CiteSeer. Tandis outperforms the baselines in
all cases.

(a) CoRA-Gcn (b) CoRA-GraphSage (c) CoRA-Gat (d) Time (CoRA)

(e) CiteSeer-Gcn (f) CiteSeer-GraphSage (g) CiteSeer-Gat (h) Time (CiteSeer)

Figure 7: Comparison of Tandis with its non-neural Greedy equivalent for the
node classification task in CoRA and CiteSeer averaged over $10$ targets.
Greedy performs better than Tandis, but it takes time more than $4$ orders of
magnitude with an improvement of only $\sim 20\%$. So, Greedy is not
practically feasible.

####  H.1 Non-neural Baselines

Here, we compare our method Tandis against two non-neural baselines — Random
and Degree, as defined in [chang2020restricted]. Figure 6 shows the results of
these baselines for node classification task in CoRA and CiteSeer compared
with Tandis. Note that our method comprehensively outperforms these baselines.

####  H.2 Comparison with Greedy

Figure 7 shows the comparison between our proposed RL optimization of Equation
10 (i.e., Tandis) and the corresponding greedy optimization (i.e., Greedy) for
$10$ targets on the node classification task in CoRA and CiteSeer. While
Greedy does consistently better, the time taken is more than $4$ orders in
magnitude (See Fig. 7(d) and Fig. 7(h). Thus, even though we can obtain better
performance by greedily optimizing the proposed neighborhood distortion, the
trade-off for efficiency is huge, which makes the proposed RL optimization
more scalable and efficient for finding optimal perturbations maximizing
neighborhood distortion (i.e., Equation 9).

####  H.3 Interpretability

In this section, we study additional node properties in order to interpret the
neighborhood distortion. In order to do that, we choose the following
different node-level properties.

##### Feature and Graph Properties

  * •

Feature Similarity: Jaccard similarity of node features of the target and the
candidate node for perturbation.

  * •

Degree: In an undirected graph, the node degree is the number of edges
adjacent to the node. In a directed graph, the in-degree and the out-degree of
a node is the number of edges incident on the node, and the number of outgoing
edges from the node respectively. In our case, since we have conducted our
study on undirected graphs, the first definition holds true. However, a
similar study can easily be conducted in case of a directed graph.

  * •

Local Clustering Coefficient: The local clustering coefficient of a vertex is
given by the ratio of the actual number of links between the vertices in its
neighborhood divided and the total no. of possible links that can exist
between these neighbor vertices.

  * •

Reverse $k$-NN Rank: Position of the candidate node in the ranked list of
nodes, sorted in descending order, according to the number of times the node
occurs in the 2-hop neighbourhood of all the other nodes in the graph.

##### Community Based Properties

We have also taken into consideration a few community related measures. For a
given target $t$ we define its community, $S$, as the $50$ nearest neighbours
in the original embedding space. Considering the fact that upon perturbation,
the neighbourhood of the target becomes distorted, we define the perturbed
community, $S^{\prime}$, of target $t$ as the $50$ nearest neighbours in the
perturbed embedding space. We expect that after perturbation, the quality of
the community should worsen. Throughout the definitions stated further, m(S)
denotes the number of edges between the nodes in community $S$, and c(S)
denotes the number of edges between nodes in $S$ and the rest of the network,
i.e., nodes in $\mathcal{V}\backslash S$. c(S) is also known as cut size of
$S$.

  * •

Edge Expansion Difference ($\Delta EE$): The edge expansion ($EE$) is defined
as the ratio of cut size and minimum of the cardinalities of the two
communities $S$ and $\mathcal{V}\backslash S$. We consider the edge expansion
difference ($\Delta EE$) as:

$\Delta EE=EE(S,\mathcal{V})-EE(S^{\prime},\mathcal{V})$ (17)

where,

$EE(S,\mathcal{V})=\frac{c(S)}{\min{\left(|S|,|\mathcal{V}\backslash
S|\right)}}$ (18)

denotes the edge expansion of the community $S$.

  * •

Conductance Difference ($\Delta C$): Conductance ($C(S)$) is the fraction of
edge volume that points outside the community $S$, where edge volume is
defined as the sum of node degrees of the nodes in the community. We consider
the conductance difference ($\Delta C$) as a property:

$\Delta C=C(S)-C(S^{\prime})$ (19)

where,

$C(S)=\frac{c(S)}{\left(2m(S)+c(S)\right)}$ (20)

denotes the conductance of the community $S$.

  * •

Volume Difference ($\Delta V$): The volume ($V(S)$) of a community $S$, is the
sum of (out-)degrees of the nodes in $S$ in case the graph is directed, or
only the sum of degrees of the nodes in $S$, if the graph is undirected. For
our case the latter holds. We consider the volume difference ($\Delta V$) as a
property:

$\Delta V=V(S)-V(S^{\prime})$ (21)

where,

$V(S)=\left(2m(S)+c(S)\right),$ (22)

denotes the volume of the community $S$.

  * •

Normalized Cut Size Difference: The normalized cut size is the cut size
multiplied with the reciprocal of the volumes of the two sets $S$ and
$\mathcal{V}\backslash S$. We consider the normalized cut size difference
($\Delta NCS$) as a property:

$\Delta NCS=NCS(S,\mathcal{V})-NCS(S^{\prime},\mathcal{V})$ (23)

where,

$NCS(S,\mathcal{V})=c(S)\left(\frac{1}{2m(S)+c(S)}+\frac{1}{2(|\mathcal{E}|+m(S))-c(S)}\right),$
(24)

denotes the normalized cut size of the community $S$.

Property | Correlation |  $p$-value
---|---|---
Feature similarity | $\mathbf{-0.20\pm 0.196}$ | $\mathbf{<0.001}$
Degree | $\mathbf{-0.15\pm 0.008}$ | $\mathbf{<0.001}$
Local Clustering Coefficient | $\mathbf{0.25\pm 0.004}$ | $\mathbf{<0.001}$
Reverse k-NN rank | $0.02\pm 0.008$ | 0.37
Edge Expansion Difference | $0.03\pm 0.014$ | 0.24
Conductance Difference | $0.01\pm 0.010$ | 0.65
Normalized-Cut Size Difference | $0.01\pm 0.010$ | 0.67
Volume Difference | $0.02\pm 0.017$ | 0.37

Table 6: Spearman’s Rank Correlation of various node properties with
neighborhood distortion along with their statistical significance.

Table 6 shows the Spearman’s Rank Correlation of these properties with the
neighborhood distortion measure. As we have already seen in Section 4.4, only
Degree, Feature Similarity, and Local Clustering Coefficient show significant
correlations and the possible reasons for them. Now, it is important to note
that the lack of significance in the correlation with the community-based
metrics indicates that the neighborhood distortion may not necessarily bring a
difference in the local community around the target node, as defined by these
community based measures. In particular, the perturbation is not large enough
to cause a significant change in the entire neighborhood community but only
enough to cause a change in the inference for the downstream task.
Additionally, the low magnitude of significant correlation with the three
parameters (i.e., degree, feature similarity, and local clustering
coefficient) further strengthens the claim that the distortion is difficult to
detect with standard attack detection techniques [survey].

###  I Reproducibility and Code-base

The code is made available at https://github.com/idea-iitd/TANDIS.


Manuscript

# Hyers–Ulam stability of derivations
and linear functions

Zoltán Boros  Department of Analysis
Institute of Mathematics
University of Debrecen
P. O. Box: 12.
Debrecen
H–4010
Hungary<EMAIL_ADDRESS>and  Eszter Gselmann  Department of Analysis
Institute of Mathematics
University of Debrecen
P. O. Box: 12.
Debrecen
H–4010
Hungary<EMAIL_ADDRESS>
###### Key words and phrases:

Stability, derivation, linear function

###### 1991 Mathematics Subject Classification:

39B82, 39B72

This research has been supported by the Hungarian Scientific Research Fund
(OTKA) grants NK 68040 and K 62316)

##  1\. Introduction and preliminaries

In this paper $\mathbb{N},\mathbb{Z},\mathbb{Q}$ and $\mathbb{R}$ denotes the
set of the natural (positive integer), the integer, the rational and the real
numbers, respectively.

The stability theory of functional equations basically deals with the
following question: Is is true that an ’approximate’ solution of a functional
equation ’can be approximated’ by a solution of the functional equation in
question? This problem was raised by S. M. Ulam (see [13]) and answered
(affirmatively) by D. H. Hyers concerning the additive Cauchy equation see
[5]. Since 1941 this result has been extended and generalized in several ways,
see e.g., Hyers–Isac–Rassias [6] and the references therein. Of course, the
question of stability can be raised not only concerning the Cauchy equation
but also in connection with other equations.

The aim of this paper is to examine the stability of a system of equations
that defines derivations as well as linear functions.

######  Definition 1.1.

A function $f:\mathbb{R}\rightarrow\mathbb{R}$ is called an _additive_
function if,

(1.1) $f(x+y)=f(x)+f(y)$

holds for all $x,y\in\mathbb{R}$. Furthermore, we say that an additive
function $f:\mathbb{R}\rightarrow\mathbb{R}$ is a _derivation_ if

(1.2) $f(xy)=xf(y)+yf(x)$

is fulfilled for all $x,y\in\mathbb{R}$.

¿From (1.2) $f(1)=0$ follows, whence every derivation vanishes at the
rationals. Furthermore, it is known that there exist not identically zero
derivations, see Kuczma [9].

It is easy to see from the above definition that every derivation
$f:\mathbb{R}\rightarrow\mathbb{R}$ satisfies the equation

(1.3)
$f(x^{k})=kx^{k-1}f(x)\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

for arbitrarily fixed $k\in\mathbb{Z}\setminus\left\\{0\right\\}$.
Furthermore, the converse is also true, in the following sense: if
$k\in\mathbb{Z}\setminus\left\\{0,1\right\\}$ is fixed and an additive
function $f:\mathbb{R}\rightarrow\mathbb{R}$ satisfies (1.3), then $f$ is a
derivation, see e.g., Kurepa [10] and Kannappan–Kurepa [8].

Motivated by a problem of I. Halperin (1963), Jurkat [7] and independently,
Kurepa [10] proved that every additive function
$f:\mathbb{R}\rightarrow\mathbb{R}$ satisfying

$f\left(\frac{1}{x}\right)=\frac{1}{x^{2}}f(x)\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

has to be linear.

In [12] A. Nishiyama and S. Horinouchi investigated additive functions
$f:\mathbb{R}\rightarrow\mathbb{R}$ satisfying the additional equation

(1.4)
$f(x^{n})=cx^{k}f(x^{m})\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right),$

where $c\in\mathbb{R}$ and $n,m,k\in\mathbb{Z}$ are arbitrarily fixed. This
approach is obviously the common generalization of the above mentioned
results. In the second part of the paper we will deal with the stability of
this last system of functional equations. Our main results could serve as a
generalization of the theorems of [12]. However, the aim of the paper is not
only to prove a stability theorem. In the so–called mixed theory of
information it is usual to consider a functional equation that characterizes
the inset measure of information, see Maksa [11]. While solving this equation
one obtains an additive function satisfying also the equation

$f\left(\frac{1}{x}\right)=-\frac{1}{x^{2}}f(x)\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right).$

Clearly, this is a particular case of equation (1.3) with $k=-1\,$. Therefore
it is rather natural to expect that the investigation of the stability of the
above mentioned equation for the inset measure of information should be
preceded by the verification of the stability of the characterization of
derivations by Kannappan and Kurepa. Thus our results can be applied when we
investigate the stability of a functional equation characterizing the inset
measure of information.

We remark that in Badora [1], a stability problem for the system (1.1)-(1.2)
concerning mappings between Banach algebras was solved. In this paper we
replace the second equation (1.2) with an equation in a single variable,
namely, with a member of the family of equations in the form (1.4). On the
other hand, we restrict our considerations to real functions.

In what follows we will list some preliminary definitions and statements that
will be used during the proof of our main result. These can be found e.g., in
Kuczma [9].

Let $p\in\mathbb{N}$ . A function $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ is
called _$p$ –additive_ if, for every $i\in\\{\,1\,,\,2\,,\,\dots\,,\,p\,\\}$
and for every $x_{1},\ldots,x_{p},y_{i}\in\mathbb{R}$

$f\left(x_{1},\ldots,x_{i-1},x_{i}+y_{i},x_{i+1},\ldots,x_{p}\right)\\\
=f\left(x_{1},\ldots,x_{i-1},x_{i},x_{i+1},\ldots,x_{p}\right)+f\left(x_{1},\ldots,x_{i-1},y_{i},x_{i+1},\ldots,x_{p}\right),$

i.e., $f$ is additive in each of its variables $x_{i}\in\mathbb{R}$,
$i=1,\ldots,p$. A $2$–additive function is called _biadditive._

######  Theorem 1.2.

Let $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a continuous $p$–additive
function. Then there exists a constant $c\in\mathbb{R}$ such that

$f(x_{1}\,,\,x_{2}\,,\,\ldots\,,\,x_{p})=cx_{1}x_{2}\cdots x_{p}$

for all $x_{1}\,,\,x_{2}\,,\,\ldots\,,\,x_{p}\in\mathbb{R}$ .

######  Theorem 1.3.

Let $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a $p$–additive function,
bounded above, or below on a set $T\subset\mathbb{R}^{p}$, which has positive
Lebesgue–measure. Then $f$ is continuous.

Given a function $F:\mathbb{R}^{p}\rightarrow\mathbb{R}$, by the
_diagonalization (or trace)_ of $F$ we understand the function
$f:\mathbb{R}\rightarrow\mathbb{R}$ arising from $F$ by putting all the
variables (from $\mathbb{R}$) equal:

$f(x)=F(x,\ldots,x).\quad\left(x\in\mathbb{R}\right)$

We will also refer to the definition of _the difference operator_ $\Delta_{h}$
with the span $h\in\mathbb{R}$, which is given for a function
$f:\mathbb{R}\rightarrow\mathbb{R}$ by the formula

$\Delta_{h}f(x)=f(x+h)-f(x)\quad\left(x\in\mathbb{R}\right).$

The superposition of several difference operators will be denoted shortly by

$\Delta_{h_{1}h_{2}\ldots
h_{p}}f=\Delta_{h_{1}}\Delta_{h_{2}}\ldots\Delta_{h_{p}}f,$

where $p\in\mathbb{N}$ and $h_{1},h_{2},\ldots,h_{p}\in\mathbb{R}$.

######  Lemma 1.4.

Let $F:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be a symmetric $p$–additive
function, and let $f:\mathbb{R}\rightarrow\mathbb{R}$ be the diagonalization
of $F$. For every $n\in\mathbb{N}$, $n\geq p$ and for every
$x,h_{1},\ldots,h_{n}\in\mathbb{R}$ we have

$\Delta_{h_{1}\ldots
h_{n}}f(x)=\left\\{\begin{array}[]{lcl}p!F\left(h_{1},\ldots,h_{p}\right),&\text{if}&n=p\\\
0,&\text{if}&n\geq p.\end{array}\right.$

We remark that according to Theorem 15.1.1 in Kuczma [9], we have for all
$p\in\mathbb{N}$,

$\Delta_{h_{1}\ldots
h_{p}}f(x)=\sum_{\varepsilon_{1},\ldots,\varepsilon_{p}=0}^{1}(-1)^{p-(\varepsilon_{1}+\ldots+\varepsilon_{p})}f\left(x+\varepsilon_{1}h_{1}+\ldots+\varepsilon_{p}h_{p}\right).$

We will also make use of a result of Kannappan–Kurepa [8].

######  Theorem 1.5.

Let $f,g:\mathbb{R}\rightarrow\mathbb{R}$ be additive functions and
$n,m\in\mathbb{Z}\setminus\left\\{0\right\\}$, $n\neq m$. Suppose that

$f(x^{n})=x^{n-m}g(x^{m})$

holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$. Then the functions
$F,G:\mathbb{R}\rightarrow\mathbb{R}$ defined by

$F(x)=f(x)-f(1)x\quad\text{and}\quad
G(x)=g(x)-g(1)x\quad\left(x\in\mathbb{R}\right)$

are derivations and $nF(x)=mG(x)$ is fulfilled for all $x\in\mathbb{R}$.

##  2\. Inequalities for additive functions

######  Lemma 2.1.

Let $f,g:\mathbb{R}\rightarrow\mathbb{R}$ be additive functions,
$n,m\in\mathbb{Z}\setminus\left\\{0\right\\}$, $n\neq m$ suppose furthermore
that either $n=-m$ or $\mathrm{sign}(n)=\mathrm{sign}(m)$ and assume that
there exists an interval $I\subset\mathbb{R}$ with positive length such that

(2.1) $\left|f(x^{n})-x^{n-m}g(x^{m})\right|\leq K$

holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$ with a certain
$K\in\mathbb{R}$. Then there exist derivations
$F,G:\mathbb{R}\rightarrow\mathbb{R}$ such that $nF(x)=mG(x)$
$\left(x\in\mathbb{R}\right)$ and

(2.2) $f(x)=F(x)+f(1)x\quad\left(x\in\mathbb{R}\right),$ (2.3)
$g(x)=G(x)+g(1)x\quad\left(x\in\mathbb{R}\right).$

###### Proof.

Firstly, we will show that inequality (2.1) implies that there exists
$L\in\mathbb{R}$ so that

(2.4) $\left|f(x^{n})-x^{n-m}g(x^{m})\right|\leq L\left|x\right|^{n}$

is fulfilled for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$.

Let $]a,b[\subset I$. Since the rationals are dense in $\mathbb{R}$, for every
$x\in\mathbb{R}\setminus\left\\{0\right\\}$ we can find $r(x)\in\mathbb{Q}$ (a
rational number depending only on $x$) such that $a<r(x)x<b$. If we replace
$x$ by $r(x)x$ in (2.1), we obtain that

$\left|f(x^{n})-x^{n-m}g(x^{m})\right|\leq K\left|r(x)\right|^{-n},$

where we used the fact that every additive function is
$\mathbb{Q}$–homogeneous. Since $a<r(x)x<b$,

$\min\left\\{|a|,|b|\right\\}<r(x)x<\max\left\\{|a|,|b|\right\\}.$

In case $n>0$, we obtain from this that

$\left(\min\left\\{|a|,|b|\right\\}\right)^{-n}|x|^{n}>|r(x)|^{-n}$

and in case $n<0$ we get that

$\left(\max\left\\{|a|,|b|\right\\}\right)^{-n}|x|^{n}>|r(x)|^{-n}.$

Therefore, if we define

$L=\left\\{\begin{array}[]{lcl}\left(\min\left\\{|a|,|b|\right\\}\right)^{-n}K,&\text{if}&n>0\\\
\left(\max\left\\{|a|,|b|\right\\}\right)^{-n}K,&\text{if}&n<0\end{array}\right.$

we get inequality (2.4).

At this point of the proof we have to distinguish several cases. First suppose
that $n,m>0$. Without the loss of generality $n>m$ can be assumed.

Define the function $H$ on $\mathbb{R}^{n}$ by

$H(x_{1},\ldots,x_{n})=f(x_{1}\cdot\ldots\cdot x_{n})\\\
-\frac{1}{n}x_{1}\cdot\ldots\cdot x_{n-m}g\left(x_{n-m+1}\cdot\ldots\cdot
x_{n}\right)-\frac{1}{n}x_{2}\cdot\ldots\cdot
x_{n-m+1}g\left(x_{n-m+2},\cdot\ldots\cdot x_{n}x_{1}\right)-\\\
\ldots-\frac{1}{n}x_{n}x_{1}\cdot\ldots\cdot
x_{n-m-1}g\left(x_{n-m}\cdot\ldots\cdot x_{2}\right).$

Due to the additivity of the functions $f$ and $g$, the function $H$ is a
symmetric and $n$–additive function, and its trace

$H(x,\ldots,x)=f(x^{n})-x^{n-m}g(x^{m}).\quad\left(x\in\mathbb{R}\right)$

In view of inequality (2.1), this yields that

$\left|H(x,\ldots,x)\right|=\left|f(x^{n})-x^{n-m}g(x^{m})\right|\leq
L|x^{n}|,\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

that is, the trace of the function $H$ can be dominated by the term
$L|x^{n}|$. On the other hand, Lemma 1.4.states that the function $H$ is
uniquely determined by its trace via the formula

$H(h_{1},\ldots,h_{n})=\frac{1}{n!}\Delta_{h_{1}\ldots
h_{n}}H(x,\ldots,x).\left(x,h_{1},\ldots,h_{n}\in\mathbb{R}\right)$

This yields that the function $H$ is bounded on a subset of $\mathbb{R}^{n}$
which has positive Lebesgue–measure. Thus, by Theorem 1.3., the function $H$
is continuous on $\mathbb{R}^{n}$. Therefore, especially,

$H(x,\ldots,x)=cx^{n}$

holds for all $x\in\mathbb{R}$ with a certain $c\in\mathbb{R}$. ¿From this we
get that $H(1,\ldots,1)=c$, on the other hand by the definition of the
function $H$, $H(1,\ldots,1)=f(1)-g(1)$ follows. All in all,

(2.5)
$\left(f(1)-g(1)\right)x^{n}=H(x,\ldots,x)=f(x^{n})-x^{n-m}g(x^{m}).\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

Define the functions $F,G:\mathbb{R}\rightarrow\mathbb{R}$ by

$F(x)=f(x)-f(1)x\quad\text{and}\quad
G(x)=g(x)-g(1)x,\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

then from (2.5) we get that

$F(x^{n})=x^{n-m}G(x^{m})$

for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$. Using Theorem 1.5., this
yields that the functions $F$ and $G$ are derivations and $nF(x)=mG(x)$ holds
for all $x\in\mathbb{R}$. This means that equations (2.2) and (2.3) hold in
case $n,m>0$.

Secondly assume that $n,m<0$. In this case let us replace $x$ by $\frac{1}{x}$
in inequality (2.4) to obtain

$\left|f(x^{-n})-x^{(-n)-(-m)}g(x^{-m})\right|\leq
L|x|^{-n}.\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

Since $-n$ and $-m$ are positive integers, the results of the previous case
can be applied. Therefore there exist derivations
$F,G:\mathbb{R}\rightarrow\mathbb{R}$ so that $nF(x)=mG(x)$ $(x\in\mathbb{R})$
and

$f(x)=F(x)+f(1)x$

and

$g(x)=G(x)+g(1)x$

holds for all $x\in\mathbb{R}$.

Suppose now that $n=-m$. Then inequality (2.1) yields that

(2.6) $\left|f(x^{-m})-x^{-2m}g(x^{m})\right|\leq L|x^{-m}|$

holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$. If we replace $x$
by $x^{1/m}$ $(x>0)$ then inequality (2.6) yields that

(2.7)
$\left|f\left(\frac{1}{x}\right)-\frac{1}{x^{2}}g(x)\right|\leq\frac{L}{|x|}$

is fulfilled for all $x>0$. Replace in this inequality $x$ by $x(x+1)$, then

$\left|f\left(\frac{1}{x(x+1)}\right)-\frac{1}{x^{2}(x+1)^{2}}g(x(x+1))\right|\leq\frac{L}{|x(x+1)|}$

is fulfilled for all $x>0$. After using the additivity of the function f,

$\left|f\left(\frac{1}{x}\right)-f\left(\frac{1}{x+1}\right)-\frac{1}{x^{2}(x+1)^{2}}g(x(x+1))\right|\leq\frac{L}{|x(x+1)|}\quad\left(x>0\right)$

Using the triangle inequality, we obtain that

$\left|\frac{1}{x^{2}}g(x)-\frac{1}{(x+1)^{2}}g(x+1)-\frac{1}{x^{2}(x+1)^{2}}g(x^{2}+x)\right|\\\
\leq\left|f\left(\frac{1}{x}\right)-\frac{1}{x^{2}}g(x)\right|+\left|f\left(\frac{1}{x+1}\right)-\frac{1}{(x+1)^{2}}g(x+1)\right|\\\
+\left|f\left(\frac{1}{x(x+1)}\right)-\frac{1}{x^{2}(x+1)^{2}}g(x(x+1))\right|\\\
\leq\frac{L}{|x|}+\frac{L}{|x+1|}+\frac{L}{|x(x+1)|}$

is satisfied for all $x>0$. Due to the additivity of the function $g$, after
rearranging this inequality, one can get

$\left|2xg(x)-g(x^{2})\right|\leq L|x|+L|x+1|+L|x(x+1)|+|x^{2}g(1)|$

for all $x>0$. At this point the results of the first part of the proof can be
used to derive that there exists a derivation
$G:\mathbb{R}\rightarrow\mathbb{R}$ such that

$g(x)=G(x)+g(1)x.\quad\left(x\in\mathbb{R}\right)$

In view of inequality (2.5), this yields that

$\left|f\left(\frac{1}{x}\right)-\frac{1}{x^{2}}G(x)-\frac{1}{x^{2}}g(1)x\right|\leq\frac{L}{|x|}$

is fulfilled for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$. Since the
function $G$ is a derivation, $-\frac{1}{x^{2}}G(x)=G\left(\frac{1}{x}\right)$
holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$, thus

$\left|f\left(\frac{1}{x}\right)+G\left(\frac{1}{x}\right)-\frac{g(1)}{x}\right|\leq\frac{L}{|x|},\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

or if we replace $x$ by $\frac{1}{x}$,

$\left|f(x)+G(x)-g(1)x\right|\leq L|x|.\quad\left(x\in\mathbb{R}\right)$

The functions $f$ and $G$ are additive, therefore the function
$f(x)+G(x)-g(1)x$ is also additive, and this inequality means that this
additive function is bounded on an interval which has positive length. Thus
this function is linear, that is

$f(x)+G(x)-g(1)x=cx$

holds for all $x\in\mathbb{R}$ with a certain constant $c$. With the
substitution $x=1$, we get however that $c=f(1)-g(1)$. Therefore

$f(x)=-G(x)+f(1)x$

for all $x\in\mathbb{R}$, that is, equations (2.2) and (2.3) are satisfied in
this case, too. ∎

######  Remark 2.2.

Our proof was not appropriate in case $\mathrm{sign}(n)\neq\mathrm{sign}(m)$
and $n\neq-m$. We remark that if the functions in the previous lemma fulfill
the condition $\kappa f(x)=g(x)$ for all $x\in\mathbb{R}$ with a real constant
$\kappa$, then we do not have to make any restrictions on the values of $n$
and $m$ and we can prove the following statement.

######  Lemma 2.3.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be an additive function,
$\kappa\in\mathbb{R}$ $n,m\in\mathbb{Z}\setminus\left\\{0,1\right\\}$, $n\neq
m$ and assume that there exists an interval $I\subset\mathbb{R}$ such that

(2.8) $\left|f(x^{n})-\kappa x^{n-m}f(x^{m})\right|\leq K$

holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$ with a certain
$K\in\mathbb{R}$. Then there exists a derivation
$F:\mathbb{R}\rightarrow\mathbb{R}$ for which $(n-\kappa m)F(x)=0$ and

$f(x)=F(x)+f(1)x$

holds for all $x\in\mathbb{R}$.

###### Proof.

In view of Lemma 2.1. we have to only deal with the case
$\mathrm{sign}(n)\neq\mathrm{sign}(m)$ and $n\neq-m$. Furthermore, due the
proof the previous lemma, inequality (2.8) is equivalent to the following
inequality

$\left|f(x^{n})-\kappa x^{n-m}f(x^{m})\right|\leq L|x^{n}|$

for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$, where $L$ is a certain
real constant. Let us substitute $x^{n}$ in place of $x$ into this inequality,

$\left|f(x^{n^{2}})-\kappa x^{n(n-m)}f(x^{nm})\right|\leq
L|x^{n^{2}}|.\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

Additionally, the above inequality with the substitution $x^{m}$ yields

$\left|f(x^{nm})-\kappa x^{m(n-m)}f(x^{m^{2}})\right|\leq
L|x^{nm}|.\quad\left(x\in\mathbb{R}\setminus\left\\{0\right\\}\right)$

This last two inequalities and the triangle inequality imply that

$\left|f\left(x^{n^{2}}\right)-\kappa^{2}x^{n^{2}-m^{2}}f\left(x^{m^{2}}\right)\right|\\\
\leq\left|f(x^{n^{2}})-\kappa x^{n(n-m)}f(x^{nm})\right|+\left|\kappa
x^{n(n-m)}\right|\cdot\left|f(x^{nm})-\kappa x^{m(n-m)}f(x^{m^{2}})\right|\\\
=L\left|x^{n^{2}}\right|+L\left|\kappa
x^{n(n-m)}x^{nm}\right|=L\left(1+\left|\kappa\right|\right)\cdot\left|x^{n^{2}}\right|$

holds for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$ . Let us observe
that $n^{2},m^{2}>0$ and the results of Lemma 2.1. can be applied (with the
choice $g(x)=\kappa f(x)$) to obtain that

$f(x)=F(x)+f(1)x$

holds for all $x\in\mathbb{R}$, where $F:\mathbb{R}\rightarrow\mathbb{R}$ is a
derivation which also satisfies $(n-\kappa m)F(x)=0$ for arbitrary
$x\in\mathbb{R}$. ∎

¿From this lemma the following statement can be concluded immediately.

######  Corollary 2.4.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be an additive function and
$r\in\mathbb{Q}\setminus\left\\{0,1\right\\}$. Assume that there exists an
interval $I\subset\mathbb{R}$ with positive length such that

$\left|f\left(x^{r}\right)-rx^{r-1}f(x)\right|\leq K$

holds for all $x\in I$ with a certain $K\in\mathbb{R}$. Then there exists a
derivation $F:\mathbb{R}\rightarrow\mathbb{R}$ such that

$f(x)=F(x)+f(1)x$

is fulfilled for all $x\in\mathbb{R}$.

##  3\. Stability of derivations and linear functions

As a starting point of the proof of the main result of this section the
theorem of Hyers will be used. Originally this statement was formulated in
terms of functions that are acting between Banach spaces, see Hyers [5].
However, we will use this theorem only in the particular case when the domain
and the range are the set of reals. In this setting the proposition of Hyers’
theorem is the following.

######  Theorem 3.1.

Let $\varepsilon\geq 0$ and suppose that the function
$f:\mathbb{R}\rightarrow\mathbb{R}$ fulfills the inequality

$\left|f(x+y)-f(x)-f(y)\right|\leq\varepsilon$

for all $x\in\mathbb{R}$. Then there exists an additive function
$a:\mathbb{R}\rightarrow\mathbb{R}$ such that

$\left|f(x)-a(x)\right|\leq\varepsilon$

holds for arbitrary $x\in\mathbb{R}$.

Applying this theorem and our results in the previous section, we can
establish our main result.

######  Theorem 3.2.

Let $\varepsilon_{1},\varepsilon_{2}\geq 0$, $\kappa\in\mathbb{R}$,
$n,m\in\mathbb{Z}\setminus\left\\{0\right\\}$, $n\neq m$ and assume that the
function $f:\mathbb{R}\rightarrow\mathbb{R}$ fulfills the inequalities

(3.1) $\left|f(x+y)-f(x)-f(y)\right|\leq\varepsilon_{1}$ (3.2)
$\left|f(x^{n})-\kappa x^{n-m}f(x^{m})\right|\leq\varepsilon_{2}$

for all $x\in\mathbb{R}\setminus\left\\{0\right\\}$. Then there exist a
derivation $F:\mathbb{R}\rightarrow\mathbb{R}$ and $\lambda\in\mathbb{R}$ such
that

$(n-\kappa m)F(x)=0$

and

(3.3) $\left|f(x)-\left[F(x)+\lambda x\right]\right|\leq\varepsilon_{1}$

are satisfied for all $x\in\mathbb{R}$.

###### Proof.

Due the theorem of Hyers, inequality (3.1) immediately implies that there
exists an additive function $a:\mathbb{R}\rightarrow\mathbb{R}$ satisfying

(3.4) $\left|f(x)-a(x)\right|\leq\varepsilon_{1}$

for all $x\in\mathbb{R}$. In view of inequality (3.2) this implies that

$\left|a(x^{n})-\kappa x^{n-m}a(x^{m})\right|\\\
\leq\left|a(x^{n})-f(x^{n})\right|+\left|\kappa
x^{n-m}\right|\cdot\left|a(x^{m})-f(x^{m})\right|+\left|f(x^{n})-\kappa
x^{n-m}f(x^{m})\right|\\\ \leq\varepsilon_{1}+\left|\kappa
x^{n-m}\right|\varepsilon_{1}+\varepsilon_{2}=\left(1+\left|\kappa
x^{n-m}\right|\right)\varepsilon_{1}+\varepsilon_{2}$

is fulfilled for all $x\in\mathbb{R}\setminus\left\\{0\right\\}\,$. Thus the
expression $\left|a(x^{n})-\kappa x^{n-m}a(x^{m})\right|$ is bounded on a real
interval with non-void interior. Therefore Lemma 2.3. yields that there exists
a derivation $F:\mathbb{R}\rightarrow\mathbb{R}$ such that $(n-\kappa
m)F(x)=0$ and

$a(x)=F(x)+a(1)x$

holds for all $x\in\mathbb{R}$. This, together with (3.4), implies (3.3) with
$\lambda=a(1)\,$. ∎

Let us note that our result serves as a stability theorem for linear functions
if $n\neq\kappa m\,$.

## References

  * [1] R. Badora, _On approximate derivations_ , Math. Inequal. Appl. 9 (2006), no. 1 167–173.
  * [2] Z. Boros, P. Erdei, _A conditional equation for additive functions_ , Aequationes Math. 70 (2005), no. 3, 309–313.
  * [3] Z. Boros, _Conditional equations for quadratic and additive functions_ , manuscript, 2008.
  * [4] I. Halperin _Problem 448_ , Colloq. Math., 11 (1963), 140\.
  * [5] D. H. Hyers, _On the stability of the linear functional equations_ , Proc. Nat. Acad. Sci. USA 27 (1941) 222–224.
  * [6] D. H. Hyers, G. Isac, Th. M. Rassias, _Stability of functional equations in several variables_ , Progress in Nonlinear Differential Equations and their Applications 34 Birkhäuser Boston, Inc., Boston, MA, 1998\.
  * [7] W. B. Jurkat _On Cauchy’s functional equation_ , Proc. Amer. Math. Soc. 16 (1965) 683–686.
  * [8] Pl. Kannappan, S. Kurepa _Some relations between additive functions. I_ Aequationes Math. 4 (1970) 163–175.
  * [9] M. Kuczma _An Introduction to the Theory of Functional Equations and Inequalities. Cauchy’s equation and Jensen’s inequality_ , Uniwersytet Ślaski, Katowice; Państwowe Wydawnictwo Naukowe (PWN), Warsaw, 1985\.
  * [10] S. Kurepa _The Cauchy functional equation and scalar product in vector spaces_ , Glasnik Mat.-Fiz. Astronom. Ser. II 19 (1964) 23–36.
  * [11] Gy. Maksa, _The general solution of a functional equation related to the mixed theory of information_ , Aequationes Math. 22 (1981), 90–96
  * [12] A. Nishiyama, S. Horinouchi _On a system of functional equations_ , Aequationes Math. 1 (1968) 1–5.
  * [13] S. M. Ulam _Problems in modern mathematics_ , Science Editions John Wiley & Sons, Inc., New York, 1964\.