Over the past few decades, attempts have been made to provide human-like commonsense reasoning to systems by acquiring vast knowledge about any domain. Humans are intuitively good at dealing with uncertainties and making meaningful inferences from incomplete, missing, and unstructured information. On the other hand, machines need precise information typically stored in a structured database and queried using a parsing strategy or well-defined rules. It is hard to rely on traditional relational data stores, as the massive influx of unstructured data and real-world information continuously evolve.

In recent years, knowledge graphs (KGs) have emerged as a flexible representation using the graph-based data model. They capture and integrate factual knowledge from diverse sources of data at a large scale in a way that machines conduct reasoning and inference over the graphs for downstream tasks such as question answering, making useful recommendations, etc., ^[1].

The knowledge graph allows for postponing the schema definition, thus letting the data evolve more flexibly ^[2]. A typical data unit in knowledge graphs is stored as entity–relationship–entity triplets, representing entities as nodes and relationships as the edges in a graph. The nodes are modeled to contain the knowledge or facts about the entities in the form of entity attributes. However, most existing systems used in answering a question over the knowledge graphs rely on static knowledge bases (KBs to train the knowledge graph question-answering (KGQA) model. These systems are trained offline with specific datasets and then deployed online to handle user queries. After deployment, they fail to learn from unseen new entities added to the graph. Thus, the problem faced by the knowledge graphs is the need for dynamic algorithms which can continuously learn and adapt to evolving data ^[3].

Another challenge is the explainability and interpretation of the results when a query is posed to these evolving graphs. Question answering in knowledge graphs requires reasoning over multiple edges to arrive at the right answer and should have a tractable path to explain the new behavior [4,5]^[4][5]. A full explanation of the answer helps the users in their interaction with the system. For example, a query such as, “Which paper author Amanda published in SIGIR conference? ” needs multihop reasoning of the form, $(Amanda,author\_write\_paper,?)$ and $(?,paper\_in\_venue,SIGIR)$ to deduce the answer. Given the nature of this domain, if more papers, conferences, or authors are added in the future, the inference mechanisms need to be adaptable to the changes and interpretable to trace the new paths.

The state-of-the-art embedding-based neural network models for answering semantic queries consider only the candidate answer entities. They learn embeddings conditioned on neighboring entities and relations while being oblivious to the query relations and path. These methods help deduce the new facts but need more interpretation and logical reasoning of the answer ^[6]. The alternative approach uses path-based methods including path ranking algorithms (PRAs) based on random walk ^[7], DeepPath ^[8] etc. These methods are highly interpretable but suffer from large search space issues ^[9]. Moreover, they consider only a static snapshot and fail to learn from dynamically changing knowledge graphs ^[10].

Auction algorithms recently introduced in the paper ^[11], are dynamic and can adapt to the changing environments in real time, making them suitable for offline and online training. They can help knowledge graphs to address the challenges of adaptability and interpretability.

2. REmbelated Workdding-Based Methods

a. Embedding-Based Methods

The popular methods used in knowledge graphs for tasks like question answering, knowledge base completion, link prediction, relation extraction, etc., are embedding-based models ^[12]. Low-dimensional vectors called graph embeddings represent the entities and relations for these tasks. The embedding models learn a scoring function in latent embedding space based on the co-occurrence of words in the text to manifest the semantics of the original graph. The higher score is used to determine the plausibility of facts ^[6]. The top-ranked entities are chosen as the predicted answers. These models learn subtle patterns in data, but they lack generic forms of reasoning. The predicted answers given by the model are a single entity and do not provide any explanation to the user. For instance, the embedding-based model is trained on individual facts such as (Irving Cummings, wasBornIn, New York City) and (New York City, isLocatedin, United States). The model can leverage the logical patterns and compute a score to possibly deduce that (Irving Cummings, isCitizenOf, United States). However, it fails to explain or offer any inference path evidence supporting the answer. This black-box style makes the reasoning process less interpretable and hampers the users from interacting with the system ^[9]. Palmonari et al. ^[13] suggested performing complex logical queries over embedding models to deal with explainability. Bhowmik et al. ^[10] used an inductive learning framework to learn representations and find reasoning paths between entities. Secondly, the embedding-based methods are used to answer factoid-based questions, and they need to improve at answering multihop queries. Most works extract a subgraph to answer the question in parts and later augment the answers ^[14]. Ren et al. ^[15] added a query synthesizer tree to parse the multihop query in parts. A multihop KBQA was proposed by Saxena et al. ^[4] to fill the gaps. They embedded all the entities instead of only using neighborhood entities, and the answers were chosen by finding the similarity score between the question and relations.

b. Path-Based Methods

3. Path-Based Methods

Another approach used for question-answering tasks in knowledge graphs is path based. This approach relies on the conventional graph traversal methods such as A*, Dijkstra, and minimum spanning tree, which use statistical characteristics such as adjacency matrix, degree, closeness, Eigenvector, PageRank, and connectivity [7,8,9,16,17]^{[7][8][9][16][17]}. The inference process is highly interpretable, but these methods suffer from scalability issues and high computation costs, as they rely on enumerating all possible paths ^[9]. All these methods consider the static snapshot of the knowledge graph and only learn the representation of the known entities they have seen before during the offline training. The models are unaware of the emerging entities and fail to keep up with the changes in the graph to answer new questions [5,9]^[5][9]. They thus may not be well-suited for an evolving knowledge graph ^[10].

c. Auction Algorithms

4. Auction Algorithms

Auction algorithms are fundamentally based on mathematical ideas of duality and convex optimization and are inspired by economic equilibrium processes. They have a long history, starting with the original proposal ^[18], which aimed to solve the classical problem of assignment of objects to persons through a competitive bidding mechanism that resembles a real-life auction. Over time, the original auction algorithm ^[18] was extended to solve a wide variety of network optimization problems with linear and convex costs (see the tutorial survey ^[19] and the book ^[20]). Among others, auction algorithms have been used widely in optimal transport applications [21,22,23]^[21][22][23] and have been applied to the training of machine learning models [24,25,26]^[24][25][26]. One paper ^[27] considered the classical shortest path problem and proposed an adaptation of the original auction algorithm, which bears similarity with the path construction algorithms recently proposed in ^[11] and used in the present paper. The more recent algorithms are different in one respect, which is critical for application in knowledge graphs. They allow arbitrary initial prices, making them faster and more suitable for dynamic environments involving a changing knowledge graph topology and queries. In particular, this property allows for the reuse of prices from one query to another similar query through an ongoing “price learning” process which can significantly improve computational efficiency, and ourthe computational experiments have also confirmed this. Thus, the “learned prices” can improve computational efficiency, and contrary to the Dijkstra-like path-based algorithms, they can adapt well to an evolving knowledge graph environment and continuously learn as new entities emerge.

5. Auction Path Construction (APC) Algorithms in KG for Question-Answering

Auction algorithms use a price mechanism to guide the search for a solution. The algorithms efficiently emulate the search process, guided by some rules for price updates. Intuitively, the algorithms can be visualized in terms of a mouse moving in a graph-like maze to reach the destination. The mouse advances from high-price to low-price nodes, going from a node to a downstream neighbor node only if that neighbor has a lower price (or equal price under some conditions). It backtracks when it reaches a node whose downstream neighbors have higher prices. In such a case, it suitably increases the price of that node, thus marking the node as less desirable for future exploration and finding alternative paths to the destination. The auction algorithms provide full traceable paths and not just the single entity answer score. The full path can give the user a logical inference for the queries requiring multihop reasoning. Thus, the final answer constructed using ourthe method is interpretable and provides an explainable answer. In particular, weresearchers can leverage the knowledge graph path relations, entity metadata, and attributes to add semantic information to the paths constructed by the auction algorithms. To answer the queries wresearchers traverse directly through the knowledge graph. WeResearchers first parse the query to extract the entities. WeThey then map the entities to find the closest matching entity in the knowledge graph and obtain the attributes of each entity from the entity metadata in the knowledge graph. In the subsequent step, weresearchers use the auction path construction algorithm to acquire the path from the source to the destination entity. In the final step, weresearchers construct an answer by mapping the attributes of all the entities in the path. The process can be used for single and multiple destination and multi-hop queries. OurThe method does not require structured query processing languages or training a model on a static knowledge base to answer the questions.  The node prices play a significant role in the search process. The node prices act as a “guide” for the algorithm and “steer” it toward nodes with lower prices, which are more likely to be part of the solution. APC provides the flexibility to use arbitrary prices. Initially, zeros or random values can be used as the starting prices for the nodes in the graph. In successive runs, prices from the previous run can be reused. Reusing the prices is similar to learning from previous experiences. For subsequent similar queries, the “experience” in terms of “learned prices” helps produce the path faster, making the algorithm computationally efficient. Eventually, the algorithm can learn favorable starting prices to generate paths faster. Given the dynamic and incomplete nature of the knowledge graphs, newly emerging relations and entities are added, and redundant ones are removed, resulting in constant changes in the graph structure. The auction algorithms are well-suited to this kind of dynamic environment. They are flexible as the node prices are initially assigned arbitrary values and updated dynamically. APC returns a complete path between the entities in question. The paths are traceable and can be inferred by mapping the entity attributes. Also the number of iterations reduces significantly by reusing the prices for similar queries.  WResearchers also compared ourthe method with the Dijkstra algorithm. Both auction and Dijkstra can be used for finding paths from source to destination, and both have polynomial time complexity. However, auction has two advantages. First, it tends to be faster, mainly because it aims to find any path (which is not guaranteed to be the shortest) rather than the shortest path, as is the case with Dijkstra. Secondly, the auction algorithm generates the prices for future queries, whereas the Dijkstra provides no such information. The auction algorithms can also be used in application contexts to provide recommendations and design flow graphs. One of the applications can be in customer contact centers where the customers call the agents to get help on their bills, payment methods, products, WIFI service, call plans, etc. These agents can be human or virtual assistants. Once the call intent or the named entities are extracted from the customer query and given the endpoints, the algorithm can provide the full path to the troubleshooting steps for the agents to resolve customer tickets quickly.