Few-shot Relational Reasoning via Connection Subgraph Pretraining Qian Huang

2025-04-24 0 0 927.69KB 18 页 10玖币

侵权投诉

Few-shot Relational Reasoning via Connection

Subgraph Pretraining

Qian Huang∗

Stanford University

qhwang@cs.stanford.edu

Hongyu Ren∗

Stanford University

hyren@cs.stanford.edu

Jure Leskovec

Stanford University

jure@cs.stanford.edu

Abstract

Few-shot knowledge graph (KG) completion task aims to perform inductive rea-

soning over the KG: given only a few support triplets of a new relation



(e.g.,

(

chop



kitchen

), (

read



library

)), the goal is to predict the query triplets

of the same unseen relation



,e.g., (

sleep



). Current approaches cast the

problem in a meta-learning framework, where the model needs to be ﬁrst jointly

trained over many training few-shot tasks, each being deﬁned 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 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 speciﬁc KG, we design a corre-

sponding 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 signiﬁcant

gains of up to 52% on the more challenging inductive few-shot tasks where the

entities are also unseen during (pre)training.

1 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

) Ji et al. [2022],

Mitchell et al. [2015], Speer et al. [2017], Toutanova et al. [2015]. Since KGs are typically highly

incomplete yet widely used in downstream applications, predicting missing edges, i.e., KG completion,

is one of the most important machine learning tasks over these large heterogeneous data structures.

Deep learning based methods have achieved great success on this task Teru et al. [2020], Wang et al.

[2021], Zhu et al. [2021], but the more challenging few-shot setting Xiong et al. [2018] is much

less explored: Given a 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 a query entity and

candidate answers based on the background knowledge graph. Such a setting captures the most

difﬁcult 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 efﬁciently. It also tests the

∗indicates equal contribution.

36th Conference on Neural Information Processing Systems (NeurIPS 2022).

arXiv:2210.06722v1 [cs.LG] 13 Oct 2022

Hypothesis

Proposal

Score = cosine

similarity

(B) Background KG

Support set Sr'

Query set Qr'

(A) Few-shot Task (C) Connection Subgraph Reasoner

Evidence

Proposal

Contextualize

Evidence

S1 :

S2 :

S1 :

S2 :

Q1 :Q1 :

Enc

Shared hypotheses

Enc

⨁

Figure 1: The few-shot KG completion problem includes (A) few-shot task that aims to learn a new

relation (purple) and (B) background knowledge graph. Our CSR framework (C) ﬁrst contexualizes

all triplets in the background KG, then ﬁnds the shared hypothesis in the form of a connection

subgraph using the Hypothesis Proposal module, and ﬁnally 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.

inductive reasoning skill of the model on deriving new knowledge data-efﬁciently, which is critical

for AI in general.

Existing approaches to few-shot KG completion Chen et al. [2019], Sun et al. [2022], Xiong et al.

[2018], Zhang et al. [2020] typically adopt the meta-learning framework Hospedales et al. [2021],

where the model is trained over a meta-training set consisting of many few-shot tasks created from

different relations in the background knowledge graph. GMatching Xiong et al. [2018], FSRL Zhang

et al. [2020] and Att-LMetric Sun et al. [2022] are metric-based meta-learning methods that try to

learn a good metric where positive query pairs are closer to representation of edges in the support set

than the negative ones. MetaR Chen et al. [2019] is an optimization-based meta-learning method

that use a meta-learner to 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

difﬁcult ad hoc process in practice. On existing benchmarks Xiong et al. [2018], 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 a 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 to 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 speciﬁcally designed meta-training set is crucial for real-world applications.

Here we propose a novel modeling framework Connection Subgraph Reasoner (CSR)that can make

prediction on the target few-shot task directly without the need for meta-learning and creation of a

curated set of training few-shot tasks. Our insight is that a triplet of the unseen relation of interest

can be inferred through the existence of a hypothesis in the form of a connection subgraph,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



kitchen

)

example, such a connection subgraph that implies



is a two hop path in KG: {(

chop

can be done

with

knife

), (

knife

is located at

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 Hunter [1998], our framework ﬁrst recovers this hypothesis from the support

triplets by ﬁnding the connection subgraph approximately shared among the support triplets, then

tests whether this hypothesis is also a connection subgraph between the query entity and a candidate

answer. We show the full pipeline along with an example of connection subgraph in Figure 1. To

better adapt to speciﬁc KG, we design a novel encoder-decoder architecture based on graph neural

networks (GNN) to implement the two stages and a corresponding self-supervised 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 Mitchell et al. [2015], FB15K-237 Toutanova

et al. [2015], and ConceptNet Speer et al. [2017], our method consistently exceeds or matches

state-of-the-art 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://github.

com/snap-stanford/csr.

2 Related Work

2.1 Few-shot Relational Learning via Meta-Learning

Meta-learning is a paradigm of learning across a set of meta-training tasks and then adapting to a new

task during meta-testing Hospedales et al. [2021]. To the best of our knowledge, all existing methods

on few-shot KG completion follow the meta-learning paradigm to address the data scarcity in the

target few-shot task Chen et al. [2019], Sun et al. [2022], Xiong et al. [2018], Zhang et al. [2020].

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 Wiki-OneXiong et al.

[2018] 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 a meta-training set is not given in real world

application and needs to be manually constructed out of the background knowledge graph

to mimic

the actual few-shot task during test time. This curation is inherently challenging because that the

background knowledge graph has a limited number of relations/tasks in

, 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 Brown et al. [2020], Radford et al. [2019] and

computer vision Chowdhury et al. [2021], Dosovitskiy et al. [2021], Gidaris et al. [2019] domains

that large-scale self-supervised pretraining can signiﬁcantly improve task-agnostic few-shot learning

ability. One of the most successful pretraining objectives is predicting the next token or 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, we design a well motivated self-supervised

pretraining objective, i.e. recovering diverse connection subgraphs that correspond to different

inductive hypothesis. We show that such a pretraining scheme can signiﬁcantly improve few-shot

relational learning tasks on knowledge graphs.

3 Few-shot KG Completion

Few-shot KG completion is deﬁned as follows Chen et al. [2019], Xiong et al. [2018]: Denote the

background KG that represents the known knowledge as

G= (E,R,T)

, where

and

represents

the set of entities and relations.

T={(h, r, t)|h, t ∈ E, r ∈ R}

represents the facts as triplets.

Given a new relation

r06∈ R

and a support set

Sr0={(hk, r0, tk)|hk∈ E}K

k=1

, we want to make

predictions over a query set

Qr0={(hj, r0,?)|hj∈ E}J

j=1

. This prediction on

(hj, r0,?)

is typically

converted to scoring triplet

(hj, r0, e)

for all candidate entities

then ranking the scores. So we will

proceed to consider Qr0as directly containing full triplets (hj, r0, e)to score. We call this a K-shot

KG completion task, typically the number of support is a small number (K≤5).

Note that existing works generally assume the entities in the few-shot tasks (support + query set)

belong to the background KG. However, in 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

, but new triplets about these unseen entities can be added at

test time.

4 Connection Subgraph Reasoner

In this section, we ﬁrst 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 Hunter

[1998]. 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. Speciﬁcally, we consider the scientiﬁc hypothesis method: eliminating

hypotheses inconsistent with observations. In the context of few-shot link prediction task, we

explicitly try to ﬁnd 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



example where the support triplets are (

chop



kitchen

), (

read



library

), and query triplet is (

sleep



). From a background KG

(e.g.ConceptNet), we can know a lot of knowledge in forms of triplets about these entities, such as

(

kitchen

is part of

a house

) and (

read

is done by

human

) etc. We essentially want to

ﬁnd an induction hypothesis that explains how chop is related to kitchen in the same way that read is

related to library. In other words, we want to ﬁnd 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)}(1)

{(read,can be done with,book),(book,is located at,library)}(2)

The abstracted inductive hypothesis consistent with both examples in the support set is then

∃Z, (hc,can be done with, Z)∧(Z, is located at, tc) =⇒(hc, , tc).(3)

This hypothesis can then be used to deduce that (

sleep



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 a connection subgraph between the two end entities instead of a connection path

(Figure 1). Here we deﬁne the connection subgraph: Let

G0= (E0,R0,T0)

be any subgraph of the

background KG

, (i.e.,

E0⊆ E

R0⊆ R

and

T0⊆ T

) that satisﬁes the following requirement

for a given pair of nodes

(hc, tc)

on the KG. (1)

hc∈ E0

and

tc∈ E0

; (2) there is no disconnected

component. We deﬁne the connection subgraph

(hc, tc)

to be any such

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 a hypothesis.

Then a hypothesis like Eq. 3 can be represented as a connection subgraph

by interpreting

each clause as an edge. And such a hypothesis is consistent with a support/query triplet (

) if

is a connection subgraph of

h, t

. In terms of the



example, the triplet (

sleep



bedroom

) is consistent with the hypothesis Eq. 3 because the connection subgraph form of the

hypothesis

(hc,can be done with, Z)∧(Z, is located at, tc)

is a connection subgraph be-

tween sleep and bedroom, with

hc, Z, tc

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 a connection subgraph of

h, t;

. Note the key difference

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Few-shotRelationalReasoningviaConnectionSubgraphPretrainingQianHuangStanfordUniversityqhwang@cs.stanford.eduHongyuRenStanfordUniversityhyren@cs.stanford.eduJureLeskovecStanfordUniversityjure@cs.stanford.eduAbstractFew-shotknowledgegraph(KG)completiontaskaimstoperforminductiverea-soningovertheKG:gi...

展开>> 收起<<

Few-shot Relational Reasoning via Connection Subgraph Pretraining Qian Huang.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Few-shot Relational Reasoning via Connection Subgraph Pretraining Qian Huang

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: