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 .
This action is in response to communications filed on 03/14/2023. Claims 1-20 are pending and have been examined.
Priority
Applicant’s claim for the benefit of a prior-filed application under 35 U.S.C. 119(e) or under 35 U.S.C. 120, 121, 365(c), or 386(c) is acknowledged.
Information Disclosure Statement
The information disclosure statement (IDS) submitted was filed on 11/06/2023. The submission is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Objections
Claim 10 is objected to because of the following informalities:
As per claim 10, it appears that “graph; and wherein” in lines 4-5 should be replaced with “graph, wherein” (note the comma instead of the semicolon and use of the word “and” because a wherein clause is not a method step).
Appropriate correction is required.
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.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claims recite a method, system, and medium comprising obtaining, generating, determining, and identifying.
The limitations “obtaining… generating… determining… and identifying…” as recited in claim 1 are each a process, under the broadest reasonable interpretation, covering performance of the limitations in the mind or by pen and paper (See Berkheimer v. HP, Inc., 881 F.3d 1360, 1366, 125 USPQ2d 1649 (Fed. Cir. 2018)) but for the recitation of generic computer components. That is, other than reciting “performed by one or more computing devices”, the limitation “obtaining a knowledge graph comprising a plurality of entities and a plurality of links between the plurality of entities, wherein a link from among the plurality of links is between at least two entities from among the plurality of entities and describes a relation between the at least two entities” in the context of the claim encompasses the user making observations. The limitation “generating, based on the knowledge graph, a query computation graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes comprises one or more anchor nodes, a root node, and one or more intermediate nodes positioned in one or more paths between the one or more anchor nodes and the root node” in the context of the claim encompasses the user making evaluations (e.g. in the mind or pen and paper). The limitation “determining a node cut of a query of the query computation graph, wherein the node cut comprises at least one node that cuts at least one path between each anchor node from among the one or more anchor nodes of the query computation graph and the root node of the query computation graph” in the context of the claim encompasses the user making a determination. The limitation “identifying one or more negative samples for the query computation graph by bidirectionally traversing the query computation graph in a first direction from the one or more anchor nodes to the node cut and in a second direction from the root node to the node cut” in the context of the claim encompasses the user making evaluations. If a claimed limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of generic computer components, then it falls within the “mental processes” grouping of abstract ideas. Accordingly, the claim recites an abstract idea. Accordingly, the claim recites an abstract idea.
This judicial exception is not integrated into a practical application. In particular, the claim recites additional elements. The claim recites “performed by one or more computing devices”. The elements are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using a generic computer component (e.g. See MPEP 2106.05(f)). Accordingly, the additional elements do not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea.
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements are no more than a generic computer component. Therefore, the claims are not patent eligible.
Claims 16 and 19 also recite similar claim language as claim 1, and thus have the same issues. It is noted, with respect to claim 16, that the claim recites “one or more processors; one or more non-transitory computer-readable media that collectively store instructions” to perform the method. The elements are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using a generic computer component (e.g. See MPEP 2106.05(f)). It is noted, with respect to claim 15, that the claim further recites “One or more non-transitory computer-readable media that collectively store instructions that, when executed by one or more processors of a computing system, cause the computing system” to perform the method. The elements are recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using a generic computer component (e.g. See MPEP 2106.05(f)). Accordingly, the additional elements do not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea and are not sufficient to amount to significantly more than the judicial exception.
Regarding claim 2, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes performing depth-first search on the query computation graph, which is a mental step (encompassing the user performing evaluations) and does not include any additional elements. This similarly apples to claims 17 and 20.
Regarding claim 3, the claim does not include any additional elements that are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes traversing in the first direction including caching, but it is recited at a high-level of generality, such that it amounts to no more than mere instructions to apply the exception using a generic computer component (e.g. See MPEP 2106.05(f)). This similarly applies to claim 18.
Regarding claim 4, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes comparing and determining, which are mental steps (encompassing the user performing observations and determinations) and does not include any additional elements.
Regarding claim 5, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the determining, which is part of the mental steps (encompassing the user performing determinations) and does not include any additional elements.
Regarding claim 6, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes obtaining and determining, which are mental steps (encompassing the user making observations and determinations) and does not include any additional elements.
Regarding claim 7, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the traversing including randomly sampling, which is a mental step (encompassing the user making determinations) and does not include any additional elements.
Regarding claim 8, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the nodes and edges (encompassing the user making determinations), which is part of the mental steps and does not include any additional elements.
Regarding claim 9, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the transformation, which is part of the mental steps (encompassing the user making determinations) and does not include any additional elements.
Regarding claim 10, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes calculating, which is a mental step (encompassing the user making calculations) and does not include any additional elements.
Regarding claim 11, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the calculating, which includes further mental steps (encompassing the user making determinations) and does not include any additional elements.
Regarding claim 12, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the graph and the query, which is part of the mental steps and does not include any additional elements.
Regarding claim 13, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the root node, which is part of the mental steps and does not include any additional elements.
Regarding claim 14, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the query, which is part of the mental steps and does not include any additional elements.
Regarding claim 15, the claim does not include any additional elements that integrate the abstract idea into a practical application or are sufficient to amount to significantly more than the judicial exception. For example, the claim merely further describes the graph, which is part of the mental steps and does not include any additional elements.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-20 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Ren et al. ("SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs", arXiv:2110.14890v2, November 1, 2021, 18 pages as cited in IDS dated 11/06/2023). The applied reference has a common joint inventor with the instant application (note, however, that Jure Leskovec is part of the reference, but is not an inventor of the present application). Based upon the earlier effectively filed date of the reference, it constitutes prior art under 35 U.S.C. 102(a)(2). This rejection under 35 U.S.C. 102(a)(2) might be overcome by: (1) a showing under 37 CFR 1.130(a) that the subject matter disclosed in the reference was obtained directly or indirectly from the inventor or a joint inventor of this application and is thus not prior art in accordance with 35 U.S.C. 102(b)(2)(A); (2) a showing under 37 CFR 1.130(b) of a prior public disclosure under 35 U.S.C. 102(b)(2)(B) if the same invention is not being claimed; or (3) a statement pursuant to 35 U.S.C. 102(b)(2)(C) establishing that, not later than the effective filing date of the claimed invention, the subject matter disclosed in the reference and the claimed invention were either owned by the same person or subject to an obligation of assignment to the same person or subject to a joint research agreement.
As per independent claim 1, Ren teaches a computer-implemented method for negative sampling with improved efficiency, the method performed by one or more computing devices and comprising:
obtaining a knowledge graph comprising a plurality of entities and a plurality of links between the plurality of entities, wherein a link from among the plurality of links is between at least two entities from among the plurality of entities and describes a relation between the at least two entities (e.g. in page 1, “A knowledge graph (KG) is a heterogeneous graph structure that captures knowledge encoded in a form of head–relation–tail triples, where the head and tail are two entities (i.e., nodes) and the relation is an edge [i.e. link] between them” and figure 1 showing links between entities);
generating, based on the knowledge graph, a query computation graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes comprises one or more anchor nodes, a root node, and one or more intermediate nodes positioned in one or more paths between the one or more anchor nodes and the root node (e.g. in page 3, “A query computation plan (Figure 1(B)) provides a plan for executing the query. The computation plan consists of nodes Vq ∪ {V1, . . . , Vk, V?}, where each node corresponds to a set of entities on the KG… the computation plan is a tree, where the anchor entity set, Vq, are the leaves and the target variable V? is the single root, representing the set of answer entities” and figure 1B showing blue anchor nodes, gray intermediate nodes, and green root node);
determining a node cut of a query of the query computation graph, wherein the node cut comprises at least one node that cuts at least one path between each anchor node from among the one or more anchor nodes of the query computation graph and the root node of the query computation graph (e.g. in page 2, “The key insight of the training data sampler is to identify the optimal node cut (red node in Figure 2(C)) of the computation plan via dynamic programming, then performing forward KG traversal (Figure 2(C)) as well as backward verification (Figure 2(D)) simultaneously, hence bidirectional rejection sampling”); and
identifying one or more negative samples for the query computation graph by bidirectionally traversing the query computation graph in a first direction from the one or more anchor nodes to the node cut and in a second direction from the root node to the node cut (e.g. in page 2, “a bidirectional rejection sampling approach to efficiently obtain high-quality negative entities for the instantiated queries… The nodes in the optimal cut cache the intermediate results from the forward [i.e. anchor to cut] KG traversal; for backward verification, we propose positive and negative candidate entities, traverse backward to the optimal cut [i.e. root to cut] and perform rejection sampling based on the overlap of the forward and backward sets”).
As per claim 2, the rejection of claim 1 is incorporated and Ren further teaches performing a depth-first search over the query computation graph from the root node of the query computation graph to the one or more anchor nodes of the query computation graph, wherein each node of the query computation graph is grounded to an entity on the knowledge graph and an edge of the query computation graph is grounded to a relation on the knowledge graph associated with a previously grounded entity on the knowledge graph (e.g. in page 4, “Reverse directional sampling uses depth-first search (DFS) over the query structure from the root (answer) to the leaves (anchor entities). During the DFS, each node on the query structure is grounded to an entity on the KG and an edge to a relation on the KG associated with the previously grounded entity”).
As per claim 3, the rejection of claim 1 is incorporated and Ren further teaches wherein traversing the query computation graph in the first direction from the one or more anchor nodes to the node cut comprises caching the one or more intermediate nodes, wherein the intermediate nodes are obtained while traversing the query computation graph in the first direction (e.g. in page 5, “We first start the traversal from the leaves (anchors) to the node cut and cache the entities we obtained in traversal”).
As per claim 4, the rejection of claim 3 is incorporated and Ren further teaches comparing overlap of the cached one or more intermediate nodes and a set of nodes traversed while traversing the query computation graph in the second direction from the root node to the node cut and determining, based on the overlap, that a node from among the set of nodes traversed is a negative non-answer to the query, wherein a negative sample comprises the negative non-answer to the query (e.g. in page 2, “for backward verification, we propose positive and negative candidate entities, traverse backward to the optimal cut [i.e. root to cut] and perform rejection sampling based on the overlap of the forward and backward sets… which makes it feasible to generate a training query, a positive answer entity and negative non-answer entities on the fly”).
As per claim 5, the rejection of claim 4 is incorporated and Ren further teaches wherein determining, based on the overlap, that a node from among the set of nodes traversed is a negative non-answer to the query comprises determining that there is no overlap between the cached one or more intermediate nodes and the set of nodes traversed while traversing the query computation graph in the second direction from the root node to the node cut (e.g. in page 5, “NGq does not have to contain all the non-answer entities… traverse from the root to the node cut and verify whether they are true negatives by checking the overlap of the cached entities and the traversed set” and figure 2D).
As per claim 6, the rejection of claim 3 is incorporated and Ren further teaches wherein obtaining, from the query computation graph, a candidate negative node and determining whether the candidate negative node overlaps with the cached one or more intermediate nodes (e.g. in page 5, “traverse from the root to the node cut and verify whether they are true negatives by checking the overlap of the cached entities and the traversed set” and figure 2D).
As per claim 7, the rejection of claim 1 is incorporated and Ren further teaches wherein bidirectionally traversing the query computation graph in the first direction from the one or more anchor nodes to the node cut and in the second direction from the root node to the node cut comprises randomly sampling one or more negative candidate nodes in the second direction (e.g. in pages 10, “bidirectional sampler (bidirectional) and randomly sampling KG entities as negative answers (random)”).
As per claim 8, the rejection of claim 1 is incorporated and Ren further teaches wherein each node from among the plurality of nodes of the query computation graph corresponds to a set of entities on the knowledge graph and the plurality of edges of the query computation graph represent a logical relational transformation of the set of entities on the knowledge graph (e.g. in page 3, “A query computation plan…consists of nodes Vq ∪ {V1, . . . , Vk, V?}, where each node corresponds to a set of entities on the KG… edges in the computation plan represent a logical/relational transformation of this set”).
As per claim 9, the rejection of claim 8 is incorporated and Ren further teaches wherein the logical relational transformation of the set of entities on the knowledge graph comprises one or more of relation projection, intersection, union, complement, and negation (e.g. in page 3, “a logical/relational transformation of this set, including relation projection, intersection, union and complement/negation”).
As per claim 10, the rejection of claim 1 is incorporated and Ren further teaches calculating computation costs for one or more node cuts based on paths between each anchor node from among the one or more anchor nodes of the query computation graph and the root node of the query computation graph and wherein the node cut comprises a node cut from among the one or more node cuts with a lowest computation cost (e.g. in page 5, “calculate the computation cost for any given node cut cq, and then we propose an efficient algorithm to find the optimal node cut, i.e., one with the lowest cost in bidirectional search”).
As per claim 11, the rejection of claim 10 is incorporated and Ren further teaches wherein calculating the computation costs for the one or more node cuts (e.g. in page 5, “calculate the computation cost for any given node cut cq, and then we propose an efficient algorithm to find the optimal node cut, i.e., one with the lowest cost in bidirectional search”) comprises: determining a maximum number of relation projections in the paths between each anchor node from among the one or more anchor nodes of the query computation graph and the root node of the query computation graph (e.g. in page 5, “maximum cost of forward traversal or backward verification”); determining a length of a path from each anchor node from among the one or more anchor nodes of the query computation graph to one or more anchor nodes from among the one or more anchor nodes of the query computation graph, wherein the length of the path comprises a number of relation projections on the path (e.g. in page 5, “representing the number of relation projections from v to the root V?, the maximum length of path from v to any anchor); and determining optimal costs of resolving the paths between each anchor node from among the one or more anchor nodes of the query computation graph and the root node of the query computation graph (e.g. in page 5, “the optimal cost of resolving all the reasoning paths that include v in the best plan”).
As per claim 12 the rejection of claim 1 is incorporated and Ren further teaches wherein the query computation graph comprises a plan for executing the query, wherein the query is executed in an embedding space (e.g. in page 2, “executing the query directly in the embedding space” and page 3, “A query computation plan (Figure 1(B)) provides a plan for executing the query”).
As per claim 13 the rejection of claim 1 is incorporated and Ren further teaches wherein the root node of the query computation graph comprises a known positive answer to the query (e.g. in page 2, “root of the instantiated query represents a known positive (answer) entity”).
As per claim 14 the rejection of claim 1 is incorporated and Ren further teaches wherein the query is a first-order logical query (e.g. in page 3, “first-order logical (FOL) query”).
As per claim 15 the rejection of claim 1 is incorporated and Ren further teaches wherein the knowledge graph is a heterogeneous graph (e.g. in page 3, “A knowledge graph (KG) is a heterogeneous graph structure”).
Claims 16-18 are the system claims corresponding to method claims 1-3 and are rejected under the same reasons set forth and Ren teaches one or more processors and one or more non-transitory computer-readable media that collectively store instructions that, when executed by the one or more processors, cause the one or more processors to perform operations (e.g. in page 6, “SMORE is built for a shared memory environment with multi-cores and multi-GPUs. It combines the usage of CPU and GPU”).
Claims 19-20 are the medium claims corresponding to method claims 1-2 and are rejected under the same reasons set forth and Ren teaches one or more non-transitory computer-readable media that collectively store instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations (e.g. in page 6, “SMORE is built for a shared memory environment with multi-cores and multi-GPUs. It combines the usage of CPU and GPU”).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
For example,
Lecue et al. (US 20200074319 A1) teaches “receiving, by the PKG platform, data representative of at least one answer provided from the user to a respective question, providing, by the PKG platform, an expanded knowledge graph based on the initial knowledge graph, the expanded knowledge graph including one or more nodes and respective edges based on the data” (e.g. in paragraph 16).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WILLIAM WONG whose telephone number is (571)270-1399. The examiner can normally be reached Monday-Friday 9am-5pm.
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, TAMARA KYLE can be reached at (571)272-4241. 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.
/W.W/Examiner, Art Unit 2144 01/09/2026
/TAMARA T KYLE/Supervisory Patent Examiner, Art Unit 2144