公开(公告)号：US20220070266A1

公开(公告)日：2022-03-03

申请号：US17008339

申请日：2020-08-31

Applicant: Adobe Inc.

Inventor： Ryan ROSSI ,  Tung MAI ,  Anup RAO

IPC: H04L29/08 ,  G06F16/901 ,  G06F17/18

Abstract: A system and method for fast, accurate, and scalable typed graphlet estimation. The system and method utilizes typed edge sampling and typed path sampling to estimate typed graphlet counts in large graphs in a small fraction of the computing time of existing systems. The obtained unbiased estimates of typed graphlets are highly accurate, and have applications in the analysis, mining, and predictive modeling of massive real-world networks. During operation, the system obtains a dataset indicating nodes and edges of a graph. The system samples a portion of the graph and counts a number of graph features in the sampled portion of the graph. The system then computes an occurrence frequency of a typed graphlet pattern and a total number of typed graphlets associated with the typed graphlet pattern in the graph.

公开(公告)号：US20210150568A1

公开(公告)日：2021-05-20

申请号：US16688700

申请日：2019-11-19

Applicant: ADOBE INC.

Inventor： Alireza FARHADI ,  Ryan A. ROSSI ,  Tung MAI ,  Anup RAO

IPC: G06Q30/02 ,  G06F16/2455 ,  G06F16/901 ,  G06F16/735

Abstract: Embodiments of the present invention provide systems, methods, and computer storage media for determining an increased matching for large graphs in which an increased matching is generated for the graph by leveraging an initial matching for a small fraction of edges of the large graph. An initial matching for a random subset of edges of an input graph is leveraged to generate alternating paths based on the initially matched edges and the remaining edges, not included in the random subset. An increased matching for the entire graph includes the alternating paths without the initial matched edges, thus increasing the number of matched edges in the increased matching by at least one for every initially matched edge. Graph-based tasks may then be triggered based on the increased matching.