3-WL GNNs for Metric Learning on Graphs
Aldo Moscatelli, Maxime Bérar, Pierre Héroux, Florian Yger, Sébastien Adam · 2025
Since the advent of Graph Neural Networks (GNNs), many works have computed distances between graphs by embedding them in vector spaces using Message Passing GNNs (MPNNs).However, MPNNs are known for their lack of expressiveness as they are bounded by the firstorder Weisfeiler-Lehman test.In this paper, we use higher-order GNNs to tackle the metric learning problem and show on benchmark datasets how they can improve performance by using a node-level strategy and the Wasserstein distance. IntroductionA key challenge in modeling structured information with graphs lies in computing the distances between them.The Graph Edit Distance(GED)[4] is a state-ofthe-art method for this purpose; however, it suffers from NP-hard complexity.Recently, several architectures have been proposed to address this limitation [9,7,8,11,12] in a learning framework.These architectures generally consist of two main components.The first is an embedding block that uses siamese Graph Neural Networks(GNNs) to embed graphs either at the graph level or at the node level.The second component is a metric block that takes the embeddings generated by the first block as input and computes the distance between graphs, taking into account the embedding level.The rationale behind these architectures is that the embedding block learns an optimal representation to facilitate the computations in the metric block.To the best of our knowledge, existing embedding blocks in the literature rely on simple yet effective Message Passing Neural Networks(MPNNs), such as GCN [3] or GIN [2].Consequently, they suffer from the well-known limitations of MPNNs, including over-smoothing, over-squashing, and limited expressive power.This last limitation is particularly significant for metric learning, as it affects the ability to generate distinct embeddings for different graphs.Yet, GCN and GIN models have been shown to be at most equivalent to the firstorder Weisfeiler-Lehman(WL) test in the WL hierarchy [1].Recently, more expressive GNNs such as PPGN [5] and G 2 N 2 [6] have been introduced in the literature, achieving a 3-WL expressivity level.To attain this level of expressivity, these architectures naturally incorporate edge embeddings, adding valuable information to the traditional node-and graph-level representations.These recent developments raise two research questions: how can 3-WL GNNs be integrated into a metric learning framework, and do they enable improved performance?283