WILTing Trees: Interpreting the Distance Between MPNN Embeddings

Masahiro Negishi, Thomas Gärtner, Pascal Welke
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:45852-45876, 2025.

Abstract

We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts with previous work, which links MPNN distances on arbitrary tasks to structural distances on graphs that ignore task-specific information. To address this gap, we distill the distance between MPNN embeddings into an interpretable graph distance. Our method uses optimal transport on the Weisfeiler Leman Labeling Tree (WILT), where the edge weights reveal subgraphs that strongly influence the distance between embeddings. This approach generalizes two well-known graph kernels and can be computed in linear time. Through extensive experiments, we demonstrate that MPNNs define the relative position of embeddings by focusing on a small set of subgraphs that are known to be functionally important in the domain.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-negishi25a, title = {{WILT}ing Trees: Interpreting the Distance Between {MPNN} Embeddings}, author = {Negishi, Masahiro and G\"{a}rtner, Thomas and Welke, Pascal}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {45852--45876}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/negishi25a/negishi25a.pdf}, url = {https://proceedings.mlr.press/v267/negishi25a.html}, abstract = {We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts with previous work, which links MPNN distances on arbitrary tasks to structural distances on graphs that ignore task-specific information. To address this gap, we distill the distance between MPNN embeddings into an interpretable graph distance. Our method uses optimal transport on the Weisfeiler Leman Labeling Tree (WILT), where the edge weights reveal subgraphs that strongly influence the distance between embeddings. This approach generalizes two well-known graph kernels and can be computed in linear time. Through extensive experiments, we demonstrate that MPNNs define the relative position of embeddings by focusing on a small set of subgraphs that are known to be functionally important in the domain.} }
Endnote
%0 Conference Paper %T WILTing Trees: Interpreting the Distance Between MPNN Embeddings %A Masahiro Negishi %A Thomas Gärtner %A Pascal Welke %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-negishi25a %I PMLR %P 45852--45876 %U https://proceedings.mlr.press/v267/negishi25a.html %V 267 %X We investigate the distance function learned by message passing neural networks (MPNNs) in specific tasks, aiming to capture the functional distance between prediction targets that MPNNs implicitly learn. This contrasts with previous work, which links MPNN distances on arbitrary tasks to structural distances on graphs that ignore task-specific information. To address this gap, we distill the distance between MPNN embeddings into an interpretable graph distance. Our method uses optimal transport on the Weisfeiler Leman Labeling Tree (WILT), where the edge weights reveal subgraphs that strongly influence the distance between embeddings. This approach generalizes two well-known graph kernels and can be computed in linear time. Through extensive experiments, we demonstrate that MPNNs define the relative position of embeddings by focusing on a small set of subgraphs that are known to be functionally important in the domain.
APA
Negishi, M., Gärtner, T. & Welke, P.. (2025). WILTing Trees: Interpreting the Distance Between MPNN Embeddings. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:45852-45876 Available from https://proceedings.mlr.press/v267/negishi25a.html.

Related Material