Graph neural networks

One or more non-transitory computer-readable storage media configured to store instructions that, in response to being execute, cause a system to perform operations, the operations comprising:

• generating, for each of a plurality of input graphs, a set of subgraphs by performing k-means clustering on nodes of the input graph based on classification scores corresponding to the nodes and obtained by inputting the input graph into a graph neural network, GNN, wherein each node in each input graph comprises a plurality of values corresponding respectively to a plurality of features;
• determining statistical measures of each feature's values in each of a plurality of subgraphs comprising the subgraphs of each set of subgraphs, to generate a set of statistical measures for each subgraph, and obtaining for each subgraph, based on the classification scores corresponding to the nodes of the subgraph, classification probabilities corresponding respectively to a plurality of classes;
• performing k-means clustering on the subgraphs based on the statistical measures to generate a plurality of clusters of subgraphs;
• generating, for each cluster of subgraphs, a set of surrogate models to approximate the classification probabilities, respectively, of the subgraphs in the cluster, in terms of the statistical measures;
• and
• determining, based on the surrogate models of each set of surrogate models, feature importance scores, each feature importance score corresponding to a feature of the plurality of features, a subgraph of the plurality of subgraphs, and a class of the plurality of classes, and indicating importance of the feature to the classification probability of the subgraph corresponding to the class.

A computer-implemented method comprising performing a minimum subgraph process for an input graph comprising:

• generating a set of subgraphs based on an input graph by performing k-means clustering on nodes of the input graph based on classification scores corresponding to the nodes and obtained by inputting the input graph into a graph neural network, GNN;
• repeating the generating of the set of subgraphs for the input graph for a plurality of iterations, varying k in the k-means clustering in each successive iteration, to obtain a plurality of candidate subgraphs which includes the subgraphs of the set of subgraphs generated in the original iteration;
• inputting each candidate subgraph into the GNN and obtaining classification probabilities for each candidate subgraph;
• computing a subgraph score for each candidate subgraph based on a difference between the input graph's classification probabilities and the candidate subgraph's classification probabilities and based on a size of the candidate subgraph;
• and
• selecting the candidate subgraph having the lowest subgraph score as a minimum subgraph of the input graph.