A Self-Explainable Heterogeneous GNN for Relational Deep Learning
Authors: Francesco Ferrini
Antonio Longa
Andrea Passerini
Manfred Jaeger
Venue: Accepted by TMLR ()

Abstract: Recently, significant attention has been given to the idea of viewing relational databases as heterogeneous graphs, enabling the application of graph neural network (GNN) technology for predictive tasks. However, existing GNN methods struggle with the complexity of the heterogeneous graphs induced by databases with numerous tables and relations.
Traditional approaches either consider all possible relational meta-paths, thus failing to scale with the number of relations, or rely on domain experts to identify relevant meta-paths. A recent solution does manage to learn informative meta-paths without expert supervision, 
but assumes that a node’s class depends solely on the existence of a meta-path occurrence.
In this work, we present a self-explainable heterogeneous GNN for relational data,
that supports models in which class membership depends on aggregate information obtained from multiple
occurrences of a meta-path.
Experimental results show that in the context of relational databases, our approach effectively identifies informative meta-paths that faithfully capture the model’s reasoning mechanisms. It significantly outperforms existing methods in both synthetic and real-world scenarios.

Published in Transactions on Machine Learning Research (02/2025)
A Self-Explainable Heterogeneous GNN for Relational Deep Learning
Francesco Ferrini University of Trento, Italy
franesso.ferrnn@@hniii.tt
Antonio Longa
antonio. mntonio.longa@@umiin..
University of Trento, Italy
Andrea Passerini
andrea..nsserrnn/@aniin.c
University of Trento, Italy
Manfred Jaeger
jaeger@cs. non, dk
Aalborg University, Denmark
Reviewed on OpenReview: https: //
// operreveew.eee.... net/ forum? id- 8Q4 q2e9a92
Abstract
Recently, significant attention has been given to the idea of viewing relational databases as heterogeneous graphs, enabling the application of graph neural network (GNN) technology for predictive tasks. However, existing GNN methods struggle with the complexity of the helerogeneous graphs induced by databases with numerous tables and relations. Traditional approaches either consider all possible relational meta-paths, thus failing to scale with the mumber of relations, or rely on domain experts identify relevant meta-paths. recent solution does manage learn informative meta-paths without expert supervision, but as- sumes that node's class depends solely on the existence of a meta-path occurrence. In this work, present self-explainable heterogeneous GNN for relational data, that supports models in which class membership depends on aggregate information obtained from multi- ple occurrences of a mela-path. Experimental results show that in the context of relational databases, our approach effectively identifies informative meta-paths that faithfully capture the model's reasoning mechanisms. significantly outperforms existing methods in both synthetic and real-world scenarios.
1 Introduction
Graph Neural Networks (GNNs) have increasingly become the de-facto standard for many predictive tasks
involving networked data, such as physical systems (Sanchez-Gonzalezz et al. 2018 Battaglia et al., 2016) Knowledge Graphs (Hamaguchi et al. 2017) and social networks (Wu et al. 2020 By learning effective node embeddings, GNNs offer a unified framework for addressing various graph- based tasks, including node classification, graph classification, and link prediction. However, similar to other representation learning paradigms, GNNs often exhibit black-box nature in their predictions. Numerous solutions have been proposed for host-hoc explainability of GNN predictions, primarily at the instance-based level (Ying et al,, 2019 Vu & Thai 2020: Miao et al. 2022 Yuan et al., 2021). Yet, as with other deep learning architectures. the ability of these approaches to genuinely reflect the underlying reasoning of the predictor has been called into question (Longa et al. 2024). To tackle this challenge, eelf-exxlainable GNNs (Kakkad et al. 20233 Christiansen et al. 2023) Sco et al. (023) have recently emerged, aiming to ensure that GNN predictions are grounded in interpretable clements, such subgraphs (Wu et al. 2022 Yu et al. 2020) or prototypes
(Zhang et. al. 2022 Ragno et. al. 2022

---

Published in Transactions on Machine Learning Research (02/2025)
Despite the widespread adoption of GNNs, most approaches are tailored for homogeneous graphs, where edge types are indistinguishabl.. While encoding edge types as features is common workaround, the standard solution simply consists in concatenating the one-hot encoded edge type to node features, which eventually boils down to learning an odge-type specific bias. This limitation is particularly problematic in knowledge graphs, which typically feature numerous relations (corresponding to edge types), with only a few being pertinent a specific predictive task fask-forming the so-called meta-paths. Existing approaches for heterogeneous GNNs either rely on domain experts to provide relevant meta-paths a priori (Chang et al., 2022 Fu et al.)
2020 Li et al.) 2021 Wang et al.) 2019), or attempt to learn them from data by assigning Hu et al. 2020 Lv et al. 2021b Mitra et al. 2022 Schlichtkrull et al.,
different weights to various relations
2018 Yu et al.
2022 Yun et al.
2019b
2022a
Zhu et al. 2019 a solution that fails to scale with the
number of candidale relations.
Recently, MP-GNN (Ferrini et al. 2024) has been proposed as a solution for learning meta-paths without requiring user supervision. This approach employs scoring function to predict the potential informativeness of partial meta-paths, enabling efficient. exploration of the combinatorial space of candidate meta-pathss However, key limitation of MP-GNN is the existential quantification assumption which states that node's class is primarily dependent on the eristence of meta-path instance, meaning just one instance is sufficient for accurate prediction.
its assumption that a node's class is primarily dependent on the eristence meta- meta-path instance, meaning just one instance is sufficient for accurate prediction. While this assumption may be reasonable for knowledge graphs, it is unrealistic when dealing with relational databases, where entities are characterized by numerous categorical and numerical attributes. On the other hand, this same complexity makes relational databases particularly well-suited for GNN technology, as evidenced by the growing interest in what is now being termed relational deep learning (Fey et al. 2023
Relational database
Heterogeneous graph
LEGEND
Medication
13
Patient
Identifled meta path
Prescription
Prescription
Medication
Pharmacy
Explanation subgraph for positive example
Doctor
Patient
Department Label
Pharmacy
15
Feature = [1. 0) Feature [0, 1]
Doctor
Node
Department
type
feature
Relation "a"
Relation "6"
Node
Relation "c"
Relation "d'
Figure 1: Left: Relational database schema for a medical domain. Right: Heterogeneous graph represen- tation of (part of) the database. The highlighted subgraph shows a prototypical counts-of-coumts pattern characterising positive patients, namely having least two exempt prescriptions (represented by node fea- ture T), each containing least two medications. Existing heterogencous GNNs struggle with these patterns as they need to learn separate weight matrix for each edge lype in the graph, while MPS-GNN is capable of learning the relevant meta path without any direct user supervision.
In this paper, extend the concept behind MP-GNN beyond the simple existential quantification of meta- paths. We introduce Meta-Path Statistics GNN (MPS-GNN), an approach that automatically identifies relevant meta-paths, where the informative content is determined by learnable statistics computed on their realiza- tions. These include counts-of-counts statistics such as having at least two exempt prescriptions with at least two medications each to characterize patients with severe illness, as shown in Figure [ Note that MP-GNN would fail to discriminate between the two patient nodes in the figure, as they both have at least one occurrence of the correct meta-path. An experimental evaluation on both synthetic and database tasks demonstrate the significant advantages of the proposed solution over existing alternatives.
relational
2

---

Published in Transactions on Machine Learning Research (02/2025)
Additionally, results show how the meta-path learning strategy behind MPS-GNN renders it inherently and gen- uinely self-explainable, in contrast to many existing self-explainable GNN architectures whose explanations often lack fidelity (Christiansen et al.) 2023).
2 Related Work
Relational deep learning Fey et al. 2023 has recently emerged as a paradigm advocating the application of deep learning lechnology, and GNNs in particular, lo relational databases. The rotale behind this research direction the popularity of relational databases as a mean to store relational information in a variety of application domains, combined with the fact that relational databases can be seen hetcrogeneous graphs. with tables converted into sets of nodes and relations into (typed) edges between table entries (Robinson) et al. 2024). This transformation allows the application of heterogeneous Graph Neural Networks (GNNs) to this kind of data.
A common characteristics of most heterogeneous graphs, including those deriving from knowledge graphs and relational databases, is that only few relations convey relevant information when targeting a specific predictive task. For this reason, plain GNNs, that do not distinguish between edge types, struggle with these type of graphs. The most popular line of research for heterogeneous GNNs identifies meta-paths, i.e., sequences of relations, as primary sources of information. Existing approaches to incorporate meta-paths follow in two main categorics. The former requires domain experts to identify relevant meta-paths for the task at hand (Chang et al., 2022 Fu et al. 2020 Li et al.) 2021 Wang et al. 2019). Clearly, this approach is suboptimal as it requires this domain information to be readily available. The alternative solutions, either utilize relation-specific graph convolutions, capturing relational patterns with distinct paramcters or dedicated components for each type of relation (Hu et al.) 2020; Lv et al.] 2021b [Shlichttrull et al., 2018 Yu et al.] (022)) focuses on graph transformation and multi-view learning to enhance relational representations (Mitra et al.] 2022 Yun et al.] [019bb 2022a] Zhhu et al. 2019). Although these methods are effective with a limited number of relations, their performance quickly deteriorates as the mumber of candidate relations grows.
Recently, a novel approach named MP-GNN (Ferrini et al., 2024 has been introduced to tackle the afore- mentioned challenges and automatically learn relevant meta-paths from data. The approach leverages a scoring function predicting the potential informativeness of partial meta-paths to guide the search in the combinatorial space of candidate meta-paths. A major limitation of this approach is the fact that it as- sumes that the existential quantification of the meta-path is informative for the class label. This assumption makes the approach unsuitable for relational deep learning tasks, in which statistics extracted from table attributes are arguably crucial to characterize predictive targets. Our approach substantially generalizes the MP-GNN method, by designing a scoring function that can predict the informativenoss of partial meta-paths in terms of the statistics that could be constructed on top of their realizations. This extension is crucial in allowing MPS-GNN to be effectively applied to relational deep learning settings, as shown by our experimental evaluation. More details about the comparison between MP-GNN and MPS-GNN in 4.6
Explainability in GNN is a major research trend, with plenty of approaches for post-hoc explanation of GNN
predictions (instance- based explainability (Ying et al. 2019 Vu & Thai 2020 Miao et al. 2022 Yuan et al.
2021 and others aiming to explain the GNN model as a whole (model-based explainability Chen et al.
2024
Wang & Shen 2022 Azzolin et al.
2020 ). Specialized metrics have been developed 2022 Yuan et al.
to estimate the faithfulness of an explanation in relation to the mothod's 's input processing behavior (Agarwal
let al. 2023 Yuan et al. 2022: Amara et al. 2022
2023 Zheng et al., 2023). Following similar evolution
in the XAI literature of convolutional neural networks, self-explainable GNNs (Wu et al., 2022 Yu et al.,
2020 Zhang et al. 2022 Ragno et al.) 2022 have recently been proposed to encourage GNN models to
adhere to their explanations by design. However, experimental studics have questioned the faithfulness of the explanations provided by these approaches (Christiansen el al. 2023 Azzolin el al. 2025), highlighting the difficulty of achieving genuine explainability with GNNs. A key advantage of our proposed method is that meta-paths can naturally serve as model-level explanations, making MPS-GNN the first truly self- explainable GNN designed for relational deep learning applications. Our experimental evaluation confirms the faithfulness of the explanations to the model's behaviour.
3

---

Published in Transactions on Machine Learning Research (02/2025)
3 Preliminaries
This scction presents the core concepts that will be utilized in the rest of the paper.
Definition 3.1 (Relational Database). A relational database (T, consists of collection of tables T Tn...Ta and links between these tables L C x T Each table is a set T = fei, En where the elements e E T are referred to as rows or entities. Each entity is a tuple e = (e, ae) where Pe is the Primary Key that uniquely identifies the entity e; K₂ is the set of Foreign Keys corresponding primary key in other tables, thus connecting the tables; de corresponds to the Attributes of the entity e.
a
Definition 3.2 (Heterogeneous graph). A heterogeneous graph a directed graph g (V, EV,E,Xy where the set of directed edges (graphs induced by relational databases will
V is the set of nodes entities, be inherently directed) and Xy is matrix of node attributes (with being the attribute vector of node v). Each edge is represented as a triple (u, r, v)), indicating that nodes u and v are connected via relation r (written 4 v). We indicate the set of relations in the graph R.
For node e and relation denote with Ng the set of nodes that can be reached from by following relation We refer to this set as r-neighbors.
Definition 3.3 (Meta-path). A meta-path mp is sequence of relations defined heterogeneous graph "h,, where 71...,,77 are relations in R. knowledge graphs.
G, represented "
From relational database to heterogeneous graph A relational database be interpreted heterogencous graph where row becomes node u attributes de become node features za; links between entries of two tables are identified by the pair of primary P and foreign I. keys in the two tables. Each pair of connected tables, originates a relation in the graph, specified by r.
4 Methodology
For now we restrict attention to binary node classification problems. Our main problem is to construct meta-paths ", ",... "4 that are predictive features for the class label. When considering a meta-path as a feature, we are thinking of possible numerical feat ures that can defined by collecting and aggregating information that is found along all occurrences of the meta-path in concrete data graph, such the count-of-count feature illustrated in Figure] [ We construct meta-paths following strategy that
Greedy; a partially constructed meta-path "h r2, Th is extended by a next relation Tit without lookahead for possible completions -+42, lh Similar as in Ferrini et al. (2024), we try to estimate the potential informaliveness of nodes reached by by learned weights associated with the nodes.
First expansion
Local surrogate problem
W:putative feature
regression
Weighted multi-instance classification
problem:
Initial
task
Label: W6
W6
Label: W5
W5
Label: W4
b
2/4
PROBLEM SETUP FOR SECOND EXPANSION
ABSTRACTION
b
Label: W3
W3
Label: W12
W2
Figure 2: Outline of greedy local meta-path construction
4

---

Published in Transactions on Machine Learning Research (02/2025)
These weights represent putative features that can either be directly matcrialized functions of the nodes' attributes, or that can be constructed as features of meta-path extensions starting at the node.
Local: the meta-path construction step - is performed based only on local consideration of the nodes reached by Tú, and their r4+1 successors. The already constructed meta-path prefix 3,3 3h plays no explicit role in this step. We realize this locality by defining for each step a surrogate classification task for the nodes reached by r;- The problem of extending the constructed meta-path prefix then translates into the problem of finding the first relation for a relevant meta- path solving the surrogate problem. The surrogate problems take the form of weighted multi-insee instance classifieation tasks.
2 illustrates the high-level principles of our approach. Given an initial (binary) node classification task, first relation is identified that could solve the task with the help of putative node feature (weight) the successor nodes. Then a surrogate classification task is set up whose target is to materialize the putative feature as feature computable from the data. This surrogate task takes the form of a weighted multi-instance classification task, which can be seen as an abstraction of a direct regression problem with target w (see Section 4.2)
Note that both the greody and local properties mirror core principles of growing decision trees, which are built incrementally, adding one relation a time based on solving local classification sub-tasks. The improvements in time complexity with respect to an algorithm that looks at every possible relations in the mela-path construction are detailed in section 4.2.1 In Section 4.1 we describe the weighled meulti-inslance
classification task and its application in our scenario. Section 4.2 outlines the methodology for constructing
meta-paths by scoring graph relations, including the examples based on Figure [ In Section 4.3] we detail the GNN used our setup, and Section 4.4 presents the complete framework of the proposed approach.
4.1 Weighted multi-instance classification
We consider a variant of multi-instance classification, where each instance consists of a bag B nodes with a class label in {+, and each node v is assigned a weight, a(v, B). We denote with S+ (training) sets of positively and negatively labeled bags, respectively. The intention to interpret the label of the bag as function of element-level features, and that a(v, B) R represents a weight of the contribution of v's feature value to the class label of B. This weight can be positive negative, and its absolute value can be interpreted as measure for the importance of node v in bag B (which may differ for different bags that v is an element of). See Foulds & Frank (2010) for related generalizations of the standard multi-instance learning setting.
Our goal is to predict the bag label via discriminant functions of the form
F(B) Σ alv,
(1)
where f(r) is learnable node feature function. Specifically, we consider functions that are parameterized by a relation r, and are of the form
A OT OTx,
if Nr = 0 EnENs Wu. if N o 0
f(e, (ier,,,,u O. =
where va denotes the attribute vector of u, θ a trainable parameter vector, and w vector of trainable weights w. E [0, 1] assigned v's r-neighbors. The node feature function is thus computed as a combination of v's own attributes and the putative feature w., of its successors. When the node attributes 2. are not informative for solving the multi-instance classification task, then parameters θ can be learned that make TT, z, constant for all v, and thus this part of the node feature function becomes irrelevant (a suitable θ exists e.g. under the mild assumption that Fp contains at least one calegorical altribute in a one-hot
In a heterogenenus graph built from a relational database, this would he the table the node belongs to. If node represen- tations are simply embeddings, one can achieve the same goal by concatenating a constant feature to the embedding.
5

---

Published in Transactions on Machine Learning Research (02/2025)
encoding: then 67x, 1 for è that is set to 1 for all entries corresponding to the one-hot encoding of the categorical attribute, and zero everywhere else). The factor LuENy Wa captures a dependence of f'(v) on the r-neighborhood of v. When the r-neighborhood is non-informative because neither the number nor the identity of nodes u E Nr has discriminative value, then the ΣVEN; We factor can be made irrelevant by learning constant weights Wy-
Ideally, the discriminant function separates the classes in the sense that for any pair B E ESt, 1 E we have F(B+)= > F.B-). We note that this problem would be trivially solvable c.g. in the case where every positive bag contains a node that has an r-successor, which is not also r-successor of some node in negative bag. Then assigning weight of 1 to all such r-successor nodes, and a weight of 0 to all other nodes, would separate the classes. In reality, the complex connectivity of relations will preclude such simple solutions, and perfect separation in general. We therefore use as our learning objective the relaxed loss function
L(r, 0,
E
( (((B,rr;,,w)) ,r, - F(B ;,,
B-ESt ES B-
where a is the sigmoid function. In practice, given that the number of terms in the sum is quadratic in the number of training examples, we approximate (3) by random sample of positive and negative bags.
4.2 Relation Scoring
The initial weighted multi-instance classification problem for our meta-path construction process is defined by letting each positive (negative) target node form a one-clement bag {u} with the corresponding label, and weight, a(v, [v}) 1. Denote with ST SS the sets of all initial positive and negative bags, respectively. At all iterations select the relation that minimizes the loss (also referred to the scoring function)
L(r) min L(r, O w). w
(4)
If all candidate relations fail to minimize the loss, i.., optimizing O, w does not lead to substantially lower loss than using random parameters (i.e., does not improve by at least 30%), then the meta-path construction terminates and the current meta-path is returned. Otherwise, the current meta-path is extended with the minimal loss relation r. At this point, the problem becomes capturing the putative node features by actual features.
A possible approach would be to set this up a node regression task with target values w.. However, due to the often very large set of alternative optimal solutions w in the minimization 4 this would lead to a too restrictive task. Our goal to approximate the whole space of possible regression tasks defined by alternative w as a single weighted multi-instance classification task. For this, let r; denote the relation found to minimize 4 in iteration with optimal parameters O, For each positive bag B+ S, define the new bag
B : N/O
containing the ry-children of the nodes in B+. Similarly for negative bags. For u E Bi define the node weight by the following sum over all nodes B that have u as an re-neighbor:
alu, B =
Σ
(T,0((1BB)).
(6)
This definition of the weights enables to essentially ignore in the setup of the multi-instance classification task for iteration + 1 those nodes that are r,-sucoossors only of nodes v that did not play major role in solving the task of the previous iteration either because of low absolute value of 6 D7z,, or because (v, BBt) already had a low absolute value. The sets of all B (Brew) form the new training sets ($
6

---

Initially, the approach evaluates the potential informativeness of two relations originating from patients: relation a and relation b. Figure Ba illustrates the scoring process for relation a. The first step involves instantiating the node feature functions for patient nodes 0 and by applying Equation 2 Since both nodes share the same unique neighbor, the loss function 4 reduces to the constant z. which cannot be minimized by Q and w. Published in Transactions on Machine Learning Research (02/2025)
Toy Example: To provide clear understanding of the proposed approach, illustrate it with the toy example of Figure [ where patients are positive if, and only if, they have at least two exempt prescriptions. each containing at least two medications.
Instantiate node feature function lea.
Instantite node feature function
eq.
a.6.
F(B,
F(
a,e,w
-
F(B b,8,
lq. (4)
1%
0015
eq.(4)
(Pt
a a.8.w.)
L(b, O, w)
min a(o) 11/2
U22
82
(a) Scoring relation a
(b) Scoring relation
Figure 3: Scoring the first two relations
Similarly, relation 6 is scored. The loss function !l now becomes
o x (wo wa + we) O"'
xo + wz + wa)),
where Ho- = xι 01, is the attribute vector representing the T value in a one-hot encoding, This loss can be brought arbitrarily close to zero, e.g. by We + 0, W3 + 0, wy + 1, W2 + 1, and e (Z,0)" with >> 0. Consequently, relation scores higher than relation a and is selected for further extension. Note that the low loss of relation b is entirely due its potential informativeness: the b neighborhoods of the nodes 0 and are completely isomorphic, and therefore the meta path consisting of b alone provides no discriminative information.
To extend the meta path prefix b we set up the weighted multi-instance classification task for the second iteration. This gives us a positive bag B2 containing nodes {2, 2,,344 4] and a negative bag Bg containing nodes {4, 5, 6}. Node weights for the bags are computed according to Equation (6) and here simply yield uniform weights alk; B2)
for all & E f2, 3, 4), and a(k; B3) for all k (4. Note that node 4 has separate weights for the two bags it is part of.
Heterogeneous graph
Bag creation eq. (5)
Score relation c
Instantiate bag feature function
B
B
or BB)
B3
eq. (1)
F(
or
Bs);
(E, B2)
13
F(Ba,
eq. (4)
C B&)
B2
< (3)
12
min a(o) =12
Figure 4: Bag generation and scoring of relation c.
For solving the new classification task we score the candidate relations e and d. The right part of Figure S illustrates the scoring of Due the indistinguishable structure of the o-neighborhood for bags B3 and B3 the loss function 4 now reduces again to the constant 1/2, as in the scoring of relation
7

---

Published in Transactions on Machine Learning Research (02/2025)
Instantiate bag feature function and minimize
B3
1912
eq.(1)
F(B, d,6.w) F(5,, d 9,w
(q)(4)
H
B2
30i0
L(d, G w)
Figure 5: Scoring relation d.
For scoring the relation d we obtain as the loss function
(wi2 - wio - wi)) + ZOT [ (wi + wi1 - -11)
a
0
(see details in Appendix A.1 This loss can be brought arbitrarily close to zero, e.g. by wio, Wi1 + 1, W12 + 0 and e = (Z', 0)" with Z' > 0. Thus, relation is selected to extend the meta-path. The constructed meta-path - now is sufficient to discriminate between positive and negative examples. This is not directly visible this step in the meta-path construction process, but will be found by training an MPS-GNN this meta-path, as detailed in sections 4.3 and 4.4 Chock A.10 for similar example with more complex node features
4.2.1 Time complexity analysis
The purpose of the scoring function is to iteratively construct the meta-path that best classifics the target nodes, avoiding the need lo explore all possible paths. A naive search algorithm that simply tests all possible paths would have a polynomial complexity of ((R](), where [ is the number of relations the graph, and L is the maximum length of the mota-path we aim find. By leveraging the scoring function, the complexity is reduced to linear ( L). This improvement achieved because, at cach step, one relationship added to the meta-path under construction, and the subsequent search builds upon it without reconsidering the other relationships scored in the same iteration.
4.3 MPS-GNN
Similarly to MP-GNN, in the MPS-GNN framework a meta-path Fi,..., Tr. defines a multi-rclational GNN with L layers. In this setup, each layer of the network corresponds to a specific relation in the meta-path: the initial layer is linked to the final relation rL, progressing sequentially until the last layer, which corresponds to ri. Our forward model then takes the form:
h(+1) =o o (w 10
(" + (1
Σ 1E
h w: A(O)
neigh
where Ngt !! are neighbours of node v under relation FL-1, h is the embedding of node v in layer I, h Zv is the feature vector of node v, while w/(0) w(!)) neigh and w(() are learnable parameter vectors. Note that the latter term (1))), which is missing the original MP-GNN (Ferrini al. 2024), represents skip connection between the input and the 1+1 layer. This allows the network to access the node attributes each layer, which is essential for enabling the MPS-GNN to capture node features corresponding to the O.r, terms in the meta- path construction as shown in the ablation study in A.2p. As in Ferrini et al. (2024). the definition can
be generalized to multiple meta-paths by concatenating the embeddings obtained from each of them using (1+1) n (1+1)
A=1 (e.)) where K is the number of meta-paths, 1 (1(11) is the embedding of node according to ((e,k)
meta-path lo and is the concatenation operator.
8

---

Published in Transactions on Machine Learning Research (02/2025)
4.4 The overall algorithm
Algorithm 1 outlines the whole MPS-GNN procedure for the single meta-path case (in practice, K beam search is used and multiple meta-paths are learned). The algorithm takes as input a graph g, the set of available relations R, an initial set of binary node la- bels maximal meta-path length Max and stop- ping criteria value 7). It initializes the targets S with set of singletons (one per labelled node) and their alpha values (collectively indicated by A) to 1. At each iteration, the scoring function identifies the rela- tion minimizing Eq. and appends it to the meta-path mp. If no relation improves the loss by a factor 7, the algorithm stops and returns the meta-path mp" con- structed so far. The algorithm then evaluates mp by training MPS-GNN on node labels, and tests it using the Fi score (computed on validation set, omitted for brevily), which reflects the meta-path's performance when embedded in an MPS-GNN, as opposed to its poten- tial informativeness measured by the scoring function. For training MPS-GNN, node embeddings are updated using 7
Algorithm 1 MPS-GNN LEARNING
procedure LEARNMPS-GNNIG R,Y, LMAX,T)
mp" + F), t S A+1
while [mpl < LMAX do
r" +- arggmin, I(r)
D Eq.
if min L(r) 2 (l)nit(() then
return mp"
end if
mp mp, r
grn + TRAIN(MPS-GNN(m))) G,
Fi + (EST(gnn)
if F1 > Fí then
mp- + mp, F 7 F
end if
A,S NEW-TARGETS(S, end while return mp² end procedure
Eq.
The algorithm keeps track of the best meta-path path prefix together to its Fi score, and creates new target bags and a values as specified in Equations 5 and 6 for the next relation scoring round. The algorithm ends when the maximum meta-path length LMAX reached The algorithm is described for simplicity in the context of single meta-path and without the additional stopping criteria described in section 4.2 In practice, however, the implementation employs a beam search over the meta-path space, selecting the top K best-scoring meta-paths concatenating their embedding for the final node representation as detailed at the end of section 4.3 MPS-GNN scales linearly in the number of relations and nodes, thanks to its incremental construction of meta-paths. The value chosen for TAAX in the experiment. was 4, while n was set to 0.7. The method is however quite robust to variations in 7,, as the identified meta-paths remained unchanged for wide range of values in our experiments.
4.5 MPS-GNN is a self-explainable model
Self-cxplainable GNNs (Kakkad et al. 2023; Christiansen et al. 2023 to achieve explainability by-design. At high level, these models can be seen composed of two modules: a detector that extracts a class-discriminative subgraph, and a classifier that outputs prediction based on the extracted subgraph. By relying on meta-paths for its predictions, MPS-GNN is a self-explainable GNN model. The scoring function serves as the detector, identifying relevant meta-paths, while the network built using them acts as the classifier. By construction, the network can only access the meta-path inducod subgraph, making it strictly sufficient by construction (no changes outside the meta-path induced graph affect the prediction). An analysis of the faithfulness of MPS-GNN's explanations is provided in Section 5.3 While most approaches for GNN explainability focus the topological aspect, by identifying (hard soft) subgraphs as explanations, determining which node features contribute to the prediction is also relevant from an interpretability perspective. While interpretability at the node feature level could be encouraged by introducing sparsifying norms for the learnable parameter vectors in Eq. 7 guaranteeing a fully transparent processing of node features in the layerwise node embedding computation is beyond the scope of current GNN- architectures.
class of GNN models that aims
4.6 Comparison with MP-GNN
The novelty of our approach compared to MP-GNN lies in our model's ability learn meta-paths that are relevant. to the target node class, not merely based their existence but statistical measures related
9

---

Published in Transactions on Machine Learning Research (02/2025)
to their occurrences. In practice the key difference between MPS-GNN and MP-GNN lies in the way in which relations are scored. Specifically MP-GNN predicts the class label of a node in the first iteration, with ih = @² z, max,eN; Wa where the max aggregation of the neighbours is used, indicating that a candidate relation r is informative for the label of a node u if at least one of the neighbors N of v according to r belongs to the ground-truth meta-path, and e has the right features. To leverage meta-path occurrences, MPS-GNN employs sum aggregation strategy, as detailed in Eq. 2 enabling the counting of their occurrences.
In subsequent iterations, MP-GNN also employs a bag creation process, where positive bags are formed by including neighbors of positive nodes that are predicted to be positive at least once across multiple prediction procedures. This formulation ensures that the node responsible for the positive label, and thus aligned with the correct meta-path, remains in a positive bag. Unlike this approach, however, we must ensure that all neighbor nodes involved in multiple occurrences of the correct meta-path are included in a positive bag. As detailed in eq. 5] the neighbors of positive nodes are therefore placed in a positive bag without the need of any additional prediction step.
The enhancements introduced in MPS-GNN, compared to MP-GNN, enable it to handle predictions over relational databases where the class label may depend statistical measures derived from meta-patl patt-ppahhho occurrences.
5 Experiments
Our experimental evaluation seeks to address the following research questions:
Q1 Can MPS-GNN recover the correct meta-path when increasing the setting complexity?
Q2 Does MPS-GNN outperform existing approaches in tasks over real world relational databases?
Q3 Is MPS-GNN self-explainable?
We compared MPS-GNN with approaches that don't 't require predefined meta-paths, handle numerous relations, and incorporate node features in learning. The identified competitors include: MLP, to test the sufficiency of target node features alone; GCN (Kipf & Welling, 2016), a baseline non-relational model; RGCN (Schlichtkrull
et al.
2017 extending GCN for multi-relational graphs, with distinct parameters for each edge type; HGN (Lv et al. 2021a), a heterogeneous GNN model extending GAT for multiple relations; GTN (Yun al. 2019a which transforms input graphs into different meta-path graphs where node representations are learned; Fast-GTN (Yun et al. 2022b), an optimized GTN variant; R-HGNN (Yu et al. 2021 relation-awee GNN using cross-relation message passing; and MP-GNN (Ferrini et al. 2024), the original meta-path GNN supporting only existentially quantified meta-paths.
We implemented our model using Py Geometric, and used the competitors' code from their respective papers for comparison. For training MPS-GNN, we used a 70/20/10 split for training, validation, and testing, respectively, and reported the test results for the model selected based on its validation performance. For the sake of comparison with Perrini et al. (2024), ; we set the maximum mela-path length to 4 and the beam size to 3. We employed Fi as evaluation metric to account for the unbalancing in many of the datasets. The code is freely available at Hyperparameters of competitors and MPS-GNN can be found in Table g in the Appendix.
5.1
Q1: MPS-GNN consistently identifies the correct meta-pate in count based synthetic scenarios
In order to address the first research question, we designed sequence of synthetic node classification scenarios where the correct structure to be learnt is known. In each scenario, node is labelled as positive if it is the starting point of at least occurrences of a given meta-path of length I, and negative otherwise. Crucially, existential ial quantification of meta-paths (as modelled by MP-GNN (Ferrini et al. 2024)) is insufficient here, as nodes which are starting points of less than e meta-path occurrences are labelled as negatives. We designed scenarios of increasing complexity by changing the length of the ground-truth meta-path 1, the number of
10

---

Published in Transactions on Machine Learning Research (02/2025)
occurrences c, and the overall number of relations in the dataset. See Figure 8 for the statistics of the different scenarios (left), and for a prototypical example for I == 2 and
3 (right).
Correct Pattern
TARGET NODES EXAMPLE
LEGEND
Relations: / % A
Node Typec &
Explanation nubgraph
S1
S2
S3
S4
S5
S6
S7
S8
5
5
5
5
10
10
10
10
langeh
2
2
3
4
2
2
3
2
3
3
2
2
3 3
2
Figure 6: (Left) sample scenario. Nodes are labeled as positive if and only they are the starting point of least c= 3 instances of the I -= meta-path "grey node 5 orange node & green node". (Right) statistics of synthetic datasets, with [R] total number of relations, e number of (correct) meta-path instances in positive nodes, 1 meta-path length. On top, the explanation subgraph for cach datasot. The complexity given by |R] (hat is visible from the table.
Table shows the Fi score of each model for an increasing complexity of the classification scenario. Results clearly show that this experimental setting is challenging for existing solutions. While the poor performance of MLP, which completely ignores the topological structure, and GCN, which ignores the difference wetween relations, are expected, solutions specifically conceived for heterogeneous networks also struggle with these datasets. Models like R-HGNN, HGN, GTN, and Fast-GTN, despite accounting for different relations in the graph, are affected by both the imbalance between positive and negative target nodes and the limited number of instances of neighbors of cortain type. RGCN and MP-GNN achieve better performance but are still sub- optimal. The former, like other relational methods, takes into account the diversity of relations in the graph but still uses all of them, thus struggling to single out the relevant portion of the graph. MP-GNN, on the other hand, suffers from its existential quantification assumption, and fails to find the correct meta-path in all scenarios. Conversely, MPS-GNN manages to achieve nearly-optimal performance in all scenarios, substantially outperforming all existing strategie Note that the lookahead capabilities of the scoring function are crucial to the effectiveness of MPS-GNN. Appendix Aopeedix[A.7ppp shows how replacing the scoring function with a simple greedy approach leads to failure in learning the correct meta-path. These results allow to answer the first rescarch question in the affirmative.
Table 1: F1 metric with standard deviations for synthetic datasets
S1
$2
S3
S4
S5
S6
S7
S8
MLP
0.466440000
0.44(440000)
0.48
0.47(440.00)
0.44(4-0.00)
0.51(+00.00
0.45((+0.00)
(.47(++0000
GCN
0.46 00)
0.46 02)
0.48(1:0.0 03)
0.52(4:0.08 050)
0.44(1:0 00)
0.48( 00)
0.46 00)
0.48(10..0
RGCN
0. 0.78(440.02)
0.87(4:0.03)
0.86 (o)
0.81(4:0002)
0.86(4-0.03)
0.77(+:0001)
0.91
0.79(400011
R-HGNN
0.50r400.0 00)
0.44( 03)
0.47(4+0.0m
0.47(110.04 04)
0.53( 00)
0.48(410.0)
0.46
0.48(400.0)
HGN
0.45(40.000)
0.46(4:0.00)
0.50(440.00 003
0.46(440.00)
0.46(440.00)
0.48(4+0.000
0.45(440.000
(000003)
0.40(4:0.12)
GTN
0.46 00)
0.52(:0..00
0.49( 00)
0.48(2:0.00 .0)
0.44( 00)
0.47(::0.00)
0.49(
0.47((:0000)
Fast-GTN
0.46 on)
1.48(19000)
0.51 00)
0.49
0.44(1:0 o0)
0.46(;10.00
0.53 .0)
0.47(::0.00
MPGNN
0.84(440.09)
0.82; 4:00
0.85
0.95(4:0.02)
0.89(4-0.06)
0.79(4:0.08)
(.84((-0.06)
0.71(4:0.21)
MPS-GNN
(0.00)
(=08
0.99 10)
(.98(20.00)
(209(2)000))
(.93
(20.00)
(.95
5.2 Q2: MPS-GNN surpasses competitors in real world databases, learning relevant meta-paths
Our approach is particularly useful for predictive tasks in relational databases with multiple tables, where features for a target entity may involve statistics from related tables. To address the second research question,
TTee residual error for IPS-GNU due the fact that despite relying on the correct meta-path, it occasionally leverages spurious instances where the relation sequence correct but (some of) the node features are not.
11

---

Published in Transactions on Machine Learning Research (02/2025)
thus focused three relational databases with many tables: EICU, medical database with 31 tables, where we predict patient stay duration in the eICU, modeled as binary node classification by thresholding duration at 20 hours to achieve two balanced classes.; MONDIAL, geographic database where the task is predicting whether a country's religion is Christian; and FrgastF1, containing Formula 1 data, where the task predicting the winner of a race in a binary classification task where larget nodes are represented by a combination of race and pilot. The databases were transformed into graphs as explained in Section B for disconnected components, we enhanced connectivity by clustering rows of auxiliary tables. Additional details for the datasets and the procedure are in the Appendix A.3
Results Table presents the F1 scores of MPS-GNN and its competitors across three real- world databases, averaged over runs with different seeds. The poor performance of MLP clearly indicates that using target node features only is insufficient for classification. Plain GCN, which treats the graph as homo- geneous, performs well only on the EICU dataset, where node degree differences exist between positive and negative nodes. Het- erogeneous GNN methods also struggle with these datasets, especially MONDIAL, where most approaches fail to outperform simple MLP, and only one (HGN) manages to substan- tially outperform the non-heterogeneous base- line (GCN). MP-GNN does not provide the per- formance boost that was observed when applied to knowledge graphs (Ferrini et al.) 2024).. confirming our intuition that existential quantification of meta-path insufficient when dealing with relational databases. On the other hand, MPS-GNN manages substantially outperform all competitors, thanks to its ability identify meta-paths that are informalive thanks to the statistics that can be computed over their realizations, shown in the following. It is worth noting that this result is achieved with one/two orders of magnitude fewer parameters than the runner-ups, namely HGN and R-HGNN. See Table in the Appendix for the details. Additionally, Table 10 in the Appendix shows that MPS-GNN has competitive execution times with respect to other heterogeneous GNN approaches, thanks to its ability to focus training on relevant meta-path induced subgraphs.
Table 2: Fi-score with standard deviations of our method and competitors on real-worle datasets.
EICU
MONDIAL
ErgastF1
MLP
0.53(+0.02)
0.52(++0000
0..0(#0.00)
GCN
0.89(10.00)
0.60(10.02)
0.50(10.01)
RGCN
0.70(==000)
0.53(+0.08)
(.00
R-HGNN
0.61(2:0.00)
0.61(+0.01)
(=020)
HGN
0.75(=0000)
0.72(#0.01)
0.70(=
GTN
0.56(10.02)
0.38(10.01)
0.60(10.01)
Fast-GTN
0.46(#4003)
(.39(40004)
0.60(+0.03)
MP-GNN 0.87(=+0002)
0.36(#0.06)
0.71(#0.01)
MPS-GNN 0.92(10.00)
0.74(10.01)
(.0.02))02)
EICU
MONDIAL
ErgastF1
Vital Aperiodic
previous
Border Country
Language
Race
Constructor
standings
M
Patient
Christian
Vital Periodic
provious Pattents
Ethnic
Border Country
Driver standings
group
Driver
MNV-
Figure 7: Extracted pttt- for the three real world datasets.
Identified Meta-Paths Figure 7 shows the meta meta-paths extracted by MPS-GNN in the three real world datasets, which clearly convey relevant features for the respective task. For EICU (left), meta-paths correlate the patient's length of stay (predictive (ask) with information on patients with similar periodic (lop) and aperiodic (bottom) vital signs. For MONDIAL (middle), Christianity is predicted collecting information about the language of border countries (top), and the ethnic group of the country and its neighbouring countries. Finally, in ErgastF1 the winner is predicted via meta-paths collecting information about the constructor (top) and driver (top) standings.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Finally, in Appendix A.8 present experimental evaluation where MPS-GNN is adapted to deal with temporal databases and tasks (Robinson et al. 2024], showing how it outperforms its competitors also in this context. Summing up, these results enable us to confidently answer Q2 in the affirmative.
5.3 Q3: MPS-GNN is a self- exllaixplae method
To address the third research question, we assessed the faithfulness of the extracted meta-paths. The meta-paths identified by the model from the graph are evaluated based on the complementary metrics of sulficiency and necessity. High sufficiency implies that changing the complement to the explanation (leaving the explanation unchanged) should not affect the model's output. High necessity implics that altering the explanation itself (leaving the complement unchanged) should result in change in the model's output. It is easy to show that our approach is inherently sufficient. Indeed, the computational graph of MPS-GNN consists solely of the subgraph containing the occurrences of the identified meta-paths. Necessity, on the other hand, is calculated as a distance metric, measuring the difference in predicted probabilities between the original predictions and those obtained after masking parts of the explanation (i.e. deleting some instances
N
of meta-paths). Defined as NEC = N ==
Σ (p) - PPr( where v is a target node, 9 is the original graph
and Pv denotes the probability associated with the predicted class. g' is obtained by removing certain meta-path occurrences (i.c. randomly removing some branches of the identified meta-paths) and (g') is the probability associated at the class predicted with Pa- Since MPS-GNN utilizes just the explanation for making prediction one should expect that removing some part of the explanation, has as effect decrease in prediction Fi.
EICU
MONDIAL
ErgastF1
0.6
0.3
0.2
75
75
Removed occurrences (%)
Removed occurrences
Removed accurrences (%)
Figure 8: Changes to F1 and posterior probability difference (necessity) when removing 25%, 50% and 75% of the learned meta-path occurrences for the real-world datasets with MPS-GNN, dashed line, and MP-GNN, solid line.
Figure 8 illustrates the effects of removing 25%, 50%, and 75% of the meta-path occurrences in terms of changes in Fi and necessity between original and modified graphs (Azzolin et al. 2025). In addition to the results for MPS-GNN (dashed linc), the figure includes the results for MP-GNN (solid line), which is also a self-explainable GNN model according to the reasoning in Section 4.5 In all datasets, there's a noticeable decline in Fi performance for MPS-GNN and a steep increase in probability difference, suggesting that the learned meta-paths are also necessary. These results clcarly indicate the faithfulness of the explanations of MPS-GNN. MP-GNN has a similar behaviour, albeit with lower F1 with respect to MPS-GNN because of its lower expressivity. The only exception is the MONDIAL dataset, where MP-GNN fails to learn any relevant pattern, resulting in a very low Fi score that remains approximately constant when removing meta-path occurrences.
6 Conclusion
We introduced novel approach to identify relevant meta-paths of relations for node classification tasks in heterogeneous graphs with a potentially large number of different relations, notably graphs derived from
13

---

Published in Transactions on Machine Learning Research (02/2025)
relational databases. Compared to earlier work, our approach does not require supervision and learns meta-paths for predictive features defined by aggregate statistics over meta-path occurrences. The explain- ability of our method is particularly beneficial for sensitive domains like medical or financial data, where it helps address fairness concerns by providing insights into prodictions. Experiments demonstrate advantages in accuracy and explainability.
Limitations and future works At this stage, our method is tailored for binary node classification but be extended to multiclass classification using standard one-vs-all strategies. However, this approach is inefficient, as it requires repeating the entire process for each class. The underlying principles of our local greedy meta-path construction based on scoring potential informativeness of relations directly applies also in the multiclass case, What would be needed in a multiclass adaptation of the approach is to replace the scalar functions ( and scalar node weights We, with vector-valued versions, and to modify the loss function accordingly. Similarly, node regression is currently not supported and would require a modification to the way relations are scored. Another limitation of the scoring function its reliance on well-connected graph structure; when target nodes have neighbors that are not connected to other target nodes, the scoring function requires a preprocessing step to create supernodes within the neighborhood, as implemented in cerlain real-world scenarios.
An interesting direction for future work involves incorporating temporal information into the process of learning optimal meta-paths. By doing so, the model would be capable of accounting for the temporal dimension, enabling it to better capture time-dependent relationships and dynamics within the graph.
7 Acknowledgments
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those the European Union or the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101120763 TANGO. AL acknowledges the support of the MUR PNRR project FAIR Future AT Research (PF00000013) funded by the NextGenerationFU.
14

---

Published in Transactions on Machine Learning Research (02/2025)
References
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Kenza Amara, Zhitao Ying, Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In Learning on Graphs Conference, pp. 44-1. PMLR, 2022.
Kenza Amara, Mennatallah El-Assady, and Rex Ying. GInx-eval: Towards in-distribution evaluation of graph neural network explanations. In XAT in Action: Past, Present, and Future Applications, 2023. URL
Steve Azzolin, Antonio Longa, Pictro Barbiero, Pictro Lio, and Andrea Passcrini. Global explainability of gnns via logic combination of learned concepts. In The Eleventh International Conference on Learning Represenlations, 2022.
Steve Azzolin, Antonio Longa, Stefano Teso, and Andrea Passerini. Reconsidering faithfulness in regular, self-explainable and domain invariant GNNs. In The Thirteenth International Conference on Learning Representations, 2025. URL http://///ooaerrreee...e////eaaa wtt.mmtt/oormmmmdds1oo0orsppppp
Peter Battaglia, Razvan Pascamu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for lcarning about objects, relations and physics. Advances in newral information processing systems, 29, 2016.
Bahareh Bina, Oliver Schulte, Branden Crawford, Zhensong Qian, and Yi Xiong. Simple decision forests for multi-relational classification. Decision Support Systems, 52693)126911 2013.
Yaomin Chang, Chuan Chen, Weibo Hu, Zibin Zheng, Xiaocong Zhou, and Shouzhi Chen. Megnn: Meta- path extracted graph neural network for heterogeneous graph representation learning. Knowledge- Based 107661.. URL
Systems, 107611 2022. ISSN 0950-7051. doi:
https://wwer wwwpw//wweennnceettccccmm ott.://www......o.cccccc..caaaan
Jialin Chen, Shirley Wu, Abhijit Gupta, and Rex Ying. D4explainer: In-distribution explanations of graph neural network via discrete denoising diffusion. Advances in Neural Information Processing Systems, 36, 2024.
Mare Christiansen, Lea Villadsen, Zhiqiang Zhong, Stefano Teso, and Davide Mottin. How faithful are self-explainable gnns? arXiv preprint or 230:8 15096, 2023.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD'96, pp. 226 231, AAAI Press, 1996.
Francesco Ferrini, Antonio Longa, Andrea Passerini, and Manfred Jaeger. Meta-path learning for multi- relational graph neural networks. In Soledad Villar and Benjamin Chamberlain (eds.), Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pp. html
2:1 2:17. PMLR, 27-30 30 Nov 2024. URL httph: httt:e////rrccedingg. mmr press//231/Eerrinmg
Matthias Fey, Weihua Hu, Kexin Huang, Jan Fric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Relational deep learning: Graph representation learning on relational databases, 2023. URL htttss://arxii http://aaxvvvvgr/reee// www./org/////eeeeeeeooooeee 2212/
James Foulds and Eibe Frank. A review of multi-instance learning assumptions. The knowledge engineering review, 25(1) 25, 2010.
for heterogeneous graph eunbeddnng. In Proceedings of the web conference 2020, pp. 2331-2344 2241, 2020. Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neural network
Takuo Hamaguchi, Hidckazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge transfer for out-of- knowledge-base entities: A graph neural network approach. arXiv preprint arxio: 05674, 2017.
15

---

Published in Transactions on Machine Learning Research (02/2025)
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogencous graph transformer. In Proceedings of the web conference 2020, pp. 2704-2710, 2020.
A. Johnson, T. Pollard, O. Badawi, and J. Raffa. eicu collaborative research database demo (version 2.0.1); 2021. URL httttt:////doi..... /tt.://..rrr//.111//////1///
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. A survey on ex- plainability of graph neural networks. arXiv preprint orNau:2306.01958 2023.
Thomas N. Kipf and Max Welling. Semi-supprvvsed classification with graph convolutional networks. CoRR, Abs//160.00907,, 2016. URL http://arxiv.
Li, Yilun Jin, Guojie Song, Zihao Zhu, Chuan Shi, and Yiming Wang. Graphinss: Efficient meta-path selection in semantically aligned feature space for graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 4206 4214, 2021.
Antonio Longa, Steve Azzolin, Gabriele Santin, Giulia Cencetti, Pietro Lio, Bruno Lepri, and Andrea Passerini. Explaining the explainers in graph neural networks: comparative study. ACM Comput. Surv., September 2024. ISSN 0360-0300. doi: 10.1145 10.1144//6696444 URT https://doi. http::///......///....oo// 1111111.115/336444
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming Hc, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, pp. 1150-1166 New York, NY, USA, 2021a. Association for Computing Machinery. ISBN 9781450383325, doi: 00.115584447548344773300 URL https:///oli org/ 10. 10.1145/3447544 3467350
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD conference knowledge discovery & data mining, pp. 1150-114 1160, 2021b.
Wolfgang May. Information extraction and integration with FLORID: The MONDIAL case study. Technical Report 131, Universität Freiburg, Institut für Informatik, 1999. Available from http://dbis. informatiiin uni- uni-goettingen. de/Mondial
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pp. 15524-15543. PMLR, 2022.
Anasua Mitra, Priyesh Vijayan, Sanasam Ranbir Singh, Diganta Goswami, Srinivasan Parthasarathy, and Balaraman Ravindran. Revisiting link prediction on heterogeneous graphs with a multi- view perspective. Tn 2022 IEFE International Conference on Data Mining (TCDM), pp. 358 368-367. IEFE, 2022.
Alessio Ragno, Biagio La Rosa, and Roberto Capobianco. Prototype-based interpretable graph neural networks. IEEE Transactions on Artificial Intelligence, 5(4):1486 1495, 2022.
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan E. Lenssen, Yiwen Yuan, Zecheng Zhang, Xinwei He, and Jure Leskovee. Relbench: A benchmark for deep learning on relational databases, 2024. URL https://arxiv. org htgg/abs/2407, 20060
Alvaro Sanzhezz-onzzaez,, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control, 2018. abs///bs/////
URL httts://arxiv hwtp///ss//....... 01242
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks, 2017. URL httpss:///a/at wttp://..rr//b///////////
06103
16

---

Published in Transactions on Machine Learning Research (02/2025)
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The semantic web: 15th international conference, ESWC 2018, Heraklion, Crete, Greece, June 3 7, 2018, proceedings 15, pp. 593 607. Springer, 2018.
Oliver Schulte, Baharch Bina, Branden Crawford, Derek Bingham, and Yi Xiong. A hicrarchy of indepen- dence assumptions for multi-relational bayes net classifiers. In 2013 IEEE Symposium on Compulational Intelligence and Data Mining (CIDM), pp. 150-159. TEEE, 2013.
Sangwoo Seo, Sungwon Kim, and Chanyoung Park. Interpretable protolype-based graph informa- tion bottleneck. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (ods.): Advances in Neural Information Processing Systems, volume 36, pp. 76737-76748 Curran Associates, Inc., 2023. URL https://prooceddngg.ntt wwt.seuuurrs..cppppeeeeeeeeeee Files//paprr/223//Eiee//
Minh Vu and My T Thai. Pgm-explaaner: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:12225 12235, 2020.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanlang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The world wide web conference, pp.
2019.
Xiaoqi Wang and Han Wei Shen. Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks. In The Eleventh International Conference on Learning Representations, 2022.
Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. In International Conference on Learning Representations, 2022.
Yongji WU, Defu Lian, Yiheng Xu, Le Wu, and Fnhong Chen. Graph convolutional networks with markov random field reasoning for social spammer detection. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 1054-1061, 2020.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advonces in neural information processing systems, 32, 2019.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In International Conference on Learning Represenlations, 2020.
Le Yu, Leilei Sun, Bowen Du, Chuanren Liu, Weifeng Lv, and Hui Xiong. Heterogeneous graph representation learning with relation awareness. CoRR, abs/2105.11122 11122, 2021. URL hutps:://arxivvor//aaa/ 11122
Le Yu, Leilei Sun, Bowen Du, Chuanren Liu, Weileng Lv, and Hui Xiong. Heterogeneous graph representation learning with relation awareness. IEEE Transoctions on Knowledge and Data Engineering, (5(6):5933 5947, 2022.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & dala mining, pp. 430-438, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explsinability of graph neural networks via subgraph explorations. In International conference on machine learning, pp. 12241- 122522 PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEFE transactions on paltern analysis and machine intelligence, (5(5))5782-5799) 2022.
Seongiun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus, E. Fox, and R. Garnett (ods.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019a. URL https:///prceedddgg www.roooedinggn.nurppps.... http://ppppp...eee////////////// Ga2234aabbb777700004444555511-a2
17

---

Published in Transactions on Machine Learning Research (02/2025)
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019b.
Seongjun Yun, Minbyul Jeong, Sungdong Yoo, Seunghun Lee, Yi Sean, Rachyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks: Learning meta-path graphs to improve gnns. Newral Networks, 153:104-119, 2022a.
Seongjun Yun, Minbyul Jeong, Sungdong Yoo, Seunghun Lee, Sean S. Yi, Raehyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks: Learning meta-path graphs improve gnns. Neural Networks, 153:104-119, 2022b. ISSN 0893-6080. doi: http://o.oor.ooo.o/oooo//eeeeeee http:///wwwwooooooooo.o/o.oooaa/
URL
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self-explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9127 9135, 2022.
Xu Zheng, Farhad Shirani, Tianchun Wang, Wei Cheng, Zhuomin Chen, Haifeng Chen, Hua Wei, and Dongsheng Luo. Towards robust fidelity for evaluating explainability graph neural networks, 2023.
Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang. Relation struclure-aware hetero- geneous graph neural network. In 2019 IEEE international conference on data mining (ICDM), pp. 1534 1539. IEEE, 2019.
18

---

Published in Transactions on Machine Learning Research (02/2025)
A Appendix
A.1 Second iteration loss computation
In this Section we show the loss computation and minimization for relation 'd' of the example in Figure Note that Z refers to the learned parameters related to the features of the target nodes in the previous
iteration with relation b (Figure 3b) and and [
represent the features of prescription nodes.
0
[ 0
F(B2, d) = ZO"
220
(wy + wa) + 20" [
(1io + wi1)
[
!]
F(B3, d) = 270T
(wis + wig)
(wro + w1) + 20
(wi2)
0
L(d) = min a (F(B3, d) 0,00
F(B2, d))
min 0,1
ZOT
(2ws 2wg w12 2ws 2wg
w10 w1
0
+20
(w10
w11 - 1))
min 2,1
ZOT
(wi2
0 w00 wii) 007
(w1o + w11 1 -1)
0
[
1 0
[0]
T
0:
T
W12 = 0;
W10. W11
A.2 Ablation study
In this section, we highlight the importance the skip connection W ( considered in equation Table anddl 4 demonstrate respectively the significance of skip connections in the synthetic and real-world settings. Without considering the initial larget node features, the F1 score drops siguificantly, underscoring the critical role these features play.
Table 3: F1 metric with standard deviations for synthetic datasets with MPS-GNN and MPS-GNN without using skip connection.
S1
$2
$3
S4
S5
S6
S7
S8
MPS-GNN
0.98(10.00)
0.99 0.98(10.01)
0.98 (10000))
0.99(10.00)
0.93 10)
0.04(10.00)
0.95(_0.00)
MPS-GNN.o slip 0.91(1000))
0.03(_0.01)
0. (.8001
0.91(10.01)
O. 10..00))
0.80(10.02)
(.90
0.85;10.03)
Table 4: Fj metric with standard deviations for real-world datasets with MPS-GNN and MPS-GNN without using skip connection.
EICU
MONDIAL Frgast
MPS-GNN 0.92(10.01)
0.74(10.01)
0.83(10.02)
MPS-GNN no skip 0.85(#0.02)
0.71(=0.01) 0.80(#0.01)
A.3 Real world setting
In our realdworld scenario, we utilized three relational databases, which are detailed below. To convert these databases into heterogencous graphs, we applied transformations to the attribute columns: categorical attributes were transformed using one-hot encoding, and numerical attributes were normalized the range [0, 1].
19

---

Published in Transactions on Machine Learning Research (02/2025)
To improve connectivity between target nodes, particularly when the transformation from relational database to a graph results in each target node (or row in the target table) becoming separate con- nected component, we employed simple clustering techniques on the rows of other tables based on their features.
Below, we provide detailed information about the databases and describe the clustering methods used when applicable.
EICU Medical database with 31 tables (node types from Johnson et al. (2021). The task is predicting the duration of patient's stay in the cICU after admission, modeled as binary node classification by thresholding duration at 20 hours to achieve two balanced classes. To create clusters of nodes, where each cluster is represented by a single new node that replaces all the nodes within that cluster, we utilized a categorical attribute for each table that is best suited for clustering the specific table.
Table 6 provides details about the clustering process applied to the nodes of the EICU database. For each table, the initial number of rows and the resulting number of clusters (representing the final number of nodes for that type) are shown. The 'Clustering Feature" column specifies the column used for creating clusters; if not specified, this indicates the absence of categorical features, and the DBSCAN algorithm is used instead.
We predict the religion of a country Christian (positive) with 114 instances vs. all other religions with 71 instances. In this dataset, clustering of tables is done using DBSCAN (Ester et al. 1996) clustering algorithm.
MONDIAL Database containing data from multiple geographical web data sources May
1999
Table shows the resulting number of clusters for each table of the original database. Clustering is computed using DBSCAN algorithm.
ErgastF1 Database containing Formula races from the 1950 season to the present day. It contains detailed information including lap times, pit stop durations, and qualifying performance for all races up 2017. The objective is to predict the winner of race using the data available before the race starts, such the list of participants and qualifying times, while the actual lap times during the race are not yet available.
Table 5: Setting of real-world datasets. [T] and [R] refers respectively to the total number of tables in the original database and the number of relations in the graph used by the models. Rows is the sum of all the rows of each specific database.
Database EICU
T
R
Rows
31
457325320
MONDIAL
40
45
21497
ErgastF1
14
33
544056
A.4 Details of competitors' architectures
In Table we present the hyperparameters for all competitors and MPS-GNN the real-world datasets. For the synthetic cases, the only difference lies in the # layers, which is adjusted to match the length of the correct meta-paths for the competitors. For the losses CE is cross-entropy and nll is negative log likelihood.
A.5 Number of parameters
In Table we present the total number of parameters required for evaluating the various models. In the synthetic setting, when comparing with the only two models that yield satisfactory results, observe that approach has similar number of parameters as RGCN (when the total number of relations in the graphs is limited) and MP-GNN. MP-GNN, which also considers only subset of graph relations like our
ctttps:///iccu-crd.miii "https//rrekationalllattt ott./taaset//tttteeeeeeesoos Manndial Mondial 6 9https//rehatiioalllaaa wwttas/tt/eet////eaooerraeeeeeee FF
20

---

Published in Transactions on Machine Learning Research (02/2025)
Table 6: Tables from the EICU dataset. "Clustering Feature' refers to the feature used to group the rows in each table. If not present, it means that the specific table does not have any feature for that purpose, so the DBSCAN algorithm employed. Clusters indicates the final number of nodes after the clustering step.
Table name
Clustering Feature
Rows
Clusters
admissiondrug
drughiclseqno
7417
578
admissiondx
admitdxname
7578
268
allergy
drughiclseqno
2475
251
apacheapsvar
2205
200
apachepatientresult
3676
200
apachepredvar
2205
200
careplancaroprovider
specialty
5627
40
careplaneol
specially
5627
careplangeneral
cplgroup
3314
careplangoal
cplcategory
3633
careplaninfectiioussisess
eplcategory
112
11
customlab
labothername
30
19
diagnosis
diagnosisstring
24978
110
hospital
region
186
infusiondrug
drugname
38256
257
intakooutput
celllabel
100466
740
lab
labname
434660
147
medication
drughiclseqno
75604
1027
microlab
organism
342
16
note
notepath
24758
360
nurseassessment
cellattributepathh
91589
81
nursecare
cellattributepathh
42080
nursccharting
mussigchartoolltpeeraaaam
1477163
pasthistory
pasthistorypath
12109
190
physicalexam
physicalexampath
84058
310
respiratorycare
currenthistoryseqquum
5436
243
respiratorychartigg
respchartvaluclaael
5436
243
treatment
treatmentstring
38290
414
vitalaperiodic
274088
200
vitalperiodic
1634960
200
method, designed have a lower number of parameters; however, still falls short of matching MPS-GNN's performance.
In the real-world setting, among the models that achieve decent results, GCN exhibits the lowest number of parameters on the EICU datasct. However, among the relational methods, MPS-GNN emerges as the most efficient. On the MONDIAL dataset, the two leading competitors, HGN and R-HGNN, despite achieving lower F1 scores, utilize all edge types and consequently require significantly larger number of parameters.
Finally, on the ErgastF1 dataset, although MP-GNN outperforms other methods in terms of parameter efficiency by considering different meta-paths, it results in considcrably lower Fj score. In contrast, HGN and R-HGNN exhibit exponential increase in the number of parameters.
21

---

Published in Transactions on Machine Learning Research (02/2025)
Table 7: Tables from the MONDIAL dataset. Clusters indicates the final number of clusters after applying DBSCAN algorithm on the features of the specific table.
Table name
Rows
Clusters
economy
234
ethnicGroup
540
65
language
144
20
politics
238
25
population
238
encorpasses
242
province
1450
18
organization
153
15
continent
city
3111
93
river
218
24
34
17
desert
63
lake
130
16
mountain
241
40
Table 8: Hyperparameters of competitors and MPS-GNN for the real-world datasots. The optimizer is omittod from the table as is Adam for all models. Ir denotes the learning rate, wd represents the weight decay, and Patience indicates the early stopping patience (if applicable).
Hyperparameters
# layers Embedding dim.
lr
wd
# epochs
Patience
Loss
MLP
32
0.01
0.0005
500
50
nll
GCN
2
32
0.01
0.0005
500
50
nll
RGCN
2 32
0.01
0.0005
500
50
nll
R- CGHNNN
2
64
0.001
0
200
50
CE
HGN
2
64
0.0001
0.0005
300
30
nll
GTN
64
0.01
0.001
200
CE
Fast-GTN
64
0.01
0.001
200
CE
MP-GNN
32
0.01
0.0005
500
50
nll
MPS-GNN
32
0.01
0.0005
500
50
nll
Table 9: Number of parameters for each model across synthetic and real-world datasets.
MLP
GCN
RGCN
R-HGNN
HGN
GTN
Fast-CTH
MP-GNN
MPS-GNN
S1
194
690
3730
525996
10927
866
126902
1346
3618
S2
194
690
6770
787796
42314
946
126942
1346
3618
S3
194
690
3730
525996
42314
866
126902
1346
3618
S4
194
690
6770
787796
74125
946
126942
1346
3618
S5
194
690
3730
525996
74125
866
126902
1346
6786
S6
194
690
6770
787796
74125
946
126942
1346
6786
S7
194
690
3730
525996
74125
866
126902
1346
6786
S8
194
690
6770
787796
74125
946
126942
8834
6786
EICU
1346
3506
400690
47496672
611785
32024
110408
24898
12066
MONDIAL
2144
90544
3709106
88396572
1142962
180554
1539457
183138
234050
ErgastF1
4356
198142
54224332
396543021
439021
2542354
11325242
23413
29538
A.6
Execution times
we present the training times for each model across the individual datasets. In the synthetic settings, observe that among models achieving significant Fi score (RGCN, MP-GNN, and MPS-GNN),
In Table 10
22

---

Published in Transactions on Machine Learning Research (02/2025)
MPS-GNN typically demonstrates the shortest exccution time. We would like to highlight that model is specifically designed to learn meaningful meta-paths in networks with many relation types, whereas the synthetic datasets are limited in the number of relation types. In the EICU database, while the MLP model achieves the shortest exccution time, it performs poorly in terms of F1. Among the models with notable results, MPS-GNN exhibits the best execution time. In the MONDIAL database, all models have relatively low execution times due the small graph size, as shown in Table 5 However, MPS-GNN still achieves the best Fi score. For the ErgastF1 dataset, while MLP again has the lowest execution time, its final accuracy is poor. In contrast, MPS-GNN is comparable them by 12 and 11 percentage points in Fi score, respectively. Overall, our approach is consistently neither the quickest nor the slowest, yet it reliably achieves the highest average Fl score across all settings.
MP-GNN and R-HGNN in terms of execution time but surpasses
Table 10: Training times, in seconds, for each model across synthetic and real-world datasets.
MLP
GCN
RGCN
H-HNNN
HGN
GTN
Fast-GTT
MP-GNN
MPS-GNN
S1
66
660
1094
898
363
388
315
234
322
S2
67
660
2197
674
375
570
812
1461
215
S3
73
675
536
612
380
260
456
657
356
S4
183
2112
551
373
697
369
986
157
S5
69
420
445
575
360
875
845
158
467
S6
69
620
111
616
377
567
167
153
321
S7
72
677
285
519
371
834
442
587
449
S8
74
777
167
680
373
878
765
1502
490
EICU
342
5882
4355
4842
3210
10324
682
5787
1273
MONDIAL
156
125
132
131
265
220
119
120
134
ErgastF1
543
954
1491
2456
2245
3015
2945
2280
2421
A.7 Scoring Function Lookahead Illustration
We report additional experiment demonstrating the lookahead capabilities implemented in the scoring function of our method, and its advantage over a simplistic greedy approach. We construct a synthetic dataset of a multi-relational graph with three relations and the ground truth melapath, T1,72 for the target. We compare our approach against a simple greedy one, in which one always extends the metapath with the relation for which a trained MPS-GNN achieves maximal Fj score. The results are presented in Table [ the first iteration of the scoring function, relation r1 achieves the lowest loss in our scoring function and would therefore be chosen the first relation of the metapath. Looking only at the immediate benefit of the relations in terms of the accuracy achieved by corresponding MPS-GNN, however, 72 would be selected as the best relation. The column r2-Extensions shows the Fi scores of all possible length 2 metapaths starting with r2. Comparing with the F1 score of the ground truth metapath we find that, indeed, starting the metapath with r2 a suboptimal choice, and that our scoring function correctly identifies the most informative relation to start the metapath with, even though this informativeness only is materialized after exlension the metapath with 72.
Table Comparison: our metapath construction vs. simple greedy alternative.
Iteration 1
F2- Extensions
Ground truth
Meta-paths
T2.
T2,
12,
Score
0.001
45
56
Fi
0.79
0.82
0.69
0.83
0.82
0.85
0.99
23

---

Published in Transactions on Machine Learning Research (02/2025)
A.8 Temporal experiment
Recently, novel benchmark, rel-bench Robinson et al. (2024) has been introduced. This benchmark consists of multiple relational databases represented as temporal graphs. Additionally, the authors propose RDL, a temporal-aware relational message-passing model. It's important to note that the released temporal graphs are not directly compatible with static models. Thorefore, in this section, we reconstruct one dataset from the rel-bench repository in a static format and apply our method to this static representation of the graph (setting in table 12). The tasks are: (1) dnf, predicting whether a driver will fail to finish a race within the next month, and (2) top3, predicting if driver will place in the top 3. To handle these temporal tasks, treated each instance of node at different timestamps distinct nodes with separate label predictions. Table 13 reports the Fi-scores for MPS-GNN and the baselines. Our approach outperforms all competitors, including RDL which performs lower due to overpredicting the majority class. Note that RDL cannot be straightforwardy appliod to our other datascts, being designed for temporal datasets. In Section A.8.1 wo provide the necessity calculations for these datasets.
Table 12: Setting of temporal real- world dataset.
Database
7
R
Rows
rel-f1
9
26
97606
Table 13: Fi-score with standard deviations of our method and competitors on two temporal datasets.
rel-fl-dnf
rel-fl-top3
MLP
0.48(=0.00)
0.48(=0.00)
GCN
0.57(10.01)
(.52(10.02)
RGCN
0.44(#0.02)
0.54(+0.02)
R-HGNN
0.60(=0.01)
0.63(=0.02)
HGN
0.61(#0.02)
0.61(=0.01)
GTN
0.41(10.02)
0.45(10.01)
Fast-GTN
0.5001))1))
0.50(+0.02)
MP-GNN
0.54(#0.02)
0.52(=0.02)
RDL
0.08(10.03)
(.53(11.7)
MPS-GNN
(=0.02)
0.65 (#0.01)
A.8.1 Necessity calculation in temporal tasks
In this section, we present the necessity calculation for the temporal datasets. Specifically, as detailed in Section 5.3 Table 14 and figureJ demonstrates that removing certain identified meta-paths results in decreased performance (Fi) and an increased necessity value. This finding confirms that the learned meta- paths are essential for the prediction task in these datasets as well.
Table 14: Changes to Fi and necessity when removing 25% 50%, and 75% of the learned meta-path occurrences for the real-world temporal tasks rel-fl-dnf and rel-fl-top3.
Necessity
Removed (%)
25
50
75
0
25
50
75
rel-fi-dnf
0.63
0.56
0.49
0.48
0.12
0.22
0.31
rel-fi-top3
0.65
0.62
0.55
0.50
0.19
0.34
0.34
24

---

Published in Transactions on Machine Learning Research (02/2025)
rel-fl-dnf
rel-f1-top3
1.0
0.8
0.6
0.4
0.2
75 Removed occurrences (%)
0
25
50
25
50
75
Removed occurrences (%)
Figure 9: Changes to F1 and posterior probability difference (necessity) when removing 25%, 50%, and 75% of the learned meta-path occurrences for the real-world temporal tasks rel-fl-dnf and rel-fl-top3.
A.9 Non-GNN models real-world databases
For the MONDIAL and ErgastF1 databases, non-GNN methods have shown competitive performance in the past. For example, (Schulte et al. (203 Bina et al. (2013) report Fi scores of 0.78 and 0.77 on MONDIAL, 0.4 and 0.3 points higher than MPS-GNN. However, these results are achieved on simplified version of the database with only 12 tables, requiring mamual feature selection. In contrast, MPS-GNN is applied directly to the raw input data across all 40 tables. The non-GNN methods use Multi-relational Bayes Net Classifiers and Simple Decision Forests, where reducing number of tables and relations aids performance. By comparison, MPS-GNN is designed handle scenarios with large number of relations effectively.
A.10
Toy example with more complex features
Relational database
Heterogeneous graph
13
LEGEND
Medication
Podent
Identified meta path
Prescription
6: L
2
Prosoritton
Medication
14
1
Pharmacy
Explanation subgraph for positive example
Patient
88 Department
Pharmacy
-uaeel
Nosture [3,
Testure 10,
Doctor
Node
type
Node feature
01.0
Dioo exeret areso poion
[Pfoomms preseriatio
Department
Relation
Ratation
Relatton
Rutationn
Figure 10: Toy example similar Figure 1 with more complex features on prescription nodes. As depicted in the legend (right), the first two positions of the feature vector determine an exempt prescription ([1,0) not exempt prescription ((0, 1]). The last value determine the price of the prescription in dollar. The highlighted subgraph shows prototypical counts-of-counts pattern characterising positive patients, namely having exempt prescriptions where the total cost is more then 100 dollars, each containing at least two medications
In Figure 10 we present a scenario similar the one depicted in Figure [ The key difference lics in the prescription nodes, which now have more complex feature representations. Specifically, the last value of the feature vector corresponds the price of each prescription.
25

---

Published in Transactions on Machine Learning Research (02/2025)
The first iteration of the scoring function follows the same process in the previous toy example, illustrated in Figures 3a and 3b The most notable aspect, however, is the second iteration, where the target nodes are prescription nodes, similar to Figure 5 where the model evaluates relation d and C. Here, we provide the computations involved in minimizing the loss. Notably, only relation allows the loss to be minimized to Therefore, relation will be the one included the identified meta-path
Minimization relation
6>0
0
F(B2, c) = -2e
0
+ Z
0
(W13) + Z
60)
70
20
1
0
1
F(Ba, c) - 220
0
+ ZO"
+ Z0"
(w13)
60
20
70
M(c) = min (F(Bs, d) F(B2, d)) e,
min or (0)
1
2
Minimization relation d
7>0
0
F(B2. 2
(ws + w6) + ZeT
0
(wio + wn) + ZOT
1
60]
70
[0]
0
[
F(B3, 2
(ws + (6) + T
1
(wio + +wi) 2OT
0
(WI2)
60
20
70
L(d) min e,
(F(Ba, d) F F(B2, d))
0
1
0
min
Z
0
(W12) + -
1
(w1o + w11) -0
0
(w1o + w11) - -
1
70
20
70
20
0
1
min
zor
0
(W12) + ZOT
(w10 + wi1 - 1) -0T
0
(wio + w11)
6,0
70
20
70
0
T
>>>
0;
W10, W11, W12 = 0
20
26


Reviews:
[{"review_id": "1UblIkxv1e", "reviewer": "Reviewer_tkeZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** - learning over relational databases is interesting problem\n\n**Weaknesses** - unfortunately, in my view there are many major ones:\n- The paper is technically very badly written, at several places very unclear, failing to present the algorithm accurately. \n- Due to insufficient technical soundness of the presentation the presented conclusions are far from convincing.\n- Some of the claims of the paper are not supported by any evidence or not sufficiently convincing evidence.\n\nSee \"Requested Changes\" for further details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Meta-Path Statistics GNN (MPS-GNN) which builds on ideas of MP-GNN and learns meta-path based on learnable statistics. The MPS-GNN can be particularly useful for learning over relational databases. The learned meta-paths can further server as model-level explanations making the model self-explainable. The paper introduces adaptations to the MP-GNN algorithms and tests the method on multiple synthetic and real datasets in order to order to answer three research questions related to i) recovery of the correct meta-path, ii) performance in comparison to existing methods, and iii) self-explainability and answers all three favorably.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The organization of the text in the Methodology section is very unclear even confusing, and makes understanding of the method very difficult. E.g. \n- The differences compared to MP-GNN need to be explicitly and much more clearly explained.\n- Use clear references to other parts of texts where you explain further details (e.g. from intro of section 4 to later subsections).\n- Top of page 5 - you say feature function (2) can be determined by own attributes, putative features $\\mathbf{w}$ or a combination of both. What do you mean? The equation clearly has all of these so is determined by all. Also why do you call $\\mathbf{w}$ *putative features*? What do you mean by this?\n- What is the motivation for the loss-function in equation (3)? What is the motivation for the sigmoid transformation (wouldn't the min be at the same param values without the sigmoid)?\n- under equation (3) - you say in practice you approximate by sampling the bags. Why? The equation is already written as a sum over bags in the training set, not as an expectation over population nodes or similar. \n- under equation (4) - you say the meta-path construction can be terminated if $\\sum w_u$ term plays \"no significant role\". What does \"significant\" mean here? This has many standard interpretations in statistics and data science which you probably do not have in mind. Please be clear and precise.\n- under equation (4) - you say, you could possibly learn $\\mathbf{w}$ by regression. How? Where would the supervision come from?\n- Figure 2 bottom - you claim that $alpha(4, \\mathcal{B}_2)=alpha(4, \\mathcal{B}_3)=2Z$. This is very confusing when comparing to equation (6) which seem to accumulate only across nodes within the same bag. Also first para in section 4.1 says that weights of a node can be different for different bags. Either the notation is confusing or this is not correct. \n- Where is equation (7) used? How are the $W$ set? I presumed these are trained? When? Missing in Algo 1.\n- Which of the equations is actually the \"scoring function\"?\n- Section 4.4. - how are multiple meta-path learned? The greedy, local approach does not have a unique solution leading to a single best meta-path?\n- page 9 top - what do you mean by \"existential quantification assumption\"?\n- What are the last two columns in Table 2?\n2. The mathematical description needs complete revamp - there are very many typos/errors and the notation is unclear and confusing. E.g.\n- Page 4 2nd para - why do you introduce $u$ as entity and $v$ as node? These are the same or not? Moreover, you use both $u$ and $v$ for nodes later on. Similarly, why introducing $a_u$ and $x_v$ as two notational approaches for the same thing?\n- Page 4 para about *Greedy* - indexing of relation re-uses $i+1$ index twice.\n- Symbol $F$ is used twice in equation (1), each time meaning something else. It is further used to indicate $F_1$ score. This is extremely confusing. \n- It is unclear what the $\\cdot$ \\cdot symbol in the presented equations means. Is this to be element-wise product or inner product?\n- It is unclear what is the dimensionality of the inputs and outputs of the functions - some seem to be scalars, some vectors, see also above point.\n- It is unclear if there are some limits on the values of the weights $\\alpha$ and attributes. For example in page 5 under equation (6) you claim that nodes have *bigger* weights in subsequent tasks. This would assume that $\\alpha$ as well as the node features $x_v$ are always positive, or am I missing something?\n- I assume $\\theta$ and $\\mathbf{w}$ parameters are shared across different $r$\n- Links between equations are very unclear - for example, I think $\\alpha(v, \\mathcal{B})$ and $\\mathbf{w}$ are probably somehow related. I'm, however, not sure and definitely not sure how.\n- Figure 2 iteration c - is wrong, should be 10 and 11 set to 1 (not 8 and 9).\n- This list is probably not exhaustive. Please review and update your math carefully.\n- Equation (7) - are these inner products? The dimensions of feature embeddings are the same as the initial feature vector $x_v$? Irrespective of the original Table in the relational database of the individual elements (nodes)?\n3. Some claims are unclear, not convincing or not evidenced. Eg.\n- All your illustrative examples are on very simplistic problems with no node attributes (simplified to true / false). It is unclear to me how this would generalized to nodes with more complex features.\n- Bottom of page 6 - you say can be generalized to multiple meta-path by concatenation. Not clear to me how exactly. \n- section 5.1 - the claim in the title is formulated rather generic while the synthetic experiments focus on one problem setting only (at least c occurrences means positive). It is not clear if the method would behave similarly for other settings. Either provide more convincing evidence or reformulate your claims more conservatively. \n- Top page 9 - you say look ahead capabilities of scoring function are crucial but in intro of section 4 you say your strategy is greedy and local. Very confusing. Please clarify.\n- in section 5.2 - your real experiments in the main text are described as regression or multi-class. It is only apparent from appendix that you binarize the outcomes. Make this clear in the main text.\n- Section 5.2 Results - you claim that MPS-GNN outperforms other methods \"thanks to its ability to identify meta-path that are informative thanks to the statistics ... \". From the presented results in Table 2 MPS-GNN outperforms other methods but the reason for this better performance is not quite clear. \n- Section 5.2 - the title claims self-explainability of the method. The sufficiency and necessity of the meta-path are interesting but in my view do not support a fairly generic claim of self-explainability of the method. It is clear that the path matters for the decision but what are the particular features in the path which make the algorithm to decide 0 or 1?\n- The results presented in Table 3 are difficult to interpret. What do you mean by dropping x% of meta-path occurrences? Have these been dropped randomly? Wouldn't changing the explanation mean changing the features within the meta-path rather than dropping meta-paths?\n- In conclusions you claim your method offers advantages over other methods in terms of sparsity. I haven't seen any evidence for this.\n- This list is probably not exhaustive. Please review your claims carefully and provide convincing evidence or re-formulate.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tjO4gCzKrA", "reviewer": "Reviewer_GSzS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is overall well-written. \n- Annonomous code is available.\n- This work conducts multiple experiments to address the three research questions (RQs) and provides strong empirical evidence demonstrating that the proposed method 1. can recover the correct meta-paths with increasing complexity 2. outperforms existing approaches on real-world relational datasets 3. is a self-explainable method.\n\nWeaknesses:\n- It appears that the previous approach, MP-GNN [1], serves as the fundamental baseline for the proposed method, as also outlined in Section 4.6. However, if I am not missing the information, in Section 5.3, the same F1 and necessity tests (Table 3 and Figure 5) are not conducted or presented for the MP-GNN baseline.\n\n- It would be helpful to include a visualization of the synthetic data, if possible, or a figure demonstrating the increasing complexity of synthetic data from S1 to S8 as the number of relations increases, apart from figure 3.\n\n\n[1] Francesco Ferrini, Antonio Longa, Andrea Passerini, and Manfred Jaeger. Meta-path learning for multirelational graph neural networks. In Soledad Villar and Benjamin Chamberlain (eds.), Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pp. 2:1–2:17. PMLR, 27–30 Nov 2024. URL https://proceedings.mlr.press/v231/ferrini24a.html.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a self-explainable heterogeneous graph-based approach for relational learning. The method leverages aggregated statistics of meta-path co-occurrences to learn meta-paths for predictive tasks, (i.e., the binary classification of graph nodes). The proposed approach outperforms existing approahces in identifying relevant meta-paths for predictive tasks on both synthetic and real-world relational datasets. The faithfulness of the learned meta-paths is validated through controlled experiments by selectively removing a certain proportion of learned meta-path occurrences.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical for acceptance:\n- I would recommend a more in-depth discussion of the MP-GNN baseline and the proposed approach regarding the RQ on the self-explainable aspect of the method.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9WRUq9PWVI", "reviewer": "Reviewer_7hSS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- MPS-GNN shows better results than the considered baselines\n- the authors focus on explainability of the developed method\n- the paper is well structured, with articulated research questions and answers to them\n- Experiments include real-world datasets\n\nWeaknesses:\n- Not enough information about the baselines: how their hyperparameters were tuned and which architectures used exactly? (for example, there are no details about the MLP baseline architecture )\n- Discussion is missing. Potential points to discuss in it: limitations of MPS-GNN; potential for extensions (e.g., regression problems);  future work\n\n- The authors provide the runtimes of MPS-GNN and the baselines, but it would be good to have some time complexity analysis to understand how well MPS-GNN scales.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method for applying GNNs to relational databases, claiming state-of-the-art performance. Experiments include various datasets (synthetic and real-world) and numerous baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I suggest providing a more detailed toy problem example (similar to MP-GNN paper), in which the meta-path construction, and the GNN role are clearly explained step-by-step. \nAlso, in the Introduction I'd prefer to have more context on the tasks the proposed approach can be applied to. (In my opinion, Figure 1 alone is not enough). Other examples than the count-on-count prediction might also help further.\n\n- adding runtime complexity analysis and/or discuss the runtime scalability of MPS-GNN to as the datasets increase (in terms of databases sizes, #relations, #features).\n\n- adding more details about the baselines\n\n- adding the Discussion section", "broader_impact_concerns": "some acknowledgement of model Fairness concerns when working with sensitive data (medical, financial etc.) might be added to the Discussion section", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We received three reviews, two of which were positive and one (tkeZ) negative. The first two reviewers highlighted a few concerns related mostly to the discussion of the method (hyper-parameters choice, runtime complexity, visualization). They did not engage further in the rebuttal, but in my opinion the author's answers were satisfying on all counts. Reviewer tkeZ had a very broad set of (valid) concerns related to the clarity of the method, the notation, and the organization, which were addressed in a complete way during rebuttal (no point remains open). Overall, all reviewers agree on the validity of the approach and on the experimental evaluation.
Decision: Accept (poster)