Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs

Shengyuan ChenYunfeng CaiHuang FangXiao HuangMingming Sun

article2023NeurIPS51 citations

Proposes DiffLogic, an end-to-end differentiable neuro-symbolic framework that integrates continuous probabilistic soft logic with knowledge graph embeddings and an efficient rule-grounding mechanism to enable scalable, accurate reasoning on large-scale knowledge graphs.

Listen

Large-scale knowledge graphs are critical across modern enterprise applications, including search engines, recommendation systems, and automated question answering. However, extracting missing facts from these networks presents a persistent operational challenge. Existing methods generally force a trade-off: traditional rule-based reasoning offers high interpretability and logical precision but collapses under the computational weight of large datasets, whereas data-driven embedding models scale well but lack logical guarantees, require massive training sets, and produce opaque inferences. Prior neuro-symbolic systems that attempt to merge these approaches have suffered from severe computational bottlenecks and optimization inconsistencies, restricting their real-world utility.

The article demonstrates and evaluates a unified neuro-symbolic framework called DiffLogic. The primary objective is to enable scalable, end-to-end differentiable reasoning across large knowledge graphs by effectively marrying the scalability of embedding models with the logical precision and uncertainty management of rule-based logic.

To achieve this, the researchers integrated continuous probabilistic soft logic with knowledge graph embeddings, utilizing an alternating optimization algorithm that iteratively updates entity representations and dynamically adjusts rule confidence weights. The framework introduces a specialized iterative grounding filter that identifies only the most essential logical rule instances, alongside a fast gradient estimation technique that exploits the mathematical sparsity of rule violations. The approach was evaluated across standard real-world benchmarks (such as CodeX, WN18RR, and the 120,000-entity YAGO3-10) and synthetic relational datasets, benchmarking against diverse embedding baselines, graph neural networks, and rule-learning systems.

The findings show that DiffLogic consistently outperforms both pure embedding methods and rule-based systems across link prediction tasks, achieving top-tier accuracy metrics (e.g., reaching 0.513 Mean Reciprocal Rank on YAGO3-10). The framework successfully scaled to large datasets where traditional rule-based baselines failed to complete inference within ten-hour execution limits. Additionally, the iterative grounding mechanism reduced the volume of required instantiated formulas by a factor of 1,000 to 100,000 without degrading predictive accuracy, completing full grounding on the largest dataset in roughly 3.2 seconds using only 263 megabytes of memory. Furthermore, controlled experiments revealed that injecting a small set of explicit rules allowed DiffLogic to achieve near-optimal performance (0.954 MRR) immediately, whereas data-driven embedding models required extensive data exposure to approach comparable accuracy.

These results establish that embedding models and logical rules can be co-optimized without prohibitive computational overhead. Operationally, this enables organizations to dramatically cut data labeling costs and model training times by embedding human domain knowledge directly as initial logical rules. DiffLogic also reduces system risk by producing inferences that remain grounded in verifiable logical statements rather than unconstrained statistical correlations.

Organizations handling large relational data graphs should consider adopting continuous neuro-symbolic architectures when logical consistency and explainability are critical. Teams can transition to using compact rule sets (with premise lengths of two or fewer) rather than maintaining fragile, exhaustive rule repositories. As a next step, development efforts should investigate integrating automatic, end-to-end rule mining algorithms into the training pipeline to reduce dependence on manual rule engineering or third-party extraction tools.

Confidence in these findings is supported by consistent performance gains across multiple established benchmarks. However, stakeholders should note that the framework's effectiveness relies fundamentally on the initial quality and coverage of the provided candidate rules. In addition, extended grounding iterations can accumulate noisy, low-scoring facts, suggesting that production deployments should apply confidence thresholding via pre-trained embedding filters to maintain optimal inference speed.

Baidu Hong Kong Polytechnic University reasoning bipartite graphs knowledge graph embedding differentiable neuro-symbolic reasoning large-scale knowledge graphs rule-based reasoning

Chen et al (2023).pdf

Paper: Markov logic networks, Matthew Richardson et al. (2006). Introduces Markov Logic Networks, establishing the foundational principles of continuous probabilistic soft logic and weighted first-order formulas that DiffLogic builds upon for neuro-symbolic reasoning.
Paper: Neural-Symbolic Models for Logical Queries on Knowledge Graphs, Zhaocheng Zhu et al. (2022). Pioneers continuous fuzzy logic operations combined with neural representations on incomplete knowledge graphs, providing direct conceptual context for DiffLogic's differentiable reasoning framework.
Paper: A Review of Relational Machine Learning for Knowledge Graphs, Maximilian Nickel et al. (2015). Surveys the interplay between latent embedding models and explicit relational rule learning on large-scale knowledge graphs, outlining the key trade-offs DiffLogic unifies.
Paper: Complex Embeddings for Simple Link Prediction, Théo Trouillon et al. (2016). Establishes standard knowledge graph embedding formulations for relational link prediction benchmarks like WN18 and FB15k used in DiffLogic's evaluation.
Paper: Modeling Relational Data with Graph Convolutional Networks, Michael Schlichtkrull et al. (2018). Provides the foundational message-passing architecture (R-GCN) for multi-relational knowledge graphs that serves as a core baseline for graph-based neural reasoning.
Paper: A Survey on Knowledge Graphs: Representation, Acquisition, and Applications, Shaoxiong Ji et al. (2020). Delivers a comprehensive overview of knowledge graph representation learning, completion, and rule-based inference methods addressed and integrated by the source.
Paper: The DLV system for knowledge representation and reasoning, Nicola Leone et al. (2002). Presents industrial-strength declarative logic programming and grounding mechanisms, contextualizing the computational grounding bottlenecks DiffLogic overcomes via iterative filtering.

Paper: Efficient Rectification of Neuro-Symbolic Reasoning Inconsistencies by Abductive Reflection, Wen-Chao Hu et al. (2025). Extends scalable neuro-symbolic inference by introducing abductive reflection to efficiently detect and rectify rule inconsistencies between neural predictions and symbolic constraints.
Paper: Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts, Emanuele Marconato et al. (2023). Analyzes and mitigates reasoning shortcuts in neuro-symbolic systems where models satisfy logical constraints while learning incorrect intermediate semantics.
Paper: Interpretable Neural-Symbolic Concept Reasoning, Pietro Barbiero et al. (2023). Builds on differentiable neuro-symbolic concepts by formulating explicit logic rules over high-dimensional embeddings while evaluating them on interpretable truth values.
Paper: Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs, Liyi Chen et al. (2024). Applies multi-hop structural graph reasoning to dynamic planning and self-correcting exploration over large knowledge graphs using language models.
Paper: Unifying Large Language Models and Knowledge Graphs: A Roadmap, Shirui Pan et al. (2023). Roadmaps the broader integration of structured knowledge graphs with neural architectures and language models for bidirectional factual reasoning.

Cover for Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs

Abstract

Knowledge graph (KG) reasoning utilizes two primary techniques, i.e., rule-based and KG-embedding based. The former provides precise inferences, but inferring via concrete rules is not scalable. The latter enables efficient reasoning at the cost of ambiguous inference accuracy. Neuro-symbolic reasoning seeks to amalgamate the advantages of both techniques. The crux of this approach is replacing the predicted existence of all possible triples (i.e., truth scores inferred from rules) with a suitable approximation grounded in embedding representations. However, constructing an effective approximation of all possible triples’ truth scores is a challenging task, because it needs to balance the tradeoff between accuracy and efficiency, while compatible with both the rule-based and KG-embedding models. To this end, we proposed a differentiable framework - DiffLogic. Instead of directly approximating all possible triples, we design a tailored filter to adaptively select essential triples based on the dynamic rules and weights. The truth scores assessed by KG-embedding are continuous, so we employ a continuous Markov logic network named probabilistic soft logic (PSL). It employs the truth scores of essential triples to assess the overall agreement among rules, weights, and observed triples. PSL enables end-to-end differentiable optimization, so we can alternately update embedding and weighted rules. On benchmark datasets, we empirically show that DiffLogic surpasses baselines in both effectiveness and efficiency.

Topics

reasoning bipartite graphs knowledge graph embedding

Keywords

differentiable neuro-symbolic reasoning large-scale knowledge graphs rule-based reasoning knowledge base completion probabilistic logic reasoning multi-hop reasoning differentiable rule mining soft logic KG-embedding models

1 Introduction
2 Preliminaries
2.1 Problem statement
2.2 First-order logic
2.3 Rule grounding and distance to satisfaction
3 Differentiable neuro-symbolic reasoning
3.1 Overall framework
3.2 Optimization
4 Experiments
4.1 Reasoning on real-world knowledge graphs
4.2 Scalability of optimization
4.3 Learning from data vs. learning from rules
5 Related work
6 Conclusion
References
A Notations and mathematical proofs
A.1 Notations
A.2 Derivation of rule weight gradient
A.3 Calculation of number of ground formulas for Kinship datasets
B Experimental details
B.1 Dataset statistics
B.2 Probabilistic logic reasoning on Kinship Dataset
B.3 Comparing inference time on Kinship

Knowls

Knowl 1 — Hinge-Loss Markov Random Field Formulation in DiffLogic
model/method
DiffLogic models the joint distribution of knowledge graph (KG) facts and logical rules by framing reasoning within a continuous Hinge-Loss Markov Random Field (HL-MRF) derived from Probabilistic Soft Logic (PSL).

Let $\mathcal{K} = (\mathcal{E}, \mathcal{R})$ be a knowledge base with entity set $\mathcal{E}$ and relation set $\mathcal{R}$ . Let $\mathcal{O} = \{(h_i, r_i, t_i)\}_{i=1}^n$ denote observed facts with continuous truth assignment vector $\mathbf{x} = [x_1, \dots, x_{|\mathcal{O}|}] \in [0, 1]^{|\mathcal{O}|}$ , and $\mathcal{H} = (\mathcal{E} \times \mathcal{R} \times \mathcal{E}) \setminus \mathcal{O}$ denote unobserved candidate facts with assignment vector $\mathbf{y} \in [0, 1]^{|\mathcal{H}|}$ . Rather than maintaining an explicit parameter table of size $O(|\mathcal{E}|^2 |\mathcal{R}|)$ , $\mathbf{x}$ and $\mathbf{y}$ are parameterized by a continuous KG-embedding model (such as RotatE) with parameter set $\theta$ , reducing the parameter complexity to $O(|\mathcal{E}|n_e + |\mathcal{R}|n_r)$ where $n_e$ and $n_r$ are entity and relation embedding dimensions. The truth value of any triple $(h, r, t)$ is computed via $r(h, t; \theta) = \sigma(s(h, r, t))$ , where $s(\cdot)$ is the embedding score function and $\sigma(\cdot)$ is the sigmoid function.

Given a set of $m$ first-order logic rules with non-negative weights $\{(F_q, W_q)\}_{q=1}^m$ , the conditional probability density function over unobserved facts $\mathbf{y}$ given observed facts $\mathbf{x}$ is defined as:

$P_W(\mathbf{y} \mid \mathbf{x}) = \frac{1}{Z(W, \mathbf{x})} \exp(-f_W(\mathbf{y}, \mathbf{x}))$

where $Z(W, \mathbf{x}) = \int_{\mathbf{y}} \exp(-f_W(\mathbf{y}, \mathbf{x})) \, d\mathbf{y}$ is the continuous partition function, and $f_W(\mathbf{y}, \mathbf{x})$ is the hinge-loss energy function defined as:

$f_W(\mathbf{y}, \mathbf{x}) = \mathbf{W}^\top \Phi(\mathbf{y}, \mathbf{x}) = \sum_{q=1}^m W_q \Phi_q(\mathbf{y}, \mathbf{x}) = \sum_{q=1}^m W_q \sum_{j=1}^{n_q} d(G_q^{(j)})$

Here, $\{G_q^{(j)}\}_{j=1}^{n_q}$ is the set of ground formulas generated from rule $F_q$ , and $d(G_q^{(j)}) \in [0, 1]$ represents the distance-to-satisfaction of the $j$ -th ground formula.
Knowl 2 — Distance-to-Satisfaction for Logic Ground Formulas via Łukasiewicz t-Norm
definition
In neuro-symbolic reasoning with Probabilistic Soft Logic, first-order logic rules are evaluated over continuous truth values in the unit interval $[0, 1]$ . Let a first-order logic rule $F_q$ be expressed in implicative clausal form:

$\bigwedge_{i \in I_q^-} r_i(A_i, B_i) \implies \bigvee_{i \in I_q^+} r_i(A_i, B_i)$

where $I_q^-$ and $I_q^+$ are index sets indexing premise (negated in disjunctive normal form) and conclusion (non-negated) atoms respectively, and $A_i, B_i$ are entity variables.

When rule $F_q$ is instantiated by substituting variables with concrete entities, it forms a ground formula $G_q^{(j)}$ . When each ground atom $r_i(h_i, t_i)$ takes a continuous truth score $r_i(h_i, t_i) \in [0, 1]$ , the degree of rule violation is quantified using the Łukasiewicz t-norm relaxation. The distance-to-satisfaction $d(G_q^{(j)})$ is defined as:

$d(G_q^{(j)}) := \max \left( 1 - \sum_{i \in I_q^+} r_i(h_i, t_i) - \sum_{i \in I_q^-} (1 - r_i(h_i, t_i)), \, 0 \right)$

The distance $d(G_q^{(j)})$ lies in the range $[0, 1]$ . A value of $d(G_q^{(j)}) = 0$ indicates that the ground formula is fully satisfied, while larger values indicate higher degrees of violation.
Knowl 3 — Rule-Guided Iterative Grounding (RGIG)
algorithm
Rule-Guided Iterative Grounding (RGIG) is a filtering and grounding procedure designed to identify important ground formulas without exhaustively generating all $\sum_{q=1}^m |\mathcal{E}|^{|I_q^-|+1}$ possible entity substitutions. It exploits the sparsity of violated rules by prioritizing formulas whose premise atoms have high truth values.
Input: Observed facts $\mathcal{O}$ , weighted first-order logic rules $\{(F_q, W_q)\}_{q=1}^m$ , maximum iterations $K$ (typically $K=3$ )
Output: Filtered set of ground formulas $\mathcal{G}$
Initialize active fact set $\mathcal{V} \leftarrow \mathcal{O}$
Initialize ground formula set $\mathcal{G} \leftarrow \emptyset$
for iteration $k = 1$ to $K$ do
    Initialize new fact set $\mathcal{V}_{\text{new}} \leftarrow \emptyset$
    for each rule $F_q = \bigwedge_{i \in I_q^-} r_i(A_i, B_i) \implies \bigvee_{i \in I_q^+} r_i(A_i, B_i)$ do
        Find all entity substitutions $\sigma$ mapping premise atoms to matching facts in $\mathcal{V}$
        for each substitution $\sigma$ matching premises do
            Construct ground formula $G_q = \sigma(F_q)$
             $\mathcal{G} \leftarrow \mathcal{G} \cup \{G_q\}$
            Extract conclusion atoms $C = \sigma(\bigvee_{i \in I_q^+} r_i(A_i, B_i))$
             $\mathcal{V}_{\text{new}} \leftarrow \mathcal{V}_{\text{new}} \cup C$
        end for
    end for
     $\mathcal{V} \leftarrow \mathcal{V} \cup \mathcal{V}_{\text{new}}$
end for
return $\mathcal{G}$
RGIG only grounds rules on facts that have already been observed or derived in previous iterations. In practice, setting $K=3$ captures the relevant multi-hop rule paths while reducing the number of ground formulas by factors of $10^3$ to $10^5$ compared to full PSL grounding.
Knowl 4 — Embedding Parameter Optimization Objective (E-Step)
equation
In the E-step of DiffLogic, the rule weights $\mathbf{W} = [W_1, \dots, W_m]^\top$ are fixed, and the knowledge graph embedding parameters $\theta$ are updated to perform Maximum a Posteriori (MAP) inference over the HL-MRF while simultaneously fitting observed positive and negative triples.

The embedding optimization problem is formulated as:

$\min_\theta \mathbf{W}^\top \Phi(\mathbf{y}(\theta), \mathbf{x}(\theta)) + \lambda \left( \frac{1}{|T^+|} \sum_{(h,r,t) \in T^+} [1 - r(h, t; \theta)] + \frac{1}{|T^-|} \sum_{(h,r,t) \in T^-} r(h, t; \theta) \right)$

where:
- $\mathbf{x}(\theta)$ and $\mathbf{y}(\theta)$ are continuous truth assignment vectors for observed and unobserved facts parameterized via $\theta$ .
- $\Phi(\mathbf{y}(\theta), \mathbf{x}(\theta)) = [\Phi_1(\mathbf{y}, \mathbf{x}), \dots, \Phi_m(\mathbf{y}, \mathbf{x})]^\top$ , where $\Phi_q(\mathbf{y}, \mathbf{x}) = \sum_{j=1}^{n_q} d(G_q^{(j)})$ is the sum of distances-to-satisfaction for all ground formulas of rule $F_q$ .
- $r(h, t; \theta) \in [0, 1]$ is the predicted truth score of triple $(h, r, t)$ produced by the embedding model.
- $T^+$ is a mini-batch of true observed triples from $\mathcal{O}$ .
- $T^-$ is a set of negative triples constructed by corrupting the entities in $T^+$ .
- $\lambda > 0$ is a regularization hyperparameter balancing logic satisfaction and embedding observation loss.
Knowl 5 — Rule Weight Gradient via Pseudo-Likelihood Optimization (M-Step)
theoretical result
In the M-step of DiffLogic, the embedding parameters $\theta$ are fixed, and the rule weights $\mathbf{W}$ are updated to maximize the likelihood of the HL-MRF. Because calculating the exact partition function gradient $\mathbb{E}_{P_W}[\Phi_q(\mathbf{y}, \mathbf{x})] - \Phi_q(\mathbf{y}, \mathbf{x})$ requires intractable high-dimensional integration over all unobserved facts $\mathbf{y}$ , DiffLogic optimizes the pseudo-likelihood $P_W^*(\mathbf{y} \mid \mathbf{x}) = \prod_{i=1}^n P^*(y_i \mid \text{MB}(y_i), \mathbf{x})$ , where $\text{MB}(y_i)$ denotes the Markov Blanket of variable $y_i$ .

The partial derivative of the pseudo-log-likelihood with respect to the weight $W_q$ of rule $F_q$ is given by:

$\frac{\partial \log P_W^*(\mathbf{y} \mid \mathbf{x})}{\partial W_q} = \sum_{i=1}^n \left( \mathbb{E}_{y_i \mid \text{MB}(y_i)} [\Psi_{q, \text{MB}(i)}] - \Psi_{q, \text{MB}(i)} \right)$

where:

$\Psi_{q, \text{MB}(i)} = \sum_{j=1}^{n_q} \mathbf{1}_{\{y_i \to G_q^{(j)}\}} d(G_q^{(j)})$

and $\mathbf{1}_{\{y_i \to G_q^{(j)}\}} = 1$ if variable $y_i$ appears in ground formula $G_q^{(j)}$ , and $0$ otherwise.

The one-dimensional expectation $\mathbb{E}_{y_i \mid \text{MB}(y_i)} [\Psi_{q, \text{MB}(i)}]$ is efficiently estimated using 1D Monte Carlo numerical integration by uniformly sampling $y_i \in [0, 1]$ while holding all other variables fixed. Computational overhead is further reduced by only evaluating ground formulas where premise atoms are predicted positive ( $> 0.5$ ) and conclusion atoms are predicted negative.
Knowl 6 — Joint Inference Combining Embedding Scores and Cumulative Rule Weights
equation
During inference in DiffLogic, predictions for a target triple $(h_i, r_i, t_i)$ can be computed either purely through the learned embedding score $r_i(h_i, t_i; \theta) \in [0, 1]$ or through joint inference combining embedding scores with explicit rule derivations.

The cumulative rule score $f_{\text{rule}}(h_i, r_i, t_i; \mathbf{W})$ sums the weights of all ground formulas that logically derive $(h_i, r_i, t_i)$ :

$f_{\text{rule}}(h_i, r_i, t_i; \mathbf{W}) = \sum_{q=1}^m W_q \sum_{j=1}^{n_q} \mathbf{1}_{\{r_i(h_i, t_i) \text{ can be inferred by } G_q^{(j)}\}}$

The combined truth score $r_i(h_i, t_i)$ is computed via convex combination:

$r_i(h_i, t_i) = (1 - \eta) \cdot r_i(h_i, t_i; \theta) + \eta \cdot \hat{f}_i(h_i, t_i; \mathbf{W})$

where $\hat{f}_i(h_i, t_i; \mathbf{W})$ is the min-max normalized value of $f_{\text{rule}}(h_i, r_i, t_i; \mathbf{W})$ scaled into $[0, 1]$ , and $\eta \in [0, 1]$ is a weighting hyperparameter tuned on the validation set.

Knowl 7 — Link Prediction Performance Comparison on Real-World Knowledge Graphs

data/table

The link prediction performance of DiffLogic (using only embedding scores) and DiffLogic+ (using joint rule and embedding scores) was evaluated against embedding-based models (MLP, RotatE, TuckER, TransE), GNN models (SACN, CompGCN), rule-learning models (AMIE, NeuraLP, DRUM, RNNLogic+, RLogic+), a discrete MLN engine (MLN4KB), and a neuro-symbolic MLN baseline (pLogicNet). Candidate rules for DiffLogic were mined using AMIE3 with rule body lengths $\le 2$ .

	CodeX-s		CodeX-m		CodeX-l		WN18RR		YAGO3-10
	MRR	hit@10	MRR	hit@10	MRR	hit@10	MRR	hit@10	MRR	hit@10
MLP	0.279	0.502	0.197	0.347	0.190	0.339	0.139	0.218	0.365	0.575
RotatE	0.421	0.634	0.325	0.466	0.319	0.453	0.469	0.566	0.495	0.670
TuckER	0.444	0.638	0.328	0.458	0.309	0.430	0.470	0.526	-	-
TransE	0.353	0.607	0.320	0.481	0.308	0.452	0.218	0.510	0.436	0.647
SACN	-	-	-	-	-	-	0.470	0.540	-	-
CompGCN	-	-	-	-	-	-	0.479	0.546	-	-
AMIE	0.195	0.283	0.063	0.095	0.026	0.029	0.360	0.485	0.250	0.343
NeuraLP	0.290	0.395	NA	NA	NA	NA	0.433	0.566	NA	NA
DRUM (T=2)	0.290	0.393	NA	NA	NA	NA	0.434	0.565	NA	NA
DRUM (T=3)	0.342	0.542	NA	NA	NA	NA	0.486	0.586	NA	NA
RNNLogic+	-	-	-	-	-	-	0.510	0.597	NA	NA
RLogic+	-	-	-	-	-	-	0.520	0.604	0.530	0.703
MLN4KB	0.082	0.134	0.035	0.045	0.028	0.032	0.368	0.374	0.460	0.525
pLogicNet	0.342	0.505	0.306	0.448	0.270	0.388	0.440	0.534	0.387	0.595
DiffLogic	0.445	0.662	0.335	0.487	0.326	0.448	0.493	0.585	0.503	0.673
DiffLogic+	0.458	0.655	0.343	0.495	0.337	0.460	0.500	0.587	0.513	0.674

Key takeaways from these results:

DiffLogic and DiffLogic+ outperform pure embedding methods (e.g., RotatE MRR of 0.421 vs DiffLogic+ 0.458 on CodeX-s) and rule-based baselines across benchmarks.
DiffLogic outperforms pLogicNet consistently; pLogicNet degrades on large graphs (CodeX-l, YAGO3-10) due to false-positive triple pseudo-labeling in its discrete MLN stage.
Rule-based models (NeuraLP, DRUM, RNNLogic) fail to finish inference within 10 hours (marked NA) on large datasets (CodeX-m, CodeX-l, YAGO3-10), whereas DiffLogic scales smoothly to YAGO3-10 (123k entities, 1.08M training triples).

Knowl 8 — Grounding Overhead and Efficiency of Rule-Guided Iterative Grounding

empirical result

The Rule-Guided Iterative Grounding (RGIG) technique achieves high computational and memory efficiency during candidate rule generation across real-world and synthetic datasets.

Datasets	CodeX-s	CodeX-m	CodeX-l	WN18RR	YAGO3-10
Run-time (/sec)	$0.03 \pm 0.00$	$0.38 \pm 0.01$	$0.87 \pm 0.04$	$0.54 \pm 0.01$	$3.20 \pm 0.04$
Memory (/MB)	2.19	11.57	25.58	18.73	262.65

On the largest evaluated graph, YAGO3-10 (123,182 entities and 1,079,040 facts), RGIG completes formula grounding in $3.20 \pm 0.04$ seconds and consumes 262.65 MB of memory.

On the synthetic Kinship dataset across five scale configurations (S1 to S5, ranging from 52 to 267 entities), classical full PSL grounding creates between $1.37 \times 10^6$ (S1) and $1.72 \times 10^8$ (S5) ground formulas. RGIG with 3 iterations generates $10^3$ to $10^5$ fewer ground formulas than full PSL while maintaining an AUC-ROC of $0.982 \pm 0.014$ to $0.999 \pm 0.000$ , and reduces inference time on Kinship-S5 from ~32 minutes (PSL) and ~20.2 minutes (ExpressGNN) to ~4 minutes (DiffLogic-RotatE) and ~1.2 minutes (DiffLogic-MLP).

Knowl 9 — Effectiveness of Explicit Rule Pattern Injection versus Implicit Data-Driven Learning

data/table

A rule-pattern re-injection experiment on WN18 evaluated how effectively DiffLogic utilizes compact logical rules compared to pure data-driven KG-embedding baselines. Fourteen rules with confidence $> 0.95$ were mined and deduplicated into 7 compact rules. Triples matching the conclusion parts of these rules were removed from the training set to form a "pattern set", leaving a pure "fact set". Varying ratios (0%, 10%, 20%, 100%) of the pattern set were added back to the training data, while DiffLogic was trained on the fact set with the 7 rules explicitly injected.

Model	MRR				Hits@10
	0%	10%	20%	100%	0%	10%	20%	100%
MLP	0.123	0.156	0.198	0.851	0.279	0.364	0.449	0.932
TransE	0.399	0.469	0.500	0.775	0.917	0.944	0.944	0.957
RotatE	0.579	0.890	0.927	0.944	0.784	0.949	0.961	0.962
DiffLogic	0.954	0.953	0.952	0.954	0.964	0.966	0.963	0.967

With 0% pattern data present in the graph, DiffLogic achieves 0.954 MRR and 0.964 Hits@10 solely from explicit rule injection. In contrast, data-driven KG embeddings require 100% of the pattern triples to reach comparable performance (RotatE reaches 0.944 MRR, TransE 0.775, MLP 0.851), demonstrating that DiffLogic leverages prior domain rules with high sample efficiency.

Knowl 10 — Dependency on External Rule Mining Quality
limitation
The performance and inference quality of DiffLogic depend heavily on the accuracy and coverage of the input first-order logic rules. DiffLogic assumes candidate rules are supplied in advance by domain experts or mined via discrete external rule-mining engines (e.g., AMIE3). The framework does not perform automatic end-to-end differentiable rule discovery, which restricts its utility in domains where rules cannot be readily mined or specified a priori.

Coverage note — None omitted; all core contributions including continuous HL-MRF formulation, RGIG grounding algorithm, E-step and M-step optimization objectives with pseudo-likelihood gradients, joint inference formulas, empirical results across benchmarks, and model limitations are included.

References

1.Stephen H. Bach, Matthias Broecheler, Bert Huang, and Lise Getoor. Hinge-loss Markov random fields and probabilistic soft logic. Journal of Machine Learning Research, 32(1), 2017.
2.Ivana Balažević, Carl Allen, and Timothy M Hospedales. Tucker: Tensor factorization for knowledge graph completion. arXiv preprint arXiv:1901.09590, 2019.
3.Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
4.Kewei Cheng, Jiahao Liu, Wei Wang, and Yizhou Sun. Rlogic: Recursive logical rule learning from knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 179–189, 2022.
5.Junnan Dong, Qinggang Zhang, Xiao Huang, Keyu Duan, Qiaoyu Tan, and Zhimeng Jiang. Hierarchy-aware multi-hop question answering over knowledge graphs. In Proceedings of the ACM Web Conference 2023, pp. 2519–2527, 2023a.
6.Junnan Dong, Qinggang Zhang, Xiao Huang, Qiaoyu Tan, Daochen Zha, and Zhao Zihao. Active ensemble learning for knowledge graph error detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 877–885, 2023b.
7.Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge vault: A web-scale approach to probabilistic knowledge fusion. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 601–610, 2014.
8.Huang Fang, Yang Liu, Yunfeng Cai, and Mingming Sun. MLN4KB: an efficient markov logic network engine for large-scale knowledge bases and structured logic rules. In The International World Wide Web Conference 2023, 2023.
9.Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Jointly embedding knowledge graphs and logical rules. In Proceedings of the 2016 conference on empirical methods in natural language processing, pp. 192–202, 2016.
10.Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Knowledge graph embedding with iterative guidance from soft rules. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
11.Feiran Huang, Zefan Wang, Xiao Huang, Yufeng Qian, Zhetao Li, and Hao Chen. Aligning distillation for cold-start item recommendation. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1147–1157, 2023.
12.Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. Knowledge graph embedding based question answering. In Proceedings of the twelfth ACM international conference on web search and data mining, pp. 105–113, 2019.
13.Jonathan Lajus, Luis Galárraga, and Fabian Suchanek. Fast and exact rule mining with amie 3. In The Semantic Web: 17th International Conference, ESWC 2020, Heraklion, Crete, Greece, May 31–June 4, 2020, Proceedings 17, pp. 36–52. Springer, 2020.
14.Freddy Lecue. On the role of knowledge graphs in explainable ai. Semantic Web, 11(1):41–51, 2020.
15.Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7710–7720, Vancouver, Canada, 2019.
16.Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. arXiv preprint arXiv:2010.04029, 2020.
17.Hongyu Ren, Hanjun Dai, Bo Dai, Xinyun Chen, Denny Zhou, Jure Leskovec, and Dale Schuurmans. Smore: Knowledge graph completion and multi-hop reasoning in massive knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1472–1482, 2022.
18.Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62:107–136, 2006.
19.Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. Advances in Neural Information Processing Systems, 32, 2019.
20.Tara Safavi and Danai Koutra. Codex: A comprehensive knowledge graph completion benchmark. arXiv preprint arXiv:2009.07810, 2020.
21.Chao Shang, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. End-to-end structure-aware convolutional networks for knowledge base completion. In Proceedings of the AAAI conference on artificial intelligence, pp. 3060–3067, 2019.
22.Baoxu Shi and Tim Weninger. Proje: Embedding projection for knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
23.Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: A Core of Semantic Knowledge. In 16th International Conference on the World Wide Web, pp. 697–706, 2007.
24.Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint arXiv:1902.10197, 2019.
25.Ilaria Tiddi and Stefan Schlobach. Knowledge graphs as tools for explainable machine learning: A survey. Artificial Intelligence, 302:103627, 2022.
26.Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-based multi-relational graph convolutional networks. arXiv preprint arXiv:1911.03082, 2019.
27.Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplanes. In Proceedings of the AAAI conference on artificial intelligence, 2014.
28.Yue Xu, Hao Chen, Zefan Wang, Jianwen Yin, Qijie Shen, Dimin Wang, Feiran Huang, Lixiang Lai, Tao Zhuang, Junfeng Ge, and Xia Hu. Multi-factor sequential re-ranking with perception-aware diversification. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 5327–5337, 2023.
29.Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information processing systems, 30, 2017.
30.Qinggang Zhang, Junnan Dong, Keyu Duan, Xiao Huang, Yezi Liu, and Linchuan Xu. Contrastive knowledge graph error detection. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 2590–2599, 2022a.
31.Qinggang Zhang, Junnan Dong, Qiaoyu Tan, and Xiao Huang. Integrating entity attributes for error-aware knowledge graph embedding. IEEE Transactions on Knowledge and Data Engineering, pp. 1–16, 2023. doi: 10.1109/TKDE.2023.3310149.
32.Wen Zhang, Jiaoyan Chen, Juan Li, Zezhong Xu, Jeff Z Pan, and Huajun Chen. Knowledge graph reasoning with logics and embeddings: survey and perspective. arXiv preprint arXiv:2202.07412, 2022b.
33.Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In Proceedings of the 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020.
34.Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34:19172–19183, 2021.
35.Da Zheng, Xiang Song, Chao Ma, Zeyuan Tan, Zihao Ye, Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis. Dgl-ke: Training knowledge graph embeddings at scale. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 739–748, 2020.

Citation

MLA

Shengyuan, C., et al. “Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs”. Advances in Neural Information Processing Systems 36, 2023, pp. 28139–54, https://doi.org/10.52202/075280-1222.

APA

Shengyuan, C., Cai, Y., Fang, H., Huang, X., & Sun, M. (2023). Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs. Advances in Neural Information Processing Systems 36, 28139–28154. https://doi.org/10.52202/075280-1222

Chicago

Shengyuan, C., Y. Cai, H. Fang, X. Huang, and M. Sun. 2023. “Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs”. Advances in Neural Information Processing Systems 36, 28139–54. https://doi.org/10.52202/075280-1222.

Harvard

Shengyuan, C. et al. (2023) “Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs”, Advances in Neural Information Processing Systems 36. Neural Information Processing Systems Foundation, Inc. (NeurIPS), pp. 28139–28154. Available at: https://doi.org/10.52202/075280-1222.

Vancouver

1. Shengyuan C, Cai Y, Fang H, Huang X, Sun M (2023) Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs. In: Advances in Neural Information Processing Systems 36. Neural Information Processing Systems Foundation, Inc. (NeurIPS), pp 28139–28154

BibTeX

@inproceedings{Shengyuan_2023, series={NeurIPS 2023}, title={Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs}, url={http://dx.doi.org/10.52202/075280-1222}, DOI={10.52202/075280-1222}, booktitle={Advances in Neural Information Processing Systems 36}, publisher={Neural Information Processing Systems Foundation, Inc. (NeurIPS)}, author={Shengyuan, Chen and Cai, Yunfeng and Fang, Huang and Huang, Xiao and Sun, Mingming}, year={2023}, pages={28139–28154}, collection={NeurIPS 2023} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Differentiable Neuro-Symbolic Reasoning on Large-Scale Knowledge Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Hinge-Loss Markov Random Field Formulation in DiffLogic

Knowl 2 — Distance-to-Satisfaction for Logic Ground Formulas via Łukasiewicz t-Norm

Knowl 3 — Rule-Guided Iterative Grounding (RGIG)

Knowl 4 — Embedding Parameter Optimization Objective (E-Step)

Knowl 5 — Rule Weight Gradient via Pseudo-Likelihood Optimization (M-Step)

Knowl 6 — Joint Inference Combining Embedding Scores and Cumulative Rule Weights