On Computing Total Variation Distance between Markov Logic Networks

Zixiang Xiong, Peter Jung, Qiaolan Meng, Yuanhong Wang, Ondřej Kuželka, Yuyi Wang
Proceedings of the 13th International Conference on Probabilistic Graphical Models, PMLR 343:895-910, 2026.

Abstract

The total variation (TV) distance is a fundamental metric for quantifying the difference between probability distributions. Bhattacharyya et al. (2024) showed that computing the TV distance between two directed graphical models is, in general, intractable. We extend this line of research to Markov Logic Networks (MLNs), a prominent class of statistical relational models that combine first-order logic with probabilistic graphical models. Specifically, we establish both tractability and hardness results regarding the computation of the TV distance between two MLNs. On the positive side, we reduce TV distance computation between MLNs to probabilistic inference, enabling the use of lifted inference techniques. Thereby, we identify classes of MLNs for which TV distance computation is tractable. On the negative side, we prove that, in general, the TV distance computation between two MLNs is intractable. In addition to these theoretical results, we empirically validate that soft rules with moderate weights can approximate hard rules, and we also present an application of the MLNs TV distance in benchmarking graph neural networks on synthetic data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v343-xiong26a, title = {On Computing Total Variation Distance between {Markov} Logic Networks}, author = {Xiong, Zixiang and Jung, Peter and Meng, Qiaolan and Wang, Yuanhong and Ku\v{z}elka, Ond\v{r}ej and Wang, Yuyi}, booktitle = {Proceedings of the 13th International Conference on Probabilistic Graphical Models}, pages = {895--910}, year = {2026}, editor = {Camps-Valls, Gustau and Leonelli, Manuele and Varando, Gherardo}, volume = {343}, series = {Proceedings of Machine Learning Research}, month = {09--11 Sep}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v343/main/assets/xiong26a/xiong26a.pdf}, url = {https://proceedings.mlr.press/v343/xiong26a.html}, abstract = {The total variation (TV) distance is a fundamental metric for quantifying the difference between probability distributions. Bhattacharyya et al. (2024) showed that computing the TV distance between two directed graphical models is, in general, intractable. We extend this line of research to Markov Logic Networks (MLNs), a prominent class of statistical relational models that combine first-order logic with probabilistic graphical models. Specifically, we establish both tractability and hardness results regarding the computation of the TV distance between two MLNs. On the positive side, we reduce TV distance computation between MLNs to probabilistic inference, enabling the use of lifted inference techniques. Thereby, we identify classes of MLNs for which TV distance computation is tractable. On the negative side, we prove that, in general, the TV distance computation between two MLNs is intractable. In addition to these theoretical results, we empirically validate that soft rules with moderate weights can approximate hard rules, and we also present an application of the MLNs TV distance in benchmarking graph neural networks on synthetic data.} }
Endnote
%0 Conference Paper %T On Computing Total Variation Distance between Markov Logic Networks %A Zixiang Xiong %A Peter Jung %A Qiaolan Meng %A Yuanhong Wang %A Ondřej Kuželka %A Yuyi Wang %B Proceedings of the 13th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2026 %E Gustau Camps-Valls %E Manuele Leonelli %E Gherardo Varando %F pmlr-v343-xiong26a %I PMLR %P 895--910 %U https://proceedings.mlr.press/v343/xiong26a.html %V 343 %X The total variation (TV) distance is a fundamental metric for quantifying the difference between probability distributions. Bhattacharyya et al. (2024) showed that computing the TV distance between two directed graphical models is, in general, intractable. We extend this line of research to Markov Logic Networks (MLNs), a prominent class of statistical relational models that combine first-order logic with probabilistic graphical models. Specifically, we establish both tractability and hardness results regarding the computation of the TV distance between two MLNs. On the positive side, we reduce TV distance computation between MLNs to probabilistic inference, enabling the use of lifted inference techniques. Thereby, we identify classes of MLNs for which TV distance computation is tractable. On the negative side, we prove that, in general, the TV distance computation between two MLNs is intractable. In addition to these theoretical results, we empirically validate that soft rules with moderate weights can approximate hard rules, and we also present an application of the MLNs TV distance in benchmarking graph neural networks on synthetic data.
APA
Xiong, Z., Jung, P., Meng, Q., Wang, Y., Kuželka, O. & Wang, Y.. (2026). On Computing Total Variation Distance between Markov Logic Networks. Proceedings of the 13th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 343:895-910 Available from https://proceedings.mlr.press/v343/xiong26a.html.

Related Material