Learning to Infer the Structure of Network Games
Authors: Emanuele Rossi
Federico Monti
Yan Leng
Michael M. Bronstein
Xiaowen Dong
Venue: ICLR 2022 Submitted (2022)
Keywords: graphs
networks
game theory
graph neural networks

Abstract: Strategic interactions between a group of individuals or organisations can be modelled as games played on networks, where a player's payoff depends not only on their actions but also on those of their neighbors. 
Inferring the network structure from observed game outcomes (equilibrium actions) is an important problem with numerous potential applications in economics and social sciences. 
Currently available methods require the knowledge of the utility function associated with the game, which is often unrealistic to obtain in real-world scenarios. To address this limitation, we propose a novel transformer-like architecture which correctly accounts for the symmetries of the problem and learns a mapping from the equilibrium actions to the network structure of the game without explicit knowledge of the utility function. We test our method on three different types of network games using both synthetic and real-world data, and demonstrate its effectiveness in network structure inference and superior performance over existing methods.

Under review as a conference paper at ICLR 2022
LEARNING TO INFER THE STRUCTURE OF NETWORK GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
Strategic interactions between group of individuals or organisations can be modelled as games played on networks, where player's payoff depends not only on their actions but also on those of their neighbors. Inferring the network structure from observed game outcomes (equilibrium actions) an important problem with numerous potential applications in economics and social sciences. Existing methods mostly require the knowledge of the utility function associated with the game, which is often unrealistic to obtain in real-world scenarios. To architecture which
address this limitation, we propose a novel transformer-De correctly accounts for the symmetries of the problem and learns mapping from the equilibrium actions to the network structure of the game without explicit knowledge of the utility function. We test method on three different types of network games using both synthetic and real-world data, and demonstrate its effectiveness in network structure inference and superior performance over existing methods.
INTRODUCTION
Individuals organizations cooperate with compete against each other in a wide range of practical situations. Strategic interactions between individuals are often modeled as games played on networks, where an individual's utility depends not only on their actions (and characteristics) but also on those of their neighbors. In network game (and games in general), the utility function is of fundamental importance, as rational agents maximize their utilities when making real-life decisions. The current literature on network games has primarily focused on the scenarios where the utility function is predefined, and the structure of the network (represented by a graph) is known beforehand. However, in practical settings, while it is common to observe the actions of the players, the underlying interaction network and the utility function remain hidden. This makes challenging to exploit network information and utility function for behavioral predictions and network-based interventions (e.g., marketing campaigns or information diffusion).
In this paper, focus the problem of inferring the structure of the interaction network from observed equilibrium actions of a network game, A few recent studies have tackled similar problems (Irfan & Ortiz] 2011 Honorio & Ortiz 2015; Ghoshal & Honorio 2017a by Garg & Jaakkola 2016) 2017] Barik & Honorio 2019;2000] Leng et al.] 2020); however, several major limitations remain. First, all these methods require the explicit knowledge of the utility function infer the underlying
network structure, which may be impractical to assume and may also change over time. The work
Honorio & Ortiz (2015) considers more general hypothesis space of games for linear influence game, but they only focus on binary actions and linear payoffs. Second, the methodology in each of these studies has been designed for the specific game under consideration, thereby limiting its scope in handling wide range of strategic interactions in real-world scenarios.
To address these limitations, we first summarise three common network games studied in the recent literature in a generic form, which is based on both individual and network factors that impact one's utility and the corresponding equilibrium actions. Despite the different nature of the games, it permits the relation between the equilibrium actions and network structure to be written in unified manner. This motivates us to propose a data-driven model where we learn the functional mapping between the equilibrium actions and network structure without explicit knowledge about the utility function of the game. Our model is based on an encoder-decoder approach where the encoder is a transformer architecture and the decoder can be chosen flexibly, and is trained using pairs of actions and network

---

Under review as a conference paper at ICLR 2022
Unear Quadratic
Linea Influence
Figure 1:
Example actions for different types of games on a Barabási-Albes graph. Actions are normalized to be in [-1, 1] and are displayed as colors nodes.
structures, Once trained, the model can be deployed to infer the network structure from only observed actions. Synthetic and real-world experiments demonstrate the superiority of our method against several sate-offtheeart approaches.
Main contributions. First, we compare three network games using a unified parameterization. which helps reveal the different nature of these games and interpret the strategic interactions they represent. Second, to our knowledge, our framework is one the first to infer the network structure behind the games without knowing the utility function. This capability is important in real-world sce- narios where the nature of the interactions remains hidden or may even evolve over time. Finally, our work contributes the emerging field of data-driven structural inference by proposing model based on a novel permutation-invarice
transformer architecture. Such a framework may find numerous applications in diverse domains transportation, social, biological, and financial network analysis.
2 SETTING
In this section, we start by analysing three commonly studied network games (Sections 1 and 2.2). Based on the specific utility function of these games, we establish generic relationship between the equilibrium actions and network structure (Section 2.3), which eventually motivates the proposed framework that learns network structure without any knowledge of the utility function (Section 3).
2.1 CONTINUOUS- ACTION NETWORK GAMES
Consider network of N individuals represented by weighted and undirected graph G(V, E), where and denote the node and edge sets, respectively. For any pair individuals i and j. wij Wye >> 0 if ji, & and Way Wjs 0 otherwise, where Way is the ij-th entry of the adjacency matrix W. this work, we assume the graph G is connected, and consider the normalized adjacency
matrix A D 1 WD- where = diag( W1), where 1 is an N-dimensional vector of ones. In network game, the payoff u, of an individual depends on their action æ; as well as the actions of neighbors j E Ng. We consider three commonly studied network games: linear quadratic games (Ballester et al., 2006), variation of the linear influence games developed in Irfan & Ortiz (011)) and the graphical game studied in Barik & Honorio (2019) (which we will refer to as Barik Honorio or BH graphical game).
Linear quadratic games. Linear quadratic games are widely studied in the economics literature
(Jackson & Zenou 2014 Ballester et al. (006). In this game, a player chooses their action by
maximizing the following utility function:
max u, = b,x; 2 + 3 Σ aIj (x,]
(I)
JeN:
where by represents the marginal benefit of by taking action v; and 3 is the strength of dependencies between actions of neighbors in the network, respectively. Note that this utility function can also be thought of as a second-orde approximation to non-linear utility functions of more complex games. The pure-strategy Nash equilibrium (PSNE) of this game is
3AA) b
2

---

Under review as a conference paper at ICLR 2022
where x* and b are N-dimensional vectors collecting actions and marginal benefits for all individuals, and is the x N identity matrix. Under the assumption that |3| < 1, the matrix inverse is guaranteed to exist the spectral radius of A is 1. Furthermore, when 3 >> 0, the game corresoonds to strategic complement relationship (i.e., intuitively, the incentive of a player to take a higher action is increasing in the number of their neighbors also taking higher action); when / 0, it corresponds strategic substitute (i.e., intuitively, the incentive of a player to take a higher action is decreasing in the number of their neighbors also taking higher action).
Linear inftuence games. Inspired by the threshold model (Granovetter 1978 Irfan & Ortiz (2011) proposed the linear influence games, where an individual chooses the action that maximizes the following utility function
Σ CbyI, b,r;; JeN
u4
{
where bN can understood as a threshold parameter for i's level of tolerance for negative effects. Under the assumption that A is invertible, the PSNE satisfies the following condition:
A "b.
BH graphical game. Finally, in the specific graphical game introduced in Barik & Honorio (2019). an individual maximizes the following utility function:
max {
Σ JeV
a.y2y
(5)
This utility can be used to model games where an individual prefers to conform to the social norm (actions of their neighbors), since their utility decreases their action deviates from those of their neighbors. The PSNE for this game satisfies the following condition:
x
AAx
(6)
This suggests that x* is the eigenvector un of A which associated with the largest eigenvalue (which is 1). We consider actions from the set of c-PSNE (Barik & Honorio 2019). which are
obtained by adding noise independently per player. The observed actions x are: X x e, where
is sub-Gaussian n
Table I: Parameterization of three network games considered in the paper.
By investigating equations equation equation 4 and equation 6 we can write the condition for the equilib- rium actions x" in a generic form (we tacitly assume that | < 1 and A is invertible, see Table I
F(A)
H(b)
Linear quadratic
(I 3A)
b
Linear influence
A
b
x = H(b),
Barik-Honorio
u1
where F(A) is function of the network structure and H((b) is function of additional parameters (if any) associated with the game. That is, F(A) accounts for the influence from the actions of
one's neighbors in the network. Conversely, H(b) is only affected by one's idiosyncratic (individual) characteristics.
2.2 MODELING OF INDIVIDUAL IDIOSYNCRATIC CHARACTERISTICS
Under the linear quadratic or linear influence games, the parameter b captures the marginal benefits or tolerance levels as idiosyncratic characteristics of players in the corresponding games. In the presence of the homophily effect (McPherson et al. (2001), we may assume that this parameter is associated with the network structure. To this end, we propose to model b as follows:
(8) where L = - A is the normalized graph Laplacian matrix, and represents pseudoinverse in case the matrix is not invertible (this happens when parameter a E [0, 1] controls the relation of the individual idiosyncratic characteristics to the network structure. The two corner cases 0 (for which we have Lg I), and a 1 (when L, L) correspond to independent idiosyncratic characteristics and homophilous idiosyncratic characteristics (individuals with similar characteristics tend be connected), respectively. By varying a from 0 to we can achieve increasing levels of homophily.
b NN Lt),, L = (1 - a+)++al + aL
1 L has smallest eigenvalue of 0). The
The actions are discrete the originally proposed game. We adapt the game to contimuous setting. variables include Gaussian variahles, any bounded random variable (e.g. Bernoulli, uniform), any random variable with strictly log-concave density, and any finite mixture of nub-Gaussian variables.
3

---

Under review as a conference paper at ICLR 2022
2.3 ANALYSIS OF EQUILIBRIUM ACTIONS
With the conditions for equilibrium actions in Section 2.1 and the modeling of individual idiosyncratic characteristics in Section 2.2 we can analyze explicitly the characteristics of these actions.
Linear quadratic games. Assuming b of the form equation g and using Eq. equation 2 and
I A, we have that the equilibrium actions x* follow multivariate Gaussian distribution:
x ~ No N (I BA) ' ( (I- aA) (I- (I- -A)
~ =
UI(I ((([I-B)](C (I- -[
(9)
with the eigendecomposition A = UAUT. Eq. equation 9 illustrates the relationship between the actions x and the network structure A and motivates the learning framework proposed in the next section. Furthermore, the covariance in Eq. equation | may be interpreted as a graph filter whose frequency response [1-xA) may shed light on the behavior of the actions. For 3 1 and a - 1, the action vector x tends to behave like the leading eigenvectors of A ('low frequency"), which are smooth on the grapt An example of the filter response (with 3 = 0.8 and 0.8) applied on the cigenvalues of an instance of a 20-node Erdōs-Rényi graph is shown in Fig. (blue). This shows that Linear-qudralie games the actions are dominated by the leading eigenvector of which is smooth.
Linear influence games. Similarly, from Eqs. equation Aquationnandd equation g we have that the equilibrium actions x follow a multivariate Gaussian distribution:
-- = UJA -U (-
x ~
(10)
Interpreting Eq. equation
10 as a spectral filter of the form x²(1-axj we can also conclude that an 1 leads to smoother actions on the graph. However, the behavior of actions in this case depends on the magnitude of the eigenvalue of A closest to O. Given that the spectrum of A lies in the range of [-1, 1], the actions are likely behave like mid-spectrum eigenvectors, which not necessarily smooth signals on the graph. Similarly, this can be seen from the filter response, under 0.8, shown in Fig. (red). This shows that in linear influence games the actions are dominated by mid-spectrum eigenvectors which are not necessarily smooth
BH graphical game. We see from Eq. equation 6 that the
Trav ivikence
equilibrium actions correspond to the largest eigenvector u, of A. Although in this setting the observed actions are e-PSNE, they will still be quite smooth on the graph.
tog tlerr cospurss
In summary, our analysis in this section shows that the smooth- ness of the equilibrium actions on the graph depends on 3 and in the linear quadratic game. The actions in linear influ- ence game are likely to be nonsmooth, whereas those in the BH graphical game are likely to be smooth. We empirically validate this analysis in Section 5.1 Regardless of the smooth- ness, the relationship between the equilibrium actions and the network structure demonstrated in this section motivates us to propose a learning framework in the next section to infer network the structure from the observed actions.
20
digemaaue Indes
Figure 2: Interpreting actions of lin- ear quadratic/influence games: the equilibrium actions for the two games are dominated by different sets of eigenvectors.
PROPOSED APPROACH
Motivated by the analysis in Section 2.3 we propose model that learns direct mapping from the observed actions to the network structure. Such a model is agnostic to the utility function of the game and avoids strong assumptions on the utility function.
In our setting, we assume to have a training set D of action-graph pairs (x(*) A (8) coming from games with the same (but unknown) utility function. The model takes as input an x K matrix X containing the actions of N players over K independent games as columns, and outputs a predicted N N adjacency matrix Å (X) for the network game. Once trained, our model can then
By 'smoothness' here understand the Dirichlet energy of the features, trace (X LX).
4

---

Under review as a conference paper at ICLR 2022
infer the network structure corresponding to previously unseen actions, as long as they generated following a similar utility function. Moreover, this framework makes our model generalizable to learning networks with the number of nodes different from what observed during training.
The model parameters are learned such that they minimize the cross entropy between the binary ground truth adjacency matrix and the predicted continuous one:
N
[()))
Σ
Σ
(f) Bij (log(ge (X ())) + (1- 2
(1 (1
log(ge (x(() (11)
D (A JED f,1=1
Binary cross-entrope is standard loss function for link prediction tasks using graph neural networks (Hamilton et al., 2017), of which our problem is an instance. We tried weighting the loss based on the proportion of edges in the graph, but it did not change the performance of the model.
Our model follows an encoder-decoder architecture ge (X) dec(enc( X)), which is standard solution for tink-prediction problems in graph neural networks (Kipf & Welling, (016) since the resulting number of parameters of the model is independent on the size of the graph, allowing for more statistical efficiency, and for the same model to work graphs of different sizes. The encoder outputs an N x K x F tensor Z enc(X), mapping each node i in game to an F-dimensional latent embedding Zik- The decoder outputs the predicted N x N adjacency matrix Á = doc(Z), (Z), where the score diş for each edge (i.j) is computed using the K F-dimensional embeddings Zi, Zj of the respective nodes.
Given that the ordering of nodes in the graph is arbitrary, the model has to be a permutation- equivariant (Bronstein et al., 2021) function over the set of nodes: g = Pige (X)P[. where P1 an N x N permutation matrix interpreted as reordering of the nodes of the graph. Additionally, in the case where there is no correspondence between game k in one graph and game in another one (e.g. actions corresponding to user rating where however users in different graphs have rated different items), the model should also be permutation-ineee invariant over the set of games, i.e.
ge (XP2 ge X), where P2 is another x permutation matrix on the games. Overall, this combined symmetry condition can be written as (P)2)) Pige (X)PI.
Encoder The input to our model is a variable-length set (of actions), which excludes using a multi-layer perceptron (since it would not be able to handle the variable length) and sequence models such as LSTMs (Hochreiter & Schmidhuber 1997) or GRUs (Cho et al. 2014) (since they treat the input an ordered sequence, while it is undordd set). Moreover, since the ground truth graph between the players is not known a priori, but it is however important for the model to exchange information between players (as the values of agents' actions are meaningless if not compared the ones of the others), the encoder needs to perform message passing on the fully connected graph of players. Therefore, we propose Transformer-like (Vaswani et al.. 2017) encoder (which we refer to as Network Game Transformer or NuGgeT). NuGgeT processes a set of games happening on a given network and outputs for each node set of K different game-specific embeddings (one for each game that happens on the network). In this architecture, the value of action never mixed with the actions of other players in a different game k', if not for the computation of an aggregated attention score Cij that captures the overall similarity between players. Intuitively, in settings where we are given the outcomes of multiple games played on multiple graphs, there is no correspondence between such games. Thus, the value of action does not bring any information about the role of a node in a graph and the only useful information that needs to be exchanged across games is the similarity of the nodes.
of player i in game k is
Specifically, for each node 1,...,N N and game 1,..., K, the embedding 2 is computed as follows:
Yik RRRUU(Zz + b)
w. b R
K
(b) softmax,
Yik
w
(K)
W
(8)
yzk)
w (h) FXF W e Fxx
N
N
Zik- = 2b Viks
(H) di yik
(12)
where denotes general permutation-invariie aggregation operator (e.g max, mean Σ
K Σ 1) 1b is some learnable function, w. b, ((()) and wi(k) Q learnable parameters, and
5

---

Under review as a conference paper at ICLR 2022
h h= L..... H denotes the attention heads. For generic node in game k. NuGgeT first expands i's action Tik into a vector Yık of F features, it then computes H attention scores (one for each head) for each pair of nodes (i. via multiplicative attention on the expanded actions y. y (aggregating the unnormalized scores across games) and finally refines vector yık via function ui that processes the H aggregated representation of the neighbors obtained from the attention mechanism.
Decoder In the case of directed graphs, there is no specific requirement for the decoder. If the graph is undirected, and therefore the adjacency matrix is symmetric, the decoder should be symmetric w.r.t pairs of nodes (i.c., (i,j) and (j.i) treated the same way). Additionally, we impose invariance w.r.t ordering of the games. NuGgeT"s decoder computes the predicted adjacency âig by aggregating the game-specific embeddings computed in (12) for pair of nodes (i, using general permutation- invariant aggregation operator
I which is then passed through a learnable function ah:
K
dig- = 2
Zide ② ZjR)
(13)
Here + denotes element-wise product, whose use ensures symmetry w.r.t. node pairs (since Z, O 2jk = Zjk O z.),, while the permutation invariant operator over & ensures invariance to the ordering of games. We empirically observe this approach to work better compared to simpler permutation- invariant functions such as the dot product of the concatenation of the games embeddings. In the SM we prove that NuGgeT satisfies the symmetry conditions outlined above.
RELATED WORK
Network games, class of problems in game theory, have been studied extensively in computer science and economics. The majority of works in the network game literature study the characteristics of games on a known and static graph (Ballester et al. 2006] Bramoullé al. 2014). While these studies useful in understanding collective actions and designing interventions (Galcotti et al.) 2017). is increasingly acknowledged that networks are difficult to obtain in practice. Furthermore, the utility function associated with the game is usually unknown well. We interested in the inverse problem of inferring the network structure based on observed actions. This inverse setting related graph or network inference, a problem that has attracted interest in statistics (Koller & Friedman 2009; Friedman et al. (2008)). physics (Gomez-Rodriguee et al.) 2010 Gooez-Rodriguez al. 201 D. signal processing (Mateos al. 2019 Dong al.) 2019). Our study differs from these works in accounting for the strategic interactions and the game theoretical framework underlying the observed data.
Deep learning models have been recently proposed for latent graph inference, c.g. structural learning problem infer DAG from the observed actions (Yu et al. 2019 Zheng et al., 2020). However, these approaches are limited to predicting acyclic graphs, whereas the graphs we are interested in are often cyclic. Kipf et al. (2018) proposed a graph neural network (GNN) model to infer the interactions of an underlying dynamical system from observational data. Differently from this work, their model is trained on predicting the future state of the system, rather than the network interactions themselves. In latent graph learning (Cosmo et al. 2020a b) Wang et al.) 2219)), the graph is learnt jointly with a downstream task, conversely to our scenario where there is no downstream task. The method of Belilovsky et al. 2017) is the mostly related to ours, since they propose supervised model to infer an undirected graphical model from observed covariates using a series dilated convolutions. However, their model is not permutation-equivane
w.r.t. the order of nodes and the number of layers depends on the number of nodes. Both issues cause the statistical efficiency of the model to scale poorly with the size of the graph. Different from these studies, our framework aims to learn game-ther theoretical relationships in supervised manner, while also leveraging the structural symmetries of this problem.
Finally, there has been recent stream of literature in learning network games from actions of players (Irfan & Ortiz, 2011 Honorio & Ortiz 2015 Ghoshal & Honorio 2017a by Garg & Jaakkola 2016 2017 Barik& Honorio 2019 2020 Leng et al.) 2020). Most of these methods focus on either
'For given player i, using the expanded actions y. rather than input scalars 2. allows the attention mechanism to produce attention scores which are not necessarily linearly dependent on the value of neighbors action Tyk, thus producing richer attention scores (see Figure i2 Appendix).

---

Under review as a conference paper at ICLR 2022
binary finite discrete action space. For continuous actions, Leng et al. (2020) formulate an optimization problem to learn the structure and marginal benefits of linear quadratic games, while Barik & Honorio (2019) are aimed at inferring the network structure from
action-conformin
graphical game. Our work differs from existing methods in the literature in that it does not assume a particular game-theoretic structure. Instead, build a Transformer- like model that learns mapping from the equilibrium actions to the network structure of the games without explicit knowledge of the utility functions.
5 EXPERIMENTS
Our implementation of NugGeT uses the sum Σx_1 as the permutation-invariant functions and -. and two different 2-layer MLPs for and v. We use the Adam optimizer (Kingma & Ba 2015) with learning rate of 0.001, batch size of 100 and a patience of 50 epochs. We did not perform any particular hyperparameter tuning for our method, since we found it to be quite robust to the choice of hyperparameters and perform well with standard choices (see Appendix). In all our experiments, we report the mean and the standard error of the mean over the test graphs. Note that we ignore diagonal elements of the adjacency matrix both for training and evaluation. Since they are always zero, the model could easily memorize them, influencing the metries. We use an AWS p3. 16xlarge machine with 8 GPUs. While the training of our model takes between 5 and 10 minutes whole set of experiments conducted in the paper necessitate roughly 4 days of GPU time.
single GPU, the
5.1 SYNTHETIC DATA
Data Generation We follow the setup in Leng et al. (2020) for generating the synthetic graphs using three different random graph models: Erdos-Renyi (ER), Watts- Strts-Sttrogaz (WS), and Barabasi- Albert (BA). More details and exact parameters for the synthetic data are provided in the Appendix. All the graphs have N = 20 vertices in our experiments. For each type of graphs above, we simulate equilibrium actions for linear quadratic, linear influence, and BH graphical games using their respective utility function. For linear quadratic games, once the graphs are constructed, we compute 3 > 0 such that the spectral radius p(B.A) varies between 0 and 1. For linear influence games, when the adjacency matrix not invertible we take its Moore-Penrose pseudoinverse. For BH games,
= 0.2. The generated actions together with the groundtruth network structure are used to train the model. We use 850 graphs in the training set, 50 graphs for validation and 100 graphs for testing and verify that there is no overlap between them.
Baselines We compare with the following general baselines: Correlation, Anticorrelation. Graph- ical Lasso (Friedman et al.] 2008b) and DeepGraph (Belilovsky et al.) 2017). We also compare to game-specifie baselines: LinQuadOpt (independent) (Leng al. 2020) and LinQuadOpt (ho- mophilous) (Leng et al. (2000) for linear quadratic games, and BlockRegression (Barik & Honorio 2019) for BH Graphical Games. A more detailed description of the baselines and how they tuned is provided in the Appendix.
Results Results for Linear Quadratic Games are reported in Figure 3 Columns are different types of graphs (ER, WS, BA), rows are different values of the marginal benefits smoothness a (0, 1, results on a = 0.5 are presented in Figure in Appendix), while the x- x-axis represents the spectral radius p(3A). NuGgeT is on par or superior to other methods in all scenarios, with DeepGraph being the runner-up competitor. We observe the largest gap when a = 1, i.e. when the marginal benefits are smooth over the graph. Interestingly, it can be observed in the left-most column that both NuGgeT and DeepGraph performs well both in the case of strategic complements (o(33) O, neighbors take similar actions) and strategic substitutes (A(3 < O, neighbors take opposite actions), whereas other baselines only perform well in one of the two cases.
For Linear Influence Games, we report the results in Figure 4 Each plot corresponds to a different type of graph, and the x-axis represents the benefit smoothness As expected, all methods improve their performance as a grows, since the actions become smoother over the graph (Section 2.3) Again, NuGgeT outperforms the baselines in all scenarios. Interestingly, the performance graphs seems to be much lower than for BA graphs. This can be understood empirically by analyzing the eigenvalues of the normalized adjacency matrix A for different graphs. For WS and ER graphs,
WS and ER
7

---

Under review as a conference paper at ICLR 2022
WS grophss c-1.0
En graphs, ==6.0
BA grophs, a-0.0
Teat HOOK ARC
Candetto
Asselian
graphs, e=1.0
graphs, a=1.0
gragpssssoomm a-1.0
NeT ROC
Speciral
Spectdd Kahee
Figure 3: Results for linear quadratic games with varying a and spectral radius p(3A).
W5 graphs
En gropho
BA gropho
etheret
Figure 4: Results on linear influence games when varying the smoothness a of the marginal benefits.
the smallest absolute (non-zero) eigenvalue of A is on average much smaller than for BA graphs (Figure 7 in Appendix). As explained in section 2.3 eigenvalues with very small absolute values will result in actions behaving like mid-spectrum eigenvectors. We verify this further in Figure g in Appendix, which shows the spectral coefficients of the actions for all combinations of graphs and games. Linear Influence games on ER and WS graphs are indeed the only scenario where we empirically observe large coefficients for mid--peetrumm eigenvectors. On BA graphs we do not observe this behaviour, and instead mid-spectrum eigenvectors are most often not represented at all by the actions. This is due to BA graphs frequently having exactly zero eigenvalues for mid-spectrum eigenvectors, which are discarded when taking the pscudoinverse.
Results for BH Graphical Games are reported in Figure Appendix. Since there are no parameters controlling the game, we only have 3 configurations corresponding to different graph types. Again, NuGgeT outperforms other methods in all configurations, with the gap being largest on BA graphs. We also perform ablation studies the number of games, number of training graphs and size of the graphs. The results are presented and discussed in Appendix.
To conclude, the main advantage of our method comes from the ability of learning from data. While learning the mapping from actions to network, the model will learn not only the utility function of the games represented in the data, but also the typical structure of the networks. If all the networks in the training data are Barabasi-Albert graphs, the prediction of the model will likely also be a Barabasi-Albert graph. On the other hand, optimization methods such as LinQuadOpt are not able to automatically bias their prediction to particular class of graphs.
5.2 REAL-WORD DATA
Players in real-world scenarios often act according to strategic interactions. has been shown in the sociology and game theory literature that people have an incentive conform to social norms YYongg 2009; [Montanar & Saberi 2010) or be influenced by their social neighbors (Leng et al.) 2020). That is, individual utilities are higher if their behaviors are similar to that of their neighbors in the
8

---

Under review as a conference paper at ICLR 2022
social network. Such mechanism will lead to strategic complement relationships. Following this assumption, we validate our model on two datasets, comparing with the baseline methods introduced in section
Indian Villages The Indian Villages dataset (Banerjee et al. 2013 contains data from a survey of social networks 75 villages rural southern Karnataka, a state India. Each village constitute graph, where nodes are households and edges are self-reported friendships. Following the setup in Leng et al. (2020), we consider as actions number of rooms, number of beds and other decisions families have to make related to their house. We only consider the 48 villages for which we have the ground truth actions and network. are used for training, for validation and 5 for testing. Categorical actions are onc-hot encoded, while numerical actions are treated as continuous features. The resulting dataset has graphs with 10 actions and number of nodes ranging between 77 and 356. It can be seen from Table 2 that NuGge'l outperforms all other methods by least 5.01%. %. DeepGraph fails to learn altogether on this dataset.
Yelp Ratings The Yelp Ratings datase consists of rating of users to business, well as the social connectivity between user. From the raw data we extract 5000 sub-graphs representing communities, where the actions are the average rating of users 22 categories of businesses. The task to reconstruct the social connectivity of the users given their actions (ratings). 4250 graphs are used for training, 250 for validation and 500 for testing. More details the dataset construction are provided in the appendix. On this dataset, NuGgeTT outperforms all other baselines by at least 2. 79%. Overall, the results on real-world data show NuGgeT efficacy in cases where the game form is unknown and common assumptions are unrealistic.
Model
Indian Villages
Yelp Rat Bagings
Correlation
0.581610.0135
0.622210.0043
Anticorrelation
0.4184
0.377810.0043
Graphical Lasso
0.0122
0.65231000038
Baraki and Honorio
0.5715+000164
0.6786+0.0032
LinQuadOpt (independent)
0.5150
0.6796+0.0033
LinQuadOpt (homophilous)
0.0174
0.6310+0.0036
DeepGraph NuGgeT
0.496510.0114
0.677610.0033 0.705710.0035
0.632410.0167
Table 2: Test ROC AUC for the Indian Villages data and the Yelp Ratings data.
6 CONCLUSION AND FUTURE WORK
In this work, we propose a novel framework to infer the network structure behind the games from their equilibrium actions. Unlike existing methods, we achieve so by learning mapping from the actions to the network structure without knowing the utility function the game. This is especially beneficial in real-world scenarios where the nature of strategic interactions between players of the game remains hidden or may evolve over time.
Limitations and Future Work. The current work only deals with static games and networks. Moreover, we do not deal with repeated games, i.e. where players have to take multiple actions sequentially. A promising future direction therefore to extend to dynamic games and networks, where both the utility function well as the structure of the network may change over time, as well as dealing with repeated games. In addition, our method cannot guarantee the uniqueness of the learned network; indeed, the main focus of the study is to propose first and efficient data-driven learning framework without assuming the utility function and prior knowledge about the network structure. We leave the identification of network structure for future work.
"The Indian Villages dataset can be accessed at hww.aar...uuuuddttttt...hhh http://sssttttttdhdd199991111111 1/2153
'The Yelp dataset can he accessed at https:/wwww..yll..cm/ttaasss

---

Under review as a conference paper at ICLR 2022
Ethics Statement. Inferring networks of strategic interactions is of key importance to behavior prediction and intervention in network settings. For example, the learned network may be useful for stratification analysis via community detection, or designing efficient targeting strategies in marketing via node centrality analysis. Both would inform decision-making in a wide range of socioeconomic, business, and marketing scenarios.
Reproducibility Statement. The code and the data to replicate the experiments are provided as part of the supplementary material. Inside the code folder, the README.md file contains detailed instructions for running the experiments.
REFERENCES
Coralio Ballester, Antoni Calvó-Armengol, and Yves Zenou. Who's who in networks. wanted: The key player. Econometrica, 74($):1403-1417, 2006.
Abhijit Banerjee, Arun G. Chandrasekhar, Esther Dutlo, and Matthew O. Jackson. The Diffusion of Microfinance, 2013. URL [tLlattts://ab..orq/// 7910/DVN/USSSHH
Adarsh Barik and Jean Honorio. Provable computational and statistical guarantees for efficient
learning of continuous-action graphical games. arXiv preprint arXiv:1911.04223; 2012,
Adarsh Barik and Jean Honorio. Provable sample complexity guarantees for learning of continuous-
action graphical games with nonparametric utilities. CoRR, abs/2004.01022, 2020. URL https
7/arxiv. org. http//bbs22000 2204 01022
Eugene Belilovsky, Kyle Kastner, Gael Varoquaux, and Matthew B Blaschko. Learning to discover sparse graphical models. International Conference on Machine Learning, pp. 440 448. PMLR, 2017.
Yann Bramoullé, Rachel Kranton, and Martin D' l'amours. Strategic interaction and networks. American Economic Review, 104(3):898-99) 2014.
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv:2104. 13478, 2021.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/v 1/115511DDDIL 14- 1179. httptt//s//:::nnm
org/D14-1179
Luca Cosmo, Anees Kazi, Seyed-Ahmal Ahmadi, Nassir Navab, and Michael M. Bronstein. Latent- graph learning for disease prediction. In Anne L. Martel, Purang Abolmaesumi, Danail Stoyanov, Diana Mateus. Maria A. Zuluaga. S. Kevin Zhou, Daniel Racoceanu, and Leo Joskowicz (eds.), Medical Image Computing and Computer Assisted Intervention MICCAI 2020 23rd International Conference, Lima, Peru, October 4-8, 2020. Proceedings, Part II, volume 12262 of Lecture Notes in Computer Science, pp. 643 653. Springer, 2020a. doi: 10.1007/978-3-10 030-59713-99-00 622 URL 3-009988----0----11111
Luca Cosmo, Anees Kazi, Seyed Ahmadi, Nassir Navab, and Michael M. Bronstein. Latent patient network learning for automatic diagnosis. CoRR, ftss/2003.136200 2020b. URL https
1000000..3662 13620
Inderjit S. Dhillon, Yuqiang Guan, and Brian J. Kulis. Weighted graph cuts without eigenvectors: multilevel approach. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 29 (0), nov 2007.
X. Dong, D. Thanou, M. Rabbat, and P. Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44-63, 2019,
Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 933):432-441 2008a.
10

---

Under review as a conference paper at ICLR 2022
Jerome Friedman, Trevor Hastie, and Robert Tibshirami. Sparse inverse covariance estimation with the graphical lasso. Biostaristics, 9(3):432 441, July 2008b. ISSN 1465-4644, 1468-4357. doi:
(0.11093bbiostatssiessk.m555..5. httpa///sss.....ooooooooaaaaaaa. http:///sssaaasss.s..ooooooooooa content/9/3/432
Andrea Galeotti, Benjamin Golub, and Sanjeev Goyal.
Targeting interventions in networks.
arXiv:/710.06026, 2017.
Vikas Garg and Tommi Jaakkola. Learning tree structured potential games. In Advances in Neural Information Processing Systems, pp. 1552-1560, 2016.
Vikas Garg and Tommi Jaakkola. Local aggregative games. In Advances in Neural Information Processing Systems, pp. 5341-5351, 2017.
Asish Ghoshal and Jean Honorio. Learning graphical games from behavioral data: Sufficient and necessary conditions. arXiv preprini arXiv: 2017a.
Asish Ghoshal and Jean Honorio. Learning sparse polymatrix games in polynomial time and sample 2017b.
complexity. arXiv preprint
M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In Proc. of the 16th ACM SIGKDD Inter. Conf. on Knowledge Discovery and Data Mining, pp- 1019-1028, Washington, DC, USA, 2010.
M. Maanez-Rodriguez,, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffuuion networks. In Proc. of the 28th Inter. Conf. on Machine Learning, pp. 561-568, Bellevue, Washington, USA, 2011.
Mark Granovetter. Threshold models of collective behavior. American journal of sociology, 83(6): 1978.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL htttppa://prcceeediniaee wtw.:/gs..nnnnin..nnneoooo 5dd9db5e033da
pdf
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
Jean Honorio and Luis E Ortiz. Learning the structure and parameters of largc-population graphical games from behavioral data. Journal of Machine Learning Research, 16: 157-110,, 2015.
Mohammad Tanvir Irfan and Luis E Ortiz. A game-theoretic approach to influence in networks. 2011.
Matthew O. Jackson and Yves Zenou. Games on networks, Handbook of Game Theory, Vol. 4, Peyton Young and Shmuel Zamir, eds., 2014.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015. http
7/arxive org. abs /1412 6980
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference Machine Learning, pp. 2688- 2697. PMLR, 2018
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
D. Koller and N. Friedman. Probabilistic graphical models: Principles and techniques. MIT Press, 2009.
11

---

Under review as a conference paper at ICLR 2022
Yan Leng, Xiaowen Dong, Junfeng Wu, and Alex Pentland. Learning quadratic games networks. In Interaational conference on Machine Learning, 2020.
G. Mateos, S. Segarra, A. G. Marques, and A. Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Magazine, 36(3):16-43, 2019.
M. McPherson, Smith-Lovin, and M. Cook. Birds of feather: Homophily in social networks. Annual Review of Sociology, 27:415 444, 2001.
Andrea Montanari and Amin Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences, 107(47):20196-2021 2010.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998-6008, 2017.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph cnn for learning on point clouds. ACM Trans. Gruph., 38(5), October 2019. ISSN 0730-0301. doi: 10.1 145/3326362. https:/ /owi .rg / 1145/33266636
H Peyton Young. Innovation diffusion in heterogeneous populations: Contagion, social influence, and social learning. American economic review, 99(5):1899- 19244 2009.
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. Dag-gnn: Dag structure learning with graph neural networks. arXiv preprint wrXiv:194..00000 2019.
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, and Eric Xing. Learning sparse nonparametric dags. In International Conference on Artificial Intelligence and Statistics, pp. 3414-3425. PMLR, 2020.
12

---

Under review as a conference paper at ICLR 2022
A PROOF OF NUGGET SYMMETRIES
We would like to show that the NuGig'l' model g is permutation-invariann over the set of games and permutation-equivaaree over the set of nodes.
Starting with the first one, we need to show that g (XP2)) - g(X), where P2 is x K permutation matrix the games. For what concerns the encoder, only need to prove that oij is invariant w.r.t. permutation of the games. Let p& be the index of the non-zero entry of the k-th column of Pz. we have:
(h)
(h) aij
(h) Q
W K
Vik
Yjk
W (h) (h)
Vipe
spp
(h) does not depend on K- is chosen to be permutation invariant operator. This shows that d the particular permutation chosen, i.e. it is invariant w.r.t. permutation of the games. Similarly, the same holds for the decoder as 1= is permutation invariant operator and therefore
since D
Zik O
2yk- K
Zipc
zipk for any permutation p.
Regarding the second part of the proof, we need to show that (Pi Pig(X)PI where P is an N x N permutation matrix interpreted as reordering of the nodes of the graph. Letting pa be the index of the non-zero entry of the k-th row of P1. Note that:
N
N
Muc(PiX) = Yycks
a PiPs y pyks
(1)
(H) Popp
j=1
j=1
xb
Ypck
Op: Yzkk
(H)
Zp.k
where the second equality stems from the fact that summation a permutation invariant operator (i.e. Σ Tpp for any permutation p). We then have:
21-1 Tz
P ( åp.p,
K
Zpck 4 Zpyk
enc (1X) O enc
(P)))
Since this holds for all indices ij. it follows that (P,)) Pi.(())]..
B EXPERIMENTS
B. SYNTHETIC DATA GENERATION
We generate the synthetic data from three different graph models: Erdos Rensy (ER), Barabasi-Albert (BA) and Watts-Strogate (WS). In ER graphs, edge is present with probability of p 0.2,
13

---

Under review as a conference paper at ICLR 2022
independently from all other possible edges. In WS graphs, we set the exact degree of the nodes to be = log2 (N), with a probability of p = 0.2 for the random rewiring process. Finally, in BA graphs, nodes added one a time and each node has 1 edges which are preferentially attached to existing nodes with already high degree.
B.2 YELP DATASET GENERATION
Starting from the raw data at https//www.yebl.co///taattt, we create dataset by performing the following steps:
1. We compute the rating for every a user has given to all business of each category
every businesses category, by averaging the ratings
2. We weight each edge in the original user-user graph with the fraction of common categories the two users rated at least once
3. We cluster the above weighted graph using Graclus Dhillon et al. (2007) with the objective minimizing the normalized cut.
4. We discard all the clusters with less than 10 nodes, or with very sparse ratings (less than 25% of the categories with rating for at least 25% of the users). The result of this step is
27k graphs of different users.
5. We rank the clusters extracted above by their density of ratings and keep the 5000 most dense clusters. Each cluster constitutes a graph associated with node attributes, which can be used to train and test our model.
B.3 BASELINES
In both the synthetic and real- world data experiments compare with the following baselines:
The Pearson correlation coefficient between the actions of two nodes. This works particularly well when the actions are homophilous over the graph, i.e. nodes connected in the graph tend to take similar actions. We implement this baseline ourselves.
Correlation
The negative of the Pearson correlation coefficient between the actions of two nodes. This works well in case of strategic substitutes, i.e. when nodes connected in the graph tend to take different actions. We implement this baseline ourselves.
Anticorrelation
Graphical Lasso Friedman al. (2008)) Computes a sparse penalized estimation of the in- verse of the covariance matrix. We use SKGGM QuicGraphicall Lasso with empirical covariance initialization for this.
LinQuadOpt Algorithm presented in Leng al. (2020) which assumes the form of the game to be linear quadratic. It has two version, one where the benefits are assumed to be independent (LinQuadOpt (Independent)), and another for homophilous benefits (LinQuadOpt (Homophilous)). We implement the algorithm ourselves (no public code was provided).
Bloceseegrssson Algorithm presented Barik & Honorio 2019). which has been designed specifically for BH graphical games. We re-implement this baseline ourselves following the paper (no public code was provided).
DeepGraph Algorithm presented in Belilovsky al. (017) which recovers the graph from the covariance matrix using a series of dilated convolutions. We re- repilmmeenn DeepGraph in Py PyTorc ourselves taking inspiration the public TensorFlow implementation of the authors.
All the baselines are tuned on the validation set. For both Graphical Lasso and BlockRegression we tune the regularization parameter the range 10 k E [-5, 5] with an interval of one, whereas for LinQuadOpt both regularization parameters are tuned in 10 k [-6, 1]. also with an interval
hhtps//gitthh.cmmkkggg/sggg
14

---

Under review as a conference paper at ICLR 2022
WS graphs, awd.5
En graphs, am0.5
graphe, en0.3
MAC AEC
MOC
04
Spattel A33
Spectra
Figure 5: Results for linear quadratic games with 0.5 and variable spectral radius p(33A).
1.00
NuGgeT
Corrolation
Graphical Lasso
Test ROC AUC
BlockRegression DeepGraph
0.85
DAA
0333
2376 711
0.70
watts strogatz
erdos renyl
barabaai
Figure Results for BH graphical games.
of one. We train DeepGraph using the same hyperparameters used for NuGget (Adam optimizer, learning rate 0.001, batch size of 100 and a patience of 50), with [log2(Nmmax) convolutional layers (Nmax corresponds here to the maximum number of nodes of any graph in the dataset) and dilation coefficient equal to dz 2 for layer specified in Belilovsky et al. (2017).
B.4 NUGGET HYPERPARAMETERS
We do not perform any extensive hyperparameter tuning for the NuGgeT model, but instead the same standard choice of hyperparameters (reported in Table for all experiments.
Hyperparameter Name
Value
F
10
F
10
(num of heads)
4 num layers
2
0 hidden dim
100
Table 3: Hyperparameters used for NuGgee all experiments.
B.5 ADDITIONAL. RESULTS
Additional results the linear quadratic and BH games are presented in Figure 5 and Figure 6
respectively.
C SPECTRAL ANALYSIS OF THE GAMES
Figure shows that the smallest absolute (non-zero) eigenvalues of the normalized adjacency matrix A is average much smaller for ER and WS graphs than for BA graphs. This results in the corresponding eigenvectors having large influence on the actions for the Linear Influence games, where the Nash equilibrium actions satisfy x* A -... This is confirmed by Figure [ which shows the graph Fourier coefficients for different eigenvalue indexes: the actions linear influence games ER and WS graphs dominated by mid-range eigenvectors.
15

---

Under review as a conference paper at ICLR 2022
Min Absolute Eigenvalue
0.7
0.6-
0.5
0.4
6.3-
0.0 WS
ER
BA
Figure 7: Mean and standard deviation of the minimum absolute non-zero eigenvalue of the adjacency matrix for different types of graph models. Statisties are computed over 1000 graphs with 20 nodes.
Lineer Quaddratic pame, WS gruphs
Liaur Quadratic gums, EX graphs
Lheer Quednatic gams, BA graphs
Linear Influente WB'
Limsar Influence grapho
Unner Iefluence
Figure 8: Magnitude of coefficients of normalized action vectors for different games and graphs. These obtained by taking the Graph Fourier Transform of the actions, i.e. taking the inner product between the action and each of the adjacency matrix eigenvectors.
16

---

Under review as a conference paper at ICLR 2022
game, graphs
gams,
game, grophs
20
20
20 21
20
15
24
30
gait,, graple
graphs
Bil game, WS graphs
Bil gams, ER gmahs
game, BA graphe
34
Figure 9: Results with varying number of games.
D ABLATION STUDIES
In Figure 9 we investigate how the performance changes with the number of games available. The smaller the number of games, the less information reconstruct the graph from. We use a 1 for both linear quadratic and linear influence games, and spectral radius of 0.6 for linear quadratic games. line with our expectations, all methods generally improve as more games are available. We analyze the effect of larger graph sizes (Figure TO). The more nodes, the more edge combinations exist and the harder the task becomes, which explains the decrease in performance of both methods as the number of nodes increases. Interestingly, the magnitude of the drop depends heavily on the combination of game and graph types, but NugGeT seems to be more robust than DeepGraph. We also investigate the effect of the number on training graphs the model performance (Figure [T]. NugGeT requires less training graphs compared to DeepGraph to obtain a similar performance. Figures and show respectively the performance of various methods when varying the number of games and the number of nodes respectively. We use a = 1 for both linear quadratic and linear influence games, and 3 = 0.6 (strategic complements) for linear quadratic games. In line with our expectations, all methods generally improve as more games are available. On the other hand, the more nodes, the more edge combinations exist and the harder the task becomes, which explains the decrease in performance of all methods as the number of nodes increases. Interestingly. the magnitude of the drop depends heavily on the combination of game and graph types, but NugGeT seems to be more robust than DeepGraph.
E NuGgeT's ATTENTION MECHANISM
We investigate the difference between a multiplicative attention mechanism operating directly on scalar actions (i.c. with unnormalized attention coefficients of the form: م,j = ITKza with a a learnable parameter), and one operating on transformed actions (i.e. āij = y; WoWWRy ky,, with y; ReLU(x, + b)). In Figure 12 we plot the non-normalized attention values of the two different mechanisms for varying values of the input actions 2;, Zj. We use a positive and a negative value of for showing the capability of the simple scalar-based attention mechanism to identify correlation and anti- conrelaorrlttin in the input actions x. and random coefficients drawn from normal distribution for W Q. W K. w. b for the attention mechanism used in NuGgeT. While the scalar attention always
17

---

Under review as a conference paper at ICLR 2022
Unser Quidratic pame, WS graphy
Unner Quedratic pams, grapto
Unser Quidratic game, gropho
Unner Influence gama, WS graphe
Unber Influence gama, graphs
Uneer Infleezee gams, graphs
BII gams, WS gropho
Bil gams, EA graphs
BHt gums, BA graphs
Figure 10: Results with varying number of nodes.
shows a linear trend for fixed x; (or n,), the multiplicative layer operating vectors is able to produce richer non- lineir attention patterns with maximum minimum values for the interior points of [-,1
18

---

Under review as a conference paper at ICLR 2022
graphe
Unear Inflaence gama, graphe
Ubear Inflcance gaRa, gright
Unerr Infloance gana graphs
IH game, Wt graphs
IH game, BR graphs
game, BA graphs
Figure 11: Results with varying number of training graphs.
19

---

Under review as a conference paper at ICLR 2022
Attention on scalar actions (a
Attention on scalar actions (e
-1.0
1
-10
-0.6
0.8
4.6
0.8
4.2
0.6
4.2
0.6
0.2
0.1
0.2
0.1
0.6
0.2
0.6
0.2
1.0
1.0
-1.0
-0.6
-0.2
0.2
0.6
1.0
-1.0
-0.6
-0.2
0.2
0.6
1.0
xyy
Attention on exponded actions
Atteation on expanded actions
-1.0
-1.0
40.6
0.8
40.6
0.8
4.2
0.6
-.2
0.6
0.2
0.1
0.2
0.1
0.6
0.2
0.6
0.2
1.0
1.0
-1.0
.0.6
-0.2
0.6
-1.0
.0.6
-0.2
0.6
.6g
Figure 12: Top, attention values for multiplicative attention layer directly operating on the input scalars 2; E [-1, 1], 2, E [] with positive (left) and negative (right) coefficient. Bottom, attention values for multiplicative attention layer with random coefficients processing the expanded actions yi, yj of 34, Zy. The result is scaled to [0. 1] for visualization purposes.
20


Reviews:
[{"review_id": "zVCh2YLem29x", "reviewer": "Reviewer_bS2U", "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": "The paper starts with a significant promise that it can reveal the network structure between agents performing games--- that too without any explicit knowledge of the network. However, later on, I got confused to see that it is a structure learning problem from network data (possibly from steady state of ant networked process). I see this paper has closest connection with information diffusion in networked systems, except that it only estimates parameters from steady state data rather than transient data. \nTo me, strategic behavior or games is very misleading in the current scenario. \n\n\nThere are other two limitations of the paper:\n(1) the paper considers a supervised structure learning setup--- in practice, explicitly networks are rarely observable. I would expect the problem to be practically useful if one tries to find the most likely graph structure which would induce the network data i.e. $X^{\\ell}$.\n(2) The paper considers same utility function (though somehow I did not find where this utility function is playing a role in the formulation/NN architecture). Such assumption in the context of the current experiments seems a bit impractical. Several subgraphs in Yelp can play different games/strategy. \n(3) I did not find the datasets to be very coherent with the main theme of the paper. Is there any strong evidence that people try to strategize in a **collaborative** manner in Yelp? One individual can game the system, but I am not sure there is an underlying https://people.mpi-sws.org/~manuelgr/pubs/netrate-jmlr16.pdf game in the platform.", "summary_of_the_paper": "The paper aims to infer the structure of the underlying graph where each agent is performing strategically.\nInitially it compares three types of games and then it proposes a mechanism that can learn the network without\nany functional form of the underlying utility function. Finally, the paper shows the efficacy of the method via experiments.", "summary_of_the_review": "The paper makes an important promise-- but the formulation and experiments are not coherent with this promise.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "xNLCz3XfKC", "reviewer": "Reviewer_rnrt", "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": "Strengths:\n- Clear definitions and paper structure - I'm not very familiar with this line of work but I was still able to follow along.\n- Model is reasonably small and takes only minutes to train on a single GPU.\n\nWeaknesses:\n- Experiments are conducted on very small graphs (tens of nodes). It is difficult to understand if this would work on much larger networks, and whether the improvements of your model over the baselines would still hold in larger networks.\n- Real-world data is tiny or somewhat artificially generated. This might also suggest that the applicability of this method in actuality might not be straightforward. I wish the authors spent more time motivating the problem describing specific examples and cases where it'd be a lot easier to obtain equilibrium action datasets compared to the corresponding network. The scarcity of real-world datasets is making me question the applicability of this problem - if labeled data is hard to get, one alternative would be to provide experiments on unlabeled datasets where meaningful networks are obtained.", "summary_of_the_paper": "In a network game, players are nodes of a graph and choose their action by maximizing a utility function which depends on their and their neighbors actions, possibly weighted by some given edge weights. \n\nThe authors consider the case where each player action is a real number x_i and its payoff is some f(x_i, x_j1, ..x_jm), where j1,..,jm are i's neighbors. The question the authors ask is the following: assuming rationality of the players and observing a noisy version of their actions x_i, can we reconstruct the original graph? In particular, while previous literature has focused on the case where utility function is known, this paper asks whether we can drop this requirement if we observe equilibrium actions for several games (on different networks but with same unknown utility function).\n\nAn encoder-decoder model is proposed to learn the mapping from the observed actions to the network structure. A transformer-like architecture is used as encoder to allow for variable-length number of players and permutation-invariance over set of games. \n\nThe proposed model performs better than baseline and existing models on synthetic and real-world data.", "summary_of_the_review": "I'm voting for borderline acceptance for this paper but I'm not very familiar with this area.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_cVYyfklJkG", "reviewer": "Reviewer_XNyt", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n- Proposing a novel approach to solve the problem of inferring the network structure of games with unknown utility function.\n- Justifying/motivating their approach by expressing the equilibrium actions in some network games as a function of network structure. \n\nComments:\n- It seems the assumption of eq (8) for b is central to the proposed method. Because with this assumption the x^* will be probabilistic and it make sense to infer A from a dataset of (X,A). But is it a realistic assumption, i.e., is the real data follows this assumption. \n- It would be good if authors discuss about the required no. of data samples to infers the (transformer architecture) model parameters.\n- last line of section3: to infer network the structure --> to infer the network structure\n- line 9 of section 4: physics --> social or complex networks", "summary_of_the_paper": "This paper propose a method to infer the network structure behind the games with unknown utility function. Given a dataset of independent games consisting of action and graph (X, G) pairs, and by modeling network structure (adjacency matrix, A) as a (transformer like) function of actions, A = g_{\\theta} (X), they inferred the parameters of the model, \\theta, by minimize a cross entropy objective function. To justify/motivate their modeling, they show that the PSNE for some well-know (utilities in) networks games, optimal actions, is related to a function of network structure (F(A)) and another function of some additional parameters (b). Then assuming a parametric Gaussian distribution for parameter  b, they derived the multivariate Gaussian distribution of the equilibrium actions x^*.", "summary_of_the_review": "Proposing a novel approach to solve the problem of inferring the network structure of games with unknown utility function, and in the experiment section authors show the superior performance of their approach compared to other alternative approach.", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "B4nQXn4uvbi", "reviewer": "Reviewer_BhGi", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength of the paper\n\n- As the authors claim, the paper is the first one conducting network inference from equilibrium states of network games without the need of knowing the actual utility functions.\n\n- Converting the network inference problem into a learning framework and applying transformer-like neural architecture contributes to the research community on the network inference task.\n\nWeakness of the paper\n\n- It is unclear that if there is any technical novelty in the paper in constructing the transformer-like architecture for the task. All the components seem to be more or less standard. Permutation invariance may be important for this task, but it is also a technique proposed in some prior work. The full proposed approach of Section 3 is only 1.5 pages, and it is unclear if there is any nontrivial technical novelty, or if any one who is familiar with transformer could come up with a similar architecture and results.\n\n- Related to the above point is that, since the authors claim that their main contribution is by not knowing the utility function in network inference, but would it give better result when knowing the network utility function? It looks like to me that it may be actually hard to incorporate the utility function as the prior knowledge into the transformer-like neural architecture. In other words, by applying the transformer-like architecture, it seems that not knowing the utility function is just a by-product, and not an intentional design point, since anyway it is not easy to incorporate such knowledge into the architecture. If I misunderstood this part, then perhaps the authors should provide an alternative architecture with the utility knowledge and compare the performance difference.\n\n- The experimental evaluation shows that the proposed algorithm performs better, but the margin is not very significant. Even the basic baseline of correlation and anti-correlation performs fairly well, indicating that correlation or anticorrelation explains a large majority of the relationship in the network, at least in the given datasets. Of course, the proposed algorithm performs well on both the positive correlation and negative correlation side. This is not surprising because it learns from the training dataset to detect whether it is positive or negative correlation, while the basic correlation and anticorrelation baseline has no learning phase.\n\n- The experiments are on small network datasets. The synthetic datasets using only 20 nodes are extremely small. Even the ablation study in the appendix (Figure 10) has networks at most size 50. The authors should provide a scalability study to show how large the network size the proposed algorithm can handle, what's the accuracy for large networks, and what's the running time.\n\nMinor comments:\n\n- Page 2, Eq.(1), the notation $a_{ij}$ is not explained. I guess it is the $i$-th row and $j$-column entry of the matrix $A$, but this needs to be clearly stated.\n\n- Page 3, Eq.(8). It is unclear why modeling $b$ as a random vector.\n\n- Page 7. The $y$-axis of the experiment figures are not explained. Even though it may be more or less standard, an explanation is still preferred. A particular thing is that the network is weighted, so it becomes unclear to me what is the ROC AUC in this setting. I would understan ROC AUC when the edges are unweighted, and this it is only a binary classification task on the edges. If the networks used in the experiments are all unweighted, please state this clearly. Moreover, some more tests on weighted graphs are needed.\n\n", "summary_of_the_paper": "The paper studies the problem of inferring the network structure from the equilibrium states of nodes in a network game. The authors put the inference into a learning framework, and it does not need the utility functions of the game. The authors use transformer-like architecture to conduct the learning task. The empirical evaluation on both synthetic networks and real-world networks show that the proposed learning algorithm NuGgeT achieves the best performance comparing to other baselines.\n", "summary_of_the_review": "Applying transformer-like architecture to network inference for network games is an interesting direction, but it is unclear how much is the technical contribution of the paper, and the experimental result is not very strong, as discussed above in the weakness part. Therefore, I think the paper is marginally below the acceptance threshold.", "strength_and_weaknesses": "", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9TAf2vvG4oo", "reviewer": "Reviewer_awAV", "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": "### Positives\n\nThe data-driven approach is novel and some of the architecture design choices made to accommodate invariance properties are well motivated. The problem is well-motivated and the general framework of using just agent actions to infer a network is potentially impactful.\n\n### Weaknesses\n\nHowever, my two main concerns for the paper are:\n\n### Lack of evidence for good generalization\n\nThe authors have shown good results on common synthetic graphs and real-world graphs. However, the train and test datasets are closely related in most cases. For example in the household benchmark, different components are used for train and test. Using subgraphs from the same network or graphs with very uniform properties for ER, WS, and BA graphs for evaluation is not convincing. I would be more convinced if the training and test set has different varieties of graph families so that the model can generalize across multiple graph types.\n\n### The model architecture can be compared with other generative and link prediction models\n\nThe proposed model can mostly be replaced by other general network structure inference models including some SOTA generative graph neural models with perhaps some changes in the encoder to preserve the invariance properties. There is nothing particularly special about the problem statement that is leveraged by the model that a slightly modified SOTA generative model can't be replaced with. Therefore, to claim top performance in the proposed task authors may also use at least some of the top Graph generative models [1] and link prediction models [2] as baselines. The current proposed model seems straightforward (transformer encoder + MLP based decoder) and I believe can be improved to leverage ideas from top models.\n\n### Other comments/questions\n\n1. It would be interesting to see what relations the attention heads capture across nodes. Do these model any specific correlation, predict centrality behavior, etc.?\n2. In what ways are networks predicted by NuGget different from other baselines? The difference in scores seems small. Therefore, what specific properties are captured by proposed models?\n3. Are the scores statistically significant (across multiple runs, train/test splits)?\n\n**Recommendation:** 4 Reject\n\n**Confidence:** 3 Fairly confident.\n\n[1] Guo et al. A Systematic Survey on Deep Generative Models for Graph Generation 2020\n\n[2] Zhang et al Revisiting Graph Neural Networks for Link Prediction 2020\n\nUpdate: I have read the text of other reviewers. My recommendation doesn't change. I hope the authors improve on the suggestions for submitting their next version.", "summary_of_the_paper": "The authors introduce a purely data-driven deep learning approach for network structure discovery using just action signals from players of network games with knowing the underlying utility function which can be mostly arbitrary.\n\nThe proposed approach uses an encoder that ingests a list of action sets of all users for independent games and outputs a graph (adjacency matrix) over the players. The proposed method outperforms other general network inference baselines as well as baselines that are designed specifically for network games authors evaluate on.", "summary_of_the_review": "The paper successfully applies Deep graph inference model to the problem of network discovery in network games. The proposed architecture is not very novel and the problem framework, while more challenging, doesn't lend too much to methodological novelty.\n\nWith regard to empirical results, I am not convinced of the generalizability and significance of the results. Therefore, I currently recommend rejecting the paper. Providing more extensive evaluation with better baselines and models as well as showing extent of generalizability would strongly help improve the contributions of the paper.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a transformer-like architecture to perform network inference in network games. While the reviewers acknowledge that the research direction is interesting, they raise concerns regarding the significance of the contribution in terms of methodology, particularly in light of the state of the art, and the experimental evaluation, which in their view did not support the promise of the work. The authors did not reply/follow up on the reviews during the rebuttal period. I would encourage the authors to use the reviewers' comments to revise their paper and resubmit to another conference.
Decision: Reject