Network spillover detection and global holdout creation using graph partitioning

Patent metadata

Field	Value
Publication number	US-2025208978-A1
Application number	US-202318392293-A
Country	US
Kind code	A1
Filing date	Dec 21, 2023
Priority date	Dec 21, 2023
Publication date	Jun 26, 2025
Grant date	—

Abstract

Methods and systems are presented for facilitating computer software feature experimentation by using one or more graph analyses to partition users into different experimentation groups. A graph is generated to represent users of a service provider and relationships among the users. When a request to perform a software feature experiment on the users of the service provider, the graph is analyzed to determine an estimated spillover effect. The graph is then coarsened across multiple levels using a label propagation technique based on one or more coarsening parameters. After the graph has been coarsened, the graph is partitioned into multiple partitions based on one or more partitioning parameters. The coarsening parameters and/or the partitioning parameters may be determined based on the estimated spillover effect. A subset of users is selected for performing the software feature experiment based on the partitioning of the coarsened graph.

First claim

What is claimed is:

1 . A system, comprising:
a non-transitory memory; and one or more hardware processors coupled with the non-transitory memory and configured to read instructions from the non-transitory memory to cause the system to perform operations comprising:
accessing a graph representing a plurality of accounts and transactions conducted among the plurality of accounts;
coarsening the graph based on merging one or more nodes in the graph that share one or more attributes;
partitioning the coarsened graph into two or more sub-graphs using one or more constraints;
applying the partitioning of the coarsened graph to the graph based on mapping the two or more sub-graphs of the coarsened graph to a plurality of sub-graphs in the graph; and
modifying an account setting of one or more accounts corresponding to a subset of nodes within a first sub-graph in the plurality of sub-graphs.

2 . The system of claim 1 , wherein the one or more constraints comprise a minimum size threshold for a first one of the two or more sub-graphs and/or a maximum size threshold for the first one of the two or more sub-graphs.

3 . The system of claim 1 , wherein the modifying the account setting comprises modifying a presentation of a user interface element on a user interface when the user interface is accessed through one of the one or more accounts.

4 . The system of claim 1 , wherein the modifying the account setting comprises including an additional transaction functionality for the one or more accounts.

5 . The system of claim 1 , wherein the coarsening the graph comprises:
assigning a first label to a first node in the graph; and propagating the first label to a first plurality of other nodes in the graph based on edge attributes of a plurality of edges in the graph.

6 . The system of claim 5 , wherein the coarsening the graph further comprises:
assigning a second label to a second node in the graph; and propagating the second label to a second plurality of other nodes in the graph based on the edge attributes of the plurality of edges in the graph.

7 . The system of claim 5 , wherein the operations further comprise:
merging the first node and a third node that has been assigned the first label.

8 . A method comprising:
accessing, by a computer system, a graph representing a plurality of users with a service provider and transactions conducted among the plurality of users; transforming, by the computer system, the graph based on iteratively performing a coarsening process on the graph; partitioning, by the computer system, the transformed graph into two or more sub-graphs based on one or more constraints; selecting, from the plurality of users, a first subset of users based on the partitioning of the transformed graph; and performing a feature experiment for the service provider, wherein the performing the feature experiment comprises modifying first instances of a computer software associated with the first subset of users.

9 . The method of claim 8 , wherein the feature experiment is performed without modifying second instances of the computer software associated with a second subset of users from the plurality of users.

10 . The method of claim 9 , further comprising:
subsequent to the modifying the first instances of the computer software, monitoring first interactions of the first subset of users with the first instances of the computer software and second interactions of the second subset of users with the second instances of the computer software.

11 . The method of claim 10 , further comprising:
comparing the first interactions against the second interactions; and determining whether to update the computer software based on the comparing.

12 . The method of claim 8 , wherein the transforming the graph comprises:
generating a first coarsened graph based on collapsing one or more first subsets of nodes in the graph into one or more first nodes; and generating a second coarsened graph based on collapsing one or more second subsets of nodes in the first coarsened graph into one or more second nodes.

13 . The method of claim 8 , wherein the modifying the first instances of the computer software comprises modifying a user interface element of a user interface in the first instances of the computer software.

14 . The method of claim 8 , wherein the modifying the first instances of the computer software comprises adding a functionality to the first instances of the computer software, wherein the functionality is unavailable to second instances of the computer software associated with a second subset of users from the plurality of users.

15 . A non-transitory machine-readable medium having stored thereon machine-readable instructions executable to cause a machine to perform operations comprising:
accessing a graph representing a plurality of users with a service provider and relationships among the plurality of users; estimating a spillover effect for performing a feature experiment on the plurality of users based on the graph; determining one or more constraint parameters based on the estimated spillover effect; partitioning the graph into two or more sub-graphs using the one or more constraint parameters; selecting, from the plurality of users, a first subset of users based on the partitioning of the graph; and performing the feature experiment on the plurality of users, wherein the performing the feature experiment comprises modifying first instances of a computer software associated with the first subset of users.

16 . The non-transitory machine-readable medium of claim 15 , wherein the graph comprises a plurality of nodes representing the plurality of users and edges representing the relationships among the plurality of users, and wherein the operations further comprise:
assigning labels to the plurality of nodes in the graph; propagating the labels through the plurality of nodes in the graph using a label propagation technique; and generating a coarsened graph from the graph based on merging one or more nodes in the graph that share an identical label, wherein the partitioning is performed on the coarsened graph.

17 . The non-transitory machine-readable medium of claim 15 , wherein the one or more constraint parameters comprise a distribution deviation parameter that specifies a threshold deviation for a distribution of a particular type of users among the two or more sub-graphs.

18 . The non-transitory machine-readable medium of claim 17 , wherein the one or more constraint parameters comprise a distribution deviation parameter that specifies a threshold deviation for a conversion rate among the two or more sub-graphs.

19 . The non-transitory machine-readable medium of claim 15 , wherein the modifying the first instances of the computer software comprises modifying a user interface element of a user interface in the first instances of the computer software.

20 . The non-transitory machine-readable medium of claim 15 , wherein the modifying the first instances of the computer software comprises adding a functionality to the first instances of the computer software, wherein the functionality is unavailable to second instances of the computer software associated with a second subset of users from the plurality of users.

Assignees

• Paypal Inc

Inventors

• Sharma Nitin S
• Amani Geshnigani Sanae
• Zhang Pengshan
• Jia Haoyang
• Guo Junshi

Classifications

• G06F11/3612 Primary

  by runtime analysis (performance monitoring G06F11/3466) · CPC title

• G06F11/3672 Primary

  Test management · CPC title