Documentation - Myerson package

The Myerson values can be calculated using different classes. The base class calculates Myerson values for arbitrary games, an inheriting class can also approximate the Myerson value through Monte Carlo sampling of the player coalitions. From the base calculator class the explainer and sampling explainer classes inherit most functionality. However, depending on the module used (pyg_explain or chemprop_explain), the graph and coalition functions are expected to be pytorch_geometric or chemprop graphs and their respective neural network modules.

Inheritance diagram of the Myerson module classes.

Calculate the Myerson value for arbitrary games

class myerson.MyersonCalculator(graph: Graph, coalition_function: Callable, disable_tqdm: bool = True)

Calculates the exact Myerson values.

For a game described by a coalition function \(v\) the Myerson values attribute the individual players contribution to the payoff of the game. For a complete graph (every node connected to every other node) the Myerson value is equal to the Shapley value (\(S\): coalition of players, \(N\): grand coalition of all players):

\[\text{Sh}_i\,({v}) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! \: (|N| - |S| - 1)!}{|N|!}\big( {v}\,(S \cup \{i\}) - {v}\,(S) \big)\]

Else, the additional gain players can obthain through coalition is restricted only to players which are connected by edges in the graph.

Parameters:

• graph (nx.classes.graph.Graph) – The coalition structure of the game.

• coalition_function (Callable) – The coalition for which to calculate the payoff of the game. Expects a coalition (tuple of node indices) and a graph which contains additional information on the players to decide on the payoff.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

calculate_all_mappings() → None

Calculates all coalitions, graph restricted coalitions, and their associated worths as class attributes:

• self.coalitions (list[tuple])

• self.graph_restricted_coalitions (set[tuple])

• self.coalitions_to_graph_restricted_coalitions (dict)

• self.graph_restricted_coalitions_to_worth (dict)

• self.coalitions_to_worth (dict)

calculate_all_myerson_values() → ndarray

Calculate the Myerson values for every node / player in the graph.

Returns:

Myerson values for each node.

Return type:

np.ndarray

calculate_coalitions(grand_coalition: list) → list

Calculate all possible coalitions for a set of players / all nodes in a graph.

Parameters:

grand_coalition (list) – Set of players / grand coalition / atoms in graph as a list of tupels.

Returns:

All \(2^N\) coalitions.

Return type:

list

calculate_graph_restricted_coalitions(coalitions: list, nx_graph: Graph) → tuple[set, dict]

Calculate the graph restricted coalitions for each coalition. The graph restricted coalitions are tuples of nodes which are connected.

Parameters:

• coalitions (list) – All coalitions.

• nx_graph (nx.classes.graph.Graph) – NetworkX Graph for which to

• values. (calculate the Myerson)

Returns:

Set of all possible graph restricted coalitions as

a tuple of nodes, dictionary mapping each coalition to its graph restricted coalitions.

Return type:

tuple[set, dict]

calculate_single_myerson_value(node: int, grand_coalition: tuple, coalitions: list[tuple], coalition_to_worth: dict) → float

Calculate a single Myerson value.

Parameters:

• node (int) – Node index for which to calculate the Myerson value.

• grand_coalition (tuple) – Set of all players.

• coalitions (list[tuple]) – List of all coalitions.

• coalition_to_worth (dict) – Mapping of every coalition to its worth.

Returns:

Myerson value.

Return type:

float

calculate_worth_of_grand_coalition(nx_graph: Graph) → float

Calculate payoff of the game, i.e. the payoff of all players / the grand coalition.

Parameters:

• coalition_function (Callable) – The coalition function associating a coalition with a payoff.

• nx_graph (nx.classes.graph.Graph) – Coalition structure of the game as a graph.

Returns:

Payoff of the game / worth of grand coalition.

Return type:

float

calculate_worth_of_graph_restricted_coalitions(graph_restricted_coalitions: set) → dict

Calculate the worth of every graph restricted coalition and map it to its worth.

Parameters:

graph_restricted_coalitions (set) – Set of connected components as tuples of node indices.

Returns:

Dictionary mapping each connected component to its worth.

Return type:

dict

calculate_worth_of_single_graph_restricted_coalition(graph_restricted_coalition: tuple, nx_graph: Graph) → float

Calculate the worth of a graph restricted coalition, i. e. a single connected component.

Parameters:

• graph_restricted_coalition (tuple) – Graph restricted coalition as node indices.

• nx_graph (nx.classes.graph.Graph) – Additional information for the coalition function, i.e. the entire graph with node parameters. The result of the coalition function should depend only on the coalition, however the node parameters might contain necessary information.

Returns:

Worth, the output of the coalition function for the connected subgraph.

Return type:

float

map_coalition_to_worth(coalitions: list[tuple], coalitions_to_graph_restricted_coalitions: dict, graph_restricted_coalitions_to_worth: dict) → dict

Map every coalition to its worth.

Parameters:

• coalitions (list) – List of all coalitions (2^{num_nodes}).

• coalitions_to_graph_restricted_coalitions (dict) – Dictionary mapping the coalitions to the corresponding graph restricted coalitions.

• graph_restricted_coalitions_to_worth (dict) – Dictionary mapping the graph restricted coalitions to their worth.

Returns:

Dictionary mapping each coalition to its worth.

Return type:

dict

restrict(coalition: tuple, nx_graph: Graph) → list[tuple]

Restricts a graph through a (sub)set of nodes / players. Generate a list of graph restricted coalitions, i. e. a list of node indices of connected nodes in the subgraph.

Parameters:

• coalition (tuple) – Nodes that remain in the graph.

• nx_graph (nx.classes.graph.Graph) – Graph from which to generate subgraphs.

Returns:

Graph restricted coalitions as tuples of node indices.

Return type:

list[tuple]

subgraph_from_coalition(graph_restricted_coalition: tuple, nx_graph: Graph) → Graph

Generates a subgraph from a graph restricted coalition (a subset of nodes / players) and a graph.

Parameters:

• graph_restricted_coalition (tuple) – Nodes / players which form the subgraph.

• nx_graph (nx.classes.graph.Graph) – Subgraph induced in this graph by the nodes_set.

Returns:

The new subgraph.

Return type:

nx.classes.graph.Graph

class myerson.MyersonSampler(graph: Graph, coalition_function: Callable, seed: None | int = None, number_of_samples: int = 1000, disable_tqdm: bool = True)

A class approximating the Myerson value using Monte Carlo sampling.

The Myerson values are approximated by randomly sampling from all permutations needed to calculate the Shapley value:

\[\text{Sh}_i\,({v}) = \frac{1}{|N|!}\; \sum_R \big({v}\,(P_i^R \cup \{i\}) - {v}(P_i^R)\big)\]

For efficiencies sake, the sampled permutations are transformed into the corresponding coalitions.

Parameters:

• graph (nx.classes.graph.Graph) – The coalition structure of the game.

• coalition_function (Callable) – The coalition for which to calculate the payoff of the game. Expects a coalition (tuple of node indices) and a graph which contains additional information on the players to decide on the payoff.

• seed (None | int, optional) – Seed for randomness. Defaults to None.

• number_of_samples (int, optional) – Number of sampling steps. Defaults to 1000.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

calculate_all_myerson_values() → None

Not implemented for sampling class.

Raises:

NotImplementedError – The MyersonSampler only has the sample_all_myerson_values() method. To accuratly calculate the Myerson values, please use the MyersonCalculator class.

get_coalitions_from_permutations(permutations: list[ndarray])

Get the set of coalitions from the different (sampled) permutations.

Parameters:

permutations (list[np.ndarray]) – The permutations.

Returns:

The sampled coalitions.

Return type:

list[tuple]

number_of_samples

Instantiates the class.

reset_rng()

Reset random number generator to seed.

sample_all_mappings() → None

Samples permutations, corresponding coalitions, graph restricted coalitions, and their associated worths as class attributes:

• self.random_node (int)

• self.permutations_without_random_node (list[np.ndarray])

• self.all_sampled_permutations (list[np.ndarray])

• self.coalitions (list[tuple])

• self.graph_restricted_coalitions (set[tuple])

• self.coalitions_to_graph_restricted_coalitions (dict)

• self.graph_restricted_coalitions_to_worth (dict)

• self.coalitions_to_worth (dict)

sample_all_myerson_values() → ndarray

Use Monte Carlo sampling to approximate the Myerson values for every node / player in the graph.

Returns:

Sampled Myerson values for each node.

Return type:

np.ndarray

sample_permutations(number_of_samples: int)

Uniformly sample permutations from all possible permutations. Samples number_of_samples`*2*`number_of_nodes permutations in total.

Parameters:

number_of_samples (int) – How many sample steps should be carried out.

Returns:

A randomly chosen

node, the sampled permutations without the random node, all the sampled permutations.

Return type:

tuple(int, list[np.ndarray], list[np.ndarray])

Explain PyG GNNs with Myerson values

class myerson.pyg_explain.MyersonExplainer(graph: Data, coalition_function: Module, disable_tqdm: bool = True)

Explains the prediction of a graph neural network (GNN) with Myerson values.

The GNN is treated as the coalition function of a game and its prediction as the payoff of the game. The Myerson values show how much each node of the graph contributed to the final prediction.

Parameters:

• graph (torch_geometric.data.Data) – The data instance that is to be explained.

• coalition_function (torch.nn.Module) – The GNN.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

calculate_prediction() → float

Calculate the prediction of the GNN for the investigated graph. When the graph is disconnected this prediction may differ from the worth of the grand coalition.

Returns:

Prediction.

Return type:

float

calculate_worth_of_grand_coalition() → float

Calculate payoff of the game, i.e. the model prediction. Note that a disconnected graph (> 2 molecules) can lead to differeces between the model prediction and this function.

Parameters:

• coalition_function (Callable) – The coalition function associating a coalition with a payoff.

• nx_graph (nx.classes.graph.Graph) – Coalition structure of the game as a graph.

Returns:

Payoff of the game / worth of grand coalition.

Return type:

float

calculate_worth_of_graph_restricted_coalitions(graph_restricted_coalitions: list) → dict

Calculate the worth of every graph restricted coalition and map it to its worth.

Parameters:

graph_restricted_coalitions (list) – Set of connected components as tuples of node indices.

Returns:

Dictionary mapping each connected component to its worth.

Return type:

dict

calculate_worth_of_single_graph_restricted_coalition(graph_restricted_coalition: tuple, pyg_graph: Data) → float

Calculate the worth of a graph restricted coalition, i. e. a single connected component.

Parameters:

• graph_restricted_coalition (tuple) – Graph restricted coalition as node indices.

• pyg_graph (torch_geometric.data.Data) – Graph from which a subgraph of the connected components will be extracted according to the graph restricted coalition.

Returns:

Worth, the output of the coalition function for the connected subgraph.

Return type:

float

subgraph_from_coalition(graph_restricted_coalition: tuple, pyg_graph: Data) → Data

Generates a subgraph from a graph restricted coalition (a subset of nodes / players) and a graph.

Parameters:

• nodes (tuple) – Nodes which form the subgraph.

• pyg_graph (torch_geometric.data.Data) – Subgraph induced in this graph by the subset of nodes.

Returns:

The new subgraph.

Return type:

torch_geometric.data.Data

class myerson.pyg_explain.MyersonSamplingExplainer(graph: Data, coalition_function: Module, seed: None | int = None, number_of_samples: int = 1000, disable_tqdm: bool = True)

A class explaining GNN predictions with approximated Myerson values.

Parameters:

• graph (torch_geometric.data.Data) – The data instance that is to be explained.

• coalition_function (torch.nn.Module) – The GNN.

• seed (None | int, optional) – Seed for randomness. Defaults to None.

• number_of_samples (int, optional) – Number of sampling steps. Defaults to 1000.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

class myerson.pyg_explain.MyersonClassExplainer(graph: Data, coalition_function: Module, disable_tqdm: bool = True)

Explains the prediction of a graph neural network (GNN) classifier with

Myerson values. The GNN is treated as the coalition function of a game and its prediction as the payoff of the game. The Myerson values show how much each node of the graph contributed to the final prediction.

Parameters:

• graph (torch_geometric.data.Data) – The data instance that is to be explained.

• coalition_function (torch.nn.Module) – The GNN.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

calculate_prediction() → tensor

Calculate the prediction of the GNN for the investigated graph. When the graph is disconnected this prediction may differ from the worth of the grand coalition.

Returns:

Prediction.

Return type:

float

calculate_worth_of_single_graph_restricted_coalition(graph_restricted_coalition: tuple, pyg_graph: Data) → tensor

Calculate the worth of a graph restricted coalition, i. e. a single connected component.

Parameters:

• graph_restricted_coalition (tuple) – Graph restricted coalition as node indices.

• pyg_graph (torch_geometric.data.Data) – Graph from which a subgraph of the connected components will be extracted according to the graph restricted coalition.

Returns:

Worth, the output of the coalition function for the connected subgraph.

Return type:

tensor

class myerson.pyg_explain.MyersonSamplingClassExplainer(graph: Data, coalition_function: Module, seed: None | int = None, number_of_samples: int = 1000, disable_tqdm: bool = True)

A class explaining a GNNs classifier predictions with approximated Myerson values.

Parameters:

• graph (torch_geometric.data.Data) – The data instance that is to be explained.

• coalition_function (torch.nn.Module) – The GNN.

• seed (None | int, optional) – Seed for randomness. Defaults to None.

• number_of_samples (int, optional) – Number of sampling steps. Defaults to 1000.

• disable_tqdm (bool, optional) – Disables progress bar. Defaults to True.

map_coalition_to_worth(coalitions: list[tuple], coalitions_to_graph_restricted_coalitions: dict, graph_restricted_coalitions_to_worth: dict) → dict

Map every coalition to its worth.

Parameters:

• coalitions (list) – List of all coalitions (2^{num_nodes}).

• coalitions_to_graph_restricted_coalitions (dict) – Dictionary mapping the coalitions to the corresponding graph restricted coalitions.

• graph_restricted_coalitions_to_worth (dict) – Dictionary mapping the graph restricted coalitions to their worth.

Returns:

Dictionary mapping each coalition to its worth.

Return type:

dict

sample_all_myerson_values() → ndarray

Use Monte Carlo sampling to approximate the Myerson values for every node / player in the graph.

Returns:

Sampled Myerson values.

Return type:

np.ndarray

Explain Chemprop Models with Myerson values