Reasoning on Graphs: Techniques and Applications in Data Analysis

What do pen, bottle, and mushroom have in common?

We have learned over the past 4 weeks that cognitive agents have basic reasoning capabilities. These capabilities are especially prevalent for solving tasks within the domain of Mathematics, Scientific Discovery, or Question Answering. However, their reasoning is limited by up-to-date knowledge which can lead to hallucinations.

We have also learned how knowledge graphs, i.e. qualified and directed relationships between nodes and edges, can contain and easily convey factual knowledge in a structured format. More specifically, data is just bits on the vastness of your storage medium. Information is data in a qualified context. Knowledge is finding all paths connecting the information. Insight is finding the right path to make a decision.

We have also shown that encoding data as graphs can guide cognitive agents to ground their reasoning based on facts. In my prior work, I have discussed how we can effectively retrieve insights for reasoning from graphs and also, to some extent, how to reason on such graphs. In this post, I want to dive a bit deeper on the latter.

When we understand information as data in context and knowledge as information in relation, then insight is finding a reliable and true path through knowledge.

If that is the case, then planning is finding a hidden logic that the cognitive agent needs to execute to find this path.

Let’s say we want to find an answer to this question.

Q: What do pen, bottle, and mushroom have in common?

How would a reasoning agent like our ReAct agent (Matt) go about it?

Planning

If we naively approach the tasks the agent is supposed to do, we quickly understand that we can indeed outline several general steps that help us answer the question.

We will use this later, and specifically Step 8, to assess the quality of the answer by measuring the probability that the answer is optimal (shortest path) given a provided question and graph relation network.

Step 1: Define categories of the objects for comparison.
Step 2: Analyze key features of each object.
Step 3: Cross-reference features by identying overlapping characteristics.
Step 4: Note unique similarities between pairs (pen-bottle, pen-mushroom, bottle-mushroom)
Step 5: Explore functional similarities considering human interactions.
Step 6: Examine structural similarities in regards to shape, form, or components.
Step 7: Investigate lifecycle comparisons like production process
osage period, or Disposal/decomposition
Step 8:  Summarize findings by listing and ranking all identified commonalities and note any surprising or unexpected connections

How can reasoning on graphs help us execute these 8 steps?

First, we must understand plans as sequences of connected nodes in a graph. The solution I am looking for in reasoning on graphs can be defined with two components

Planning: constructing relation paths as plans.

Retrieval-reasoning: Reasong through traversing these plans to retrieve an answer.

How would this work?

We continue by tasking the cognitive agent to create relation paths given the provided question “What do pen, bottle, and mushroom have in common?”.