Meta-Path Learning for Multi-relational Graph Neural Networks
Existing multi-relational graph neural networks use one of two strategies for
identifying informative relations: either they reduce this problem to low-level
weight learning, or they rely on handcrafted chains of relational dependencies,
called meta-paths. However, the former approach faces challenges in the
presence of many relations (e.g., knowledge graphs), while the latter requires
substantial domain expertise to identify relevant meta-paths. In this work we
propose a novel approach to learn meta-paths and meta-path GNNs that are highly
accurate based on a small number of informative meta-paths. Key element of our
approach is a scoring function for measuring the potential informativeness of a
relation in the incremental construction of the meta-path. Our experimental
evaluation shows that the approach manages to correctly identify relevant
meta-paths even with a large number of relations, and substantially outperforms
existing multi-relational GNNs on synthetic and real-world experiments.
Francesco Ferrini, Antonio Longa, Andrea Passerini, Manfred Jaeger
# Meta-Path Learning for Multi-relational Graph Neural Networks

###### Abstract

Existing multi-relational graph neural networks use one of two strategies for identifying informative relations: either they reduce this problem to low-level weight learning, or they rely on handcrafted chains of relational dependencies, called meta-paths. However, the former approach faces challenges in the presence of many relations (e.g., knowledge graphs), while the latter requires substantial domain expertise to identify relevant meta-paths. In this work we propose a novel approach to learn meta-paths and meta-path GNNs that are highly accurate based on a small number of informative meta-paths. Key element of our approach is a scoring function for measuring the potential informativeness of a relation in the incremental construction of the meta-path. Our experimental evaluation shows that the approach manages to correctly identify relevant meta-paths even with a large number of relations, and substantially outperforms existing multi-relational GNNs on synthetic and real-world experiments.

## 1 Introduction

Graph neural networks (GNNs) have emerged as a powerful framework for analyzing networked data [6; 8; 18; 24], enabling effective learning and representation of complex relationships in several real-world applications [2; 23; 31; 39]. Standard GNN approaches have mostly focused on homogeneous graphs [7; 30; 34], where all nodes and edges belong to a single type. However, many real-world graph datasets exhibit heterogeneity, with multiple types of nodes and relations [4; 22; 28].

Treating heterogeneous graphs as homogeneous and aggregating information uniformly across all relations is a suboptimal approach, as different relations can convey largely different semantic information about the nodes they connect. A simple and effective strategy to retain the rich semantic information present in heterogeneous graphs is relying on meta-paths, which are chains of relational dependencies (e.g., "actor -> acted in -> movie -> has genre"). The challenge lies in determining the relevant meta-paths in a given graph. Existing methods either rely on predefined meta-paths defined by domain experts [3; 5; 32], which are extremely expensive to collect, or learn "soft" meta-paths by learning to assign weights to relations [25; 37; 38], an approach that only works with few relations and fails to scale to knowledge graphs. Solutions conceived for mining meta-paths from knowledge graphs typically consider relations only, ignoring node features altogether [16; 33].

To overcome these limitations, we propose a novel approach to learn meta-paths and meta-path GNNs that are highly accurate based on a small number of informative meta-paths. Key to our approach is the formalization of a scoring function, inspired by the relational information gain principle [14], that evaluates the potential informativeness of a relation in the incremental construction of the meta-path. This allows to learn a Meta-Path Graph Neural Network (MP-GNN) in which different layers convey information from different relations while retaining node-specific features in the aggregation process.

The main contributions of this work can be summarized as follows:
* We propose a scoring function evaluating the potential informativeness of a relation in the meta-path construction.
* We introduce MP-GNN, a simple variant of the RGCN architecture, which effectively combines learned meta-paths and node features into a multi-relational graph processing architecture.
* We provide an extensive experimental evaluation on synthetic and real-world datasets showing how our approach substantially outperforms existing multi-relational GNNs when dealing with graphs with a large number of relations.

## 2 Related work

In recent research, meta-path mining has emerged as an effective approach for analyzing heterogeneous graphs, relying on frequency cutoffs and sequential pattern mining strategies to identify promising meta-paths [17, 26, 36]. In the field of neuro-symbolic reasoning for knowledge graph completion (KGC), various approaches use reinforcement learning-based algorithms to explore relation-paths and derive logical formulas [16, 33]. Other approaches [11, 12, 20], search for the most relevant meta-path using variants of random walk search. A major limitation of all these approaches is that they are incapable of accounting for node features in determining the relevance of a candidate meta-path, making them unusable in knowledge graph embedding scenarios.

In the field of heterogeneous graph embedding, several methods have been proposed to enhance node and graph embedding by incorporating meta-paths. These methods can be broadly categorized into two groups: those using predefined meta-paths and those learning meta-paths by weighting the contribution of different relations.

In the first group, Meta-path Aggregated Graph Neural Network [5] focuses on aggregating node features along predefined meta-paths using an attention mechanism, capturing diverse structural patterns. Heterogeneous Attention Network [32] introduces a hierarchical attention mechanism to handle heterogeneous graphs, enhancing performance and interpretability. GraphMSE [13] tackles the problem of information-rich meta-path selection by aggregating information using different meta-paths and adopting BFS (Breadth First Search) as meta-path expansion strategy. Meta-path extracted graph neural network [3] incorporates message passing and emphasizes interpretability and semantic relationships. However, these approaches require that meta-paths are provided beforehand, something which severely limits their adaptability.

In the second group, Relational Graph Convolutional Networks (RGCN) [25] capture relation-specific patterns with distinct trainable parameters for each edge type. R-HGNN [35] uses a dedicated graph convolution component for unique node representations from relation-specific graphs. RSHN [40] integrates Coarsened Line Graph Neural Network (CL-GNN) for enhanced embedding in large-scale heterogeneous graphs. Graph Transformer Networks (GTN) [37] learn task-specific multi-hop connections (i.e., meta-paths) for useful node representations. FastGTN [38] addresses GTN's high complexity by implicitly transforming graphs. HGN [15] employs GAT as a backbone for a simple yet effective model. HGT [9] uses node and edge-type dependent parameters for heterogeneous attention. MVHRE [19] enriches relational representations for link prediction using a multi-view network representation learning framework. While effective with a small number of candidate relations, these approaches' performance degrades as the number increases, as shown in our experimental evaluation.

## 3 Preliminary

In this section, we provide an overview of fundamental concepts of our approach.

**Heterogeneous graph.** A heterogeneous graph is a directed graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T}_{v},\mathcal{T}_{e})\) where \(\mathcal{V}\) is the set of nodes or entities and \(\mathcal{E}\) is the set of edges. Each node \(v\) and edge \(e\) has a type, specified by the mapping functions \(\tau_{v}(v):\mathcal{V}\rightarrow\mathcal{T}_{v}\) and \(\tau_{e}(e):\mathcal{E}\rightarrow\mathcal{T}_{e}\). Moreover, each node \(v\) has a feature vector \(x_{v}\in\mathrm{I\!R}^{d}\).

**Meta-path** A meta-path \(mp\) is a relation sequence defined on a heterogeneous graph \(\mathcal{G}\), denoted in the form \(\xrightarrow{r_{1}}\xrightarrow{r_{2}}...\xrightarrow{r_{L}}\), where \(r_{1},...,r_{L}\) are relation types and for each consecutive pair of relations \(\xrightarrow{r_{i}}\xrightarrow{r_{i+1}}\) the intersection between the valid node types that are the destination of \(\xrightarrow{r_{i}}\) and the valid node types that are the source of \(\xrightarrow{r_{i+1}}\) is non-empty. Note that this is a more general definition than
the one in [27], in that it allows multiple node types as sources and destinations of a given relation, consistently with what can be found in large general-purpose knowledge graphs.

**RGCN layer** The relational graph convolutional layer from [25] extends the standard convolution operation on graphs [10] to the multi-relational setting by assigning specific parameters for each relation type. Message passing update for node \(i\) at layer \(l\) is given by:

\[h_{i}^{(l+1)}=\sigma\left(W_{0}^{(l)}h_{i}^{(l)}+\sum_{r\in\mathcal{R}}\sum_{j \in\mathcal{N}_{i}^{r}}\frac{1}{c_{i,r}}W_{r}^{(l)}h_{j}^{(l)}\right) \tag{1}\]

where \(\mathcal{R}\) is the set of relations in the graph, \(\mathcal{N}_{i}^{r}\) is the set of \(r\)-neighbours of node \(i\) and \(c_{i,r}\) is a fixed or learnable normalizing parameter.

## 4 MP-GNN learning

The goal of our approach is to learn relevant meta-paths that can serve as predictive features for the node classification task. 1 Differently from the approaches that use all relations at the same time by weighting each edge type contribution, we focus on finding the relevant chains of relations (i.e., meta-paths) beneficial for making accurate predictions. Note that, differently from what happens in purely relational settings [11, 12, 17, 20, 26, 36], we assume here that the informativeness of a meta-path also depends on the features of the nodes that are being traversed (which include the node type, but also node attributes and potentially pre-computed node embeddings). Our approach accounts for this aspect in mining relevant meta-paths. Meta-paths are constructed in a greedy, incremental approach using the idea of relational information gain [14] to score candidate extensions of an already constructed meta-path prefix. Consider the toy node classification task in Figure 1. To incrementally build the correct meta-path (bottom right in the legend), one has to realize that "Main actor in" is a better candidate than "Appeared in". Intuitively, our scoring function does this by assigning weights (i.e., pseudo-labels) to nodes reached by a candidate relation in such a way that the label of the target node can be inferred by propagating the pseudo-label of the neighbour. Figure 2 shows an example of weight assignment for the "Main actor in" and "Appeared in" relations, indicating a higher score for the former. However, these pseudo-labels only hint at the potential informativeness of the relation. Indeed, being a main actor in a movie is not enough to qualify as an award winning actor, even in the toy example of Figure 1. The movie should be a drama (node feature), and be directed by an award winning director. Whether this potential informativeness actually materializes is determined in the following steps, where the pseudo-labels become new prediction targets for the next extension of the meta-path under construction. Details of this method are described in Section 4.1.

Figure 1: A toy node classification problem. Node shapes indicate types, while node attributes and edge types are encoded as colors. The task consist in labelling actor nodes (pentagons, which do not have attributes). An \(Actor\) is labelled as positive if involved as main actor in a drama directed by and award winning director.
Once a candidate meta-path has been extracted, it is used to build a MP-GNN in which each layer corresponds to a relation on the meta-path. Section 4.2 presents a formalization of this architecture, and shows how to extend it to account for multiple meta-paths. Finally, these ingredients are combined into an overall algorithm to jointly learn a meta-path and a corresponding MP-GNN. For the sake of readability, the algorithm is presented for the single meta-path case, but its extension to multiple meta-paths using a beam search is straightforward (we employed a beam size equal to three in the experiments). Note that this algorithm is designed to identify existential meta-path features, i.e., cases where the existence of an instance of a meta-path is informative for the class label. Adaprations and extensions where counts or proportions of meta-path realizations are the relevant feature are subject of future work.

### Scoring function

The goal of the scoring function is that of providing a measure of informativeness of a relation towards predicting node labels. We start discussing the first iteration, i.e., identifying the first relation in the meta-path, and then show how the function can be adapted to deal with meta-path extension.

In the first iteration, the scoring function takes as input a list of nodes together with their target labels. Under the previously introduced existential quantification assumption, a candidate relation \(r\) is informative for the label of a node \(i\) if at least one of the neighbors \(\mathcal{N}_{i}^{\tau}\) of \(i\) according to \(r\) belongs to the ground-truth meta-path, and \(i\) has the right features (remember that the label is assumed to depend on the combination of the meta-path and the features of the nodes being traversed). This can be formalized as follows:

\[\tilde{y}_{i}^{r}=\Theta^{T}h_{i}^{(0)}\cdot\max_{j\in\mathcal{N}_{i}^{r}}w_{j} \tag{2}\]

Here \(\Theta\) is a learnable weight vector accounting for the contribution of the node features, while \(w_{j}\) is a learnable node weight that is set (close) to 1 if node \(j\) is predicted as belonging to the ground-truth meta-path, and (close to) zero otherwise. The score of \(r\) is computed by minimizing the MSE between the predicted and ground truth node labels over \(\Theta\) and \(\mathbf{w}\):

\[s_{r}=\min_{\Theta,\mathbf{w}}\frac{1}{N}\sum_{i=1}^{N}(\tilde{y}_{i}^{r}-y_{ i})^{2} \tag{3}\]

The relation with the minimum score is selected as the first relation of the meta-path.

To explain how the scoring of the following relations in the meta-path works, it is important to remember that the weights \(\mathbf{w}\) represent a tentative assignment to neighbours as belonging or not-belonging to the ground-truth meta-path (i.e., their _potential informativeness_). Multiple potential assignments can be minimizers of Eq. 3. In the left panel of Figure 2, where relation \(r_{1}\) (green) is being scored, any minimizers of Eq. 3 requires \(w_{E}=1\) (to account for the positive label of node \(A\)) and \(W_{F}=0\) (to account for the negative label of node \(B\)). On the other hand, (0,1), (1,0) and (1,1) are all valid assignments to the \((W_{G},W_{A})\) pair. Indeed, the only constraint that the positive label of \(C\) enforces is that the bag \((W_{G},W_{A})\) contains at least one node with value 1, as happens in multi-instance classification settings [1]. We thus generate labelled bags of nodes for the following iteration(s) of meta-path construction, that will play the role of the node labels \(y\) in the initial iteration.

Figure 2: **First iteration:** the scoring function assigns a high score to the red (“Main actor in”) relation (left panel) by giving large weights to movies D and E, that are only connected to a positive node, and small weights to the other movie nodes. On the other hand, the green (“Appeared in”) relation (right panel) has low score, as no weight assignment can jointly explain the positive label of the A node and the negative label of the B node.
Positive bags are computed as follows:

\[B^{+}(i)=\{j\in\mathcal{N}_{i}^{r}\mid\nexists k:j\in\mathcal{N}_{k}^{r}\wedge y_{ k}=-1\} \tag{4}\]

where \(i\) is a positive-labelled node (\(y_{i}=+1\)). Negative bags, on the other hand, are singletons, i.e., given a negatively-labelled node \(j\), we create a negative bag \(B^{-}(k)=\{k\}\) for each of its neighbors \(k\in\mathcal{N}_{j}^{r}\). The informativeness of the new relation \(s\) (as extension of relation \(r\)) can now be computed in terms of its potential in predicting bag labels:

\[\tilde{y}_{B(i)}^{s}=\max_{j\in B(i)}\Bigl{(}\Theta^{T}h_{j}^{(0)}\cdot\max_{k \in\mathcal{N}_{j}^{r}}w_{k}\Bigr{)} \tag{5}\]

and obtained minimizing MSE at the bag-label level. See Figure 3 for a graphical representation of the components involved.

Once the next relation is selected, the procedure could in principle continue, by further expanding positive bags with a procedure analogous to Eq. 4, where \(i\) is itself replaced with a bag of nodes. However, this procedures ends up diluting information too much, so that the informativeness of relations becomes difficult to predict. We rather assign a positive label to a node within a bag if it is used to predict the positive label of the bag (Eq. 2) at least once out of \(M\) restarts with randomly initialized weights. See the Appendix for the details.

### Mp-Gnn

In the single meta-path MP-GNN, a meta-path \(mp=r_{1},...,r_{L}\) induces a multi-relational GNN with \(L\) layers, that we denote by MP-GNN(\(mp\)). The first layer is associated to the last relation of the meta-path \(r_{L}\), and so on until the final layer which is associated with \(r_{1}\). The message passing update is formalized as follows:

\[h_{i}^{(l+1)}=\sigma\left(W_{0}^{(l)}h_{i}^{(l)}+\sum_{j\in\mathcal{N}_{i}^{r _{L}-l+1}}\frac{1}{|\mathcal{N}_{i}^{r_{L}-l+1}|}W^{(l)}h_{j}^{(l)}\right) \tag{6}\]

where \(l\) ranges from \(1\) to \(L\).

The definition can be generalized to deal with multiple meta-paths by concatenating embeddings coming from the different meta-paths:

\[h_{i}^{(l)}=\big{\|}_{k=1}^{K}h_{(i,k)}^{(l)} \tag{7}\]

where \(K\) is the number of meta-paths, \(h_{(i,k)}^{(l)}\) is the embedding of node \(i\) according to meta-path \(k\) computed using Eq. 6 and \(\|\) is the concatenation operator.

It is worth mentioning here that while this definition of MP-GNN is a straightforward adaptation of the RGCN architecture to deal with learned meta-paths, more complex architectures involving

Figure 3: **Second iteration**: The scoring function assigns a high score to the purple (”Directed by”) relation (left panel) by assigning a large weight to the M director, which is only one connected to a positive bag, and small weights to the other directors. On the other hand, the “pink” (Inspired) relation (right panel) gets a low score as no weight assignment is compatible with the positive bag.
pre-defined meta-paths could in principle be employed [3; 5; 13; 32]. We opted for this simple choice in the paper so as to best single out the contribution of the scoring function in determining the performance of the resulting architecture.

### Overall algorithm

The overall algorithm for learning MP-GNN is outlined in Algorithm 1. The algorithm takes as inputs a heterogeneous graph \(\mathcal{G}\), a set of candidate relations \(\mathcal{R}\), a set of node-label pairs \(labels\) and a hyper-parameter \(L_{MAX}\) indicating the maximal length of candidate meta-paths. The algorithm repeatedly call the scoring function (Eq. 3) to score candidate relations and keeps track of the best scoring one. It then builds an MP-GNN with the current (partial) meta-path and trains it to predict node labels, using \(F_{1}\) score (computed on a validation set, omitted in the algorithm for the sake of compactness) as final meta-path evaluation metric. Note that this is the only "real" measure of meta-path quality, as the one computed by the scoring function is still a "potential" informativeness, that only fully materializes when the meta-path is embedded into an MP-GNN. The algorithm keeps track of the highest \(F_{1}\) meta-path prefix so far, and proceeds by generating labelled bags as described in Section 4.1 for the next round of relation scoring.

As previously mentioned, the algorithm is presented for the sake of simplicity in the single meta-path case. However, the actual implementation performs beam search on the space of meta-paths, retaining the \(K\) top-scoring ones according to Eq. 3 and concatenating their embeddings into the MP-GNN as per Eq. 7. Notice that in evaluating the resulting MP-GNN, meta-paths not contributing to increasing \(F_{1}\) are discarded, so as to retain only the informative meta-paths in the final architecture.

```
1:procedureLearnMP-GNN(\(\mathcal{G}\), \(\mathcal{R}\), \(labels\), \(L_{MAX}\))
2: Initialize \(mp^{*}\leftarrow[\ ]\), \(mp\leftarrow[\ ]\), \(F_{1}^{*}\gets 0\), \(target\gets labels\)
3:while\(|mp|<L_{MAX}\)do
4:for\(r\in\mathcal{R}\)do
5:\(s_{r}\leftarrow\textsc{score-relation}(\mathcal{G},target,r)\)\(\triangleright\) Equation 3
6:endfor
7:\(r^{*}\leftarrow\) best scoring relation
8:\(mp\gets mp,r^{*}\)
9:\(gnn\leftarrow\textsc{train}(\textsc{MP-GNN}(mp),\mathcal{G},labels)\)
10:\(F_{1}\leftarrow\textsc{test}(gnn)\)
11:if\(F_{1}>F_{1}^{*}\)then
12:\(mp^{*}\gets mp,\ F_{1}^{*}\gets F_{1}\)
13:endif
14:\(target\leftarrow\textsc{generate-bags}(target,r^{*})\)\(\triangleright\) Section 4.1
15:endwhile
16:return\(mp^{*}\)
17:endprocedure
```

**Algorithm 1**LearnMP-GNN algorithm. \(\mathcal{G}\) is a heterogeneous graph, \(\mathcal{R}\) is the set of possible relations, \(labels\) is the initial set of node-label pairs and \(L_{MAX}\) is the maximal meta-path length

## 5 Experimental results

Our experimental evaluation aims to answer the following research questions:

1. Can MP-GNN recover the correct meta-path for an increasing number of candidate relations?
2. Is MP-GNN competitive with existing approaches in real-world datasets with few relations?
3. Does MP-GNN outperform existing approaches in real-world datasets with many relations?

We compared MP-GNN with existing solutions that: 1) do not require to pre-specify relevant meta-paths, 2) can handle (possibly high-dimensional) node features. Given these requirements, we identified the following competitors:

* **RGCN**[25], a generalization of the GCN architecture to the multi-relational case, that employs a different matrix of parameters for each edge type.
* **GTN**[37] can convert an input graph into different meta-path graphs for specific tasks and learn node representations within these graphs.
* **FastGTN**[38], an efficient variant of GTN that avoids adjacency matrices multiplication for graph transformation.
* **R-HGNN**[35], employs a different convolution for each edge type. Finally combines different embeddings with a cross-relation message passing.
* **HGN**[15], utilizes GAT as backbone to design an extremely simple HGNN model.

We implemented MP-GNN using Pytorch Geometric [21], while the code of the competitors was taken from their respective papers. For MP-GNN we used Adam optimizer with a learning rate of 0.01. We set the maximum meta-path length \(L_{MAX}=4\) and the beam size \(K=3\). We used an 80/20/10 split between train, validation and test in all cases, with model selection performed on the validation set for all methods. We employed F1-macro score on the test set as evaluation metric to account for the unbalancing present in many of the datasets. The code is available at LINK.

In the following we report the experimental setting and the results we obtained in addressing each of the research questions under investigation. The statistics of the datasets used in the experiments are reported in the Appendix.

### Q1: MP-GNN consistently identifies the correct meta-path

In order to answer the first research question, we designed a controlled setting where the correct meta-path is known, and experiments can be run for an increasing number of candidate relations. We generated synthetic datasets where nodes are typed A or B, the number of relations \(|\mathcal{R}|\) varies in \(\{4,8,10,14\}\), and the number of relations that can connect more than one pair of node types (e.g., \(A\xrightarrow{\tau}B\) and \(A\xrightarrow{\tau}A\)). The ground truth meta-path consists of a (valid) sequence of relations and nodes of a given type (e.g., \(x\xrightarrow{\tau}A\xrightarrow{\tau}B\), with \(x\) being a node of arbitrary type). Nodes are labelled as positive if found to be starting points of a ground-truth meta-path, and negative otherwise. We generated labelled datasets using ground-truth meta-paths of different lenghts \(L\in\{2,3,4\}\). Details of the different settings can be found in the Appendix (Figure 7).

Figure 4 shows the \(F_{1}\) score for each model when varying the overall number of relations and the number of shared relations, for a ground-truth meta-path of length three. Darker cells correspond to higher \(F_{1}\) value. Results show that the performance of existing multi-relational GNN approaches is severely affected by the relational complexity of the graph, with RGCN and R-HGNN being more sensible to the overall number of candidate relations and GTN and FastGTN having bigger problems with the number of shared relations, while HGN has poor performance in all settings, likely due to its lack of an explicit modelling of relation types. Conversely, MP-GNN consistently achieves optimal or quasi-optimal performance in all settings. Whenever \(F_{1}=1\), MP-GNN manages to perfectly recover the ground-truth meta-path, while values smaller than one are due to spurious relations being added at the end of the meta-path (which however have a limited impact on predictive performance).

Figure 5 shows results when increasing the relational complexity of the network _and_ the length of the meta-path characterizing the positive class. Each setting corresponds to an entry in the main diagonal of Figure 4, where we additionally varied the length of the meta-path from 2 to 4. Results show that GTN, FastGTN and HGN struggle in most settings, while RGCN and R-HGNN are competitive in the simplest settings (few relations and/or short meta-paths) but its performance quickly degrade when the size of the search space increases. Again, MP-GNN consistently achieves excellent performance in all settings, almost always perfectly recovering the ground-truth meta-path.

Figure 4: Synthetic setting: F1-score (the darker the better) as a function of the overall number of relations (rows) and the number of shared relations (columns).
### Q2: MP-GNN achieves state-of-the-art results on real-world datasets with few relations

The second set of experiments focuses on popular real-world benchmarks for multi-relational GNNs. In all cases the task is multi-class classification at the node level. We quickly summarize the characteristics of the benchmarks in the following: **IMDB**: a dataset extracted from the popular Internet Movie Database. It contains 3 types of nodes (movies (M), directors (D) and actors (A)) and uses the genres of movies as labels. **DBLP**: citation network where nodes are of paper (P), author (A) or conference (C) type, connected by edge types PA, AP, PC, CP, and the task is predicting the research area of authors. **ACM**: again a citation network, similar to the one of DBLP with conference nodes replaced by subject (S) nodes (and edge types replaced accordingly).

Table 1 (top) shows the \(F_{1}\) scores achieves by the different methods. As expected, all approaches achieve similar results, which are consistent with the ones observed in previous work [38]. Indeed, the number of relations is very limited (three for IMDB, four for DBLP and ACM) and, most importantly, no relations are shared among different node pair types, substantially restricting the number of candidate meta-paths. Still, MP-GNN achieves slightly better results, most likely thanks to its ability to select a minimal set of meta-paths, as shown in Table 1 (bottom).

### Q3: MP-GNN substantially outperforms competitors on real-world datasets with many relations

The last set of experiments aims to evaluate MP-GNN in a complex real-world setting characterized by a large set of relations, as typical of general-purpose knowledge graphs. We thus designed a set of node-classification tasks over **FB15K-237**[29], which is a large knowledge graph derived from Freebase. Each entity in the graph is associated with a text description, that we transformed into a bag-of-words representation of length 100 (retaining the most frequent words in the dataset). We identified as target labels all many-to-one relations that have from 2 to 20 possible destination types (to avoid having classes with too few examples). Examples include gender, event type and a number of currency-related relations. See the Appendix for the statistics of the datasets.

Table 2 reports \(F_{1}\) scores for the different methods. GTN and FastGTN have serious difficulties in learning reasonable models in all cases. Indeed, the unbalancing in the class distribution, combined with the large pool of candidate relations to learn from, drives them to boil down to majority class

\begin{table}
\begin{tabular}{l l l l} \hline Model & DBLP & IMDB & ACM \\ \hline R-HGNN & 0.86\(\pm\)(0.04) & **0.64\(\pm\)**(0.01) & 0.9(\(\pm\)0.01) \\ HGN & **0.94\(\pm\)**(0.01) & 0.63(\pm\)(0.02) & 0.92(\(\pm\)0.02) \\ RGCN & 0.91\(\pm\)(0.01) & 0.6(\(\pm\)0.01) & 0.9(\(\pm\)0.02) \\ GTN & 0.9(\(\pm\)0.01) & 0.62(\(\pm\)0.01) & 0.91(\(\pm\)0.01) \\ FastGTN & 0.92(\(\pm\)0.00) & 0.63(\(\pm\)0.01) & **0.93(\(\pm\)**0.00) \\ MP-GNN & **0.94\(\pm\)**(0.01) & **0.64**(\(\pm\)0.01) & **0.93(\(\pm\)**0.00) \\ \hline GTN/ & APCPA, & MAM, & PAP, \\ FastGTN & APAPA, & MDM, & PSP, \\  & APA & MDMM & \\ MP-GNN & APCPA, & MAM, & PAP, \\  & APAPA & MDM & PSP \\ \hline \hline \end{tabular}
\end{table}
Table 1: Few-relations datasets. **(Top)**: \(F_{1}\) scores, mean and std computed over five runs. Best results highlighted in bold. **(Bottom)**: learnt meta-paths for MP-GNN and GTN/FastGTN (which learn the very same meta-paths). Other baselines not reported as they do not explicitly extract meta-paths.

Figure 5: Synthetic setting: F1-score as a function of the ground-truth meta-path length, for an increasing complexity of the search space.
prediction in most cases. Despite the better performance of RGCN, HGN, and R-HGNN, they still exhibit substantially lower F1-scores compared to MP-GNN. Notably MP-GNN is surpassed only by RGCN and R-HGNN in the "event" and "team sport" classification tasks, respectively. Figure 6 shows some examples of extracted meta-paths for two different classification tasks, namely predicting the currency of domestic tuition fees in educational institutions and predicting the sport a team is playing. In the former case, extracted meta-paths lead to the headquarters of the organization delivering the educational program, which clearly correlate with the currency being used. In the latter case, meta-paths include the league where the team is playing, which again carries information about the sport being played. Note that in both cases, node features are crucial in leveraging meta-path information, as there are not enough examples to generalize via, e.g., specific headquarter or sport league name. Indeed, an ablation experiment excluding node feature information (the typical setting of meta-path mining approaches [11, 17, 26]), shows that none of the methods manages to learn any sensible meta-path, always boiling down to learning majority class prediction rules (see Appendix 8). For the same reasons, plain meta-path mining fails to extract sensible meta-paths, resulting in poor performance (see Appendix 9 for the results using the popular PRA meta-path miner [11]).

Finally, to assess the computational efficiency of MP-GNN, we conducted a running time comparison, detailed in Appendix 10. Results show that our approach is comparable with that of the competitors on the synthetic and few relation (IMDB, DBLP, ACM) datasets. On the freebase tasks, which have a larger set of candidate relations, our approach is more expensive than (most) competitors, but these have substantially lower performance in terms of F1, with the fastest approaches (GTN and FastGTN) completely failing to learn anything sensible.

## 6 Conclusion

In this work we introduced a novel approach inspired by information theoretic principles to effectively learn meta-paths and meta-path based multi-relational GNNs in settings characterized by a large number of candidate relations combined with arbitrarily rich node features. Our experimental evaluation confirms the potential of the approach in recovering correct (in synthetic tasks) and informative (in real-world tasks) meta-paths despite the large number of candidate relations, a setting where existing multi-relational GNNs struggle to learn meaningful models.

Future work includes generalizing the approach to account for counts or proportions of meta-path realizations as relevant features, as well as more complex relational structures like meta-trees.

\begin{table}
\begin{tabular}{l l l l l l l} \hline Label & R-HGNN & HGN & RGCN & GTN & FastGTN & MP-GNN \\ \hline PNC & 0.72 & 0.68 & 0.74 & 0.33 & 0.33 & **0.83** \\ EDC & 0.6 & 0.75 & 0.71 & 0.12 & 0.12 & **0.96** \\ EIC & 0.63 & 0.65 & 0.73 & 0.12 & 0.12 & **0.8** \\ ELC & 0.47 & 0.74 & 0.72 & 0.12 & 0.15 & **0.78** \\ FBC & 0.45 & 0.48 & 0.42 & 0.14 & 0.14 & **0.61** \\ GNC & 0.8 & 0.74 & 0.82 & 0.19 & 0.19 & **0.90** \\ OC & 0.67 & 0.73 & 0.78 & 0.14 & 0.14 & **0.93** \\ G & 0.81 & 0.64 & 0.8 & 0.44 & 0.44 & **0.84** \\ TS & **0.67** & 0.53 & 0.62 & 0.09 & 0.09 & 0.63 \\ E & 0.89 & 0.8 & **0.98** & 0.07 & 0.07 & 0.96 \\ \hline \end{tabular}
\end{table}
Table 2: Many-relations dataset: F1-scores for the different node classification tasks on the FB15K-237 dataset. Results with standard deviations can be found in Table 7 in Appendix. See Table 3 in the Appendix for the meaning of the label acronyms.

Figure 6: Examples of learned meta-paths on two node classification tasks
## Acknowledgments

This research was supported by TAILOR, a project funded by the EU Horizon 2020 research and innovation program under GA No 952215. AL acknowledges the support of the MUR PNRR project FAIR - Future AI Research (PE00000013) funded by the NextGenerationEU.
