Method and apparatus for processing graph data, device, storage medium, and program product

Patent metadata

Field	Value
Publication number	US-12585703-B2
Application number	US-202217977881-A
Country	US
Kind code	B2
Filing date	Oct 31, 2022
Priority date	Mar 8, 2021
Publication date	Mar 24, 2026
Grant date	Mar 24, 2026

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.

First claim

What is claimed is:

1 . A graph data processing method, performed by at least one processor, the method comprising:
acquiring relationship data formed when terminals interact through an application server, the relationship data representing interactions between user identifiers in a network system; generating a directed graph from the relationship data, wherein a vertex in the directed graph represents a user identifier, and a directed edge in the directed graph represents a directional relationship between user identifiers corresponding to a start vertex and a destination vertex; re-representing the directed edge in a unified form that is different from a form of the directed graph as obtained, in a data structure comprising a matrix or a list, according to a specified order between a vertex identifier of the start vertex and a vertex identifier of the destination vertex, wherein the specified order is determined independently from a traversal order of the directed graph; recording, in the data structure, a tagged edge indicating an original edge direction of the directed edge prior to re-representing the directed edge in the unified form based on the original edge direction being different than an edge direction of the re-represented directed edge, to obtain a tagged directed graph, wherein a tag of the tagged edge indicates which first vertex from among vertices in the acquired directed graph corresponds to the start vertex and which second vertex from among the vertices in the acquired directed graph corresponds to the destination vertex; 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, wherein the identified category of the triangle is configured for generating a feature vector of the vertex for application to pattern identification tasks including identifying abnormal network activities or discovering network communities.

2 . 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.

3 . 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.

4 . 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.

5 . 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.

6 . 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.

7 . 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.

8 . 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.

9 . 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.

10 . 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.

11 . 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.

12 . 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.

13 . The method according to claim 12 , wherein the identifying of the category of the triangle f

Assignees

• Tencent Tech Shenzhen Company Ltd

Inventors

• Xu Jie
• Li Xiaosen
• Ouyang Wen
• Xiao Pin
• Tao Yangyu

Classifications

• G06Q10/40

  Business processes related to social networking or social networking services · CPC title

• G06Q10/42

  Determination of affinities or common interests between users · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F16/9536

  Search customisation based on social or collaborative filtering · CPC title