# US 12,602,735 B2 · Graph data calculation method and apparatus > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,735 B2 - Document ID: US12602735B2 - Status: Granted - Kind: B2 - Application number: 18/463,386 - Filed: 2023-09-08 - Published: 2024-03-14 - Granted: 2026-04-14 - Earliest claimed: 2022-09-08 - Assignees: Korea Advanced Institute of Science and Technology - Applicants: Korea Advanced Institute of Science and Technology - Inventors: Min-Soo Kim; Seyeon Oh; Donghyoung Han; Inju Na - Web page: https://patentgrep.com/patent/US12602735B2 ## CPC - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06T 1/60: Memory management - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Provided are a graph data calculation method and apparatus. A computing device divides graph data including a source vertex and a destination vertex of an edge into a plurality of blocks, and identifies an out-degree of each vertex. Next, the computing device repeatedly performs a process of calculating, in units of blocks, a weight of a destination vertex of each edge by using a pagerank and an out-degree of a source vertex of each edge existing in a block, and updating a pagerank of each vertex of the graph data by accumulating a weight of a destination vertex of each block. ## Claims ### Claim 1 A graph data calculation method used by computing device comprising one or more memories, one or more processors, and one or more input/output devices to calculate a graph comprising edges each having a source vertex and a destination vertex, the graph data calculation method comprising: dividing graph data comprising a source vertex and a destination vertex of each edge into a plurality of blocks; identifying an out-degree of each source vertex in the graph; calculating, in units of blocks, a weight of a destination vertex of each edge by using a pagerank and an out-degree of a source vertex in the graph of each edge existing in a block; and updating the pagerank of each destination vertex of the graph data by accumulating weights of destination vertices of each block. ### Claim 2 (depends on 1) The graph data calculation method of claim 1, wherein the calculating is performed in units of blocks by one or more graphics processing units (GPUs). ### Claim 3 (depends on 1) The graph data calculation method of claim 1, wherein the dividing comprises recursively dividing the graph data so that a size of a block is equal to or less than a size of a GPU memory. ### Claim 4 (depends on 1) The graph data calculation method of claim 1, wherein the dividing comprises dividing an adjacency matrix in which source vertices and destination vertices of edges are expressed in rows and columns into a plurality of blocks. ### Claim 5 (depends on 4) The graph data calculation method of claim 4, wherein the calculating comprises performing, in units of blocks, a process of calculating weights of edges of each row existing in a block of the adjacency matrix by using pageranks and out-degrees of source vertex of each row and calculating a weight of a destination vertex of each edge for each block by accumulating the weights of the edge of each row in a column direction. ### Claim 6 (depends on 4) The graph data calculation method of claim 4, wherein the calculating is performed in units of blocks and in an order of a column direction. ### Claim 7 (depends on 1) The graph data calculation method of claim 1, wherein out-degree information for each block comprising out-degrees of source vertices of edges included in each block and pagerank information for each block comprising pageranks of the source vertices of the edges included in each block are included, wherein the calculating comprises calculating a weight based on block unit data comprising the out-degree information for each block, the pagerank information for each block, and graph data for each block. ### Claim 8 (depends on 7) The graph data calculation method of claim 7, wherein the calculating comprises: loading the block unit data into one or more GPU memories; and calculating, by one or more GPU, weights in units of blocks by using the block unit data loaded into the GPU memories. ### Claim 9 (depends on 7) The graph data calculation method of claim 7, wherein the dividing comprises dividing the graph data into a plurality of blocks based on a source vertex and a destination vertex, and the loading comprises loading the plurality of blocks into a plurality of GPU memories through a plurality of streams. ### Claim 10 (depends on 1) The graph data calculation method of claim 1, wherein the calculating and the updating are repeatedly performed a predefined number of times or until a predefined condition is satisfied. ### Claim 11 A computing device comprising: a main memory storing a plurality of blocks into which graph data comprising edges each having a source vertex and a destination vertex are divided, an out-degree of each source vertex, and a pagerank of each source vertex; one or more graphics processing units (GPUs) configured to calculate, in units of blocks, a weight of a destination vertex of each edge by using a pagerank and an out-degree of a source vertex of each edge existing in a block; and a processor configured to update a pagerank of each source vertex of the graph data by accumulating weights of destination vertices of each block. ### Claim 12 (depends on 11) The computing device of claim 11, wherein the processor is further configured to recursively divide the graph data so that a size of a block is equal to or less than a size of a GPU memory. ### Claim 13 (depends on 11) The computing device of claim 11, wherein the main memory stores out-degree information for each block comprising out-degrees of source vertices of edges included in each block and pagerank information for each block comprising pageranks of the source vertices of the edges included in each block, wherein the one or more GPUs are further configured to calculate a weight based on block unit data comprising the out-degree information for each block, the pagerank information for each block, and graph data for each block. ### Claim 14 (depends on 11) The computing device of claim 11, wherein the main memory comprises a plurality of blocks into which the graph is divided based on a source vertex and a destination vertex, wherein the processor is further configured to load a plurality of block unit data into a plurality of GPU memories through a plurality of streams. ### Claim 15 (depends on 1) A non-transitory computer-readable recording medium having recorded thereon a computer program for performing the graph data calculation method of claim 1.