# Pre-image Free Graph Machine Learning with Normalizing Flows

Clément Glédel, Benoit Gaüzère, Paul Honeine

► To cite this version:

Clément Glédel, Benoit Gaüzère, Paul Honeine. Pre-image Free Graph Machine Learning with Normalizing Flows. Pattern Recognition Letters, 2025, 190, pp.45-51. 10.1016/j.patrec.2025.02.005. hal-04936630

HAL Id: hal-04936630

https://normandie-univ.hal.science/hal-04936630v1

Submitted on 8 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Pre-image Free Graph Machine Learning with Normalizing Flows*

Clément Glédel, Benoît Gaüzère, Paul Honeine

Univ Rouen Normandie, INSA Rouen Normandie,

Université Le Havre Normandie, Normandie Univ,

LITIS UR 4108, F-76000 Rouen, France

clement.gledel@univ-rouen.fr

benoit.gauzere@insa-rouen.fr

paul.honeine@univ-rouen.fr

## Abstract

Nonlinear embeddings are central in machine learning (ML). However, they often suffer from insufficient interpretability, due to the restricted access to the latent space. To improve interpretability, elements of the latent space need to be represented in the input space. The process of finding such inverse transformation is known as the pre-image problem. This challenging task is especially difficult when dealing with complex and discrete data represented by graphs. In this paper, we propose a framework aimed at defining ML models that do not suffer from the pre-image problem. This framework is based on Normalizing Flows (NF), generating the latent space by learning both forward and inverse transformations. From this framework, we propose two specifications to design models working on predictive contexts, namely classification and regression. As a result, our approaches are able to obtain good predictive performances and to generate the pre-image of any element in the latent space. Our experimental results highlight the predictive capabilities and the proficiency in generating graph pre-images, thereby emphasizing the versatility and effectiveness of our approaches for graph machine learning.

**Keywords**— Graph Normalizing Flow, Pre-image problem, Regression, Classification, Interpretability, Nonlinear embedding

<footnote>*Preprint of paper published in Pattern Recognition Letters, 2025.</footnote>
# 1 Introduction

Machine learning (ML) often transforms graph data to a relevant latent space. This transformation is either implicit using kernels (Jia et al., 2022), or explicit using graph integration techniques or nonlinear operations in graph neural networks (Balcilar et al., 2021). While these methods provide effective prediction models for a given task, they lack of interpretability. To overcome this drawback, it is of great interest to reverse the transformation process, mapping the results from the latent space into the graph space. This challenge is commonly known as the pre-image problem. Various approaches have been proposed to address it on Euclidean data (Honeine and Richard, 2011; Zhu and Honeine, 2017; Tran Thi Phuong et al., 2020), and on graph data (Bakır et al., 2004b; Jia et al., 2021).

This paper introduces a framework to define interpretable models that are insensitive to the pre-image problem. To do this, it is inspired by recent advances in generative graph models (De Cao and Kipf, 2018; Guo and Zhao, 2022), particularly Normalizing Flows (NF) for graphs data (GraphNF) (Liu et al., 2019). A NF generates, from a complex data distribution, a latent space where the embedded data follows a Gaussian distribution. Moreover, the model learns this transformation such that its invertibility is guaranteed and known. We revisit the NF to go beyond a Gaussian distribution, by addressing prediction tasks, namely classification and regression. The performance of the proposed methods is demonstrated using the MoFlow architecture (Zang and Wang, 2020). The conducted experiments on benchmark graph datasets demonstrate the applicability of our approach to graph prediction tasks, by providing an efficient representation space and overcoming the pre-image problem.

The rest of the paper is organized as follows. Section 2 introduces the NF and GraphNF. Our contributions are described in Section 3, by first presenting our framework and then its specifications for classification and regression. Experimental results are given in Section 4, followed by the conclusion in Section 5.

# 2 Normalizing Flows Preliminaries

Normalizing Flows (NF) are generative models that learn an invertible transformation function $\Phi$ describing the relationship between a complex distribution $P_X$ associated with the data and another distribution $P_Z$, often chosen as a Gaussian distribution. This allows data to be generated efficiently by sampling in the latent space $Z$ and applying the inverse function $\Phi^{-1}$ to produce data in the input space $\mathcal{X}$. The relationship between the probability densities in NF is determined by the change of variable formula. Thus, with $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_N \in \mathcal{X}$ the input samples, the training involves maximizing the log-likelihood function

$$ \log P_X(X) = \sum_{i=1}^{N} \log P_Z(\Phi(\mathbf{x}_i)) + \log \left| \det \left( \frac{\partial \Phi(\mathbf{x}_i)}{\partial \mathbf{x}_i} \right) \right|. \quad (1) $$

This equation captures the exact relation between the distributions, thus contrasting with variational autoencoders that are built using lower bounds. However, to use this formula, the NF must have an easily invertible structure and the determinant must be simple to compute. To increase the expressiveness of the model, the $\Phi$ transformation function combines bijective functions $\Phi = \Phi_{\ell} \circ \Phi_{\ell-1} \circ \dots \circ \Phi_1$. Then, computing the Jacobian determinant of $\Phi$ involves multiplying the determinants of the individual $\Phi_i$
components. To meet these requirements, various NF architectures were introduced (Kobyzev et al., 2020).

GraphNF extends the NF principle to graphs (Shi et al., 2020; Liu et al., 2019; Madhawa et al., 2019; Honda et al., 2019; Zang and Wang, 2020). GraphNVP (Madhawa et al., 2019) and MoFlow (Zang and Wang, 2020) are GraphNF that represent molecular graphs via a paired structure of the node feature matrix and adjacency tensor. Both models use affine coupling layers to transform both the node feature matrix and the adjacency tensor. MoFlow, in particular, incorporates a modified version of Glow (Kingma and Dhariwal, 2018), originally designed as a convolutional NF working on image data, to capture the bonds in a graph. Moreover, MoFlow proposes a conditional graph flow structure to model atoms with respect to the graph bonds by using Relational Graph Convolutional Network models. In addition, since MoFlow is designed for molecular graphs, it adds a post-hoc correction step to guarantee the validity of the generated molecules.

# 3 Proposed Framework

The pre-image problem is a major limitation of most ML techniques. However, computing the pre-image of a particular point in the latent space $\mathcal{Z}$ can be of great interest when we wish to bring interpretability to a model and its predictions. This is even more the case when dealing with graph data, describing complex data with discrete structures. In order to solve this problem, we propose a framework that considers the latent space $\mathcal{Z}$ generated by a NF as the embedding space of interest.

Graphs are complex data structures that can be represented in different ways. Thus, we generally define the reversible function of a GraphNF, working directly on the graph space $\mathcal{G}$, as $\Phi_G: \mathcal{G} \to \mathcal{Z}$. To deal with such data, some GraphNF as MoFlow operate on matrix representations of graphs. This representation considers the case where each graph is divided into a feature matrix and an adjacency tensor, i.e., $\mathcal{G} = (\mathbf{X}, \mathbf{A}) \in \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e}$, where each graph is represented by at most $n$ nodes of $d$ dimensions and a set of edges characterized by $e$ dimensions. In this case, we define the reversible function generated by a GraphNF with $\Phi: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \to \mathcal{Z}$. This representation allows working directly with a complete graph representation, but has certain drawbacks, such as potentially high memory costs for large graphs and sensitivity to permutations of matrix graph representations. The latter is a major drawback, as the non-uniqueness of the representation of a $n$-node graph results in the presence of $n!$ different representations in the latent space generated by the model. Despite the multiple potential representations for a single graph, we maintain that applying our learning approaches can effectively address this issue. Once the model is trained, we expect these representations to align with the structure of the intended latent space.

In this paper, we consider the use of GraphNF working on feature matrices and adjacency tensors to represent graphs, where each data is represented by a two-part latent representation corresponding to the node feature matrix and the adjacency tensor. In addition, we propose to concatenate the flattened representations of these two parts to obtain the data representation in the latent space $\mathcal{Z}$, corresponding to a $D$-dimensional vector in $\mathbb{R}$ determined by $D = n^2 \times e + n \times d$.

Our framework, illustrated in Figure 1, involves three steps:

(i) Using a function $\Phi: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \to \mathbb{R}^D$ learned by a GraphNF, the first step aims to generate a distribution in $\mathcal{Z}$ formed from multiple label-based Gaussian
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of the framework of our approach</figcaption></figure>

distributions, each parameterized by different means and covariance matrices.

(ii) From the generated latent space $\mathcal{Z}$, we have the capability to employ either basic operations or advanced algorithms, such as support vector machines (SVM) for classification or ridge regression for regression.

(iii) As we are working with a GraphNF model, characterized by its invertibility, our learning procedure allows us to generate both the $\Phi$ transformation and its inverse $\Phi^{-1}$. As a result, we can compute the graph pre-image for any sample in the latent space $\mathcal{Z}$.

Based on our framework, we present two task-specific approaches, for classification (Section 3.1) and regression (Section 3.2), allowing both prediction and pre-image generation.

# 3.1 Classification-based GraphNF

GraphNF models generally embed the data to follow a specific probability density in the latent space, usually defined as a Gaussian distribution. Unfortunately, this configuration cannot efficiently separate the data into distinct classes. In this section, our objective is to use a GraphNF model, in a classification context, to learn latent representations of graph data that are linearly separable. The inverse function provided by the GraphNF will allow us to generate the graph pre-image from any sample in the space $\mathcal{Z}$ where the predictive model operates.

## 3.1.1 Learning process

In this section, we present a new supervised formulation of class-aware GraphNF learning. To this end, the objective function of GraphNF is modified to allow graphs to be encoded in specific regions of the latent space $\mathcal{Z} \subset \mathbb{R}^D$ according to their respective class. Thus, the learned transformation function $\Phi: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \rightarrow \mathcal{Z}$ allows the generation of a latent space in which data representations are linearly separable.
Let $\mathcal{D} = \{(G_1, y_1), (G_2, y_2), \dots, (G_N, y_N)\}$ be a dataset where $G_i \in \mathcal{G}$ represents an observed data graph and $y_i \in Y = \{1, \dots, C\}$ its class encoding. We assign to each class $c \in \{1, \dots, C\}$ a Gaussian distribution in $\mathcal{Z}$, i.e.,

$$P_{\mathcal{Z}}(\mathbf{z}, \boldsymbol{\mu}_c, \boldsymbol{\Sigma}_c) = \frac{1}{\sqrt{(2\pi)^D \det(\boldsymbol{\Sigma}_c)}} e^{-\frac{1}{2}(\mathbf{z} - \boldsymbol{\mu}_c)^{\top} \boldsymbol{\Sigma}_c^{-1} (\mathbf{z} - \boldsymbol{\mu}_c)}$$

where the mean $\boldsymbol{\mu}_c$ and covariance matrix $\boldsymbol{\Sigma}_c$ are the parameters of the Gaussian associated with the $c$ class. From this, we need to adapt the GraphNF training so that each graph representation in $\mathcal{Z}$ is fitted to the appropriate Gaussian distribution according to the $c$ class encoded by $y_i$. Consequently, the log-probability term used in (1) is defined as follows:

$$\log P_{\mathcal{Z}}(\mathbf{z}, \boldsymbol{\mu}_c, \boldsymbol{\Sigma}_c) = -\frac{1}{2} \left( D \log(2\pi) + (\mathbf{z} - \boldsymbol{\mu}_c)^{\top} \boldsymbol{\Sigma}_c^{-1} (\mathbf{z} - \boldsymbol{\mu}_c) \right) - \log(\det(\boldsymbol{\Sigma}_c)). \quad (2)$$

Using such function allows the data belonging to the same class to be fitted to a specific region of the latent space $\mathcal{Z}$, creating linearly separable representations between the different classes.

In addition, we wish to learn the position of the different Gaussian distributions in the latent space in order to capture potentially existing relationships between classes in the dataset. Thus, we encourage the model to distinguish between the different classes by incorporating an additional loss term in the GraphNF objective function to learn the means of the distributions of each class $\boldsymbol{\mu}_c$. Consequently, our optimization consists in minimizing two losses. The first describes the change in density of a sample using the change-of-variable formula, i.e.,

$$\mathcal{L}_{\text{nf}}(\mathbf{X}_i, \mathbf{A}_i, \boldsymbol{\mu}_{y_i}, \boldsymbol{\Sigma}_{y_i}) = - \log P_{\mathcal{Z}}(\Phi(\mathbf{X}_i, \mathbf{A}_i), \boldsymbol{\mu}_{y_i}, \boldsymbol{\Sigma}_{y_i}) - \log \left| \det \left( \frac{\partial \Phi(\mathbf{X}_i, \mathbf{A}_i)}{\partial \mathbf{X}_i \partial \mathbf{A}_i} \right) \right|.$$

The second one measures the proximity of the distributions, i.e.,

$$\mathcal{L}_{\mu} = - \log \left( 1 + \frac{1}{C^2} \sum_{i=1}^{C} \sum_{j=1}^{C} \| \boldsymbol{\mu}_i - \boldsymbol{\mu}_j \|_2^2 \right).$$

Combining these two terms with a trade-off parameter $\beta$, the final loss function for an observed data is defined as follows:

$$\mathcal{L}(\mathbf{X}_i, \mathbf{A}_i, y_i) = \mathcal{L}_{\text{nf}}(\mathbf{X}_i, \mathbf{A}_i, \boldsymbol{\mu}_{y_i}, \boldsymbol{\Sigma}_{y_i}) + \beta \mathcal{L}_{\mu}. \quad (3)$$

In addition, to distinguish classes in the latent space, we associate specific dimensions with each class, by defining $C$ different covariance matrices. To do this, we define them with a class-specific set of $\lambda_i$ eigenvalues. Furthermore, given the two-part structure of the latent representation and the fact that our latent representation in $\mathcal{Z}$ is a concatenation of these representations, we propose to define these eigenvalues separately for each part. Thus, for each of these two parts, we apply the following eigenvector assignment method:

(i) We first compute the maximum number of dimensions to assign to each class using the formula $k = \lfloor \frac{l}{C} \rfloor$, where $l$ denotes the number of dimensions and $\lfloor \cdot \rfloor$ the largest integer less than or equal to that number.
(ii) Then, for each c class, we assign high values to k different eigenvalues according to {$\lambda_1...\lambda_k$} for c = 1, {$\lambda_{k+1}...\lambda_{2k}$} for c = 2, ... In this way, each distribution will extend over the dimensions assigned to it.

(iii) Finally, the remaining $l-k$ eigenvalues are set to $\lambda_1^{k/(k-l)}$, so that the determinant of the covariance matrix is 1, thus preserving in $\mathcal{Z}$ the data dispersion in $\mathcal{G}$.

Applying this method to both parts of the latent representation yields the D eigenvalues for each class, constructing the covariance matrices with $\Sigma_c = \sum_{i=1}^{D} \lambda_i v_i^T v_i$, with $v_i$ the eigenvectors corresponding to a set of orthogonal vectors.

Let $\Omega = \{\Theta, \mu_1, \mu_2, ..., \mu_C\}$ be the set of optimizable parameters, with $\Theta$ the set of parameters of $\Phi$. To estimate the parameters of $\Omega$, we use a stochastic gradient descent algorithm to minimize the loss function (3) on a batch $I$ of samples randomly selected from the training dataset at each iteration, i.e.,

$$ \Omega \leftarrow \Omega - \eta \sum_{i \in I} \nabla_{\Omega} \mathcal{L}(\mathbf{X}_i, \mathbf{A}_i, y_i) \quad (4) $$

where $\eta$ is the learning rate.

### 3.1.2 Operations in $\mathcal{Z}$

Our approach allows the learning of a latent space $\mathcal{Z}$ where graphs are linearly separable for a given classification task. Consequently, working on classification tasks, the structure of the generated space $\mathcal{Z}$ allows the learning of an efficient linear classifier using algorithms such as SVM or logistic regression. We denote $g: \mathcal{Z} \rightarrow \{1...C\}$ this model. Thus, predictions are made by transposing graphs into $\mathcal{Z}$ using $\Phi$ and obtaining a predicted label with the prediction model $g$. Moreover, since $\Phi$ corresponds to a nonlinear transformation, defining a linear predictive model $g$ in the latent space $\mathcal{Z}$ is equivalent to defining a nonlinear predictive model $f: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \rightarrow \{1...C\}$. The latter is described by $f(\mathbf{X}, \mathbf{A}) = g(\Phi(\mathbf{X}, \mathbf{A}))$.

Moreover, the availability of $\Phi^{-1}$ allows computing the graph pre-image of any point of interest of the latent space, thus eliminating the pre-image problem. In a classification context, the resulting space $\mathcal{Z}$ could be used to generate graph pre-images of class prototypes or random points of the Gaussian parametrized by $(\mu_c, \Sigma_c)$ to obtain graphs of any class c.

## 3.2 Regression-based GraphNF

Among the various prediction tasks, regression is also one of the most common. Unlike classification, our objective is not to create linearly separable representations of graphs, but to generate linearly organized representations based on their quantitative label values. Thus, our proposal involves a new supervised formulation of GraphNF training that takes into account the quantitative labels associated with graphs. To this end, we adapt the objective function of the GraphNF to embed graph data based on their quantitative values, by designing GraphNF to represent data in a latent space suitable for linear regression.

### 3.2.1 Learning process

Let us consider a dataset $\mathcal{D} = \{(G_1, y_1), (G_2, y_2), ..., (G_N, y_N)\}$, where each input consists of graph data represented by $G_i \in \mathcal{G}$ and their associated quantitative labels
designated by $y_i \in Y \subset \mathbb{R}$. In the same way as in the previous section, we build the latent space using Gaussian distributions, each parameterized by a mean $\mu$ and a covariance matrix $\Sigma$ defined by

$$P_Z(\mathbf{z}, \mu, \Sigma) = \frac{1}{\sqrt{(2\pi)^D \det(\Sigma)}} e^{-\frac{1}{2}(\mathbf{z}-\mu)^\top \Sigma^{-1} (\mathbf{z}-\mu)}.$$

Taking the log of this equation gives

$$\log P_Z(\mathbf{z}, \mu, \Sigma) = -\frac{1}{2} \left( D \log(2\pi) + (\mathbf{z}-\mu)^\top \Sigma^{-1} (\mathbf{z}-\mu) \right) - \log(\det(\Sigma)). \quad (5)$$

To organize the data representations linearly in the latent space, we associate each data with a Gaussian distribution aligned along an axis by computing an interpolated distribution mean based on the quantitative label's value. This interpolation is achieved by defining two extreme Gaussians corresponding to the maximum and minimum values of the quantitative labels. To do this, we define two Gaussian distributions parametrized by $(\mu_{\min}, \Sigma_{\min})$ and $(\mu_{\max}, \Sigma_{\max})$, assigned to the minimum and maximum values of $Y$, respectively. To simplify, we use isotropic Gaussian distributions, i.e., $\Sigma_{\min} = \Sigma_{\max} = \sigma^2 \mathbb{I}_D$, where $\mathbb{I}_D$ is the $D \times D$ identity matrix, and $\sigma^2$ the variance.

For the interpolation process, we assign a belonging coefficient $\tau_{y_i}$ to each graph sample based on its quantitative value. This coefficient is computed using $\tau_{y_i} = \frac{y_i - \min(Y)}{\max(Y) - \min(Y)}$. The mean of the interpolated Gaussian, denoted $\mu_{y_i}$, is computed based on the resulting coefficient with

$$\mu_{y_i} = \tau_{y_i} \mu_{\min} + (1 - \tau_{y_i}) \mu_{\max}. \quad (6)$$

In order to make our interpolation method meaningful, it is essential that the locations of the extreme Gaussians in $\mathcal{Z}$ are both distinct and sufficiently separated. We propose to learn their means $(\mu_{\min}, \Sigma_{\min})$ during the GraphNF learning in the same way as in our classification approach. To achieve this, we add another term into the objective function to maximize the Gaussian separability.

The loss function is therefore made up of two terms. The first is based on (1), where we represent each graph $G_i$ in matrix form $(\mathbf{X}_i, \mathbf{A}_i)$, yielding

$$\mathcal{L}_{\text{nf}}(\mathbf{X}_i, \mathbf{A}_i, \mu_{y_i}) = - \log P_Z(\Phi(\mathbf{X}_i, \mathbf{A}_i), \mu_{y_i}, \Sigma_{y_i}) - \log \left| \det \left( \frac{\partial \Phi(\mathbf{X}_i, \mathbf{A}_i)}{\partial \mathbf{X}_i \partial \mathbf{A}_i} \right) \right|.$$

Here, $\log P_Z(\Phi(\mathbf{X}_i, \mathbf{A}_i), \mu_{y_i}, \Sigma_{y_i})$ corresponds to (5) in which the interpolated Gaussian parameters $(\mu_{y_i}, \Sigma_{y_i})$ are used. The equation (6) is used to compute the mean $\mu_{y_i}$, while $\Sigma_{y_i} = \sigma^2 \mathbb{I}_D$. To encourage the separation of the two extreme Gaussians, we define the second term as $\mathcal{L}_{\mu} = - \log (1 + \| \mu_{\min} - \mu_{\max} \|_2^2)$. Hence, the resulting loss function is defined as follows:

$$\mathcal{L}(\mathbf{X}_i, \mathbf{A}_i, y_i) = \mathcal{L}_{\text{nf}}(\mathbf{X}_i, \mathbf{A}_i, \mu_{y_i}) + \beta \mathcal{L}_{\mu}, \quad (7)$$

for the trade-off parameter $\beta$. The optimization uses the same scheme as in the classification approach, following (4) with a set of optimizable parameters defined as $\Omega = \{\Theta, \mu_{\min}, \mu_{\max}\}$.
### 3.2.2 Operations in $\mathcal{Z}$

Our method allows us to create a space $\mathcal{Z}$ where graph representations are organized linearly. As a result, it is possible to produce a simple and efficient predictive model within $\mathcal{Z}$. As $\Phi$ is a nonlinear function, we can specify a nonlinear predictive model $f: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \to \mathbb{R}$ by specifying a linear predictive model $g: \mathcal{Z} \to \mathbb{R}$, such that $f(\mathbf{X}, \mathbf{A}) = g(\Phi(\mathbf{X}, \mathbf{A}))$.

Consider the linear predictive model $g(\mathbf{z}) = \mathbf{z}^\top \varphi^*$, where $\varphi^* \in \mathcal{Z}$ are its parameters. We consider a ridge regression in the latent space, allowing us to find the best parameters $\varphi^*$ by minimizing the regularized mean-squared error, expressed by

$$ \min_{\varphi} \frac{1}{N} \sum_{i=1}^{N} \left( y_i - \Phi(\mathbf{X}_i, \mathbf{A}_i)^\top \varphi \right)^2 + \lambda \|\varphi\|_2^2, $$

where the importance of the regularization term is weighted by $\lambda$. By nullifying its gradient, we get:

$$ \varphi^* = (\mathbf{Z}^\top \mathbf{Z} + \lambda \mathbb{I}_D)^{-1} \mathbf{Z}^\top \mathbf{y}. \qquad (8) $$

Thus, once $\varphi^*$ is computed using the equation (8), we obtain the optimal predictive model $g$ and by coupling the latter with the function $\Phi$, defining the nonlinear predictive model $f: \mathbb{R}^{n \times d} \times \mathbb{R}^{n \times n \times e} \to \mathbb{R}$. The use of this method allows a quantitative value of any graph $G \in \mathcal{G}$ to be predicted by converting it into a matrix representation $(\mathbf{X}, \mathbf{A})$, then applying the predictive model with $f(\mathbf{X}, \mathbf{A}) = \Phi(\mathbf{X}, \mathbf{A})^\top \varphi^*$.

In addition, $\Phi^{-1}$ allows us to compute the graph pre-image for any point of interest sampled in the latent space. We propose a method for generating graph pre-images to obtain new data from a desired quantitative label $y$. Our regression approach establishes a linear relation between quantitative labels and their positions in the latent space. Specifically, we intentionally associate the Gaussian distribution characterized by $(\mu_{\min}, \Sigma_{\min})$ with the minimum quantitative label in $Y$, and the Gaussian distribution defined by $(\mu_{\max}, \Sigma_{\max})$ with the maximum quantitative label in $Y$. This association allows us to determine the mean position $\mu_y$ associated to a quantitative label $y$ using (6). Afterwards, a point $\mathbf{z}$ can be sampled from the Gaussian distribution parameterized by $(\mu_y, \Sigma_y)$, according to $\mathbf{z} \sim \mathcal{N}(\mu_y, \sigma^2 \mathbb{I}_D)$. Finally, the graph pre-image is obtained with $(\hat{\mathbf{X}}, \hat{\mathbf{A}}) = \Phi^{-1}(\mathbf{z})$, then converting the result into a graph $\hat{G} \in \mathcal{G}$.

## 3.3 Extension of latent space dimension

We propose an extension of our approach in order to improve its performance. Given an input space $\mathcal{G}$ of $D$ dimensions, the use of a GraphNF implies the generation of a space $\mathcal{Z}$ limited to the same dimension as $\mathcal{G}$. Inspired by graph kernels that allow graphs to be encoded in a space of possibly higher dimension than the input space, we propose to increase the expressiveness of the latent space by manually increasing the number of dimensions in the input space. This process has the effect of increasing the number of dimensions in the latent space.

We increase the number of node features by appending them with $p$ zeros. Thus, we represent the graph data by $G = (\mathbf{X}, \mathbf{A})$ with the unchanged adjacency tensor $\mathbf{A}$ and the augmented feature matrix $\mathbf{X} \in \mathbb{R}^{n \times (d+p)}$. Figure 2 illustrates this extension.
<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration of the proposed extension, consisting in increasing the number of node feature dimensions (orange) with $p = 2$.</figcaption></figure>

# 4 Experiments

We evaluate our framework on classification and regression graph datasets<fnref n="1" />, by answering three distinct questions:

**Q1** Is the latent space generated by our classification method effective for classification purposes? (Section 4.1)

**Q2** Does our regression method generate an efficient latent space for regression applications? (Section 4.2)

**Q3** Is the generation capacity of our models relevant and consistent? (Section 4.3)

Several well-known datasets were used in the experiments. In general, when representing molecules with graphs, the nodes are associated with atoms and edges with the chemical bonds.

**Classification datasets AIDS** (Riesen et al., 2008) is composed of 2000 molecular graphs. By removing graphs with more than 25 nodes, we got a dataset to 1748 graphs. The predictive task aims at predicting the anti-HIV activity of the molecule (present or absent). **MUTAG** (Debnath et al., 1991) contains 188 chemical compounds. Each graph comprises up to 28 nodes. The 2 classes indicate if the chemical compound is mutagenic or non-mutagenic. **Letter datasets** (Riesen et al., 2008) is a collection of three datasets, each composed of 2300 attributed node graph representing 15 different uppercase letters. Each graph contains up to 9 nodes, where each node has 2 dimensional features representing its position. The nodes are connected by unlabelled edges corresponding to the lines. The three datasets, Letter-low, Letter-med and Letter-high, are distinguished by the deformation force applied to the graphs, which is low, medium and high respectively.

**Regression datasets QM7** (Rupp et al., 2012; Blum and Reymond, 2009) quantum chemistry dataset consists of small organic molecules with up to 7 heavy atoms (excluding hydrogen). It contains 7165 molecules. The prediction task used in our experiments consists in predicting the atomization energy of each molecule. **ESOL** (De Laney, 2004) consists of 1128 molecules with a maximum size of 55 atoms. The nodes of the graphs correspond to atoms, selected from a set of 9 different atom types. By

<footnote n="1">¹To ensure reproducibility, all experiments can be carried out using the GitHub repository: https://github.com/clement-g28/nf-kernel.</footnote>
filtered out molecules with more than 25 atoms, we get a dataset of 1068 graphs. The prediction task consists in predicting the solubility measure of each molecule. **FREESOLV** (Mobley and Guthrie, 2014) contains 643 small molecules, represented by labeled node graphs, on which information on experimental and computed hy- dration free energies is given. Each graph is composed of a maximum of 24 nodes representing the atoms of the molecule.

In this paper, we evaluate our framework using the GraphNF MoFlow, where we omit the molecular correction step in the case where the data do not represent molecules. We compare our framework with graph kernel methods. For datasets of labeled node graphs, we used the graph kernels Weisfeiler-Lehman (WL) (Shervashidze et al., 2011), Shortest path (SP) (Borgwardt and Kriegel, 2005) and Hadamard code (Hadcode) (Kataoka and Inokuchi, 2016). For datasets of attributed node graph, we used the graph kernels Propagation (Neumann et al., 2016) and Multi-scale Laplacian (MSLap) (Kondor and Pan, 2016). Moreover, as our method involves using a ridge regression on the flattened graph representations concatenated in the latent space, we assess our performance against traditional kernels that operate on the concatenation of flattened graph representations ($X_i, A_i$). From this, we applied the linear, RBF, polynomial and sigmoid kernels. In addition, the ability to generate pre-images is compared to the approach described in Bakır et al. (2004a), used on the kernel methods previously mentioned.

The used protocol, presented here for reproducibility, is as follows<fnref n="2" />: When the official allocation is not known, we divided the datasets by allocating 80% of the data to model learning, 10% to evaluation and the remaining 10% to testing.

As a graph containing *n* nodes can be represented in *n!* unique ways with the representation ($\mathbf{X}, \mathbf{A}$), the models were trained by incorporating a random permutation transformation of the used graph data. In addition, to test the permutation variability of our method, we computed each experiment using random permutations 20 times and thus, the results are reported as a pair of values indicating the mean performance and its standard deviation.

## 4.1 Classification

We aim to evaluate the latent space for classification (Q1) with two types of datasets, labelled node graphs (e.g. MUTAG) and attributed node graphs (e.g. Letter datasets). The performances are given in Table 1. The results obtained on MUTAG show that our method allows an improvement on the classification performance compared to standard kernels and some graph kernels, while providing the inverse transform. When considering the Letter datasets, our approach consistently outperforms all other kernels in terms of classification performance.

In addition, we evaluate the performance of our model by increasing the dimensions of the latent space according to the extension explained in Section 3.3. The last line of Table 1 shows the obtained results. These results show that the extension of our method has a favorable impact on the classification performances obtained on Letter datasets. However, the similar classification performance obtained on MUTAG suggests that increasing the number of dimensions is not useful in all situations. Indeed, we assume that the size of the observation data in MUTAG is already large enough

<footnote n="2">²The kernel parameters were set by cross-validation on a search grid, with a selection of 10 $\lambda$ values spanning from $10^{-5}$ to $10^2$. A logarithmic scale was employed for the classical kernels to select 5 weighting values to be applied on the similarity measure, ranging from $10^{-5}$ to $10^3$. The power value of the polynomial kernel was selected among a set of candidates {1, 2, 3, 4}.</footnote>
<table><caption>Table 1: Classification accuracy (± standard deviation), with the best result in bold and second-best underlined.</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="5">Datasets</th></tr><tr><th>AIDS</th><th>MUTAG</th><th>Letter-low</th><th>Letter-med</th><th>Letter-high</th></tr></thead><tbody><tr><td rowspan="4">Standard Kernels</td><td>Linear</td><td>0.989 ± 0.003</td><td>0.719 ± 0.054</td><td>0.594 ± 0.027</td><td>0.428 ± 0.026</td><td>0.358 ± 0.022</td></tr><tr><td>RBF</td><td>0.980 ± 0.006</td><td>0.711 ± 0.060</td><td>0.566 ± 0.024</td><td>0.421 ± 0.028</td><td>0.339 ± 0.020</td></tr><tr><td>Polynomial</td><td>0.979 ± 0.007</td><td>0.650 ± 0.078</td><td>0.591 ± 0.026</td><td>0.414 ± 0.030</td><td>0.344 ± 0.022</td></tr><tr><td>Sigmoid</td><td>0.983 ± 0.008</td><td>0.661 ± 0.094</td><td>0.313 ± 0.026</td><td>0.292 ± 0.023</td><td>0.241 ± 0.023</td></tr><tr><td rowspan="5">Graph Kernels</td><td>WL</td><td><b>0.994</b> ± 0.000</td><td>0.778 ± 0.000</td><td>-</td><td>-</td><td>-</td></tr><tr><td>SP</td><td><b>0.994</b> ± 0.000</td><td>0.778 ± 0.000</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Hadcode</td><td><b>0.994</b> ± 0.000</td><td><b>0.889</b> ± 0.000</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Propagation</td><td>-</td><td>-</td><td>0.472 ± 0.186</td><td>0.267 ± 0.066</td><td>0.226 ± 0.049</td></tr><tr><td>MSLap</td><td>-</td><td>-</td><td>0.860 ± 0.031</td><td>0.469 ± 0.043</td><td>0.229 ± 0.025</td></tr><tr><td rowspan="2">Our approach Extension</td><td>MoFlow</td><td><u>0.993</u> ± 0.002</td><td>0.786 ± 0.066</td><td><u>0.889</u> ± 0.017</td><td><u>0.799</u> ± 0.014</td><td><u>0.526</u> ± 0.024</td></tr><tr><td>MoFlow</td><td><b>0.994</b> ± 0.000</td><td><u>0.803</u> ± 0.054</td><td><b>0.918</b> ± 0.008</td><td><b>0.837</b> ± 0.018</td><td><b>0.570</b> ± 0.026</td></tr></tbody></table>

<table><caption>Table 2: R² score (± std) on regression (same legend as Table 1).</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="3">Datasets</th></tr><tr><th>QM7</th><th>ESOL</th><th>FREESOLV</th></tr></thead><tbody><tr><td rowspan="4">Standard Kernels</td><td>Linear</td><td>0.680 ± 0.004</td><td>0.453 ± 0.047</td><td>0.051 ± 0.052</td></tr><tr><td>RBF</td><td>0.677 ± 0.004</td><td>0.451 ± 0.062</td><td>0.055 ± 0.054</td></tr><tr><td>Polynomial</td><td>0.678 ± 0.004</td><td>0.458 ± 0.057</td><td>0.051 ± 0.052</td></tr><tr><td>Sigmoid</td><td>0.652 ± 0.005</td><td>0.455 ± 0.058</td><td>0.068 ± 0.033</td></tr><tr><td rowspan="3">Graph Kernels</td><td>WL</td><td>0.481 ± 0.000</td><td>0.480 ± 0.000</td><td><u>0.871</u> ± 0.000</td></tr><tr><td>SP</td><td><b>0.718</b> ± 0.000</td><td>0.458 ± 0.000</td><td>0.536 ± 0.000</td></tr><tr><td>Hadcode</td><td>0.481 ± 0.000</td><td>0.451 ± 0.000</td><td><b>0.876</b> ± 0.000</td></tr><tr><td rowspan="2">Our approach Extension</td><td>MoFlow</td><td>0.707 ± 0.006</td><td><b>0.683</b> ± 0.035</td><td>0.605 ± 0.045</td></tr><tr><td>MoFlow</td><td><u>0.714</u> ± 0.006</td><td><u>0.642</u> ± 0.026</td><td>0.611 ± 0.067</td></tr></tbody></table>

to differentiate the 2 classes, so there is no need to add additional dimensions. On the other hand, Letter datasets contain smaller graphs with a limited number of node features that need to be classified into 15 distinct categories, thus increasing the latent space helps the model to distinguish between data from different classes.

## 4.2 Regression

In order to answer **Q2**, Table 2 shows the average regression performance and standard deviation. The results demonstrate the effective predictive capacity of our approach employing linear regression within the latent space Z for the majority of the datasets. Nevertheless, the best performance for the FREESOLV dataset is achieved when using the WL and the Hadamard code graph kernels. To explain this observation, it is important to point out that the FREESOLV dataset consists of fewer graphs, that are also larger in size when compared to other datasets like QM7. In addition, the predictions values in FREESOLV are non-uniformly distributed with over 97% falling between -2.57 and 1.79, while the whole range goes from -5.48 to 1.79. Consequently, the linear regression employed in this paper is probably not the most suitable for this type of dataset. Nevertheless, our approach has an advantage over graph kernels: having trained the model, predictions can be made directly and with minimal effort, unlike graph kernel methods, which can involve higher computational costs. Furthermore,
<figure><img src="image_4.png" /><figcaption>Figure 3: Pre-images generated from 8 points sampled in $\mathcal{Z}$ according to each Gaussian distribution associated with each class on the MUTAG dataset.</figcaption></figure>

the results show non-zero standard deviations in our performances, caused by the used graph representations. This contrasts with graph kernels, which are intentionally designed to remain permutations invariant. In addition, the last row of Table 2 shows that the extension introduced in the Section 3.3 changes slightly the results of these regression experiments.

## 4.3 Pre-image quality

To answer **Q3** and assess our model's capacity to produce graph pre-images, we used our trained models to generate molecular graphs from sample points in $\mathcal{Z}$ for both tasks.

**Classification pre-images** Graph pre-image generation is evaluated on MUTAG, by randomly sampling 8 points in $\mathcal{Z}$ for each class, namely by applying $z \sim N(\mu_c, \Sigma_c)$ with $c \in \{1...C\}$. The graph pre-images were generated in the input space by applying the inverse transformation $\Phi^{-1}$ to the sampled $z$. These are presented in Figure 3, together with the values of the used class $y$ and the predicted class $f(\mathbf{X}, \mathbf{A})$ using our prediction model.

**Regression pre-images** The capacity to generate graph pre-images in a regression context is evaluated on QM7 as follows. We first sample 8 values of $y$ between $\min(Y)$ and $\max(Y)$ and then, for every $y$, we sample $z \sim N(\mu_y, \sigma^2 I_D)$ where $\mu_y$ is computed according to (6). Finally, we generate the graph pre-images using $\Phi^{-1}$ on the sampled $z$. Figure 4 displays the graph pre-images along with their sampled quantitative values $y$ and their predicted values $f(\mathbf{X}, \mathbf{A})$ obtained from our model.

These experiments illustrate the capacity to generate consistent pre-images, allowing to answer **Q3** affirmatively.

## 5 Conclusion

We introduced a framework defining ML models that are insensitive to the pre-image problem. In addition, two different specifications were proposed to address the pre-
<figure><img src="image_5.png" /><figcaption>Figure 4: Pre-images generated from 8 points sampled uniformly in $Z$ between $min(Y)$ and $max(Y)$ on the QM7 dataset.</figcaption></figure>

dictive tasks of classification and regression. Our framework allowed the supervised generation of a latent space in which linear classification or regression can be efficiently performed, as demonstrated by our experiments. Moreover, it offered improved interpretability, thanks to the learned inverse transformation, which allowed to generate graph pre-images of points of interest.

Although the used graph representation makes our methodology sensitive to node permutation in graphs, it could be relevant to apply it to other types of graph representations, which could eventually lead to permutation invariance.

## Acknowledgements

The authors acknowledge the support of the French *Agence Nationale de la Recherche*, under grant ANR-18-CE23-0014.

## References

G. H. Bakır, J. Weston, and B. Schölkopf. Learning to find pre-images. *Advances in neural information processing systems*, 16:449–456, 2004a.

G. H. Bakır, A. Zien, and K. Tsuda. Learning to find graph pre-images. In *Pattern Recognition: 26th DAGM Symposium, Tübingen, Germany, August 30-September 1, 2004. Proceedings 26*, pages 253–261. Springer, 2004b.

M. Balcilar, G. Renton, P. Héroux, B. Gaüzère, S. Adam, and P. Honeine. Analyzing the expressive power of graph neural networks in a spectral perspective. In *International Conference on Learning Representations*, Vienna, Austria, 2021.

L. C. Blum and J.-L. Reymond. 970 million druglike small molecules for virtual screening in the chemical universe database gdb-13. *Journal of the American Chemical Society*, 131(25):8732–8733, 2009.

K. M. Borgwardt and H.-P. Kriegel. Shortest-path kernels on graphs. In *Fifth IEEE international conference on data mining (ICDM'05)*, pages 8–pp. IEEE, 2005.
N. De Cao and T. Kipf. Molgan: An implicit generative model for small molecular graphs. *ICML 2018 workshop on Theoretical Foundations and Applications of Deep Generative Models*, 2018.

A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. *Journal of medicinal chemistry*, 34(2):786-797, 1991.

J. S. Delaney. Esol: estimating aqueous solubility directly from molecular structure. *Journal of chemical information and computer sciences*, 44(3):1000–1005, 2004.

C. Glédel, B. Gaüzère, and P. Honeine. Graph normalizing flows to pre-image free machine learning for regression. In *International Workshop on Graph-Based Representations in Pattern Recognition*, pages 92–101. Springer, 2023.

X. Guo and L. Zhao. A systematic survey on deep generative models for graph generation. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 2022.

S. Honda, H. Akita, K. Ishiguro, T. Nakanishi, and K. Oono. Graph residual flow for molecular graph generation. preprint arXiv:1909.13521, 2019.

P. Honeine and C. Richard. Preimage problem in kernel-based machine learning. *IEEE Signal Processing Magazine*, 28(2):77–88, Mar. 2011.

L. Jia, B. Gaüzère, and P. Honeine. A graph pre-image method based on graph edit distances. In *Proc. of IAPR Joint International Workshops on Statistical techniques in Pattern Recognition (SPR 2020) and Structural and Syntactic Pattern Recognition (SSPR 2020)*., 2021.

L. Jia, B. Gaüzère, and P. Honeine. Graph kernels based on linear patterns: theoretical and experimental comparisons. *Expert Systems With Applications*, 189:116095, 2022. ISSN 0957-4174.

T. Kataoka and A. Inokuchi. Hadamard code graph kernels for classifying graphs. In *ICPRAM*, pages 24–32, 2016.

D. P. Kingma and P. Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In *Advances in neural information processing systems*, pages 10215–10224, 2018.

I. Kobyzev, S. J. Prince, and M. A. Brubaker. Normalizing flows: An introduction and review of current methods. *IEEE transactions on pattern analysis and machine intelligence*, 43(11):3964–3979, 2020.

R. Kondor and H. Pan. The multiscale laplacian graph kernel. *Advances in neural information processing systems*, 29, 2016.

J. Liu, A. Kumar, J. Ba, J. Kiros, and K. Swersky. Graph normalizing flows. *Advances in Neural Information Processing Systems*, 32, 2019.

K. Madhawa, K. Ishiguro, K. Nakago, and M. Abe. Graphnvp: An invertible flow model for generating molecular graphs. *arXiv preprint arXiv:1905.11600*, 2019.
D. L. Mobley and J. P. Guthrie. Freesolv: a database of experimental and calculated hydration free energies, with input files. *Journal of computer-aided molecular design*, 28:711–720, 2014.

M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting. Propagation kernels: efficient graph kernels from propagated information. *Machine Learning*, 102:209–245, 2016.

K. Riesen, H. Bunke, et al. Iam graph database repository for graph based pattern recognition and machine learning. In *SSPR/SPR*, volume 5342, pages 287–297, 2008.

M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. Von Lilienfeld. Fast and accurate modeling of molecular atomization energies with machine learning. *Physical review letters*, 108(5):058301, 2012.

N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borg-wardt. Weisfeiler-lehman graph kernels. *Journal of Machine Learning Research*, 12 (9), 2011.

C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. In *International Conference on Learning Representations*, 2020.

T. Tran Thi Phuong, A. Douzal, S. V. Yazdi, P. Honeine, and P. Gallinari. Interpretable time series kernel analytics by pre-image estimation. *Artificial Intelligence*, 286:103342, Sept. 2020. ISSN 0004-3702.

C. Zang and F. Wang. Moflow: an invertible flow model for generating molecular graphs. In *Proc. of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining*, pages 617–626, 2020.

F. Zhu and P. Honeine. Online kernel nonnegative matrix factorization. *Signal Processing*, 131:143–153, Feb. 2017. ISSN 0165-1684.