Strategic Classification with Graph Neural Networks
Authors: Itay Eilat
Ben Finkelshtein
Chaim Baskin
Nir Rosenfeld
Venue: ICLR 2023 poster (2023)
Keywords: Strategic classification
Graph Neural Networks
Robust classification

Abstract: Strategic classification studies learning in settings where users can modify their features to obtain favorable predictions. Most current works focus on simple classifiers that trigger independent user responses. Here we examine the implications of learning with more elaborate models that break the independence assumption. Motivated by the idea that applications of strategic classification are often social in nature, we focus on graph neural networks, which make use of social relations between users to improve predictions. Using a graph for learning introduces inter-user dependencies in prediction; our key point is that strategic users can exploit these to promote their goals. As we show through analysis and simulation, this can work either against the system---or for it. Based on this, we propose a differentiable framework for strategically-robust learning of graph-based classifiers. Experiments on several real networked datasets demonstrate the utility of our approach.

Published as a conference paper at ICLR 2023
STRATEGIC CLASSIFICATION WITH GRAPH NEURAL NETWORKS
Itay Eilat', Ben Finkelshtein", Chaim Baskin, Nir Rosenfeld Technion - Israel Institute of Technology
(itayei 1at, benfin) ecampus. techn i on. ac. [chaimbaskin, nirr) 0 8cs. techni on ac. il
ABSTRACT
Strategic classification studies learning in settings where users can modify their features to obtain favorable predictions. Most current works focus on simple classi- fiers that trigger independent user responses. Here we examine the implications of learning with more elaborate models that break the independence assumption. Motivated by the idea that applications of strategic classification are often social nature, we focus graph neural networks, which make use of social relations be- tween users to improve predictions. Using a graph for learning introduces inter-user dependencies in prediction; our key point is that strategic users exploit these to promote their own goals. As we show through analysis and simulation, this can work either against the system- for it. Based this, propose differentiable framework for strategically learning of graph-based classifiers. Experiments several real networked datasets demonstrate the utility of our approach.
INTRODUCTION
Machine learning is increasingly being used to inform decisions about humans. But when users of a system stand to gain from certain predictive outcomes, they may be prone to "game" the system by strategically modifying their features (at some cost). The literature on strategic classification (Brückner & Scheffer, 2011; I; Hardt et al., 2016) studies learning in this setting, with emphasis on how to learn classifiers that are robust to strategic user behavior. The idea that decision rule applies broadly and across many domains, from hiring, admissions, and scholarships to loan approval, insurance, welfare benefits, and medical eligibility (McCrary, 2008; Almond et al., 2010; Camacho & Conover, 201 I; Lee & Lemieux, 2010). This, along with its clean formulation as a learning problem, have made strategic classification the target of much recent interest (Sundaram et al., 2021; :; Zhang & Conitzer, 2021; 1; Levanon & Rosenfeld, 2021; Ghalme et al., 2021; Jagadeesan al., 2021; Zrnic et al., 2021; Estornell al., 2021: Lechner & Urner, 2021; Harris et al., 2021; Levanon & Rosenfeld, 2022; Liu et al., 2022; Ahmadi et al., 2022; Barsotti et al., 2022a).
may respond to
But despite these advances, most works in strategic classification remain to follow the original problem formulation in assuming independence across users responses. From a technical perspective, this assumption greatly simplifies the learning task, as allows the classifier consider each user's response in isolation: user behavior is modeled via response mapping (z) determining how users modify their features æ in response to the classifier h, and learning aims to find an for which y hx)) Intuitively, user will modify her features if this 'moves' her across the decision boundary, as long as this is worthwhile (i.e., gains from prediction exceed modification costs). Knowing A allows the system anticipate user responses and learn h that is robust.
For a wide range of settings, lcarning under independent user responses has been shown to be theoretically possible (Hardt et al., 2016; Zhang & Conitzer, 2021; Sundaram al., 2021) and practically feasible (Levanon & Rosenfeld, 2021; 2022). Unfortunately, once this assumption of independence is removed-resulte no longer hold. One reason is that current approaches can safely assume independence because the decision rules they consider induce independence: when predictions inform decisions for each user independently, users have no incentive account for the behavior of others. This limits the scope of predictive models to include only simple functions of single inputs.
"Equal contribution, alphahetical order

---

Published as a conference paper at ICLR 2023
In this paper, we aim to extend the literature on strategic classification to support richer learning paradigms that enable inter-dependent user responses, with particular focus on the domain of Graph Neural Networks (GNNs) (Monti et al., 2017; Wang et al., 2019; Bronstein et al., 2017; Hamilton et al., 2017). Generally, user responses can become dependent through the classifier if predictions for user rely also information regarding other users, i.e., if h((2)) is also a function of other zz. In this way, the affects of a user modifying her features via z + An (zz) can propagate to other users and affect their decisions (since h((;)) now relies on A (zy) rather than xy). For GNNS, this expresses through their relience on the graph. GNNs take as input a weighted graph whose nodes correspond to featurized examples, and whose edges indicate relations that are believed to be useful for prediction (e.g., if j-v indicates that yi yj is likely). In our case, nodes represent users, and edges represent social links. The conventional approach is to first embed nodes a way that depends on their neighbors' features, 04 = = Fpel(()), and then perform classification (typically linear) in embedded space, ú; sign(w" ())) Notice ÿ; depends on Iú, but also on all other Iy E (nei((); hence, in deciding how to respond, user i must also account for the strategic responses of her neighbors j E nei(t). We aim to establish the affects of such dependencies on learning.
As concrete example, consider Lenddo', company that provides credit scoring services to lending institutions. Lenddo specializes in consumer-focur focussd microlending for emerging economies, where many applicants lack credible financial records. To circumvent the need to rely historical records, Lenddo uses applicants' social connections, which are easier to obtain, as factor in their scoring system. 2 As an algorithmic approach for this task, GNNs are an adequate choice (Gao et al., 2021). Once loan decisions become dependent on social relations, the incentives for acting strategically change (Wei et al., 2016). To see how, consider that user who lies far to the negative side of the decision boundary (and so independently cannot cross) may benefit from the graph if her neighbors "pull" her embedding towards the decision boundary and close enough for her to cross. Conversely, the graph can also suppress strategic behavior, since neighbors can "hold back" nodes and prevent them from crossing. Whether this is helpful to the system or not depends on the true label of the node,
This presents a tradeoff: In general, graphs are useful if they are informative of labels in way that complements features; the many success stories of GNNs suggest that this is often the case (Zhou et al., 2020). But even if this holds sans strategic behavior- -nce introduced, graphs inadvertently create dependencies through user representations, which strategic users can exploit. Graphs therefore hold the potential to benefit the system, but also its users. Here we study the natural question: who does the graph help more? Through analysis and experimentation, we show that learning in a way that neglects account for strategic behavior not only jeopardizes performance, but becomes worse as reliance on the graph increases. In this sense, the graph becomes a vulnerability which users can utilize for their needs, turning from an asset the system-to to potential threat.
As a solution, we propose a practical approach to learning GNNs in strategic environments. We show that for a key neural architecture (SGC: Wu al. (2019)) and certain cost functions, graph-dependent user responses can be expressed as 'projectionlikke operator. This operator admits simple and differentiable closed form; with additional smoothing, this allows us to implement responses as a neural layer, and learn robust predictors h using gradient methods. Experiments on synthetic and real data (with simulated responses) demonstrate that our approach not only effectively accounts for strategic behavior, but in some cases, can harness the efforts of self-interested users to promote the system's 's goals. Our code is publicly available at:
1.1 RELATED WORK
Strategic classification. Since its introduction in Hardt et al. (2016) (and based on earlier formula- tions in Brückner & Scheffer (2009); Brückner al. (2012); Großhans et al. (2013)), the literature on strategic classification has been growing a rapid pace. Various aspects of learning have been studied, including: generalization behavior (Zhang & Conitzer, 2021; Sundaram et al., 2021: Ghalme et al.. 2021). algorithmic hardness (Hardt et al., 2016), practical optimization methods (Levanon & Rosenfeld, 2021; 2022), and societal implications (Milli et al., 2019; Hu et al., 2019; Chen et al., 2020; Levanon & Rosenfeld, 2021). Some efforts have been made to extend beyond the conventional user models, e.g., by adding noise (Jagadeesan et al., 2021), relying on partial information (Ghalme
hhttp://enndoeff.com see also http://wwwwwrred. wttp:ww.ww..coo//oooo 4/05//enddo-facceeeeeeee facebook/.
For discussion on ethics, see final section. For similar initiatives, see http:://enwwwiiiiiii.oorgre enddo.
2

---

Published as a conference paper at ICLR 2023
et al., 2021;
Bechavod et al., 2022), or considering broader user interests (Levanon & Rosenfeld, 2022); but these, as do the vast majority of other works, focus on linear classifiers and independent user responses. We study richer predictive model classes that lead to correlated user behavior.
Graph Neural Networks (GNNs). The use of graphs in learning has a long and rich history, and remains a highly active area of research (Wu et al., 2020). Here we cover small subset of relevant work. The key idea underlying most methods is to iteratively propagate and aggregate information from neighboring nodes. Modern approaches implement variations of this idea as differentiable neural architectures (Gori et al., 2005; Scarselli et al., 2008; Kipf & Welling, 2017; Gilmer et al., 2017). This allows to express more elaborate forms of propagation (Li et al., 2018; Alon & Yahav, 2021) and aggregation (Wu et al., 2019; Xu et al., 2019; Li et al., 2016), including attention based mechanisms (Veličković et al., 2018; Brody et al., 2022). Nonetheless, a key result by Wu et al. (2019) shows that, both theoretically and empirically, linear GNNs are also quite expressive.
Robustness of GNNs. As most other fields in deep learning. GNNs have been the target of recent inquiry as to their sensitivity to adversarial attacks. Common attacks include perturbing nodes, either in sets (Züggner et al., 2018; Zang et al., 2021) or individually (Finkelshtein et al., 2020). Attacks can be applied before training (Zügner& & Günnemann, 2019; Bojchevski & Günnemann, 2019; Li et al., 2021; Zhang & Zitmik, 2020) or at test-time (Szegedy et al., 2014; Goodfellow et al., 2015); our work corresponds to the latter. While there are connections between adversarial and strategic behavior (Sundaram et al., 2021), the key difference is that strategic hehavior is not a zero-sum game; in some cases, incentives can even align (Levanon & Rosenfeld, 2022). Thus, system-user relations become more nuanced, and provide a degree of freedom in learning that does not exist in adversarial settings.
2 LEARNING SETUP
Our setting includes n users, represented as nodes in a directed graph G = (V, E) with non-negative edge weights W = {ung J(.nEE Wiy 2 O. Each user i also described by a feature vector x; E I and binary label y e {+1}. We use x- = { to denote the set of features of all nodes other than i. Using the graph, our goal is to learn a classifier h that correctly predicts user labels. The challenge in our strategic setting is that inputs at test-time can strategically modified by users, in response to l and in way that depends on the graph and on other users (we describe this shortly). Denoting by x the (possibly modified) strategic response of i to ht, our learning objective is:
argmin
Σ Lys. Dt), REHf
fJ = hha);;
where H is the model class and L is a loss function (i.c., log-loss). Note that both predictions ÿ. and modified features xi can depend on G and the inductive graph learning setting, in which training is done on G. but testing is done on a different graph, G' (often G, G' are two disjoint components of larger graph). Our goal is therefore to learn a classifier that generalizes to other graphs in a way that is robust to strategic user behavior.
x², (possibly indirectly through h). We focus on
Graph-based learning. We consider linear graph-based classifiers these are linear classifiers that operate on linear, graph-dependent node embeddings, defined as:
ha x = s0 (( + b): <(Z;z_1) = Way +
Σ Wyyyy jfi
where o, = o(x;z_1) is node i's embedding.* 4 0 E Re and b E R are learned parameters, and Wi 0 are pairwise weights that depend on G and W. We refer to users j with Wi; & 0 as the embedding neighbors of i. A simple choice of weights is Wjj = Wye for (j. i) E E (and O otherwise), but different methods propose different ways to construct w;; here we adopt the weight scheme of Wu et al. (2019). We assume the weights 인 are predetermined, and aim to learn 0 and b in Eq. (1).
Our focus on linear GNNs stems from several factors. From the perspective of strategic classification, linear decision rules ensure that strategic responses are computationally tractable (see Eq. (4)). This is conventionally required, and most works remain in the linear regime, From the perspective of GNNs.
'The only exception we know of is Liu et al. (2022) who study strategic ranking, but do not consider learning. Note that embedding preserve the dimension of the original features.
3

---

Published as a conference paper at ICLR 2023
row
(A)
(D)
modified
emb. 0z.
emb. du.
(8)
UG
(E)
graph edge
move (w/o graph)
effective radius
(C)
Figure 1: Simple graphs, complex behavior. In all examples h& has b 0, and úigy unless otherwise noted. (A) Without the graph, does not move, but with j-xi, Φ2 is close enough to cross. (B) i can cross, but due to j-vi, must move beyond 0. (C) Without the graph, has D; 1, but due to j-+i, must move. (D) Without the graph would move, but with the graph-cannot. (E) Hitchhiker: i cannot move, but once j moves and crosses, Φ crosses for free. (F) Effective radii for various a.
linear architectures have been shown to match state-of-the-arr performance on multiple tasks (Wu al., 2019), implying sufficiently manifest the fundamental role of graphs. Thus, linear GNNs serve as minimal necessary step for bridging standard strategic classification and graph-based learning, in a way that captures the fundamental structure of the learning task in both domains. Nonetheless, as we show in Sec. 4, even for linear GNNs user responses can cause learning to be highly non-lineat
Strategic inputs. For the strategic aspects of our setting, we build on the popular formulation of Hardt et al. (2016). Users seek to be classified positively (i.e., have fA = 1), and to achieve this, are willing to modify their features (at some cost). Once the system has learned and published h,, test-time user can modify her features T, + x² in response to h. Modification costs are defined by a cost function c(x, x²) (known to all); here we focus mainly on 2-norm costs c(x, x²) = || - x (Levanon & Rosenfeld, 2022: Chen et al., 2020), but also discuss other costs (Brückner al., 2012: Levanon & Rosenfeld, 2021; Bechavod et al., 2022). User modifies her features (or "moves")
-1 but (=x)) 1) and is cost-effective (i.e., prediction gains exceed modification costs); for linear classifiers, this means crossing the decision boundary. Note that since [+1}, gains are at most luxx) - (xx) 2. Users therefore do not move to any x' whose cost c(2, x') exceeds a 'budget' of 2, and the maximal moving distance is d = 2.
this improves her prediction (i.e., if hxx,))
Distribution shift. One interpretation of strategic classification that user responses cause distribu- tion shift, since in aggregate, p(x') # p(r). Crucially, how the distribution changes depends on h, which implies that the system has some control over the test distribution p(z'), indirectly through user how users respond a special case of model-induced distribution shift (Miller et al., 2021; Maheshwari al., 2022). The unique aspect of our setting is that user responses are linked through their mutual dependence the graph. We next describe our model of user responses in detail.
STRATEGIC USER BEHAVIOR: MODEL AND ANALYSIS
Eq. (2) states that h classifies according to her embedding di. which in turn weighted sum of her features and those of her neighbors. To gain intuition as to the effects of the graph on user behavior, it will be convenient assume weights w are normalized that we can write:
Φ x( = (1- a,)x; + a²ē; for some ag [0, 1]
(3)
L.e., @; can be viewed an interpolation between I; and some point T; RR representing all other nodes, where the precise point along the line depends on a parameter that represents the influence of the graph (in a graph-free setting, a, 0). This reveals the dual effect a graph has on users: On the one hand, the graph limits the ability of user i to influence her own embedding, since any effort invested in modifying v; affects Φ; by most - or. But the flip side of this that an ax-portion of é, is fully determined by other users (as expressed in ãz); if they move, i's embedding also 'moves' for free. A user's "effective" movement radius is r, = d(1 - ax). Fig. 1 (F) shows this for varying ag
Thiis indeed the in several common approaches.
4

---

Published as a conference paper at ICLR 2023
3.1 STRATEGIC RESPONSES
Given that /t relies on the graph for predictions-hove should a user modify her features r; to obtain iJ = 1? In vanilla strategic classification (where h operates on each æ; independently). users are modeled as rational agents that respond to the classifier by maximizing their utility, i.e., play 1 = a h(z') - c(z,, z'), which is a best-response that results in immediate equilibrium (users have no incentive to move, and the system has no incentive to change h). In our graph-based setting, however, the dependence of OJ on all other users via h(ar;;; x=-)) makes this notion of best- response ill-defined, since the optimal x² can depend on others' strategic responses, ''_;, which are unknown to user at the time of decision (and may very well rely on x itself).
As feasible alternative, here we generalize the standard model by assuming that users play myopic best-response over a sequence of multiple update rounds. As we will see, this has direct connections to key ideas underlying graph neural networks. Denote the features of node at round t by z and set 22!0) Izz myopic best response means that at round f, each user i chooses x. to maximize her utility at time t according to the state of the game at time t - 1, i... assuming all other users play {x] (t) Jepes with costs accumulating over rounds. This defines a myopic response mapping:
A (2 x. k)
argmax hrgmax((r;;aa
c(x;, x') -
(4)
z'ER'
where at round updates are made (concurrently) via.;; ((+1) An (a/ - (1) with accumulating (t) costs Ki; (t-1) + c(x:' (1-1 (1) Kg
),,,,,, (0) = 0. Predictions for round t are j/ = h( (1) =x;-))
Eq. (4) naturally extends the standard best-response mapping (which is recovered when a; 0 Vi, and converges after one round). By adding a temporal dimension, the actions of users propagate over the graph and in time affect others. Nonetheless, even within single round, graph-induced dependencies can result in non-trivial behavior; some examples for f = 1 are given in Fig. (A-D).
3.2 ANALYSIS
We now give several results demonstrating basic properties of our response model and consequent dynamics, which shed light on how the graph differentially affects the system and its users.
Convergence. Although users are free to move at will, movement adheres to a certain useful pattern.
Proposition 1. For any h, if users move via Eq. (4), then for all i E [n]. 2 (t) A x at most once.
(t-1)
Proof. User will move only when: (i) she is currently classified negatively, h( (;-; -1, and (ii) there is some x' for which utility can improve, i.e., h(2'; x,- ) ((z,,x'' 1, which in our case occurs if h(x'; x;-)= x() = 1 and c( x') < 2 (since h maps to 1- 1J. Eq. (4) ensures that the modified x will be such that <(24; -x) lies exactly on the decision boundary of h; hence, 2f must be closer to the decision boundary (in Euclidian distance) than 2;. This means that any future moves of an (incoming) neighbor j can only push i further away from the decision boundary; hence, the prediction for remains positive, and she has no future incentive to move again.*
Hence, all users move at most once. The proof reveals a certain monotonicity principle: users always (weakly) benefit from any strategic movement of others. Convergence follows as an immediate result. Corollary 1. Myopic-best response dynamics converge for any h. (and after at most n rounds).
We will henceforth use z to denote the features of user at convergence (w..t. h), denoted T Tmax. Hitchhiking. When i moves, the embeddings of (outgoing) neighbors j who currently have úJ -1 also move closer to the decision boundary; thus, users who were initially too far to cross may be able to
'Note 'rational' here implies users are assumed to know h. As most works in the field, we also make this assumption; for the practically-inclined reader. note that (i) in some cases, there is reason to believe it may approximately hold (c.g., http://openschufa.de) and (ii) relaxing this assumption (and others) is ongoing community effort (Ghalme al., 2021; Jagadeesan al., 2021; Bechavod et al., 2022; Barsotti al., 2022b). In line with Hardt et al. (2016), we assume that if the value is zero then the user does not move.
Users moving only once ensures that cumulative costs are never larger than the final gain.
5

---

Published as a conference paper at ICLR 2023
do so at later rounds. In this sense, the dependencies across users introduced by the graph-dependent embeddings align user incentives, and promote an implicit form of cooperation. Interestingly, users can also obtain positive predictions without moving. We refer to such users 'hitchhikers'.
Proposition 2. There exist cases where v." -1 and doesn't 't move, but D.
(t+11) 1.
A simple example can be found in Figure 1 (E). Hitchhiking demonstrates how relying on the graph for classification can promote strategic behavior under a single response round.
Cascading behavior. Hitchhiking shows how the movement of user can flip the label of another, but the effects of this process are constrained to a single round. When considering multiple rounds, a single node can trigger 'domino effect' of moves that span the entire sequence.
Proposition 3. For any n, there exists graph where a single move triggers additional rounds. Proposition 4. For any n and k S n, there exists a graph where n users move at round k.
Proofs are constructive and modular, and rely on graphs that are predictively useful (Appendix A.2). Note also that graph diameter is not a mediating factor (Appendix E.3). Both results show that, through monotonicity, users also (weakly) benefit from additional rounds. This has concrete implications.
Corollary 2. In the worst case, the number of rounds until convergence is (2()). Corollary 3. In the worst case, Q2()) users move after Q))) rounds.
Thus, exactly account for user behavior, the system must correctly anticipate the strategic responses of users many rounds into the future, since a bulk of predictions may flip in the last round. Fortunately, these results also suggests that in some cases, blocking one node from crossing can prevent cascade of flips; thus, it may be worthwhile to 'sacrifice" certain predictions for collateral gains. This presents an interesting tradeoff in learning, encoded in the learning objective we present next, and which motivate with our final result on the potential impact of strategic behavior:
Proposition 5. The gap in accuracy between (i) the optimal non-strategic classifier on non-strategic data, and (ii) the optimal strategic classifier strategic data, can be large 30% (see Apx. E.
4 LEARNING AND OPTIMIZATION
We are now ready to describe our learning approach. Our learning objective can be restated as:
h = argmin
Σ L(y h(2 x4,))
(5)
hEH
for = ( as in Eq. (2). The difficulty in optimizing Eq. (5) is that h depend on h through the iterative process, which relies on A.. At test time, ' can be computed exactly by simulating the dynamics. However, at train time, we would like allow for gradients of 8, b to propagate through ² For this, we propose an efficient differential proxy of y² implemented as a stack of layers, each corresponding to one response round. The number of layers is a hyperparameter, T.
Single round. We begin with examining a single iteration of the dynamics, i.e., T = 1. Note that since user moves only if the cost is most 2, Eq. (4) can be rewritten as:
x if h( = - and c( xx() < 2
A (x
O.W.
where a = proj x =i)) is the point to which x; must move in order for o(z;; x.)) to be projected onto h. This projection-like operator (on xr;) can be shown to have closed-form solution:
T "0x;
proja (my4 x,) = xq
10130a
See Appendix B. for a derivation using KKT conditions. Eq. (7) is differentiable in and by to make the entire response mapping differentiable, we replace the "hard if' in Eq. (6) with 'soft if', which we now describe. First, to account only for negatively-classffeed points, we ensure that only points in the negative halfspace are projected via 'positive-only' projection:
0 ((xx( x +
projit ( = I, min 0,
(8)

---

Published as a conference paper at ICLR 2023
0.9
T-1224
---non-strateiic (banch)
S0curacy
0.8
nave:
robust (ours)
aucurac
0.8
T+1
6026
round
mounds
0.7
2 rounds
10 rounds
rounds
conoerged
0.6
0.6
0.45
0.9
0.0
6.2
0.4
0.8
1.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
relance
threshold
Figure 2: (Left) Accuracy of learned h for varying graph importancies [0, 1]. (Right) Accuracy for all threshold classifiers his with sensitivity (horizontal lines) and per network depth '' (dots).
Then, we replace the S 2 constraint with smoothed sigmoid that interpolates between 2; and the projection, as a function of the cost of the projection and thresholded at 2. This gives our differentiable approximation of the response mapping:
Aag x) J; ( 2,)o, (2 c( x4)) x) where a/ = projjt (x;;)=))
(9)
where is sigmoid and т is temperature hyperparameter (r O recovers Eq. (6)) and for T R 0. In practice we add small additive tolerance term for numerical stability (See Appendix B.3).
Multiple rounds. Next, consider the computation of (approximate) modified features after T 1 rounds, denoted a(T), in differentiable manner. Our approach is to apply Å iteratively as:
(t)), x ((+1) = Á(z (z : Ki
3z
(10)
Considering Å as a layer neural network, approximating rounds can be done by stacking.
In Eq. (10), Ki is set to accumulate costs of approximate responses, Ki k (t-1) + c(x! , One observation that for 2-norm costs, ki all points move along a line, equality holds). We can therefore simplify Eq. (9) and replace
(t) c( ,((")) (by the triangle inequality: since
c(a) (t-1) x4) (t-1) with c(x!") .xx).. For other costs, this gives lower bound (see Appendix B.
EXPERIMENTS
5.1 SYNTHETIC DATA
We begin our empirical evaluation by demonstrating different aspects of learning in setting using a simple but illustrative synthetic example. Additional results and insights on movement trends, the effects of movement accuracy, and the importance of looking ahead, be found in Appendix D.1.
For our experimental setup, we set l 1 and sample features Σς E R for each class from a corresponding Gaussian N(y, 1) (classes are balanced). For each node, uniformly sample neighbors from the same class and 3 from the other, and use uniform weights. This creates a informative about labels, but only partially, and in
task where both features and the graph complementary manner (i.c., noise is uncorrelated; for with = 1, if I; < 0, it is still more likely that most neighbors have x; > and vice versa). As it a-priori unclear how optimally combine these sources, we study the effects of relying on the graph to various degrees by varying global a, ie., setting W = - a) and W,y = a/dog, for all i and all * non-strategic settings, the latter serving as a benchmark. Since = 1, H {h₂} is simply the class of thresholds, hence we can scan all thresholds b and report learning outcomes for all models lo, E H. For non-strategic data, the optimal h² has by* 2 0; for strategic data, the optimal h² can be found using line search. Testing is done on disjoint but similarly sampled held-out features and graph.
We examine both strategic and
The effects of strategic behavior. Figure (left) presents the accuracy of the learned for varying and in different settings. In a non-strategic setting (dashed gray), increasing helps, but if reliance on the graph becomes exaggerated, performance deteriorates (a z 0.7 is optimal). Allowing users respond strategically reverses this result: for a 0 (i.e., no graph), responses lower accuracy by
7

---

Published as a conference paper at ICLR 2023
Cora 52.56
CiteSeer
PubMed
Naive Robust (ours)
61.06
19.02 0.01
77.51 + 0.38
75.21 0.25
82.41 = 0.38
Non-strategic (benchmark)
87.95 0.08
77. 1 = 0.05
91.34 0.03
Table I:
Test accuracy of different methods, For all results T = 3 and d = 0.25.
0.26 points; but as a is increased, the gap grows, this becoming more pronounced test-time response rounds progress (blue lines). Interestingly, performance under strategic behavior is worst around the previously-optimal neglecting to account for strategic behavior- can be detrimental. By accounting for user behavior, our approach (orange line) not only recovers performance, but slightly improves upon the non-strategic setting (this can occur when positive points are properly incentivized; see Appendix D.I).
0.75. This shows how learning in strategic environment-
Sensitivity analysis. Figure 2 (right) plots the accuracy of threshold models ha for increasing values of a. For each performance exhibits a "bell-curve' shape, with its peak at the optimal h" As a increases, bell-curves change in two ways. First, their centers shift, decreasing from positive values towards zero (which is optimal for non-strategic data); since using the graph limits users' effective radius of movement, the optimal decision boundary can be less 'stringent'. Second, and interestingly, bell-curves become narrower. We interpret this measure of tolerance: the wider the curve, the lower the loss in accuracy when the learned f is close to (but does not equal) h". The figure shows for a subset of a-s 'tolerance bands': intervals around b* that include thresholds b for which the accuracy of hy is at least 90%, 95%, and 97.5% of the optimum (horizontal lines). Results indicate that larger a-8 provide less tolerance. If variation in h can be attributed to the number of examples, this can be interpreted as hinting that larger a-- may entail larger sample complexity.
Number of layers (7). Figure/ (right) also shows for each bell-curve the accuracy achieved by learned models of increasing depths, T' I,....4 . 4 (colored dots). For a = (no graph), there no inter-user dependencies, and dynamics converge after round. Hence, T = suffices and is optimal, and additional layers are redundant. However, as a increases, more users move in later rounds, and learning with insufficiently large T results in deteriorated performance. This becomes especially distinct for large a: e.g., for a = 0.9, performance drops by ~ 11% when using 4. Interestingly, lower always result in lower, more 'lenient'
T = instead of the optimal thresholds; as result, performance deteriorates, and more quickly for larger, more sensitive a. Thus, the relations between a and T' suggest that greater reliance on the graph requires more depth.
5.2 EXPERIMENTS ON REAL DATA
Data. We use three benchmark datasets used extensively in the GNN literature: Cora, CiteSeer, and PubMed (Sen et al., 2008; Kipf& & Welling, 2017), and adapt them to our setting. We use the standard (transductive) train-test split of Sen et al. (2008); the data is made inductive by removing all test-set nodes that can be influenced by train-set nodes (Hamilton et al., 2017). All three datasets describe citation networks, with papers as nodes and citations as edges. Although these are directed relations by nature, the available data include only undirected edges; hence, we direct edges towards lower- degree nodes, so that movement of higher-degree nodes more influential. As our setup requires binary labels, we follow standard practice and merge classes, aiming for balanced binary classes that sustain strategic movement. Appendix C includes further details. see Appendix D.2 for additional results on strategic improvement, extending neighborhood size, and node centrality and influence.
We compare our robust learning approach to naïve approach that does not account for strategic behavior (i.e.. falsely assumes that users do not move). As benchmark we report the perfor- mance of the naive model on non-strategic data (for which it is appropriate). All methods are based on the SGC architecture (Wu et al., 2019) as it is expressive enough effectively utilize the graph, but simple enough to permit rational user responses (Eq.. (4); see also notes Sec. 1.1). We use the standard weights W D + AD & where A is the adjacency matrix and D is the diagonal degree matrix.
Methods.
Optimization and setup. We train using Adam and set hyperparameters according to Wu et al. (2019) (learning rate=0.2, weight decay=1.3, 100 10-5). Training is stopped after 20 epochs (this usually suffices
8

---

Published as a conference paper at ICLR 2023
Cora
CReeeer
PubMed
80
Accuracy
70
Naive
60
Robust (ours)
60
Non strategic (bench)
20
0.2
0.4
0.5
0.2
0.4
0.1
0.4
max moving distance (d)
Citeeeer
PubMed
80
80
Naive
70
70
60
Robust (ours)
Ntr-strategic (bench)
60
10
10
10
number layers (T)
Figure 3: Accuracy for increasing: (Top:) max distance d (T 3); (Bottom:) depth T (d 0.25).
for convergence). Hyperparameters were determined based only on the train set: == 0.05, chosen to be the smallest value which retained stable training, and T = 3, training typically saturates then (we also explore varying depths). We use B-scaled 2-norm costs, Ca (I, x') = BB| x' 2|,, 3 E IR,,, which induce maximal moving distance of d3 2/ We observed that values around d = 0.5 permit almost arbitrary movement; we therefore experiment in the range E [0, 0.5], but focus primarily on the mid-point d 0.25 (note d implies no movement), Mean and standard errors are reported over five random initializations. Appendix C includes further details.
Results. Table presents detailed results for d 0.25 and T 3. As can be seen, the naive approach is highly vulnerable to strategic behavior. In contrast, by anticipating how users collectively respond, our robust approach is able to recover most of the drop accuracy (i.e., from 'benchmark' to 'naīve'; ; Cora: 35% CiteSeer: 16%, PubMed: 72%). Note this is achieved with T much smaller than necessary for response dynamics to converge (T max: Cora=7, CiteSeer=7, PubMed=11).
Fig. 3 (top) shows results for varying max distances d E 0.5) and fixing T = 3 (note d = 0 entails no movement). For Cora and CiteSeer, larger max distances result lower modification costs-hurt performance; nonetheless, our robust approach maintains fairly stable recovery rate over all values of d. For PubMed, our approach retains Rs 92% of the optimum, showing resilience to reduced costs. Interestingly, for CiteSeer, in the range d [0.05, 0.15), our approach improves over the bascline, suggesting it utilizes strategic movements for improved accuracy (as in Sec. 5.1).
Fig. (bottom) shows results for varying depths T E (O...., 10). For all datasets, results improve as T increases, but saturate quickly at T x 3; this suggests a form robustness of our approach to overshooting in choosing T (which due to smoothing can cause larger deviations from the true dynamics). Using T = 1 recovers between 65% 91% (across datasets) of the optimal accuracy. This shows that while considering only one round of user responses (in which there no dependencies) is helpful, it is much more effective to consider multiple, dependent rounds- even if only a few.
6 DISCUSSION
In this paper we study strategic classification under graph neural networks. Relying on a graph for prediction introduces dependencies in user responses, which can result in complex correlated behavior. The incentives of the system and its users are not aligned, but also not discordant; our proposed learning approach utilizes this degree of freedom to learn strategically-robust classifiers. Strategic classification assumes rational user behavior, this necessitates classifiers that are simple enough to permit tractable best-responses. A natural future direction is to consider architectures coupled with appropriate boundedly-rate -rationa user models, in hopes of shedding further light on questions regarding the benefits and risks of transparency and model explainability.
elaborate predictive

---

Published as a conference paper at ICLR 2023
ETHICS AND SOCIETAL IMPLICATIONS
In our current era, machine learning is routinely used to make predictions about humans. These, in turn, are often used inform-or or even deternine-conseqeeniaall decisions. That humans can (and do) respond to decision rules is a factual reality, and is a topic of continual interest in fields such as economics (e.g. Nielsen et al., 2010) and policy-making (e.g.. Camacho & Conover, 2013); the novelty of strategic classification is that it studies decision rules that are product of learned predictive models. Strategic classification not only acknowledges this reality, but also proposes tools for learning in ways that account for it. But in modeling and anticipating how users respond, and by adjusting learning to accommodate for their effeets- -earning also serves to 'steer' its population of users, perhaps inadvertently, towards certain outcomes (Hardt et al., 2022).
GNNs are no exception to this reality. In the domain of graph-based learning, the role predictive models is expressed in how they associate social connections with decision outcomes for individuals; Clearly, the choice of whether to make use of social data for decisions can be highly sensitive, and doing so necessitates much forethought and care. But the question of whether to social data to enhance prediction is not a binary in nature, i.e., there is no simple 'right" or 'wrong'. Consider our example of the credit scoring company, Lenddo. On the one hand, Lenddo has been criticized that it may be discriminating applicants based on who they chose to socialize with (or, rather, who chooses socialize with them). But on the other hand, Lenddo, who focuses primarily on developing countries, has been acclaimed for providing financial assistance to a large community of deserving applicants who, due conservative norms typically credit scoring rules, would otherwise be denied a consequential loan." 9
Such considerations apply broadly. In other focal domains in strategic classification, such as loans, university admissions, and job hiring, the use of social data for informing decisions can be highly controversial, on both ethical and legal grounds. Regulation is necessary, but as in similar areas, often lags far behind the technology itself. This highlights the need for transparency and accountability in how, when, and to what purpose, social data is used (Ghalme et al., 2021; Jagadeesan et al., 2021; Bechavod et al., 2022; Barsotti et al., 2022b).
ACKNOWLEDGEMENTS
This research was supported by the Israel Science Foundation (grant No. 278/22).
REFERENCES
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. arXiv preprint arXiv:2203.00124, 2022.
Douglas Almond, Joseph J Doyle Jr, Amanda E Kowalski, and Heidi Williams. Estimating marginal returns to medical care: Evidence from at-risk newborns. The quarterly journal of economics, 125 (2):591-634. 2010.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference Learning Representations, 2021. URL https://opemneview.nee/ forum (irmmm"d=8000
Flavia Barsotti, Rüya Gökhan Koger, and Fernando P Santos. Can algorithms be explained without compromising efficiency? the benefits of detection and imitation in strategic classification. In Proceedings of the 2 st International Conference on Autonomous Agents and Multiagent Systems, pp. 1536-1538, 2022a.
Flavia Barsotti, Ruya Gokhan Kocer, and Fernando P. Santos. Transparency, detection and imitation in strategic classification. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 67-73. International Joint Conferences on Artificial Intelligence Organization, 2022b. doi: 10.24963//jcai URL htps://doi.org! 10.24/93//jcaa.22222/0. Main Track.
facehoook/
10

---

Published as a conference paper at ICLR 2023
Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In Kamalika Chaudhuri, Stefamie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp- 1691-1715. PMLR, 17-23 Jul 2022.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference Machine Learning, pp. 695-704, 2019.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Inter- national Conference Learning Representations, 2022. URL http:///peeneviewn///ffooottt
F72ximsx7CI.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017. doi: 10.1100//SP2201.22994444
Michael Brückner and Tobias Scheffer. Nash equilibria of static prediction games. In Advances in neural information processing systems, pp. 171-179, 2009.
Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 547-555, 2011.
Michael Brückner, Christian Kanzow, and Tobias Scheffer. Static prediction games for adversarial learning problems. The Journal of Machine Learning Research, 13(1):2617-2654, 2012.
Adriana Camacho and Emily Conover. Manipulation of social program eligibility, American Economic Journal: Economic Policy, 3(2):41655 65,, 2011.
Adriana Camacho and Emily Conover. Effects of subsidized health insurance on newborn health in developing country. Economic Development and Cultural Change, 61(3):633-66 658- 2013.
Yatong Chen, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. arXiv preprint arXiv:2011.00355 2020.
Andrew Estornell, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Unfairness despite awareness: Group-fair classification with strategic agents. In Thirty-fifth Conference Neural Information Processing Systems (NeurIPS), StratML workshop, 2021.
Ben Finkelshtein, Chaim Baskin, Evgenii Zheltonozhskii, and Uri Alon. Single-node attack for fooling graph neural networks. arXiv preprint arXiv:2011.03574, 2020.
Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jing Piao, Yuhan Quan, Jianxin Chang, Depeng Jin, Xiangnan He, and Yong Li. Graph neural networks for recommender systems: Challenges, methods, and directions. ArXiv, abs/2109.12843. 2021.
Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam- and Nir Rosenfeld. Strategic classi- fication in the dark. In Proceedings of the 38th International Conference Machine Learning (ICML), 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Ian J. Goodfellow. Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://ankiv.orggass///111.....
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., 2005.
11

---

Published as a conference paper at ICLR 2023
Michael Großhans, Christoph Sawade, Michael Brückner, and Tobias Scheffer. Bayesian games for adversarial regression problems. International Conference on Machine Learning pp. 53-63, 2013.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS, 2017.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations theoretical computer science, pp- 111-122, 2016.
Moritz Hardt, Meena Jagadcesan, and Celestine Mendler-Düinner. Performative power. arXiv preprint arXiv:2203. 17232 2022.
Keegan Harris, Hoda Heidari, and Steven Z. Wu. Stateful strategic regression. Advances in Neural Information Processing Systems, 34:28728-28744 287411, 2021.
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*). pp. 159,268,777 2019.
Meena Jagadeesan, Celestine Mendler-Dünner and Moritz Hardt. Alternative microfoundations for strategic classification. In International Conference Machine Learning, pp. 4687-4697. PMLR, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Tosca Lechner and Ruth Umner. Learning losses for strategic classification. In Thirty-fifhh Conference on Neural Information Processing Systems (NeurIPS), Workshop on Learning in Presence of Strategic Behavior, 2021.
David S Lee and Thomas Lemieux. Regression discontinuity designs in economies. Journal of economic literature, 48(2):281-38) -355, 2010.
Sagi Levanon and Nir Rosenfeld. Strategic classification made practical. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incentives. In Proceedings of the 39th International Conference Machine Learning (ICML), 2022.
Jintang Li, Tao Xie, Chen Liang, Fenfang Xie, Xiangnan He, and Zibin Zheng. Adversarial attack on large scale graph. IEEE Transactions on Knowledge and Data Engineering, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 1604.
Apr. 2018 URL
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http://arxxv..or/abb////t 1.0549..
Lydia T Liu, Nikhil Garg, and Christian Borgs. Strategic ranking. In International Conference on Artificial Intelligence and Statistics, pp. 2489-2518, PMLR, 2022.
Chinmay Maheshwari, Chih-Yuan Chiu, Eric Mazumdar, Shankar Sastry, and Lillian Ratliff. Zeroth- order methods for convex-concave min-max problems: Applications to decision-dependeee risk minimization. In International Conference Artificial Intelligence and Statistics, pp. 6702-6734, PMLR, 2022.
Justin McCrary. Manipulation of the running variable in the regression discontinuity design: A density test. Journal of econometrics, 142(():698-71) 2008
12

---

Published as a conference paper at ICLR 2023
John P Miller, Juan C Perdomo, and Tijana Zmnie Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pp. 7710-7720. PMLR, 2021.
Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classifica- tion. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*), pp. 230-239, 2019.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Helena Skyt Nielsen, Torben Sørensen, and Christopher Taber. Estimating the effect of student aid on college enrollment: Evidence from government grant policy reform. American Economic Journal: Economic Policy, 2(2):185-215, 2010.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rae Radd Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008.
Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. PAC-learning for strategic classification.
In International Conference on Machine Learning, pp. 9978-9988. PMLR, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http://arxiv.org/ab///3 131266999
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL http:://openeeieeeneneeommutddDp
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph enn for learning on point clouds. ACM Trans. Graph., 38(5), oct 2019. ISSN 0730-0301. doi: 10.1145/3326362. URL https://doi.org// /ttp://bbboorg/001114322266....
Yanhao Wei, Pinar Yildirim, Christophe Van den Bulte, and Chrysanthos Dellarocas. Credit scoring with social network data. Marketing Science, 35(2):234-258 2016.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neu- ral networks? In International Conference on Learning Representations, 2019, URL hitps: Soopeneeiew..eeffouummddyyy
Xiao Zang, Yi Xie, Jie Chen, and Bo Yuan. Graph universal adversarial attacks: few bad actors ruin graph learning models. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 3328-3334, International Joint Conferences on Artificial Intelligence Organization, 8 2021.
Hanrui Zhang and Vincent Conitzer. Incentive-awart PAC learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in Neural Information Processing Systems, 33:9263-9275, 2020.
13

---

Published as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020.
Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan. Who leads and who follows in strategic classification? Advances in Neural Information Processing Systems, 34, 2021.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. International Conference on Learning Representations, 2019.
Daniel Zügner, Amir Akbarnejdd and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2018.
14

---

Published as a conference paper at ICLR 2023
A ANALYSIS
A.1 HITCHHIKING
Here we provide a concrete example of hitchhiking, following Fig. (B). The example includes three nodes, J. k, positioned at:
Ik -3,
2: 221
3y = 005,
and connected via edges k-+j, and j-vi. Edge weights Wiz 0.6 and Wy; = 0.4; üij = 1/3 and W,i 2/3: and Wks = The example considers a threshold classifier hi with 0, and scale costs (i.e., B 1) inducing maximal moving distance of d d=22 2.
We show that i cannot invest effort to cross and obtain d = 1; but once j moves (to obtain 3j = 1), this results in also being classified positively (without moving). Initially (at round 0), node embeddings are:
4
Φ = -3 : = -1.1 8 3
and all points are classified negatively, Un. 0J új = = 1. Notice that cannot cross the decision boundary even if she moves the maximal cost-feasible distance of d 2:
6lz; (0) + 2 = (x) (0) +) + W (0) = 0.4( (-.4-2.11 2.1 + 2) + 0.6((- 1 -0.34
Hence, i doesn't 't move, so x; (1) (0) Similarly, k cannot cross, so Te = 2x (0)
x;
(1)
However, j can
cross by moving to 1.5 (at cost 2) in order get Vi 1:
-15
(0) +2
= >oa ((a)) = و + m (0) =
2 (1)
1 (-3)= =0 = 11 =1
3
After moves, is classified positively (and so does not need to move):
6lz; (1) 11 - = W (1) + " 0.4(-2.1) + 0.6 = 0.06 >
7 0,00 =1
A.2 CASCADING BEHAVIOR
We give constructive example (for any n) which will be used to prove Propositions and 4. The construction is modular, meaning that we build small 'cyclic' structure of size 3, such that for any given n, we simply replicate this structure roughly n/3 times, and include two additional 'start' and "finish' nodes. Our example assumes threshold classifier hú with b O, and scale costs ca with 1.5 inducing maximum moving distance of dg =3
Let n. We construct graph of size + follows. Nodes are indexed .,..., + 1. The graph
has bi-directional edges between each pair of consecutive nodes, namely (f, + 1) and (i + 1, for all i = O, , except for the last node, which has only outgoing edge (n + 1, n), but no incoming edge. We set uniform normalized edge weights, i.e., Wij 1/3 and Wis = 1/3 for all 1 < j n, and wo,0 W0,1 = 1/2 and Wa+1 Wntlin 1/2. The initial features of each node are defined as:
{ 2 if mod 3 = O.W.
To
Wi 1,
(11)
Figure 4 (A) illustrates this for positioning of node features is cyclic (starting from n = 1): 2, -4. 44 2, - -4, 2, etc.
3. Note that while the graph creates a 'chain' structure, the
We begin with lemma showing that in our construction, each node = 1,..., moves precisely at round =
Lemma 1. At every round st n.
(I) node = moves, with 1.th = 5 if mod 3 3= 1, and (1()) = -1 otherwise
(2) all nodes j do not move, i.e., 2 5 (1-1)
15

---

Published as a conference paper at ICLR 2023
(A)
raw X modified x
emb. de. 91
emb. du 9, =1 graph edge
(w// graph)
effective radius
Figure 4: Cascading behavior. The construction for Propositions 3 and 4, for: (A) 3, which includes one copy of the main 3-node module (light blue box), and (B) for any n >> 3, by replicating the module in sequence (note [V] + 2).
Note that (1) (together with Prop. 1) implies that for any round t, all nodes < (which have already moved at the earlier round L' = i) do not move again. Additionally, (2) implies that all j > / remain in their initial position, i.e., =
(0) Finally, notice that the starting node 2o has do 0.5. meaning that %00 1, and does not move any round.
Proof. We begin with the case for n = 3.
Round 1: Node i
cross moving the maximal distance of 3:
W1, (51 (0) 3) + 1 (0) + U2 122 (0)
+)++) (-1)) (-4) (12)
However, nodes 2,3 cannot cross even if they move the maximal feasible distance:
3222(12 (0) + 3) + 112211 + U3
1 (
1
(-4+
+ (2) -14))-100 (-)))
(13)
3
33,3 (0)
3) W2 (0)
34 (0) = 3
1
(-4+
( (-)
(14)
Round 2: Node i = 2 can cross by moving the maximal distance of 3:
2 (1) + 3) + "1221 + 23.273
(1)
(44+3) + (5)
(-4) (14)) 00
(15)
3
However, node cannot cross even if moves the maximal feasible distance:
34,3 (I) 1 Round 3: Node i = 3 can cross by moving the maximal distance of 3:
3 (1) 3) W2,302 (1)
3 (-4+ (-4) -
(2)
(16)
1 (-4+3) + 3 (-1) + (2)
W3.3 (3
3) + 22.302 + a
(2) =0
(17)
3
Fig. 4 (A) illustrates this procedure for 3.
Next, consider n > 3. Due to the cyclical nature of feature positioning and the chain structure of our graph, we consider what happens when sequentially add nodes to the graph. By induction, can show that:
mod 3 1: Consider round t n.. Node n has x (t-1) 1) 2, and two neighbors:
1, who
after moving at the previous round has x = 11; and n + 1, who has a fixed x Thus, it is in the same configuration as node i 1, and so its movement follows Eq. (12).
n mod 2: Consider round t n. Node n has (t (t-1) -4, and two neighbors: n 1, who (t-1)
after moving at the previous round has [t-1)) 5; and n + 1, who has a fixed x #n+1 = -4.
Thus, it is in the same configuration as node i 2, and so its movement follows Eq. (15).
16

---

Published as a conference paper at ICLR 2023
mod O: Consider round / ys. Node has un (t-1) -4, and two neighbors: n 1, who (t-1)
after moving at the previous round has æn-1 11; and n + 1, who has a fixed 1++1 Thus, it is in the same configuration as node i 2, and so its movement follows Eq. (17).
Fig. 4 (B) illustrates this idea for n 3.
We now proceed to prove the propositions.
The proposition follows immediately from Lemma the only detail that remains to be shown is that node n + 1 does not move at all. To see this, note that since it does not have any incoming edges, embedding depends only on own features, In+1- have Fn++1 = 2, and so J.+1 without movement. Otherwise, Ix+1 -4, meaning that it is too far to cross.
Proposition 3:
mod 1, we
Proposition 4: Fix and k S Consider the same construction presented above for graph of size Then, add n nodes identical nodes: for each k: < j S n, add an edge k-tj, and set 2 T2k - 6. We claim that all such nodes will move exactly round k. Consider some node j < n. Since T4 moves only at round & (following Lemma 1), j does not move in any of the first i k rounds:
ر +3) f
(- -6+3)
1
(0)
3) 1 (0)) ( (xb (0)) (1 / (- -0-)))3)+
1.5 < (18)
At the end of round k. node has value of maximal distance of 3:
+ 3. This enables cross by moving the
1 3) 2
(x) +3)+ Wh
(- - 6+
+ 0 (19)
2
As this applies to all such j. we get that n - k nodes move at round k, which concludes our proof.
Note the graph is such that, for (increases accuracy from 66% to 100%). so that learner that unaware of (or does not account for) strategic behavior is incentivized utilize the graph. However, once strategic behavior introduced, naively using the graph causes performance to drop to 0%.
without strategic behavior the graph is useful for prediction
B OPTIMIZATION
B. PROJECTION
prove for --norn-squared costs. Correctness holds for 2-norm-costs since the argmin the same (squared over positives is monotone). Calculation of 's best response requires solving the following equation:
min c(1,,,)) s.t 8 (+)()=) b- x'
min - 1il12 o (o((ia
To solve for z', we apply the Lagrange method. Define the Lagrangian as follows:
I( = | - 1:112 A x())x=1)) + b]
Next, find the minimum of derive with respect to a/. and compare
2( 221) + A0T; 0
2/ = Awaa 0
17

---

Published as a conference paper at ICLR 2023
Plugging 2 into the constraint gives:
Adi
0 Wai
1) +
W
+ 0
j7t
Aw
0 [0(x)i-_1)
0) + b = 0
2
Aw
0 (( 6
|0
0 M( +
10 2
Finally, plugging À into the expression for x obtains:
1 = 0 (T)
|101200a
B.2 GENERALIZED COSTS
Here we provide a formula for computing projections in closed form for generalized quadratic costs:
d(x,x')
2 (x' x) A(r' =T)'('( x)
for positive-definit A. As before, the same formula holds for generalized 2-norm costs (since the argmin is the same). Begin with:
min c(2),,;)) s.t 0 (T + -
min (x:) T A(x1 a.)) sat 0 ()) + b-
As before, apply the Lagrangian method:
2 (04 );) A(x! - xi) + x o(x5;==;) +
Derivation w.r.t. to n/;:
1 [A (o) - -z;) + A(x' - x²] + \0W; = 0
2
(AT + A)a' (AT + A)z: 2A0w;
Since the matrix (A T + A) PD, we can invert get:
1 = x 2x(A T + A
Plugging of in the constrain:
0 [1, - 21(A* T + -1)-1000 + Σ WijHz [ogti,(+b00 -b=0
0 (((G) - 2A A) A)- - bb
0 0(IA)_1) + b= 2A0 (A + -1)
Since (AT + A) is also PD. we get 0 T (AT + +A)-10 0, and hence:
0 6(0;5 x;) + =
2Ø (AT + -) 1002
Finally, pluging in A:
0 0xI; x +
1 = Tz
(AT + -1000
0 OT (AT + A) -10
0 (0
2 = x
(AT + AA-
0 (AT + 1
Setting A 7 recovers Eq. (7).
18

---

Published as a conference paper at ICLR 2023
Table 2: Real data statístics and experimental details
[V]
E]
Thrain
iest
negative classes
positive classes
% 1}
(train (tein/
Cora
2,708
5,728
1,433
640
577
0,2,3
1,4,5,6
44% 44%%
CiteSeer
3,327
4,552
3,703
620
721
0,2,3
1,4,5
50% 49%
Pubmed
19,717
44,324
500
560
941
1,2
0
21% / 18%
B.3 IMPROVING NUMERICAL STABILITY BY ADDING A TOLERANCE TERM
Theoretically, strategic responses move points precisely on the decision boundary. For numerical stability in classifying (e.g., test time), we add small tolerance term, tol, that ensures that points are projected to lie strictly within the positive halfspace. Tolerance is added as follows:
min c(2/, 27)) s.t HT ((x;;==)) + tol
(20)
This necessitates the following adjustment to Eq. (7):
proja( 3z 0 Ma + bb tol
0
(21)
1 101
However, blindly applying the above to Eq. (8) via:
projt (xn min { o. 0J (xx;; x--) + tol
(22)
10122a
erroncous, since any user whose score is lower than tol will move although in principal she shouldn't, t. To correct for this, we adjust Eq. (8) by adding a mask that ensures that only points in the negative halfspace are projected:
("
(TTM(x;--)) x-) b 1-t--ol
tol
(EgT = I; - 110 (bc;
0)
(23)
1011200;
C ADDITIONAL EXPERIMENTAL DETAILS
Data. We experiment with three citation network datasets: Cora, CiteSeer, and Pubmed Sen et al. (2008). Table 2 provides summary statistics of the datasets, as well as experimental details.
Splits. All three datasets include standard trin-validatioo-tes split, which we adopt for our use. For our purposes, we use make no distinction between 'train' and 'validation', and use both sets for training purposes. ensure the data is appropriate for the inductive setting, we remove from the test set all nodes which can be influenced by train-set nodes this ranges from 6%-43% of the test set, depending on dataset (and possibly setting; see Sec. D.2.1). In Table the number of train samples is denoted Ruain and the number of inductive test samples is denoted niss (all original transductive test sets include 1,000 samples).
Binarization. To make the data binary (original labels multiclass), enumerated possible partitions of classes into 'negative' and 'positive', and chose the most balanced partition. Experi- menting with other but similarly-balanced partitions resulted in similar performance (albeit times less distinct strategic movement). The exception to this was PubMed (having only three classes), for which the most balanced partition was neither 'balanced' nor stable, and so here we opted for the more stable alternative. Reported partitions and corresponding negative-positive ratios (for train and for test) are given in Table 2.
Strategic responses. At test time, strategic user responses are computed by simulating the response dynamics in Sec. 3.1 until convergence.
Note that nodes in these do necessarily account for all nodes in the graph.
19

---

Published as a conference paper at ICLR 2023
sccuray
changa dusitacm
Tu
acurcyy
-24
95 10 1.5 2.
0.5
UriaA
Figure 5: Synthetic data: relations between movement and accuracy. All results use a 0.7. (Left:) The relative number of points that move for every threshold b, per class, and comparing one round (I' = 1) to convergence (T" = oo). (Center:) Accuracy for every threshold b, after one round (T'=) = 1) and at convergence (7' oc). For each optimal b, bars show the relative number of points (per class) that obtain ÿ = 1 due to strategic behavior. (Right:) Accuracy for T = 1 (top) and T = co 0), and result of strategic movement of negative points (red arrows; decrease accuracy) and positive points (green arrows; improve accuracy).
(bottom), relative to the non-strategic benchmark
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 EXPERIMENTS SYNTHETIC DATA
In this section we explore further in depth the relation between user movement and classification performance, using our synthetic setup Sec. 5.1 (all examples discussed herein use a 0.7). From predictive point of view, graphs generally helpful if same-class nodes are well-connected. This is indeed the case in our construction (as can be seen by the performance of the benchmark method with non-extreme increases cooperation, since neighboring nodes can positively influence each other over time. In our construction, cooperation occurs mostly within classes, i.e., negative points that move encourage other negative points to move, and similarly for positive points.
> 0 values). From strategic perspective, however, connectivity
Movement trends. Fig. 5 (left) shows how different threshold classifiers ha, induce different degrees of movements. The plot shows the relative number of points (in percentage points) whose predictions changed as result of strategic behavior. per class (red: y 1,, green: y 1) and over time: after one round (7 1, dashed lines), and at convergence (T = oc, solid lines). As can be seen, there is general trend: when is small, mostly negative points move, but increases, positive points move instead. The interesting point to observe is the gap between the first round (T = 1) and final round (T = =c). For negative points, movement at = peaks at bj -0.25, but triggers relatively little consequent moves. In contrast, the peak for T = occurs a larger d R 0.15. For this threshold, though less points move in the first round, these trigger significantly more additional moves at later rounds-2e result of the connectivity structure within the negative cluster of nodes (blue arrows). A similar effect takes place for positive nodes.
The importance of looking ahead. Fig. 5 (center) plots for range of thresholds the accuracy of hg at convergence (T = oo; orange line), and after one round (T- ===1 1; gray line). The role of the latter is to illustrate the outcomes as 'perceived' by a myopic predictive model that considers only one round (e.g., includes only one response layer Å); the differences between the lines demonstrate the gap between perception (based on which training chooses a classifier h) and reality (in which the classifier h is evaluated). As can be seen, the mypoic approach leads to an under-estimation of the optimal b*; at bj x 0.5, performance for T = 1 is optimal, but is severely worse under the true oo, for which optimal performance is at 0. Rs 1.15.
The figure also gives insight as to why this happens. For both by and bsc. the figure shows (in bars) the relative number of points from each class who obtain ÿ = as result of strategic moves. Bars are stacked, showing the relative number of points that moved per round T (darker = earlier rounds; lightest = convergence). As can be seen, at by the myopic models believes that many positive points, but only few negative points, will cross. However, in reality, convergence, the number of positive points that crossed is only slightly higher than that of negative points. Hence, the reason for the(erroneous) optimism of the myopic model is that it did not correctly account for the magnitude of
20

---

Published as a conference paper at ICLR 2023
Cora
CRteeeer
PubMed
80
80
70
Accuracy
70
Naive
Robust (ours)
65
Non-strategic (bench)
60
50
30
+layers (K)
Figure 6: Accuracy for varying number of SGC layers (K). Note test sets may vary across K.
correlated moves of negative points, which is expressed over time. In contrast, note that at b barely any negative points cross.
How movement affects accuracy. An important observation about the relation between movement and accuracy is that for any classifier h, any negative point that moves hurts accuracy (since -1 1), whereas any positive point that moves helps accuracy (since y 1 and predictions are now g = 1). Fig. 5 (right) shows how these movements combine to affect accuracy. The figure compares accuracy before strategic behavior (T 0; dashed line) to after one response round (T = 1; solid line, top plot) and to convergence (7 = oo; solid line, lower plot). As can be seen, for any b, the difference between pre-strategic and post-strategic accuracy amounts exactly the degradation due to negative points (red arrows) plus the improvement of positive points (green arrows).
but predictions become
Note, however, the difference between T = and T' = oc, as they relate to the benchmark model (T 0, i.e., no strategic behavior). For T (top), across the range of positive and negative moves roughly balance out. A result of this is that curves for T = 0 and T = 1 are very much similar, and share similar peaks in terms of accuracy (both have 0.89). One interpretation of this that if points were permitted to move only one round, the optimal classifier can completely recover the benchmark accuracy by ensuring that the number of positive points the moves overcomes the number of negative points. However, for T co (bottom), there is skew in favor of positive points (green arrows). The result of this is that for the optimal 6, additional rounds allow positive points to move in way that obtains slightly higher accuracy (0.91) compared the benchmark (0.89). This is one possible mechanism underlying our results on synthetic data in Sec. 5.1, and later for our results on real data in Sec. 5.2.
D.2 EXPERIMENTS ON REAL DATA
D.2.1 EXTENDING NEIGHBORHOOD SIZE
One hyperparameter of SGC is the number 'propagation' layers, K, which effectively determines the graph distance at which nodes can influence others (i.e., the 'neighborhood radius'). Given K, the embedding weights are defined as W Dー A D- where A is the adjacency matrix and D is the diagonal degree matrix. For K 0, the graph is unused, which results in a standar linear classifier over node features. Our results in the main body of the paper use K = 1.
Fig. shows results for an increasing K (we set = 3, d = 0.25 as in our main results). Results are mixed: for PubMed, higher K seems to lead to less drop in accuracy for naïve and less recovery for our approach; for Cora and CiteSeer, results are unstable. Note however that this may likely be a product of our inductive setup: since varying K also changes the effective test set (since preserve inductiveness, larger K often necessitates removing more nodes), test sets vary across conditions and decrease in size, making it difficult directly compare result across different K.
21

---

Published as a conference paper at ICLR 2023
D.2.2 STRATEGIC IMPROVEMENT
Our main results Sec. 5.2 show that for CiteSeer, our strategically-awan approach outperforms the non-strategic benchmark (similarly to our synthetic experiments). Here show that these results robust. Fig. 7 provides higher-resolution results on CiteSeer for max distances d E [0, 0.22] in hops of 0.01. All other aspects the setup match the original experiment. As be seen, our approach slightly but consistently improves upon the benchmark until d xs 0.17.
Sloe
77.5
75.0
Accuracy
72.5
70.0
67.5
Naive
Robust (ours)
strabegic (bench)
62.5
0.00
0.05
0.10
0.15
0.20
max moving distance (d)
Figure 7: Accuracy on CiteSeer for increasing max distance (focused and higher-resolltion))
D.3 NODE CENTRALITY AND INFLUENCE
In this experiment set to explore the role played by central nodes in the graph in propagating the influence of strategic behavior. Since the embedding of a node is partly determined by its in-neighbors, broadly we would expect that nodes have high out-degree would be highly influential: as 'anchors' that prevent others from moving if they themselves do not, and as 'carriers' which either push neighbors over the boundary- or at least promote the closer to it they do move.
Experimental setup. To study the role of such nodes, we preform the following experiment. First, we order the nodes by decreasing out-degree, so that the potentially more influential nodes appear first in the ranking. Then, for each E {0. 10, 20, .... 100}. we disconnect nodes in the gth percentile, i.e., remove edges emanating from the top-4% ranked nodes. For each such condition, we examine learning and its outcomes, and compare performance to control condition in which nodes ordered randomly. The difference in performance and other learning outcomes provides us with a measure of the importance of high-degree nodes.
Results. Figure 8 shows results for all methods (naïve, robust (ours), and the non-strategic benchmark) and across all three datasets (Cora, CiteSeer, and Pubmed). In all conditions, the x-axis the portion of nodes that remain connected, where at zero (left end) we get an empty graph, and at 100 (right end) we get the original graph. Note that the y-axis varies in scale across plots.
vary on
First, consider Cora. In terms of accuracy (upper plots), results show that on the benchmark (evaluated in non-strategic environment, which users do move), the general trend is that more edges help improve performance. However, the gain in performance is much more pronounced for high- degree nodes. Interestingly, for the naïve method (which operates on strategically modified data, but does not anticipate updates), the trend is reversed: user utilize edges in way that is detrimental to performance- and more so when high-degree nodes remain, making them vulnerability. Our robust approach is also sensitive to the addition of edges, but to much lesser degree (the drop is performance is minor); moreover, which nodes are disconnected appears to make little difference, which we take to mean that our approach can counter the dominant role of central nodes.
The lower plots, which describe the portion of users that moves and the portion users that crossed, provides some explanation as to how this is achieved. For the naïve approach, nearly half of all user move- and all users that move, also cross. This occurs faster (in terms of the portion of nodes removed) in the degree condition. In our robust approach, note that the number of nodes that move is halved, and of those, not all cross, which demonstrates how are learning objective, which anticiaptes strategic behavior, can act to prevent it.
22

---

Published as a conference paper at ICLR 2023
Core
nolve
rabust (ours)
non stretegic (benchmark)
56
75.0
88123
58.00
87.75
94
77.0
87.50
87.25
rcecom
degres-mneed deggess cirieed
20
40
00
80
100
30.0
of nodes
connected
69.5
15g to Dosses
fandeer cresees
48.0
47.5
20-
portion noces romath connected
porto nodes remain connected
noive
rabust (ours)
non www.stttrticccc.. (benchmark)
dayan
75.5
dagres
78.25
73.0
78.00
$1.2
$1.0
71.50
04:0
60.8
77.25
77.00
randor-rouut
4egree-Tov15
20
10
00
80
100
degiee- 27000-20058
portion of nodes that remaain connected
26.0
39.8
35.6
35.4
39.2
remain
PubMed
(benchmark)
30.25
(anden
aandr
01.38
91.56
49.75
49.90
91.52
06.0
52.5
10.5
that romTa connected
42.0
10.3
51.0
8.5
40
60
portion modes Erat remaiin connected
portion of nodes remain connectec
Figure 8: The effect of node centrality on performance and strategic behavior across datasets.
For CiteSeer and PubMed, the general trend in accuracy is reversed for the non-strategic benchmark, and for the naïve approach, begins with gap, which closes at some point (sooner in CiteSeer). Despite these differences, the qualitative behavior of our robust classifier is similar to Cora, and achieves fairly stable accuracy (with a mild negative slope) both conditions and for both datasets. As in citeseer, movement and crossing behavior similar, in that for the naïve approach considerable portion of users move and cross (with a gap between conditions in PubMed); and that our robust approach greatly reduces the number of users that move, and even more so the number that cross.
23

---

Published as a conference paper at ICLR 2023
E ADDITIONAL ANALYTIC RESULTS
E. PERFORMANCE GAPS: ROBUST LEARNING VS. THE NON-STRATEGIC BENCHMARK
When learning robust classifier on strategic data, intuitively we may hope that its performance approaches that of the optimal classifier on non-strategic data, which we may think of as a target upper bound. natural question to then ask can we always reach this upper bound and close the performance gap? Here we answer this question in the negative, by showing simple example where the optimal classifier on non-strategic data achieves perfect accuracy, but the optimal classifier on strategic data achieves only 0.66 accuracy. We then show that by introducing a mild change -amely slightly shifting the features of one node- performance gap closes entirely. This, combined with result from the previous Sec. D.2.2 showing that the gap can also be negative, highlights how the gap in performance greatly depends on the structure the input (i.c., the graph, features, and labels), and in way which be highly sensitive even minor changes.
E.1.1 LARGE GAP
Our first example in which the best obtainable gap is 0.33 is shown in Figure (Left). The example has three nodes described by one-dimensional features xi = 1.2, 222 = -1,, T3 = -- 1 and with labels y1 1, 1/2 -1, 1/3 1. We use the standard cost function so that maximal distance to move is dg = 2, and use uniform edge weights. Since x R. classifiers are simply threshold functions on the real line, defined by threshold parameter b E R.
First, we demonstrate that for non-strategic data, there exists a 'benchmark' classifier that achieves perfect accuracy. bet 0. Node embeddings are:
T1 +
T2
1-1
Φ1
0
2
3
+
32
+
33
1- --1
0
<0=b
3
3
3
F2 +
F3
03
-
b=b
2
2
This give predictions Φ1
91 02 -
y2 D3
yss which are all correct.
Next. we prove that there is no robust classifier capable of achieving perfect accuracy on strategic data. Suppose by contradiction that such a classifier exists, denoted For zy move in the first round, the following conditions must hold:
T1 + z/g I3
1+ 2/2 1 3b,
z/2 =b
Since 22 moves at most distance 2, it moves the first round only if - < b S 1.2 However, it does move it ends up getting incorrect prediction. In addition, in this a positive prediction (either in the first round or in the next round, depending on whether b >> 0), in which the accuracy is 1. Thus, we get that positive which is wrong).
T3 can also get
(note that for b < 22 is classified as
Next, we look the behavior of xi in the first round. Conditions for movement are:
x + x2
x - 1 2b,
2 = 26 +
Here Iı gets negative classification if 0. b 1, then 21 does not move, since the distance required is larger than 2. Thus, does move (beyond the classifier) and gets the correct prediction
only if b <
However, considering now the second round of movement for (which only occurs if b > 1 for 0 < b S 2e moves at the first round), we get the conditions:
3 since
2 2'+24++33
2b 2b+1+66 - 3b,
J/B
3
24

---

Published as a conference paper at ICLR 2023
Large gap
No gap
optimal nonsstratngic
optimal robust (accel) (6 1.1)
optmall
[aco-1] G 0)
(b
now
Modified dCx) emb. 91.
D
X1
amb. 91.
graph edge
33
12
Figure 9: An example of how small change in features leads a large decrease the performance of the robust model (Left:) An optimal robust classifier achieves an accuracy of 1. (Right) The optimal robust classifier achieves an accuracy of (there no movement in that case).
This means that for all 0 b S 1, D2 moves and gets an incorrect prediction. This occurs either for 2 or for 22. Consequently, there is no that achieves an accuracy of 1, which contradicts the assumption.
The optimal accuracy of any robust classifier for this example is 3. which is achieved by any > 1. In this case, none of the nodes move, and 21 is classified negatively, whereas its true label is positive.
E.1.2 No GAP
We now give nearly identical example, shown in Figure (Right), in which the gap becomes zero.
We use the same example as before, but set æ1 (instead æ = 1.2). We begin by showing that there does exist classifier which achieves perfect accuracy on non-strategic data. Let 0, then embeddings are now:
+ x2
1
0.1 0=
T1
+
D2 + Ø3
1.2
1-2
<0=b
3
15
T2
F3
-1
(note that since all nodes are connected in the graph, changing क requires us to recompute all embeddings). Predictions now become:
0 +1 Vi
0/2 - U2
Ú3
y/3
which are all correct.
Next, show that there also exists a classifier which achieves perfect accuracy no strategic data. Let b = 1.1. In the first round, I1 moves, and flips its predicted label:
2 +
T +2
2 +
3.2
1.1 =
2
2
2
2
Here, even if the other nodes move to the fullest extent, they do not have sufficient influence to revert this prediction:
I
+
12
33
1.2 + -1 1 = 0.4 < -11
2
3
3
I2
+
I
-1-1+2
03
111=b
2
2
25

---

Published as a conference paper at ICLR 2023
Thus, get
ÿ1 = +1 = y1,
1/2 = = 1/2,
Ú3 = = = ya
which are also all correct.
E.2 STRATEGIC BEHAVIOR OF CLIQUES
Here we give result that considers graph structure. In particular, we consider cliques, and show that for uniform weights, either all nodes move together-or none do.
Proposition 6. Consider nodes which all fully connected, i.e., form a clique, and assume uniform edge weights. Then for any dimension d any assignment of Z1..... In E R", and for any classifier h, either all n nodes move the first round, or (ii) none of the nodes move all.
Proof. Consider the case in which at least one node i moves in the first round. Denote by the change in z; made in order to cross the classifier, i.e., 2 = az!1) 2(()) Note that in order for 2; to move, the following conditions must be satisfied:
|| 2,
8T ( (1) x (
We now show that every other node I, if it moves a distance of then it can also cross the classifier the first round:
42 (1)
(0)
$(x (1),
Ljzt
3j
I; + 2 + Σ Žj 2j
(0)
(0)
n
(0)
+ ΣØ=1 Zjj
It
+ 2 + Σ Ejet j+tt 2
11
4t + Σ j$t
(1)
x (0)
Hence, we get that ((x = ((x(") ;
(0) and thus  6(x; x( b = O, which indicates
that ve can also cross classifier in the first round.
E.3 GRAPH DIAMETER AND THE SPREAD OF INFORMATION
Since nodes that move can influence outcomes for their neighbors, intuitively we might expect that the diameter of the graph would be upper bound on the reach of such influence. Here we give negative result which shows that influence can far exceed the diameter.
Proposition 7. Let G be a graph with diameter then the number of update rounds is not bounded by d + c, for any constant c.
Proof. We prove by giving an example in which the number of rounds until convergence, T, is roughly twice the diameter.
We use the same example as Sec. A.2, but with the following small changes: (i) we add edge from In to Ta+1; (ii) add
node, 2n-2 = -8, and connect it with bidirectional edges zo and In+1; and (iii) we set the weight of every edge to be 1.2 We denote by G the original graph from Sec. A.2, and by G' the graph with the above changes applied. By construction, G" is circular graph with n + nodes; hence, its diameter [
We claim that the changes made to G' do not affect the behavior of nodes, i.e., in both G and G', in each round t, the same nodes move and the same manner. Note that our construction in Sec. A.2 contains "modules" of size 3 that are connected sequentially, together with start and end nodes, to
26

---

Published as a conference paper at ICLR 2023
Figure 10: Circular cascading example. The diameter is [=+3 J. but the number movement rounds is n.
form a graph of size + 2. To show that the node we add in this construction does not cause the final nodes to move, it suffices consider whether In+1 can cross-we will show that cannot, which implies that 2n+2 and To will not cross either.
In the first round, we saw that in G. Iı moves, but for no change in the features of these nodes or the edge weights, this behavior also occurs in G'. Note zo does not move at the first round:
S. n, I; does not move. Since there is
o (0)
+ wi o (0)
2.0 (0)
(-1+3) 5 (-8) 4 <0
Next, show that xn does move in the first round either.
22. (0) + 2 + 3) + 2 n+1 - _ +-1)+ (-8+3)) <<0
3
Next, we show that In+1 does not move:
(0) n+2 + (1 (0) 3) + on (0) <
1 +(-))
1
In the second round, node can potentially move only one of its neighbours moved in the first round. As in G, 22 moves in G' as well. We now show that 2o does not move:
(1) 3) "1 (1 (x!
(1) 1 (-1+3) 1 3
(-8)
- <0
1
1
For each round let S n correspond to the node x; which moves in G" moves in G. We now show that in round + 1 there is no movement. In round 2n is the only one that moves. Thus, the only nodes that might move are neighbors, #n-1 and Ix+1- Since r, has already moved round 1, it will not move again (Prop. 1). This leaves In+1, which we now show does not move either:
1 (n) + Ln++L (m(m) + 3) + "n
(n)
3 (-8)
1 (2 (-1) <0
1
This concludes that while the diameter of the graph is 7 J. the number of rounds in n.
27


Reviews:
[{"review_id": "yvyXd1NY8k", "reviewer": "Reviewer_rHAu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors formulate the problem of strategic classification on graphs, which users shall modify their features with some cost (strategic classification) and the predictor on a user relies on the smoothed embedding of neighbors of a user. Users are assumed to make myopic decisions based on other users' previous behavior. The fact that one user's actions can impact predictions on other users introduces interesting dynamics on the collective behavior of users. Authors identify interesting properties of the dynamics with both mathematical analysis and numerical experiments. ", "summary_of_the_review": "Both practically & analytically interesting problem formulation with good insights from both analytical & numerical experiments. However the analysis could've been strengthened by taking graph properties into account, or considering non-myopic behavior of users.", "strength_and_weaknesses": "The problem formulation is elegant. It is different enough from existing strategic classification formulations to introduce interesting dynamics across users. It is realistic enough to motivate real-world scenarios like credit scoring for microlending. It is simple enough to allow interesting mathematical analysis and possible to be adapted for more complex problems. Authors made a good judgment balancing these considerations.\n\nBoth mathematical analysis and empirical analysis provide good insights into how GNN introduces dynamics to the collective behavior of users. On the other hand, neither mathematical analysis nor empirical analysis actually take the property of the graph into consideration. This is unfortunate, because for sure the characteristics of graphs would play a crucial role determining the dynamics. For example, if the graph is divided into components, no information shall propagate across components. Short-radius graphs would propagate changes faster than long-radius graphs. A central node (say, in terms of PageRank or other centrality metrics) would play a bigger role impacting the dynamics than peripheral nodes would. \n\nThe fact that users only make myopic decisions also make the problem less interesting. Users would not really take advantage of opportunities to \"collude\" with their neighbors. Given it is reasonable to assume users shall communicate their plans with their social network, the fact that this works stops at myopic model is disappointing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "xu3Yw5xXqn", "reviewer": "Reviewer_uqWQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the problem of strategic classification on graphs under a simplified linear graph model. The authors consider an iterative strategy for nodes changing features. An approximation learning algorithm is proposed to learn a robust classifier. The authors experiment on both synthetic 1d case and three real-world graph dataset.", "summary_of_the_review": "Though the paper studies an interesting problem, several assumptions are too simplistic and not practical.  ", "strength_and_weaknesses": "Strength\n1. The authors study an interesting question to generalize the i.i.d assumption in strategic classification to graph neural networks.\n\nWeakness\n1. Several assumptions in the problem definition are too simplistic for practical usage. On the model side: (1) it assumes nodes can directly change its embedding instead of the features which is mostly not the case. (2) The assumption of linearity and only considering direct neighbors severely limits the expressibility of GNN. On the strategy side, though, assuming access to h is already a strong assumption. The access to features of all neighbors nodes is way too strong to be practical especially in multi-step updates. Also, the assumption that all nodes have the same incentive to move towards the same class is also limiting.\n2. The analysis framework of multi-step is not appropriate for the problem. It is much more natural to consider game-theoretical concepts like equilibrium. Several results from the analysis are straightforward. It would be very interesting to see results like convergence results to equilibrium etc. Also, the assumption to set gain as 2 if flipped is also arbitrary.\n3. The empirical evaluation uses different assumptions compared to previous model and analysis. Section 2 allows nodes to change features arbitrarily as long as it is smaller than the gain. However, Section 5.2 assumes a max distance which induces quite different behavior.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "wLAN5mOO7b", "reviewer": "Reviewer_KAMH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies strategic classification under graph neural networks. In the model of strategic user behavior, it is assumed that a user plays myopic best-response over a sequence of multiple update rounds. The myopic response mapping means that a user may move their reported features in the direction that best improves their classification outcome from the graph neural network model. Several results are then stated to demonstrate the basic properties of the myopic response model and the consequent dynamics.\n\nThen, the learning objective based on the myopic best response is optimized over multiple rounds. This optimization computes the approximately modified features after T rounds.\n\nEmpirical evaluation is provided to demonstrate different aspects of learning in the above setting. Several experiments are conducted on popular settings in the GNN literature, this includes the Cora, CiteSeer, and PubMed datasets, trained with a simplified GCN architecture. The results show that by anticipating the strategic behavior of users in the GNN, the optimized graph neural network performs robustly against the naive baseline, which trains a GNN without accounting for any strategic behaviors.", "summary_of_the_review": "Overall this paper studies strategic classification in graph neural networks; it adopts a myopic best response strategy for modeling user’s strategic behavior. Then it incorporates such myopic behavior into an optimization procedure. Experiments verify the robustness of this optimization method. On the other hand, it remains unclear to what extend could one close the gap between robust and non-robust performance, and how general the reported result is (in the broader context of GNN literature).", "strength_and_weaknesses": "This paper is generally well-written; the methods and the experiments are both clearly described. The experiments also provide clear evidence about the proposed method in the presence of strategic behaviors of users.\n\nOne question with the reported results (e.g., in table 1) is to what extent is the gap between robust and non-strategic performance necessary. Whereas for CiteSeer, there is only a 2% gap between the two settings; for Cora and PubMed, there are about 10% gap between the two settings. To what extent can we close the performance gap between the robust performance and the non-strategic performance?\n\nAnother question is to what extend do these results hold under architectural modifications—e.g., suppose one changes the diffusion matrix in the GNN, would the same result still apply?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "d89sFdzOhJY", "reviewer": "Reviewer_aLDo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the strategic classification problem on graphs. Specifically, they consider a linear graph-based classifier, which classifies each node in the graph based on the node embedding with a linear function. The node embedding of each node depends on the features of this node and also the features of its neighborhood. In the strategic classification setting, each user (node) can modify the features of this node to change the classification result. The strategic classification problem is to learn a linear graph-based classifier to minimize the misclassification loss under strategic behavior. \n\nThis paper shows that the inter-user dependency on the graph might be exploited by strategic users and cause a higher loss. They also propose a differential framework for strategically-robust learning of graph-based classifiers.  Their theoretical results and method are supported by experimental results.", "summary_of_the_review": "I think this paper is interesting and provides valuable insights into the strategic classification with interaction, which might be useful for further investigation.", "strength_and_weaknesses": "Strengths:\n1. This paper proposes a novel strategic classification setting on the graph. \n2. This paper analyzes the strategic behavior of users in interaction with others.\n3. They propose a differentiable framework to learn a robust classifier in the strategic classification on graph setting. \n\nWeaknesses:\n1. It seems properties in section 3.2 and the learning algorithm highly depend on that the classifier is linear. I understand that linear classifier is widely used in practice and more accessible as the first step toward this problem. \n2. At the beginning of section 3 and experiments, you normalize the weights such that the node embedding depends on one parameter $\\alpha$. It seems this simplifies the effects of the graph structure and makes the problem easier.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster