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 .
Response to Arguments
Applicant’s arguments regarding the 103 rejection have been fully considered but are respectfully not persuasive. Applicant argues that the Zhu reference (cited as Ali in the rejection) does not teach the elements not cited from Zheng. In particular, it is argued that the references do not teach nodes that are “invisible” or features that cannot be accessed by the server, or use of those embeddings to augment a subsequent training stage. It is also argued that regarding Zhu/Ali specifically that it des not teach pre-computed, abstract embeddings to use as a substitute for raw data.
In response, Examiner argues that as per MPEP 2111.01.II, it is improper to import claim limitations from the specification, “"Though understanding the claim language may be aided by explanations contained in the written description, it is important not to import into a claim limitations that are not part of the claim. For example, a particular embodiment appearing in the written description may not be read into a claim when the claim language is broader than the embodiment." Superguide Corp. v. DirecTV Enterprises, Inc., 358 F.3d 870, 875, 69 USPQ2d 1865, 1868 (Fed. Cir. 2004).” In this situation, Applicant appears to be improperly importing limitations from the specification as it is not recited anywhere in the claims that invisible is defined as features not accessed by a server. The broadest reasonable interpretation of invisible to the first sever is simply not seen. “Seen” in this case as well has many broadest reasonable interpretations. Further so, even if one was to look into the specification, the specification merely describes as invisible nodes being nodes that the host has no awareness, which is consistent with the general definition of invisible. The cited prior art meets these limitations because the combination of Zheng with Ali introduces multiple GNN systems that do not necessarily interact with each other, these meeting the limitations of “invisible”. Applicant argues that the Zhu/Ali reference makes a call to a graph as needed, however as the reference states this is just in the situation of the data is not cached. The existence of cached data is the data that is invisible to the first sever, so a cache is stored locally. In this case, data being visible or invisible to a server simply means does the data originate from that server. Should the Applicant wish for the claims to be read with their intentions, Examiner suggest stronger language than visible/invisible, such as accessible with/accessible to.
Applicant argues that there is no motivation to combine the two cited references since they allegedly require a redesign of training architecture. In response, Examiner argues that the two reference are not being combined in their entirety but rather, known and useful aspects from the two. Ali in particular teaches optimal methods of storing and/or receiving data that it doesn’t have, i.e. invisible data.
Dependent claims 16-19 have been fully considered but their arguments are moot in light of a rejection necessitated by the amendment.
Claim Rejections - 35 USC § 103
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 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-15 and 18-19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zheng, Da, et al. "DistDGL: Distributed graph neural network training for billion-scale graphs." in view of Zhu, Rong, et al. "Aligraph: A comprehensive graph neural network platform." [herein Ali].
Regarding claims 1 and 14, Zheng teaches “a computer-implemented method for distributed training of a graph-embedding neural network, the method performed at a first server and comprising” (abstract “DistDGL distributes the graph and its associated data (initial features and embeddings) across the machines and uses this distribution to derive a computational decomposition by following an owner-compute rule. DistDGL follows a synchronous training approach and al lows ego-networks forming the mini-batches to include non-local nodes”):
“computing, based on a first input data sample, first model data and first embedding data of a first graph neural network, the first graph neural network corresponding to a first set of nodes of a graph that are visible to the first server” (pg. 2 left col. ¶1 “It distributes graph data (both graph structure and the associated data, such as node and edge features) across all machines and run trainers, sampling servers (for sampling subgraphs to generate mini-batches) and in-memory KVStore servers (for serving node data and edge data) all on the same set of machines”);
“sharing the first model data and the first embedding data with a second server” (pg. 3 left col. “A number of trainers that compute the gradients of the model parameters over a mini-batch. At each iteration, they first fetch the mini-batch graphs from the samplers and the corresponding vertex/edge features from the KVStore. They then run the forward and backward computation on their own mini-batches in parallel to compute the gradients.” i.e. sharing);
While Zheng generally teaches the remaining limitations Ali, in the same field of endeavor teaches “receiving second embedding data from a third server” (Ali pg. 3 left col. “If the neighbors of a vertex are not cached, a call to remote graph server is needed. When getting the context of a batch of vertices, we first partition the vertices into sub-batches, and the context of each sub-batch will be stitched together after being returned from the corresponding graph server”), “the second embedding data comprising embedding data of a second graph neural network corresponding to a second set of nodes of the graph that are invisible to the first server” (pg. 5 §3.3 “Recall that, GNN algorithms rely on aggregating neighborhood information to generate embeddings of each vertex. However, the degree distribution of real-world graphs is often skewed [48], which makes the convolution operation hard to operate. To tackle this, existing GNNs usually adopt various sampling strategies to sample a subset of neighbors with aligned sizes”); and
“computing second model data of the first graph neural network based on a second input data sample and the embedding data of the second graph neural network” (Ali previous citation “existing GNNs usually adopt various sampling strategies to sample a subset of neighbors with aligned sizes” i.e. using the other data to compute the current data)
It would have been obvious to one having ordinary skill in the art at the time that the invention was effectively filed to combine the teachings of Zheng with that of Ali since “AliGraph runs 40%-50% faster with the novel caching strategy and demonstrates around 12 times speed up with the improved runtime. In addition, our in-house developed GNNmodels all showcase their statistically significant superiorities in terms of both effectiveness and efficiency (e.g., 4.12%–17.19% lift by F1 scores).” Ali abstract. That is, by combining the two references, one would have faster distributed GNN training.
Note that independent claim 14 recites the same substantial subject matter as independent claim 1, only differing in embodiment. The difference in embodiment, a computer-implemented method as opposed to a computer service executing the method are an obvious vibration of another. The additional limitations of a processor and memory are inherent components to any computing system such as the system of Zheng and Ali.
Regarding claim 2, the Zheng and Ali references have been addressed above. Ali further teaches “computing third embedding data of the first graph neural network based on the second input data sample and the second embedding data” (Ali pg. 5 §3.3 “Recall that, GNN algorithms rely on aggregating neighborhood information to generate embeddings of each vertex. However, the degree distribution of real-world graphs is often skewed [48], which makes the convolution operation hard to operate. To tackle this, existing GNNs usually adopt various sampling strategies to sample a subset of neighbors with aligned sizes” the system is not limited to any particular number of servers/data and therefore the functionality is the same whether its third, fourth, fifth, data, etc.); and
Zheng teaches “sharing the third embedding data with the second server” (pg. 8 right col. “GNN models are composed of multiple operators organized into multiple graph convolution network layers shared among all nodes and edges”)
Regarding claim 3, the Zheng and Ali references have been addressed above. Ali further teaches “wherein the embedding data of the second graph neural network is computed by a fourth server” (Ali pg. 5 §3.3 “Recall that, GNN algorithms rely on aggregating neighborhood information to generate embeddings of each vertex. However, the degree distribution of real-world graphs is often skewed [48], which makes the convolution operation hard to operate. To tackle this, existing GNNs usually adopt various sampling strategies to sample a subset of neighbors with aligned sizes” the system is not limited to any particular number of servers/data and therefore the functionality is the same whether its third, fourth, fifth, data, etc.)
Regarding claim 4, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein the third server is a parameter server that receives the embedding data of the second graph neural network from the fourth server” (pg. 3 left col. “A number of trainers that compute the gradients of the model parameters over a mini-batch. At each iteration, they first fetch the mini-batch graphs from the samplers and the corresponding vertex/edge features from the KVStore.”)
Regarding claim 5, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein the third server is the fourth server” (abstract “we develop DistDGL, a system for training GNNs in a mini-batch fashion on a cluster of machines.” i.e. servers/machines can be the same or not)
Regarding claim 6, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein the second server is different than the fourth server” (abstract “we develop DistDGL, a system for training GNNs in a mini-batch fashion on a cluster of machines.” i.e. servers/machines can be the same or not and fig. 3 which shows two distinct machines/servers)
Regarding claim 7, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein sharing the third embedding data with the second server comprises sharing the computed third embedding data and the second embedding data received from the third server” (pg. 8 right col. “GNN models are composed of multiple operators organized into multiple graph convolution network layers shared among all nodes and edges”)
Regarding claim 8, the Zheng and Ali references have been addressed above. Ali further teaches “wherein the third server combines the first embedding data and the embedding data of the second graph neural network to form the second embedding data” (Ali pg. 3 algorithm 1 shows combination of vertexes/embeddings)
Regarding claim 9, the Zheng and Ali references have been addressed above. Zheng further teaches “further comprising sharing the second model data of the first graph neural network with the second server” (pg. 8 right col. “GNN models are composed of multiple operators organized into multiple graph convolution network layers shared among all nodes and edges”)
Regarding claim 10, the Zheng and Ali references have been addressed above. Zheng further teaches “further comprising receiving third model data, comprising a model of the graph-embedding neural network, from the third server, said third model data being used when computing said second model data” (pg. 2 right col. “This sampling strategy forms a computation graph for passing messages on. Figure 1b depicts such a graph for computing representation of one target vertex when the GNN has two layers. The sampled graph and together with the extracted features are called a mini-batch in GNN training” which can and is received by any of the servers and used by any)
Regarding claim 11, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein said third model data comprises aggregate model data obtained by aggregating, at the third server, a plurality of model data received from different servers” (pg. 3 left col. “A dense model update component for aggregating dense GNN parameters to perform synchronous SGD. Dist DGL reuses the existing components depending on DGL’s backend deep learning frameworks”)
Regarding claim 12, the Zheng and Ali references have been addressed above. Zheng further teaches “further comprising aggregating the third model data with the first model data to produce aggregate model data; and using the aggregate model data when computing the second model data” (pg. 3 left col. “A dense model update component for aggregating dense GNN parameters to perform synchronous SGD. Dist DGL reuses the existing components depending on DGL’s backend deep learning frameworks” and pg. 6 left col. “This hybrid approach is potentially more advantageous than the multiprocessing approach for synchronous SGD because we need to aggregate gradients of model parameters from all trainer processes and broadcast new model parameters to all trainers. More trainer processes result in more communication overhead for model parameter updates”)
Regarding claim 13, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein computing the second model data of the first graph neural network comprises integrating the embedding data of the second graph neural network into the first graph neural network beginning at a first convolutional layer of the first graph neural network” (pg. 2 right col. “Similar to convolutional neural networks (CNNs), a GNN model iteratively applies Equations (1) to generate vertex representations for multiple layers.”).
Regarding claim 15, the Zheng and Ali references have been addressed above. Zheng further teaches “the computer server of claim 14; and at least one server, connected to the computer server” (abstract “we develop DistDGL, a system for training GNNs in a mini-batch fashion on a cluster of machines” machines i.e. servers),
Ali teaches “said at least one server configured to receive model data and embedding data from the computer server and to return aggregate model data and aggregate embedding data to the computer server” (pg. 3 right col. “Specifically, we apply the SAMPLE function
to fetch a subset S of vertices based on the neighbor set Nb(v) of vertex v, aggregate the embeddings of all vertices u 2 S by the AGGREGATE function to obtain a vector h0 v, and combine h0 v with h(k1) v to generate the embedding vector h(k) v by the COMBINE function. After processing all vertices, the embedding vectors are normalized. Finally, after kmax hops, h(kmax) v is returned as the embedding result hv of vertex v”)
Regarding claim 18, the Zheng and Ali references have been addressed above. Zheng further teaches “wherein the received second embedding data are propagated from a first hidden layer of the first graph neural network to a second hidden layer of the first graph neural network” (pg. 4 §C “The features of vertices and edges are partitioned and stored in multiple machines. Even though DistDGL partitions a graph to assign densely connected vertices to a partition, we still need to read data from remote partitions. To simplify the data access on other machines, DistDGL develops a distributed in memory key-value store (KVStore) to manage the vertex and edge features as well as vertex embeddings,”)
Regarding claim 19, the Zheng and Ali references have been addressed above. Zheng further “teaches wherein the second embedding data are used in place of feature data associated with the second set of nodes” (pg. 5 ¶ above §D “In GNN mini-batch training, only a small subset of vertex embeddings are involved in the computation and updated during each iteration” i.e. using the embeddings)
Claim(s) 16-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zheng in view of Ali further in view of Mei, Guangxu, et al. "Sgnn: A graph neural network based federated learning approach by hiding structure."
Regarding claim 16, the Zheng and Ali references have been addressed above. More specifically, Mei teaches “wherein the second set of nodes corresponds to nodes for which the first server has no feature information” (Mei pg. 4 §III “Users’ private information should be protected carefully and users’ content information and structural information could be represented separately. Instead of including its own features merely, the embedding of a node could be aggregated from information of its local neighborhood in cluding their structure and features.To avoid leaking these private information, we use federated learning framework to solve our problem more suitably” wherein federated learning inherently keeps data private)
It would have been obvious to one having ordinary skill in the art at the time that the invention was filed to combine the teachings of Zheng and Ali with that of Meng since “We use deep graph neural network with convolutional layers and dense layers to classify the nodes based on their structures and features. The node classification experiment results on public data sets including Aminer coauthor network, Brazil and Europe flight networks indicate that our proposed model outperforms state-of-the-art models with a higher accuracy” Meng abstract. This shows that by utilizing these techniques together, one has better (more accurate) models.
Regarding claim 17, the Zheng, Ali, and Mei references have been addressed above. Mei further teaches “wherein the first server cannot access feature information associated with the second set of nodes” (previous citations, again in federated learning, data is private and secure, i.e. other servers cannot access other data)
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to KEVIN W FIGUEROA whose telephone number is (571)272-4623. The examiner can normally be reached Monday-Friday, 10AM-6PM EST.
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, MIRANDA HUANG can be reached at (571)270-7092. 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.
KEVIN W FIGUEROA
Primary Examiner
Art Unit 2124
/Kevin W Figueroa/Primary Examiner, Art Unit 2124
Prosecution Insights