DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Step 1
According to the first part of the analysis, in the instant case, claims 1-6 are directed to a method, claims 7-12 are directed to an apparatus, claims 13-18 are directed to a non-transitory computer readable medium. Each of these claims fall within one of the four statutory categories (i.e., process, machine, manufacture, or composition of matter).
For claim 1,
Step 2A Prong One
decomposing the weight matrix W into vector products of an orbit weight matrix P containing information on each orbit and an orbit-class score matrix S;
(This step for decomposing a weight matrix into vector products is a mathematical concept)
selecting a specific node among nodes and classifying the selected specific node as the specific class;
(This step for selecting and classifying a node without any supporting structure is a mental process)
Step 2A Prong Two
A method of generating explanations for a graph neural network to be performed by an apparatus for generating explanations for the graph neural network, the method comprising: preparing the graph neural network that embeds an input graph into a node representation matrix H, and then outputs a result matrix Z in which a score of a specific class for each node is represented corresponding to the node representation matrix using a weight matrix W; … generating a global explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of orbit-class scores indicating contributions of orbits when the graph neural network classifies nodes into a specific class on the basis of results of decomposition; … and generating a local explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of node-orbit-class scores indicating contributions of nodes when the graph neural network classifies the selected specific node as the specific class on the basis of the results of decomposition.
(Each of these steps (preparing a GNN, receiving input, generating outputs) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes such as selecting and classifying and mathematical concepts such as decomposing a weight matrix into vector products while the additional elements are insignificant extra-solution activity recited at a high degree of generality.
For claim 2,
Step 2A Prong One
(Claim 2 depends on claim 1, which has been determined to recite abstract ideas including mental processes and mathematical concepts. Therefore, claim 2 also recites an abstract idea.)
Step 2A Prong Two
The method of claim 1, wherein the decomposing includes: training the orbit weight matrix P using each node embedding vector in the input graph as an input such that presence or absence of a specific orbit for each node is predictable using a vector product of each node embedding vector and an orbit weight vector; and training orbit-class scores using the trained orbit weight matrix P as an input such that the weight matrix W is able to be restored using a matrix product of the orbit weight matrix P and the orbit-class score matrix S.
(Each of these steps (parameter training) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes and mathematical concepts while the additional elements are insignificant extra-solution activity recited at a high degree of generality.
For claim 3,
Step 2A Prong One
The method of claim 2, wherein the training of the orbit weight matrix P includes: calculating the vector product for all node embedding vectors in the input graph, applying a sigmoid function to the vector product,
(This step for calculating the vector product and applying a sigmoid function are mathematical concepts)
Step 2A Prong Two
and then training a case in which the specific orbit exists at a corresponding node as 1 and a case in which the specific orbit does not exist at the corresponding node as 0; and normalizing the trained orbit weight vector in order to obtain an orbit weight vector of a certain size to train a final orbit weight vector containing orbit distribution information.
(Each of these steps (parameter training and normalization) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes and mathematical concepts while the additional elements are insignificant extra-solution activity recited at a high degree of generality.
For claim 4,
Step 2A Prong One
when a weight vector is decomposed into linear combinations of orbit weights.
(This step for decomposing a weight vector into linear combinations of orbit weights is a mathematical concept)
Step 2A Prong Two
The method of claim 2, wherein the training of the orbit-class scores comprises training coefficients
(This step (parameter training) is considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes and mathematical concepts while the additional elements are insignificant extra-solution activity recited at a high degree of generality.
For claim 5,
Step 2A Prong One
(Claim 5 depends on claim 1, which has been determined to recite abstract ideas including mental processes and mathematical concepts. Therefore, claim 5 also recites an abstract idea.)
Step 2A Prong Two
The method of claim 4, wherein the orbit-class score is limited to positive numbers at the time of training the coefficients.
(Each of these steps (parameter training) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes and mathematical concepts while the additional elements are insignificant extra-solution activity recited at a high degree of generality.
For claim 6,
Step 2A Prong One
wherein the training orbit-class scores is performed such that differences from the weight vector are reduced by selecting orbit weights one by one.
(This step for selecting orbit weights one by one during training without supporting structure is a mental process)
Step 2A Prong Two
The claim does not include additional elements, when considered separately and in combination, that integrate the judicial exception into a practical application.
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes and mathematical concepts without any technological improvement or inventive step.
For claim 7,
Step 2A Prong One
decompose the weight matrix W into vector products of an orbit weight matrix P containing information on each orbit and an orbit-class score matrix S;
(This step for decomposing a weight matrix into vector products is a mathematical concept)
selecting a specific node among nodes and classifying the selected specific node as the specific class;
(This step for selecting and classifying a node without any supporting structure is a mental process)
Step 2A Prong Two
An apparatus for generating explanations for a graph neural network, the apparatus comprising: a memory configured to store one or more instructions; and a processor configured to execute the one or more instructions stored in the memory, wherein the instructions, when executed by the processor, cause the processor to:
(This step for using a generic computing device is mere instructions to apply an exception. See MPEP § 2106.05(f))
prepare the graph neural network that embeds an input graph into a node representation matrix H, and then outputs a result matrix Z in which a score of a specific class for each node is represented corresponding to the node representation matrix using a weight matrix W;… generate a global explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of orbit-class scores indicating contributions of orbits when the graph neural network classifies nodes into a specific class on the basis of results of decomposition;… and generate a local explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of node- orbit-class scores indicating contributions of nodes when the graph neural network classifies the selected specific node as the specific class on the basis of the results of decomposition.
(Each of these steps (preparing a GNN, receiving input, generating outputs) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes such as selecting and classifying and mathematical concepts such as decomposing a weight matrix into vector products while the additional elements are mere-instruction to apply an exception and insignificant extra-solution activity recited at a high degree of generality.
For claims 8-12
Claims 8-12 are system claims directly corresponding to method claims 2-6 and are rejected under 101 using the same reasoning.
For claim 13,
Step 2A Prong One
decomposing the weight matrix W into vector products of an orbit weight matrix P containing information on each orbit and an orbit-class score matrix S;
(This step for decomposing a weight matrix into vector products is a mathematical concept)
selecting a specific node among nodes and classifying the selected specific node as the specific class;
(This step for selecting and classifying a node without any supporting structure is a mental process)
Step 2A Prong Two
A non-transitory computer readable storage medium storing computer executable instructions, wherein the instructions, when executed by a processor, cause the processor to perform a method of generating explanations for a graph neural network, the method comprising:
(This step for using a generic computing device is mere instructions to apply an exception. See MPEP § 2106.05(f))
preparing the graph neural network that embeds an input graph into a node representation matrix H, and then outputs a result matrix Z in which a score of a specific class for each node is represented corresponding to the node representation matrix using a weight matrix W;… generating a global explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of orbit-class scores indicating contributions of orbits when the graph neural network classifies nodes into a specific class on the basis of results of decomposition;… and generating a local explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of node-orbit-class scores indicating contributions of nodes when the graph neural network classifies the selected specific node as the specific class on the basis of the results of decomposition.
(Each of these steps (preparing a GNN, receiving input, generating outputs) are considered insignificant extra-solution activity. See MPEP § 2106.05(g))
Step 2B
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because, when considered individually and in combination, they do not add significantly more (also known as an inventive concept) to the exception. The claim recites mental processes such as selecting and classifying and mathematical concepts such as decomposing a weight matrix into vector products while the additional elements are mere-instruction to apply an exception and insignificant extra-solution activity recited at a high degree of generality.
For claims 14-18
Claims 14-18 are non-transitory computer readable medium claims directly corresponding to method claims 2-6 and are rejected under 101 using the same reasoning.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Rex Ying et al. (hereinafter Ying) (“GNNExplainer: Generating Explanations for Graph Neural Networks”, 2019-11-13), in view of Bolei Zhou et al. (hereinafter Zhou) (“Interpretable Basis Decomposition for Visual Explanation”, 2018), further in view of Thomas Kipf et al. (hereinafter Kipf) (“SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS”, 2017-02-22), further in view of Freddy Lecue (hereinafter Lecue) (US 11442963 B1, 2022-09-13), further in view of Ryan Rossi et al. (hereinafter Rossi) (US 20200177466 A1, 2020-06-04)
Regarding claim 1, Ying teaches;
A method of generating explanations for a graph neural network to be performed by an apparatus for generating explanations for the graph neural network, the method comprising:
([Abstract] Here we propose GNNEXPLAINER, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task.)
selecting a specific node among nodes and classifying the selected specific node as the specific class;
PNG
media_image1.png
178
1296
media_image1.png
Greyscale
[pg. 3]
NOTE: Ying teaches a node classification task, where a given node is classified to one specific class. Thus, Ying teaches selecting a specific node among nodes and classifying the selected specific node as the specific class.
and generating a local explanation in which
PNG
media_image2.png
231
1139
media_image2.png
Greyscale
[pg. 4]
NOTE: Teaches generating a local explanation (explanation of a node classification) in which a subgraph of the input graph is provided (the computation graph of v is limited to the explanation subgraph) indicating contributions of the nodes (the contribution graph is used to indicate the contribution of its nodes, vj) when the graph neural network classifies the selected specific node as the specific class (when the GNN classifies node vi as the specific class, as previously taught).
Ying fails to teach but Zhou teaches;
decomposing the weight matrix W into vector products of an
[pg. 9]
PNG
media_image3.png
136
797
media_image3.png
Greyscale
PNG
media_image4.png
693
1255
media_image4.png
Greyscale
NOTE: Zhou teaches decomposing a weight matrix W by decomposing each weight vector w_k of W into a linear combination of concept vectors q_c (which can be considered concept weight vectors, as they are derived from weight vectors) with class specific coefficients s_k (where the coefficients can be considered class scores, as they indicate contributions to the class). The matrix decomposition can be rewritten as W ≈ CS (or the transpose equivalent form), representing the decomposition of all weight vectors w_k of W, where C is the matrix containing the concept weight vectors, q_c, and S is the matrix containing all class specific coefficient vectors. Equivalently, the matrix product CS can be expressed as a sum of vector outer products. Thus, Zhou teaches decomposing a weight matrix W into vector products of a concept weight matrix C containing information on each concept and a concept-class score matrix S.
generating a global explanation in which
[pg. 9]
PNG
media_image5.png
143
856
media_image5.png
Greyscale
NOTE: Teaches generating a global explanation for an entire class k in which concepts (c) and their corresponding class scores (s_c) are provided indicating contributions of concepts when the neural network classifies images into class k on the basis of the results of the decomposition (s_c is derived from the decomposition of w_k).
and generating a local explanation in which
[pg. 10]
PNG
media_image6.png
371
1383
media_image6.png
Greyscale
NOTE: Teaches generating a local explanation of a specific prediction in which concept labels are provided in descending order of class scores (ranking the instance specific concept contribution scores / class scores, which indicate how the concept contributes to the classification) when the neural network classifies the image as class k on the basis of the results of the decomposition (contribution terms come from decomposed w_k).
OBVIOUSNESS TO COMBINE ZHOU WITH YING
Zhou and Ying are analogous art to the present disclosure as Zhou pertains to using matrix decompositions to generate explanations for neural network, and Ying pertains to generating explanations for Graph neural networks.
From Ying;
([Abstract] Here we propose GNNEXPLAINER, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GNNEXPLAINER identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN’s prediction.)
Ying teaches the need to explain GNN predictions and identifies compact subgraph structures that are crucial to a GNN prediction. It is model-agnostic and applies to node classification, graph classification, and link prediction.
From Zhou;
[pg. 10]
PNG
media_image7.png
206
1007
media_image7.png
Greyscale
NOTE: Zhou teaches that neural networks are black boxes that do not provide human interpretable justification for predictions, and proposes decomposing internal states of a neural network into interpretable components so the prediction can be explained by ranking component contributions.
Applying Zhou’s decomposition framework to the GNN setting of Ying’s GNNExplainer would have predictably improved the explanation by identifying not only which graph structures are important, how also how much each interpretable graph structure component contributes to the selected class prediction.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to apply the decomposition framework of Zhou to the GNN setting of Ying’s GNNExplainer to further improve the interpretability and expressivity of the GNN explanation.
Using this reasoning, Ying in view of Zhou reasonably teaches;
generating a local explanation in which
NOTE: Ying teaches locally explaining GNN node classification using subgraphs, while Zhou teaches generating local explanations where candidate explanations are ranked in order of class scores on the basis of results of a decomposition.
Ying and Zhou fail to teach but Kipf teaches;
preparing the graph neural network that embeds an input graph into a node representation matrix H, and then outputs a result matrix Z in which a score of a specific class for each node is represented corresponding to the node representation matrix using a weight matrix W;
[pg. 3]
PNG
media_image8.png
384
730
media_image8.png
Greyscale
NOTE: ReLU(ÂXW(0)) is a matrix which has one row per node, where each row is a learned vector representation of that node, which can be considered a node representation / embedding matrix. Thus, Kipf teaches preparing the graph neural network (the GCN / graph convolutional network) that embeds an input graph into a node representation matrix H (where H = ReLU(ÂXW(0))).
The output of the GCN is a matrix Z, where each row corresponds to a node, and each column corresponds to a class. The output Z corresponds to the node representation matrix ReLU(ÂXW) multiplied by a weight matrix W(1). Thus, Kipf teaches a graph neural network (the GCN) outputting a result matrix Z in which a score of a specific class for each node is represented corresponding to the node representation matrix ReLU(ÂXW(0)) using a weight matrix W(1).
OBVIOUSNESS TO COMBINE KIPF WITH YING AND ZHOU:
Kipf is analogous art to the present disclosure as it pertains to classification using graph neural networks.
Ying provides a method of explaining GNN classification predictions using important subgraphs while Kipf provides a baseline GNN node classification pipeline, having a node representation matrix, an output result matrix, and class scores for nodes.
From Kipf;
([pg. 9] We have introduced a novel approach for semi-supervised classification on graph-structured data. Our GCN model uses an efficient layer-wise propagation rule that is based on a first-order approximation of spectral convolutions on graphs. Experiments on a number of network datasets suggest that the proposed GCN model is capable of encoding both graph structure and node features in a way useful for semi-supervised classification. In this setting, our model outperforms several recently proposed methods by a significant margin, while being computationally efficient)
NOTE: The proposed GNN architecture of Kipf displays better performance for graph-based classification tasks compared to similar methods.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to provide the GNN structure proposed by Kipf (GCN) as the GNN structure used in GNNExplainer (Ying) to provide a GNN model for graph-based classification having competitive performance compared to related methods.
Ying, Zhou, and Kipf fail to teach but Lecue teaches;
generating a global explanation in which corresponding
([col. 23 ln. 24-31] The potential explanation ranking procedure 380 outputs, for each respective edge property type 318, respective set of ranked list of potential explanation subgraphs 384. The respective ranked list of potential explanations subgraphs 384 are considered to be potential explanations for the respective edge property type 318, i.e. class, ranked based on their respective probabilities, i.e. explanation expressivity scores.)
NOTE: Lecue pertains to explaining machine learning model graph classifications, where the model can be a neural network. Lecue teaches generating a global explanation (an explanation for an entire class / type) in which subgraphs of the input graph are provided in descending order (the subgraphs are ranked from highest to lowest score) of subgraph-class scores indicating contributions of subgraphs when the graph neural network classifies edges into a specific class (subgraphs are ranked based on explanation expressivity scores, which indicate the contribution of a subgraph to the class, which can be considered a subgraph-class score).
OBVIOUSNESS TO COMBINE LECUE WITH YING, ZHOU, AND KIPF:
Lecue is analogous art to the present disclosure as it pertains to generating explanations for graph-based classifications using ranked subgraphs.
Ying teaches GNN explanations using subgraphs, Zhou gives decomposition-based class contribution scores for explanations, Kipf provides the GCN/node-classification output structure, and Lecue supplies a method for ranking potential explanation subgraphs based on contribution scores for a class.
Lecue further states;
([col. 26 ln. 6-15] It will be appreciated that at least one or more embodiments of the present technology aim to expand a range of technical solutions for addressing a particular technical problem, namely improving performance of deep neural networks used for classification tasks in graphs by providing one or more subgraphs as potential explanations for a given class which enables interpretability of the classification, which may in turn enable tuning a deep neural network to be less prone to errors and enable saving computational resources.)
NOTE: Teaches that the method of providing ranked potential subgraphs enables interpretability of the classification, enabling less error prone tuning and decreased computational overhead.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to incorporate the ranked subgraph method of Lecue into Ying’s GNN explanation framework, using Kipf’s GCN/node-classification output structure, with Zhou’s decomposition-based contribution scores, to provide global explanations for a node class of the GNN, to further improve interpretability of the class, thereby decreasing computational overhead and errors during model tuning.
From this, Ying in view of Zhou, Kipf, and Lecue reasonably teaches;
generating a global explanation in which
NOTE: Ying teaches classifying selected nodes into a specific class using a GNN and explaining classifications using subgraphs, Zhou teaches global explanations where candidate explanations are associated with scores indicating contributions to a specific class on the basis of the results of decomposition, while Lecue teaches a global explanation where subgraphs of the input graph are provided as explanations in descending order of class scores indicating contributions of subgraphs when the GNN classifies into a specific class.
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
graphlets and orbits of a graph
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS TO COMBINE ROSSI WITH YING, ZHOU, KIPF, LECUE:
Rossi is analogous art to the present disclosure as it pertains to determining graphlet and orbit representations for a graph structure.
Ying and Lecue already teach explaining graph/GNN predictions using important subgraphs, Zhou teaches a matrix decomposition method for improving the interpretability of explanations, while Rossi teaches that graphlets and orbits are known higher order graph substructures for representing node roles, structural similarity, and subgraph patterns.
Rossi further states;
([0017] The techniques for higher-order network embedding are described herein as a general computational framework for deriving node (e.g., network entity) embeddings based on subgraph patterns (e.g., network motifs) that capture higher-order connectivity patterns and structural similarity between the nodes of a graph. The higher-order network embeddings may then be used for modeling user behavior, entity resolution, and other graph-based machine learning tasks that depend on an appropriate representation of a complex network.)
NOTE: Rossi states that representing nodes using subgraph patterns / motifs (such as the aforementioned orbits and graphlets) captures higher-order connectivity patterns, thereby providing more structurally meaningful insights of the graph or network.
Additionally, Ying states;
([pg. 2] We evaluate GNNEXPLAINER on synthetic as well as real-world graphs. Experiments show that GNNEXPLAINER provides consistent and concise explanations of GNN’s predictions. On synthetic graphs with planted network motifs, which play a role in determining node labels, we show that GNNEXPLAINER accurately identifies the subgraphs/motifs as well as node features that determine node labels outperforming alternative baseline approaches by up to 43.0% in explanation accuracy)
NOTE: Ying details the GNNExplainer is capable of utilizing motifs (such as the aforementioned graphlets and orbits) in explanations.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Using this reasoning, Ying in view of Zhou, Kipf, Lecue, and Rossi reasonably teach;
decomposing the weight matrix W into vector products of an orbit weight matrix P containing information on each orbit and an orbit-class score matrix S;
NOTE: Zhou teaches the weight matrix decomposition base, while Rossi teaches the graph / network orbit representations.
generating a global explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of orbit-class scores indicating contributions of orbits when the graph neural network classifies nodes into a specific class on the basis of results of decomposition;
NOTE: Ying teaches classifying selected nodes into a specific class using a GNN and subgraph based explanations, Zhou teaches a global explanation where candidate explanations are associated with scores indicating contributions to a specific class on the basis of the results of decomposition, Lecue teaches a global explanation where subgraphs of the input graph are provided in descending order of scores indicating contributions of subgraphs when the GNN classifies into a specific class, while Rossi teaches representing graph / network substructures (nodes, subgraphs) using graphlets and corresponding orbits.
and generating a local explanation in which corresponding orbits and graphlets including the corresponding orbits are provided as subgraphs of the input graph in descending order of node-orbit-class scores indicating contributions of nodes when the graph neural network classifies the selected specific node as the specific class on the basis of the results of decomposition.
NOTE: Ying provides a teaching for locally explaining GNN node classifications using subgraphs, Zhou teaches generating local explanations where explanations are ranked in order of class scores on the basis of results of a decomposition, while Rossi teaches representing graph / network substructures (nodes, subgraphs) using graphlets and corresponding orbits
Regarding claim 2, Ying fails to teach but Zhou teaches;
wherein the decomposing includes: training the absence of a specific
[pg. 8]
PNG
media_image9.png
150
1090
media_image9.png
Greyscale
NOTE: Each feature vector ‘a’ is the input to the classifier.
PNG
media_image10.png
299
1097
media_image10.png
Greyscale
[pg. 6]
NOTE: Teaches training the each learned concept weight vector w_c (which is the un-normalized form of the aforementioned q_c of the concept weight matrix C) using each feature vector as an input (feature vectors ‘a’ are used as input to the classifier during training) such that the presence or absence of a specific concept for each feature vector is predictable (the prediction indicates the probability of the concept appearing) using a vector product of each feature vector a and an orbit weight vector w_c.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to perform this training in a setting using orbits, nodes, and node embeddings, further explained later.
and training
[pg. 5]
PNG
media_image11.png
259
985
media_image11.png
Greyscale
NOTE: Teaches training (finding the optimal s using a minimization function can be considered training) the aforementioned concept class scores s_c using the trained concept weight matrix C (C is the matrix having each learned and normalized concept weight vector, q_c, as columns) as input (C is used in the minimization function) such that each weight vector w_k of the weight matrix W is able to be restored / approximated using a matrix product of the concept weight matrix C and the concept class score matrix s.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to perform this training in a setting using orbits, nodes, and node embeddings, further explained later.
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to apply the decomposition framework of Zhou to the GNN setting of Ying’s GNNExplainer to further improve the interpretability and expressivity of the GNN explanation.
Ying and Zhou fail to teach but Kipf teaches;
node embeddings as input to a classifier
[pg. 3]
PNG
media_image8.png
384
730
media_image8.png
Greyscale
NOTE: ReLU(ÂXW(0)) is a matrix which has one row per node, where each row is a learned vector representation of that node, which can be considered a node representation / embedding matrix of the graph, which is used as input to the GNN (GCN) classifier.
OBVIOUSNESS:
Ying teaches a method for GNN classification explanations, Zhou teaches training decomposed classifier parameters for explanation, while Kipf provides the GNN architecture (node embedding inputs, etc.) for tying the decomposition-based explanations of Zhou to the GNN classifications of Ying.
Using the same motivation from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to provide the GNN structure proposed by Kipf (GCN) as the GNN structure used in GNNExplainer (Ying) to provide a GNN model for graph-based classification having competitive performance compared to related methods.
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
Orbits
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Regarding claim 3, Ying fails to teach but Zhou teaches;
wherein the train of the orbit weight matrix P includes: calculating the vector product for all
and then training a case in which the specific
and normalizing the trained
[pg. 8]
PNG
media_image9.png
150
1090
media_image9.png
Greyscale
The input of the classifier includes each feature vector ‘a’ of the input.
[pg. 6]
PNG
media_image10.png
299
1097
media_image10.png
Greyscale
NOTE: Teaches calculating a vector product for each feature vector ‘a’ of the input, applying a sigmoid function to the vector product. Zhou further teaches training the binary classifier to detect whether concept c is present or absent in ‘a’.
The binary sigmoid classifier is trained with two target cases, y=1 (when the concept is present), and y=0 (when the concept is absent). Thus, Zhou teaches, and then training a case in which the specific concept exists at a corresponding location (the location specified by ‘a’) as 1 and a case in which the specific concept does not exist at the corresponding location as 0.
Zhou further teaches normalizing the trained concept weight vector (trained/learned concept weight vector w_c is normalized to q_c) in order to obtain a concept weight vector of a certain size (to eliminate arbitrary scaling, i.e., to obtain a concept weight vector of a certain size) to train a final orbit weight vector, q_c, which contains concept distribution information, because q_c captures information showing how the class weight is distributed across the concepts.
It would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to perform this process in setting having orbits instead of concepts and node embeddings instead of feature vectors, further explained later below.
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to apply the decomposition framework of Zhou to the GNN setting of Ying’s GNNExplainer to further improve the interpretability and expressivity of the GNN explanation.
Ying and Zhou fail to teach but Kipf teaches;
node embeddings of an input graph
[pg. 3]
PNG
media_image8.png
384
730
media_image8.png
Greyscale
NOTE: ReLU(ÂXW(0)) is an N x D matrix which has one row per node, where each row is a learned vector representation of that node, which can be considered a node representation / embedding matrix of the graph, which is used as input to the GNN (GCN) classifier.
OBVIOUSNESS:
Ying teaches a method for GNN classification explanations, Zhou teaches training decomposed classifier parameters for explanation, while Kipf provides the GNN architecture (node embedding inputs, etc.) for tying the decomposition-based explanations of Zhou to the GNN classifications of Ying.
Using the same motivation from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to provide the GNN structure proposed by Kipf (GCN) as the GNN structure used in GNNExplainer (Ying) to provide a GNN model for graph-based classification having competitive performance compared to related methods.
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
Orbits
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Regarding claim 4, Ying fails to teach but Zhou teaches;
wherein the training of the
[pg. 5]
PNG
media_image12.png
597
1152
media_image12.png
Greyscale
NOTE: Teaches training coefficients, s_c, when a weight vector is decomposed into linear combinations of concept weights (weight vector w_k is decomposed into linear combinations of concept weights q_c).
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
Orbits
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Regarding claim 5, Ying fails to teach but Zhou teaches;
the
[pg. 6]
PNG
media_image13.png
532
1151
media_image13.png
Greyscale
NOTE: Teaches the concept-class score, s_c, is limited to positive numbers at the time of training the coefficients (each coefficient s_c is positive).
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
Orbits
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Regarding claim 6, Ying fails to teach but Zhou teaches;
the training
[pg. 6]
PNG
media_image13.png
532
1151
media_image13.png
Greyscale
NOTE: Teaches training the aforementioned concept-class scores, s, being performed such that differences (residual error) from the weight vector, w_k, is reduced by selecting concept weights one by one (greedy addition of one candidate concept weight vector q_c at a time).
Ying, Zhou, Kipf, and Lecue fail to teach but Rossi teaches;
Orbits
([0041] Network Motifs: In aspects of higher-order network embedding, the framework can use graphlets or orbits, where the term network motifs 116 is used generally to refer to graphlets or orbits (also referred to as graphlet automorphisms). Notably, a graphlet H.sub.t=(V.sub.k, E.sub.k) is an induced subgraph consisting of a subset V.sub.k⊂V of k vertices from G=(V, E) together with all edges whose endpoints are both in this subset E.sub.k={∀e∈E|e=(u,v)∧u,v∈V.sub.k}. Alternatively, the nodes of every graphlet can be partitioned into a set of automorphism groups called orbits.)
OBVIOUSNESS:
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the previously taught decomposition based GNN classification explanations to use graphlets and corresponding orbits as the interpretable subgraph units to provide more structurally meaningful and human-interpretable graph explanations.
Regarding claim 7,
Claim 7 is an apparatus claim that is substantially similar to method claim 1, with one added limitation, which is taught by Lecue;
An apparatus …, the apparatus comprising: a memory configured to store one or more instructions; and a processor configured to execute the one or more instructions stored in the memory, wherein the instructions, when executed by the processor, cause the processor to:
([col. 4, ln. 31-33] The processor is operatively connected to a non-transitory storage medium comprising instructions, the processor, upon executing the instructions, is configured for… [performing the methods of the disclosure])
OBVIOUSNESS:
Ying provides the base implementation for GNN explanations and Lecue provides hardware capable of generating graph-based neural network explanations.
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to implement the system using the hardware taught by Lecue, to incorporate the ranked subgraph method of Lecue into Ying’s GNN explanation framework, using Kipf’s GCN/node-classification output structure, with Zhou’s decomposition-based contribution scores, to provide global explanations for a node class of the GNN, to further improve interpretability of the class, thereby decreasing computational overhead and errors during model tuning.
NOTE: The remaining limitations are substantially similar to claim 1 and are taught using the same reasoning provided in claim 1.
Regarding claims 8-12,
Claims 8-12 are apparatus claims which are substantially similar to method claims 2-6, and are rejected using the same reasoning.
Regarding claim 13,
Claim 13 is a non-transitory computer readable medium claim directly corresponding to method claim 1, with one added limitation, which is taught by Lecue;
A non-transitory computer readable storage medium storing computer executable instructions, wherein the instructions, when executed by a processor, cause the processor to perform…
([col. 4, ln. 31-33] The processor is operatively connected to a non-transitory storage medium comprising instructions, the processor, upon executing the instructions, is configured for… [performing the methods of the disclosure])
OBVIOUSNESS:
Ying provides the base implementation for GNN explanations and Lecue provides hardware capable of generating graph-based neural network explanations.
Using the same reasoning from claim 1, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to implement the system using the hardware taught by Lecue, to incorporate the ranked subgraph method of Lecue into Ying’s GNN explanation framework, using Kipf’s GCN/node-classification output structure, with Zhou’s decomposition-based contribution scores, to provide global explanations for a node class of the GNN, to further improve interpretability of the class, thereby decreasing computational overhead and errors during model tuning.
NOTE: The remaining limitations are substantially similar to claim 1 and are rejected using the same reasoning provided in claim 1.
Regarding claims 14-18,
Claims 14-18 are non-transitory computer readable medium claims directly corresponding to method claims 2-6, and are rejected using the same reasoning.
CONCLUSION
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Matthew Alan Cady whose telephone number is (571) 272-7229. The examiner can normally be reached Monday - Friday, 7:30 am - 5:00 pm ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Cesar Paula can be reached on (571)272-4128. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC)
at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/MATTHEW ALAN CADY/ Examiner, Art Unit 2145
/CESAR B PAULA/ Supervisory Patent Examiner, Art Unit 2145
Prosecution Insights