# US 2023/0056760 A1 · Method and apparatus for processing graph data, device, storage medium, and program product

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0056760 A1
- Document ID: US20230056760A1
- Status: Published application
- Kind: A1
- Application number: 17/977,881
- Filed: 2022-10-31
- Published: 2023-02-23
- Earliest claimed: 2021-03-08
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Ltd
- Inventors: Jie XU; Xiaosen LI; Wen OUYANG; Pin XIAO; Yangyu TAO
- Web page: https://patentgrep.com/patent/US20230056760A1

## CPC

- G06Q 30/0201: Market modelling; Market analysis; Collecting market data
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06Q 10/42: Determination of affinities or common interests between users
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A graph data processing method includes acquiring a directed graph, where a directed edge in the directed graph is represented as pointing to a destination vertex from a start vertex; representing the directed edge in a unified form according to a specified order between a vertex identifier of the start vertex and a vertex identifier of the destination vertex; generating a tagged edge for recording an original edge direction of the directed edge, to obtain a tagged directed graph; and identifying a category of a triangle constituted by a vertex in the tagged directed graph, a neighbor vertex of the vertex, and a common vertex commonly adjacent to the vertex and the neighbor vertex, based on tagged edges between two of the vertex, the neighbor vertex, and the common vertex.

## Claims

### Claim 1

A graph data processing method, performed by at least one processor, the method comprising:
acquiring a directed graph, a directed edge in the directed graph being represented as pointing to a destination vertex from a start vertex;
representing the directed edge in a unified form according to a specified order between a vertex identifier of the start vertex and a vertex identifier of the destination vertex;
generating a tagged edge for recording an original edge direction of the directed edge, to obtain a tagged directed graph; and
identifying a category of a triangle constituted by a vertex in the tagged directed graph, a neighbor vertex of the vertex, and a common vertex commonly adjacent to the vertex and the neighbor vertex, based on tagged edges between two of the vertex, the neighbor vertex, and the common vertex, the identified category of the triangle being used for generating a feature vector of the vertex.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the acquiring of the directed graph comprises:
acquiring a payment record corresponding to user identifiers;
obtaining payment interaction data between the user identifiers according to the payment record; and
generating a directed payment network graph according to the payment interaction data as the directed graph, a vertex of the directed payment network graph representing a user identifier, a directed edge between two vertexes in the directed payment network graph representing that there is a one-way or two-way payment interaction event between corresponding two user identifiers.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the acquiring of the directed graph comprises:
acquiring a contact list corresponding to user identifiers in a community network;
obtaining contact relationship data between the user identifiers according to the contact list; and
generating a directed community network graph according to the contact relationship data as the directed graph, a vertex in the directed community network graph representing a user identifier, a directed edge between two vertexes in the directed community network graph representing that there is a one-way or two-way contact relationship between corresponding two user identifiers.

### Claim 4 (depends on 1)

The method according to claim 1,
wherein the representing of the directed edge in the unified form comprises representing the directed edge as pointing to the start vertex from the destination vertex based on the start vertex at which the directed edge is located being a larger vertex and the destination vertex being a smaller vertex; and
wherein the generating of the tagged edge comprises tagging an edge direction pointing to the start vertex from the destination vertex as a first value.

### Claim 5 (depends on 4)

The method according to claim 4, wherein the representing of the directed edge as pointing to the larger vertex from the smaller vertex comprises tagging an edge direction pointing to the destination vertex from the start vertex as a second value in a case that the start vertex at which the directed edge is located is less than the destination vertex.

### Claim 6 (depends on 1)

The method according to claim 1,
wherein the representing of the directed edge in the unified form comprises representing the directed edge as pointing to the start vertex from the destination vertex based on the start vertex at which the directed edge is located being less than the destination vertex; and
the generating of the tagged edge comprises tagging an edge direction pointing to the start vertex from the destination vertex as a first value.

### Claim 7 (depends on 6)

The method according to claim 6, wherein the generating of the tagged edge further comprises tagging an edge direction pointing to the destination vertex from the start vertex as a second value based on the start vertex at which the directed edge is located being greater than the destination vertex.

### Claim 8 (depends on 1)

The method according to claim 1, further comprising:
for each vertex in the tagged directed graph, aggregating neighbor vertexes to which the vertex points, to obtain a neighbor vertex set corresponding to the vertex; and
generating, according to tagged edges between the vertexes and neighbor vertexes in the corresponding neighbor vertex set, an adjacency list carrying the tagged edges and corresponding to the vertexes.

### Claim 9 (depends on 8)

The method according to claim 8, further comprising:
replacing a tagged edge of a directed edge between the vertex and the neighbor vertex with a third value based on there being a neighbor vertex whose tagged edge is both a first value and a second value in the neighbor vertex set, the third value being used for representing that the directed edge between the vertex and the neighbor vertex is a two-way edge.

### Claim 10 (depends on 1)

The method according to claim 1, further comprising:
acquiring edge directions of three directed edges constituting a triangle and the category of the triangle;
arranging the three directed edges in sequence to obtain an edge direction sequence of the triangle; and
storing the edge direction sequence and the category of the triangle in a corresponding manner to generate a category index of the triangle.

### Claim 11 (depends on 10)

The method according to claim 10, wherein the storing of the edge direction sequence and the category of the triangle in the corresponding manner comprises:
determining, according to the edge direction sequence, a quantity of two-way edges in the three directed edges constituting the triangle; and
storing the quantity of two-way edges, the edge direction sequence, and the category of the triangle in the corresponding manner to generate the category index of the triangle.

### Claim 12 (depends on 1)

The method according to claim 1, wherein the identifying of the category of the triangle comprises:
traversing the vertexes of the triangle in the tagged directed graph;
determining a first neighbor vertex set to which a current traversed vertex points, a second neighbor vertex set to which neighbor vertexes in the first neighbor vertex set point, and common vertexes of the first neighbor vertex set and the second neighbor vertex set; and
identifying, based on tagged edges between the current traversed vertex, the neighbor vertex, and the common vertex, a category of a triangle constituted by the current traversed vertex, the neighbor vertex, and the common vertex.

### Claim 13 (depends on 12)

The method according to claim 12, wherein the identifying of the category of the triangle further comprises:
arranging a tagged edge between the current traversed vertex and the neighbor vertex, a tagged edge between the current traversed vertex and the common vertex, and a tagged edge between the neighbor vertex and the common vertex in sequence, to obtain a tagged edge sequence; and
matching the tagged edge sequence with edge direction sequences in a category index of the triangle, to obtain the category of the triangle.

### Claim 14 (depends on 13)

The method according to claim 13, wherein the matching of the tagged edge sequence with the edge direction sequences comprises:
determining a quantity of tagged edges representing that the directed edge is a two-way edge in the tagged edge sequence; and
matching the tagged edge sequence with edge direction sequences, in the category index of the triangle, corresponding to the quantity of tagged edges, to determine the category of the triangle according to the matched edge direction sequence.

### Claim 15 (depends on 1)

The method according to claim 1, wherein the directed graph is a community network graph, a vertex in the community network graph represents a user identifier in a community network, a directed edge in the community network graph represents that there is a social relationship between a user identifier corresponding to the start vertex and a user identifier corresponding to the destination vertex, and the method further comprises:
generating, according to a quantity of different categories of triangles in which the respective vertexes are located in the community network graph, a feature vector corresponding to the user identifier represented by the vertex;
determining, according to the feature vector corresponding to the user identifier, a community sub-network graph formed by user identifiers having a similarity degree greater than a threshold from the community network graph; and
determining a community sub-network from the community network based on the community sub-network graph.

### Claim 16

A graph data processing apparatus, comprising:
at least one memory configured to store computer program code; and
at least one processor configured to operate as instructed by the computer program code, the computer program code including:
acquisition code configured to cause the at least one processor to acquire a directed graph, a directed edge in the directed graph being represented as pointing to a destination vertex from a start vertex;
edge representation code configured to cause the at least one processor to represent the directed edge in a unified form according to a specified order between a vertex identifier of the start vertex and a vertex identifier of the destination vertex;
edge tagging code configured to cause the at least one processor to generate a tagged edge for recording an original edge direction of the directed edge, and obtain a tagged directed graph; and
identification code configured to cause the at least one processor to identify a category of a triangle constituted by a vertex in the tagged directed graph, a neighbor vertex of the vertex, and a common vertex commonly adjacent to the vertex and the neighbor vertex, based on tagged edges between two of the vertex, the neighbor vertex, and the common vertex, the identified category of the triangle being used for generating a feature vector of the vertex.

### Claim 17 (depends on 16)

The graph data processing apparatus according to claim 16, wherein the identification code is further configured to cause the at least one processor to:
traverse the vertexes in the tagged directed graph;
determine a first neighbor vertex set to which a current traversed vertex points, a second neighbor vertex set to which neighbor vertexes in the first neighbor vertex set point, and common vertexes of the first neighbor vertex set and the second neighbor vertex set; and
identify, based on tagged edges between the current traversed vertex, the neighbor vertex, and the common vertex, a category of a triangle constituted by the current traversed vertex, the neighbor vertex, and the common vertex.

### Claim 18 (depends on 17)

The graph data processing apparatus according to claim 17, wherein the identification code is further configured to cause the at least one processor to:
arrange a tagged edge between the current traversed vertex and the neighbor vertex, a tagged edge between the current traversed vertex and the common vertex, and a tagged edge between the neighbor vertex and the common vertex in sequence, to obtain a tagged edge sequence; and
match the tagged edge sequence with edge direction sequences in a category index of the triangle, to obtain the category of the triangle.

### Claim 19

At least one non-transitory computer-readable storage medium, storing computer-readable instructions that, when executed by at least one processor, cause the at least one processor to:
acquire a directed graph, a directed edge in the directed graph being represented as pointing to a destination vertex from a start vertex;
represent the directed edge in a unified form according to a specified order between a vertex identifier of the start vertex and a vertex identifier of the destination vertex;
generate a tagged edge for recording an original edge direction of the directed edge, to obtain a tagged directed graph; and
identify a category of a triangle constituted by a vertex in the tagged directed graph, a neighbor vertex of the vertex, and a common vertex commonly adjacent to the vertex and the neighbor vertex, based on tagged edges between two of the vertex, the neighbor vertex, and the common vertex, the identified category of the triangle being used for generating a feature vector of the vertex.

### Claim 20 (depends on 19)

The at least one non-transitory computer-readable storage medium of claim 19, wherein the computer-readable instructions further cause the at least one processor to:
traverse the vertexes in the tagged directed graph;
determine a first neighbor vertex set to which a current traversed vertex points, a second neighbor vertex set to which neighbor vertexes in the first neighbor vertex set point, and common vertexes of the first neighbor vertex set and the second neighbor vertex set; and
identify, based on tagged edges between the current traversed vertex, the neighbor vertex, and the common vertex, a category of a triangle constituted by the current traversed vertex, the neighbor vertex, and the common vertex.