# US 2020/0401931 A1 · Location dimension reduction using graph techniques

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

- Number: US 2020/0401931 A1
- Document ID: US20200401931A1
- Status: Published application
- Kind: A1
- Application number: 16/447,810
- Filed: 2019-06-20
- Published: 2020-12-24
- Earliest claimed: 2019-06-20
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Qing Duan; Xiaowen Zhang; Xiaoqing Wang; Junrui Xu
- Web page: https://patentgrep.com/patent/US20200401931A1

## CPC

- G06F 16/26: Visual data mining; Browsing structured data
- G06F 16/29: Geographical information databases
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 18/23: Clustering techniques
- G06F 18/2323: based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 20/00: Machine learning
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Technologies for generating a graph containing clusters of feature attribute values for training a machine learning model for content item selection and delivery are provided. The disclosed techniques include, for each entity, of a plurality of entities, a system identifies transitions from one geographic location to another geographic location. A graph is generated based on the transitions associated with each entity. The graph comprises nodes representing geographic locations and edges connecting the nodes. Each of the edges connects two nodes, represents a transition from one geographic location to another geographic location, and each edge represents an edge weight value that is based on frequencies of transitions between geographic locations represented by the two connected nodes. The system generates a plurality of clusters from the nodes based upon the edge weight value of each edge. The system includes the plurality of clusters as features in a machine learning model.

## Claims

### Claim 1

A method comprising:
for each entity of a plurality of entities, identifying one or more transitions from one geographic location to another geographic location;
generating a graph based on the one or more transitions associated with each entity of the plurality of entities;
wherein the graph comprises a plurality of nodes representing geographic locations and a plurality of edges connecting the plurality of nodes;
wherein each edge of the plurality of edges (1) connects two nodes of the plurality of nodes, (2) represents a transition from a geographic location represented by one of the two nodes to the other of the two nodes, and (3) represents an edge weight value that is based on frequencies of transitions between geographic locations represented by the two nodes;
generating a plurality of clusters from the plurality of nodes based on the edge weight value of each edge of the plurality of edges; and
including the plurality of clusters as feature values in a machine-learned model;
wherein the method is performed by one or more computing devices.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with said each geographic location;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
removing the subset of geographic locations from the geographic locations to be used to generate the graph;
after removing the subset of geographic locations from the geographic locations to generate a second subset of geographic locations, generating the graph based on the one or more transitions associated with each entity of the plurality of entities and the second subset of geographic locations.

### Claim 3 (depends on 1)

The method of claim 1, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each specific geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with the specific geographic location of the geographic locations;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
for each geographic location in the subset of geographic locations:
determining a nearby geographic location based on a distance between said geographic location and the nearby geographic location, wherein the nearby geographic location is part of the geographic locations and is not part of the subset of geographic locations;
assigning each of the entities that are associated with said geographic location to the nearby geographic location.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
upon generating the graph based on the one or more transitions associated with each entity of the plurality of entities, identifying one or more edges within the graph that have edge weight values below a dropping threshold that represents the minimum edge weight value for edges within the graph; and
removing the one or more edges from the graph.

### Claim 5 (depends on 1)

The method of claim 1, further comprising, for each edge of the plurality of edges:
determining a first subset of transitions of the frequencies of transitions for said each edge that have transition timestamps older than a recency threshold, wherein the recency threshold is a range of time defining whether a transition is recent;
assigning a first weight to each transition of the first subset of transitions;
determining a second subset of transitions of the frequencies of transitions for said edge that have transition timestamps younger than the recency threshold;
assigning a second weight to each transition of the second subset of transitions, wherein the second weight is larger than the first weight;
calculating the edge weight value for said edge as a sum of the first weights of the first subset of transitions and the second weights of the second subset of transitions.

### Claim 6 (depends on 1)

The method of claim 1, wherein generating the plurality of clusters from the plurality of nodes based on the edge value of each edge, comprises:
for each pair of edges connected to a pair of nodes within the graph:
calculating an edge difference value as an absolute value of the difference between edge weight values of said pair of edges;
determining whether the edge difference value is below a clustering threshold value, wherein the clustering threshold value defines whether the pair of nodes are to be clustered;
upon determining that the edge difference value is below the clustering threshold value, generating a cluster made up of the pair of nodes, wherein the cluster is part of the plurality of clusters.

### Claim 7 (depends on 6)

The method of claim 6, wherein the clustering threshold value is based on a desired number of total nodes in the graph.

### Claim 8 (depends on 6)

The method of claim 6, wherein the clustering threshold value is based upon a percentage of a sum of the edge weight values of said pair of edges.

### Claim 9

A computer program product comprising:
one or more non-transitory computer-readable storage media comprising instructions which, when executed by one or more processors, cause:
for each entity of a plurality of entities, identifying one or more transitions from one geographic location to another geographic location;
generating a graph based on the one or more transitions associated with each entity of the plurality of entities;
wherein the graph comprises a plurality of nodes representing geographic locations and a plurality of edges connecting the plurality of nodes;
wherein each edge of the plurality of edges (1) connects two nodes of the plurality of nodes, (2) represents a transition from a geographic location represented by one of the two nodes to the other of the two nodes, and (3) represents an edge weight value that is based on frequencies of transitions between geographic locations represented by the two nodes;
generating a plurality of clusters from the plurality of nodes based on the edge weight value of each edge of the plurality of edges; and
including the graph and the plurality of clusters as feature values in a machine-learned model.

### Claim 10 (depends on 9)

The computer program product of claim 9, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with said each geographic location;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
removing the subset of geographic locations from the geographic locations to be used to generate the graph;
after removing the subset of geographic locations from the geographic locations to generate a second subset of geographic locations, generating the graph based on the one or more transitions associated with each entity of the plurality of entities and the second subset of geographic locations.

### Claim 11 (depends on 9)

The computer program product of claim 9, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each specific geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with the specific geographic location of the geographic locations;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
for each geographic location in the subset of geographic locations:
determining a nearby geographic location based on a distance between said geographic location and the nearby geographic location, wherein the nearby geographic location is part of the geographic locations and is not part of the subset of geographic locations;
assigning each of the entities that are associated with said geographic location to the nearby geographic location.

### Claim 12 (depends on 9)

The computer program product of claim 9, wherein the one or more non-transitory computer-readable storage media comprises further instructions which, when executed by the one or more processors, cause:
upon generating the graph based on the one or more transitions associated with each entity of the plurality of entities, identifying one or more edges within the graph that have edge weight values below a dropping threshold that represents the minimum edge weight value for edges within the graph; and
removing the one or more edges from the graph.

### Claim 13 (depends on 9)

The computer program product of claim 9, wherein the optimized graph generation system performs further operations comprising, for each edge of the plurality of edges:
determining a first subset of transitions of the frequencies of transitions for said each edge that have transition timestamps older than a recency threshold, wherein the recency threshold is a range of time defining whether a transition is recent;
assigning a first weight to each transition of the first subset of transitions;
determining a second subset of transitions of the frequencies of transitions for said edge that have transition timestamps younger than the recency threshold;
assigning a second weight to each transition of the second subset of transitions, wherein the second weight is larger than the first weight;
calculating the edge weight value for said edge as a sum of the first weights of the first subset of transitions and the second weights of the second subset of transitions.

### Claim 14 (depends on 9)

The computer program product of claim 9, wherein generating the plurality of clusters from the plurality of nodes based on the edge value of each edge, comprises:
for each pair of edges connected to a pair of nodes within the graph:
calculating an edge difference value as an absolute value of the difference between edge weight values of said pair of edges;
determining whether the edge difference value is below a clustering threshold value, wherein the clustering threshold value defines whether the pair of nodes are to be clustered;
upon determining that the edge difference value is below the clustering threshold value, generating a cluster made up of the pair of nodes, wherein the cluster is part of the plurality of clusters.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein the clustering threshold value is based on a desired number of total nodes in the graph.

### Claim 16 (depends on 14)

The computer program product of claim 14, wherein the clustering threshold value is based upon a percentage of a sum of the edge weight values of said pair of edges.

### Claim 17

A system comprising:
one or more computer processors;
an optimized graph generation system coupled to the one or more processors, wherein the optimized graph generation system performs operations comprising:
for each entity of a plurality of entities, identifying one or more transitions from one geographic location to another geographic location;
generating a graph based on the one or more transitions associated with each entity of the plurality of entities;
wherein the graph comprises a plurality of nodes representing geographic locations and a plurality of edges connecting the plurality of nodes;
wherein each edge of the plurality of edges (1) connects two nodes of the plurality of nodes, (2) represents a transition from a geographic location represented by one of the two nodes to the other of the two nodes, and (3) represents an edge weight value that is based on frequencies of transitions between geographic locations represented by the two nodes;
generating a plurality of clusters from the plurality of nodes based on the edge weight value of each edge of the plurality of edges; and
including the graph and the plurality of clusters as feature values in a machine-learned model.

### Claim 18 (depends on 17)

The system of claim 17, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with said each geographic location;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
removing the subset of geographic locations from the geographic locations to be used to generate the graph;
after removing the subset of geographic locations from the geographic locations to generate a second subset of geographic locations, generating the graph based on the one or more transitions associated with each entity of the plurality of entities and the second subset of geographic locations.

### Claim 19 (depends on 17)

The system of claim 17, wherein generating the graph based on the one or more transitions associated with each entity of the plurality of entities, comprises:
for each specific geographic location of the geographic locations, determining a count of entities from the plurality of entities that are associated with the specific geographic location of the geographic locations;
determining a subset of geographic locations of the geographic locations that have counts of entities that are below a dropping threshold that represents the minimum size for nodes in the graph;
for each geographic location in the subset of geographic locations:
determining a nearby geographic location based on a distance between said geographic location and the nearby geographic location, wherein the nearby geographic location is part of the geographic locations and is not part of the subset of geographic locations;
assigning each of the entities that are associated with said geographic location to the nearby geographic location.

### Claim 20 (depends on 17)

The system of claim 17, wherein the optimized graph generation system performs further operations comprising:
upon generating the graph based on the one or more transitions associated with each entity of the plurality of entities, identifying one or more edges within the graph that have edge weight values below a dropping threshold that represents the minimum edge weight value for edges within the graph; and
removing the one or more edges from the graph.