Author name cluster

Sixie Yu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

ICLR Conference 2025 Conference Paper

Adversarial Machine Unlearning

Zonglin Di
Sixie Yu
Yevgeniy Vorobeychik
Yang Liu 0018

This paper focuses on the challenge of machine unlearning, aiming to remove the influence of specific training data on machine learning models. Traditionally, the development of unlearning algorithms runs parallel with that of membership inference attacks (MIA), a type of privacy threat to determine whether a data instance was used for training. However, the two strands are intimately connected: one can view machine unlearning through the lens of MIA success with respect to removed data. Recognizing this connection, we propose a game-theoretic framework that integrates MIAs into the design of unlearning algorithms. Specifically, we model the unlearning problem as a Stackelberg game in which an unlearner strives to unlearn specific training data from a model, while an auditor employs MIAs to detect the traces of the ostensibly removed data. Adopting this adversarial perspective allows the utilization of new attack advancements, facilitating the design of unlearning algorithms. Our framework stands out in two ways. First, it takes an adversarial approach and proactively incorporates the attacks into the design of unlearning algorithms. Secondly, it uses implicit differentiation to obtain the gradients that limit the attacker's success, thus benefiting the process of unlearning. We present empirical results to demonstrate the effectiveness of the proposed approach for machine unlearning.

Details

UAI Conference 2022 Conference Paper

Learning binary multi-scale games on networks

Sixie Yu
P. Jeffrey Brantingham
Matthew Valasik
Yevgeniy Vorobeychik

Network games are a natural modeling framework for strategic interactions of agents whose actions have local impact on others. Recently, a multi-scale network game model has been proposed to capture local effects at multiple network scales, such as among both individuals and groups. We propose a framework to learn the utility functions of binary multi-scale games from agents’ behavioral data. Departing from much prior work in this area, we model agent behavior as following logit-response dynamics, rather than acting according to a Nash equilibrium. This defines a generative time-series model of joint behavior of both agents and groups, which enables us to naturally cast the learning problem as maximum likelihood estimation (MLE). We show that in the important special case of multi-scale linear-quadratic games, this MLE problem is convex. Extensive experiments using both synthetic and real data demonstrate that our proposed modeling and learning approach is effective in both game parameter estimation as well as prediction of future behavior, even when we learn the game from only a single behavior time series. Furthermore, we show how to use our framework to develop a statistical test for the existence of multi-scale structure in the game, and use it to demonstrate that real time-series data indeed exhibits such structure.

Details

IJCAI Conference 2021 Conference Paper

Altruism Design in Networked Public Goods Games

Sixie Yu
David Kempe
Yevgeniy Vorobeychik

Many collective decision-making settings feature a strategic tension between agents acting out of individual self-interest and promoting a common good. These include wearing face masks during a pandemic, voting, and vaccination. Networked public goods games capture this tension, with networks encoding strategic interdependence among agents. Conventional models of public goods games posit solely individual self-interest as a motivation, even though altruistic motivations have long been known to play a significant role in agents' decisions. We introduce a novel extension of public goods games to account for altruistic motivations by adding a term in the utility function that incorporates the perceived benefits an agent obtains from the welfare of others, mediated by an altruism graph. Most importantly, we view altruism not as immutable, but rather as a lever for promoting the common good. Our central algorithmic question then revolves around the computational complexity of modifying the altruism network to achieve desired public goods game investment profiles. We first show that the problem can be solved using linear programming when a principal can fractionally modify the altruism network. While the problem becomes in general intractable if the principal's actions are all-or-nothing, we exhibit several tractable special cases.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Design and Analysis of Networks under Strategic Behavior

Sixie Yu

Networks are enablers, allowing the diffusion of valuable information. But just as a network is a conduit for valuable information, so it is for misinformation. One major challenge in a networked environment is limiting the spread of misinformation. Consider a large online social network, such as Twitter. Unethical users spread anti-social posts, which negatively affect other users and damage community dynamics [6], fraudsters send spam and phishing emails that threaten people’s financial security [7], accounts occupied by malicious parties spread toxic information (e. g. , hate speech, fake news), stirring up controversy and manipulating political views among social network users [1], fake reviews posted by bots mislead consumers’ decision making [15], etc. An intuitive idea to limit the spread of misinformation is removing malicious nodes from networks, for example, terminate accounts on Twitter that spread spam. Importantly, a principled method to decide which nodes to remove from a network has wide applications; in the case of infectious disease, the inoculation of a group of people is essentially “removing” them from the contagion network [2, 5, 8, 12, 16–19]. A critical observation is that the loss associated with a decision whether to remove a node depends both on the node’s likelihood of being malicious and its local network structure. Consequently, the typical approach in which we simply classify nodes as malicious or benign using a threshold on the associated maliciousness probability [10] is inadequate, as it fails to account for network consequences of such decisions. Rather, the problem is fundamentally about choosing which subset of nodes to remove, as decisions about removing individual nodes are no longer independent. We developed a model that provides decisions about which nodes to remove [20]. The model considers both the likelihood of nodes being malicious and their local network structures. Several algorithmic insights are derived from studying the model, including hardness results, as well as approximation algorithms. Our ongoing effort focuses on making the model scalable to large-scale networks. Another challenge in a networked environment arises when taking individuals’ strategic behavior into account. When facing strategic individuals, game theory is a powerful tool to model their interaction. Many game-theoretic models have been proposed to model strategic behavior on networks, e. g. , graphical games [13], networked public goods game [3, 4, 11], etc. Among these models, the research on equilibrium outcomes has attracted much attention. In particular, equilibrium outcomes are not always socially preferable. When the equilibrium outcomes are not socially preferable, a principal may be interested in changing the parameters of the game Proc. of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), U. Endriss, A. Nowé, F. Dignum, A. Lomuscio (eds.), May 3–7, 2021, Online. © 2021 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved. so as to induce equilibrium outcomes that are better aligned with the social interest. Changing the payment structure is one way to promote preferable equilibria, as in traditional mechanism design, or the structure of information available to the players [9], another parameter subject to change is the network structure itself. A prominent challenge in a networked environment is to induce desirable equilibrium outcomes through modifying network structures. We initiated an algorithmic study of network structure modifications in networked public goods games with binary actions, with the goal of inducing equilibrium outcomes with desirable properties [14, 21]. Such desirable properties are application dependent, for example, in the case of crime prevention, it would be desirable to encourage as many individuals in a community to invest in safety service as possible. From a wider perspective, our study is categorized into network design. One interpretation of network design is through the lens of optimization, that is, a principal has an objective in mind and she optimizes over the underlying network to achieve the objective. Many interesting questions arise from the angle of optimization, for example, what is the objective, how should we define the feasible region of the modifications, is the design choice robust, etc. These questions consist of our ongoing and future research plan.

PDF

AAAI Conference 2020 Conference Paper

Computing Equilibria in Binary Networked Public Goods Games

Sixie Yu
Kai Zhou
Jeffrey Brantingham
Yevgeniy Vorobeychik

Public goods games study the incentives of individuals to contribute to a public good and their behaviors in equilibria. In this paper, we examine a speciﬁc type of public goods game where players are networked and each has binary actions, and focus on the algorithmic aspects of such games. First, we show that checking the existence of a pure-strategy Nash equilibrium is NP-complete. We then identify tractable instances based on restrictions of either utility functions or of the underlying graphical structure. In certain cases, we also show that we can efﬁciently compute a socially optimal Nash equilibrium. Finally, we propose a heuristic approach for computing approximate equilibria in general binary networked public goods games, and experimentally demonstrate its effectiveness. Due to space limitation, some proofs are deferred to the extended version1.

PDF Details

AAMAS Conference 2019 Conference Paper

Adversarial Coordination on Social Networks

Chen Hajaj
Sixie Yu
Zlatko Joveski
Yifan guo
Yevgeniy Vorobeychik

Extensive literature exists studying decentralized coordination and consensus, with considerable attention devoted to ensuring robustness to faults and attacks. However, most of the latter literature assumes that non-malicious agents follow simple stylized rules. In reality, decentralized protocols often involve humans, and understanding how people coordinate in adversarial settings is an open problem. We initiate a study of this problem, starting with a human subjects investigation of human coordination on networks in the presence of adversarial agents, and subsequently using the resulting data to bootstrap the development of a credible agentbased model of adversarial decentralized coordination. In human subjects experiments, we observe that while adversarial nodes can successfully prevent consensus, the ability to communicate can significantly improve robustness, with the impact particularly significant in scale-free networks. On the other hand, and contrary to typical stylized models of behavior, we show that the existence of trusted nodes has limited utility. Next, we use the data collected in human subject experiments to develop a data-driven agent-based model of adversarial coordination. We show that this model successfully reproduces observed behavior in experiments, is robust to small errors in individual agent models, and illustrate its utility by using it to explore the impact of optimizing network location of trusted and adversarial nodes.

PDF

AAMAS Conference 2019 Conference Paper

Removing Malicious Nodes from Networks

Sixie Yu
Yevgeniy Vorobeychik

A fundamental challenge in networked systems is detection and removal of suspected malicious nodes. In reality, detection is always imperfect, and the decision about which potentially malicious nodes to remove must trade o� false positives (erroneously removing benign nodes) and false negatives (mistakenly failing to remove malicious nodes). However, in network settings this conventional tradeo� must now account for node connectivity. In particular, malicious nodes may exert malicious in�uence, so that mistakenly leaving some of these in the network may cause damage to spread. On the other hand, removing benign nodes causes direct harm to these, and indirect harm to their benign neighbors who would wish to communicate with them. We formalize the problem of removing potentially malicious nodes from a network under uncertainty through an objective that takes connectivity into account. We show that optimally solving the resulting problem is NP-Hard. We then propose a tractable solution approach based on a convex relaxation of the objective. Finally, we experimentally demonstrate that our approach signi�cantly outperforms both a simple baseline that ignores network structure, as well as a state-of-the-art approach for a related problem, on both synthetic and real-world datasets.

PDF

AAMAS Conference 2018 Conference Paper

Adversarial Classification on Social Networks

Sixie Yu
Yevgeniy Vorobeychik
Scott Alfeld

The spread of unwanted or malicious content through social media has become a major challenge. Traditional examples of this include social network spam, but an important new concern is the propagation of fake news through social media. A common approach for mitigating this problem is by using standard statistical classification to distinguish malicious (e. g. , fake news) instances from benign (e. g. , actual news stories). However, such an approach ignores the fact that malicious instances propagate through the network, which is consequential both in quantifying consequences (e. g. , fake news diffusing through the network), and capturing detection redundancy (bad content can be detected at different nodes). An additional concern is evasion attacks, whereby the generators of malicious instances modify the nature of these to escape detection. We model this problem as a Stackelberg game between the defender who is choosing parameters of the detection model, and an attacker, who is choosing both the node at which to initiate malicious spread, and the nature of malicious entities. We develop a novel bi-level programming approach for this problem, as well as a novel solution approach based on implicit function gradients, and experimentally demonstrate the advantage of our approach over alternatives which ignore network structure.

PDF

ICML Conference 2018 Conference Paper

Adversarial Regression with Multiple Learners

Liang Tong
Sixie Yu
Scott Alfeld
Yevgeniy Vorobeychik

Despite the considerable success enjoyed by machine learning techniques in practice, numerous studies demonstrated that many approaches are vulnerable to attacks. An important class of such attacks involves adversaries changing features at test time to cause incorrect predictions. Previous investigations of this problem pit a single learner against an adversary. However, in many situations an adversary’s decision is aimed at a collection of learners, rather than specifically targeted at each independently. We study the problem of adversarial linear regression with multiple learners. We approximate the resulting game by exhibiting an upper bound on learner loss functions, and show that the resulting game has a unique symmetric equilibrium. We present an algorithm for computing this equilibrium, and show through extensive experiments that equilibrium models are significantly more robust than conventional regularized linear regression.

Details