Advancements in �Knowledge Graph Reasoning

Innovative Approaches to Complex Logical Query Answering�and Logical Hypothesis Generation

Jiaxin Bai

KnowComp, Department of CSE�The Hong Kong University of Science and Technology

Jiaxin Bai, KnowComp, HKUST

1

4/8/2025

Roadmap

• Background
• Complex Query Answering
• Complex Hypothesis Generation
• Complex Session Intension Understanding
• Future Work

​

Jiaxin Bai, KnowComp, HKUST

2

4/8/2025

Limitations of Current AI Systems

• LLMs struggle with hallucinations in complex reasoning

​

Jiaxin Bai, KnowComp, HKUST

3

4/8/2025

Limitations of Current AI Systems

• Vector DBs focus on document similarity, not logical queries
• Need for deeper inference and structured knowledge

​

Jiaxin Bai, KnowComp, HKUST

4

4/8/2025

Need Grounded Reasoning on Structured Data!

For example a knowledge graph

Structured Knowledge: Knowledge Graphs

G consisting of:

• Entities (nodes) E: objects, concepts, or ideas
• Relation types (edge labels) R: associations between entities
• Triples (e_h, r, e_t) ∈ G: head and tail entities connected by a relation

​

5

4/8/2025

How to use KG for Reasoning?

• How to answer knowledge graph queries on different types of knowledge graphs given the graphs are always incomplete?

Complex Query Answering

• How to obtain logical hypothesis from observations by using structured knowledge?

Logical Hypothesis Generation

• How to apply the KG reasoning to real e-commerce application like search and recommendation?

Complex Session Intension Understanding

​

​

Jiaxin Bai, KnowComp, HKUST

6

4/8/2025

Roadmap

• Background
• Complex Query Answering
• Complex Hypothesis Generation
• Complex Session Intension Understanding
• Future Work

​

​

Jiaxin Bai, KnowComp, HKUST

7

4/8/2025

Complex Query Answering

How do we deal with the incompleteness of KG?

​

How do we scale up to large knowledge graphs and long queries?

​

8

Query Encoding

How do we deal with the incompleteness of KG?

Use embeddings to represent queries and subqueries

How do we scale up to large knowledge graphs and long queries?

Using computation to replace graph search / subgraph matching

Only a single approximate nearest neighbor search in inference

​

​

9

Turing

Award

Canada

HasWinner

Intersection

HasCitizen

HasWinner

Neural Query Encoders

10

https://github.com/neuralgraphdatabases/awesome-logical-query

Figures from [1]

Figures from [2]

Figures from [3]

Query2Particles: Knowledge Graph Reasoning with Particle Embeddings

Jiaxin Bai, Zihao Wang, Hongming Zhang, Yangqiu Song

NAACL-2022 (Findings)

Jiaxin Bai, KnowComp, HKUST

11

4/8/2025

Embedding Space and Set Representations

Jiaxin Bai, KnowComp, HKUST

12

4/8/2025

Computation Graph

The multi-hop logical operations make the query answers diversified

The answers embeddings are set(s) scattered in the embedding space

Example from: Jiaxin Bai, Zihao Wang, Hongming Zhang, Yangqiu Song: Query2Particles: Knowledge Graph Reasoning with Particle Embeddings. NAACL-HLT (Findings) 2022: 2703-2714

Relational Projection

Jiaxin Bai, KnowComp, HKUST

13

4/8/2025

Relational Projection

Intersection, Union, and Negation

Jiaxin Bai, KnowComp, HKUST

14

4/8/2025

Intersection

Complement

Union

Training Query2Particles

Jiaxin Bai, KnowComp, HKUST

15

4/8/2025

Dataset

Jiaxin Bai, KnowComp, HKUST

16

4/8/2025

The basic information about the three knowledge graphs used for the experiments.

The detailed information for the queries used for training, validating, and testing all query embedding methods.

Training Query2Particles

Jiaxin Bai, KnowComp, HKUST

17

4/8/2025

2p

1p

3p

2i

3i

2in

3in

inp

pni

pin

ip

pi

2u

up

n

n

n

n

n

u

u

In-distribution types

Out-of-distribution types

p: projection

i: intersection

n: negation

u: union

In-distribution: used for training and evaluation

Out-of-distribution: no training, evaluation only

Comparison with baselines

• There is no need to pre-process the queries to their disjunction-normal forms (DNF), which takes exponential complexity
• Fast inference speed compared to the query decomposition method

18

Queries with Diverse Answers

19

MRR on the top ten percent diversified queries

Diversity is measured by the number of answers.

Significantly better on the queries with diverse answers

Sequential Query Encoding For Complex Query Answering on Knowledge Graphs

Jiaxin Bai*, Tianshi Zheng*, Yangqiu Song

Transactions of Machine Learning Research

Jiaxin Bai, KnowComp, HKUST

20

4/8/2025

Neural Networks as Operators

Jiaxin Bai, KnowComp, HKUST

21

4/8/2025

Interact

Mad Cow Disease

Alzheimer’s Disease

Union

Assoc

Answers

Assoc

From a query to a computation graph

Do we have to parameterize and then execute such computational graph?

From Computing to Encoding

• Previous: neural networks as operators, then execute the graph

​

• SQE: tokenize & encode the whole query graph by a single NN

​

​

​

​

Jiaxin Bai, KnowComp, HKUST

22

4/8/2025

[(] [P] [Interact]

[(] [U]

[(] [P] [Assoc] [MadCow] [)]

[(] [P] [Assoc] [Alzheimer ] [)]

[)]

[)]

Interact

Mad Cow Disease

Alzheimer’s Disease

Union

Assoc

Answers

Assoc

Tokenization

Sequential Query Encoding

Jiaxin Bai, KnowComp, HKUST

23

4/8/2025

Sequence Encoder

[(] [P] [Interact] [(] [U] [(] [P] [Assoc] [MadCow] [)] [(] [P] [Assoc] [Alzheimer] [)] [)] [)]

[Melanin]

E_[(]

E_[P]

E_[(]

C

E_[U]

E_[(]

E_[Interact]

​

E_[P]

E_[Assoc]

​

E_[MadCow]

​

…

…

​

E_[)]

E_[(]

E_[P]

E_[Assoc]

​

E_[Alzheimer]

​

E_[)]

E_[)]

E_[)]

Sequence Encoder: Transformers, LSTMs, Temporal CNN…

Experiments - Benchmarks

Jiaxin Bai, KnowComp, HKUST

24

4/8/2025

We construct a larger benchmark with diverse query types.

Results

Jiaxin Bai, KnowComp, HKUST

25

4/8/2025

The operator-level parametrization is good for compositional generalization

for unseen query types

Sequential query encoding is good for the queries when its query types are seen

Knowledge Graph Reasoning over Entities and Numerical Values

Jiaxin Bai, Chen Luo, Zheng Li, Qingyu Yin, Bing Yin, Yangqiu Song

KDD-2023

Jiaxin Bai, KnowComp, HKUST

26

4/8/2025

Numerical Complex Query Answering

Jiaxin Bai, KnowComp, HKUST

27

4/8/2025

Interpretations

Complex Queries

Category

Number Reasoning Network

Jiaxin Bai, KnowComp, HKUST

28

4/8/2025

Find the cities that have a higher latitudes than Japanese cities.

(1) Relational

Projection

(2) Attribute

Projection

(3) Numerical

Projection

(4) Reverse

Attribute Projection

Jiaxin Bai, Chen Luo, Zheng Li, Qingyu Yin, Bing Yin, Yangqiu Song: Knowledge Graph Reasoning over Entities and Numerical Values. KDD 2023: 57-68

Main Results on Three KGs

Jiaxin Bai, KnowComp, HKUST

29

4/8/2025

Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints

Jiaxin Bai, Xin Liu, Weiqi Wang, Chen Luo, Yangqiu Song

NeurIPS-2023

Jiaxin Bai, KnowComp, HKUST

30

4/8/2025

31

https://github.com/HKUST-KnowComp/ASER

Hongming Zhang, Xin Liu, Haojie Pan, Yangqiu Song, Cane Wing-Ki Leung: ASER: A Large-scale Eventuality Knowledge Graph. WWW 2020: 201-211

Katz, J. J., & Fodor, J. A. (1963). The structure of a semantic theory. Language, 39(2), 170–210.

Yorick Wilks. 1975. An intelligent analyzer and understander of English. Communications of the ACM, 18(5):264–274.

Principle 1: Comparing semantic meanings by fixing grammar (Katz and Fodor, 1963)

Principle 2: The need of language inference based on ‘partial information’ (Wilks, 1975)

CQA on Eventuality Knowledge Graph

Jiaxin Bai, KnowComp, HKUST

32

4/8/2025

Complex query on eventuality graphs are different from the entity-relation graph

Whether and when the eventualities occur are important

Interpretations

Type

Queries

Jiaxin Bai, Xin Liu, Weiqi Wang, Chen Luo, Yangqiu Song: Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints. NeurIPS, 2023

Query Encoding with Constraint Memory

Jiaxin Bai, KnowComp, HKUST

33

4/8/2025

V_?

PersonX

complains

PersonX leaves

restaurant

Succession

PersonY

adds ketchup

Computational Graph

Constraint Memory

Food is bad

…

Precedence

ChosenAlter.

PersonY

adds vinegar

PersonY

adds soy sauce

…

…

Key

Value

Succession

Intersection

Reason

(1)

(2)

(3)

Jiaxin Bai, Xin Liu, Weiqi Wang, Chen Luo, Yangqiu Song: Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints. NeurIPS, 2023

The MEQE Combined with Various QE methods

Jiaxin Bai, KnowComp, HKUST

34

4/8/2025

Roadmap

• Background
• Complex Query Answering
• Complex Hypothesis Generation
• Complex Session Intension Understanding
• Future Work

​

​

​

Jiaxin Bai, KnowComp, HKUST

35

4/8/2025

Advancing Abductive Reasoning in Knowledge Graphs through Complex Logical Hypothesis Generation

Jiaxin Bai*, Yicheng Wang*, Tianshi Zheng, Yue Guo, Xin Liu, Yangqiu Song

ACL-2024

Jiaxin Bai, KnowComp, HKUST

36

4/8/2025

Abductive Reasoning

• Abductive reasoning is a form of reasoning that seeks to find the best explanation for an observation, distinct from the other two major types of inference: deduction and induction.

​

• Abductive Reasoning on KG:

To use structured knowledge in KG to explain observations.

Jiaxin Bai, KnowComp, HKUST

37

4/8/2025

Abductive Reasoning

• Abductive Reasoning on KG:

To use structured knowledge in KG to explain observations.

Jiaxin Bai, KnowComp, HKUST

38

4/8/2025

Tokenization of Hypothesis

Jiaxin Bai, KnowComp, HKUST

39

4/8/2025

Tokens : [I][I][Brand][Apple]

[Release][2010][N][Type][Phone]

Complex Logical Hypothesis Generation

Jiaxin Bai, KnowComp, HKUST

40

4/8/2025

Step 1:

Sample observation-hypothesis pairs.

Observations

Hypotheses

KG:

Complex Logical Hypothesis Generation

Jiaxin Bai, KnowComp, HKUST

41

4/8/2025

Observation

Step 3:

Optimize hypothesis generation model with Reinforcement Learning From Knowledge Graph feedback (RLF-KG).

Dataset

Jiaxin Bai, KnowComp, HKUST

42

4/8/2025

This figure provides basic information about the three knowledge graphs utilized in our experiments. The graphs are divided into standard sets of training, validation, and testing edges to facilitate the evaluation process.

The detailed information about the queries used for training, validation, and testing.

Performance

Jiaxin Bai, KnowComp, HKUST

43

4/8/2025

Real Examples:

Jiaxin Bai, KnowComp, HKUST

44

4/8/2025

Jiaxin Bai, KnowComp, HKUST

45

4/8/2025

Output from Supervised Training:

Output after RLF-KG Training:

Roadmap

• Background
• Complex Query Answering
• Complex Hypothesis Generation
• Complex Session Intension Understanding
• Future Work

​

​

​

Jiaxin Bai, KnowComp, HKUST

46

4/8/2025

Understanding Inter-Session Intentions via Complex Logical Reasoning

Jiaxin Bai, Chen Luo, Zheng Li, Qingyu Yin, Yangqiu Song

KDD-2024

Jiaxin Bai, KnowComp, HKUST

47

4/8/2025

Search with Logic is Hard

• Search products with complex requirements is hard.
• Particularly hard for requirements like NOT.

48

4/8/2025

Search with hidden intentions from sessions

• Intentions can be hidden and implicit, not always from keywords.
• We need to use behaviour data, like session information, to model intentions.

​

• Often people do a single decision across multiple sessions.
• People may search and spend multiple sessions before making a big decision ,like buying a smartphone or a fridge.
• If a person buy a mattress in a previous session, he is not likely to buy another one, but a bed frame.

​

• We need a complex logic reasoning across sessions.
• Find the desired item of a session with the brand Nike or Adidas
• Find the desired item with wooden material that is desired by the session₁ but is not desired by session₂.
• Dealing with sessions, attributes, and logics in one.

49

4/8/2025

Integrating sessions, attributes, and logics

For Product Recommendation

​

​

50

4/8/2025

Find next item of a given session

Find an item with the brand Nike

Find an item with the brand Adidas or Nike

Or

Find an item with the brand Adidas

Find the next item of a session with the brand Nike or Adidas

And

Find the next item of a session with the brand Nike or Adidas

Logical Session-CQA on Hypergraph

• Sessions are treated as hyperedges.
• Other attributes and relations are treated as binary edges.

51

4/8/2025

(A) Hypergraph

(B) Hyper-Relational KG

Discovered By

Albert

Einstein

Photoelectric

Effect

Educated At

Degree: BSc

ETH

Zurich

(C) Hyper Session Graph

Item₁ Item₂ Item₃ Item₄

Session₁

Red

Blue

Nike

Adidas

Brand

Colour

Brand

Colour

Brand

Session₂

Hyperedge₁

Hyperedge₂

CQA Methods for Inter-Session Logic Reasoning

52

N-ary QE methods

StarQE [1] and NQE [2] are designed for hyper-relational KG, difficult to be adopted to session graphs.

​

SQE [3] can be extended to N-ary quires, but it cannot capture some important aspects of query graph, like permutation invariance in AND and OR.

Session Encoders + Logic Encoders

When doing logic reasoning, the logic encoder can only access session embedding but not the detailed items in the session in the reasoning process.

Brand

Intersection

Next

Next

[(] [P] [Brand]

[(] [I]

[(] [P] [Next] [(] [S] [Item_1,1] … [Item_1,m] [)] [)]

[(] [P] [Next] [(] [S] [Item_2,1] … [Item_2,n-1] [Item_2,n] [)] [)]

[)]

[)]

Need a new query encoding method on session hypergraph

[1] Dimitrios Alivanistos, Max Berrendorf, Michael Cochez, Mikhail Galkin: Query Embedding on Hyper-Relational Knowledge Graphs. ICLR 2022

[2] Haoran Luo, Haihong E, Yuhao Yang, Gengxian Zhou, Yikai Guo, Tianyu Yao, Zichen Tang, Xueyuan Lin, Kaiyang Wan: NQE: N-ary Query Embedding for Complex Query Answering over Hyper-Relational Knowledge Graphs. AAAI 2023

[3] Jiaxin Bai, Tianshi Zheng, Yangqiu Song: Sequential Query Encoding for Complex Query Answering on Knowledge Graphs. Trans. Mach. Learn. Res. 2023 (2023)

​

Logical-Session Graph Transformer

• v_i are product items
• S_i are sessions
• P_i are projection operators
• I_i are intersection operators
• U_i are union operators
• N_i are negation operators

53

4/8/2025

​

​

​

Query Graph

​

​

Find the item that is desired by the session₁ and desired by session₂.

Logical-Session Graph Transformer

54

4/8/2025

Brand

Intersection

Next

Next

S₂

S₁

I₁

P₂

P₁

P₃

v₁

v₂

v₃

v₂

v₃

v₄

Query Graph

​

​

Node identifiers (from 0 to 9) are assigned to each node, involving items, sessions, and operators in the graph

v₁

v₂

v₃

v₄

S₁

S₂

P₁

P₂

P₃

I₁

1

2

3

4

5

6

7

8

9

0

Logical-Session Graph Transformer

55

4/8/2025

Transformer Encoder

[Predictions]

Type

Identifiers:

v

[node]:

[edge]:

e

Logical-Session Graph Transformer

• Permutation Invariant to Logical Operators.
• Sensitive to Item-order in Session.
• Specialised Token Graph Transformer [1] for encoding query graph

56

4/8/2025

Brand

Intersection

Next

Next

Transformer Encoder

S₂

S₁

I₁

P₂

P₁

P₃

v₁

v₂

v₃

v₂

v₃

v₄

Node

Identifiers:

v₁

v₂

v₃

v₄

S₁

S₂

P₁

P₂

P₃

I₁

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

6

7

8

9

0

1

2

3

4

5

6

7

8

9

0

[2]

1

2

0

4

4

4

1

2

3

5

5

5

4

6

5

7

6

9

7

9

9

8

[g]

[v₁]

[v₂]

[v₃]

[v₄]

[S]

[S]

[P]

[P]

[P]

[I]

[1]

[3]

[2]

[1]

[3]

[Next]

[Next]

[I]

[I]

[Brand]

v

v

v

v

v

v

v

v

v

v

e

e

e

e

e

e

e

e

e

e

e

Items and Operators

Sessions Structures

Logical Structures

[Predictions]

Type

Identifiers:

v

[node]:

[edge]:

e

(A)

(B)

(C)

[1] Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, Seunghoon Hong: Pure Transformers are Powerful Graph Learners. NeurIPS 2022

Experiment Dataset

• Diginetica Dataset
• The Diginetica dataset is commonly used in session-based recommendation research. It originates from the CIKM Cup 2016, focusing on e-commerce applications. The dataset contains user sessions, item interactions, and transaction information.
• Dressipi Dataset
• The Dressipi dataset is a fashion-oriented dataset designed for personalized recommendation systems. It comes from the clothing and fashion domain, making it relevant for session-based recommendations in retail.
• Amazon M2 Dataset
• The Amazon M2 dataset (KDD Cup 2023) focuses specifically on user sessions and interactions with products, making it suitable for session-based and sequential recommendation tasks. The dataset is often used in research on e-commerce platforms to enhance recommendations by modeling user behavior over time.

​

57

4/8/2025

Experiment Dataset

58

4/8/2025

59

4/8/2025

1p

2p

3i

2iA

2iS

ip

pi

2uS

up

2inS

2inA

inp

pin

3in

3iA

u

u

n

n

n

n

n

3ip

3inA

n

3inp

n

Zero-shot Types:

Supervised Training Types:

Experiment Results

60

4/8/2025

Existential Positive First Order (EPFO): queries types that involves conjunction, disjunction, and variables are existential quantified. No negations.

​

Out-of-Distribution Queries Results

61

4/8/2025

OOD query types: queries types that are not trained during the training phrase.

As their sub-queries are trained, we can use this as a measure of compositional generalization.

Roadmap

• Background
• Complex Query Answering
• Complex Hypothesis Generation
• Session Intension Modeling by Logic
• Future Work

​

​

​

Jiaxin Bai, KnowComp, HKUST

62

4/8/2025

Future Work: Neural Graph Database

Jiaxin Bai, KnowComp, HKUST

63

4/8/2025

Text Data

Database Data

Neural Graph Database

🡪 Database Foundation Model

Large Language Model

[1] https://youtu.be/1yvBqasHLZs

[2] Wang, Y., Wang, X., Gan, Q., Wang, M., Yang, Q., Wipf, D., & Zhang, M. (2025). Griffin: Towards a Graph-Centric Relational Database Foundation Model. arXiv preprint arXiv:2505.05568.

[2]

Ilya Sutskever [1]

​

LLM Pre-training scaling will stop

because we only have one internet!

• Data within databases continues to grow and won't be easily depleted;
• At very early stage where universities can do research [2];
• Combines general applicability to real-world applications, positioning it to make industry impact.

Neural Graph Database (NGDB) show great potential to scale to Database Foundation Model!

Future Work – Agentic Database

• Ask the “correct” question on behalf of the user based on a context
• The future direction for abductive reasoning and beyond
• Conduct approximation and inferences given various typed data
• The future direction for complex logical query answering
• Integrate results on behalf of the user and present to them
• The future direction for KG reasoning together with the LLMs

​

​

Jiaxin Bai, KnowComp, HKUST

64

4/8/2025

Language Modeling via Next Token Prediction:

We would like to invite esteemed senior professors who have made significant contributions to computer science to give a talk on-site. To accommodate them, we have decided to hold the seminar in ________

…… we have decided to hold the seminar in __Toronto__.

Thank you for your attention! ☺�More related work on my website:�bjx.fun�

66