Learning Strategic Network Emergence Games

Rakshit Trivedi, Hongyuan ZhaNeurIPS 2020 · OpenReview

Most machine learning models for network analysis—such as predicting who will follow whom on social media—rely heavily on stochastic assumptions. They treat link formation as a series of probabilistic events based on structural properties like "clustering" or "diameter." However, real-world networks, from international trade agreements to corporate hierarchies, are often the result of strategic behavior. Agents (humans, companies, countries) are "selfish" actors who form links to maximize their own benefits.

Existing game-theoretic models for these "Network Emergence Games" are usually hand-designed by researchers based on intuition. This manual approach makes them prone to misspecification and prevents them from learning directly from complex, real-world data. To bridge this gap, researchers have proposed MINE (Multi-agent Inverse models of Network Emergence mechanism), a novel framework that treats network formation as a strategic game and "reverse-engineers" the hidden payoff functions driving agents to form links.

The MINE Methodology

MINE models network creation as a sequential Markov game, moving away from simple probability to a framework of strategic intent and mutual consent.

  1. The Game of Mutual Consent: At each step, $n$ players (nodes) announce their intentions to form links based on the current state of the network. Crucially, a link is only formed or maintained if there is "mutual consent" between two agents, reflecting the reality of many social and professional networks.
  2. Multi-Agent Inverse Reinforcement Learning (IRL): Instead of manually defining the rewards, MINE uses Multi-Agent IRL (building on the MA-AIRL algorithm) to discover the latent reward function—the payoff mechanism—that makes the observed network look like a strategic equilibrium.
  3. Bounded Rationality: To handle the mathematical complexity of finding an equilibrium in a changing network, MINE utilizes Markov Quantal Response Equilibrium (MQRE). This concept accounts for "bounded rationality," acknowledging that while agents make mostly optimal decisions, they can occasionally make small errors or "noisy" choices.
  4. Differentiable Architecture: Graph Neural Networks (GNNs) are used to represent the state of the network, and a continuous action space represents agent intentions. This makes the entire process differentiable and capable of generalizing to unseen nodes.

Key Insights: Interpretability and Strategic Logic

By learning the why (the reward function) rather than just the what (the link probability), MINE provides a much deeper level of interpretability.

Interpretability analysis on the Australian Bank dataset, showing the network structure, learned payoff matrix, and the relationship between agent reward and Katz centrality.

For example, when applied to a dataset of an Australian Bank's personnel hierarchy, you can examine the learned reward to see that a bank teller values links with managers differently than links with other tellers. Furthermore, because MINE learns a reward function based on agent attributes via GNNs, it achieves strategic generalization. You can train the model on one group of agents and use that learned "strategic logic" to predict how a completely different group of agents might form a network.

The paper evaluates MINE across a diverse range of synthetic and real-world networks, including Zachary’s Karate Club, the Australian Bank, and massive datasets like Andorra Phone Calls.

Experimental results showing high correlation (PCC) with ground-truth rewards in a synthetic game (a) and successful strategic link recovery in the Karate Club network (b).
  • High Fidelity: In synthetic tests with a known ground-truth reward function, MINE’s learned rewards demonstrated a high correlation (Pearson Correlation Coefficient of ~0.82) with the actual rewards.
  • Superior Link Recovery: On the classic Zachary's Karate Club dataset, MINE recovered 72-81% of the original strategic links. Crucially, it assigned much higher utility to the real network than to "perturbed" versions that looked structurally similar but were strategically nonsensical.
  • Effective Transfer Learning: The authors demonstrated that MINE could be trained on just 100 nodes of the massive Andorra dataset (32k nodes, 513k edges) and successfully transfer those learned rewards to the full network, achieving similar performance with significantly less training time.
  • Competitive Prediction: In strategic link prediction tasks across financial and co-authorship networks, MINE consistently outperformed or matched state-of-the-art game-theoretic baselines.

Limitations and Future Directions

While MINE represents a significant step forward in modeling strategic network emergence, it has limitations. The model struggled slightly with bipartite networks (like a movie director-actor network), suggesting that such networks may require more specific structural constraints encoded into the model. Additionally, finding equilibria in extremely large, dense games remains a significant computational challenge.

Finally, while MINE offers deep interpretability, translating the learned neural reward functions into human-readable strategic rules currently requires manual qualitative analysis. Future work focusing on automated interpretability could make these strategic insights even more accessible to researchers and practitioners.

Summary updated

Abstract

Real-world networks, especially the ones that emerge due to actions of animate agents (e.g. humans, animals), are the result of underlying strategic mechanisms aimed at maximizing individual or collective benefits. Learning approaches built to capture these strategic insights would gain interpretability and flexibility benefits that are required to generalize beyond observations. To this end, we consider a game-theoretic formalism of network emergence that accounts for the underlying strategic mechanisms and take it to the observed data. We propose MINE (Multi-agent Inverse models of Network Emergence mechanism), a new learning framework that solves Markov-Perfect network emergence games using multi-agent inverse reinforcement learning. MINE jointly discovers agents' strategy profiles in the form of network emergence policy and the latent payoff mechanism in the form of learned reward function. In the experiments, we demonstrate that MINE learns versatile payoff mechanisms that: highly correlates with the ground truth for a synthetic case; can be used to analyze the observed network structure; and enable effective transfer in specific settings. Further, we show that the network emergence game as a learned model supports meaningful strategic predictions, thereby signifying its applicability to a variety of network analysis tasks.
BibTeX
@inproceedings{trivedi2020learning,
  author = {Rakshit Trivedi and Hongyuan Zha},
  title = {{Learning Strategic Network Emergence Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=kTHn2_I4WM3},
}
Figure