Determining relatedness of data using graphs to support machine learning, natural language parsing, search engine, or other functions

An apparatus comprising:

• at least one processor configured to:
• obtain a graph comprising vertices that represent items and edges that represent relationships between the items;
• identify pairwise relatedness values associated with pairs of vertices in the graph, wherein each pairwise relatedness value is determined as a measure of diffusion on a space in the graph with a first vertex acting as a diffusion source and a boundary acting as a diffusion sink such that a diffusion density at a second vertex defines the pairwise relatedness value associated with the first and second vertices;
• and
• perform at least one of machine learning, natural language parsing, or a search via a search engine using the pairwise relatedness values as a measure of how the items associated with the pairs of vertices in the graph are related to one another;
• wherein, to identify the pairwise relatedness values, the at least one processor is configured to use a boundary condition that defines the boundary on the space in the graph around the diffusion source, wherein vertices outside the boundary are assumed to have a pairwise relatedness value of zero with respect to the diffusion source;
• and
• wherein the at least one processor is configured to determine the measure of diffusion for each pairwise relatedness value as an approximation of the Green's function of a discrete Laplacian of the graph by, for each of multiple vertices acting as the diffusion source, (i) using a moving wavefront around the diffusion source as a boundary and (ii) stopping movement of the wavefront when the Green's function value or its derivative at the wavefront reaches a specific threshold.

A non-transitory computer readable medium containing instructions that when executed cause at least one processor to:

• obtain a graph comprising vertices that represent items and edges that represent relationships between the items;
• identify pairwise relatedness values associated with pairs of vertices in the graph, wherein each pairwise relatedness value is determined as a measure of diffusion on a space in the graph with a first vertex acting as a diffusion source and a boundary acting as a diffusion sink such that a diffusion density at a second vertex defines the pairwise relatedness value associated with the first and second vertices;
• and
• perform at least one of machine learning, natural language parsing, or a search via a search engine using the pairwise relatedness values as a measure of how the items associated with the pairs of vertices in the graph are related to one another,
• wherein the instructions that when executed cause the at least one processor to identify the pairwise relatedness values comprise instructions that when executed cause the at least one processor to use a boundary condition that defines the boundary on the space in the graph around the diffusion source, wherein vertices outside the boundary are assumed to have a pairwise relatedness value of zero with respect to the diffusion source;
• and
• wherein the instructions when executed cause the at least one processor to determine the measure of diffusion for each pairwise relatedness value as an approximation of the Green's function of a discrete Laplacian of the graph by, for each of multiple vertices acting as the diffusion source, (i) using a moving wavefront around the diffusion source as a boundary and (ii) stopping movement of the wavefront when the Green's function value or its derivative at the wavefront reaches a specific threshold.