GDLNN: Marriage of Programming Language and Neural Networks for Accurate and Easy-to-Explain Graph Classification

## Abstract

Abstract We present GDLNN, a new graph machine learning architecture, for graph classification tasks.
GDLNN combines a domain-specific programming language, called GDL, with neural networks.
The main strength of GDLNN lies in its GDL layer, which generates expressive and interpretable graph representations.
Since the graph representation is interpretable, existing model explanation techniques can be directly applied to explain GDLNN’s predictions.
Our evaluation shows that the GDL-based representation achieves high accuracy on most graph classification benchmark datasets, outperforming dominant graph learning methods such as GNNs.
Applying an existing model explanation technique also yields high-quality explanations of GDLNN’s predictions. Furthermore, the cost of GDLNN is low when the explanation cost is included.

## 1 Introduction

In graph classification, graph representation learning holds the key to success.
The goal of this task is to learn useful feature representations (embeddings) for the entire graph that effectively capture its key structure and properties.
These representations are utilized in various graph machine learning tasks, including graph classification.
Beyond predictive performance, learning interpretable graph representations has become increasingly important, as it directly impacts model explainability, crucial in decision-critical domains such as drug discovery (Kakkad et al., 2023).
Despite the dual requirement of both accuracy and explainability, generating effective and interpretable graph representations for entire graphs remains a key challenge.

Current Trends and Limitations.
Currently, the dominant approach to graph representation learning for graph-level tasks is the combination of graph neural networks (GNNs) and graph pooling operations (Wu et al., 2021).
GNNs perform message passing to generate node and edge representations that capture local structures.
After message passing, a pooling operation aggregates the node- and edge-level representations into a single graph-level representation (Grattarola et al., 2024).

During this two-step process, the resulting graph-level representation loses substantial structural information, which degrades both accuracy and explainability.
Because the graph-level representation is a complex mixture of all node and edge features, important structural details are often obscured or lost during aggregation.
This loss restricts the model’s ability to capture key patterns crucial for accurate predictions, while also limiting its ability to explain graph classification results.
For example, standard model explanation techniques that identify key features of the representation are inapplicable for explaining GNNs (Yuan et al., 2022).
As a result, GNNs are explained using inefficient and indirect methods (Jeon et al., 2024).

Our Approach.
To address these problems, we present GDLNN (Graph Description Language + Neural Network), a novel architecture that generates interpretable graph representations that preserve key graph structures.
GDLNN leverages a domain-specific programming language, GDL (Graph Description Language (Jeon et al., 2024)), to explicitly capture key graph patterns as representations.
During training, GDLNN mines a set of high-quality GDL programs that capture discriminative patterns across the training graphs.
Each GDL program describes a specific graph pattern, enabling GDLNN to represent graphs as collections of such patterns through its GDL layer.
The resulting representation is then fed into a Multi-Layer Perceptron (MLP) for classification, combining the interpretability of programming languages with the predictive power of neural networks.

Results.
Our evaluation shows that GDLNN achieves high accuracy on most of graph classification benchmarks, and its predictions can be explained using standard model explanation techniques.
For example, GDLNN consistently outperforms popular GNNs across these datasets.
Combination of GDLNN with a standard model explanation technique Lime (Ribeiro et al., 2016) also achieves better explainability than GNNs with state-of-the-art GNN explanation techniques SubgraphX (Yuan et al., 2021).
In addition, GDLNN is efficient when explanation costs are taken into account.

Contributions. We summarize our contributions as follows:

- •
We present GDLNN, a novel graph machine learning architecture that combines a domain-specific programming language (GDL) with neural networks (NN).
- •
We experimentally demonstrate that GDLNN achieves high accuracy on graph classification benchmarks and can provide high-quality explanations through applying existing model explanation techniques. Also, GDLNN is fast when the explanation cost is included.

## 2 Related Works

Graph Neural Networks.
Graph Neural Networks (GNNs) are dominant methods in graph machine learning because of their high accuracy.
In graph classification, GNNs (Hamilton et al., 2017; Defferrard et al., 2016) perform a message-passing procedure to generate node and edge representations that capture local structure (i.e., neighborhood information).
For instance, GCN (Kipf & Welling, 2017) is a simplified convolutional network that uses a localized first-order approximation of spectral graph convolutions.
GAT (Veličković et al., 2018) learns to weigh the importance of neighboring nodes via attention mechanisms, enabling more relevant neighbors to contribute more when updating a node’s representation.
GIN (Xu et al., 2019) aggregates neighbor features using a sum operation and applies an MLP, making it as powerful as the Weisfeiler-Lehman graph isomorphism test in distinguishing graph structures.
After message passing, GNNs apply a pooling mechanism to aggregate node representations into a single representation of the entire graph (Grattarola et al., 2024).
During this two-step process, the graph-level representation loses significant structural information.
This not only degrades accuracy but also makes the representation difficult to interpret; the predictions of GNNs are challenging to explain (Kakkad et al., 2023).

Explainable Graph Machine Learning.
To achieve both accuracy and explainability, several graph machine learning methods have been proposed.
A mainstream approach is to explain the predictions of GNNs (Kakkad et al., 2023).
For instance, GraphChef (Müller et al., 2023) aims to interpret a GNN model by learning a decision tree that is faithful to it.
SubgraphX (Yuan et al., 2021) generates subgraphs as explanations for GNN predictions.
Inherently explainable graph learning methods have also been explored.
For example, PL4XGL (Jeon et al., 2024) is an inherently explainable graph learning method that employs GDL programs for classification.
PL4XGL classifies a graph using the highest-weighted GDL program and provides it as an explanation.
However, existing explainable graph machine learning methods face limitations: inherently explainable approaches often suffer from low accuracy, while explaining GNN predictions is computationally costly and may not be faithful.
GDLNN addresses these limitations by combining a domain-specific programming language with neural networks.

Figure: (a) Graph $G_{1}$ (Label 1)

## 3 Overview

This section provides a high-level overview of how GDLNN works using a running example.

Example graphs.
Figures [1(a)](#S2.F1.sf1), [1(b)](#S2.F1.sf2), [1(c)](#S2.F1.sf3), and [1(d)](#S2.F1.sf4) depict four example directed graphs.
Each graph contains four nodes, each associated with a one-dimensional feature ranging from 1.0 to 4.0.
In $G_{1}$, for example, the successor of the node with feature value $\langle 4.0\rangle$ has a feature value of $\langle 2.0\rangle$.
Graphs $G_{1}$ and $G_{3}$ are labeled 1, while graphs $G_{2}$ and $G_{4}$ are labeled 2.
Our goal is to generate graph representations such that graphs with the same label have similar representations.

How GDLNN works.
Figure [1(e)](#S2.F1.sf5) and [1(f)](#S2.F1.sf6) show two example GDL programs that are used for generating two-dimensional graph representations.
A GDL program consists of node and edge variables, each associated with a vector of feature value constraints.
For example, the GDL program $P_{1}$ in Figure [1(e)](#S2.F1.sf5) contains three node variables ($x$, $y$, $z$) and two edge variables ($(x,y)$ and $(y,z)$).
The node variables $x$, $y$, and $z$ are associated with vectors of feature value constraints $\langle[3.0,4.0]\rangle$, $\langle[2.0,2.0]\rangle$, and $\langle[1.0,1.0]\rangle$, respectively.
In English, the GDL program $P_{1}$ describes the following graph pattern:

> “Graphs that contain a node with a feature value between 3.0 and 4.0, whose successor has a feature value of 2.0, and the successor also has a successor with a feature value of 1.0.”

For example, graphs $G_{1}$ and $G_{3}$ are described by the GDL program $P_{1}$, since a subgraph of each graph
(e.g.,
$\langle 2.0\rangle$
$\langle 4.0\rangle$
$\langle 1.0\rangle$
in $G_{1}$)
matches the pattern defined by $P_{1}$. In contrast, graphs $G_{2}$ and $G_{4}$ are not described by $P_{1}$.
The GDL program $P_{2}$ in Figure [1(f)](#S2.F1.sf6) captures a different graph pattern, described as follows:

> “Graphs that contain a node with a feature value of 1.0, whose successor has a feature value between 0.0 and 5.0, and the successor also has a successor with a feature value 1.0.”

$G_{2}$ (Figure [1(b)](#S2.F1.sf2)) and $G_{4}$ (Figure [1(d)](#S2.F1.sf4)) match this pattern, as their subgraphs
(
$\langle 2.0\rangle$
$\langle 1.0\rangle$
$\langle 1.0\rangle$
) satisfy the constraints defined by $P_{2}$.
In contrast, graphs $G_{1}$ and $G_{3}$ do not match this pattern.

Figure [1(g)](#S2.F1.sf7) illustrates the two-dimensional graph representations of the four graphs, generated using the GDL programs $P_{1}$ and $P_{2}$.
Each graph representation is a vector indicating whether the corresponding graph is described by each of the two GDL programs.
For example, graphs $G_{1}$ and $G_{3}$ have representations $\langle 1.0,0.0\rangle$, since they are described by $P_{1}$ but not by $P_{2}$.

Once the graph representations are generated, GDLNN uses a multi-layer perceptron (MLP) to classify the graphs.
That is, the performance of GDLNN depends on both the quality of the learned GDL programs and the effectiveness of the MLP.
During training, GDLNN learns a set of high-quality GDL programs that would generate similar representations for graphs with the same label, and trains the MLP to accurately classify the graphs based on the generated representations.

Explaining Classifications.
As the graph representations used in GDLNN are interpretable, existing model explanation techniques can be applied directly.
For example, Lime (Ribeiro et al., 2016) or SHAP (Lundberg & Lee, 2017) can be applied to identify the most important features of the graph representation, thereby explaining the classification results.
For instance, suppose Lime determines that the first feature of the graph representation is important when GDLNN classifies graph $G_{1}$ as label 1.
In this case, a user can identify that the GDL program $P_{1}$ corresponds to a key graph pattern driving the classification in GDLNN.

## 4 GDLNN

In this section, we formally define GDLNN.
We first introduce GDL, a domain-specific programming language for describing graph patterns, and then present the architecture of GDLNN.

Notations.
We consider a directed graph $G=(\mathcal{V},\mathcal{E},X^{\mathcal{V}},X^{\mathcal{E}})$, where $\mathcal{V}=\{v_{1},v_{2},\dots,v_{n}\}$ is the set of nodes, and $\mathcal{E}=\{e_{1},e_{2},\dots,e_{m}\}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges.
$X^{\mathcal{V}}\subseteq\mathbb{R}^{n\times d}$ and $X^{\mathcal{E}}\subseteq\mathbb{R}^{m\times c}$ are matrices of node and edge feature vectors, respectively.
$X^{\mathcal{V}}_{i}$ and $X^{\mathcal{E}}_{j}$ denote the feature vectors of node $v_{i}$ and edge $e_{j}$, respectively.

Figure: Figure 2: The syntax of GDL.

Figure: Figure 3: The semantics of GDL where $G=(\mathcal{V},\mathcal{E},X^{\mathcal{V}},X^{\mathcal{E}})$ is a graph.

### 4.1 GDL: Graph-Pattern Description Language

Syntax of GDL.
Figure [2](#S4.F2) illustrates the syntax of GDL.
$\overline{A}$ denotes a sequence of elements in $A$ (e.g., $\overline{A}=\langle A_{1},A_{2},\dots,A_{k}\rangle$).
A GDL program consists of a sequence of descriptions $\overline{\delta}$, where each description is either a node description ($\delta_{\mathcal{V}}$) or an edge description ($\delta_{\mathcal{E}}$).
A node (resp., edge) description combines a variable (e.g., node x or edge (x,y)) with a vector of intervals (e.g., ${{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[3.0,4.0],[1.0,2.0],\dots}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}$) that specifies the node’s (resp., edge’s) feature values.

Semantics of GDL.
We now define the semantics of GDL programs (i.e., the patterns they describe).
Figure [3](#S4.F3) presents the formal semantics of GDL.
Given a vector of intervals ${{{{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{\phi_{1}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language,}}}}\dots\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language,}}}}\phi_{k}}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}$, its semantics ${{{{\llbracket\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{\phi_{1}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language,}}}}\dots\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language,}}}}\phi_{k}}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\rrbracket$ defines a set of feature vectors in which the $i$-th feature value lies within the interval $\phi_{i}$.
For example, ${{\llbracket\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[3.0,4.0],[1.0,2.0]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\rrbracket$ defines the set of feature vectors $\{\langle 3.0,1.0\rangle,\dots,\langle 4.0,2.0\rangle\}$.
A valuation $\eta\in\mathbb{X}\to\mathcal{V}$ maps each node variable in the GDL program to a distinct node in a given graph $G=(\mathcal{V},\mathcal{E})$. That is, $(G,\eta)\in\llbracket\overline{\delta}\rrbracket$ indicates that a subgraph of $G$ is captured by the GDL program $P=\overline{\delta}$ via the valuation $\eta$.
For example, the GDL program $P_{1}$ in Figure [1(e)](#S2.F1.sf5) captures a subgraph of $G_{1}$ through the following valuation $\eta$, which defines the subgraph $G_{1}^{\prime}$:

$$ ${{{\eta=\{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}x}}}}}}\to\resizebox{43.36464pt}{}{ \hbox to35.4pt{\vbox to17.07pt{\pgfpicture\makeatletter\hbox{\qquad\lower-8.533pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{13.50002pt}{8.33301pt}\pgfsys@lineto{-13.50002pt}{8.33301pt}\pgfsys@curveto{-15.70918pt}{8.33301pt}{-17.50002pt}{6.54218pt}{-17.50002pt}{4.33301pt}\pgfsys@lineto{-17.50002pt}{-4.33301pt}\pgfsys@curveto{-17.50002pt}{-6.54218pt}{-15.70918pt}{-8.33301pt}{-13.50002pt}{-8.33301pt}\pgfsys@lineto{13.50002pt}{-8.33301pt}\pgfsys@curveto{15.70918pt}{-8.33301pt}{17.50002pt}{-6.54218pt}{17.50002pt}{-4.33301pt}\pgfsys@lineto{17.50002pt}{4.33301pt}\pgfsys@curveto{17.50002pt}{6.54218pt}{15.70918pt}{8.33301pt}{13.50002pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{-17.50002pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.50002pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 4.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}} },\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}y}}}}}}\to\resizebox{43.36464pt}{}{ \hbox to35.4pt{\vbox to17.07pt{\pgfpicture\makeatletter\hbox{\qquad\lower-8.533pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{13.50002pt}{8.33301pt}\pgfsys@lineto{-13.50002pt}{8.33301pt}\pgfsys@curveto{-15.70918pt}{8.33301pt}{-17.50002pt}{6.54218pt}{-17.50002pt}{4.33301pt}\pgfsys@lineto{-17.50002pt}{-4.33301pt}\pgfsys@curveto{-17.50002pt}{-6.54218pt}{-15.70918pt}{-8.33301pt}{-13.50002pt}{-8.33301pt}\pgfsys@lineto{13.50002pt}{-8.33301pt}\pgfsys@curveto{15.70918pt}{-8.33301pt}{17.50002pt}{-6.54218pt}{17.50002pt}{-4.33301pt}\pgfsys@lineto{17.50002pt}{4.33301pt}\pgfsys@curveto{17.50002pt}{6.54218pt}{15.70918pt}{8.33301pt}{13.50002pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{-17.50002pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.50002pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 2.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}} },\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}z}}}}}}\to\resizebox{43.36464pt}{}{ \hbox to35.4pt{\vbox to17.07pt{\pgfpicture\makeatletter\hbox{\qquad\lower-8.533pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{13.50002pt}{8.33301pt}\pgfsys@lineto{-13.50002pt}{8.33301pt}\pgfsys@curveto{-15.70918pt}{8.33301pt}{-17.50002pt}{6.54218pt}{-17.50002pt}{4.33301pt}\pgfsys@lineto{-17.50002pt}{-4.33301pt}\pgfsys@curveto{-17.50002pt}{-6.54218pt}{-15.70918pt}{-8.33301pt}{-13.50002pt}{-8.33301pt}\pgfsys@lineto{13.50002pt}{-8.33301pt}\pgfsys@curveto{15.70918pt}{-8.33301pt}{17.50002pt}{-6.54218pt}{17.50002pt}{-4.33301pt}\pgfsys@lineto{17.50002pt}{4.33301pt}\pgfsys@curveto{17.50002pt}{6.54218pt}{15.70918pt}{8.33301pt}{13.50002pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{-17.50002pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.50002pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 1.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}} }\},\;\;G_{1}^{\prime}=\resizebox{130.08731pt}{}{ \hbox to124.54pt{\vbox to30.8pt{\pgfpicture\makeatletter\hbox{\hskip 62.26888pt\lower-15.39902pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{\the\pgflinewidth}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{13.50002pt}{8.33301pt}\pgfsys@lineto{-13.50002pt}{8.33301pt}\pgfsys@curveto{-15.70918pt}{8.33301pt}{-17.50002pt}{6.54218pt}{-17.50002pt}{4.33301pt}\pgfsys@lineto{-17.50002pt}{-4.33301pt}\pgfsys@curveto{-17.50002pt}{-6.54218pt}{-15.70918pt}{-8.33301pt}{-13.50002pt}{-8.33301pt}\pgfsys@lineto{13.50002pt}{-8.33301pt}\pgfsys@curveto{15.70918pt}{-8.33301pt}{17.50002pt}{-6.54218pt}{17.50002pt}{-4.33301pt}\pgfsys@lineto{17.50002pt}{4.33301pt}\pgfsys@curveto{17.50002pt}{6.54218pt}{15.70918pt}{8.33301pt}{13.50002pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{-17.50002pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-9.50002pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 2.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} {}{ {}{}{}}{{{ {}{}{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{{}{}}}{{}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{-30.43584pt}{8.33301pt}\pgfsys@lineto{-57.43587pt}{8.33301pt}\pgfsys@curveto{-59.64503pt}{8.33301pt}{-61.43587pt}{6.54218pt}{-61.43587pt}{4.33301pt}\pgfsys@lineto{-61.43587pt}{-4.33301pt}\pgfsys@curveto{-61.43587pt}{-6.54218pt}{-59.64503pt}{-8.33301pt}{-57.43587pt}{-8.33301pt}\pgfsys@lineto{-30.43584pt}{-8.33301pt}\pgfsys@curveto{-28.22667pt}{-8.33301pt}{-26.43584pt}{-6.54218pt}{-26.43584pt}{-4.33301pt}\pgfsys@lineto{-26.43584pt}{4.33301pt}\pgfsys@curveto{-26.43584pt}{6.54218pt}{-28.22667pt}{8.33301pt}{-30.43584pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{-61.43587pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-53.43587pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 4.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} {}{ {}{}{}}{{{{}{}{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{} {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{ }{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{{}{}{{}}}{{}{}{{}}}{}{}{}\pgfsys@moveto{57.43587pt}{8.33301pt}\pgfsys@lineto{30.43584pt}{8.33301pt}\pgfsys@curveto{28.22667pt}{8.33301pt}{26.43584pt}{6.54218pt}{26.43584pt}{4.33301pt}\pgfsys@lineto{26.43584pt}{-4.33301pt}\pgfsys@curveto{26.43584pt}{-6.54218pt}{28.22667pt}{-8.33301pt}{30.43584pt}{-8.33301pt}\pgfsys@lineto{57.43587pt}{-8.33301pt}\pgfsys@curveto{59.64503pt}{-8.33301pt}{61.43587pt}{-6.54218pt}{61.43587pt}{-4.33301pt}\pgfsys@lineto{61.43587pt}{4.33301pt}\pgfsys@curveto{61.43587pt}{6.54218pt}{59.64503pt}{8.33301pt}{57.43587pt}{8.33301pt}\pgfsys@closepath\pgfsys@moveto{26.43584pt}{-8.33301pt}\pgfsys@stroke\pgfsys@invoke{ } \pgfsys@invoke{ }\pgfsys@endscope}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{34.43584pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{19.00003pt}\hbox{}{$\langle 1.0\rangle$}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} { {}{}{}}{{{ {}{}{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.00002pt}{-12.06601pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{30.00005pt}\hbox{}{}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} { {}{}{}}{{{ {}{}{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-58.93587pt}{-12.06601pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{30.00005pt}\hbox{}{}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} { {}{}{}}{{{ {}{}{}}}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.93584pt}{12.06601pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{\minipage[t]{30.00005pt}\hbox{}{}\endminipage} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} { {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}\pgfsys@moveto{-26.23584pt}{0.0pt}\pgfsys@lineto{-17.70001pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}\pgfsys@beginscope\pgfsys@invoke{ } {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {{}} {{}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{2.0}{0.0}{0.0}{2.0}{-21.69997pt}{0.0pt}\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}}}} \pgfsys@invoke{ }\pgfsys@endscope}\pgfsys@invoke{ }\pgfsys@endscope}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {{}} } \pgfsys@invoke{ }\pgfsys@endscope}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-21.96793pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} { {}{}{}}{}{ {}{}{}} {{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}\pgfsys@moveto{17.70001pt}{0.0pt}\pgfsys@lineto{26.23584pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }{\pgfsys@beginscope\pgfsys@invoke{ } {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}}{{{{}{}{{}} }}{{}}\pgfsys@beginscope\pgfsys@invoke{ } {\pgfsys@beginscope\pgfsys@invoke{ }{{}} {{}} {{}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{2.0}{0.0}{0.0}{2.0}{22.23589pt}{0.0pt}\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@invoke{ }\pgfsys@endscope}}{{}}}} \pgfsys@invoke{ }\pgfsys@endscope}\pgfsys@invoke{ }\pgfsys@endscope}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {{}} } \pgfsys@invoke{ }\pgfsys@endscope}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{21.96793pt}{0.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{}}} }}\pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope}}} \pgfsys@invoke{ }\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{ }\pgfsys@endscope\hss}}\endpgfpicture}} }$ $$

Figure: Figure 4: Architecture of GDLNN
Refer to caption: /html/2510.00374/assets/x1.png

### 4.2 Architecture of GDLNN

Figure [4](#S4.F4) shows the architecture of GDLNN, which consists of GDL layer and NN layers.

GDL Layer.
Each perceptron in the GDL layer is associated with a GDL program $P_{i}$ mined during the training phase.
Details of the training phase are presented in Section [5](#S5).
The output of the $i$-th perceptron is determined by an activation function $\sigma(P_{i},G)$, defined as:

$$ $\sigma(P_{i},G)=\left\{\begin{array}[]{ccl}1.0&&\mbox{if}~G\models P_{i}\\ 0.0&&\mbox{otherwise}\end{array}\right.$ $$

where $G\models P_{i}$ indicates that the graph $G$ satisfies the pattern defined by $P_{i}$:

$$ $G\models P\iff\exists\eta.\;(G,\eta)\in\llbracket P\rrbracket.$ $$

Note that the activation function $\sigma$ is a design choice.
Due to space limitations, alternative choices are discussed in Appendix [A](#A1).

MLP Layers.
The MLP layers consist of standard multi-layer perceptrons.
The MLP takes the generated graph representation as input and produces a classification output for the graph.

## 5 Learning GDLNN

Now we present the learning procedure of GDLNN.
The learning procedure of GDLNN consists of two sequential steps: 1) mining GDL programs and 2) training the MLP.
Let $\mathcal{D}=\{(G_{i},y_{i})\}_{i=1}^{m}$ be a training dataset (consists of $m$ graphs) where each $G_{i}$ represents a graph and $y_{i}\in L$ is its corresponding label ($L$ is the set of labels).
For convenience, we define $\mathcal{D}_{y}=\{(G_{i},y_{i})\mid(G_{i},y_{i})\in\mathcal{D},y_{i}=y\}$ as the training graphs in $\mathcal{D}$ with label $y$.

### 5.1 Mining GDL Programs

The learning procedure first mines GDL programs that will be used in the GDL layer.

Objective.
The objective of this procedure is to mine GDL programs that generate high-quality graph representations.
To this end, our algorithm mines GDL programs that describe graphs having the same labels while excluding graphs with different labels.
We expect that such mined GDL programs will produce high-quality graph representations.
The detailed objective is presented in Appendix [B](#A2).

Figure: Algorithm 1 Overall GDL program mining procedure

GDL Program Mining.
Algorithm [1](#alg1) presents the overall GDL program mining procedure.
The procedure takes a training dataset $\mathcal{D}=\{(G_{i},y_{i})\}_{i=1}^{m}$ as input and outputs a set of GDL programs $\mathcal{P}$.
Lines 3–5 describe the process of mining and collecting a GDL program from each training graph.
At line 4, a GDL program $P$ is mined using the procedure $\textsc{Mine}_{\textit{Score}}(\mathcal{D},G,y)$.
We employ an existing GDL program mining algorithm (Jeon et al., 2024), which aims to mine a GDL program $P$ that maximizes the quality score function Score defined as:

$$ $\textit{Score}(P,\mathcal{D},y)={{|\{G\mid(G,y)\in\mathcal{D}_{y},(G,\eta)\in\llbracket P\rrbracket\ \}|}\over{|\{G\mid(G,y)\in\mathcal{D},(G,\eta)\in\llbracket P\rrbracket\ \}|+\epsilon}}$ $$

where $\epsilon$ is a hyperparameter.
Intuitively, $\textit{Score}(P,\mathcal{D},y)$ measures the precision of the mined GDL program $P$ in describing graphs with label $y$ in the training dataset $\mathcal{D}$.
$\epsilon$ enables the score to consider robustness of the mined GDL program.
Using a bigger $\epsilon$ makes robust programs (i.e., describe many graphs that belong to label $y$) have a higher score than others.
In our evaluation we set $\epsilon$ as 0.1, 1, or $|\mathcal{D}|*0.01$ that performs best on the validation set.
Due to the space limit, the detailed mining algorithm is presented in Appendix [B](#A2).
Each mined program is collected into $\mathcal{P}$ at line 5.
At line 6, the algorithm selects the top-$k$ GDL programs based on their scores:

$$ $\textit{TopK}(\mathcal{P})=\{P\in\mathcal{P}\mid|\{P^{\prime}\in\mathcal{P}\mid\textit{Score}(P^{\prime},\mathcal{D},y)\geq\textit{Score}(P,\mathcal{D},y)\}|\leq k\}$ $$

where $k$ is a hyperparameter that determines the number of units in the GDL layer.
We select $k$ from $\{0.01\cdot|\mathcal{D}|,0.2\cdot|\mathcal{D}|,0.4\cdot|\mathcal{D}|,0.6\cdot|\mathcal{D}|,0.8\cdot|\mathcal{D}|,|\mathcal{D}|\}$ based on the validation set.

MLP Training.
After mining GDL programs, the MLP layers are trained to classify graphs based on the representations generated by the GDL layer.
The MLP takes these graph representations as input and outputs the predicted label $\hat{y}$.

Figure: Algorithm 2 Explaining GDLNN

### 5.2 Explaining GDLNN

The predictions of GDLNN can be explained by directly applying existing model explanation techniques.
In GDLNN, each feature corresponds to a graph pattern (i.e., a GDL program); thus, identifying key features directly reveals the graph patterns responsible for the prediction.

The identified key features can also be transformed into subgraph explanations.
In the graph machine learning domain, explanations are usually subgraphs (Kakkad et al., 2023) describing key parts that are responsible for the predictions.
Algorithm [2](#alg2) illustrates how to generate subgraph explanations in GDLNN using existing model explanation techniques that identify important features.
The algorithm takes as input a target graph $G$ (to be explained), a GDLNN model $\mathcal{M}$, and an explanation method T.
At line 2, the algorithm collects the important features (i.e., GDL programs) using the explanation technique T.
It then iteratively refines the graph into a subgraph that preserves the same feature values for the important features $\mathcal{P}$.
At line 6, $\textit{Refine}(G,\mathcal{P})$ attempts to find a subgraph $G^{\prime}$ by removing nodes (and their corresponding edges) from $G$, such that:

$$ $\forall P\in\mathcal{P}.G\models P\Rightarrow G^{\prime}\models P.$ $$

If no such subgraph exists, $\textit{Refine}(G,\mathcal{P})$ returns the original graph $G$.
The algorithm then outputs this subgraph as the explanation.

## 6 Evaluation

In this section, we evaluate the performance of GDLNN on various graph classification benchmarks.
Our evaluation aims to answer the following research questions:

- •
RQ1 (Accuracy): How does GDLNN compare to existing popular graph machine learning methods in terms of classification accuracy?
- •
RQ2 (Explainability): How does the explainability of GDLNN compare to other methods?
- •
RQ3 (Cost): How does the computational cost of GDLNN compare to baseline methods?

Datasets.
We evaluate GDLNN on nine widely used graph classification datasets.
We use eight molecular datasets: BBBP, BACE, Mutagenicity, ENZYMES, PROTEINS, MUTAG, PTC (MR), and NCI1.
Additionally, we include a synthetic dataset, BA-2Motifs, which is commonly used for evaluating explainability (Yuan et al., 2021).
Dataset statistics are provided in Appendix [C](#A3).

Baselines.
For comparison, we include five popular baseline methods representing different approaches to graph classification.
First, we consider three widely-used graph neural networks: GCN (Kipf & Welling, 2017), GIN (Xu et al., 2019), and GAT (Veličković et al., 2018).
We also include MLP, a simple multi-layer perceptron that generates graph representations via graph pooling, and PL4XGL (Jeon et al., 2024), a symbolic (non-neural) graph learning method that employs GDL programs for classification.
Hyperparameters are selected based on the validation set.
The hyperparameter search space is provided in Appendix LABEL:sec:appendix:hyperparameter.
All experiments are conducted on an AMD Ryzen Threadripper 3990X (64 cores) with an NVIDIA RTX A6000 GPU. Datasets are randomly split into 80/10/10 for training, validation, and test sets.

**Table 1: Accuracy comparison on nine graph classification datasets.**
|  | MUTAG | Mutagenicity | BBBP | BACE | ENZYMES | PROTEINS | PTC | NCI1 | BA-2Motifs |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GIN | 94.0±5.1 | 81.0±1.0 | 82.9±3.3 | 81.1±3.8 | 64.3±3.4 | 71.3±3.9 | 61.2±7.4 | 81.3±2.4 | 99.8±0.5 |
| GCN | 72.0±13.6 | 79.6±1.7 | 83.0±1.7 | 74.3±17.8 | 65.9±3.0 | 71.7±1.6 | 54.1±4.1 | 77.4±0.8 | 99.8±0.5 |
| GAT | 90.0±0.0 | 76.0±1.2 | 84.4±2.8 | 65.5±15.4 | 60.0±5.2 | 72.8±4.5 | 62.3±12.5 | 65.8±3.3 | 81.2±4.4 |
| MLP | 93.0±10.3 | 80.1± 1.6 | 83.4±3.4 | 81.3±3.1 | 54.3±6.9 | 71.7±2.5 | 49.4±9.1 | 77.8±1.2 | 99.8±0.5 |
| PL4XGL | 100±0.0 | 76.9±0.0 | 86.3±0.0 | 82.8±0.0 | 50±0.0 | 62.1±0.0 | 67.6±0.0 | 72.7± 0.0 | 100.0±0.0 |
| GDLNN | 100±0.0 | 81.1±1.1 | 88.2±1.1 | 84.4±1.0 | 68.3±2.6 | 68.1±1.2 | 68.8±6.1 | 83.3±1.2 | 100.0±0.0 |

### 6.1 Accuracy Comparison

We first compare the accuracy of GDLNN with the baseline graph machine learning methods.
Following prior work (Park et al., 2022), we report the 95% confidence intervals over five runs.
Table [1](#S6.T1) presents the comparison results, with the best-performing models for each dataset highlighted in bold.
As shown, GDLNN achieves the highest accuracy on all datasets except PROTEINS.
Compared to the baseline GNNs, GDLNN consistently shows better accuracy, demonstrating that GDL-based graph representations are a competitive alternative to standard message-passing and pooling-based embeddings for high accuracy.
Compared to PL4XGL, a symbolic graph learning method using GDL programs, GDLNN achieves higher accuracy across all datasets. This improvement is mainly due to the neural network layers in GDLNN, which can capture more complex patterns in the graph data.
Compared to MLP, a simple multi-layer perceptron with graph pooling, GDLNN also performs consistently better on all datasets except PROTEINS.
This shows that pooled node features are useful for the PROTEINS dataset, and relying solely on GDL program-based features may slightly reduce accuracy.
Developing an ensemble of GDL-based and pooled node features is a promising direction for future work to further improve accuracy.

Figure: (a) An example graph of label 1

### 6.2 Explainability Comparison

Next, we compare the explainability of GDLNN with baseline methods.
In our evaluation, we adopt Lime (Ribeiro et al., 2016) to explain GDLNN.
Once Lime identifies the important features, we transform these features into subgraph explanations using Algorithm [2](#alg2).

Baselines.
As baselines, we use SubgraphX (Yuan et al., 2021), a state-of-the-art GNN explanation technique.
Intuitively, SubgraphX identifies important subgraphs that contribute to the classification decisions of GNNs.
Following Yuan et al. (2021), we apply SubgraphX to explain GIN’s predictions.
We also compare GDLNN with PL4XGL, an inherently explainable graph learning method.
PL4XGL classifies a graph using one of the highest-scoring GDL programs and directly provides it as an explanation.

Qualitative Comparison.
We first qualitatively compare explanations using the synthetic dataset BA-2Motif, which is designed to evaluate the performance of model explanation techniques.
In the dataset, each node is represented by its degree as a feature. For example, if a node has degree 3, its feature is $\langle 3.0\rangle$.
BA-2Motifs has two labels: label 1 and label 2.
Each label is determined by the presence of a specific motif (i.e., graph pattern).
The evaluation checks whether the explanation technique can correctly identify the motif.
Figures [5(a)](#S6.F5.sf1) and [5(b)](#S6.F5.sf2) show example graphs from the BA-2Motifs dataset.
Label 1 corresponds to a house-shaped motif consisting of five nodes (a roof node, two middle nodes, and two bottom nodes) connected by edges.
One of the middle nodes is further connected to a randomly generated graph following the Barabási-Albert model.
In the motif of label 1, the two middle nodes are connected.
In contrast, the motif of label 2 also consists of five nodes, but the two middle nodes are not connected.

Figure: (a) GDLNN
Refer to caption: /html/2510.00374/assets/figures/label2.png

Figure [6](#S6.F6) shows the explanations of GDLNN, SubgraphX, and PL4XGL for graphs classified into label 1, and all three techniques correctly identify the motif-related property of label 1.
For example, Figure [6(a)](#S6.F6.sf1) shows a subgraph explanation generated by GDLNN.
The identified subgraph exactly matches the motif of label 1.
Similarly, the subgraph explanation of SubgraphX in Figure [6(b)](#S6.F6.sf2) (highlighted with bold edges) also contains the motif of label 1.
PL4XGL provides a GDL program that captures a property describing the motif of label 1.
Figure [6(c)](#S6.F6.sf3) shows a graphical representation of this GDL program, which consists of four node variables and three edge variables.
The GDL program also correctly distinguishes graphs in label 1 from those in label 2.
Explanations for label 2 similarly identified the motif of label 2.
Explanations for label 2 are presented in Appendix LABEL:appendix:explainability.

Figure: Figure 7: Quantitative comparison of explanations on the BACE and Mutagenicity datasets. A lower Fidelity value indicates that the explanations are more faithful to the model’s predictions (i.e., lower is better). A higher Sparsity value indicates that the explanations are simpler (i.e., higher is better).
Refer to caption: /html/2510.00374/assets/x2.png

Quantitative Comparison.
Now, we quantitatively compare the explanations of GDLNN and SubgraphX.
For comparison, we use Sparsity and Fidelity  as evaluation metrics (Kakkad et al., 2023).
Intuitively, Fidelity measures the faithfulness of explanations; a lower score indicates higher faithfulness (i.e., lower is better).
Sparsity measures the simplicity of explanations; a higher score indicates greater simplicity (i.e., higher is better).
The formal definitions are provided in Appendix LABEL:appendix:explainability.

Figure [7](#S6.F7) compares the explainability of GDLNN(+Lime), GNN+SubgraphX, and PL4XGL on the two metrics across two datasets.
In SubgraphX, the explanation size is user-defined; the blue lines indicate the performance of SubgraphX.
In GDLNN+Lime, the explanation size is determined by Lime (orange line).
In our evaluation, Lime selected varying numbers of features, ranging from 5 to 1000.
For PL4XGL, the explanation size is fixed by the model, and the gray squares indicate its performance.
As the plots show, GDLNN achieves a better trade-off between sparsity and fidelity than SubgraphX on both datasets.
In terms of fidelity, GDLNN performs worse than PL4XGL because PL4XGL is inherently explainable (fidelity score is guaranteed to be 0 (Jeon et al., 2024)).
By sacrificing some explainability, however, GDLNN achieves better accuracy than PL4XGL as shown in Table [1](#S6.T1).
We achieve consistent results for the other datasets.
Due to space limits, results for the remaining seven datasets are provided in Appendix LABEL:appendix:explainability.

Figure: Figure 8: Accumulated (training + inference + explanation) cost comparison on the two datasets.
Refer to caption: /html/2510.00374/assets/x4.png

### 6.3 Cost of GDLNN

Now, we compare the cost of GDLNN against the baselines.
For fairness, we report the total accumulated cost, which includes training, inference, and explanation costs.
Figure [8](#S6.F8) presents the accumulated cost (in minutes) of GDLNN and the baselines on two datasets: BACE and Mutagenicity.
In the figure, the y-axis shows the accumulated cost (training + inference + explanation), while the x-axis shows the number of classified and explained graphs.
The blue lines correspond to GIN with SubgraphX, and the green and orange lines correspond to PL4XGL and GDLNN(+Lime), respectively.

Compared to GIN+SubgraphX, GDLNN is substantially faster.
Initially (i.e., when only the training cost is included), GDLNN is more expensive than GNNs due to its costly GDL program mining process.
However, the total accumulated cost of GDLNN becomes much lower than that of GNN+SubgraphX, thanks to its significantly faster explanation process.
Compared to PL4XGL, the cost difference is small since they share the same GDL learning process, and both have small classification and explanation costs.
We also achieved consistent results for the other datasets.
Due to space limits, results for the remaining seven datasets are provided in Appendix LABEL:appendix:explainability.

## 7 Conclusion

In this paper, we present a new graph machine learning architecture called GDLNN, which is a combination of a domain-specific programming language and neural networks.
Thanks to the effective and interpretable GDL program-based graph representations, GDLNN achieves outstanding accuracy on various graph classification benchmarks, and the predictions of GDLNN are easy to explain as the representations are inherently interpretable.
Also, GDLNN is fast when the explanation cost is included.
We believe this work is a starting point for a new graph machine learning architecture that employs effective and interpretable graph representations through domain-specific programming languages.

## 8 Ethics Statement

This work presents methods for graph classification and relies solely on publicly available benchmark datasets. To the best of our knowledge, these datasets do not contain personally identifiable information, and we have complied with their licenses and terms of use.
No human-subject experiments, user studies, or data collection involving vulnerable populations were conducted in this work.
Potential risks include harmful outcomes if learned GDL programs capture spurious correlations.
Regarding privacy, since graph classification can be applied to sensitive domains such as social-network analysis, we discourage applications that enable surveillance, profiling, or other infringements of privacy and civil liberties.

## 9 Reproducibility Statement

We provide the source code of GDLNN and the datasets used in this work as a zip file in the supplementary material.
The artifact provides the required environment and instructions to run the code.
The manual is available as README.md in the supplementary material.

## References

- Defferrard et al. (2016)
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.
Convolutional neural networks on graphs with fast localized spectral
filtering.
In *Proceedings of the 30th International Conference on Neural
Information Processing Systems*, NIPS’16, pp. 3844–3852, Red Hook, NY,
USA, 2016. Curran Associates Inc.
ISBN 9781510838819.
- Grattarola et al. (2024)
Daniele Grattarola, Daniele Zambon, Filippo Maria Bianchi, and Cesare Alippi.
Understanding pooling in graph neural networks.
*IEEE Transactions on Neural Networks and Learning Systems*,
35(2):2708–2718, 2024.
doi: 10.1109/TNNLS.2022.3190922.
- Hamilton et al. (2017)
Will Hamilton, Zhitao Ying, and Jure Leskovec.
Inductive representation learning on large graphs.
In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus,
S. Vishwanathan, and R. Garnett (eds.), *Advances in Neural Information
Processing Systems*, volume 30. Curran Associates, Inc., 2017.
URL
[https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf](https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf).
- Jeon et al. (2024)
Minseok Jeon, Jihyeok Park, and Hakjoo Oh.
Pl4xgl: A programming language approach to explainable graph
learning.
*Proc. ACM Program. Lang.*, 8(PLDI), June 2024.
doi: 10.1145/3656464.
URL [https://doi.org/10.1145/3656464](https://doi.org/10.1145/3656464).
- Kakkad et al. (2023)
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya.
A survey on explainability of graph neural networks, 2023.
- Kipf & Welling (2017)
Thomas N. Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
In *International Conference on Learning Representations
(ICLR)*, 2017.
- Lundberg & Lee (2017)
Scott M. Lundberg and Su-In Lee.
A unified approach to interpreting model predictions.
In *Proceedings of the 31st International Conference on Neural
Information Processing Systems*, NIPS’17, pp. 4768–4777, Red Hook, NY,
USA, 2017. Curran Associates Inc.
ISBN 9781510860964.
- Müller et al. (2023)
Peter Müller, Lukas Faber, Karolis Martinkus, and Roger Wattenhofer.
Graphchef: Learning the recipe of your dataset.
In *ICML 3rd Workshop on Interpretable Machine Learning in
Healthcare (IMLH)*, 2023.
URL [https://openreview.net/forum?id=ZgYZH5PFEg](https://openreview.net/forum?id=ZgYZH5PFEg).
- Park et al. (2022)
Jinyoung Park, Sungdong Yoo, Jihwan Park, and Hyunwoo J Kim.
Deformable graph convolutional networks.
In *Proceedings of the AAAI Conference on Artificial
Intelligence*, volume 36, pp. 7949–7956, 2022.
- Ribeiro et al. (2016)
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.
”why should i trust you?”: Explaining the predictions of any
classifier.
In *Proceedings of the 22nd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining*, KDD ’16, pp. 1135–1144, New
York, NY, USA, 2016. Association for Computing Machinery.
ISBN 9781450342322.
doi: 10.1145/2939672.2939778.
URL [https://doi.org/10.1145/2939672.2939778](https://doi.org/10.1145/2939672.2939778).
- Veličković et al. (2018)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro
Liò, and Yoshua Bengio.
Graph attention networks.
In *International Conference on Learning Representations*, 2018.
- Wu et al. (2021)
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and
Philip S. Yu.
A comprehensive survey on graph neural networks.
*IEEE Transactions on Neural Networks and Learning Systems*,
32(1):4–24, 2021.
doi: 10.1109/TNNLS.2020.2978386.
- Xu et al. (2019)
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.
How powerful are graph neural networks?
In *7th International Conference on Learning Representations,
ICLR 2019, New Orleans, LA, USA, May 6-9, 2019*. OpenReview.net, 2019.
URL [https://openreview.net/forum?id=ryGs6iA5Km](https://openreview.net/forum?id=ryGs6iA5Km).
- Yuan et al. (2021)
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.
On explainability of graph neural networks via subgraph explorations.
In *Proceedings of the 38th International Conference on Machine
Learning (ICML)*, pp. 12241–12252, 2021.
- Yuan et al. (2022)
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji.
Explainability in graph neural networks: A taxonomic survey.
*IEEE Transactions on Pattern Analysis and Machine
Intelligence*, pp. 1–19, 2022.
doi: 10.1109/TPAMI.2022.3204236.

## Appendix A Alternative Activation Function

The activation function $\sigma$ in GDLNN is a design choice.
Various alternative functions can be defined to generate values (i.e., embeddings) from a given graph $G$ and a GDL program $P_{i}$.
For example, inspired by graphlets, we can define a more expressive activation function $\sigma^{\prime}$ that counts the number of subgraphs in $G$ matching the pattern specified by $P_{i}$:

$$ $\sigma^{\prime}(P_{i},G)=|\{(G,\eta)\mid(G,\eta)\in\llbracket P_{i}\rrbracket\}|.$ $$

Unlike $\sigma$, which only indicates whether at least one subgraph of $G$ matches the pattern $P_{i}$, the function $\sigma^{\prime}$ measures the number of distinct matching subgraphs.
This provides richer information about $G$, though at the cost of higher inference time.
In this work, we adopt the simple $\sigma$ function for efficiency, while exploring more sophisticated activation functions remains an interesting direction for future research.

Figure: Algorithm 3 GDL program mining algorithm

## Appendix B GDL program mining Algorithm

### B.1 Objective

The goal of GDL program mining is to learn high-quality GDL programs that will be used in the GDL layer.
The detailed objective of GDL program mining is to enable the GDL layer generate similar representations for graphs with the same labels while different representations for graphs with different labels.
Formally, the goal is to mine a set of GDL programs $\mathcal{P}=\{P_{1},\ldots,P_{n}\}$ that maximizes

$$ $\sum_{i,j}\text{sim}(\bm{\phi}(G_{i},\mathcal{P}),\bm{\phi}(G_{j},\mathcal{P}))\cdot(2\mathbb{I}[y_{i}=y_{j}]-1)$ $$

where $\text{sim}(\bm{\phi}(G_{i},\mathcal{P}),\bm{\phi}(G_{j},\mathcal{P}))$ denotes the Hamming similarity between the representations of graphs $G_{i}$ and $G_{j}$ generated by the GDL programs $\mathcal{P}$.
Here, $\mathbb{I}[y_{i}=y_{j}]$ is the indicator function, which returns 1 if $y_{i}=y_{j}$ and 0 otherwise.
The representation $\bm{\phi}(G,\mathcal{P})$ of a graph $G$ generated by the GDL programs $\mathcal{P}$ is defined as

$$ $\bm{\phi}(G,\mathcal{P})=\langle\sigma(P_{1},G),\sigma(P_{2},G),\ldots,\sigma(P_{n},G)\rangle$ $$

A GDL layer consisting of programs $\langle P_{1},\ldots,P_{n}\rangle$ that satisfies this objective is expected to yield highly discriminative representations, thereby achieving high accuracy on graph classification tasks.

### B.2 Mining a GDL Program

We reuse an existing GDL program mining algorithm (Jeon et al., 2024) to mine a GDL program $P$ that maximizes the quality score function Score defined in Section [5](#S5).
Algorithm [3](#alg3) presents the detailed procedure of the Mine function used in Algorithm [1](#alg1).
It takes a training dataset $\mathcal{D}$, a target training graph $G$, the label $y$ of the target graph $G$, and a quality score function Score as input and outputs a mined GDL program $P$.
At line 2, the algorithm initializes a GDL program $P$ using the Initialize function with the given graph $G$.
Suppose $\mathcal{V}=\{v_{1},v_{2},\dots,v_{n}\}$ and $\mathcal{E}=\{e_{1},e_{2},\dots,e_{m}\}$ are the node and edge sets of the graph $G$.
Then, $\textit{Initialize}(G)$ returns the following GDL program $P$ using a mapping function ${\it mapNode}:\mathcal{V}\to\mathbb{X}$ and ${\it mapEdge}:\mathcal{E}\to\mathbb{X}\times\mathbb{X}$:

$$ ${{{{{{{{{{{{{{{{{{\begin{array}[]{l}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}node}}}}}}\;{\it mapNode}(v_{1})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{V}}_{1,1},X^{\mathcal{V}}_{1,1}],[X^{\mathcal{V}}_{1,2},X^{\mathcal{V}}_{1,2}],\dots,[X^{\mathcal{V}}_{1,d},X^{\mathcal{V}}_{1,d}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}node}}}}}}\;{\it mapNode}(v_{2})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{V}}_{2,1},X^{\mathcal{V}}_{2,1}],[X^{\mathcal{V}}_{2,2},X^{\mathcal{V}}_{2,2}],\dots,[X^{\mathcal{V}}_{2,d},X^{\mathcal{V}}_{2,d}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \dots\\ \text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}node}}}}}}\;{\it mapNode}(v_{n})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{V}}_{n,1},X^{\mathcal{V}}_{n,1}],[X^{\mathcal{V}}_{n,2},X^{\mathcal{V}}_{n,2}],\dots,[X^{\mathcal{V}}_{n,d},X^{\mathcal{V}}_{n,d}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}edge}}}}}}\;{\it mapEdge}(e_{1})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{E}}_{1,1},X^{\mathcal{E}}_{1,1}],[X^{\mathcal{E}}_{1,2},X^{\mathcal{E}}_{1,2}],\dots,[X^{\mathcal{E}}_{1,c},X^{\mathcal{E}}_{1,c}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}edge}}}}}}\;{\it mapEdge}(e_{2})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{E}}_{2,1},X^{\mathcal{E}}_{2,1}],[X^{\mathcal{E}}_{2,2},X^{\mathcal{E}}_{2,2}],\dots,[X^{\mathcal{E}}_{2,c},X^{\mathcal{E}}_{2,c}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \dots\\ \text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language{\@listingGroup{ltx_lst_keyword}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}edge}}}}}}\;{\it mapEdge}(e_{m})\;\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[X^{\mathcal{E}}_{m,1},X^{\mathcal{E}}_{m,1}],[X^{\mathcal{E}}_{m,2},X^{\mathcal{E}}_{m,2}],\dots,[X^{\mathcal{E}}_{m,c},X^{\mathcal{E}}_{m,c}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\\ \end{array}$ $$

where ${\it mapNode}$ maps each node to a distinct variable and ${\it mapEdge}$ maps each edge $(v_{i},v_{j})$ to a distinct variable pair $({\it mapNode}(v_{i}),{\it mapNode}(v_{j}))$.
$X^{\mathcal{V}}_{i,j}$ (resp., $X^{\mathcal{E}}_{i,j}$) denotes the $j$^th value of the feature vector of node $X^{\mathcal{V}}_{i}$ (resp., edge $X^{\mathcal{E}}_{i}$).
Intuitively, Initialize($G$) transforms the given graph $G$ into the most specific GDL program $P$ that describes the graph $G=(\mathcal{V},\mathcal{E})$.
At lines 3–8, the algorithm iteratively refines $P$ into a more general one.
At line 4, it enumerates possible generalizations of $P$ using the Enumerate function, defined as

$$ $\textit{Enumerate}(P)=\{P^{\prime}\mid P\leadsto P^{\prime}\},$ $$

where the mutation rule ($\leadsto$) is defined in Figure [B.2](#A2.Ex16).
Intuitively, Enumerate mutates $P$ either by removing a node or edge variable (i.e., RemoveNode or RemoveEdge) or by widening the interval of a variable (i.e., GeneralizeNode or GeneralizeEdge).
The operation GeneralizeItv widens an interval as follows:

$$ ${{{{{{\textit{GeneralizeItv}(\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[a_{1},b_{1}],[a_{2},b_{2}],\dots[a_{k},b_{k}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}})=\\ \{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[a_{1}^{\prime},b_{1}^{\prime}],[a_{2}^{\prime},b_{2}^{\prime}],\dots[a_{k}^{\prime},b_{k}^{\prime}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\mid j\in[1,k],\forall i\neq j.\;a_{j}^{\prime}={-\infty},b_{j}^{\prime}=b_{j},a_{i}^{\prime}=a_{i},b_{i}^{\prime}=b_{i}\}\cup\\ \{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textless}}}}{[a_{1}^{\prime},b_{1}^{\prime}],[a_{2}^{\prime},b_{2}^{\prime}],\dots[a_{k}^{\prime},b_{k}^{\prime}]}\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\textgreater}}}}\mid j\in[1,k],\forall i\neq j.\;a_{j}^{\prime}=a_{j},b_{j}^{\prime}={\infty},a_{i}^{\prime}=a_{i},b_{i}^{\prime}=b_{i}\}.$ $$

At line 5, the algorithm selects a program $P^{\prime}$ from the set of enumerated GDL programs $\mathcal{P}$ using the Choose function, defined as

$$ $\textit{Choose}(\mathcal{P},\mathcal{D},y,\textit{Score})=\left\{\begin{array}[]{ccl}\bot&&\mbox{if}~{\mathcal{P}=\emptyset}\\ \operatorname*{arg\,max}_{P\in\mathcal{P}}\textit{Score}(P,\mathcal{D},y)&&\mbox{otherwise}\end{array}\right.$ $$

Intuitively, the Choose function returns a better-scored program from the set of enumerated GDL programs $\mathcal{P}$.
At line 6, it checks whether the refined program $P^{\prime}$ has a higher score than the previous program $P$.
If so, the algorithm continues refining.
Otherwise (i.e., the refinement degrades the score), the algorithm returns the previous program $P$.

Figure: Figure 9: One-step mutation rules ($\leadsto$) for Enumerate function

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: - How does the proposed GDLNN differ fundamentally from PL4XGL beyond adding an MLP classifier? Can the MLP’s role be seen as a learned weighting over symbolic patterns rather than genuine neural integration?

- Could GDL program mining be jointly optimized with the neural loss via reinforcement learning or differentiable relaxation to realize an actual hybrid model?

- How scalable is the GDL mining process to larger graph datasets (e.g., OGB benchmarks)? Is there any parallelization or pruning mechanism?

- How interpretable are the mined programs in practice? Have human evaluators been consulted to assess their comprehensibility or domain relevance?

- Since LIME operates on tabular feature vectors, what guarantees exist that its explanations correspond to meaningful graph substructures rather than artifacts of binary encodings?
soundness: 3
strengths: The paper tackles an important and underexplored direction, symbolic-neural hybrid modeling for explainable graph learning, and presents an architecture that is both conceptually interesting and relatively simple to implement. Integrating a declarative language layer (GDL) for interpretable pattern extraction with a neural classifier is an appealing idea for bridging symbolic reasoning and representation learning. The presentation is thorough, with clear syntax and semantics definitions for GDL (Figures 2-3) and explicit mining algorithms (Algorithms 1 and 3). The use of interpretable intermediate representations allows off-the-shelf explainers like LIME or SHAP to operate without architectural modifications, which is a pragmatic design choice. Empirical evaluation is broad, covering diverse datasets and comparing to both symbolic (PL4XGL) and neural (GNN + SubgraphX) baselines.
summary: This paper presents GDLNN, a hybrid architecture that integrates a domain-specific GDL with neural networks for graph classification. The GDL component encodes explicit graph patterns as symbolic programs, while a MLP operates on the binary activations of these patterns to produce predictions. The core motivation is to create graph representations that are both interpretable and expressive, addressing the limitations of GNNs, whose learned embeddings are often opaque and entangled. The authors claim that the mined GDL programs yield interpretable representations that allow standard explainability methods (e.g., LIME, SHAP) to be applied directly. Experiments across nine benchmark datasets show that GDLNN achieves competitive or higher accuracy than GNN baselines (e.g., GIN, GCN, GAT) and that the combination of GDLNN with LIME provides better sparsity–fidelity trade-offs than SubgraphX explanations for GNNs.
weaknesses: - The paper’s technical novelty and contribution depth are modest. Most of the work builds directly on the authors’ previous PL4XGL (Jeon et al., 2024) system, which already introduced GDL as a symbolic approach to explainable graph learning. GDLNN primarily adds a shallow MLP layer and reuses the existing GDL mining and scoring pipeline with minimal conceptual changes. The claim that “GDLNN is the marriage of programming language and neural networks” oversells what is effectively a two-stage system—symbolic feature mining followed by standard supervised learning—without genuine co-training or mutual optimization between the symbolic and neural components.

- From a ML standpoint, the proposed system behaves like a feature-engineering pipeline rather than a unified differentiable model. The GDL program mining step is discrete, non-gradient-based, and computationally heavy, while the downstream MLP training is conventional. The lack of end-to-end optimization means the neural component cannot influence the symbolic search space, limiting expressiveness and adaptability. This disconnect also undermines the claimed synergy between programming languages and neural networks.

- On the theoretical side, the semantics and learning objectives of GDLNN are largely definitional rather than novel. The pattern-matching and scoring functions replicate existing approaches in symbolic subgraph mining or inductive logic programming, and the formal grammar of GDL provides syntactic clarity but no new learning capabilities. The “interpretability” argument is also overstated: while GDL programs are human-readable, their mined intervals and node-edge mappings can become complex, especially for large graphs, making practical interpretation nontrivial. Moreover, the paper treats applying LIME or SHAP on top of GDL features as evidence of explainability, but this does not demonstrate causal fidelity or human-aligned interpretability.

- Empirically, while GDLNN performs competitively on small to mid-scale datasets (Table 1, p.7), its advantage is not significant over strong GNN baselines. Gains on MUTAG and BACE are minor, while on larger datasets such as PROTEINS, GDLNN slightly underperforms. The improvement over PL4XGL seems primarily due to the neural classifier, not the hybrid design. The evaluation lacks variance analysis across random seeds, and scalability beyond thousands of nodes per graph is untested. The explanation metrics (Figure 7, p.8) rely on sparsity and fidelity alone, which are simplistic and insufficient to assess interpretability quality. The cost analysis (Figure 8, p.9) demonstrates marginal efficiency improvements once mining time is included.

- Finally, the paper’s writing and framing could be more critical and focused. Much of the space (Sections 4-5, Appendices B-D) is devoted to reproducing existing definitions and pseudocode from earlier GDL-based work, giving the impression of incremental advancement rather than a breakthrough. The discussion of limitations and future directions is minimal.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weaknesses.
soundness: 3
strengths: 1. Novel integration of symbolic and neural paradigms: The proposed combination of a programming language (GDL) and neural network is innovative and provides a promising direction for interpretable graph learning.

2. Explainability focus: The authors convincingly demonstrate that GDLNN enables model-agnostic explanation methods (e.g., LIME, SHAP) to directly interpret its predictions.

3. Efficiency consideration: Including explanation cost in total model evaluation is insightful and practically relevant.

4. Well-structured evaluation: The paper provides both qualitative and quantitative analyses, with visual examples and detailed metrics (fidelity, sparsity).
summary: This paper introduces GDLNN, a hybrid architecture that integrates a domain-specific programming language (Graph Description Language, GDL) with neural networks for graph classification. The core idea is to generate interpretable and expressive graph representations using GDL programs, which are then classified using an MLP. The authors claim that this approach enhances both accuracy and interpretability compared to conventional GNN-based methods. Experiments on nine benchmark datasets demonstrate strong performance in accuracy, explainability (measured via LIME), and computational efficiency when explanation cost is considered.
weaknesses: While the paper claims that GDLNN can be combined with any post-hoc explanation method to generate interpretable results, this statement seems only partially true. In practice, the GDL layer produces discrete binary representations (each feature indicates whether a GDL program matches a given graph), which are not differentiable. Therefore, gradient-based explainers such as Integrated Gradients, Saliency Maps, or Grad-CAM cannot be directly applied. The approach is thus mainly compatible with perturbation-based, model-agnostic explainers (e.g., LIME, SHAP, Anchors). The paper should clarify whether GDLNN can meaningfully cooperate with gradient-based explanation methods, and if not, discuss this limitation explicitly.


In addition, the mechanism by which GDLNN works with LIME is not clearly explained. Algorithm 2 abstractly defines the step ImportantFeatures(G, M, T) but does not describe how perturbations are generated in the discrete binary feature space or how the identified important features are mapped back to subgraph structures. More details are needed on how LIME interacts with the GDL layer, including the perturbation sampling strategy and the reconstruction of subgraph explanations.


Finally, the comparison of explainability methods is incomplete. The experiments only evaluate SubgraphX and PL4XGL, omitting well-established baselines such as GNNExplainer, PGExplainer, and GraphLIME. Including these would provide a more comprehensive and fair comparison, and help position GDLNN within the broader landscape of explainable graph learning.

---

confidence: 3
contribution: 1
initial_rating: 2
presentation: 2
questions: * The method loses interpretability while it could retain some level of self-
explainability. Although the mined program features are inherently interpretable,
the unconstrained MLP obscures interpretability, forcing the adoption of post-
hoc explainability techniques. Why not avoid the MLP by adopting a non-
negative linear classifier that could help achieve some level of self-explainability?

* The authors claim that existing model explanation techniques can be used,
yet only LIME is evaluated. Why LIME over alternatives like SHAP or gradient-
based feature attribution? Please justify and possibly compare.

* The authors define the accumulated cost as the sum of the training, infer-
ence, and explanation times, but separating these components would be more
informative to understand the costs of each phase (the authors themselves note
substantial differences regarding training time). Please justify this decision.
soundness: 3
strengths: * The overall architecture is clear and intuitive: mined programs become
binary features, and a standard MLP operates on them for the final prediction.
* The method attains strong accuracy while still enabling post-hoc explana-
tions.
summary: This paper proposes GDLNN, a two-stage graph classification architecture that
first mines a set of graph patterns expressed in a domain-specific Graph De-
scription Language (GDL), then encode each graph as a binary feature vector
indicating the presence of each mined program and feed this vector into an MLP
classifier. A graph ”activates” a program if it contains a subgraph matching that
pattern. Explanations are obtained post-hoc: the authors instantiate LIME to
rank programs and then apply a refinement routine to extract a subgraph that
preserves the selected programs.
weaknesses: * (Most important) Novelty is very limited and incremental. The method
proposed adopts the mining process from PL4XGL, and the explainability is
obtained through already established post-hoc techniques. The only novelties
are the use of top-k programs as binary features instead of only taking the best
program (PL4XGL), the addition of an MLP for prediction and the refinement
step to get the post-hoc explanation.

* Cost analysis and discussion are scarce, and potentially misleading. In
the appendix, costs are reported for 7 of the 9 datasets tested (BACE dataset is
shown in the main paper; it’s unclear why MUTAG is omitted here). Although
GDLNN has lower accumulated cost on 6/8 datasets (MUTAG missing), it is
markedly higher than GNN+SubgraphX on BA-2Motifs and ENZYMES, with
no further analysis on why this behaviour is obtained. Thus, despite the claim
of GDLNN being faster in the main paper, its cost appears to be highly dataset-
dependent.

* What value was assigned to k to get the accuracies in Table 1 is not
shown. The absence of this value k makes the assessment of the performance
difficult

* SubgraphX settings unclear. The user-defined upper-bound controlling
SubgraphX explanations size is not reported, making the interpretation of the
fidelity-sparsity plots difficult.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. Can you provide ROC-AUC and a scaffold/OOD split for the molecule datasets, or at least discuss how close train and test graphs can be? Random splits may leak near-duplicate structures across train and test, which can inflate accuracy.
   
2. On MUTAG you report $100%$ accuracy with zero variance. Can you provide evidence that this is not just memorizing a few motifs tied to specific labels? For example, how does performance look if you hold out whole motifs or use fewer programs?
   
3. When you sweep $k$ (number of kept programs) and $\epsilon$, do you rerun program mining, or do you mine once and then just select top-$k$? I found that the appendix and main text list slightly different and inconsistent $\epsilon$ grids as I mentioned above. Which one matches the reported numbers?
   
4. The cost comparison argues that explanations are cheap once the program bank is mined. Suppose I deploy to a new dataset or a new label space. Do I have to re-mine programs, or can I reuse the old bank?
soundness: 3
strengths: 1. **Readable features.** Each dimension in the learned representation literally means “this specific typed subgraph exists in $G$.” This makes the model’s reasoning easy to audit and communicate.
2. **Practical explanation path.** The paper shows a nice workflow: rank important programs with LIME, then prune the graph to the minimal subgraph that still satisfies those programs. This gives sparse, faithful subgraphs at a lower cost. And the paper argues that once the GDL programs are mined, explanations for many new graphs are cheap.
summary: This paper's model, GDLNN, first mines a bunch of readable subgraph patterns (called GDL programs). It then checks which patterns a graph contains, turns that into a binary vector (like a checklist), and feeds that vector to an MLP for classification.
Since each feature is tied to a concrete pattern, the paper argues that they can explain predictions by ranking these programs (with LIME/SHAP) and showing the supporting subgraph. After reading and checking the paper and appendix, I give a **"weak accept" (6) rating and I think using auditable patterns as features is a reasonable idea for interpretability, but I still have some concerns about their evaluation and clarity.**
weaknesses: 1. **Novelty positioning.** Conceptually, GDLNN mines discriminative GDL programs (very similar in spirit to PL4XGL) and then feeds their binary activations to an MLP. That is a reasonable and useful engineering step, but the paper currently frames this as a new paradigm. I think the author could use a more nuanced and honest positioning that acknowledges prior work more clearly.

2. **No end-to-end training.** The GDL programs are mined once, then frozen. The activation $\sigma(P,G)$ is a hard 0/1 test of pattern presence. The MLP never updates the programs. This is fine, but it should be stated clearly as a two-stage pipeline instead of implying a single differentiable model. The appendix hints at a richer count-based $\sigma'(P,G)$ but it seems not used in the main experiments.

3. **Reproducibility details and inconsistency.** A few hyperparameter details are inconsistent between main text and appendix (e.g., candidate values for $\epsilon$, how $k$ is chosen). In Sec 5, the paper defines$k$ as the number of kept programs and says “we select $k$ from ${0.01\cdot|D|, 0.2\cdot|D|, 0.4\cdot|D|, 0.6\cdot|D|, 0.8\cdot|D|, |D|}$ based on the validation set,” together with the TopK definition $\text{TopK}(P)={P \in \mathcal{P} \mid |{P' \in \mathcal{P} \mid \text{Score}(P',D,y)\ge \text{Score}(P,D,y)}|\le k}$. However, Appendix D says that both $k$ and $\epsilon$ are tuned on validation, and it lists the search grid for $\epsilon$ as ${0.1, 0.01, 0.01\cdot|D|}$, which is not stated in the main text. The appendix also implies that $\epsilon$ directly affects the mining score $\text{Score}(P,D,y)=\frac{|{G\in D_y\mid G\models P}|}{|{G\in D\mid G\models P}|+\epsilon}$,but the main text not clearly reports which $\epsilon$ was finally used per dataset.

4. **Explainability robustness.** Explanation quality is evaluated mainly with LIME. LIME can be unstable on sparse binary features. However this paper didn't provide either a short sensitivity study or a comparison with SHAP to check that the fidelity and sparsity curves are not an artifact of one attribution method.