Few-shot Relational Reasoning via Connection Subgraph Pretraining
Authors: Qian Huang
Hongyu Ren
Jure Leskovec
Venue: NeurIPS 2022 Accept (2022)
Keywords: Few-shot learning
knowledge graphs
graph neural networks
self-supervised pretraining

Abstract: Few-shot knowledge graph (KG) completion task aims to perform inductive reasoning over the KG: given only a few support triplets of a new relation $\bowtie$ (e.g., (chop,$\bowtie$,kitchen), (read,$\bowtie$,library), the goal is to predict the query triplets of the same unseen relation $\bowtie$, e.g., (sleep,$\bowtie$,?). Current approaches cast the problem in a meta-learning framework, where the model needs to be first jointly trained over many  training few-shot tasks, each being defined by its own relation, so that learning/prediction on the  target few-shot task can be effective. However, in real-world KGs, curating many training tasks is a challenging  ad hoc process. Here we propose Connection Subgraph Reasoner (CSR), which can make predictions for the target few-shot task directly without the need for pre-training on the human curated set of training tasks. The key to CSR is that we explicitly model a shared connection subgraph between support and query triplets, as inspired by the principle of eliminative induction. To adapt to specific KG, we design a corresponding self-supervised pretraining scheme with the objective of reconstructing automatically sampled connection subgraphs. Our pretrained model can then be directly applied to target few-shot tasks on without the need for training few-shot tasks. Extensive experiments on real KGs, including NELL, FB15K-237, and ConceptNet, demonstrate the effectiveness of our framework: we show that even a learning-free implementation of CSR can already perform competitively to existing methods on target few-shot tasks; with pretraining, CSR can achieve significant gains of up to 52% on the more challenging inductive few-shot tasks where the entities are also unseen during (pre)training.

Few-shot Relational Reasoning via Connection
Subgraph Pretraining
Qian Huang" Stanford University ghwang@es. stanford.. edu
Hongyu Ren"
Jure Leskovec Stanford University juredcs stanford. edu
Stanford University hyrenccs. stanford. sarren@cssstanfrd.. edu
Abstract
Few-shot knowledge graph (KG) completion task aims to perform inductive rea- soning over the KG: given only few support triplets of new relation (e.g., (chop, p4, kitchen), (read, >x, library)), the goal is to predict the query triplets of the same unseen relation ix1, e.g., (sleep, 1x, ?). Current approaches cast the problem in a meta-learning framework, where the model needs to be first jointly trained over many training few-shot tasks, each being defined by its own relation, so that learning/prediction on the target few-shot task can be effective. However, in real-world KGs, curating many training tasks is challenging ad hoc process. Here we propose Connection Subgraph Reasoner (CSR), which can make predic- tions for the target few-shot task directly without the need for pre-training on the human curated set of training tasks. The key to CSR is that we explicitly model a shared connection subgraph between support and query triplets, as inspired by the principle of eliminative induction. To adapt to specific KG, design a corre- sponding supervieee pretraining scheme with the objective of reconstructing automatically sampled connection subgraphs. Our pretrained model can then be directly applied to target few-shot tasks on without the need for training few-shot tasks. Extensive experiments real KGs, including NELL,, FB15K-237, and ConceptNet, demonstrate the effectiveness of our framework: we show that even a learning- free implementation of CSR can already perform competitively to existing methods on target few-shot tasks; with pretraining, CSR can achieve significant gains of up to 52% on the more challenging inductive few-shot tasks where the entities are also unseen during (pre)training.
Introduction
Knowledge Graphs (KGs) are structured representations of human knowledge, where each edge represents a fact in the triplet form of (head entity, relation, tail entity) [TC. 20) Since KGs are typically highly incomplete yet widely used in downstream applications, predicting missing edges, i.e., KG completion,
of the most important machine learning tasks over these large heterogencous data structures. Deep learning based methods have achieved great success on this task 19 26 but the more challenging few-shot setting [ is much less explored: Given background knowledge graph, an unseen relation, and a few support edges in triplet form, the task is to predict whether this unseen relation exists between query entity and candidate answers based on the background knowledge graph. Such a setting captures the most difficult and important case during KG completion: predict rare relations (i.e. appearing only a few times in the existing KG) and incorporating new relations into the KG efficiently. It also tests the inductive reasoning skill of the model on deriving new knowledge data-efficiently, which is critical for Al in general.
indicates equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(A) Few-shot Task
(B) Background KG
(C) Connection Subgraph Reasoner
Support s
S
S,
Hypothesis Proposal
Enc
DD
+
S2
Shared hypotheses
Score cosine
ismilarity
Query set Qp
Evidence
Enc
Qg
P
Proposal
Evidence
Figure I: The few-shot KG completion problem includes (A) few-shot task that aims to learn new relation (purple) and (B) background knowledge graph. Our CSR framework (C) first contexualizes all triplets in the background KG, then finds the shared hypothesis in the form of connection subgraph using the Hypothesis Proposal module, and finally tests whether there is an evidence close enough to the hypothesis using Evidence Proposal module. In general all edges shown have different relation types, but here we only highlight ones in the connection subgraph with colors.
typically adopt the meta-learning framework [8]. where the model is trained over meta-training set consisting of many few-shot tasks created from different relations in the background knowledge graph. GMatching (23,, FSRL [24] and Att-LMetric [13] metric-based meta-learning methods that try learn good metric where positive query pairs are closer to representation of edges in the support set than the negative ones.
Existing approaches to few-shot KG completion B 18 23 4
MetaR K is an optimization-base meta-learning method that use a meta-learner improve the optimization of the task learner, such that the task learner can quickly learn with only few examples.
However, creating the meta-training set for some unknown few-shot tasks in test time is a very difficult ad hoc process in practice. On existing benchmarks 23]. the training few-shot tasks and the target few-shot tasks are both randomly sampled from relations with least occurrences in the full knowledge graph, meaning the training and target relations are from the same distribution. But in reality, one has no information about the target few-shot tasks and the meta-training needs to be manually constructed out of the background knowledge graph. This is challenging since background knowledge graph often has limited number of tasks due to the limited number of relations; creating too many meta-training tasks out of the background KG may remove a large number of edges from the KG, making it sparse and hard learn over. Moreover, with a small meta-training set, the target few-shot tasks are very likely out of the curated meta-training set distribution, since the novel relation could be more complicated than known ones and the entities involved the target few-shot tasks can also be unseen. This then makes meta-learning based method suffer negative transfer due to distribution shift. Thus, having a method that can perform well on any novel few-shot tasks without relying on specifically designed meta- meta-trainin training set is crucial for real-world applications.
Here we propose novel modeling framework Connection Subgraph Reasoner (CSR) that make prediction on the target fhw-shot task directly without the need for meta-learnig and creation of a curated set of training few-shot tasks. Our insight that triplet of the unseen relation of interest can be inferred through the existence of hypothevis in the form of a connection subgruph, i.e. a subgraph in KG that connect the two entities of the triplet. Intuitively, the connection subgraph represents the logical pattern that implies the existence of the triplet. For the (chop, b4, kitchen) example, such a connection subgraph that implies ><t is a two hop path in KG: [(chop, can be done with, knife), (knife, is located at, ki kitchen)). This insight allows us to cast the few-shot link prediction as an inductive reasoning problem. Following the eliminative induction method of inductive reasoning [9) our framework first recovers this hypothesis from the support triplets by finding the connection subgraph approximately shared among the support triplets, then tests whether this hypothesis is also connection subgraph between the query entity and candidate answer. We show the full pipeline along with an example connection subgraph in Figure [ To better adapt to specific KG, we design novel encoder-decoder architecture based on graph neural networks (GNN) to implement the two stages and a corresponding supervisdd pretraining scheme to reconstruct diverse connection subgraphs.

---

We demonstrate that a training- free implementation of CSR via edge mask optimization can already discover the connection subgraph and reach link prediction performance competitive to many meta- learning methods over real- world knowledge graphs. With pretraining and optionally meta-learning over background KG uniformly, our method achieves high performance on both transductive and inductive few-shot test tasks that involve long tails relations, which are out of distribution to the training tasks; while existing methods using meta-learning suffers from distribution shift and cannot handle inductive tasks. Over real KGs including NELL [3. FB 15K-233 [00 and ConceptNet [7], our method consistently exceeds or matches state-of-the-an methods in meta-training tasks free setting, and far exceeds the best existing methods by up to 52 % in the the more challenging inductive few-shot tasks where entities in the target few-shot tasks are also unseen. The implementation of CSR can be found in https://giiae //github........ comm snap- stanf ord/csr
2 Related Work
2.1 Few-shot Relational Learning via Meta-Learning
Meta-learnig is paradigm of learning across set of meta-training tasks and then adapting to new task during meta-testing [8). To the best of our knowledge, all existing methods on few-shot KG completion follow the meta-learning paradigm address the data scarcity in the target few-shot
task [
24 Therefore, these methods require the access to a meta-training set that contains many few-shot KG completion tasks for training. On the two existing benchmarks NELL-One and [
18
23
Wiki-One the meta-training set is constructed by sampling from long tail relations, in the same way as the target few-shot tasks are constructed. However, such meta-training set is not given in real world application and needs to be manually constructed out of the background knowledge graph mimic the actual few-shot task during test time. This curation is inherently challenging because that the background knowledge graph has limited number of relations/tasks in G. the distribution of the novel relations of interest is unknown, and the entites in the target few-shot tasks can be unseen in the background KG. In this paper, we develop a more general pretraining procedure to remove the dependency on manually created training tasks.
2.2 Few-shot Learning via Pretraining
It has been shown in natural language processing 2 16 and computer vision 4 domains that large-scale self-supervised pretraining can significantly improve task-agnostic few-shot learning ability. One of the most successful pretraining objectives is predicting the next token image patch given ones seen before it. However, how to design such powerful pretraining objectives for few-shot relational learning is still under-explored. In this work, design well motivated self-supervised pretraining objective, i.e. recovering diverse connection subgraphs that correspond to different inductive hypothesis. We show that such pretraining scheme can significantly improve few-shot relational learning tasks on knowledge graphs.
3 Few-shot KG Completion
Denote the background KG that represents the known knowledge as G = (E, TT) where and R represents the set of entities and relations. T t)),t tt E E,r E R} represents the facts as triplets. Given new relation r' & R and a support set S,, = {(h,, r', (x)) h2 E E we want to make predictions over a query set Qr = ( ?))h, E E) This prediction on (hy.r', ?) is typically converted to scoring triplet (hy.r' for all candidate entities e then ranking the scores. So we will proceed to consider Qr as directly containing full triplets (hy, r', e) to score. We call this a K-shot KG completion task, typically the number of support is a small number (K < 5).
Few- KG completion is defined as follows 3 23
Note that existing works generally assume the entities in the few-shot tasks (support + query set) belong to the background KG. However, real world cases, the goal of few-shot KG completion is to simulate learning of novel relations that may involve new entities not exist yet on the KG. Thus, in this paper we also consider a more challenging inductive setting where entities in the few-shot tasks do not belong to the entity set E, but new triplets about these unseen entities can be added at test time.
3

---

4
Connection Subgraph Reasoner
In this section, we first discuss our main motivation from the inductive reasoning perspective and present the general framework based on it. Then we introduce both learning-free and learning-based implementations of this framework.
4.1 Inductive Reasoning
Inductive Reasoning refers to the reasoning process of synthesizing a general principle from past observations, and then using this general principle to make predictions about future events [. Few-shot link prediction task can be seen as an inductive reasoning task with background knowledge.
The key motivation of our work is eliminative induction, one of the principled methods used to reach inductive conclusions. Specifically, we consider the scientific hypothesis method: eliminating hypotheses inconsistent with observations. In the context of few-shot link prediction task, explicitly try to find a hypothesis consistent with all examples in the support set, then test whether the the query is consistent with this hypothesis.
To illustrate a simple case of this, we use the de example where the support triplets are (chop, pa, kitchen), (read, pa, library), and query triplet is (sleep, De, ?). From background KG (e.g. Co..concpp,,,) we can know a lot of knowledge in forms of triplets about these entities, such as (kitchen, is part of, house) and (read, is done by, human) etc. We essentially want to find an induction hypothesis that explains how chop is related to kitchen in the same way that read is related to library. In other words, want to find the shared connection pattern over the background KG that connects both two pairs of entities. In this case, we can observe that there is a simple shared 2 hop connection path that connects both pairs:
{(chop, can be done with, knife), (knife, is located at, kitchen)) {(read, can be done with, book), (book, is located at, library)
(1)
(2)
The abstracted inductive hypothesis consistent with both examples in the support set is then
32, (he, can be done with Z) A (Z, is located at, tz) = (he,Ds,te)
(3)
This hypothesis can then be used to deduce that (sleep, D4, bedroom) has a high score, since we know ((sleep, can be done with, bed), (bed, is located at, bedroom)) from the background KG.
More generally, the shared connection pattern can be graph structured instead of a two-hop path, which then form connection subgraph between the two end entities instead of a connection path (Figure D]. Here we define the connection subgraph: Let G' = (E', R', T') be any subgraph of the background KG G. (i.e., E' C E, R' C R and T' T) that satisfies the following requirement for a given pair of nodes (he, Le) on the KG. (1) hr E E" and L. E E'; (2) there is no disconnected component. We define the connection subgraph Go of (he, te) to be any such G' where we further ignore the node identity. The key insight is that we should only consider the relation structure patterns and abstract away the node identity in order to construct hypothesis.
Then a hypothesis like Eq. B can be represented as connection subgraph Ge by interpreting each clause as an edge. And such a hypothesis is consistent with a support/query triplet (h, if Go is a connection subgraph of h, t. In terms of the ix example, the triplet (sleep, Da, bedroom) is consistent with the hypothesis Eq. 3 because the connection subgraph form of the hypothesis (he: can be done with Z) A (Z, located at, is a connection subgraph be- tween sleep and bedroom, with he, 7, L. corresponding to sleep, bed and bedroom respectively. Given a pair of node, we further call the KG subgraph with node identity an evidence that wit- nesses why the hypothesis is consistent with connection subgraph of h, t; Note the key difference between hypothesis and evidence is that, different pair nodes may share the same hypothe- sis but each may have different evidence to support the consistency with such hypothesis. As an example, for both (sleep, X4, bedroom) and (chop, D4, kitchen), the hypothesis is the same (he, can be done with Z)A is located at,t.). Yet the evidences are respectively ((leepp can be done with bed), (bed, is located at. bedroom)) and [(chop, can be done with, knife), (knife, is located at, kitchen))
Note that this hypothesis formulation can be seen as a generalization of the typical path structured logic rules considered by the multi-hop reasoning [|] 12] 22 and rule induction 6 [5] literature.

---

However, even with our graph structured hypothesis so far, such a strict way of testing the consisteney with a hypothesis by checking of whether Gc is connection subgraph of h, t exactly would be time-consuming and brittle due to the fuzziness of target relations and the KG incompleteness. Below we develop our framework that relaxes the hypothesis representation and consistency testing criteria.
4.2 General Framework
Based on the above motivation, we design the following general framework Connection Subgraph Reasoner (CSR) that includes 2 main modules: hypothesis proposal module Mp and evidence proposal module Me. CSR then has the following 3 components:
(1) Triplet Contextualization. We first contextualize each triplet (h, r'; .t) in support set S,, and query set Qr by retrieving its contextualized graph G(h, 1) C 9 such that it contains h, / and captures most of the immediately relevant information about the pair. There are several prior works on retrieving smaller subgraph around a triplet in KG for link prediction IT9 25]. We choose to use the enclosing subgraph proposed by Grail (99, which is the subgraph induced by all nodes that in the & hops neigborhood of both h, t. We generally use k = 1, depends on the density of KG. We also supplement with random sampling of the neighbors of t in case the enclosing subgraph itself is too small. We call the contextualized graphs of support triplets support graphs, and the contextualized graphs of query triplets query graphs.
(2) Hypothesis Proposal. After contextualization, we would like find the hypothesis consistent with all support graphs. We use hypothesis proposal module Mp to generate hypothesis from each support graph such that they are most similar to each other. Each hypothesis can represented as soft edge mask m [0, l over edges in the corresponding support graph. To aggregates these hypotheses to produce the embedding of one final hypothesis b, we take the mean of their GNN embedding produced by graph encoder Menc
1K = Mp((GG(h,,t) th),,, (t) E S,
1 K
(4)
b = Σ K
(ene t.), m.)
M, should compare all support graphs and output masks that represent the largest common connection subgraph, iee
arg max
mi),
s.t. Vi,j E 1...K, ((Mene(G((, 14), mz); Menc (G(h,, 1 (5)
(3) Hypothesis Testing. Finally, want to test whether each query graph is consistent with the proposed hypothesis. We uses evidence proposal module M, to take in b and query graph to output the closest evidence to the hypothesis represented by b. The score of the query is then the cosine similarity between b and the embedding of the evidence.
my = Me (b, G(hg: tq))
(6)
score s(b, Mene Men my))
Me is intended to output my such that
s s(Mene (g), ()))b) -
(7)
Overall, we model hypothesis softly the aggregation of approximately shared hypothesis connection subgraphs between support graphs as found by Mp. then test its probabilistic consistency with query graph by finding how close evidence for this hypothesis can be found in the query graph by Mc.
5

---

For the Mene. we use the alternative message passing in PathCon 21 so that that it does not use entity embedding as input can measures graph isomorphism
ag 1 EeEN(e) me cEN(e)
Σ
8e me
(8)
5 a [1]11(vv = ( h1]
(9)
6 = o ((((o, Su, sel) W + +b'), u ((e)
(10)
Mene (G, m) = maa__pool (a |
(11)
where is number of layers and se is random or pretrained relation embedding. Note that we concatenate the head and tail representation in the final graph representation so that the hypothesis and evidence subgraph are compared with heads and tails matched already.
For Mp and Mc. we introduce two specific implementations that satisfies the requirements Eq. and in the following sections.
4.3 CSR-OPT: Learning-free Implementation
We implement M, and Me as a learning free optimization processes, where the masks are optimized toward Eq. 5 andd directly.
For Mp, we formulate as constraint optimization problem:
Mp((G((h, (4), r', t.) E ), arg max Σ ((milit)) - A H (m²)
(12)
s.t. Σ (M [MMen(G(hb) (4), m.). Mena Mene(GG(yy (g) connectivity(m:) > 1
-
Here we add constraint the connectivity that measures whether the nodes in the subgraph represented by m, can be reachable from head or tail within 2 hops in the subgraph. Let be a soft adjacency matrix of the edge mask m, E [0. 1] El, We compute whether two nodes i, can reach each other within 2 hops Rag min((1 + A AR) 1), then
connectivity(m:)
Σ em (E
mie min (n,, Ru,,, Rn,c,
(13)
We also add the entropy regularization terms H-) to force the mask to represent a valid subgraph. Similarly, for Mc:
T(b, G(hg ty)) = arg max s(b, Menn ty), my))
H (mg)
(14)
We optimize each objective independently using gradient descent, but do not train them together end to end. The Menc remains random initialized, but we found that this "random" GNN is already powerful enough to distinguish non- non-isomorphic graphs as needed. Although this implementation is straight forward and learning free, it is slow and difficult to incorporate additional training. Nevertheless, serves as good way for directly verifying our hypothesis on the framework design.
4.4 CSR- Learning-basee Implementation and Pretraining Scheme
We also design fully GNN-based encoder-decoder approach to implement Mp and Mc. We use two models as building blocks: encoder fENC (G1, m1) G x R + Rd that encodes graph G1 weighted by my to embedding b. and decoder fDBc(G2, G x Fd - [| that decodes out the weight m2 such that graph G2 weighted by m2 corresponds to the input embedding b. Intuitively, fuEc(G2, fENe(Gr (G1, m)))) compares G1, G2 and finds the subgraph of G2 that is closest to the subgraph of G₁ induced by mi-
We then implement M, as an iterative process of comparing between all pairs of support graphs using this encoder-decoder, as shown in Algorithm We start with a full edge mask m; for each graph G, During each iteration, each graph G, obtains edge mask mys as result of comparing against G weighted by my- Gj then takes the shared parts between myk by taking an element wise minimum to obtain my.

---

Algorithm Hypothesis Proposal Module M, of CSR-GNN
Require: support graphs Gi...., C.
I: Initialize the masks of all support graphs all ones: m, 1, 1.....
2: for iter < 1.... do
3: for <- ....., do
4: for 1 + 1,.. ....., do
5: end for
m,R (G, (Gk, mx))
7: m ming mik
8:
end for
9:
end for
11: return Mma.... mn]
Algorithm 2 CSR- -NN Full Architecture
Require: support graphs G1, Gl,..., Gn query graph Gg
1: mi,.... m, Mp GG1....,GGr
2: Obtain subgraph embedding using the encoder: gi = SFNc: (G.: m))
3: Average subgraph embedding of the supporting graphs b = 1 E,
4: Decode masks using y from the query graph Gg: my SDEC Cq.
5: Obtain subgraph embedding for the query graph: 9u fENc(Gy, mgg)
7:
return dosine_similaree
b)
We use fDEC(-) directly as M, Combining these two steps, the full architecture is shown in the encoder fENC(-) is shared with Mene- We use the same PathCon atchitecture for fDEC for Mene, except that we concatenate to the input edge embeddings before the first layer.
where
Encoder-Decoder Pretraining To train this encoder-decoder architecture, we simply use recon- struction: given graph G and randomly sampled mask m E IR IREE,, we should obtain back the same mask after applying both encoder and decoder (Figure 2
L0s8recon fce(m, SDEC G, JENC m)))
(15)
To jointly train together with Mencs we also add contrastive loss
Mene (G,
(16)
Spas Mene (G, SDE JENc(( (G, m)))
(17)
Gneg Mene (G', (C fENc (G, m)))
(18)
contrant max s [poss g) s(gneg: g) + 0,
(19)
During pretraining, sample graph G and G' by sampling random triplets per relation and con- textualize them. G, G' should correspond to different relations. Then we sample m that represents mutiple random paths connecting either head or tail in G.
5
Experiments
We evaluate method CSR-OPT and CSR-GNN few-shot KG completion tasks over three real world KGs NELL, FB15K-237 and ConceptNet. We take NELL directly from NELL-One [3] but
Optimize Reconstruction Loss
Sample Edge Masks
Encode
Decode
Reconstruct Edge Masks
Figure Pretraining Connection Subgraph Reconstruction.

---

Table 1: Statistics of the benchmark datasets. BG refers to the background KG available during
training time.
NELL
FB15K-237
ConceptNet
#rels
#entities
#edges
#tasks
#rels
#entities
#edges
#tasks
#rels
#entities
#odges
#tusks
Trans-BG
291
68544
181109
11
200
14543
268039
30
790703
2541996
Ind- BG
291
44005
82318
200
11290
112477
14
619163
1191782
Ind-Test Test
291
24539
98791
11
200
3253
155562
10
14
171540
1350214
2
add different settings; select the fewest appearing relations as target few-shot tasks in FB15K-233
and ConceptNet following [12 23] We summarize the statistics of all three datasets in Table I We also created one synthetic dataset for explanatory purpose. Across all four KGs, (1) we first evaluate our method against the previous methods on real KGs in terms of few-shot learning performance without the pre-designed training few-shot tasks set, on both transductive and inductive settings; (2) we perform extensive ablation studies on each component of our method and show that every component are indispensable in our framework: (3) we show that with a manually curated meta-train set, meta-learning based method suffers from negative transfer when facing a different target test set; (4) on the synthetic dataset, we further show that our method is able to recover complex hypothesis and evidence connection subgraphs during the prediction. We consider state-of-ther the--rt few-shot KG completion baselines MetaR and FSRL in terms of the standard ranking metrics MRR and Hits where we sample 50 negative tail candidates for each query triplet and rank them together with the positive tail entity. Hits @ h measures the percentage of times that the positive tail ranked higher than h among the negative tail candidates. We use h = 1, 5, 10. For simplicity, we only consider the number of few shot example K = 3, even though all methods here can generalize to arbitrary K. See appendix for more details on full experiment setups. Since the methods have low variance in general, bellow we omit the standard deviations in the table and provide them instead in appendix A
5.1 Few-shot Learning without Curated Training Tasks
We first evaluate our method CSR-OPT and CSR-GNN along with baselines on the three real KGs without curated training tasks. This means that on NELL we do not use the meta-train split originally provided in NELL-One. To adapt MetaR and FSRL to this setting, we use pretrained entity and relation embeddings as in the original papers, but meta-train them on randomly sampled tasks from the background KG instead. Since our method is designed to not include entity embeddings, we add it in by concatenating the head and tail entity embedding to the representation produced by M in CSR-GN -NNN. Similarly, we also perform end-to-end finetuning on the same set of randomly sampled tasks in addition to our pretraining objectives. See ablations for these modifications in Section 5.2
5.1.1 Transductive Setting
As shown in Table 2 competitive performance without any training over the real dataset. With CSR-GNN, we can pretrain over these real KG to achieve higher performance exceeding/oompetttvv to meta learning results: CSR- GRR-NN gives 17.8% improvement of MRR over the second best method on NELL, 5% improvement on ConceptNet and comes close second on FB15k-237. On FB15K-233 237, the graph much denser than NELL and ConceptNet so that the pretrained entity embeddings could already capture most relational structures when predicting the query triples. However, this is only limited to the transductive setting, where all entities are seen during pretraining.
we demonstrate that our learning-free method CSR-OPT can already give
5.1.2 Inductive Setting
We evaluate the same set of methods in inductive version of these three datasets, where all entities involved in the testing few-shot task and their one hop neigbors are unseen in the background knowledge graph. In this setting, we do not use entity embedding for our methods, and pick the best performance for baselines between using and not using entity embedding. As shown in table 5 our methods only drops slightly performance than in the transductive setting comparing to baselines, resulting in significantly larger gains of up to 52% in this more challenging setting. This is because our architecture is designed entirely based on topological rule and does not rely on entity embeddings. while the performance of basclines in the transductive setting rely heavily on entity embedding. To
8

---

Table 2: Performance comparison transductive few-shot tasks without curated training tasks
MRR
Hits@
H
Hits @ 10
MetaR
0,471
0.322
0.647
0.763
NELL
FSRL
0.490
0.327
0.695
0.853
CSR-OPT
0.463
0,321
0.629
0.760
CSR-GNN
0.577
0.442
0.746
0.858
ConceptNeet FB15K-22 237
MetaR
0.805
0.740
0.881
0.937
FSRL
0.684
0.573
0.817
0.912
CSR-OPT
0.619
0.512
0.747
0.824
CSR-GNN
0.781
0.718
0.851
0.907
MetaR
0.318
0.226
0.390
0.496
FSRL
0.577
0.469
0.695
0.753
CSR-OPT
0.559
0,450
0.692
0.736
CSR-GNN
0.606
0,496
0.735
0.777
Table 3: Inference time on NELL (inductive setting).
Table 4: Inference time NELL (transduc- tive setting).
NELL (inductive)
MetaR
FSRL
CSR-GNN
NELL (transductive)
MetaR
FSRL.
CSR-GNN
Inference Time (8)
5,52
14.24
17,50
Inference Time (S)
5,50
14.49
18.33
MRR
0.355
0.180
0.511
MRR
0.471
0.490
0.577
further demonstrate this, we show in Appendix B that our methods achieve similar large gain of to 52% under transductive setting when all entity embedding are randomized during testing, equivalent to an extreme inductive setting.
Table 5: Performance comparison on inductive few-shot tasks without curated training tasks
MRR
Hits@1
Hits@s
Hits @ 10
MetaR
0.353
0.191
0.517
0.820
FB1 NELL
FSRI.
0.180
0.090
0.242
0.360
CSR-OPT
0.425
0.303
0.534
0.657
CSR-GNN
0,511
0.348
0.725
0.837
MetaR
0,315
0.143
0.506
0.896
FSRL
0.453
0,299
0.571
0.922
CSR-OPT
0.554
0,429
0.727
0.844
CSR-GNN
0.624
0.479
0.833
0.894
MetaR
0.154
0.041
0.260
0.452
FSRL
0.402
0.233
0.603
0.740
CSR-OPT
0.547
0.425
0.726
0.740
CSR-GNN
0.611
0.496
0.729
0.786
5.1.3 Inference Time
We have also measured the inference time of our method and baselines on NELL. As shown in Table and 4 we find that our method has comparable inference runtime compared with state-of-the oftte-of-hheartt baselines FSRL but it's slower than MetaR. The reason is that for each query triplet, our model needs to use the evidence proposal module to decode the edge masks and obtain the embeddings for connection subgraphs. Compared with MetaR, which directly uses shallow KG embeddings to score each query triplet TransE style, CSR achieves much better empirical performance and also allows inductive sho-shot KG link prediction.

---

Table 6: Ablative results on NELL.
Entity Embedding
Finetuning
Hypothesis Proposal
Evidence Proposal
MRR
0.577
X
0.511
X
0.466
X
0.441
X
0.436
X
0.420
5.2
Ablation Study
Here we conduct ablation study on each component of our proposed model CSR-GN on the NELL dataset. Specifically we consider the four components of our models. It includes (1) whether we use the pretrained KG entity embeddings or not; (2) whether we perform additional finetuning of our model; (3) whether we perform the hypothesis proposal as shown in Algorithm I an alternative is to directly assign full one masks for m....... my, without detecting the common subgraph: (4) whether we perform the evidence proposal for the query triplets, if not, we will propose full one mask for the query graph. As shown in Table 6 each component in our model is indispensable. Due our model architecture design, without entity embeddings, MRR decreases from 0.577 to 0.511, however it's still much higher than state-of-the- Next we show that the two proposed stages Hypothesis Proposal and Evidence Proposal play key role. Without either of them, it means that our model can no longer accurately perform eliminative induction over the support or the query triples, which may significantly deteriorates the performance.
baselines with pretrained entity embeddings (0.471 for MetaR).
5.3 Robustness to Distribution Shift
To demonstrate the distribution shift problem when constructing meta-training set, we construct new set of test few-shot learning tasks and compare the meta-learning based methods performance on this new test set against performance on the original test set when using the same meta-training set. Specifically, on the existing NELL dataset, the meta-training and test tasks/relations are sampled from the same long-tail distribution. Here sample the new set of test few-shot learning tasks by randomly sampling the 10 test relations from the whole background KG, so that there exists a gap between the training tasks and the test tasks the new set. Comparing ours with the state-of-the-art FSRL, we achieve comparable MRR on both test the original and our new challenging tasks (0.590 0.540) while FSRL suffers greatly from the distribution gap (0.578 0.459). This demonstrates the robustness of our method in handling different distribution of test tasks.
5.4 Synthetic Dataset
For explanatory purpose, we construct synthetic datasets that strictly follow our assumptions so that we have the ground truth of hypothesis connection subgraphs. In each task, support graphs contain shared connection graph, and the query is only True if the query graph also contains the same connection graph. We show that CSR-OPT can recover hypothesis and evidence connection subgraphs with high IOU of 0.843 and 0.992 when the hypothesis is in the form of 4 clique. With direct supervision of ground truth hypothesis during training, CSR-GNN can also achieve high IOU of 0.809 and 0.981. See full details in Appendix
Conclusion
In this paper proposed CSR, general framework for few-shot relational reasoning over knowledge graphs using self-supervised pretraining. Based on eliminative induction, we model hypothesis as shared connection subgraph between the support triplets and predict the query triplets by checking evidence of the connection subgraph the query graph. Our method achieves sfate-of-the-an performance across multiple datasets few-shot link prediction without curated training tasks.
10

---

Acknowledgments and Disclosure of Funding
We thank Yuhuai Wu for discussions and for providing feedback on our manuscript. We also grate- fully acknowledge the support of DARPA under Nos. HR001 12190039 (TAMI), N66001 1924033 (MCS); ARO under Nos. W911NE-16 16-1-442 (MURI), W91 IN 16- 1-0171 (DURIP); NSF under Nos. OAC- MACC-183555 835598 (CINES), DAC-1934577 (HDR), CCF-1918940 (Expeditions), NIH under No. BU54HG010426-04SI (HuBMAP), Stanford Data Science Initiative, Wu Tsai Neurosciences Insti- tute, Amazon, Docomo, GSK, Hitachi, Intel, JPMorgan Chase, Juniper Networks, KDDI, NEC, and Toshiba. Hongyu Ren is supported by Masason Foundation PhD fellowship. Apple PhD fellowship and Baidu PhD scholarship. Qian Huang is supported by Open Philamthropy Al fellowship.
The content solely the responsibility of the authors and does not necessarily represent the official views of the funding entities.
References
[1] T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next-generation hyperparam- eter optimization framework. KDD, 2019.
[2] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, Askell, S. Agarwal, A. Herbert- Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. ArXiv, 100/20055111165 2020.
[3] M. Chen, W. Zhang, W. Zhang, Q. Chen, and H. Chen. Meta relational learning for few-shot link prediction in knowledge graphs. In EMNLP, 2019.
[4] A. Chowdhury, M. Jiang, and C. Jermaine. Few-shot image classification: Just use library of pre-trained feature extractors and a simple classifier. In ICCV, 2021.
[5] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani,
M. Minderer, G. Heigold, S. Gelly, Uszkoreit, and N. Houlsby. An image is worth 16x16 words; Transformers for image recognition at scale. ArXiv, 2021.
[6] L. Galárraga, C. Teffioudi, K. Hose, and F. M. Suchanek. Amie: association rule mining under incomplete evidence in ontological knowledge bases. In WWW, 2013.
[7] S. Gidaris, A. Bursuc, N. Komodakis, P. Pérez, and M. Cord. Boosting few-shot visual learning with self-supervision. In ICCV, 2019.
[8] T. M. Hospedales, A. Antoniou, P. Micaelli, and A. J. Storkey. Meta-learning in neural networks: survey, IEEE transactions on pattern analysis and machine intelligence, 2021.
[9] D. Hunter. No wilderness of single instances: inductive inference in law. Journal of Legal Education, 1998.
[10] S. Ji, S. Pan, E. Cambria, P. Marttinen, and P. S. Yu. A survey on knowledge graphs: Repre- sentation, acquisition, and applications. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[11] X. V. Lin, R. Socher, and C. Xiong. Multi-hop knowledge graph reasoning with reward shaping. In EMNLP, 2018
[12] X. Lv, Y. Gu, X. Han, L. Hou, J. Li, and Z. Liu. Adapting meta knowledge graph information for multi-hop reasoning over few-shot relations. In EMNLP-IJCNLP. 2019.
[13] T. M. Mitchell, W. W. Cohen, E. R. Hruschka, P. P. Talukdar, B. Yang. J. Betteridge, A. Carlson, B. Dalvi, M. Gardner, B. Kisiel, Krishnamurthy, N. Lao, K. Mazaitis, T. Mohamed, Nakas- hole, E. A. Platanios, A. Ritter, M. Samadi, B. Settles, R. C. Wang, D. Wijaya, A. K. Gupta, X. Chen, A. Saparov, M. Greaves, and Welling. Never-ending learning. Communications of the ACM, 2015.
11

---

[14] J. C. Platt and A. H. Barr. Constrained differential optimization. In NeurlPS, 1987.
[15] M. Qu, J. Chen, L.-P. Xhonneux, Y. Bengio, and J. Tang. (RNNLJogic: Learning logic rules for reasoning on knowledge graphs. In ICLR, 2021.
[16] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. 2019.
[17] R. Speer, J. Chin, and C. Havasi. Conceptnet 5.5: An open multilingual graph of general knowledge. In AAAI, 2017.
[18] J. Sun, Y. Zhou, and C. Zong. One-shot relation learning for knowledge graphs via neighbor- hood aggregation and paths encoding. Trunsactions on Asian and Low-Resource Language Information Processing, 2022.
[19] K. K. Teru, E. Denis, and W. L. Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
[20] K. Toutanova, D. Chen, P. Pantel, H. Poon, P. Choudhury, and M. Gamon. Representing text for joint embedding of text and knowledge bases. In EMNLP, 2015.
[21] H. Wang. Ren, and J. Leskovec. Relational message passing for knowledge graph completion. In KDD, 2021.
[22] W. Xiong, T.-L.-. Hoang, and W. Y. Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
[23] W. Xiong, M. Yu, S. Chang, X. Guo, and W. Y. Wang. One-shot relational learning for knowledge graphs. In EMNLP, 2018
[24] C. Zhang, H. Yao, C. Huang, M. Jiang, Z. Li, and N. Chawla. Few-shot knowledge graph completion. In AAAI, 2020.
[25] M. Zhang and Y. Chen. Link prediction based on graph neural networks. In NeurIPS, 2018.
[26] Z. Zhu, Z. Zhang, L.-P. Xhonneux. and J. Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. In NeurlPS, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We described limitation on dense KG such as FB 15332-337 briefly in the experiment section. See Appendix for more discussion
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] in supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix.
12

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Appendix.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasin new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "qh_wBdd4ATN", "reviewer": "Reviewer_LUSp", "summary": "The author proposes  a method that can perform well on any novel few-shot tasks without relying on specifically designed meta-training set.\nThe proposed approach relies on an intuition that entities linked by the same relation should have a similar-strctured subgraph.\nThe framework is called connection subgraph reasoner, it has two major components: hypothesis proposal module and evidence proposal module. The hypothesis proposal module generates a hypothesis embedding from each support graph such that they are most similar to each other. Then, the evidence model attempts to find the closest evidence to the hypothesis embedding.\nIn a leanring-free optimization, the output masks are optimized directly. \nThere's also a learning version where the masks are outputed by a neural model.\nIn experiments strong performance is shown. Especially in inductive setting.", "questions": "Some part of the paper is not easy to follow. (see my questions)", "limitations": "I did not find a limitation section in the main text.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed method is novel.\n\nI think the idea of subgraph matching is interesting. \n\nIn experiments strong performance is shown. Especially in  inductive setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GH20k547zEr", "reviewer": "Reviewer_iFPo", "summary": "* The paper presents a novel way of performing few-shot KB completion without having to rely on meta-train datasets constructed in an ad-hoc fashion. Specifically, they propose learning a hypothesis proposal module that given different support evidence graphs, finds a common hypothesis that is supported by the evidence. The hypothesis is then instantiated with the different examples and passed to the encoder to generate a representation of the support examples. During inference, the proposed method checks if there is an evidence close enough to the proposed hypothesis using the Evidence Proposal module to first generate a hypothesis, and then instantiating it with the query, and using the encoder to generate the query evidence representation. \n* The authors present 2 approaches for the hypothesis proposal and evidence proposal modules: an optimization based training free method, and a fully trainable GCNN approach. For the latter, they present a self-supervised pre-training method for training. \n* The optimization free method is competitive against other Meta learning approaches, while the fully trainable approach outperforms them, especially for the scenario where inference is performed on unseen entities (dubbed the inductive setting in the paper).  ", "questions": "Questions and Typographic improvements:\n* Is there a hypothesis why even randomly initialized encoders work well with the training free approach. On a similar line of reasoning, would it be possible to get the results of using the training free approach, but leveraging the encoder trained with the learning based scheme ?\n* For Algorithm 1, I think line 8 is incorrectly placed ? (It should be placed after line 6, if my understanding is correct)\n* In Line 62, cook => chop ?\n* For the Synthetic dataset experiment, it would be good to include some more details in the main paper from the appendix.", "limitations": "The authors have covered the limitations fairly well. I am a little concerned w.r.t inference cost of the proposed method. If it is indeed an issue, it would also be good to mention that in the limitations as well.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper presents an interesting approach for adapting to few-shot KB completion, which is contrary to the popular meta-learning approach.\n* It is especially interesting to see that the training free approach, with randomly initialized encoders performs competitively against other Meta learning approaches.\n * The results especially for the transductive setting for ConceptNet and NELL, and inductive setting for all 3 datasets, are quite compelling with substantial improvements over the baseline. In addition, the approach also appears to be fairly robust to distribution shifts.\n\nWeakness\n* Given that during inference, for each entity pair, the model needs to compute a forward pass through Evidence Proposal Module and the Encoder Module, it would be good to also compare the inference time of the proposed method compared to the baseline approaches. \n* Since the approach should produce interpretable masks, it might be helpful and insightful to include some qualitative examples. Eg: for the running example in the paper (chop, <>, kitchen), does the hypothesis proposal module actually identify the underlying accurate hypothesis, and is that correctly re-generated from the Evidence Proposal module. \n* The definition of pre-training is a bit overloaded. From the Supplementary material, it seems like the model is jointly trained with all 3 losses, as opposed to first doing self-supervised pre-training followed by finetuning. It might be good to clarify that in the paper. \n* [Minor] This setup for few-shot link prediction seems to be very well suited for in-context learning setups. I wonder if it makes sense to also compare against the same. \n* [Minor] The paper is a bit hard to parse: some of the notation (eg: Equations 9 and 11) are somewhat non-standard, in Equation 16, T is not defined, and it is somewhat unclear how all the pieces fit together. It would be nice if the authors could present (even in the Appendix, if space is a concern) an Algorithm that clearly defines how the different proposals are connected for a training and inference pass through the dataset. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5_djsQdOf3a", "reviewer": "Reviewer_LgC2", "summary": "In this paper, the authors investigated few-shot knowledge graph completion task. Previous work usually model this under meta-learning framework. The authors proposed to leverage sub-graph between the head entity and tail entity, which may be shared between support and query triplets. Through this way, they are able to better predict the target entity through the shared subgraph, which contains richer local information that the model can leverage. To get a model that can be generalized to specific KG, they proposed to pretrained encoder-decoder model with the pretraining task to recover the masked nodes and relations in the subgraph. The experimental verify the effectiveness of the proposed model, which outperforms the baseline models on multiple existing datasets dramatically.", "questions": "What if there are no relationship between  subgraphs in support and query sets, will the pretrained model still work properly?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The authors proposed an approach to leverage local subgraph for few-shot relational reasoning tasks, which achieves state-of-the-art performance on multiple datasets.\n* They proposed to pretrain an encoder-decoder model which can generalize to specific KG.\n* The paper is well-written and easy to follow.\n\nWeaknesses:\nOn some datasets like FB15K-237, the proposed approach underperforms an existing baseline model, which may raise the question of the generalization ability of the pretrained model and on what kind of datasets will this model performs better. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept