Learning from the Dark Boosting Graph Convolutional Neural Networks with Diverse Negative Samples Wei Duan1 Junyu Xuan1 Maoying Qiao2 Jie Lu1

2025-04-29 0 0 2.39MB 9 页 10玖币

侵权投诉

Learning from the Dark: Boosting Graph Convolutional Neural Networks with

Diverse Negative Samples

Wei Duan1, Junyu Xuan1, Maoying Qiao 2, Jie Lu1

1The Australian Artiﬁcial Intelligence Institute (AAII), University of Technology Sydney

2Australian Catholic University

Wei.Duan@student.uts.edu.au, Junyu.Xuan@uts.edu.au, maoying.qiao@acu.edu.au, Jie.Lu@uts.edu.au

Abstract

Graph Convolutional Neural Networks (GCNs) has been gen-

erally accepted to be an effective tool for node representations

learning. An interesting way to understand GCNs is to think

of them as a message passing mechanism where each node

updates its representation by accepting information from its

neighbours (also known as positive samples). However, be-

yond these neighbouring nodes, graphs have a large, dark, all-

but forgotten world in which we ﬁnd the non-neighbouring

nodes (negative samples). In this paper, we show that this

great dark world holds a substantial amount of information

that might be useful for representation learning. Most speciﬁ-

cally, it can provide negative information about the node rep-

resentations. Our overall idea is to select appropriate negative

samples for each node and incorporate the negative informa-

tion contained in these samples into the representation up-

dates. Moreover, we show that the process of selecting the

negative samples is not trivial. Our theme therefore begins by

describing the criteria for a good negative sample, followed

by a determinantal point process algorithm for efﬁciently ob-

taining such samples. A GCN, boosted by diverse negative

samples, then jointly considers the positive and negative in-

formation when passing messages. Experimental evaluations

show that this idea not only improves the overall performance

of standard representation learning but also signiﬁcantly alle-

viates over-smoothing problems.

Introduction

Graphs are powerful structures for modelling speciﬁc kinds

of data such as molecules, social networks, citation net-

works, trafﬁc networks, etc. (Chakrabarti and Faloutsos

2006). However, the representation power of graphs is not

a free lunch; it brings with it issues of incompatibility with

some of the strongest and most popular deep learning algo-

rithms, as these can often only handle regular data structures

like vectors or arrays. Hence, to lend learning power to these

great tools of representation, graph neural networks (GNNs)

have emerged as a congruent deep learning architecture (Wu

et al. 2020). Such has been their success that, today, there

are many different GNN variants, each adapted for a spe-

ciﬁc task – for instance, graph sequence neural networks (Li

et al. 2016), graph convolutional neural networks (Kipf and

Figure 1: Illustration of the motivation of this work, includ-

ing the dark world (gray shadow), different semantic clusters

(green, yellow, purple, blue nodes), positive samples (nodes

2, 3, 4) and selected diverse negative samples (nodes 6, 11,

and 18) of a given node (node 1).

Welling 2017), and spatio-temporal graph convolutional net-

works (Yu, Yin, and Zhu 2018).

Among all the varieties of GNNs, graph convolutional

neural networks (GCN) (Kipf and Welling 2017) is a sim-

ple but representative and salient one, which introduces the

concept of convolution to GNNs that means to share weights

for nodes within a layer. An easy and intuitive way to under-

stand GCNs is to think of them as a message passing mech-

anism (Geerts, Mazowiecki, and P´

erez 2021) where each

node accepts information from its neighbouring nodes to up-

date its representation. The basic idea is that the representa-

tions of nodes with edge between them should be positively

correlated. Hence, the neighboring nodes are also named

as positive samples1. This message-passing mechanism is

highly effective in many scenarios, but it does lead to an an-

noying over-smoothing problem where the node representa-

tions become more and more similar as the number of layers

of the graph neural network increases. This is hardly sur-

1Hereafter we refer to neighbouring nodes and positive samples

interchangeably.

arXiv:2210.00728v1 [cs.LG] 3 Oct 2022

prising when each node only updates its representation ac-

cording to its neighbours. Yet, beyond these observed edges,

there is a dark world that could provide diverse and useful

information to the representation updates and help to over-

come the over-smoothing problem at the same time, as illus-

trated in Fig. 1. The reasoning is this: two nodes without

edge between them should have different representations,

so we can understand this as a negative link. However, in

contrast to the commonly used positive links, these negative

links are rarely used in the existing various GCNs.

Selecting appropriate negative samples in a graph is not

trivial. To our knowledge, only three studies have explored

procedures to this end. The ﬁrst is Kim and Oh (Kim and

Oh 2021), who propose the natural and easy approach of

uniformly randomly selecting some negative samples from

non-neighbouring nodes. However, as we all know, a large

graph is normally has the small-world property (Watts and

Strogatz 1998) which means the graph will tend to contain

some clusters. Moreover, nodes in the same cluster will tend

to have similar representations while nodes within different

clusters will tend to have different representations, as illus-

trated in Fig. 1. Hence, under uniform random selection, the

large clusters will overwhelm the smaller ones, and the ﬁnal

converged node representations will be short on information

contained in the small clusters. Of the other two methods,

one is based on Monte Carlo chains (Yang et al. 2020) and

the other on personalised PageRank (Ying et al. 2018), and

neither covers diverse information as well. Further, the se-

lected negative samples should not be redundant; each of

them should not be overlapping and hold distinct informa-

tion. Hence, as a deﬁnition, a good negative sample should

contribute negative information to the given node contrast

to its positive samples and include as much information as

possible to reﬂect the variety of the dark world.

In this paper, we propose a graph convolutional neu-

ral network boosted by diverse negative samples selected

through a determinant point process (DPP). DPP is special

point process for deﬁning a probability distribution on a set

where more diverse subset has a higher probability (Hough

et al. 2009). Our idea is to ﬁnd diverse negative samples

for a given node by ﬁrstly deﬁning a DPP-based distribu-

tion on diverse subsets of all non-neighbouring nodes of this

node, and then outputting a diverse subset from this distri-

bution. The number of subsets is limited because the sam-

ples are mutually exclusive. However, when applying this

algorithm to large graphs, the computational cost can be as

high as O(N3), where Nis the number of non-neighbouring

nodes. Therefore, we propose a method based on a depth-

ﬁrst search (DFS) that collects diverse negative samples se-

quentially along the search path for a node. The motivation

is that a DFS path is able to go through all different clus-

ters in the graph and, therefore, the local samples collected

will form a good, diverse approximation of all the infor-

mation in the dark world. Further, the computational cost

is approximately O(pa ·deg3)where pa Nis the path

length (normally smaller than the diameter of the graph) and

deg Nis the average degree of the graph. As an ex-

ample, consider a Cora graph (Sen et al. 2008) with 3,327

Symbol Meaning

Ga graph

Gnthe node set of graph G

Ya ground set

Ya node subset

kthe number of negative samples of a given

node in a graph

N(i)neighbours (positive samples) of node i

N(i)negative samples of node i

x(l)

ithe representation of node iat layer l

deg(i)the degree of node i

Lthe L-ensemble of DPP

λthe eigenvalues of L

e|Y|

kthe kth elementary symmetric polynomial on

eigenvalues λ1, λ2, . . . , λ|Y| of L

vthe eigenvectors of the L-ensemble

Vthe set v

Table 1: Key notations

nodes, pa = 19, and deg = 3.9. Thus, O(N3)=3.6e10 

1,127 = O(pa ·deg3).

In evaluating these ideas, we conducted empirical experi-

ments on different tasks, including node classiﬁcation and

over-smoothing tests. The results show that our approach

produces superior results.

Thus, the contributions of this study include:

• A new negative sampling method based on a DPP that

selects diverse negative samples to better represent the

dark information;

• A DFS-based negative sampling method that sequentially

collects locally diverse negative samples along the DFS

path to greatly improve computational efﬁciency;

• We are the ﬁrst to fuse negative samples into the graph

convolution, yielding a new GCN boosted by diverse

negative samples (D2GCN) to improve the quality of

node representations and alleviate the over-smoothing

problem.

Preliminaries

This section brieﬂy introduces the basic concepts of graph

convolutional neural networks, message passing, and deter-

minantal point process.

Graph Convolutional Neural Networks (GCNs)

GCNs introduce traditional convolution from classical neu-

ral networks to graph neural networks. Like a message-

passing mechanism, the representation of a node is updated

using its neighbours’ representations through

xi(l)=X

j∈Ni∪{i}

pdeg(i)·pdeg(j)Θ(l)·x(l−1)

j(1)

where x(l)

iare the representation of node iat layer l,N(i)

is the neighbours of node i(i.e., positive samples), deg(i)is

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

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

10 玖币 0人已下载

立即下载

摘要：

LearningfromtheDark:BoostingGraphConvolutionalNeuralNetworkswithDiverseNegativeSamplesWeiDuan1,JunyuXuan1,MaoyingQiao2,JieLu11TheAustralianArticialIntelligenceInstitute(AAII),UniversityofTechnologySydney2AustralianCatholicUniversityWei.Duan@student.uts.edu.au,Junyu.Xuan@uts.edu.au,maoying.qiao@acu....

展开>> 收起<<

Learning from the Dark Boosting Graph Convolutional Neural Networks with Diverse Negative Samples Wei Duan1 Junyu Xuan1 Maoying Qiao2 Jie Lu1.pdf

共9页,预览2页

还剩页未读，继续阅读

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

Learning from the Dark Boosting Graph Convolutional Neural Networks with Diverse Negative Samples Wei Duan1 Junyu Xuan1 Maoying Qiao2 Jie Lu1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: