Prediction over PediaTypes. We report standard deviations over 5 runs. A
higher value means better doubly inductive link prediction performance. “Rand”
column contains unbiased estimations of the performance from a random
predictor. Both ISDEA+ and DEq-InGram consistently achieve better results than
the baselines. N/A*: Not available due to constant crashes.

(a) Relation prediction $(i,?,j)$ performance in %. Higher $\uparrow$ is
better.

Models | EN-FR | FR-EN | EN-DE | DE-EN | DB-WD | WD-DB | DB-YG | YG-DB
---|---|---|---|---|---|---|---|---
Rand | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$
GAT | 1.07$\pm 00.14$ | 1.01$\pm 00.01$ | 1.03$\pm 00.03$ | 1.11$\pm 00.09$ | 1.07$\pm 00.14$ | 0.99$\pm 00.21$ | 0.96$\pm 00.16$ | 1.09$\pm 00.25$
GIN | 1.01$\pm 00.03$ | 0.95$\pm 00.08$ | 1.03$\pm 00.06$ | 1.10$\pm 00.06$ | 0.96$\pm 00.15$ | 1.00$\pm 00.15$ | 0.92$\pm 00.15$ | 0.83$\pm 00.17$
GraphConv | 0.91$\pm 00.03$ | 0.97$\pm 00.06$ | 1.05$\pm 00.14$ | 1.01$\pm 00.03$ | 1.09$\pm 00.07$ | 0.91$\pm 00.04$ | 0.94$\pm 00.22$ | 0.88$\pm 00.20$
NBFNet | 4.43$\pm 01.24$ | 3.62$\pm 01.01$ | 2.49$\pm 01.23$ | 0.51$\pm 00.18$ | 4.18$\pm 02.17$ | 2.80$\pm 00.83$ | 1.63$\pm 00.89$ | 7.30$\pm 05.01$
RMPI | 3.92$\pm 02.08$ | 4.04$\pm 01.83$ | 3.37$\pm 02.20$ | 2.13$\pm 00.79$ | N/A* | 2.39$\pm 02.35$ | 7.36$\pm 09.03$ | 0.91$\pm 00.92$
InGram | 35.19$\pm 07.73$ | 12.40$\pm 07.55$ | 8.45$\pm 06.57$ | 16.46$\pm 16.33$ | 33.66$\pm 12.09$ | 25.69$\pm 03.88$ | 14.24$\pm 12.00$ | 15.83$\pm 12.59$
DEq-InGram (Ours) | 65.26$\pm 10.23$ |  26.90$\pm 12.97$ |  36.80$\pm 11.16$ |  25.34$\pm 18.48$ | 75.00$\pm 06.42$ | 60.35$\pm 02.56$ |  24.28$\pm 14.29$ |  30.82$\pm 10.43$
ISDEA+ (Ours) |  58.43$\pm 01.29$ | 48.68$\pm 00.96$ | 37.29$\pm 05.11$ | 75.08$\pm 01.99$ |  57.05$\pm 00.92$ |  56.00$\pm 01.17$ | 59.36$\pm 07.96$ | 49.41$\pm 00.85$

(b) Node prediction $(i,k,?)$ performance in %. Higher $\uparrow$ is better.

Models | EN-FR | FR-EN | EN-DE | DE-EN | DB-WD | WD-DB | DB-YG | YG-DB
---|---|---|---|---|---|---|---|---
Rand | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$ | 1.96$\pm 00.00$
GAT | 31.80$\pm 00.64$ | 30.19$\pm 02.30$ | 10.23$\pm 00.96$ | 8.68$\pm 01.69$ | 7.98$\pm 00.89$ | 16.26$\pm 00.34$ | 26.09$\pm 00.47$ | 33.06$\pm 00.29$
GIN | 34.59$\pm 04.64$ | 34.57$\pm 05.26$ | 17.69$\pm 07.91$ | 20.74$\pm 10.01$ | 12.42$\pm 06.59$ | 23.10$\pm 09.67$ | 23.72$\pm 01.62$ | 32.26$\pm 01.89$
GraphConv | 47.48$\pm 02.60$ | 40.37$\pm 01.52$ | 31.96$\pm 01.02$ | 28.46$\pm 00.13$ | 12.53$\pm 00.34$ | 35.82$\pm 03.54$ | 24.12$\pm 00.80$ | 37.05$\pm 00.51$
NBFNet |  64.17$\pm 02.68$ | 69.68$\pm 01.63$ |  57.50$\pm 02.66$ | 32.26$\pm 02.81$ |  34.56$\pm 02.54$ |  59.70$\pm 01.38$ | 33.32$\pm 01.11$ | 47.47$\pm 02.08$
RMPI | 48.27$\pm 03.74$ | 26.92$\pm 04.87$ | 27.38$\pm 03.09$ | 29.60$\pm 04.77$ | N/A* | 34.81$\pm 08.97$ |  33.29$\pm 03.20$ |  42.14$\pm 02.87$
InGram | 60.00$\pm 02.06$ | 41.59$\pm 06.37$ | 39.05$\pm 02.99$ |  45.44$\pm 01.69$ | 22.06$\pm 08.10$ | 42.54$\pm 04.50$ | 13.47$\pm 03.50$ | 20.09$\pm 04.96$
DEq-InGram (Ours) | 69.46$\pm 01.12$ |  57.65$\pm 05.54$ | 51.93$\pm 01.88$ | 57.06$\pm 01.96$ | 32.12$\pm 09.51$ | 57.84$\pm 03.28$ | 20.49$\pm 03.35$ | 33.01$\pm 08.87$
ISDEA+ (Ours) | 62.17$\pm 02.38$ | 44.67$\pm 01.92$ | 63.36$\pm 00.78$ |  47.78$\pm 00.48$ | 51.76$\pm 00.86$ | 60.15$\pm 00.69$ | 20.74$\pm 00.28$ | 26.24$\pm 02.03$

Table 4:  Relation & Node Hits@5 performance on Doubly Inductive Link
Prediction over PediaTypes. We report standard deviations over 5 runs. A
higher value means better doubly inductive link prediction performance. “Rand”
column contains unbiased estimations of the performance from a random
predictor. Both ISDEA+ and DEq-InGram consistently achieve better results than
the baselines. N/A*: Not available due to constant crashes.

(a) Relation prediction $(i,?,j)$ performance in %. Higher $\uparrow$ is
better.

Models | EN-FR | FR-EN | EN-DE | DE-EN | DB-WD | WD-DB | DB-YG | YG-DB
---|---|---|---|---|---|---|---|---
Rand | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$
GAT | 9.08$\pm 00.39$ | 8.63$\pm 00.25$ | 9.47$\pm 00.18$ | 9.20$\pm 00.24$ | 8.95$\pm 00.36$ | 8.63$\pm 00.29$ | 9.58$\pm 00.50$ | 9.16$\pm 00.23$
GIN | 9.09$\pm 00.16$ | 9.31$\pm 00.15$ | 9.18$\pm 00.28$ | 9.23$\pm 00.34$ | 9.12$\pm 00.12$ | 8.85$\pm 00.56$ | 8.53$\pm 00.66$ | 8.61$\pm 00.34$
GraphConv | 8.97$\pm 00.66$ | 8.74$\pm 00.26$ | 9.23$\pm 00.11$ | 8.82$\pm 00.10$ | 9.17$\pm 00.29$ | 9.11$\pm 00.50$ | 9.01$\pm 00.72$ | 8.73$\pm 00.15$
NBFNet | 12.94$\pm 01.77$ | 12.46$\pm 01.40$ | 8.56$\pm 01.67$ | 2.68$\pm 00.72$ | 13.44$\pm 04.02$ | 11.74$\pm 03.02$ | 11.95$\pm 03.78$ | 20.37$\pm 05.90$
RMPI | 16.39$\pm 04.15$ | 15.76$\pm 04.58$ | 15.86$\pm 08.05$ | 12.56$\pm 02.70$ | N/A* | 8.91$\pm 03.51$ | 24.25$\pm 19.24$ | 4.98$\pm 03.08$
InGram | 67.15$\pm 05.04$ | 37.86$\pm 14.41$ | 30.99$\pm 11.82$ | 40.00$\pm 13.02$ | 65.80$\pm 09.59$ | 51.66$\pm 03.57$ | 43.27$\pm 19.30$ | 51.54$\pm 26.09$
DEq-InGram (Ours) |  83.23$\pm 05.64$ |  59.83$\pm 11.57$ |  54.30$\pm 08.25$ |  57.65$\pm 15.74$ |  87.08$\pm 02.55$ |  70.79$\pm 03.80$ |  51.45$\pm 29.14$ |  75.85$\pm 07.26$
ISDEA+ (Ours) | 93.79$\pm 00.20$ | 91.21$\pm 00.25$ | 94.04$\pm 01.21$ | 96.64$\pm 00.13$ | 90.83$\pm 02.29$ | 93.97$\pm 00.45$ | 74.27$\pm 06.29$ | 92.75$\pm 00.40$

(b) Node prediction $(i,k,?)$ performance in %. Higher $\uparrow$ is better.

Models | EN-FR | FR-EN | EN-DE | DE-EN | DB-WD | WD-DB | DB-YG | YG-DB
---|---|---|---|---|---|---|---|---
Rand | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$ | 9.80$\pm 00.00$
GAT | 78.49$\pm 00.44$ | 74.70$\pm 00.68$ | 42.17$\pm 00.91$ | 42.39$\pm 00.52$ | 20.96$\pm 00.65$ | 57.26$\pm 00.89$ | 46.92$\pm 00.37$ | 59.20$\pm 00.41$
GIN | 79.96$\pm 01.88$ | 74.33$\pm 01.16$ | 53.97$\pm 07.61$ | 55.89$\pm 10.06$ | 25.05$\pm 09.23$ | 61.94$\pm 06.71$ | 46.56$\pm 01.37$ | 57.48$\pm 00.35$
GraphConv | 85.21$\pm 00.63$ | 80.67$\pm 00.30$ | 67.76$\pm 01.19$ | 64.97$\pm 00.43$ | 28.37$\pm 01.41$ | 67.36$\pm 02.37$ |  53.79$\pm 00.72$ | 64.13$\pm 00.23$
NBFNet | 81.48$\pm 02.24$ | 85.15$\pm 01.06$ | 77.62$\pm 02.41$ | 48.73$\pm 02.59$ | 51.52$\pm 03.21$ | 72.18$\pm 00.90$ | 44.01$\pm 01.40$ | 60.34$\pm 02.28$
RMPI | 82.47$\pm 02.25$ | 64.88$\pm 07.62$ | 67.24$\pm 04.38$ | 69.47$\pm 06.60$ | N/A* | 60.11$\pm 08.77$ | 51.57$\pm 05.03$ | 66.67$\pm 01.28$
InGram | 85.15$\pm 01.74$ | 72.32$\pm 05.31$ | 78.84$\pm 02.86$ | 81.01$\pm 00.97$ | 45.96$\pm 11.09$ | 74.88$\pm 03.09$ | 37.49$\pm 06.84$ | 50.66$\pm 06.76$
DEq-InGram (Ours) |  89.62$\pm 00.63$ |  81.54$\pm 02.82$ |  84.57$\pm 00.95$ | 87.16$\pm 01.04$ |  57.44$\pm 09.14$ |  83.14$\pm 01.64$ | 51.77$\pm 05.14$ |  65.33$\pm 09.57$
ISDEA+ (Ours) | 92.45$\pm 00.73$ | 71.24$\pm 02.13$ | 89.98$\pm 00.96$ |  82.65$\pm 00.79$ | 76.12$\pm 00.87$ | 83.33$\pm 00.46$ | 48.04$\pm 01.78$ | 57.92$\pm 01.47$

####  F.1.3 WikiTopics: Testing self-supervised pre-trained zero-shot meta-
learning capabilities

As discussed in Section 5.2, the WikiTopics dataset is created from the
WikiData-5M (Wang et al., 2021b) (under CC0 1.0 license). Each node in the
graphs of this dataset represents an entity described by an existing Wikipedia
page, and each relation type corresponds to a particular relation between the
entities, such as “director of” or “designed by”. The node and relation type
indices are codenames that start with the prefix “Q” and “P” respectively,
which are devoid of semantic meaning. Nevertheless, WikiData-5M (Wang et al.,
2021b) provides aliases for all nodes and relation types that map their
indices to textual descriptions, and we use these textual descriptions to
group the relation types into 11 different topic groups, or domains (we do not
however provide these textual descriptions to the models per the specification
of the doubly inductive link prediction task). In total, WikiData-5M (Wang et
al., 2021b) contains 822 relation types. We create WikiTopics datasets from
all 822 relation types, which comprise graphs with as many as 66 relation
types. Each graph has a disjoint set of relation types from all other graphs.
Table 5 shows the 11 topics/domains of the WikiTopics dataset, each
corresponding to a distinct KG with distinct relation types.

Table 5: The 11 different topics/domains of the WikiTopics dataset.

Domain KG index | Abbreviation | Description
---|---|---
T1 | Art | Art and Media Representation
T2 | Award | Award Nomination and Achievement
T3 | Edu | Education and Academia
T4 | Health | Health, Medicine, and Genetics
T5 | Infra | Infrastructure and Transportation
T6 | Loc | Location and Administrative Entity
T7 | Org | Organization and Membership
T8 | People | People and Social Relationship
T9 | Science | Science, Technology, and Language
T10 | Sport | Sport, and Game Competition
T11 | Tax | Taxonomy and Biology

To control the overall size of the graphs in WikiTopics, we downsample
$10,000$ nodes for each domain from the subgraph consisting of only the
triplets with the relation types belonging to that domain. We adopt the Forest
Fire sampling procedure with burning probability $p=0.8$ (Leskovec &
Faloutsos, 2006) implemented in the Little Ball of Fur Python package
(Rozemberczki et al., 2020). We then split the downsampled domain KG into 90%
observable triplets and 10% querying triplets to be predicted by the models.
When splitting, we ensure that the set of nodes in the querying triplets is a
subset of those in the observable triplets. This way, the model is not tasked
with the impossible task of predicting relation types between orphaned nodes
previously unseen in the observable part of the graph. This is implemented via
an iterative procedure, where we first sample a batch of missing triplets from
the downsampled domain graph, then discard those that contain unseen nodes in
the rest of the triplets, and repeat this process until the number of sampled
triplets reaches 10% of total triplets. Figure 6 shows the data statistics of
WikiTopics dataset.

| #Nodes | # Relations | #Triplets (Obv.) | #Triplets (Qry.) | Avg. Deg.
---|---|---|---|---|---
Art | 10000 | 45 | 28023 | 3113 |  6.23
Award | 10000 | 10 | 25056 | 2783 |  5.57
Edu | 10000 | 15 | 14193 | 1575 |  3.15
Health | 10000 | 20 | 15337 | 1703 |  3.41
Infra | 10000 | 27 | 21646 | 2405 |  4.81
Loc | 10000 | 35 | 80269 | 8918 | 17.84
Org | 10000 | 18 | 30214 | 3357 |  6.71
People | 10000 | 25 | 58530 | 6503 | 13.01
Sci | 10000 | 42 | 12516 | 1388 |  2.78
Sport | 10000 | 20 | 46717 | 5190 | 10.38
Tax | 10000 | 31 | 19416 | 2157 |  4.32

Figure 6: Statistics of WikiTopics: We report graph statistics including the
number of nodes, number of relations, observed (obv.) triplets, querying
(qry.) triplets, and average degree for each graph. We also report (in & out)
degree distribution on each graph at the bottom. We omit tail distribution
larger than 35 since they are fairly small and almost flat.

##### Self-supervised pre-trained zero-shot meta-learning tasks over
WikiTopics to train on a KG of one domain and test on a KG of a completely
unseen test domain

We train the models on each of the $11$ graphs for 5 random seeds, and for
each trained model checkpoint, we cross-test it on all the other 10 graphs,
resulting in a total of $550$ statistics. We report the mean results across
random seeds in heatmaps. We present a detailed results (heatmaps with values)
of Node and Relation Hits@10, Hits@1, and MRR for WikiTopics in Figures 7 and
8. Due to the large number of runs ($11\times 10=110$ different train-test
scenarios, each with 5 random seeds, resulting in a total of 550 runs) and the
time constraints to run all baseline models, we perform the evaluation over
only the three models (ISDEA+, DEq-InGram, and InGram) that are designed for
our doubly inductive link prediction task. Figure 7 shows that for the task of
predicting missing relation types $(i,?,j)$, ISDEA+ and DEq-InGram are
consistently better than InGram across all different metrics. Especially, the
structural double equivariant ISDEA+ model exhibits more consistent results
across different train-test scenarios than both DEq-InGram and InGram, and
achieves significantly better results in Hits@1 and MRR, showcasing its
ability for doubly inductive link prediction in a much harder evaluation
scenario. For the task of prediction missing nodes $(i,k,?)$ as shown in
Figure 8, ISDEA+, DEq-InGram, and InGram showcase comparable performance,
whereas ISDEA+ exhibits more consistent results across different train-test
scenarios than both DEq-InGram and InGram. We also note that similar to the
relation prediction task, ISDEA+ also exhibits the best performance in the
Hits@1 metric for the node prediction task.

(a) ISDEA+ Hits@10

(b) DEq-InGram Hits@10

(c) Original InGram Hits@10

(d) ISDEA+ Hits@1

(e) DEq-InGram Hits@1

(f) Original InGram Hits@1

(g) ISDEA+ MRR

(h) DEq-InGram MRR

(i) Original InGram MRR

Figure 7: Relation prediction $(i,?,j)$ performance over WikiTopics for
ISDEA+, DEq-InGram, and InGram (Lee et al., 2023). Each row within each
heatmap corresponds to a training graph, and each column within each heatmap
corresponds to a test graph. A darker color means better performance. Both
ISDEA, DEq-InGram perform significantly better than InGram, especially for
Hits@1 and MRR, whereas ISDEA+ exhibits more consistent results across
different train-test scenarios than both DEq-InGram and InGram.

(a) ISDEA+ Hits@10

(b) DEq-InGram Hits@10

(c) Original InGram Hits@10

(d) ISDEA+ Hits@1

(e) DEq-InGram Hits@1

(f) Original InGram Hits@1

(g) ISDEA+ MRR

(h) DEq-InGram MRR

(i) Original InGram MRR

Figure 8: Node prediction $(i,k,?)$ performance over WikiTopics for ISDEA+,
DEq-InGram, and InGram (Lee et al., 2023). Each row within each heatmap
corresponds to a training graph, and each column within each heatmap
corresponds to a test graph. A darker color means better performance. ISDEA+,
DEq-InGram, and InGram showcase comparable performance in general, and ISDEA+
exhibits the best performance on Hits@1 in particular.

##### Self-supervised pre-trained zero-shot meta-learning tasks over
WikiTopics to train on combined KGs with an increasing number of distinct
domains and test on KGs with completely unseen test domains

In Section 5.2, we describe an experiment conducted with WikiTopics, focusing
on the zero-shot meta-learning tasks and the effect of varying the number of
training KGs. For this experiment, we selected 8 out of the 11 domains from
WikiTopics. In each experimental setup, we randomly select
$1,2,3,\text{~{}or~{}}4$ KGs with distinct domains for training. The model’s
performance is then evaluated on each of the remaining KGs for testing. We
repeat this process to collect performance across various combinations,
enabling us to calculate an average performance gain when training on an
increasing number of KGs. In addition, we compare the inductive performance of
our ISDEA+ against the best-performing transductive model, which is trained
and tested on the KG of the same domain. This approach helps us analyze
whether ISDEA+, via meta-learning on a more diverse set of training graphs,
can match or even surpass the transductive model in performance.

To select the best transductive performance, we train two models: ISDEA+ and
SOTA relational GNN model NBFNet (Zhu et al., 2021) (with its original
implementation) and test on graphs within the same domain, and then select the
best performance from these two models as the transductive SOTA performance.
We experimented with a total of 5 setups, and for each setup, we trained
models with 3 different random seeds for each training combination.

Table 6 shows training and test domains sampled for each setup, and Sections
F.1.3 and F.1.3 shows the Hits@10 and Hits@5 results on each test domain
respectively. The boxplots shown in Figure 2 are the aggregated results of
Sections F.1.3 and F.1.3. Similar to Figure 2, we can observe that the
performance of ISDEA+ consistently increases when training on more and more
domains, and finally reaching or even surpassing the performance of the best-
performing transductive model on certain test domains.

Table 6:  The 5 randomly sampled setups of training and test combinations of
WikiTopic domain KGs (Table 5) that are used in our zero-shot meta-learning
experiment. The $+$ between different domains denotes that the KGs
corresponding to these domains are merged for model training.

Setup | 1 Training Domain | 2 Training Domains | 3 Training Domains | 4 Training Domains | Test Domains
---|---|---|---|---|---
1 | Infra | Infra + Sci | Infra + Sci + Sport | Infra + Sci + Sport + Tax | Art, Award, Edu, Health
2 | Award | Award + Edu | Award + Edu + Tax | Award + Edu + Tax + Sport | Art, Health, Infra, Sci
3 | Sport | Sport + Infra | Sport + Infra + Edu | Sport + Infra + Edu + Health | Art, Award, Sci, Tax
4 | Art | Art + Award | Art + Award + Health | Art + Award + Health + Infra | Edu, Sci, Sport, Tax
5 | Health | Health + Sport | Health + Sport + Tax | Health + Sport + Tax + Art | Award, Edu, Infra, Sci

Table 7:  Average Relation & Node Hits@10 performance of ISDEA+ on the Zero-
Shot Meta-Learning task over WikiTopics on each test domain. We also report
the performance of the best transductive model. ISDEA+ consistently achieves
better and better performance when training on more and more domains, closing
and even sometimes surpassing the best transductive model performance.

(a) Relation prediction $(i,?,j)$ performance in %. Higher $\uparrow$ is
better.

Training Scenario | Test on Art | Test on Award | Test on Edu | Test on Health | Test on Infra | Test on Sci | Test on Sport | Test on Tax
---|---|---|---|---|---|---|---|---
Best Transductive | 95.37$\pm 00.54$ | 99.95$\pm 00.02$ | 98.33$\pm 00.11$ | 99.61$\pm 00.10$ | 99.83$\pm 00.03$ | 99.64$\pm 00.16$ | 94.40$\pm 07.55$ | 87.11$\pm 16.02$
1 training domain | 92.31$\pm 02.15$ | 99.83$\pm 00.18$ | 97.99$\pm 00.38$ | 92.28$\pm 08.67$ | 96.41$\pm 06.41$ | 98.50 $\pm 01.23$ | 98.82$\pm 00.36$ | 94.15$\pm 08.49$
2 training domains | 93.61$\pm 02.00$ | 99.81$\pm 00.07$ | 97.66$\pm 00.55$ | 98.64$\pm 01.54$ | 99.25$\pm 00.30$ | 98.78$\pm 01.20$ | 98.43$\pm 00.52$ | 96.15$\pm 09.00$
3 training domains | 95.00$\pm 01.75$ | 99.82$\pm 00.10$ | 98.25$\pm 00.22$ | 99.31$\pm 00.19$ | 99.73$\pm 00.22$ | 99.35$\pm 00.51$ | 98.57$\pm 00.35$ | 99.50$\pm 00.60$
4 training domains | 96.14$\pm 00.80$ | 99.84$\pm 00.09$ | 98.17$\pm 00.16$ | 99.25$\pm 00.17$ | 99.83$\pm 00.09$ | 99.55$\pm 00.27$ | 99.38$\pm 00.12$ | 99.71$\pm 00.38$

(b) Node prediction $(i,k,?)$ performance in %. Higher $\uparrow$ is better.

Training Scenario | Test on Art | Test on Award | Test on Edu | Test on Health | Test on Infra | Test on Sci | Test on Sport | Test on Tax
---|---|---|---|---|---|---|---|---
Best Transductive | 91.70$\pm 00.54$ | 93.57$\pm 01.32$ | 96.85$\pm 00.18$ | 98.92$\pm 00.07$ | 97.75$\pm 00.17$ | 96.73$\pm 00.65$ | 81.21$\pm 00.10$ | 90.87$\pm 05.16$
1 training domain | 88.55$\pm 04.53$ | 85.16$\pm 05.44$ | 94.75$\pm 01.23$ | 89.44$\pm 09.11$ | 81.81$\pm 08.62$ | 95.91$\pm 00.52$ | 66.93$\pm 14.16$ | 82.85$\pm 12.84$
2 training domains | 88.55$\pm 05.52$ | 88.14$\pm 01.69$ | 95.87$\pm 01.37$ | 96.84$\pm 01.58$ | 89.90$\pm 07.05$ | 95.88$\pm 01.05$ | 66.98$\pm 13.73$ | 86.92$\pm 11.03$
3 training domains | 92.26$\pm 00.71$ | 87.93$\pm 01.23$ | 96.85$\pm 00.53$ | 97.27$\pm 01.22$ | 87.63$\pm 06.73$ | 96.33$\pm 00.54$ | 77.19$\pm 05.87$ | 93.67$\pm 01.25$
4 training domains | 90.74$\pm 02.54$ | 89.47$\pm 00.82$ | 97.00$\pm 00.36$ | 97.82$\pm 00.48$ | 94.01$\pm 01.82$ | 96.19$\pm 00.28$ | 80.69$\pm 00.29$ | 92.89$\pm 01.19$

Table 8:  Average Relation & Node Hits@5 performance of ISDEA+ on the Zero-
Shot Meta-Learning task over WikiTopics on each test domain. We also report
the performance of the best transductive model. ISDEA+ consistently achieves
better and better performance when training on more and more domains, closing
and even sometimes surpassing the best transductive model performance.

(a) Relation prediction $(i,?,j)$ performance in %. Higher $\uparrow$ is
better.

Training Scenario | Test on Art | Test on Award | Test on Edu | Test on Health | Test on Infra | Test on Sci | Test on Sport | Test on Tax
---|---|---|---|---|---|---|---|---
Best Transductive | 83.80$\pm 01.92$ | 97.32$\pm 00.14$ | 94.31$\pm 00.27$ | 98.43$\pm 00.26$ | 98.32$\pm 00.43$ | 99.57$\pm 00.16$ | 90.60$\pm 05.84$ | 87.11$\pm 16.02$
1 training domain | 79.93$\pm 03.42$ | 96.08$\pm 01.68$ | 92.83$\pm 00.99$ | 88.99$\pm 08.63$ | 92.02$\pm 06.72$ | 98.45$\pm 01.29$ | 88.40$\pm 01.23$ | 94.14$\pm 08.48$
2 training domains | 82.78$\pm 03.27$ | 96.19$\pm 00.51$ | 93.33$\pm 01.07$ | 96.48$\pm 01.73$ | 95.93$\pm 00.88$ | 98.72$\pm 01.18$ | 89.79$\pm 05.11$ | 96.12$\pm 08.98$
3 training domains | 84.46$\pm 03.01$ | 96.08$\pm 00.39$ | 92.66$\pm 01.32$ | 96.92$\pm 00.22$ | 96.28$\pm 00.72$ | 99.30$\pm 00.49$ | 86.47$\pm 01.64$ | 99.48$\pm 00.59$
4 training domains | 85.44$\pm 02.71$ | 96.20$\pm 00.40$ | 92.74$\pm 01.20$ | 96.65$\pm 00.57$ | 97.33$\pm 00.71$ | 99.47$\pm 00.26$ | 92.25$\pm 02.16$ | 99.69$\pm 00.37$

(b) Node prediction $(i,k,?)$ performance in %. Higher $\uparrow$ is better.

Training Scenario | Test on Art | Test on Award | Test on Edu | Test on Health | Test on Infra | Test on Sci | Test on Sport | Test on Tax
---|---|---|---|---|---|---|---|---
Best Transductive | 85.01$\pm 00.89$ | 75.54$\pm 03.10$ | 86.10$\pm 00.27$ | 95.95$\pm 00.30$ | 96.24$\pm 00.11$ | 95.15$\pm 00.29$ | 67.30$\pm 00.08$ | 85.04$\pm 06.03$
1 training domain | 80.20$\pm 05.57$ | 60.59$\pm 09.59$ | 77.25$\pm 06.02$ | 81.27$\pm 09.32$ | 73.61$\pm 08.63$ | 94.30$\pm 00.71$ | 52.22$\pm 14.46$ | 77.75$\pm 12.63$
2 training domains | 80.55$\pm 05.80$ | 65.41$\pm 03.45$ | 83.19$\pm 02.46$ | 90.89$\pm 02.09$ | 84.92$\pm 08.23$ | 94.36$\pm 01.03$ | 52.88$\pm 14.05$ | 81.17$\pm 10.75$
3 training domains | 84.32$\pm 01.34$ | 65.56$\pm 02.17$ | 84.03$\pm 01.60$ | 92.20$\pm 01.14$ | 81.93$\pm 07.45$ | 94.97$\pm 00.53$ | 62.13$\pm 06.85$ | 87.91$\pm 00.88$
4 training domains | 83.29$\pm 02.56$ | 68.97$\pm 01.44$ | 83.93$\pm 01.11$ | 91.94$\pm 02.09$ | 88.38$\pm 04.51$ | 94.64$\pm 00.43$ | 66.12$\pm 00.17$ | 86.91$\pm 01.09$

####  F.1.4 Doubly Inductive Link Prediction over datasets from InGram (Lee et
al., 2023)

Lee et al. (2023) proposed the NL-$k$, WK-$k$, and FB-$k$ benchmarks
originally used to evaluate InGram’s performance of reasoning over new nodes
and new relation types at test time, where $k\in\\{25,50,75,100\\}$ means
that, in the test graphs, approximately $k\%$ of triplets have unseen
relations. For example, the test graph of WK-100 does not contain any training
relations and thus induces a doubly inductive link prediction task. Hence, we
run our models (ISDEA and DEq-InGram) against InGram on these benchmarks with
results shown in Section F.1.4. We note that, however, due to the different
experimental settings (as we discuss next), our results reported in Section
F.1.4 are not directly comparable to those reported in Lee et al. (2023), even
though they are experimented on essentially the same datasets.

##### Difference to the original data split and evaluation in InGram (Lee et
al., 2023):

Different from Lee et al. (2023), which uses part of the test graph as the
validation set to conduct model hyperparameter search, our experiments
consider a harder setting where the relations in test are not observed in the
validation data. Hence, to modify the NL-$k$, WK-$k$, and FB-$k$ datasets to
our setting, we discard the original validation set and instead split the
original training set into a new set of training and validation triplets with
a ratio of 9:1. During training, the models perform self-supervised masking
over the training set of triplets to create the training-time observable
triplets and training-time target triplets. During validation, the entire set
of the new training triplets is taken as the validation-time observable
triplets, and the new validation triplets are the target triplets to predict.
In addition, Lee et al. (2023) evaluate their model’s node prediction
performance against all nodes in the graph. For efficiency reasons, we
evaluate the model performance by sampling without replacement 50 negative
nodes for the node prediction task and sampling with replacement 50 negative
relation types for the relation prediction task.

Section F.1.4 shows the results, where we can see that ISDEA outperforms
InGram on most datasets on the relation prediction task and has smaller
standard deviation in general, and DEq-InGram consistently outperforms InGram
on all datasets for both relation prediction and node prediction tasks.
Importantly, in the dataset FB-100 which follows our doubly inductive link
prediction setting with completely new nodes and new relation types in the
test with the largest number of training and test relations ($134$ in train
and $77$ in test) (Lee et al., 2023), ISDEA achieves significant better
results in the relation perdiction task, showcasing its ability for doubly
inductive link prediction.

Table 9:  Relation & Node Hits@10 performance on Doubly Inductive Link
Prediction over NL-$k$, WK-$k$, and FB-$k$ of Lee et al. (2023). We report
standard deviations over 5 runs. A higher value means better doubly inductive
link prediction performance. The best values are shown in bold font, while the
second-best values are underlined. ISDEA outperforms InGram on most datasets
on the relation prediction task, and DEq-InGram consistently outperforms
InGram on all datasets for both relation prediction and node prediction tasks.

(a) Performance in % on WK-$k$ datasets. Higher $\uparrow$ is better.

| Relation prediction $(i,?,j)$ |  | Node prediction $(i,k,?)$
---|---|---|---
Models | WK-25 | WK-50 | WK-75 | WK-100 |  | WK-25 | WK-50 | WK-75 | WK-100
InGram | 58.76$\pm 13.91$ | 84.01$\pm 03.30$ | 80.19$\pm 04.19$ | 58.20$\pm 11.13$ |  | 76.99$\pm 07.72$ | 70.93$\pm 02.38$ | 78.85$\pm 04.65$ | 66.29$\pm 03.70$
DEq-InGram (Ours) |  81.06$\pm 22.31$ | 94.85$\pm 00.85$ | 95.84$\pm 01.54$ |  81.83$\pm 10.10$ |  |  87.91$\pm 05.68$ |  82.58$\pm 01.70$ |  89.10$\pm 02.15$ |  79.69$\pm 03.07$
ISDEA+ (Ours) | 96.25$\pm 00.86$ |  93.10$\pm 02.55$ |  95.66$\pm 00.82$ | 95.00$\pm 00.15$ |  | 94.41$\pm 01.61$ | 90.34$\pm 01.71$ | 91.98$\pm 01.61$ | 91.22$\pm 00.45$

(b) Performance in % on FB-$k$ datasets. Higher $\uparrow$ is better.

| Relation prediction $(i,?,j)$ |  | Node prediction $(i,k,?)$
---|---|---|---
Models | FB-25 | FB-50 | FB-75 | FB-100 |  | FB-25 | FB-50 | FB-75 | FB-100
InGram | 68.26$\pm 08.27$ | 50.41$\pm 08.79$ | 79.51$\pm 02.69$ | 40.46$\pm 12.21$ |  |  86.79$\pm 00.70$ | 73.32$\pm 06.64$ | 86.57$\pm 00.69$ | 71.72$\pm 06.93$
DEq-InGram (Ours) |  82.89$\pm 03.58$ |  76.65$\pm 04.05$ |  89.70$\pm 01.14$ |  46.88$\pm 15.76$ |  | 92.39$\pm 00.30$ |  81.08$\pm 06.98$ | 92.14$\pm 00.43$ |  77.54$\pm 06.36$
ISDEA+ (Ours) | 96.68$\pm 00.15$ | 93.55$\pm 00.77$ | 96.86$\pm 00.58$ | 97.55$\pm 00.33$ |  | 85.01$\pm 00.92$ | 84.40$\pm 00.38$ |  86.62$\pm 00.31$ | 91.28$\pm 00.19$

(c) Performance in % on NL-$k$ datasets. Higher $\uparrow$ is better.

| Relation prediction $(i,?,j)$ |  | Node prediction $(i,k,?)$
---|---|---|---
Models | NL-25 | NL-50 | NL-75 | NL-100 |  | NL-25 | NL-50 | NL-75 | NL-100
InGram | 64.54$\pm 16.86$ | 64.54$\pm 12.56$ | 80.16$\pm 04.43$ | 70.84$\pm 08.52$ |  |  89.95$\pm 02.01$ |  92.74$\pm 00.52$ |  95.40$\pm 01.38$ | 88.20$\pm 01.92$
DEq-InGram (Ours) |  83.58$\pm 17.57$ |  91.32$\pm 05.60$ |  96.01$\pm 01.23$ |  87.52$\pm 10.39$ |  | 95.03$\pm 00.32$ | 96.02$\pm 00.34$ | 97.94$\pm 00.34$ | 93.80$\pm 01.38$
ISDEA+ (Ours) | 92.04$\pm 02.67$ | 93.78$\pm 01.37$ | 96.57$\pm 01.85$ | 99.72$\pm 00.15$ |  | 82.20$\pm 04.36$ | 83.35$\pm 00.40$ | 90.94$\pm 00.85$ |  90.06$\pm 00.49$

####  F.1.5 A Synthetic Case Study for ISDEA

Figure 9:  Synthetic Example of FD-2: Training and test has their own node and
relation type sets:
${\mathcal{V}}^{(\text{tr})}\cap{\mathcal{V}}^{(\text{te})}=\emptyset$ and
${\mathcal{R}}^{(\text{tr})}\cap{\mathcal{R}}^{(\text{te})}=\emptyset$.

To further understand the expressive power and limitations of our proposed
sturctural double equivariant model ISDEA, we create FD-2 to empirically
justify the expressivity of our proposal on tasks over both new nodes and new
relation types. On FD-2, training has 127 nodes and 2 relations, while test
has 254 nodes and 4 relations (more nodes and more relations).

FD-2 is constructed by only a single rule,
$\left(E_{1},R_{1},E_{3}\right)\land\left(E_{3},R_{2},E_{2}\right)\Rightarrow\left(E_{1},R_{1},E_{3}\right)$
where $E_{1},E_{2},E_{3}$ and $R_{1},R_{2}$ are all variables. As illustrated
in Figure 9, The training data has only two relation types
$\\{r_{1},r_{2}\\}$, while test data has four relation types
$\\{r_{3},r_{4},r_{5},r_{6}\\}$ which are all different from training
relations. For all relation types, only $r_{1},r_{3},r_{4}$ can be used for
$R_{1}$ assignments, and only $r_{2},r_{5},r_{6}$ can be use for $R_{2}$
assignments. Besides, training and test also have distinct node sets.

Each graph (training or test) is consisted by one or more tree-like structures
as left side of Figure 9. In each tree-like structure, all solid edges are
used as observations, and will form a complete binary tree; while all dashed
edges are used as training, validation or test samples which are built by
applying the only rule over all observed edges. In training, we have only one
tree-like structure; while in test, we have two disconnected tree-like
structures. A more detailed generation algorithm for a graph given depths of
all tree-like structures is provided in Algorithm 2.

Since the structure of FD-2 does not satisfy the requirement of the spanning
tree algorithm used in InGram (Lee et al., 2023), we are not able to apply
InGram and DEq-InGram on FD-2. So we provide the results on FD-2 in Section
F.1.5 with all remaining baselines and ISDEA. We can see that ISDEA clearly
perform better than other baselines, especially in the relation prediction
task, and shows capability to perform accurately on the doubly inductive link
prediction over both new nodes and new relation types, while methods like
NBFNet and RMPI are not able to correctly perdict this task, even for node
prediction.

Table 10:  Relation & Node performance on Doubly Inductive Link Prediction
over FD2. We report standard deviations over 5 runs. A higher value means
better doubly inductive link prediction performance. The best values are shown
in bold font, while the second-best values are underlined. ISDEA consistently
achieve better results than the baselines, especially in the Relation
perdiction task. NA* due to the fact that FD2 does not satisfy the spanning
tree algorithm used in InGram (Lee et al., 2023).

| Relation prediction $(i,?,j)$ |  | Node prediction $(i,k,?)$
---|---|---|---
Models | MRR | Hits@1 | Hits@2 | Hits@4 |  | MRR | Hits@1 | Hits@2 | Hits@4
GAT | 7.61$\pm 00.71$ | 0.77$\pm 00.39$ | 2.78$\pm 00.80$ | 5.85$\pm 00.95$ |  | 84.62$\pm 02.64$ | 71.61$\pm 04.94$ |  93.51$\pm 01.03$ | 99.72$\pm 00.27$
GIN | 8.44$\pm 00.40$ | 1.29$\pm 00.37$ | 3.51$\pm 00.58$ |  7.18$\pm 01.01$ |  | 73.99$\pm 09.60$ | 65.73$\pm 06.58$ | 76.69$\pm 12.44$ | 81.45$\pm 15.80$
GraphConv | 7.88$\pm 00.45$ | 0.81$\pm 00.29$ | 2.62$\pm 00.61$ | 6.98$\pm 01.09$ |  |  85.95$\pm 00.77$ |  74.52$\pm 01.81$ | 92.66$\pm 01.02$ | 99.84$\pm 00.15$
RMPI |  9.09$\pm 03.18$ |  1.94$\pm 01.88$ |  3.95$\pm 04.43$ | 7.10$\pm 05.58$ |  | 21.16$\pm 05.85$ | 9.84$\pm 05.04$ | 16.74$\pm 06.50$ | 27.98$\pm 09.96$
NBFNet | 6.39$\pm 02.19$ | 1.50$\pm 02.49$ | 1.79$\pm 02.39$ | 2.91$\pm 02.22$ |  | 21.95$\pm 04.14$ | 14.44$\pm 04.34$ | 18.61$\pm 04.29$ | 26.47$\pm 04.24$
InGram | N/A* | N/A* | N/A* | N/A* |  | N/A* | N/A* | N/A* | N/A*
DEq-InGram (Ours) | N/A* | N/A* | N/A* | N/A* |  | N/A* | N/A* | N/A* | N/A*
ISDEA (Ours) | 44.39$\pm 12.17$ | 32.82$\pm 12.69$ | 38.71$\pm 13.60$ | 50.73$\pm 14.04$ |  | 90.98$\pm 03.55$ | 83.59$\pm 06.22$ | 95.69$\pm 02.34$ |  99.72$\pm 00.27$

Algorithm 2 Synthesis Algorithm for FD-2. This is triplet generation code for
a single graph (either training and test). It will provide observation and
query triplets. For training, query triplets are further divided into training
and validation triplets; For test, query triplets directly become test
triplets.

1:Tree depth $\\{D_{1},\ldots,D_{M}\\}$, Node Labeling
“$\text{Names}^{\text{nd}}$”, Relation Type Labeling
“$\text{Names}^{\text{rl}}$”.

2:Observation triplets ${\mathcal{S}}$, Query triplets ${\mathcal{Q}}$

3:${\mathcal{S}}=\emptyset$

4:${\mathcal{Q}}=\emptyset$

5:$n\leftarrow 0$

6:for $m\leftarrow 1,\ldots,M$ do

7: for $d\leftarrow 1,\ldots,D_{m}$ do

8: for $v\leftarrow 2^{d}-1,\ldots,2^{d+1}-2$ do

9: $u_{1}\leftarrow\lceil\nicefrac{{(v-2)}}{{2}}\rceil$

10: $u_{2}\leftarrow\lceil\nicefrac{{(u_{1}-2)}}{{2}}\rceil$

11: if $v\text{ mod }2=0$ then $\triangleright$ For relation type variable
$R_{2}$.

12: if $u_{1}\geq 0$ then

13:
${\mathcal{S}}$.add$\big{(}\,(\text{Names}^{\text{nd}}[n+v],\text{Names}^{\text{rl}}[2m-1],\text{Names}^{\text{nd}}[n+u_{1}])\,\big{)}$

14: end if

15: if $u_{2}\geq 0$ then

16:
${\mathcal{Q}}$.add$\big{(}\,(\text{Names}^{\text{nd}}[n+v],\text{Names}^{\text{rl}}[2m-1],\text{Names}^{\text{nd}}[n+u_{2}])\,\big{)}$

17: end if

18: else$\triangleright$ For relation type variable $R_{1}$.

19: if $u_{1}\geq 0$ then

20:
${\mathcal{S}}$.add$\big{(}\,(\text{Names}^{\text{nd}}[n+v],\text{Names}^{\text{rl}}[2m-2],\text{Names}^{\text{nd}}[n+u_{1}])\,\big{)}$

21: end if

22: if $u_{2}\geq 0$ then

23:
${\mathcal{Q}}$.add$\big{(}\,(\text{Names}^{\text{nd}}[n+v],\text{Names}^{\text{rl}}[2m-2],\text{Names}^{\text{nd}}[n+u_{2}])\,\big{)}$

24: end if

25: end if

26: end for

27: $n\leftarrow n+2^{d}$

28: end for

29:end for

####  F.1.6 Expressivity Limitation Case Study with FD-2 for ISDEA

We now provide a FD-2 variant where we show that double equivariant
representation is not expressive enough to solve a specific task. It is a
simple 2-depth tree structure as shown in Figure 10. We denote node
representations given by arbitrary double equivariant representation as
$H_{v,r}$ where $v\in[1,7]$ and $r\in[1,4]$. We can easily notice that $e_{4}$
and $e_{7}$ are symmetric, $e_{5}$ and $e_{6}$ are symmetric (simply flipping
blue and orange colors), thus we will expect
$H_{4,1}=H_{7,2},H_{4,2}=H_{7,1},H_{5,1}=H_{6,2},H_{5,2}=H_{6,1}$.

Figure 10:  Expressivity Limitation: Relation $r_{1}$ and $r_{2}$ are always
observed, while $r_{3}$ and $r_{4}$ are always querying. $r_{3}$ implies that
relation types on the path are same, while $r_{4}$ implies that relation types
on the path are different..

Since there is no $r_{3}$ and $r_{4}$ in observation, they are freely
exchangeable with each other, thus we will also expect

$\begin{gathered}H_{1,3}=H_{1,4},\\\ H_{4,3}=H_{4,4}=H_{7,4}=H_{7,3},\\\
H_{5,3}=H_{5,4}=H_{6,4}=H_{6,3}.\\\ \end{gathered}$

After getting all those representations, we can now focus on querying triplet
representations (dashed green and red) by concatenating head and tail node
representations w.r.t. relation types:

$\begin{gathered}\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{4}\right),\mathbf{A}\right)=H_{1,4}\mathbin{\|}H_{4,4},\\\
\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{5}\right),\mathbf{A}\right)=H_{1,3}\mathbin{\|}H_{5,3},\\\
\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{6}\right),\mathbf{A}\right)=H_{1,3}\mathbin{\|}H_{6,3},\\\
\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{7}\right),\mathbf{A}\right)=H_{1,4}\mathbin{\|}H_{7,4}.\\\
\end{gathered}$

We can notice that

$\begin{gathered}\overbrace{H_{1,4}\mathbin{\|}H_{4,4}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{4}\right),\mathbf{A}\right)}=\overbrace{H_{1,4}\mathbin{\|}H_{7,4}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{7}\right),\mathbf{A}\right)}=\overbrace{H_{1,3}\mathbin{\|}H_{7,3}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{7}\right),\mathbf{A}\right)}=\overbrace{H_{1,3}\mathbin{\|}H_{4,3}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{4}\right),\mathbf{A}\right)},\\\
\overbrace{H_{1,4}\mathbin{\|}H_{5,4}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{5}\right),\mathbf{A}\right)}=\overbrace{H_{1,4}\mathbin{\|}H_{6,4}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{4},e_{6}\right),\mathbf{A}\right)}=\overbrace{H_{1,3}\mathbin{\|}H_{6,3}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{6}\right),\mathbf{A}\right)}=\overbrace{H_{1,3}\mathbin{\|}H_{5,3}}^{\Gamma_{\text{tri}}\left(\left(e_{1},r_{3},e_{5}\right),\mathbf{A}\right)}.\\\
\end{gathered}$

Suppose the score of $\left(e_{u},r_{c},e_{v}\right)$ utilizing such
representation is $s_{u,c,v}$, we will have

$\begin{gathered}s_{4,4,1}=s_{7,4,1}=s_{7,3,1}=s_{4,3,1},\\\
s_{5,4,1}=s_{6,4,1}=s_{6,3,1}=s_{5,3,1}.\\\ \end{gathered}$

If a model can distinguish $r_{3}$ and $r_{4}$, it should at least rank node
$e_{7}$ higher than $e_{6}$ given head node $e_{1}$ and relation $r_{3}$ since
this is a positive triplet in training. Then, we will have
$s_{7,3,1}>s_{6,3,1}$, since we already knew that
$s_{7,3,1}=s_{7,4,1},s_{6,3,1}=s_{6,4,1}$, we will also have
$s_{7,4,1}>s_{6,4,1}$. This means that we rank node $e_{7}$ higher than node
$e_{6}$ given head node $e_{1}$ and relation $r_{4}$, however, this is
incorrect since $\left(e_{7},r_{4},e_{1})\right)$ is negative while
$\left(e_{6},r_{4},e_{1}\right)$ is positive. In summary, if we use double
equivariant representation for triplet scoring in this specific example, there
is no way for it to correctly rank $r_{3}$ and $r_{4}$ in the same time. This
shows that double equivariant representation (even the most expressive) can
face challenges for doubly inductive link prediction on knowledge graph.

###  F.2 Complexity Analysis for ISDEA and ISDEA+

For each layer of our method ISDEA, it can be treated as running 2
unattributed GNN $|{\mathcal{R}}|$ times on the knowledge graph, thus time
cost is roughly $2|{\mathcal{R}}|$ times of adopted GNN. In our experiment, we
use node representation GNNs (e.g., GIN (Xu et al., 2019a), GAT (Veličković et
al., 2017), GraphConv (Morris et al., 2019)) as our GNN architecture, thus the
complexity is
$\mathcal{O}(|{\mathcal{R}}|L(|{\mathcal{S}}|d+|{\mathcal{V}}|d^{2}))$ where
$L$ is the number of layers, $d$ is the maximum size of hidden layers,
$|{\mathcal{V}}|$ is number of nodes and $|{\mathcal{R}}|$ is number of
relations in the knowledge graph, and $|{\mathcal{S}}|$ is number of fact
triplets (number of edges) in the knowledge graph.

However, for ISDEA+, since the update for each relation can be conducted
independently, by using parrallezing or a carefully designed training batch
process, we can reduce the time complexity to
$\mathcal{O}(L(|{\mathcal{S}}|d+|{\mathcal{V}}|d^{2}))$, $|{\mathcal{R}}|$
times faster than ISDEA.

Besides, for both positive and negative samples $(i,k,j)$, our method requires
the shortest distance between any two nodes without considering $(i,k,j)$,
which can be achieved from the Dijkstra or Floyd algorithm, where we will pre-
split the graph in ISDEA+ and simplify the computation of calculating
distances to only one time rather than repeating it in each batch as
implemented in ISDEA.

###  F.3 Ablation study for ISDEA

Since a part of negative samplings is drawn by uniformly corrupting objects
(without loss of generality), it is very likely that corrupted objects are far
way from the subject while the true object is close to the subject. Then, the
distance feature can help predict in such cases. However, the shortest
distance feature will not provide any additional information if we corrupt the
relation type. Under such a scenario, shortest distance itself may provide
some features to achieve good ranking performance in inductive link prediction
on knowledge graph, thus we want to know if shortest distance feature
augmentation contributes to the performance gain. We perform an ablation study
for ISDEA with or without distance on doubly inductive link prediction over
PediaTypes.

As shown in Section F.3, even if the shortest distance is excluded from our
model, our model still performs quite well and is better than most other
baselines in the doubly inductive link prediction on PediaTypes. Especially,
as we anticipate, the distance feature is more helpful in the node prediction
task than the relation prediction task. Thus, we can say that double
equivariant node representation itself is enough to provide good performance
on doubly inductive link prediction.

Table 11:  Relation & Node performance on Doubly Inductive Link Prediction
over PediaTypes for ISDEA with/without Shortest Distances. We report standard
deviations over 5 runs. A higher value means better doubly inductive link
prediction performance. Even without the shortest distance as an augmented
feature, our proposal still achieves comparable results, especially in the
relation prediction task.

(a) Relation prediction $(i,?,j)$ performance in %. Higher $\uparrow$ is
better.

Dataset | MRR | Hits@1 | Hits@5 | Hits@10
---|---|---|---|---
EN-FR | ISDEA w/ Distance | 70.06$\pm 02.01$ | 61.46$\pm 00.79$ | 82.11$\pm 04.01$ | 84.94$\pm 05.00$
ISDEA w/o Distance | 68.65$\pm 00.41$ | 60.34$\pm 00.53$ | 80.17$\pm 00.99$ | 82.80$\pm 01.73$
FR-EN | ISDEA w/ Distance | 69.01$\pm 00.57$ | 58.18$\pm 00.14$ | 83.19$\pm 01.73$ | 84.75$\pm 02.51$
ISDEA w/o Distance | 67.74$\pm 01.15$ | 56.35$\pm 01.53$ | 83.07$\pm 00.75$ | 86.23$\pm 00.56$
EN-DE | ISDEA w/ Distance | 78.38$\pm 04.04$ | 68.00$\pm 06.41$ | 92.39$\pm 00.83$ | 95.26$\pm 00.63$
ISDEA w/o Distance | 76.52$\pm 01.32$ | 67.66$\pm 02.37$ | 87.49$\pm 00.87$ | 88.47$\pm 00.64$
DE-EN | ISDEA w/ Distance | 88.82$\pm 00.28$ | 84.83$\pm 00.29$ | 93.59$\pm 00.53$ | 94.23$\pm 00.71$
ISDEA w/o Distance | 88.94$\pm 00.92$ | 84.76$\pm 00.49$ | 93.98$\pm 01.74$ | 94.73$\pm 01.98$
DB-WD | ISDEA w/ Distance | 65.89$\pm 04.71$ | 57.51$\pm 05.40$ | 75.95$\pm 03.89$ | 82.22$\pm 02.44$
ISDEA w/o Distance | 70.66$\pm 07.05$ | 63.36$\pm 05.30$ | 79.87$\pm 10.19$ | 82.96$\pm 11.89$
WD-DB | ISDEA w/ Distance | 72.57$\pm 00.73$ | 62.72$\pm 01.24$ | 86.10$\pm 01.26$ | 88.87$\pm 02.94$
ISDEA w/o Distance | 67.98$\pm 02.14$ | 60.83$\pm 01.55$ | 76.65$\pm 03.14$ | 77.90$\pm 03.09$
DB-YG | ISDEA w/ Distance | 75.88$\pm 01.58$ | 69.12$\pm 02.40$ | 85.80$\pm 01.23$ | 91.42$\pm 01.79$
ISDEA w/o Distance | 75.42$\pm 00.35$ | 69.17$\pm 01.13$ | 84.86$\pm 01.58$ | 88.78$\pm 02.36$
YG-DB | ISDEA w/ Distance | 74.04$\pm 00.47$ | 66.68$\pm 00.81$ | 83.36$\pm 01.55$ | 85.34$\pm 01.49$
ISDEA w/o Distance | 74.22$\pm 01.56$ | 66.97$\pm 01.63$ | 83.62$\pm 01.85$ | 85.73$\pm 02.66$

(b) Node prediction $(i,k,?)$ performance in %. Higher $\uparrow$ is better.

Dataset | MRR | Hits@1 | Hits@5 | Hits@10
---|---|---|---|---
EN-FR | ISDEA w/ Distance | 53.92$\pm 00.26$ | 43.03$\pm 00.25$ | 64.45$\pm 00.24$ | 76.28$\pm 00.50$
ISDEA w/o Distance | 45.12$\pm 00.41$ | 34.04$\pm 00.36$ | 56.61$\pm 00.48$ | 63.46$\pm 00.76$
FR-EN | ISDEA w/ Distance | 57.68$\pm 00.68$ | 47.38$\pm 00.28$ | 67.24$\pm 01.32$ | 77.51$\pm 01.46$
ISDEA w/o Distance | 42.52$\pm 00.91$ | 30.41$\pm 01.17$ | 54.94$\pm 00.22$ | 65.29$\pm 00.20$
EN-DE | ISDEA w/ Distance | 50.30$\pm 02.08$ | 35.41$\pm 02.25$ | 68.80$\pm 01.90$ | 82.24$\pm 00.94$
ISDEA w/o Distance | 45.16$\pm 00.76$ | 30.26$\pm 00.76$ | 62.59$\pm 00.57$ | 76.98$\pm 00.63$
DE-EN | ISDEA w/ Distance | 51.33$\pm 00.40$ | 37.12$\pm 00.31$ | 68.20$\pm 00.53$ | 81.80$\pm 00.68$
ISDEA w/o Distance | 43.67$\pm 00.32$ | 28.97$\pm 00.25$ | 60.36$\pm 00.54$ | 74.95$\pm 00.51$
DB-WD | ISDEA w/ Distance | 45.75$\pm 00.66$ | 35.59$\pm 00.73$ | 54.83$\pm 00.90$ | 66.69$\pm 01.01$
ISDEA w/o Distance | 40.26$\pm 03.77$ | 30.59$\pm 03.89$ | 48.15$\pm 03.68$ | 59.43$\pm 03.76$
WD-DB | ISDEA w/ Distance | 51.64$\pm 00.60$ | 40.56$\pm 01.72$ | 62.60$\pm 02.55$ | 75.19$\pm 03.12$
ISDEA w/o Distance | 45.94$\pm 00.14$ | 35.17$\pm 00.30$ | 56.89$\pm 00.33$ | 66.46$\pm 00.55$
DB-YG | ISDEA w/ Distance | 41.72$\pm 01.64$ | 27.70$\pm 01.95$ | 55.21$\pm 01.07$ | 72.87$\pm 01.03$
ISDEA w/o Distance | 32.71$\pm 00.60$ | 17.69$\pm 00.39$ | 47.82$\pm 00.60$ | 66.92$\pm 01.90$
YG-DB | ISDEA w/ Distance | 48.21$\pm 01.06$ | 35.29$\pm 01.67$ | 61.87$\pm 01.30$ | 76.41$\pm 01.52$
ISDEA w/o Distance | 37.52$\pm 00.79$ | 23.10$\pm 00.76$ | 53.34$\pm 00.88$ | 68.43$\pm 01.62$

###  F.4 Limitations and Impacts for ISDEA and ISDEA+

ISDEA and ISDEA+ excels both in synthetic and real-world benchmarks. However,
the simplification from pairwise to node embeddings limits its expressivity.
In Section F.1.5, we give a synthetic counterexample how this could be an
issue in some knowledge graphs. We also do not envision a direct negative
social impact of our work.

##  Appendix G Future Work

As addressed in the main paper, our implemented architecture has a few
limitations, which could be addressed in future work. First, ISDEA+ has high
pre-processing cost. This high time cost is introduced by using shortest
distances whose computation is of the same complexity as enclosed subgraph.
However, our ablation studies show that shortest distances is not a dominant
factor in our model for real-world tasks, thus it is possible that shortest
distances can be replaced by other heuristics that can be efficiently
extracted.

Second, our specific implementation ISDEA happens to have high training and
inference costs, since it relies on repeating GNNs for each relation. Thus,
complexity ISDEA of scales linearly w.r.t. number of relations, which is often
a large number in real-world knowledge base, e.g., Wikipedia. However, fully
equivariance over all relations can be too strong, and we may only want
partial equivariance which may reduce the cost. We resolve this issue by
introduing ISDEA+.

Third, ISDEA+ has expressivity limitation. This limitation is related to
former two cost issues since it is caused by compromising most-expressive
pairwise representation to node-wise representation due to time cost. Thus if
we can reduce the cost, we may be able to use more expressive graph encoder.

Finally, although we show ISDEA+ representations can capture UQER Horn
clauses, there is no algorithm to create UQER Horn clauses from ISDEA+
representations. This topic is known as explainability which is important in
graph machine learning community. We leave such an algorithm as another future
work other than optimization.