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 .
Status of Claims
Claims 1-20 are pending and examined herein.
Claim 4 is objected to.
Claims 1-20 are rejected under 35 U.S.C. 101.
Claims 1-20 are rejected under 35 U.S.C. 103.
Information Disclosure Statement
The attached information disclosure statement(s) (IDS) filed on 12/27/2026 is/are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement(s) is/are being considered by the examiner.
Claim Objections
Claim 4 is objected to because of the following informalities:
Claim 4 recites the limitation “the set of tensor processing subsystems”. There is insufficient antecedent basis for this limitation. However, the metes and bounds of claim 4 is clear. Therefore, “the set of tensor processing subsystems” will be interpreted as “a set of tensor processing subsystems”.
In claim 4, “include” should be “includes”.
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.
MPEP § 2109(III) sets out steps for evaluating whether a claim is drawn to patent-eligible subject
matter. The analysis of claims 1-20, in accordance with these steps, follows.
Step 1 Analysis:
Step 1 is to determine whether the claim is directed to a statutory category (process, machine,
manufacture, or composition of matter. Claims 1-19 are directed to a process and claim 20 is directed to a machine. All claims are directed to statutory categories and analysis proceeds.
Step 2A Prong One, Step 2A Prong Two, and Step 2B Analysis:
Step 2A Prong One asks if the claim recites a judicial exception (abstract idea, law of nature, or natural phenomenon). If the claim recites a judicial exception, analysis proceeds to Step 2A Prong Two, which asks if the claim recites additional elements that integrate the abstract idea into a practical application. If the claim does not integrate the judicial exception, analysis proceeds to Step 2B, which asks if the claim amounts to significantly more than the judicial exception. If the claim does not amount to significantly more than the judicial exception, the claim is not eligible subject matter under 35 U.S.C. 101.
None of the claims represent an improvement to technology.
Regarding claim 1, the following are abstract ideas:
A method for generating a latent representation of a graph, the graph comprising a set of nodes and a set of edges, each edge in the set of edges connecting a respective pair of nodes in the graph, the method comprising: (Generating a latent representation of a graph can be practically performed in the human mind, i.e. determining values that represent graphs.)
for each of a series of training steps: (See below.)
generating, by a set of worker subsystems, a batch of training data, the batch of training data comprising a portion of the plurality of graph samples selected for use as positive training samples for the batch; (Generating training data can be practically performed in the human mind. This is a mental process.)
determining losses for the graph samples in the batch including, for each graph sample in the batch, determining a respective loss for the graph sample based on (i) a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample; and (Determining losses based on a measure of similarity and a count of co-occurrences can be practically performed in the human mind. This is a mental process.)
The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
obtaining a plurality of graph samples, each graph sample identifying a source node from the set of nodes in the graph, a second node from the set of nodes in the graph, and a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph; (Obtaining data is the insignificant extra-solution activity of ‘mere data gathering’. See MPEP § 2106.05(g), list 1, ex. i-vi.)
initializing values of an embedding table for the graph, the embedding table comprising a plurality of sets of embedding parameters, each set of embedding parameters defining a respective latent representation for a different node of the graph; (Initializing values in an embedding table is an existing process in computing; this amounts to mere instructions to apply an exception.)
using the losses to update the current values of the sets of embedding parameters in the embedding table for the source nodes identified by the graph samples in the batch. (Updating parameters in an embedding table is an existing process in machine learning. This amounts to mere instructions to apply an exception.)
Regarding claim 2, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
performing a respective set of random walks for each source node in the graph, wherein performing each random walk comprises making a defined number of hops to follow a succession of nodes in the graph starting from the source node, wherein the destination for each hop is selected randomly from among the set of nodes directly connected by a respective edge to the node where the walk is currently located. (Performing random walks can be practically performed in the human mind. This is a mental process.)
Claim 2 does not recite any further additional elements.
Regarding claim 3, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
performing a defined number of random walks initiated from each source node in the graph, each random walk limited to a defined number hops from the respective source node for that random walk. (Performing random walks can be practically performed in the human mind. This is a mental process.)
Claim 3 does not recite any further additional elements.
Regarding claim 4, the rejection of claim 1 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein the set of tensor processing subsystems include one or more matrix multiplication units optimized for performing matrix multiplication operations, wherein the set of worker subsystems are without matrix multiplication units. (The components tensor processing subsystems, matrix multiplication units, and worker subsystems are recited at a high-level of generality. The inclusion of these components amounts to mere instructions to apply an exception.)
Regarding claim 5, the rejection of claim 4 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein the set of worker subsystems are implemented on a collection of central processing units (CPUs), a collection of graphics processing units (GPUs), or a collection of CPUs and GPUs. (The components CPUs and GPUs are recited at a high-level of generality. The inclusion of these components amounts to mere instructions to apply an exception.)
Regarding claim 6, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
further comprising de-duplicating training inputs in the batch of training data (De-duplicating training inputs can be practically performed in the human mind. This is a mental process.)
Claim 6 does not recite any further additional elements.
Regarding claim 7, the rejection of claim 1 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein a total number of nodes in the graph is at least a million, at least ten million, at least one hundred million, at least a billion, at least ten billion, or at least one hundred billion. (The number of nodes processed is irrelevant to the mental processes performed on the nodes. Note that MPEP 2106.04(a)(2)(III) states "Nor do the courts distinguish between claims that recite mental processes performed by humans and claims that recite mental processes performed on a computer. As the Federal Circuit has explained, "[c]ourts have examined claims that required the use of a computer and still found that the underlying, patent-ineligible invention could be performed via pen and paper or in a person’s mind." Versata Dev. Group v. SAP Am., Inc., 793 F.3d 1306, 1335, 115 USPQ2d 1681, 1702 (Fed. Cir. 2015). See also Intellectual Ventures I LLC v. Symantec Corp., 838 F.3d 1307, 1318, 120 USPQ2d 1353, 1360 (Fed. Cir. 2016) (‘‘[W]ith the exception of generic computer-implemented steps, there is nothing in the claims themselves that foreclose them from being performed by a human, mentally or with pen and paper.’’); Mortgage Grader, Inc. v. First Choice Loan Servs. Inc., 811 F.3d 1314, 1324, 117 USPQ2d 1693, 1699 (Fed. Cir. 2016) (holding that computer-implemented method for "anonymous loan shopping" was an abstract idea because it could be "performed by humans without a computer"). Mental processes recited in claims that require computers are explained further below with respect to point C." Thus, a generic computer could implement the mental processes to process a large number of nodes in a graph.)
Regarding claim 8, the rejection of claim 7 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein each node in the graph is represented in the embedding table. (This is the insignificant extra-solution activity of selecting a particular data source or type of data to be manipulated. See MPEP § 2106.05(g), ‘Selecting a particular data source or type of data to be manipulated’, ex. i. – iv.)
Regarding claim 9, the rejection of claim 7 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein only a subset of nodes in the graph are represented in the embedding table. (This is the insignificant extra-solution activity of selecting a particular data source or type of data to be manipulated. See MPEP § 2106.05(g), ‘Selecting a particular data source or type of data to be manipulated’, ex. i. – iv.)
Regarding claim 10, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
using trained values for the set of embedding parameters of nodes in the graph to model at least a portion of the graph in a downstream graph analysis process. (Modelling a portion of the graph using the trained values for embedding parameters can be practically performed in the human mind. This is a mental process)
Claim 10 does not recite any further additional elements.
Regarding claim 11, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
for each training step in the series of training steps, generating, by the set of worker subsystems or the set of tensor processing subsystems, a set of negative training samples for the batch of training data, each negative training sample identifying a source node in the graph and a randomly selected second node in the graph. (Generating training data in this manner can be practically performed in the human mind. This is a mental process.)
Claim 11 does not recite any further additional elements.
Regarding claim 12, the rejection of claim 11 is incorporated herein. The following is an abstract idea:
wherein generating the set of negative training samples for the batch of training data comprises, for each positive training sample in the batch, generating n negative training samples that identify the same source node as the positive training sample but that identifies a respective second node that was not identified from the result of a random walk initiated at the source node, wherein n > 1. (Generating training data in this manner can be practically performed in the human mind. This is a mental process.)
Claim 12 does not recite any further additional elements.
Regarding claim 13, the rejection of claim 11 is incorporated herein. The following is an abstract idea:
determining a respective loss for each negative training sample in the batch based on a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the negative training sample and the second node identified by the training sample; and (Determining a loss based on a measure of similarity can be practically performed in the human mind. This is a mental process.)
using the respective losses for the negative training samples in the batch to update the current values of the sets of embedding parameters for the source nodes identified by the negative training samples in the batch. (Updating the embedding parameters using the losses can be practically performed in the human mind. This is a mental process.)
Claim 13 does not recite any further additional elements.
Regarding claim 14, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
for each source node in the graph, accumulating losses generated from positive and negative training samples for the source node; (Accumulating losses is a mathematical calculation, which is a mathematical concept.)
determining a gradient of the accumulated losses; and (Determining a gradient is a mathematical calculation, which is a mathematical concept.)
The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
propagating the gradient of the accumulated losses back through a neural network that includes the embedding table as an embedding layer and an output layer. (Propagating the gradient of the losses through a neural network with an embedding layer and output layer is a existing and generic process in machine learning. This amounts to mere instructions to apply an exception.)
Regarding claim 15, the rejection of claim 1 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein the measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample is a cosine distance or a Euclidean distance. (This is the insignificant extra-solution activity of selecting a particular data source or type of data to be manipulated. See MPEP § 2106.05(g), ‘Selecting a particular data source or type of data to be manipulated’, ex. i. – iv.)
Regarding claim 16, the rejection of claim 1 is incorporated herein. The following is an abstract idea:
wherein determining the respective loss for the graph sample comprises weighting the measure of similarity by the count of co-occurrences. (Weighting the measure of similarity by the count of co-occurrences can be practically performed in the human mind. This is a mental process.)
Claim 16 does not recite any further additional elements.
Regarding claim 17, the following are mental processes:
A method for generating a latent representation of a graph, the graph comprising a set of nodes and a set of edges, each edge in the set of edges connecting a respective pair of nodes in the graph, the method comprising:
determining, by the worker subsystem, a loss for the graph sample based on (i) a measure of similarity between the obtained master values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample;
generating, by the worker subsystem, updated values for the set of embedding parameters of the source node based on the loss; and
The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
obtaining a plurality of graph samples, each graph sample identifying a source node from the set of nodes in the graph, a second node from the set of nodes in the graph, and a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph; (Obtaining data is the insignificant extra-solution activity of ‘mere data gathering’. See MPEP § 2106.05(g), list 1, ex. i-vi.)
initializing master values of an embedding table for the graph, the embedding table comprising a plurality of sets of embedding parameters, each set of embedding parameters defining a respective latent representation for a different node of the graph; (Initializing values in an embedding table is an existing process in computing; this amounts to mere instructions to apply an exception.)
maintaining, by a server system, the master values of the embedding table for the graph, including maintaining master values for the plurality of sets of embedding parameters; (Maintaining embedding/parameter values is an existing process in machine learning. This amounts to mere instructions to apply an exception.)
for each worker subsystem in a set of worker subsystems, and for each of a subset of the plurality of graph samples from the plurality of graph samples assigned to the worker subsystem: (This recites generic worker subsystems, which amounts to mere instructions to apply an exception.)
obtaining, by the worker subsystem and from the server system, the master values of the set of embedding parameters for the source node identified in the graph sample; (Obtaining data is the insignificant extra-solution activity of ‘mere data gathering’. See MPEP § 2106.05(g), list 1, ex. i-vi.)
updating the master values for the set of embedding parameters for the source node at the server system with the updated values generated by the worker subsystem. (Updating master values is a existing and generic process in machine learning. This amounts to mere instructions to apply an exception.)
Regarding claim 18, the rejection of claim 17 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein the server system is configured to leave the master values for the set of embedding parameters for each node unlocked while a given worker subsystem works on updating the master values for the node. (This does not meaningfully limit the claims, as the master values must be unlocked for the worker subsystem to update the master values.)
Regarding claim 19, the rejection of claim 17 is incorporated herein. The following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
wherein the plurality of graph samples are sharded across the set of worker subsystems. (Sharding data amongst worker subsystems is an existing/generic process in machine learning. This amounts to mere instructions to apply an exception.)
Regarding claim 20, the following claim elements are additional elements which, taken alone or in combination with the other additional elements, do not integrate the judicial exception into a practical application nor amount to significantly more than the judicial exception:
A system, comprising: one or more processors; and one or more non-transitory computer-readable media having instructions stored thereon that, when executed by the one or more processors, cause performance of operations comprising: (This recites generic computer components and processes, which amount to mere instructions to apply an exception.)
The remainder of claim 20 recites substantially similar subject matter to claim 1 and is rejected with the same rationale, mutatis mutandis.
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.
The factual inquiries 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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 1-3, 7-10, and 16-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wanjing Wei et al., “A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent”, August 18, 2021, arXiv, hereinafter “Wei” and Sepideh Nahali et al., “IsoGloVe: A New Count-based Graph Embedding Method based on Geodesic Distance”, 2022, The 36th Canadian Conference on Artificial Intelligence, hereinafter “Nahali.”
Wei was provided via IDS by Applicant.
Regarding claim 1, Wei teaches
A method for generating a latent representation of a graph, the graph comprising a set of nodes and a set of edges, each edge in the set of edges connecting a respective pair of nodes in the graph, the method comprising: (Page 1 states "We design and implement a high-performance large-scale node embedding system that uses hybrid model data parallel training and can run on any commodity GPU clusters.” Page 1 further states "Given a network G = (V; E), where V is the set of vertices and E is the set of edges." The set of vertices is interpreted as the set of nodes. Edges in a graph network, by definition, connect a respective pair of nodes in the graph.)
obtaining a plurality of graph samples, each graph sample identifying a source node from the set of nodes in the graph, a second node from the set of nodes in the graph, and (Page 3 states "Random walk engine writes walks to sample pool, embedding training engine sends samples and embeddings to GPU and performs training." Page 2 states that the GPU requires a "sample pool that contains edges in the form of source node ID and destination node ID pairs.")
initializing values of an embedding table for the graph, the embedding table comprising a plurality of sets of embedding parameters, each set of embedding parameters defining a respective latent representation for a different node of the graph; (Page 3 states "We use data parallelism to send batches of edge samples to all N * M GPUs on the cluster from sample pool, and we use model parallelism to partition the node embeddings and send each partition to the embedding PS which is distributed on GPUs." The embedding parameter server is interpreted as the embedding table for the graph. Node embeddings by definition are latent representations of the nodes in the graph.)
for each of a series of training steps: (Page 3 states "During the training of one epoch, we locally train model with different embeddings in parallel for N * M episodes, where after each episode we transfer each partition of the embeddings to a new GPU with a different edge sample block using multi-level ring-based communication.")
generating, by a set of worker subsystems, a batch of training data, the batch of training data comprising a portion of the plurality of graph samples selected for use as positive training samples for the batch; (Page 2 states "On a cluster with N nodes and M GPUs on each node, we first use 2-D partition strategy to partition edge samples (augmented and with negative sampling) into
N
*
M
2
sample blocks. We use data parallelism to send batches of edge samples to all N * M GPUs on the cluster from sample pool, and we use model parallelism to partition the node embeddings and send each partition to the embedding PS which is distributed on GPUs." Page 2 states "Training Process: embedding training on the augmented network involves picking a batch of samples with both positive samples and negative samples, computing the similarity score of vertex[u] and context[v] for an edge sample (u, v), and optimizing (e.g. via standard SGD) to encourage neighbor nodes to have close embeddings, whereas distant nodes to have very different embeddings." Therefore, the worker subsystems generate a batch of training data from the positive graph samples.)
using the losses to update the current values of the sets of embedding parameters in the embedding table for the source nodes identified by the graph samples in the batch. (Page 2, Algorithm 1 shows that the training, which one of ordinary skill in the art would realize includes losses, updates the embedding for vertex v, which is the source node in the edge sample in line 8.) Wei does not appear to explicitly teach
a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph;
determining losses for the graph samples in the batch including, for each graph sample in the batch, determining a respective loss for the graph sample based on (i) a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample; and
However, Nahali—directed to analogous art—teaches
a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph; (Page 2 states "Step 2: IsoGloVe constructs a large matrix of the co-occurrence of nodes from the random walks. In this matrix, the ith row and the jth column represent the value of the co-occurrence of node i and j in random walks. The co-occurrence count matrix needs to be factorised to yield a low-dimensional (D) matrix, where each row represents a node vector.")
determining losses for the graph samples in the batch including, for each graph sample in the batch, determining a respective loss for the graph sample based on (i) a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample; and (Page 2 states "The vector representation of each node is trained by minimizing the difference between the geodesic distance among the embeddings and the logarithm of their co-occurrence count. To accomplish this, the counts in the matrix are first normalized and smoothed using logarithms. Next, the geodesic distance between every pair of nodes is calculated." The geodesic distance is interpreted as the measure of similarity. The loss function is presented in Eq. 2.1, wherein the geodesic distance is measured between the vector representations (embedding parameters) of the source (node
i
) and second node (node
j
).)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali because, as stated by Nahali on page 2, "This paper proposes IsoGloVe, a graph representation that addresses challenges in node representation learning. IsoGloVe generates embeddings by normalizing and log-smoothing co-occurrence matrices of random walks, using geodesic distances between nodes to capture the intrinsic geometry of the network. This approach has several advantages: it considers the graph structure, preserves relationships between nodes, captures nuanced similarities, and is robust to noisy or missing nodes. The main contribution of the work is mapping complex networks to a vector space that preserves community structure and structural equivalence, using geodesic distances to calculate the similarity between vectors."
Regarding claim 2, the rejection of claim 1 is incorporated herein. Wei does not appear to explicitly teach
performing a respective set of random walks for each source node in the graph, wherein performing each random walk comprises making a defined number of hops to follow a succession of nodes in the graph starting from the source node, wherein the destination for each hop is selected randomly from among the set of nodes directly connected by a respective edge to the node where the walk is currently located.
However, Nahali—directed to analogous art—teaches
performing a respective set of random walks for each source node in the graph, wherein performing each random walk comprises making a defined number of hops to follow a succession of nodes in the graph starting from the source node, wherein the destination for each hop is selected randomly from among the set of nodes directly connected by a respective edge to the node where the walk is currently located. (Page 2 states "IsoGloVe randomly generates a truncated random walk for each node using the edge list. The random walk algorithm preserves the local neighborhood of nodes by randomly choosing a node and performing a random walk of length L." As the random walk generation uses the edge list, one of ordinary skill in the art would understand that the destination for the hops are chosen from the directly connected edges from the edge list.) It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali for the reasons given above in regards to claim 1.
Regarding claim 3, the rejection of claim 1 is incorporated herein. Wei does not appear to explicitly teach
performing a defined number of random walks initiated from each source node in the graph, each random walk limited to a defined number hops from the respective source node for that random walk.
However, Nahali—directed to analogous art—teaches
performing a defined number of random walks initiated from each source node in the graph, each random walk limited to a defined number hops from the respective source node for that random walk. (Page 2 states "IsoGloVe randomly generates a truncated random walk for each node using the edge list. The random walk algorithm preserves the local neighborhood of nodes by randomly choosing a node and performing a random walk of length L." The defined number of random walks is 1 and the defined number of hops is length L.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali for the reasons given above in regards to claim 1.
Regarding claim 7, the rejection of claim 1 is incorporated herein. Wei teaches
wherein a total number of nodes in the graph is at least a million, at least ten million, at least one hundred million, at least a billion, at least ten billion, or at least one hundred billion. (Page 6 states "We use the following datasets for our experiments (details in Table II). YOUTUBE [8] is a social network dataset crawled from YouTube (www.youtube.com) that consists of over 1.1 million nodes (users) and 4.9 million edges (links); HYPERLINK-PLD [9] is a label-free hyperlink network with 43 million nodes and 623 million edges; FRIENDSTER [10] is a very large social network on a social gaming site with 65 million nodes and 1.8 billion edges. Part of the nodes have labels that represent social groups formed by users; KRON & DELAUNAY are two networks widely used for benchmarking graph processing systems. Kron is a scale-free network where degree distribution is skew and Delaunay is a mesh network where degree distribution is uniform. ANONYMOUS is a set of networks sampled from multiple internal networks with billion level nodes and hundred-billion level edges. We have anonymized the node and edge information but only preserve the network topology information for the purpose of running the experiments. GENERATED is a set of generated networks with hundred-million level nodes and ten-billion level edges that resemble the topology of real-world social networks. We use this set of networks to test the scalability and performance of our system."
Regarding claim 8, the rejection of claim 7 is incorporated herein. Wei teaches
wherein each node in the graph is represented in the embedding table. (Page 1 states "Each node in the original network generates random walk paths and uses nodes on the paths to form additional positive samples." Therefore, each node is represented as a source node in the positive samples. Page 1 states "Algorithm 1 shows the pseudo code. The training process takes several epochs, where one epoch goes over all the sample edges in the augmented network, and can be broken up into several episodes where each episode train embeddings on one part of sample edges." Algorithm 1, line 7-13 show that the embeddings are trained for each sample, meaning that each vertex (node) is represented by an embedding, stored in the embedding table.)
Regarding claim 9, the rejection of claim 7 is incorporated herein. Wei teaches
wherein only a subset of nodes in the graph are represented in the embedding table. (Page 1 states "Each node in the original network generates random walk paths and uses nodes on the paths to form additional positive samples." Therefore, each node is represented as a source node in the positive samples. Page 1 states "Algorithm 1 shows the pseudo code. The training process takes several epochs, where one epoch goes over all the sample edges in the augmented network, and can be broken up into several episodes where each episode train embeddings on one part of sample edges." Algorithm 1, line 7-13 show that the embeddings are trained for each sample, meaning that each vertex (node) is represented by an embedding, stored in the embedding table. A subset, by definition, includes the set.)
Regarding claim 10, the rejection of claim 1 is incorporated herein. Wei teaches
using trained values for the set of embedding parameters of nodes in the graph to model at least a portion of the graph in a downstream graph analysis process. (Page 7 states "2) Evaluation on Node Embedding Tasks: Link Prediction: We evaluate link prediction task on two open datasets: YouTube dataset and Hyperlink-PLD dataset. To compare with GraphVite, we adopt its method for link prediction evaluation: We split the edges into three sets: training set, test set and validation set. For training set, the negative samples are generated during the training, for test and validation set, we generate negative samples by randomly picking up node pairs that are not real edges in the network. We use 1% and 0.01% edges for test and validation on YouTube and HyperlinkPLD dataset respectively. We also keep the same training settings as GraphVite, such as the learning rate, the number of negative samples, and embedding initialization method." Link prediction is interpreted as the downstream graph analysis process, which requires the trained embeddings to perform the link prediction.)
Regarding claim 16, the rejection of claim 1 is incorporated herein. Wei does not appear to explicitly teach
wherein determining the respective loss for the graph sample comprises weighting the measure of similarity by the count of co-occurrences.
However, Nahali—directed to analogous art—teaches
wherein determining the respective loss for the graph sample comprises weighting the measure of similarity by the count of co-occurrences. (Page 2, Eq. 2.1 shows that the function
f
(
X
i
j
)
, which includes the co-occurrence matrix and is multiplied by the distance metric d, meaning that the measure of similarity is weighted by the co-occurrence count.)\
Regarding claim 17, Wei teaches
A method for generating a latent representation of a graph, the graph comprising a set of nodes and a set of edges, each edge in the set of edges connecting a respective pair of nodes in the graph, the method comprising: (Page 1 states "We design and implement a high-performance large-scale node embedding system that uses hybrid model data parallel training and can run on any commodity GPU clusters.” Page 1 further states "Given a network G = (V; E), where V is the set of vertices and E is the set of edges." The set of vertices is interpreted as the set of nodes. Edges in a graph network, by definition, connect a respective pair of nodes in the graph.)
obtaining a plurality of graph samples, each graph sample identifying a source node from the set of nodes in the graph, a second node from the set of nodes in the graph, and (Page 3 states "Random walk engine writes walks to sample pool, embedding training engine sends samples and embeddings to GPU and performs training." Page 2 states that the GPU requires a "sample pool that contains edges in the form of source node ID and destination node ID pairs.")
initializing master values of an embedding table for the graph, the embedding table comprising a plurality of sets of embedding parameters, each set of embedding parameters defining a respective latent representation for a different node of the graph; (Page 3 states "We use data parallelism to send batches of edge samples to all N * M GPUs on the cluster from sample pool, and we use model parallelism to partition the node embeddings and send each partition to the embedding PS which is distributed on GPUs." The embedding parameter server is interpreted as the embedding table for the graph. Node embeddings by definition are latent representations of the nodes in the graph.)
maintaining, by a server system, the master values of the embedding table for the graph, including maintaining master values for the plurality of sets of embedding parameters; ("Batched with samples generated by negative sampling, these training samples are sent to a task dispatcher, which loads orthogonal samples to GPU trainers for training the embeddings. The system also contains an ondevice embedding parameter server (PS) that manages node embeddings on each GPU." The parameter server is interpreted as the server system.)
for each worker subsystem in a set of worker subsystems, and for each of a subset of the plurality of graph samples from the plurality of graph samples assigned to the worker subsystem: (Fig. 2 shows the worker subsystems (GPUs).)
obtaining, by the worker subsystem and from the server system, the master values of the set of embedding parameters for the source node identified in the graph sample; ("As shown in Figure 2, in one round of training using a GPU cluster with two 8GPU computing nodes, edge samples with different source node ID range and destination node ID range are loaded from sample pool. Vertex embeddings and context embeddings are transferred among GPUs and nodes, so that one part of embeddings get trained on all samples that share source node IDs with it.")
generating, by the worker subsystem, updated values for the set of embedding parameters of the source node based on the loss; and (Fig. 1 shows that data is transferred back and forth from the parameter server. As one of ordinary skill in the art would understand, the trained values will be updated in the parameter server.)
updating the master values for the set of embedding parameters for the source node at the server system with the updated values generated by the worker subsystem. (Page 5 states "When one sub-part finishes its training on the GPU, we use peer-to-peer communication between GPUs to send this sub-part of vertex embeddings to a new GPU with a different sample block;-While a new round of training is going on, the embedding PS on each GPU will load a new sub-part of vertex embeddings. The vertex embeddings that have been trained on all sample blocks within this computing node can also be sent to a new node for training on a new set of sample blocks.")
Wei does not appear to explicitly teach
a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph;
determining losses for the graph samples in the batch including, for each graph sample in the batch, determining a respective loss for the graph sample based on (i) a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample; and
However, Nahali—directed to analogous art—teaches
a count of co-occurrences between the source node and the second node in a set of random walks initiated from the source node in the graph; (Page 2 states "Step 2: IsoGloVe constructs a large matrix of the co-occurrence of nodes from the random walks. In this matrix, the ith row and the jth column represent the value of the co-occurrence of node i and j in random walks. The co-occurrence count matrix needs to be factorised to yield a low-dimensional (D) matrix, where each row represents a node vector.")
determining losses for the graph samples in the batch including, for each graph sample in the batch, determining a respective loss for the graph sample based on (i) a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample and (ii) the count of co-occurrences between the source node and the second node in the set of random walks initiated from the source node in the graph as identified by the graph sample; and (Page 2 states "The vector representation of each node is trained by minimizing the difference between the geodesic distance among the embeddings and the logarithm of their co-occurrence count. To accomplish this, the counts in the matrix are first normalized and smoothed using logarithms. Next, the geodesic distance between every pair of nodes is calculated." The geodesic distance is interpreted as the measure of similarity. The loss function is presented in Eq. 2.1, wherein the geodesic distance is measured between the vector representations (embedding parameters) of the source (node
i
) and second node (node
j
).)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali because, as stated by Nahali on page 2, "This paper proposes IsoGloVe, a graph representation that addresses challenges in node representation learning. IsoGloVe generates embeddings by normalizing and log-smoothing co-occurrence matrices of random walks, using geodesic distances between nodes to capture the intrinsic geometry of the network. This approach has several advantages: it considers the graph structure, preserves relationships between nodes, captures nuanced similarities, and is robust to noisy or missing nodes. The main contribution of the work is mapping complex networks to a vector space that preserves community structure and structural equivalence, using geodesic distances to calculate the similarity between vectors."
Regarding claim 18, the rejection of claim 17 is incorporated herein. Wei teaches
wherein the server system is configured to leave the master values for the set of embedding parameters for each node unlocked while a given worker subsystem works on updating the master values for the node. (One of ordinary skill in the art would understand that for the master values to be updated, it would have to be unlocked for a worker subsystem to write into it.)
Regarding claim 19, the rejection of claim 17 is incorporated herein. Wei teaches
wherein the plurality of graph samples are sharded across the set of worker subsystems. (Page 3 states "On a cluster with N nodes and M GPUs on each node, we first use 2-D partition strategy to partition edge samples (augmented and with negative sampling) into
N
*
M
2
sample blocks")
Regarding claim 20, Wei teaches
A system, comprising: one or more processors; and one or more non-transitory computer-readable media having instructions stored thereon that, when executed by the one or more processors, cause performance of operations comprising: (Page 6 states "A. System and Hardware Information We have two sets of hardware settings run on CentOS 7.2: Set A: runs on a GPU cluster where each node has two 2.50GHz Intel 24-core Xeon Platinum 8255C processors (with hyper-threading), 364GB of main memory, eight 32GB memory NVIDIA V100 GPUs with NVLink 2.0, and one NVMe SSD storage. All nodes in cluster are connected with 100Gb/s InfiniBand switch." The method taught by the paper must be stored on the computer-readable media and be executed by the processor to perform the method.)
The remainder of claim 20 recites substantially similar subject matter to claim 1 and is rejected with the same rationale, mutatis mutandis.
Claim(s) 4-5 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wanjing Wei et al., “A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent”, August 18, 2021, arXiv, hereinafter “Wei” and Sepideh Nahali et al., “IsoGloVe: A New Count-based Graph Embedding Method based on Geodesic Distance”, 2022, The 36th Canadian Conference on Artificial Intelligence, hereinafter “Nahali”, and further in view of Martin Abadi et al., “TensorFlow: A System for Large-Scale Machine Learning”, November 2, 2016, Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’16), hereinafter “Abadi”.
Regarding claim 4, the rejection of claim 1 is incorporated herein. Wei does not appear to explicitly teach
wherein the set of tensor processing subsystems include one or more matrix multiplication units optimized for performing matrix multiplication operations, wherein the set of worker subsystems are without matrix multiplication units.
However, Abadi—directed to analogous art—teaches
wherein the set of tensor processing subsystems include one or more matrix multiplication units optimized for performing matrix multiplication operations, wherein the set of worker subsystems are without matrix multiplication units. (Page 271 states "Dataflow simplifies distributed execution, because it makes communication between subcomputations explicit. It enables the same TensorFlow program to be deployed to a cluster of GPUs for training, a cluster of TPUs for serving, and a cellphone for mobile inference." Therefore, the GPUs are the workers (perform the training), and the TPU is the tensor processing subsystem. One of ordinary skill in the art would understand that a GPU does not include matrix multiplication units, while a TPU includes matrix multiplication units optimized for performing matrix multiplication operation.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali with the teachings of Abadi because, as stated by Abadi on page 271, "TensorFlow thus permits great flexibility in how operations in the dataflow graph are mapped to devices. While simple heuristics yield adequate performance for novice users, expert users can optimize performance by manually placing operations to balance the computation, memory, and network requirements across multiple tasks and multiple devices within those tasks."
Regarding claim 5, the rejection of claim 4 is incorporated herein. Wei does not appear to explicitly teach
wherein the set of worker subsystems are implemented on a collection of central processing units (CPUs), a collection of graphics processing units (GPUs), or a collection of CPUs and GPUs.
However, Abadi—directed to analogous art—teaches
wherein the set of worker subsystems are implemented on a collection of central processing units (CPUs), a collection of graphics processing units (GPUs), or a collection of CPUs and GPUs. (Page 271 states "Dataflow simplifies distributed execution, because it makes communication between subcomputations explicit. It enables the same TensorFlow program to be deployed to a cluster of GPUs for training, a cluster of TPUs for serving, and a cellphone for mobile inference." Therefore, the GPUs are the worker subsystem (perform the training).)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Nahali with the teachings of Abadi for the reasons given above in regards to claim 4.
Claim(s) 6 and 11-14 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wanjing Wei et al., “A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent”, August 18, 2021, arXiv, hereinafter “Wei” and Sepideh Nahali et al., “IsoGloVe: A New Count-based Graph Embedding Method based on Geodesic Distance”, 2022, The 36th Canadian Conference on Artificial Intelligence, hereinafter “Nahali”, and further in view of Tao-yang Fu et al., “HIN2Vec: Explore Meta-paths in Heterogeneous Information Networks for Representation Learning”, November 6, 2017, CIKM’17, hereinafter “Fu”.
Regarding claim 6, the rejection of claim 1 is incorporated herein. The combination of Wei and Nahali does not appear to explicitly teach
further comprising de-duplicating training inputs in the batch of training data
However, Fu—directed to analogous art—teaches
further comprising de-duplicating training inputs in the batch of training data (Page 1801 states "Thus, we eliminate data entries with any cycle by checking duplicate nodes.")
Regarding claim 11, the rejection of claim 1 is incorporated herein. Wei teaches
for each training step in the series of training steps, generating, by the set of worker subsystems or the set of tensor processing subsystems, a set of negative training samples for the batch of training data, each negative training sample identifying a source node in the graph and a randomly selected second node in the graph. (Page 2 states "Training Process: embedding training on the augmented network involves picking a batch of samples with both positive samples and negative samples, computing the similarity score of vertex[u] and context[v] for an edge sample (u, v)." As shown in Algorithm 1, lines 10-11, the negative sample contains a second node
u
'
.)
The combination of Wei and Nahali does not appear to explicitly teach
a randomly selected second node in the graph
However, Fu—directed to analogous art—teaches
a randomly selected second node in the graph ("Thus, while generating positive samples via random walks, we also generate negative data entries following the ideas of negative sampling in Word2Vec [21]. For each sampled positive entry, ⟨x;y;r⟩, we generate negative data entries by randomly replacing one of the three values with other x′, y′, or r′, where x′ and y′ are randomly selected nodes, and r′ is a randomly selected relationship from R.")
Regarding claim 12, the rejection of claim 11 is incorporated herein. The combination of Wei and Nahali does not appear to explicitly teach
wherein generating the set of negative training samples for the batch of training data comprises, for each positive training sample in the batch, generating n negative training samples that identify the same source node as the positive training sample but that identifies a respective second node that was not identified from the result of a random walk initiated at the source node, wherein n > 1.
However, Fu—directed to analogous art—teaches
wherein generating the set of negative training samples for the batch of training data comprises, for each positive training sample in the batch, generating n negative training samples that identify the same source node as the positive training sample but that identifies a respective second node that was not identified from the result of a random walk initiated at the source node, wherein n > 1. (Page 1801 states "Thus, while generating positive samples via random walks, we also generate negative data entries following the ideas of negative sampling in Word2Vec [21]. For each sampled positive entry, ⟨x;y;r⟩, we generate negative data entries by randomly replacing one of the three values with other x′, y′, or r′, where x′ and y′ are randomly selected nodes, and r′ is a randomly selected relationship from R." Page 1801 further states "To maintain efficiency and the cleanness of the negative samples, we only sample negative data by randomly replacing x or y, and filter out erroneously generated positive samples." As the positive samples are filtered, only negative samples that identify a respective second node that was not identified from the result of a random walk initiated at the source node remain.)
Regarding claim 13, the rejection of claim 11 is incorporated herein. Wei teaches
determining a respective loss for each negative training sample in the batch based on a measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the negative training sample and the second node identified by the training sample; and (Page 2 states "Embedding training on the augmented network involves picking a batch of samples with both positive samples and negative samples, computing the similarity score of vertex[u] and context[v] for an edge sample (u, v), and optimizing (e.g. via standard SGD) to encourage neighbor nodes to have close embeddings, whereas distant nodes to have very different embeddings.")
using the respective losses for the negative training samples in the batch to update the current values of the sets of embedding parameters for the source nodes identified by the negative training samples in the batch. (Algorithm 1, Line 11, states that the embedding for the vertex v is trained, and therefore updated. One of ordinary skill in the art would understand that losses are calculated to update the embedding parameters.)
Regarding claim 14, the rejection of claim 1 is incorporated herein. The combination of Wei and Nahali does not appear to explicitly teach
for each source node in the graph, accumulating losses generated from positive and negative training samples for the source node;
determining a gradient of the accumulated losses; and
propagating the gradient of the accumulated losses back through a neural network that includes the embedding table as an embedding layer and an output layer.
However, Fu—directed to analogous art—teaches
for each source node in the graph, accumulating losses generated from positive and negative training samples for the source node; (Page 1801 shows the equation for the log of the objective function O, which adds the losses from the positive and negative training samples.)
determining a gradient of the accumulated losses; and (Page 1801 states "Specifically, for each training data entry, ⟨x, y, r, L(x, y, r)⟩, it goes backwards to adjust the weights in [weights] based on the gradients of [log of the objective function].")
propagating the gradient of the accumulated losses back through a neural network that includes the embedding table as an embedding layer and an output layer. (As the stochastic gradient descent algorithm goes backwards to adjust the weights, it propagates the gradient of the accumulated losses back through the neural network. Fig. 4 on page 1800 shows the neural network. Page 1799 states "In the latent layer, ⃗x and ⃗y are transformed into latent vectors." Therefore, this layer includes the embedding table. Pages 1799-1800 state “Finally, in the output layer, the model outputs a vector.”)
Claim(s) 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wanjing Wei et al., “A Distributed Multi-GPU System for Large-Scale Node Embedding at Tencent”, August 18, 2021, arXiv, hereinafter “Wei” and Sepideh Nahali et al., “IsoGloVe: A New Count-based Graph Embedding Method based on Geodesic Distance”, 2022, The 36th Canadian Conference on Artificial Intelligence, hereinafter “Nahali”, and further in view of Mengjia Xu, “Understanding Graph Embedding Methods and Their Applications”, 2021, SIAM Review, Vol. 63, no. 4, pp. 825-853, hereinafter “Xu”.
Regarding claim 15, the rejection of claim 1 is incorporated herein. The combination of Wei and Fu does not appear to explicitly teach
wherein the measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample is a cosine distance or a Euclidean distance.
However, Xu—directed to analogous art—teaches
wherein the measure of similarity between current values of the respective sets of embedding parameters for the source node identified by the graph sample and the second node identified by the graph sample is a cosine distance or a Euclidean distance. (Page 834 states "The distance (e.g., dot product, cosine similarity, or Euclidean distance) between vectors (or “node embeddings") in the latent vector space approximates the similarity in the original graph.")
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine the teachings of Wei and Fu with the teachings of Xu because, as stated by Xu on page 834, "The learned node embedding features for all nodes can be readily and efficiently used for different downstream tasks, such as link prediction, node classification, and community detection.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JESSICA THUY PHAM whose telephone number is (571)272-2605. The examiner can normally be reached Monday - Friday, 9 A.M. - 5:00 P.M..
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, Li Zhen can be reached at (571) 272-3768. 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.
/J.T.P./Examiner, Art Unit 2121
/Li B. Zhen/Supervisory Patent Examiner, Art Unit 2121
Prosecution Insights