Methods and systems for encoding graphs

1. A computer-implemented method comprising:

receiving, by one or more computing devices, data describing a first graph;

generating, by the one or more computing devices and based at least in part on the data describing the first graph, data describing a second graph, the second graph comprising, for each node, of one or more nodes, of the first graph, multiple nodes corresponding to the node of the first graph, each node of the multiple nodes representing an instantiation of the node of the first graph in a community to which the node of the multiple nodes belongs, wherein generating the data describing the second graph comprises:

generating data describing a plurality of ego networks comprising, for each node, of the one or more nodes, of the first graph, one or more ego networks of the node of the first graph;

partitioning the plurality of ego networks into a plurality of partitions; and

generating the data describing the second graph based at least in part on the plurality of partitions;

encoding, by the one or more computing devices, one or more of the first graph or the second graph, the encoding comprising, for each node, of the one or more nodes, of the first graph, determining, based at least in part on the data describing the second graph and for each node of the multiple nodes of the second graph corresponding to the node of the first graph, a representation of a role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs; and

identifying, by the one or more computing devices and based at least in part on the encoding, a link between two different nodes of one or more of the first graph or the second graph.

2. The computer-implemented method of claim 1 , wherein determining the representation comprises determining the representation based at least in part on an overlapping structure of the community to which the node of the multiple nodes belongs and one or more other communities.

3. The computer-implemented method of claim 1 , wherein generating the data describing the second graph comprises, for each node, of the one or more nodes, of the first graph, determining, based at least in part on a number of the plurality of partitions comprising the node of the first graph, a number of the multiple nodes corresponding to the node of the first graph to include in the second graph.

4. The computer-implemented method of claim 1 , wherein generating the data describing the second graph comprises generating data describing a persona graph of the first graph.

5. The computer-implemented method of claim 1 , wherein:

the first graph comprises an undirected graph;

each node of the second graph corresponds to a node of the first graph; and

each edge of the second graph corresponds to an edge of the first graph.

6. The computer-implemented method of claim 1 , wherein:

the method comprises determining, by the one or more computing devices, for each node, of the one or more nodes, of the first graph, and based at least in part on the data describing the first graph, a representation of the node of the first graph in the first graph; and

determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining, based at least in part on the representation of the node of the first graph in the first graph, the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.

7. The computer-implemented method of claim 6 , wherein determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining, based at least in part on a parameter that regularizes the degree to which the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs can deviate from the representation of the node of the first graph in the first graph, the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.

8. The computer-implemented method of claim 1 , wherein determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs such that the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs predicts the node of the first graph.

9. The computer-implemented method of claim 1 , wherein determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs such that the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises a dependency on the node of the first graph.

10. The computer-implemented method of claim 1 , comprising predicting, by the one or more computing devices, for a node, of the one or more nodes, of the first graph, and based at least in part on representations, determined by the one or more computing devices for the multiple nodes of the second graph corresponding to the node of the first graph, of roles of the multiple nodes in communities to which the multiple nodes belong, a link between the node of the first graph and another node of the first graph.

11. The computer-implemented method of claim 1 , comprising generating, by the one or more computing devices, for a node, of the one or more nodes, of the first graph, and based at least in part on representations, determined by the one or more computing devices for the multiple nodes of the second graph corresponding to the node of the first graph, of roles of the multiple nodes in communities to which the multiple nodes belong, a graphical user interface (GUI) depicting the communities to which the multiple nodes belong.

12. The computer-implemented method of claim 1 , wherein determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining a numerical embedding in an embedding dimensional space.

13. The computer-implemented method of claim 1 , wherein a dot-product between a pair of representations respectively determined by the one or more computing devices for a pair of nodes of the second graph encodes a similarity between the pair of nodes in the second graph.

14. A system comprising:

one or more processors; and

a memory storing instructions that when executed by the one or more processors cause the system to perform operations comprising:

receiving data describing a first graph;

generating data describing a plurality of ego networks comprising, for each node, of one or more nodes, of the first graph, one or more ego networks of the node of the first graph;

partitioning the plurality of ego networks into a plurality of partitions;

generating, based at least in part on the plurality of partitions, a second graph, the second graph comprising, for each node, of the one or more nodes, of the first graph, multiple nodes corresponding to the node of the first graph, each node of the multiple nodes representing an instantiation of the node of the first graph in a community to which the node of the multiple nodes belongs; and

for each node, of the one or more nodes, of the first graph, determining, based at least in part on the data describing the second graph, and for each node of the multiple nodes of the second graph corresponding to the node of the first graph, a representation of a role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.

15. The system of claim 14 , wherein generating the data describing the second graph comprises, for each node, of the one or more nodes, of the first graph, determining, based at least in part on a number of the plurality of partitions comprising the node of the first graph, a number of the multiple nodes corresponding to the node of the first graph to include in the second graph.

16. The system of claim 14 , wherein:

the operations comprise determining, for each node, of the one or more nodes, of the first graph and based at least in part on the data describing the first graph, a representation of the node of the first graph in the first graph; and

determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining, based at least in part on the representation of the node of the first graph in the first graph, the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.

17. One or more non-transitory computer-readable media comprising instructions that when executed by one or more computing devices cause the one or more computing devices to perform operations comprising:

receiving data describing a first graph;

generating data describing a plurality of ego networks comprising, for each node, of one or more nodes, of the first graph, one or more ego networks of the node of the first graph;

partitioning the plurality of ego networks into a plurality of partitions;

generating, based at least in part on the plurality of partitions, a second graph, the second graph comprising, for each node, of the one or more nodes, of the first graph, multiple nodes corresponding to the node of the first graph, each node of the multiple nodes representing an instantiation of the node of the first graph in a community to which the node of the multiple nodes belongs; and

for each node, of one or more nodes, of the first graph, determining, based at least in part on data describing the second graph, and for each node of the multiple nodes of the second graph corresponding to the node of the first graph, a representation of a role of the node of the multiple nodes in a community to which the node of the multiple nodes belongs.

18. The one or more non-transitory computer-readable media of claim 17 , wherein:

the operations comprise determining, for each node, of the one or more nodes, of the first graph and based at least in part on the data describing the first graph, a representation of the node of the first graph in the first graph; and

determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining, based at least in part on the representation of the node of the first graph in the first graph, the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.

19. The one or more non-transitory computer-readable media of claim 18 , wherein determining the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs comprises determining, based at least in part on a parameter that regularizes the degree to which the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs can deviate from the representation of the node of the first graph in the first graph, the representation of the role of the node of the multiple nodes in the community to which the node of the multiple nodes belongs.