Reasoning Over Knowledge Graphs

Different Classes of Graph Algorithms

For the purposes of computing over knowledge graphs, there are three broad categories of algorithms:

• Statistical : Provides metrics about the graph, such as the number of nodes and relationships, degree distribution of relationships, types of node labels, and so on. These will provide context for interpretation of your results.
• Analytical: Surfaces significant patterns or latent knowledge over the whole knowledge graph or significant subcomponents.
• Machine learning (ML) : Uses the results from graph algorithms as features to train machine learning models or uses machine learning to evolve the knowledge graph itself.

Within statistical and analytic algorithms, there are five categories that are common to knowledge graph use cases: 

• Network propagation : Understanding how signals propagate through a  knowledge graph requires deep path computations. The resulting pathways  can identify the spread of disease in a community or supply-chain  weaknesses. Correspondingly, the results can be used to optimize for  containment or adding redundancy to critical paths. 
• Influence : In current times of near-ubiquitous social media, you are  accustomed to the idea of “influencers,” or people whose opinions spread  rapidly through the social graph. In graph data science, the goal is more  general. Influential nodes act as bridges (and bottlenecks) between  subgraphs and are ideally positioned to spread information (or disruption)  around the network quickly since they are, on average, close to all the other  nodes. A measure of a node’s influence is known as its centrality.
• Community detection : In the human world, communities are the ties that  bind us together. That’s true in the world of graph algorithms too, but to find  tightly knit communities, graph algorithms tend to partition groups by  looking for weak links to remove. Being able to detect communities in a  knowledge graph tells you about related works that you might want to read,  fraudsters cooperating to commit financial crimes, or communities where pathogens (including disinformation) will spread quickly.
• Similarity : When you visualize a knowledge graph, you can often easily spot  similar patterns being repeated in the graph. For example, you can see  customers with a particular purchase history who would be well served with a particular product recommendation or road intersections associated with  abnormal levels of vehicle collisions. But when the graph is large, manual  inspection falls short. Similarity algorithms search for known  relationships/hierarchies between nodes or common properties on them.
• Link prediction : Using the existing topology of the knowledge graph with  some heuristics (for example, creating triangles), link prediction algorithms  can enrich the knowledge graph by computing missing relationships. This is a common use case in social networks where possible friends/followers/contacts can be computed.