Geodesic Graph Neural Network for Efﬁcient Graph Representation Learning Lecheng Kong

2025-04-29 0 0 751.62KB 20 页 10玖币

侵权投诉

Geodesic Graph Neural Network for Efﬁcient Graph

Representation Learning

Lecheng Kong

Washington University in St. Louis

jerry.kong@wustl.edu

Yixin Chen

Washington University in St. Louis

ychen25@wustl.edu

Muhan Zhang

Peking University

muhan@pku.edu.cn

Abstract

Graph Neural Networks (GNNs) have recently been applied to graph learning tasks

and achieved state-of-the-art (SOTA) results. However, many competitive methods

run GNNs multiple times with subgraph extraction and customized labeling to

capture information that is hard for normal GNNs to learn. Such operations are time-

consuming and do not scale to large graphs. In this paper, we propose an efﬁcient

GNN framework called Geodesic GNN (GDGNN) that requires only one GNN run

and injects conditional relationships between nodes into the model without labeling.

This strategy effectively reduces the runtime of subgraph methods. Speciﬁcally,

we view the shortest paths between two nodes as the spatial graph context of

the neighborhood around them. The GNN embeddings of nodes on the shortest

paths are used to generate geodesic representations. Conditioned on the geodesic

representations, GDGNN can generate node, link, and graph representations that

carry much richer structural information than plain GNNs. We theoretically prove

that GDGNN is more powerful than plain GNNs. We present experimental results

to show that GDGNN achieves highly competitive performance with SOTA GNN

models on various graph learning tasks while taking signiﬁcantly less time.

1 Introduction

Graph Neural Network (GNN) is a type of neural network that learns from relational data. With the

emergence of large-scale network data, it can be applied to solve many real-world problems, including

recommender systems [

], protein structure modeling [

], and knowledge graph completion [

The growing and versatile nature of graph data pose great challenges to GNN algorithms both in their

performance and their efﬁciency.

GNNs use message passing to propagate features between connected nodes in the graph, and the

nodes aggregate their received messages to generate representations that encode the graph structure

and feature information around them. These representations can be combined to form multi-node

structural representations. Because GNNs are efﬁcient and have great generalizability, they are widely

employed in node-level, edge-level, and graph-level tasks. A part of the power of GNNs comes from

the fact that they resemble the process of the 1-dimensional Weisfeiler-Lehman (1-WL) algorithm

[

]. The algorithm encodes subtrees rooted from each node through an iterative node coloring

process, and if two nodes have the same color, they have the same rooted subtree and should have very

similar surrounding graph structures. However, as pointed out by Xu et al.

[45]

, GNN’s expressive

power is also upper-bounded by the 1-WL test. Speciﬁcally, GNN is not able to differentiate nodes

that have exactly the same subtrees but have different substructures. For example, consider the graph

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

arXiv:2210.02636v2 [cs.LG] 12 Feb 2023

in Figure 1 with two connected components, because all nodes have the same number of degrees,

they will have exactly the same rooted subtrees. Nevertheless, the nodes in the left component are

clearly different from the nodes in the right component, because the left component is a 3-cycle and

the right one is a 4-cycle. Such cases can not be discriminated by GNNs or the 1-WL test. We refer

to this type of GNN as plain GNN or basic GNN.

Figure 1: An example where

plain GNN fails to distinguish

nodes in the graph.

On the other hand, even when a carefully-designed GNN can dif-

ferentiate all node substructures in a graph, Zhang et al.

[54]

show

that the learned node representation still cannot effectively perform

structural learning tasks involving multiple nodes, including link

predictions and subgraph predictions, because the nodes are not able

to learn the relative structural information. We will discuss this in

more detail in Section 3.1.

These limitations motivate recent research that pushes the limit of

GNN’s expressiveness. One branch is to use higher-order GNNs

that mimic higher-dimensional Weisfeiler-Lehman tests [

]. They extend node-wise message

passing to node-tuple-wise and obtain more expressive representations. Another branch is to use

labeling methods. By extracting subgraphs around the nodes of interest, they design a set of subgraph-

customized labels as additional node features. The labels can be used to distinguish between the

nodes of interest and other nodes. The resulting node representations can encode substructures that

plain GNNs cannot, like cycles.

However, the major drawback of these methods is that compared to plain GNNs, their efﬁciency is

signiﬁcantly compromised. Higher-order GNNs update embeddings over tuples and incur at least

cubic complexity [

]. Labeling tricks usually require subgraph extraction on a large graph and

running GNNs on mini-batches of subgraphs. Because the subgraphs overlap with each other, the

aggregated size of the subgraphs is possibly hundreds of times the large graph. Nowadays GNNs are

massive, the increased graph computation cost makes labeling methods inapplicable to real-world

problems with millions of nodes.

We observe that a great portion of the labeling methods relies on geodesics, namely the shortest

paths, between nodes. For node representation, Distance-Encoding (DE) [

] labels the target nodes’

surrounding nodes with their shortest path distance to the target nodes and achieves higher than 1-WL

test expressiveness. Current state-of-the-art methods for link prediction, such as SEAL [

], leverage

the labeling tricks in order to capture the shortest path distance along with the number of shortest

paths between the two nodes of the link. Inspired by this, we propose our graph representation

learning framework, Geodesic GNN (GDGNN), where we run GNN

only once

and inject higher

expressiveness into the model using shortest paths information by a geodesic pooling layer. Our

framework can obtain higher than 1-WL power without multiple runs of plain GNNs, which largely

improves the efﬁciency of more expressive methods.

Speciﬁcally, our GDGNN model learns a function that maps the learning target to a geodesic-

augmented target representation (the target can be a node, edge, graph, etc). The model consists

of two units, a GNN unit, and a geodesic pooling unit. The two units are connected to perform

end-to-end training. We ﬁrst apply the GNN to the graph to obtain embeddings of all nodes. Then, for

each target, we ﬁnd the task-speciﬁc geodesics and extract the corresponding GNN representations

of nodes on the geodesics. The task-speciﬁc geodesics have three levels. For node-level tasks, we

extract the geodesics between the target node and all of its neighbors. For edge-level tasks, we

extract the geodesics between the two target nodes of the edge. For graph-level tasks, we get the

geodesic-augmented node representation for each node as in node-level tasks and readout all node

representations as the graph representation. Finally, using the geodesic pooling unit, we combine

the geodesic representation and target representation to form the ﬁnal geodesic augmented target

representation. Figure 2 summarizes the GDGNN framework.

All task-speciﬁc geodesics are formed by one or multiple

pair-wise

geodesics between two nodes.

We propose two methods to extract the pair-wise geodesic information, horizontal and vertical. The

horizontal geodesic is obtained by directly extracting one shortest path between the two nodes. The

vertical geodesic is obtained by extracting all direct neighbors of the two nodes that are on any of

their shortest paths. They focus on depth and breadth respectively. Horizontal geodesic is good at

capturing long-distance information not covered by the GNN. Vertical geodesic is provably more

powerful than plain GNN. Moreover, by incorporating the information of the subgraph induced by

Task-Specific Geodesics Pooling Function

Link Representation

GNN

Target graph GNN processed graph

with embeddings Vertical Geodesic

Horizontal Geodesic

Node Representation Graph Representation

Embeddings of

colored nodes are

used to generate

Pair-wise Geodesic

Representation

Multiple pair-

wise geodesics

are combined

Geodesics

information of

multiple nodes

are combined

Figure 2: The overall pipeline of GDGNN. GNN is applied once to generate node embeddings. We

then use horizontal or vertical geodesic to extract pair-wise geodesic representation. One or more

such representations are collected to generate task-speciﬁc representation.

the vertical geodesic nodes, we can use GDGNN to distinguish some distance-regular graphs, a type

of graph that many current most powerful GNNs cannot distinguish.

During inference, the GNN unit is applied only once to the graph, after which we feed nodes and

geodesic information to the efﬁcient geodesic pooling unit. This limits the number of GNN runs from

the query number (or the number of nodes for graph-level tasks) to a constant of one and remarkably

reduces the computation cost. Compared to labeling methods, GDGNN only requires one GNN run

and is much more efﬁcient. Compared to plain GNN methods, GDGNN uses geodesic information

and thus is more powerful. We conducted experiments on node-level, edge-level, and graph-level

tasks across datasets with different scales and show that GDGNN is able to signiﬁcantly improve

the performance of basic GNNs and achieves very competitive results compared to state-of-the-art

methods. We also demonstrate GDGNN’s runtime superiority over other more-expressive GNNs.

2 Preliminaries

A graph can be denoted by

G= (V,E,R)

, where

V={v1, ..., vn}

is the node set,

E ⊆

{(vi, r, vj)|vi, vj∈ V, r ∈ R}

is the edge set and

is the set of edge types in the graph. When

|R| = 1

, the graph can be referred to as a homogeneous graph. When

|R| >1

, the graph can be

referred to as a heterogeneous graph. Knowledge graphs are usually heterogeneous graphs. The

nodes can be associated with features

X={xv|∀v∈ V}

. For simplicity, we use homogeneous

graphs to illustrate our ideas and methods.

We follow the deﬁnition of message passing GNNs in [

] with AGGREGATE and COMBINE

functions. Such GNNs iteratively update the node embeddings by receiving and combining the

neighbor nodes’ embeddings. The k-th layer of a GNN can be expressed as:

m(k)

u=AGGREGATE(K)(h(k−1)

u),h(k)

v=COMBINE({m(k)

u, u ∈ N(v)},h(k−1)

v)(1)

where

h(k)

is the node representation after

iterations,

h(0)

v=xv

N(v)

is the set of direct

neighbors of

is the message embedding. Different GNNs vary mainly by the design choice of

the AGGREGATE and COMBINE functions. In this paper, we use

to represent the ﬁnal node

representation of

from the plain GNN. In this paper, we use bold letters to represent vectors, capital

letters to represent sets, and Nk(v)to refer to nodes within the k-hop neighborhood of v.

3 Geodesic Graph Neural Network

Geodesic is conventionally deﬁned as the shortest path between two nodes and indeed in homogeneous

graphs, it encodes only the distance. However, we found that when combined with GNNs and node

representations, geodesics express information much richer than the shortest path distance alone. In

this section, we ﬁrst discuss the intuition behind GDGNN and its effectiveness. Then, we describe

the GDGNN framework and how its GNN unit and geodesic pooling unit are combined to make

predictions. Finally, we provide theoretical results of the better expressiveness of GDGNN.

B C

(a)

B B

(b)

(c)

𝒗𝟏

𝒗𝟐

(d)

Figure 3: (a) A circular graph where plain GNN cannot distinguish link AB and AC. (b) and (c) are

the GNN computation graphs of A if B and C, respectively, are labeled. (d) is an example where

geodesic representation can distinguish links AB and AC, but distance fails to do so.

3.1 Intuition and Overview

The key weakness of directly using plain GNNs is that the embeddings are generated without

conditional information. For node-level tasks, as pointed out in [

], a plain GNN is unaware of

the position of the target node in the rooted subtree, and hence the target node is oblivious of the

conditional information about itself. For edge-level tasks, Zhang et al.

[54]

shows that despite a

node-most-expressive-GNN, without node labeling, the embedding of one node in the edge is not

able to preserve the conditional information of the other node. Concretely, take link prediction as

an example, in Figure 3a, we have two target links AB and AC. Since AB is already connected by a

link and AC is not, they should be represented differently. On the other hand, All nodes in the graph

are symmetric and should be assigned the same embeddings using any GNN. Hence, if we simply

concatenate the node representations of AB and AC, they will have the same link representations, and

cannot be differentiated by any downstream learner. To overcome this problem, previous methods

rely on labeling tricks to augment the computation graphs with conditional information. When node

B and C are labeled respectively in two separate subgraphs, the resulting computation graphs of A

are different as shown in Figure 3b and 3c.

Notice that, for the labeling methods to take effect, subgraph extraction is necessary. However,

relabeling the graph and applying a GNN to every target to predict is extremely costly. Hence, we

wonder whether we can also incorporate conditional information between nodes without customized

labeling. Observe that in the example, the computation graph captures the number of layers before

node A ﬁrst receives a message from a labeled node, which is essentially the shortest path distance

between A and the other node. This implies that even when we

only

have node representations

from a plain GNN, by adding the distance information (which is 1 and 3 for AB and AC respectively)

independent of the computation graph, we can still distinguish the links.

While the previous example demonstrates the effectiveness of a simple shortest path distance metric,

we notice that distance alone is not always sufﬁcient. For example, in Figure 3d, node B and node C

are symmetric and hence should be assigned the same node embedding when the graph is not labeled.

However, links AB and AC are apparently different as

connecting AB connects to another group of

nodes whereas

connecting AC does not connect to any other node. If we only use the shortest path

distance between AB and AC to assist the prediction, we still cannot differentiate them. However, if

we inject the

entire geodesic

expressed by the corresponding

node embeddings along the shortest

path to the model, we are able to tell AB and AC apart due to v1and v2’s different embeddings.

Consider a naive GNN that outputs all node embeddings as one. Taking the shortest path can be seen

as extracting a one-valued vector with a length of the shortest distance between the two nodes. In the

neural setting, a general GNN can model the naive GNN and the nodes on the same shortest path can

have different representations besides one by encoding their own neighborhood. The extension of the

shortest path to the neural setting grants stronger expressive power to the geodesics. The geodesic

generation and the GNN are decoupled, because the selection of geodesic nodes is independent of

the node representations, while the node representations in subgraph GNNs are tied to a subgraph.

Dwelling on this decoupling and conditioning philosophy, GDGNN can run the GNN

only once

generate generic node embeddings and then use geodesic information to inject conditional information

into the model in a much more efﬁcient way.

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

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

10 玖币 0人已下载

立即下载

摘要：

GeodesicGraphNeuralNetworkforEfcientGraphRepresentationLearningLechengKongWashingtonUniversityinSt.Louisjerry.kong@wustl.eduYixinChenWashingtonUniversityinSt.Louisychen25@wustl.eduMuhanZhangPekingUniversitymuhan@pku.edu.cnAbstractGraphNeuralNetworks(GNNs)haverecentlybeenappliedtographlearningtasksa...

展开>> 收起<<

Geodesic Graph Neural Network for Efﬁcient Graph Representation Learning Lecheng Kong.pdf

共20页,预览4页

还剩页未读，继续阅读

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

Geodesic Graph Neural Network for Efﬁcient Graph Representation Learning Lecheng Kong

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: