Strategic Classification with Graph Neural Networks

Itay Eilat, Ben Finkelshtein, Chaim Baskin, Nir Rosenfeld

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.

Introduction

Traditional strategic classification models assume that individuals act in isolation when modifying their features to "game" an algorithm. However, in many real-world applications—such as credit scoring or social media moderation—outcomes are determined by relational data. When a system employs Graph Neural Networks (GNNs), a user's prediction depends not only on their own data but also on the features and actions of their social connections. This paper explores how these inter-user dependencies change the strategic landscape, introducing phenomena like "hitchhiking" and "cascades," and provides a framework for training GNNs that are robust to such collective behavior.

Modeling Strategic Behavior in Graphs

The study focuses on Simple Graph Convolution (SGC) architectures. The linear nature of SGC allows for a tractable mathematical analysis of "best-response" strategies. User behavior is modeled as a multi-round game where, in each round, a user modifies their features to cross a decision boundary, assuming other users' features remain constant. Because GNNs aggregate neighbor information, these individual modifications propagate through the network over time.

Conceptual illustration of strategic behaviors in GNNs: (A) hitchhiking, where a user crosses the boundary due to neighbors' moves; (B) cascades, where one move triggers another; and (C) strategic improvement.

Key Conceptual Insights

  • Hitchhiking: A user can achieve a favorable classification without changing their own features if their neighbors move enough to shift the local graph aggregate.
  • Cascades: A single user's feature modification can create a "domino effect," making it marginally cheaper for their neighbors to move, which in turn influences further nodes. The authors prove these dynamics converge in at most $n$ rounds.
  • The Graph as a Liability: While relational data typically improves accuracy, high reliance on the graph ($\alpha$) can become a vulnerability. Clusters of users can coordinate to flip predictions more easily than they could individually.
  • Strategic Improvement: Counter-intuitively, strategic behavior can be beneficial. If the system is well-designed, the effort users exert to change their features can align with the system's underlying goals, potentially leading to higher accuracy than in non-strategic environments.

Differentiable Robust Training

To defend against strategic manipulation, the authors propose a differentiable framework that anticipates user responses during training. They derive a closed-form, differentiable "projection-like" operator that calculates the optimal user move. By stacking these operators into $T$ layers, the training process simulates multiple rounds of user responses, allowing the GNN to account for long-term cascades.

Experimental Results

The framework was evaluated on standard citation networks (Cora, CiteSeer, PubMed) and synthetic datasets.

Performance analysis: (Left) Accuracy vs. graph reliance ($\alpha$), showing the robust model's stability compared to naive models. (Right) Accuracy vs. decision threshold ($b$), illustrating how increasing training rounds ($T$) improves performance.

Key Findings

  1. Robustness Recovery: On the Cora dataset, a naive GNN's accuracy drops to ~52% under strategic pressure. The robust GNN recovers this to ~77%.
  2. The Importance of Depth: In high-influence settings, training with multiple response rounds ($T > 1$) is critical. On synthetic data with high graph reliance, using $T=4$ instead of $T=1$ improved performance by approximately 11%.
  3. Centrality Awareness: The robust model naturally learns to discount the influence of highly central nodes, which are the most likely triggers for large-scale cascades.

Conclusion and Ethical Considerations

While this work provides a path toward robust GNNs, it currently relies on the linearity of SGC and assumes users have perfect information about the classifier. Furthermore, the authors highlight the ethical risks of using social data for consequential decisions, noting that robust learning must be balanced with transparency to prevent unfair discrimination based on social circles.

Summary updated

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 \emph{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.
BibTeX
@inproceedings{eilat2023strategic,
  author = {Itay Eilat and Ben Finkelshtein and Chaim Baskin and Nir Rosenfeld},
  title = {{Strategic Classification with Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=TuHkVOjSAR},
}
Figure