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 responsive to the Application filed on December 21, 2023. Claims 10-17 are cancelled. Claims 1-9, 18, and 19 are pending in the case. Claims 1, 18, and 19 are the independent claims.
This action is non-final.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
For example, claim 19 recites “a means for mirror fusion unit, configured to perform the following fusion operations…” and “a means for sending unit, configuration to sequentially send….”
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.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1, 2, 4-6, 8, 9, 18, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Md et al. DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks. ArXiv.org. April 16, 2021. arXiv:2104.06700. Retrieved from the Internet: https://arxiv.org/pdf/2104.06700. (hereinafter referred to as “Md”).
With respect to claims 1, 18, and 19, Md teaches a non-transitory computer-readable storage medium for distributed graph learning…the non-transitory computer-readable storage medium comprising instructions stored therein that, when executed by a processor of a computing device, cause the processor to perform a method; a computing device for distributed graph learning… the computing device comprises: a means for mirror fusion unit… and a means for sending unit, configured to perform respective method steps (e.g. page 6, section 6.1, system utilized includes either a device having Intel Xeon 8280 CPU with 28 cores and 98 GB of memory per socket for single socket experiments or a cluster with 64 Intel Xeon 9242 CPUs with 48 cores per socket, and where each compute node is equipped with 384 GB of memory for distributed memory runs; the section further describes the software (executable instructions) executed on the system); and the data fusion method for distributed graph learning, applied to a distributed graph learning process for graph data in a distributed system,
wherein a single device in the distributed system is pre-allocated with a plurality of graph nodes of the graph data and a corresponding node connection relationship, a first device comprises N graph nodes and M mirror nodes, a single mirror node is a mirror of a corresponding graph node on another device, the single graph node corresponding to the single mirror node on the another device and a single graph node in the N graph nodes are neighboring nodes of each other (e.g. page 1, second column, third full paragraph, DistGNN consists of family of scalable distributed solutions for large scale training on clusters on CPUs; page 2, second column, section 3, employing data parallelism by portioning input graph across CPU sockets or GPU cards; distributed multi-GPU systems; page 4, second column, section 5.1, using vertex-cut based graph partitions to distribute the edges among the partitions; each edge is present in only one partition, while a vertex can reside in multiple ones; each vertex that splits due to the vertex-cut carries with it a partial neighborhood of the original vertex from the input graph; clones of such vertex in other partitions; page 4, second column, section 5.2, continuing on page 5, first column; partition has two types of vertices: split-vertices and non-split vertices; split-vertices have their own copy of the feature vector; thus each vertex in a partition is associated with a feature vector and takes part in local aggregation; Fig. 1(b) showing partitioned version of original graph of Fig. 1(a), (where each partition would be allocated to a corresponding device such as a GPU for that partition) where at least one partition includes a plurality of graph nodes/vertices and edges/connections, including at least one graph node/vertex and at least one clone/mirror node/vertex which corresponds to a graph node/vertex in a different partition (and therefore device), and one or more graph nodes/vertices in the first partition are neighboring nodes of the graph node/vertex in the other partition which corresponds to the clone/mirror node, as shown in the original graph of Fig. 1(a)), and
in a data fusion process for distributed graph learning, the method is performed by the first device, and comprises: performing the following fusion operations on each of the M mirror nodes through a plurality of mutually independent mirror fusion threads (e.g. page 3, section 4.1, describing implementation of aggregation; computation is parallelized by distributing destination vertices across OpenMP threads; this way, there are no collisions because only one thread owns the feature vector at each destination vertex; page 3, second column, final paragraph, continuing on page 4, utilizing cache blocking by parallelizing across source vertices leading to race conditions on destination vertices; for each block, going through all destination vertices in parallel ensuring that all threads work on one block B of source vertices at a time; using dynamic thread scheduling with OpenMP, allocating a chunk of contiguous destination vertices at a time to ensure that a thread writes to contiguous feature vectors):
obtaining a current representation vector of the single mirror node, wherein the current representation vector of the single mirror node is provided by a device in which the corresponding graph node is located (e.g. page 4, second column, section 5.1, when partitioning is performed, each vertex that splits due to vertex-cut results in clones in various partitions; page 4, second column, section 5.2, indicating that when partitioning is performed, each split-vertex receives its own copy of the feature vector; page 5, section 5.3(2), describing portion of set of algorithms used during aggregation operation, indicating that all split-vertices communicate partial aggregates to their remote clones such that each vertex in each partition receives its complete neighborhood; i.e. when the graph is partitioned, each clone/mirror vertex/node receives a complete copy of its feature vector, analogous to obtaining a current representation vector for the single mirror node from a device where the corresponding graph node is located);
determining a mirror fusion vector of the single mirror node based on a current representation vector of the graph node and a current representation vector of each neighboring node of the graph node on the first device, wherein a representation vector of a single node is used to describe attribute information of a corresponding graph node (e.g. page 5, section 5.3 on first and second columns, describing aggregation operations; at each layer, each partition first performs local aggregation; after local aggregation, each split-vertex (i.e. clone/mirror node) has aggregated from its local partial neighborhood; i.e. local aggregation at the split-vertex (which is a clone/mirror node in a corresponding partition) includes aggregating the current vector of the split-vertex along with the vectors of the local partial neighborhood, i.e. each neighboring node on the first partition/device); and
adding the mirror fusion vector to a local aggregation data sequence (e.g. page 5, first column section 5.3(3) and second column, describing use of a delay parameter r to configure the system to perform the delayed partial aggregation algorithm in order to delay communicating partial aggregates among split-vertices such that each split-vertex starts communication in epoch i and asynchronously receives and processes aggregates in epoch (i + r), and further reducing communication by involving only a subset of split-vertices through binning in each epoch; i.e. a delay parameter is utilized to enforce the sending of the local aggregation data in a particular sequence, analogous to adding the mirror fusion vector to a local aggregation data sequence); and
sequentially sending, through a sending thread, determined mirror fusion vectors in the local aggregation data sequence to a device in which a graph node corresponding to a corresponding mirror node is located (e.g. page 3, section 4.1, describing implementation of aggregation; computation is parallelized by distributing destination vertices across OpenMP threads; this way, there are no collisions because only one thread owns the feature vector at each destination vertex; page 3, second column, final paragraph, continuing on page 4, utilizing cache blocking by parallelizing across source vertices leading to race conditions on destination vertices; for each block, going through all destination vertices in parallel ensuring that all threads work on one block B of source vertices at a time; using dynamic thread scheduling with OpenMP, allocating a chunk of contiguous destination vertices at a time to ensure that a thread writes to contiguous feature vectors; page 5, first column section 5.3(3) and second column, as cited above, describing use of a delay parameter and binning to send local aggregation data in a particular sequence; for each original vertex, creating a tree in which one split-vertex is assigned as the root while the rest become leaves; synchronizing aggregates across split-vertices in two phases, including (i) all leaves send their partial aggregates to the root),
so that the device in which the corresponding graph node is located determines, based on the corresponding mirror fusion vector, attribute information fused for the corresponding graph node, to update a current representation vector of the corresponding graph node (e.g. page 5, second column, for each original vertex, creating a tree in which one split-vertex is assigned as the root while the rest become leaves; synchronizing aggregates across split-vertices in two phases, including (ii) the root receives partial aggregates from leaf split-vertices (clone/mirror) and aggregates them and then communicates the final aggregates back to the leaves; i.e. the root split-vertex (analogous to a corresponding graph node which has one or more clones/mirrors) determines fused attribute information by aggregating all received aggregated feature vectors from its clones/mirrors to update the current feature/representation vector for the root split-vertex (graph node)).
With respect to claim 2, Md teaches all of the limitations of claim 1 as previously discussed, and further teaches
wherein the graph learning is performed by processing the graph data by using a graph model with a multi-layer iterative structure (e.g. page 4, first column, final paragraph, using the GraphSAGE GNN model; page 6, first column, fourth paragraph, in the GraphSAGE model, we use two graph convolutional layers for the Reddit dataset with 16 hidden layer neurons; for the remaining datasets, we use three layers with 256 hidden layer neurons; page 9, second column, final paragraph, GraphSAGE model contains three layers),
the fusion operation is correspondingly performed at a single layer of the graph model (e.g. page 5, first column, section 5.3, at each layer, each partition first performs local aggregation; page 9, second column, final paragraph, within each layer, the neighborhood aggregation step is followed by MLP operations; Examiner notes that this claim and paragraph 0077 of the specification of the instant application both indicate that the fusion operation can be performed at both “the single layer” and “a previous layer”, i.e. the fusion operation is performed at the single layer, but if the single layer is not the first layer, the current representation vector includes information fused at the previous layer; therefore the limitation “at a single layer” appears to indicate that the fusion operation is performed at a single layer, but does not appear to exclude the possibility that fusion operations can also be performed at other layers in addition to the fusion operation at the single layer; therefore, Md’s teaching of performing aggregation/fusion operations “at leach layer” appears to be analogous to performing the fusion operation in at least one single layer), and
upon determining that the single layer is the first layer, a current representation vector of the single graph node is a feature vector extracted based on attribute information of an entity corresponding to the single graph node (e.g. page 4, second column, section 5.1, when partitioning is performed, each vertex that splits due to vertex-cut results in clones in various partitions; page 4, second column, section 5.2, indicating that when partitioning is performed, each split-vertex receives its own copy of the feature vector; page 5, section 5.3(2), describing portion of set of algorithms used during aggregation operation, indicating that all split-vertices communicate partial aggregates to their remote clones such that each vertex in each partition receives its complete neighborhood; i.e. when the graph is partitioned, each clone/mirror vertex/node receives a complete copy of its feature vector, analogous to obtaining a current representation vector for the single mirror node from a device where the corresponding graph node is located; when the single layer is the first layer, the corresponding current representation vector would be this initially-received copy of the feature vector, prior to any processing through subsequent neural network layers, which is based on/representative of the corresponding node), or
upon determining that the single layer is not the first layer, a current representation vector of the single graph node is a representation vector corresponding to attribute information that is of the single graph node and that is fused at a previous layer (e.g. page 5, second column, indicating that after all leaves send their partial aggregates to the root split-vertex, the root aggregates these and the communicates final aggregate back to the leaves; i.e. where aggregation is performed at each layer as cited above, aggregation of partial aggregate feature vectors from leaf/mirror/clone nodes at the root vertex/single graph node would occur in a first layer, producing a final aggregate, and then this final aggregate would be passed back to the leave/mirror/clone nodes for use in a next layer of the GNN, as a representation vector corresponding to attribute information of the single graph node (root node) that is fused at a previous layer (the first layer)).
With respect to claim 4, Md teaches all of the limitations of claim 1 as previously discussed, and further teaches wherein the mirror fusion vector of the single mirror node is determined by obtaining one of a sum, an average, a weighted sum, and a median of current representation vectors of neighboring nodes of the graph node in the N graph nodes (e.g. page 6, first column, fourth paragraph, employing GCN aggregation operator which is element-wise sum and as a post-processing step, it adds aggregated and original features of each vertex and normalizes the sum with respect to the in-degree of the vertex).
With respect to claim 5, Md teaches all of the limitations of claim 1 as previously discussed, and further teaches wherein the N graph nodes comprise a first node, the first node corresponds to mirror nodes distributed on S devices and R local neighboring nodes, R is greater than or equal to 0 (e.g. page 4, second column, section 5.2, partition contains split-vertices and non-split vertices; Fig. 1, showing three partitions each including a first node which is a split-vertex which corresponds to clone/mirror nodes in other partitions, as well as a number of neighbor nodes, where at least one of these neighbor nodes may also be a split-vertex which can be designated as either a leaf (clone/mirror) or root, and may therefore correspond to other leaf/clone/mirror split-vertices/nodes on other devices/partitions), and for the first node, the method further comprises:
fusing a current representation vector of the R neighboring nodes and a current representation vector of the first node through a single local fusion thread in a plurality of local fusion threads, to obtain a local fusion vector of the first node (e.g. page 3, second column, first full paragraph, computation is parallelized by distributing destination vertices across OpenMP threads; there are no collisions because only one thread owns the feature vector at each destination vertex and reduces the pulled source feature vectors into the feature vector; page 5, first column, sections 5.3(1) and 5.3(2), for each layer, each partition performs local aggregation; after local aggregation, each split-vertex has aggregated from its local neighborhood; i.e. where a split-vertex (i.e. local clone/mirror node in a given partition, or a local root vertex/node in a given partition) is a destination vertex with respect to a local neighborhood aggregation operation (aggregating feature vectors from neighboring nodes at the split-vertex), Md appears to describe that this destination split-vertex in the partition is associated with a single thread and the split-vertex/single thread own the corresponding feature vector resulting from the local aggregation; Examiner additionally notes that the claim appears to indicate that there may be 0 neighboring nodes, such that this corresponding fusion/aggregation operation may not actually be performed in some instances); and
fusing, through a single aggregation thread in a plurality of aggregation threads, the local fusion vector and S mirror fusion vectors respectively determined by the S devices for the first node, to obtain attribute information fused for the first node, so as to update the current representation vector of the first node (e.g. page 3, second column, first full paragraph, computation is parallelized by distributing destination vertices across OpenMP threads; there are no collisions because only one thread owns the feature vector at each destination vertex and reduces the pulled source feature vectors into the feature vector; page 5, first column, section 5.3(2), all split-vertices communicate partial aggregates to their remote clones; page 5, second column, all leaves send their partial aggregates to the root; the root receives and aggregates them, resulting in final aggregate; i.e. where a split-vertex which is designated as the root (i.e. root/master node corresponding to a plurality of clone/mirror nodes at corresponding partitions) is a destination vertex with respect to an aggregation operation between root and leaf split-vertices (aggregating feature vectors from leaf/clone/mirror split-vertices/nodes to a root/master split-vertex), Md appears to describe that this destination root split-vertex is associated with a single thread and the root split-vertex/single thread own the corresponding feature vector resulting from the aggregation between all corresponding split-vertices, i.e. between all leaf/clone/mirror vertices and the root/master vertex with receives the feature vectors and aggregates to produce a final aggregate).
With respect to claim 6, Md teaches all of the limitations of claim 5 as previously discussed, and further teaches wherein the fusing, through a single aggregation thread in a plurality of aggregation threads, the local fusion vector and S mirror fusion vectors respectively determined by the S devices for the first node comprises: obtaining the S mirror fusion vectors respectively determined by the S devices for the first node; and fusing the S mirror fusion vectors and the local fusion vector of the first node (e.g. page 5, first column, section 5.3(2), all split-vertices communicate partial aggregates to their remote clones; page 5, second column, all leaves send their partial aggregates to the root; the root receives and aggregates them, resulting in final aggregate; i.e. all clone/mirror split-vectors/nodes provide their corresponding feature vectors, including to a root split-vector/node, where they are fused/aggregated along with the feature vector of the receiving split-vector/node).
With respect to claim 8, Md teaches all of the limitations of claim 5 as previously discussed, and further teaches wherein the fusing, through a single aggregation thread in a plurality of aggregation threads, the local fusion vector and S mirror fusion vectors respectively determined by the S devices for the first node comprises: in response to receiving a single mirror fusion vector of the first node from a single device in the S devices, aggregating the single mirror fusion vector to the local fusion vector of the first node, and updating the local fusion vector of the first node by using an aggregation result, until the S mirror fusion vectors sent by the S devices are all aggregated (e.g. page 5, first column, section 5.3(3), continuing on second column, applying communication avoidance mechanism, overlapping remote aggregate communication with local computation; applying inter-epoch compute-communication overlap; delaying communicating partial aggregates among split-vertices; each split-vertex starts communication in epoch i and asynchronously receives and processes aggregates in epoch (i+r); communication further reduced by involving only a subset of split-vertices in each epoch; this operation is described in Algorithm 4; split-vertex assigned as root, and the rest of them become leaves; to synchronize aggregates across split-vertices, communication between leaves and the root occurs in two phases, including all leaves sending their partial aggregates to the root which receives and aggregates them resulting in a final aggregate; setting r greater than zero, performing partial delayed aggregations; i.e. where the system implements delayed partial aggregation, the communication of the partial aggregate feature vector or each leaf split-vertex (clone/mirror) may be delayed, and may be further limited to a particular leaf split-vertex per each subsequent epoch, such that the communication of the corresponding partial aggregate feature vectors occurs asynchronously, and in each epoch a single vector is received and aggregated at the root split-vertex (master node) to update the vector at the root split-vertex, until all partial aggregate feature vectors have been received and aggregated at the root split-vertex after multiple epochs have completed).
With respect to claim 9, Md teaches all of the limitations of claim 5 as previously discussed, and further teaches wherein the first device sets r mirror nodes for r neighboring nodes in the R neighboring nodes, and the fusing a current representation vector of the R neighboring nodes and a current representation vector of the first node comprises: obtaining a current representation vector of r graph nodes corresponding to the r mirror nodes; and fusing a current representation vector of the R neighboring nodes, the current representation vector of the r graph nodes, and the current representation vector of the first node (e.g. page 5, Fig. 1 along with sections 5.3(1) and 5.3(2), at each layer, each partition first performs local aggregation; after local aggregation, each split-vertex has aggregated from its local partial neighborhood; page 5, second column, split-vertices assigned as either root or leaf; all leaves send partial aggregates to root, which then aggregates them to obtain final aggregate; i.e. as shown in Fig. 1 (such as in partition P2), a local graph partition may include a combination of multiple split-vertices (where these may be designated as either a leaf/mirror/clone or a root/master) along with additional local neighbor nodes, analogous to at least a single mirror node which is a mirror of a corresponding graph node on another device/partition (as recited in claim 1) along with neighboring nodes, where one of these neighboring nodes may include a first node which corresponds to mirror nodes (i.e. a root split-vertex) on other devices/partitions, along with at least one additional local neighboring node (as recited in claim 5), where one of these neighboring nodes may further be associated with a mirror/leaf node in another partition/device (as recited in claim 9), such that the local aggregation operation for the partition would include obtaining current vectors of all of the neighboring nodes (including those which have corresponding leaves/mirrors) and fusing/aggregating the vectors for each of the neighboring nodes along with the current vector of other nodes in the partition (such as a first node), to produce the local aggregate feature vector; Examiner additionally notes that claim 5 appears to indicate that there may be 0 of the R neighboring nodes, such that this corresponding fusion/aggregation operation may not actually be performed in some instances).
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Md in view of Yan et al. "Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters," in IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 6, pp. 1647-1659, 1 June 2016, doi: 10.1109/TPDS.2015.2453978. Retrieved from the Internet: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7152922. (hereinafter referred to as “Yan”).
With respect to claim 7, Md teaches all of the limitations of claim 5 as previously discussed, and further teaches wherein the fusing, through a single aggregation thread in a plurality of aggregation threads, the local fusion vector and S mirror fusion vectors respectively determined by the S devices for the first node comprises: obtaining a single mirror fusion vector that is of the first node and that is received from a single device in the S devices; aggregating the single mirror fusion vector to a mirror aggregation vector of the first node until the S mirror fusion vectors sent by the S devices are all aggregated, to obtain a mirror aggregation result; and fusing the mirror aggregation result and the local fusion vector of the first node (e.g. page 5, Fig. 1 and section 5.3, as shown in Fig. 1, a partition may include multiple split-vertices, such that at least one may be a root split-vertex associated with leaf/mirror/clone split-vertices on other partitions; all split-vertices communicate partial aggregates to their remote clones; utilizing delayed communication of partial aggregates among split-vertices, including by involving only a subset of split-vertices in each epoch; to synchronize aggregates across split-vertices, all leaves send their partial aggregates to the root; the root receives and aggregates them; i.e. where a given vertex/node in a given partition is a root split-vertex (master node), it may be synchronized with its clones/mirrors by receiving partial aggregates (of feature vectors) from the leaves/clones/mirrors in a synchronous or asynchronous manner (analogous to obtaining at least a single mirror fusion vector from a single device, aggregating it to a vector until all vectors are received from leave/clone/mirror nodes, and then fusing/aggregating to a local vector of the first node).
Assuming arguendo that Md does not explicitly disclose that the single mirror fusion vector is aggregated to a mirror aggregation vector until the S mirror fusion vectors are all aggregated, to obtain a mirror aggregation result, and fusing the mirror aggregation result and the local fusion vector of the first node, Yan teaches these limitations (e.g. page 1649, Fig. 3, showing different graph parallel frameworks, including frameworks with split-vertices including clone/mirror vertices and corresponding root/master vertices/nodes, such as GraphLab, PowerGraph, and Graphine; page 1650, section 3.1, Equation 2(b) implementing a commutative and associative gather/combine operation in which, once a message arrives, it may be computed immediately, and several partial sums may be computed to a vertex v and them combined into one; page 1651, Fig. 5., showing a combine operation in which vertex data is received and aggregated/fused in a sequential manner, such that, when implemented for a set of split-vertices including a root/master vertex/node and multiple mirror vertices/nodes, first received mirror data (a vector as taught by Md) would be aggregated to a mirror aggregation vector along with other received mirror data/vectors to obtain a mirror aggregation result (such as the result of combining/aggregating data of V1, V2, and V3 in Fig. 5), with these then being combined/fused to local data/vector of the root/master vertex/node (i.e. shown in Fig. 5 where combined/aggregated data is then passed to node V4)).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Md and Yan in front of him to have modified the teachings of Md (directed to scalable distributed training for large-scale graph neural networks), to incorporate the teachings of Yan (directed to programming graph-parallel computation of large natural graphs for multicore clusters) to include the capability to aggregate the single mirror fusion vector to a mirror aggregation vector until the S mirror fusion vectors are all aggregated, obtain a mirror aggregation result, and fuse the mirror aggregation result and the local fusion vector of the first node. One of ordinary skill would have been motivated to perform such a modification in order to improve the vertex-cut method in distributed graph placement as described in Yan (page 1650, second column, paragraph immediately above section 3.2).
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Md in view of McCune et al. "Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing." ACM Comput. Surv. 48, 2, Article 25 (October 2015). DOI: http://dx.doi.org/10.1145/2818185. Retrieved from the Internet: https://dl.acm.org/doi/pdf/10.1145/2818185. (hereinafter referred to as “McCune”).
With respect to claim 3, Md teaches all of the limitations of claim 1 as previously discussed, and further teaches wherein the graph node is recorded in a candidate node queue upon determining that the device in which the graph node corresponding to the single mirror node is located provides the current representation vector of the graph node, and all the fusion threads sequentially obtain a single current representation vector at a single time (e.g. page 3, second column, first full paragraph, computation is parallelized by distributing destination vertices across OpenMP threads; there are no collisions because only one thread owns the feature vector at each destination vertex and reduces the pulled source feature vectors into the feature vector; page 4, second column, section 5.2, split-vertices have their own copy of the feature vector; vertices in each partition have global and local IDs; Global IDs are the vertex IDs from the original input graph; local IDs assigned to vertices according to partition, and a global data structure vertex_map stores the local ID range of each partition; local ID along with vertex_map pinpoints vertex’s partition and location within the partition; for each split-vertex, using an array to store the local IDs lf all its clones; page 5, second column, tree structure facilitating communication among split-vertices; for each original vertex, creating a tree in which one of its split-vertices is assigned as a root while the rest become leaves; to synchronize aggregates across split-vertices communication includes the root communicating a final aggregate back to the leaves; i.e. upon determining which split-vertex is the root (which provides the master/current feature vector for the node in the original graph), a data structure is utilized to record the split-vertices designated as root and leaves, along with IDs of all clones for each vertex, analogous to recording the graph node in a candidate node queue; in addition, during a given time within a given iteration/epoch, the root vertex/node provides the current final aggregate back to all leaves, where the leaves are, for the purposes of this operation, each destination nodes, such that each leaf would receive the updated current final aggregate via its own thread, analogous to all fusion threads sequentially obtaining the single current representation vector at a single time).
Md does not explicitly disclose the candidate node queue is used to store a current representation vector of a local mirror node or a local graph node. However, McCune teaches the candidate node queue is used to store a current representation vector of a local mirror node or a local graph node (e.g. pages 1-13, section 3.2.1, describing message passing communication between vertices, where the message contains local vertex data and is addressed to the ID of the recipient vertex; placing messages between vertices on a message queue and/or outgoing message buffer; page 18, fourth paragraph, storing cached copy of accumulator for each vertex; applying changes to the cached copy; neighboring vertex then using the cached copy during an update; page 13, section 3.2.2, describing a shared memory implementation in which vertex data is exposed as shared variable that can be directly read or modified by other vertex programs; ensuring memory consistency through mutual exclusion by requiring serializable schedules; providing locally cached ghost copies of remote neighbors; maintaining consistency across cached mirrors of cut vertex using parallel Chandy-Misra locking, etc.; i.e. the current data of a given vertex/node (i.e. a current feature vector as taught by Md, whether it is a root/master vertex/node or a leaf/clone/mirror vertex/node) is stored in a corresponding data structure, such as a message queue, message buffer, or a data structure withing a shared memory which may be accessed by other vertices/nodes according to corresponding control mechanisms, analogous to using a candidate node queue to store a current representation vector).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Md and McCune in front of him to have modified the teachings of Md (directed to scalable distributed training for large-scale graph neural networks), to incorporate the teachings of McCune (directed to vertex-centric frameworks for large-scale distributed graph processing) to include using the candidate node queue to store a current representation vector of a local mirror node or a local graph node. One of ordinary skill would have been motivated to perform such a modification in order to address challenges in large-scale graph processing as described in McCune (page 1, first paragraph).
It is noted that any citation to specific pages, columns, lines, or figures in the prior art references and any interpretation of the references should not be considered to be limiting in any way. “The use of patents as references is not limited to what the patentees describe as their own inventions or to the problems with which they are concerned. They are part of the literature of the art, relevant for all they contain,” In re Heck, 699 F.2d 1331, 1332-33, 216 USPQ 1038, 1039 (Fed. Cir. 1983) (quoting in re Lemelson, 397 F.2d 1006, 1009, 158 USPQ 275, 277 (GCPA 1968)). Further, a reference may be relied upon for all that it would have reasonably suggested to one having ordinary skill the art, including nonpreferred embodiments. Merck & Co, v. Biocraft Laboratories, 874 F.2d 804, 10 USPQ2d 1843 (Fed. Cir.), cert, denied, 493 U.S. 975 (1989). See also Upsher-Smith Labs. v. Pamlab, LLC, 412 F,3d 1319, 1323, 75 USPQ2d 1213, 1215 (Fed. Cir, 2005): Celeritas Technologies Ltd. v. Rockwell International Corp., 150 F.3d 1354, 1361, 47 USPQ2d 1516, 1522-23 (Fed. Cir. 1998).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JEREMY L STANLEY whose telephone number is (469)295-9105. The examiner can normally be reached on Monday-Friday from 9:00 AM to 5:00 PM CST.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Abdullah Al Kawsar, can be reached at telephone number (571) 270-3169. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from Patent Center and the Private Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from Patent Center or Private PAIR. Status information for unpublished applications is available through Patent Center and Private PAIR for authorized users only. Should you have questions about access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free).
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) Form at https://www.uspto.gov/patents/uspto-automated- interview-request-air-form.
/JEREMY L STANLEY/
Primary Examiner, Art Unit 2127
