Node Importance Specific Meta Learning in Graph Neural Networks
Authors: Hao Liu
Yixin Chen
Dacheng Tao
Muhan Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Meta Learning
Graph Neural Network
Node Importance

Abstract: While current node classification methods for graphs have enabled significant progress in many applications, they rely on abundant labeled nodes for training. In many real-world datasets, nodes for some classes are always scarce, thus current algorithms are ill-equipped to handle these few-shot node classes. Some meta learning approaches for graphs have demonstrated advantages in tackling such few-shot problems, but they disregard the impact of node importance on a task. Being exclusive to graph data, the dependencies between nodes convey vital information for determining the importance of nodes in contrast to node features only, which poses unique challenges here. In this paper, we investigate the effect of node importance in node classification meta learning tasks. We first theoretically analyze the influence of distinguishing node importance on the lower bound of the model accuracy. Then, based on the theoretical conclusion, we propose a novel Node Importance Meta Learning architecture (NIML) that learns and applies the importance score of each node for meta learning. Specifically, after constructing an attention vector based on the interaction between a node and its neighbors, we train an importance predictor in a supervised manner to capture the distance between node embedding and the expectation of same-class embedding. Extensive experiments on public datasets demonstrate the state-of-the-art performance of NIML on few-shot node classification problems.

Under review as a conference paper at ICLR 2023
NODE IMPORTANCE SPECIFIC META LEARNING IN GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
While current node classification methods for graphs have enabled significant progress in many applications, they rely on abundant labeled nodes for training. In many real-world datasets, nodes for some classes are always scarce, thus current algorithms are ill-equipped to handle these few-shot node classes. Some meta learning approaches for graphs have demonstrated advantages in tackling such few-shot problems, but they disregard the impact of node importance on a task. Being exclusive to graph data, the dependencies between nodes convey vital infor- mation for determining the importance of nodes in contrast to node features only, which poses unique challenges here. this paper, we investigate the effect node importance in node classification meta learning tasks. We first theoretically analyze the influence of distinguishing node importance on the lower bound of the model accuracy. Then, based on the theoretical conclusion, we propose novel Node Importance Meta Learning architecture (NIML) that learns and applies the importance score of each node for meta learning. Specifically, after construct- ing an attention vector based on the interaction between node and its neighbors, we train an importance predictor in a supervised manner capture the distance between node embedding and the expectation of same-class embedding. Exten- sive experiments on public datasets demonstrate the state-of-the- performance of NIML on few-shot node classification problems.
INTRODUCTION
Graph structure can model various complicated relationships and systems, such as molecular struc- ture (Subramanian et al.) 2005). citationships (Tang et al.) [2008b) and social media relation- ships (Ding et al. 2019). The use of various deep learning methods (Hamilton et al. 2017; Kipl & WWlling 2016) analyze graph structure data has sparked lots of research interest recently, where node classification is one of the essential problems. Several types of graph neural networks (GNNs) (Veličković et al. 2017 Wu al. (020) have been proposed address the problem by learning high-level feature representations of nodes and addressing the classification task end-to- end.
Despite the success in various domains, the performance of GNNs drops dramatically under the few-shot scenario (Mandal et 2022), where extremely few labeled nodes are available for novel classes. For example, annotating nodes in graph-structured data is challenging when the samples originate from specialist disciplines (Guo et al., 202T) like biology and medicine.
Many meta learning works, including optimization-basel methods (Finn et al. 2017) and metric- based methods (Snell al.) 2017 Vinyals et al., (016), have demonstrated their power address few-shot problems in diverse applications, such as computer vision and natural language process- ing (Lee et al.] 2022). In meta learning, a meta learner trained on various tasks with limited labeled data in order be capable of fast generalization and adaption been encountered before. However, it is considerably challenging to generalize these meta learning algorithms designed for independent and identically distributed (i.i.d.) Euclidean data to graph data.
task that has never
To address the few-shot node classification problem. some graph meta learning approaches have been proposed (Liu et al., 2021 Ding al. 2020 Yao et al. 2020). They structure the node clas- sification problem as a collection of tasks. The key idea is to learn the class of nodes in the query set by transferring previous knowledge from limited support nodes in each task. However, most

---

Under review as a conference paper at ICLR 2023
existing approaches simply assume that all labeled nodes are of equal importance represent the class they belong to. Differences and interdependencies between nodes are not considered in the learning process of the few-shot models. Since only limited data points are sampled to generate tasks in meta learning, each sampled task has high variance; therefore, treating all the data points equally might lead to loss of the crucial information supplied by central data points and render the model vulnerable to noises or outliers. In particular, the relationship between nodes and neighbors in graph is an important factor that carries node information in addition to node features, and can be utilized as starting point to investigate the importance of nodes. Although some work (Ding al. 2020) considers the importance of nodes, there lack of theoretical analysis about it.
To address the aforementioned challenges, we first explore, in theoretical manner, the effect of distinguishing nodes of different degree of importance on the lower bound of the accuracy of the model. We analyze the ProtoNet (Snell et al., (017), and conclude that when important nodes are given more weight when computing prototype representations closer to its own expectation, thus the lower bound of the accuracy will be increased. Based on this theoretical result, we propose a node importance meta learning framework (NIML) for learning and using the node importance in task. Specifically, an attention vector is constructed for each node to describe the relationship distribution of that node and its neighbors. Then we train a supervised model using this attention vector as input learn the distance between the node embedding and the same-class prototype expectation, effectively capturing the importance of that node to its class. The obtained distance will be used calculate a weighted prototype in meta learning. We conduct experiments on three benchmarks, and results validate the superiority of proposed NIML framework.
task, the prototype will get
To summarize, the main contributions of this paper are as follows: 1) We theoretically explore the influence of node importance on the lower bound of model accuracy and show the benefit of distinguishing between nodes of different importance a meta learning task. The theory conclusion can be applied to any domain, not only graph data. 2) We design sategory-irreleaan predictor to estimate the distance between node embedding and approximated prototype expectation and follow the theorem conclusion to compute weighted prototype, where we construct an attention vector as the input, which describes the distribution of neighbor relationships for given node. 3) We perform extensive experiments various real-world datasets and show the effectiveness of our approach.
RELATED WORKS
2.1 GRAPH NEURAL NETWORKS
Recent efforts develop deep neural networks for graph-sine sttucustructrred data have been largely driven by the phenomenal success of deep learning (Cao et al., [016)] CChang et al.] 2015). A large number of graph convolutional networks (GCNs) have been proposed based on the graph spectral theory. Spec- tral CNN (Bruna et al.) 2013) mimics the properties of CNN by defining graph convolution kernels at each layer form a GCN. Based on this work, researches on GCNs are increasingly getting success
in (Defferrard et al., 2016 Henaff et al. 2015 Kipf & Welling 2016). Graph Attention Networks (GAT's) (Veličković et al. (017) learn the weights of node neighbors in the aggregation process by an attention mechanism. GraphSAGE (Hamilton et al. (017) utilizes aggregation schemes to aggre- gate feature information from local neighborhoods. However, modern GNN models are primarily concerned with supi-super node classification. As result, we develop GNN framework to address the few-shot difficulties in graph data, which is one of their largest obstacles.
2.2 META LEARNING
Existing meta learning algorithms mainly fall into two categories (Hospedales et al.)
2020):
optimization- based meta learning and metric-based meta learning. Optimization- based meta learn- ing (Finn et al., 2017 Li et al. 2017; Mishra et al. 2017 Ravi & Larochelle, 2016, Mishra et al.) 2017) aims to learn an initialization of parameters in a gradient-based network. MAML (Finn et al. 2017 discovers the parameter initialization that is suitable for various few-shot tasks and can be used in any gradient descent model. MetaSGD (Li et al., 2017) advances MAML and learns the initialization of weights, gradient update direction, and learning rate in single step. Metric-based meta learning (Liu et al. 2019 Ren et al.) 22018) [Snell et al., 2017: Sung et al. 2018 /inyall et al. 2016) focuses learning a generalized metric and matching function from training tasks. In partic-
2

---

Under review as a conference paper at ICLR 2023
ular, Prototypical Networks (ProtoNet) (Snell al. 2017) embed each input into a continuous latent space and carry out classification using the similarity of an example to the representation of latent classes. Matching Networks (Vinyals et al. 2016) learn weighted nearest-neighhor classifier with attention networks. Ren et al. (2018) propose a novel extension of ProtoNet that are augmented with the ability to unlabeled examples when producing prototypes. Relation Network (Sung al.) 2018) classifies new classes by computing relation score between the query set and a few samples in each new class. Most existing meta learning methods cannot be directly applied graph data due to lack of the ability to handle node dependencies.
2.3 FEW SHOT LEARNING ON GRAPHS
Current node representation learning cannot handle unseen classes with few-shot data. Some few- shot research on graphs target on node/tink/graph classification (Mandal et al.) (022). We introduce the node classification works as follows. Meta-GNN (Zhou et al. al. (2019) extends MAML (Finn et al.) 2017) to graph data. RALE (Liu et al. (02TT) considers the dependency between nodes within task and alignment between tasks, then learns the hub-based relative and absolute location embedding.
G-Meta (Huang & Zitmik, (020)) uses local subgraph to represent the nodes given local structural information. MetaHG (Qian et al. 2021) presents a heterogeneous graph few-shot learning model for automatically detecting illicit drug traffickers
Instagram. MetaT'NE (Lan al., 2020)) com-
bines the skip-gree gra-gram mechanism with meta learning to capture the structural information with known labels and without node attributes. GFL (Yao et al. (2020) implements few-shot classification on unseen graphs for the same set of node classes. GPN (Ding et al. 2020) aggregates node importance scores and learns node embedding with few-shot attributed network based on ProtoNet. However, a theoretical analysis of the effect of node importance on meta learning is still missing.
3 PRELIMINARY
3.1 META LEARNING PROBLEM SETUP
We first introduce some notations of few-shot classification problems. Let C be the space of classes with a probability distribution т, and be the space of input data. We sample N classes -1. CN iid form as S. = {1_11'" ( )by) E X C' (=V} c to constitute the support set, where ,, E IR Ds is the dimension of input data, sMy is the class of , Thus the support set is union of S, and S = S.
form an N-way classification problem. For each class c;, k data points are sampled
S.. Besides, for each class c;, we sample m data points to form a part of query set Q in the same way. The table of notation and definition can be found in the appendix.
The core idea of meta learning algorithms is to train on various tasks sampled from distribution and then equip the model with the ability fast generalize and adapt to unseen tasks with limited labeled data. Each N-way k-shot task is sampled by the above method. In the meta-train phase, ground truth of S and Q are both known, and Q used to evaluate the performance of model updated by S. During the meta-test phase, the performance of the model will be evaluated on unseen classes. We assume each unseen class follows the same distribution T.
3.2 PROTOTYPICAL NETWORKS
ProtoNet (Snell et al. 2017) is metric-based meta learning algorithm. It learns embedding func- tion fo : R' + R" which maps input data from X to the embedding space. The M-dimensional prototype representation c; for each class c; is computed by averaging the embedding of all data points belonging to e in the support set:
c
Σ fo(szz).
Given distance function d(ær, x'), the probability a data point æ belongs to class n is calculated by Softmax function over squared distance between the embedding of x and prototype representations.
exp( cxp(-d(f((2)) c.))
Po ly = n|x) =
(2)
3

---

Under review as a conference paper at ICLR 2023
The prediction of an imput æ is computed by taking argmax over probability function (y nla=). Let ý be the prediction of an input æ, then y = arg max, (p& = =]))). The loss function for input data belongs to class is in the form of negative log- li-likkeiihodd (()) [V n x)). Thus, the parameters of embedding function fo is updated by minimizing the sum of loss functions on query sets. After the process of meta learning, the function fe has the ability embed data points belonging the same class to the same group in the embedding space RM.
4 THEORETICAL ANALYSIS
In this section, we use ProtoNet (Snell et al., 2017). a classic metric-based meta learning algorithm as an example, to theoretically explore the effect of node importance on the lower bound of model accuracy in the embedding space. The theoretical conclusion is that assigning higher weight to the data point that has closer distance to the prototype expectation will increase the lower bound of accuracy. This conclusion thus motivates us use abundant data learn the distance between node representation and prototype expectation in NIML framework.
We derive our theorem based on previous work (Cao et al. 2019). The detailed proof process is included in the Appendix A. We first define the expected accuracy R of Φ as:
R(6)= = E. arg max {po j jl x. (c] w
where 7 denotes the indicator function.
In order to simplify the theorem, we present the analysis for special case: 2-way 2-shot problem iee a binary classification with 2 nodes for each class. Note that the theorem we present can also be extended to an N-way k-shot problem. We adopt the assumption that for any input æ in each class e, the embedding vector fa(a)) follows a Gaussian distribution, where p(f((a) y = c) = N (Me, Ee)- He the expectation of (ar) when the input æ: belongs to class c, and E. the expected intra-class variance of class We denote Σ as the variance between classes.
Define importance based on prototype deviation: We want to explore the influence of differen- tiating data with different degrees of importance on the accuracy R. Since only few data points are sampled for one class to form a task, when we compute c; following Equation( [T]. there exists deviation between C and μ4: As we simplify the problem to 2-shot setting, the embedding vector of two nodes belonging to the class & can be denoted by μ - and μ + e2 respectively. We would like emphasize that the sign of 6 can be permuted freely and will have effect the theorem. After that, we naturally treat the node which has an embedding vector that is closer to the expectation μ4 as the more important node. Based on this consideration, we redefined the prototype calculation as below.
Definition 1 We change the definition of to a weighted Let and be the feature vector of two nodes belonging to class Ct The embedding of I and x2 is: fa(x)) pt Ci, and følœ2) p4i 62. Wi and w2 are weights related to fo(w)) and folaz)), which can be either trainable or pre-defined. Then,
C
W1
fa(#11
W2
S (ar2)-
(4)
W1 + W12
W1 + W2
When W1 W2 in Equation( Equation
is equivalent to Equation( 7
We would like to prove our key idea: in Definition I when wi, and e e2 have opposite relative value relationships (i.e. If wi >> W2, él < E2), which means greater weight is assigned to the more important node, this setting allows the lower bound of the model to be raised. Some theoretical results are provided below, and the whole proof included the Appendix.
Let and b denote the two classes sampled from for a task. Since all classes follow the same distribution, we only need to select one class and investigate the model aceuracy for each node inside this class and extend the results to remaining classes. Let æ be the feature of node drawn from class a, then Equation(] 3 can be written as:
R R(Φ) Eyg Ex [ a).
(5)
4

---

negatively Under review as a conference paper at ICLR 2023
Proposition 1 We can express Equation! 5 probability function::
R(Ø) x3 a) PLa,b,,, 0),
(6)
Tall where a & - llf())) -
From the one-sided Chebyshev's 's inequality, it can be derived that:
E|a]² +
R(Φ)= Pr(a > 0)
Lemma Consider space of classes C with sampling distribution T, a, b lid Let (Sa, S.
S = f1.1..... a , {,xr1...-, b k E N is the shot number, and y(a) = a. Define Co.
and tb as shown in Equation( 7.. Then,
[, (Wa pn))
(an)T(pa (Ma - puh) + (2ph + σb 2(pa) oo 0b o oa.
(8)
Eg E, =2 + of 0..
(9)
Tr/Ee ( k
Ba,[/Vrr( a. b)] s 1 k.
o 0b to 0a). Ee + 2Σ
(10)
where
a 22
Wlff
bW2b52 bwIbE1
all²
a001
b11² 6901
Lemma | provides several key components for Theorem and 0b defined by C. Ha and 0 Cb P4-
Two new variables are introduced: de
Theorem Under the condition where Lemmal 7 Thold we have:
R(Ø) (2Tr(E) + of o% )2)² fi(da, + oz(
(11)
where
f1(00, = 01) = E. +2 + of 0b + o% 0.))
- o)) Ba,s! mb) mb) (pa mb) + (2ps + To)
The lower bound of model accuracy R(d) in the form of a fraction, where we denote the denom- inator using the sum of two functions fi (o,, σb) and f2(0.,0)) We would like investigate the effect of a change in oa, Fy on R(Ø), where oa, σy are the bias between (aa Mh and C,, Cp. From the definition in Lemma []] correlated, the value of ae is closest to 0 among the three cases; If the same w is given to each e, this corresponds the case of calculating the prototype directly with the average embedding value. w and e are positively correlated, which is an opposite case from the first one, the value of az is farthest from O. We emphasize that for all classes in one episode, they have the same assignment strategy, thus a. and σ, are positively correlated.
divide o. for class into three cases: If w and
notice that о, and σ always appear in the form of a squared norm; According Theorem I thus, their positives or negatives have little effect on the result. In the numerator, of a and o a are subtractive, whereas they are additive in the denominator. After analyzing their degree and coefficients, we can reach the following conclusion: when we use the first strategy to assign values for we and 6, the lower bound of accuracy R(Ø) will be improved. negatively correlated, aa and are both closest to O, resulting in an increase in the value of lower bound. This theoretical result is exactly in line with our perception: when the value of a, and σ, are close to 0. it means that the prototype embedding is very close to its expectation Ha and μig, which is what we anticipate the prototype should achieve. Besides. from fz(0., ob), we conclude that bringing σ close to 0 will help reduce the sensitivity of the lower bound to μ4- Thus, if the distance e between given data point and prototype expectation could be predicted, the weight can be assigned by the first strategy to enhance the model accuracy.
detail, when w and are
compute with the weighted node embedding
5

---

Under review as a conference paper at ICLR 2023
5 FRAMEWORK
Inspired by theoretical results, we propose to prioritize node importance graph meta learning problems by introducing an importance score predictor. In detail, by constructing attention vector to describe the relationship distribution of given node, we and-to-end predict the distance between node embedding and protolype expectation, which is further used compute a weighted average of node embeddings as the more accurate prototype representation.
5.1 FEW-SHOT NODE CLASSIFICATION TASK
A, where is the node set, E fei, cm is the edge set. The adjacency matrix
We denote an undirected graph
Support Set
V ..,,,.., Un
{0, 1] represents the graph structure, where daj denotes the weight between node and vi. X Baxd is the feature matrix, where 2; E Rd represents the feature of node U/-
Query
We focus on solving few-shot node classification problems. Episode training is adopted in the meta-train phase as previous works (nell et al. (2017), which samples several tasks and updates parameters based on the sum the loss functions of the query sets. In problem. nodes in the graphs correspond to data points Euclidean space, and an N-way k-shot problem implies that each of the N categories has nodes. The query and support illustrated in Figure
ooo
oo0
O 000
An episode for a 3- way k-shot problem. 6 repre- sents node class, l and m de- note the number of nodes for each class in support set S and query set Q
Figure I:
5.2 NODE REPRESENTATION LEARNING
Our graph prototypical network has node representation learning component. Following the idea from ProtoNet (Snell et al. (017) introduced in Section 3, we aim to train an embedding function fo(U, a.;) that learns the node representation of u; thus prototypes representing each category the task can be computed. The node classification can then be implemented by calculating the distance between the current node and each prototype.
On graph data, the embedding function is implemented with inductive Graph Neural Network (GNN) (Hamilton et al., 2017) that learns a low-dimensional latent representation of each node. follows neighborhood combination and aggregation scheme, where each node recursively fetches information from its neighbors layer by layer. Let h' denote a node v's representation at the th step,
h h'(() AGGREGATE,, Vu N()),,
(12)
h o (W' CONCAT(H), 1-1 h,,,))
where NN (v) represents node v's (sampled) neighbors. The first step to aggregate the representa- tions of neighbor nodes in layer I into new vector h N The node representation layer 1 1 and the aggregated neighborhood representation concatenated, which is then fed to fully connected layer with nonlinear activation function a. We denote this L-layer GNN by fe(-).
5.3 NIML: NODE IMPORTANCE SPECIFIC PROTOTYPICAL NETWORK
Prototype is typically calculated by averaging node embeddings inside the support set as Equa- tion( ① shows. However, based on our theoretical findings, distinguishing nodes of different impor- tance within a category can increase the model accuracy. When the number of nodes in the task relatively small, the deviation produced by randomly sampling nodes for the prototype computation can be reduced by assigning higher weights to nodes with more importance (i.c. less distance to the prototype expectation). We therefore develop model to learn the importance which contributes to a weighted prototype computation.
of each node,
Although the theory motivates representation and the prototype expectation, it is based on the assumption that the distance is known. To overcome this obstacle, we design model which end-to-end predicts the distance.
assign weights according the distance between the node

---

Under review as a conference paper at ICLR 2023
Since numerous tasks are sampled during meta-train phase, get access to relatively abundant nodes belonging to each class. When the number of nodes in a category is large enough, the pro- totype expectation Me can be approximated by the mean embedding of same-class nodes among the whole graph, where Ae = mean(Sa (z,)), for each node u belongs to class c. Then the ground truth distance between node and its same-class prototype expectation be computed by dup = (x)) Re). Thus, theoretically speaking, we expect that the distance function can be learned with the iterative meta-training.
The next step is to decide which node information should be used to predict the distance. Directly using node embedding generated by Proto- GCN input does not meet our expectation for distance predictor. Proto-GCN maps same-class nodes to close locations in the embedding space: whereas distance predictor maps nodes of comparable importance to close distance value, so nodes of differ- ent categories may be mapped to the same location (as shown in Figure Gl Appendix A.3). Hence, is necessary design an input which containing as little label information as possible.
Due to the feature smoothing mechanism of GNN, an L-layer GNN brings the same smooth intensity for each node. Assuming we consider the homophily graph, the neighboring nodes have similar features. With equal smooth in- tensity, the similarity between a central node and its neighbors is higher than that between a marginal node and its neighbors, thus the re- lationship between a central node and its neigh- bors is more uniformly distributed.
R3 = [dyz dyz. R1.. attention sorted vector
R22
MLP
dup dife (he)) (f a is all same-class nodes us v
Figure 2: Illustration of distance model
We thus construct an attention vector ay for each node v to represent the relationship distribution, where a more uniform distribution indicates a higher node importance and a much closer distance to prototype expectation. As shown below and in Figure / each component in a, is an attention score between node u and u E (v). Note that a fixed number of neighbors are sampled for each node.
Og [awl , (o))
(13)
cap(LeakyRelU(a""W Wh,))
Ocea E (()(())
(exp[LcakyReLUUaa" [ [Whr || W wh,)))
(14)
where W is a linear transformation, is a concatenation operation. Attention coefficient is cal- culated by single-layer feed-forward neural network with LeakyReLu nonlinear activation and parameterized by a vector a, then a Softmax function is utilized for normalization.
Thus, Og is the category-irrelevant node representation that deseribes the relation distribution be- tween given node y and its neighbors. We use sorted as the input of the supervised distance predictor to avoid the effect of neighbor nodes' sampling order. For a node in class c, the distance between node representation and prototype is predicted by multi-layer supervised model:
d(ʃe (Lf)
M MT.P(SOTTED(())))
(15)
where F. is the node feature, Me = mean(f fo (xxw), for all nodes u belongs to class c. Then given the support set S. of class the importance score 8, is computed by
crrp(d([flla (
5B Eues. exp(-dl [[[[ (xx)), pc))
(16)
Prototype representation č of class can be obtained by weighted combination of embeddings,
fofozz).
(17)
MER
Then the probability p(clu) that node with feature belonging to class can be computed following the Softmax function in Equation( (2) Thus, the loss function can be defined as a sum over query set Q of negative log- pigobbbabyllty of a node v's true label c.
L -
ΣΣ
-logp(clu),
(18)
NIQ c= DEQ.
where N is the number of classes, Qn is the nodes that belong to class c in query set Q The parameters in representation network fo(-) and importance score network are then updated by SGD.

---

Under review as a conference paper at ICLR 2023
Table 1: Experiment result Reddit, Amazon-FElectronic and DBLP w.r. ACC and FI (%)
Reddit
Amazon-Eleccrrone
DBLP
Method
5-way
3-shot F1
5-way
5-shot
5-way
3-shot
5-way Acc
5-shot
5-way Acc
3-shot
5-way
5-shot
Acc
Acc
F1
Acc
F1
F1
F1
Acc
F1
Deepwalk
26.13
26.9
30.11
29.74
23.24
21.27
26.51
25.39
44.62
43.19
62.87
61.57
node2vec
27.16
26.41
31.32
29.83
24.18
24.05
27.46
26.93
41.96
40.15
58.64
58.03
GCN
38.82
38.17
45.53
44.14
54.36
54.07
56.31
55.04
58.76
57.44
69.28
69.57
GAT
39.69
39.12
47.58
46.39
53.18
52.19
56.22
56.18
60.45
59.31
70.64
68.29
ProtoNet
34.72
33.31
37.89
38. 12
53.17
52.65
58.34
57.69 69.69
37.28
36.52
43.08
44.31
MAML
29.21
26.78
32.14
33.45
54.09
54.17
59.17
58.46 46
38.72
39.43
45.63
44.81
Proto-GCN
61.43
60.74
64.08
63.15
63.18
62.49
67.32
66.93
71.35
70.72
74.89
74.66
Meta-GCN
60.81
58.32
62.73
61.21
62.17
60.47
67.16
65.08
69.58
69.24
74.67
73.19
Proto-GAT
61.49
60.82
63.67
64.27
63.27
62.51
68.30
67.96
71.86
70.67
74.33
73.17
Meta-GAT
61.45
59.34
64.06
61.48
63.86
61.55
67.97
66.74
68.62
66.94
73.38
72.17
RALE
64.73
64.42
66.35
64.27
66.82
65.39
71.48
70.05
73.17
72.46
76.95
76.47
GPN
65.37
64.28
66.57
65.19
65.69
64.32
70.31
70.24
74.69
73.82
78.58
77.43
NIML
67.51
66.90
69.67
69.33
68.93
68.24
73.85
73.19
76.53
75.32
81.37
81.09
EXPERIMENT
To verify the effectiveness of NIML on few-shot node classification problem, in this section, we first introduce the experimental settings and then present the detailed experiment results with ablation study and parameter analysis on three public datasets.
6.1 EXPERIMENT SETTINGS
We implement the experiment three public datasets: Reddit (Hamilton et al. 2017). Amazon- Electronic (McAuley et al., 2015), and DBLP (Tang et al. 2008a). Details of datasets are provided in Appendix A.2. N classes are sampled episode by episode from training classes in meta-train phase, and N novel classes from testing classes are used for evaluation. A fixed number of neighbors sampled to construct the attention vector, where zero is padded for the nodes without enough neighbors. We compare with several baselines which can be grouped into three categories.
GNNs:: We test on four graph algorithm including DeepWalk, node2vee, GCN and GAT. Deep- Walk (Perozzi et al., 2014) is done by series of random work technique, and node embeddings are learnt from the random walks. Node2vec (Grover & Leskoved (2016) is an extension from DeepWalk, which is combination of DFS and BFS random walk. GCN (Kipf & Welling 2016) is like an first-order approximation of spectral graph convolutions. GAT (Veličković et al. 2017) leverages self-attention to enable specifying different weights different nodes in neighborhood.
Meta Learning: We test on two typical meta learning algorithms without using GNN as backbone.
ProtoNet (nell et al. (2017) is a metric-based meta learning method, which learns an embedding function and use prototype to do a classification. MAML Finn al. (2017) 7) is an optimization- based meta learning method, which learns a good parameter initialization of networks.
Meta Learning GNN: We consider six works that implement GNN in meta learning framework. Proto-GCN is a baseline we design for an ablation purpose, which learns a GCN as an embedding function and uses the average value work which extends MAML to graph data by using GCN base model. Proto-GAT and Meta- GAT are baselines where the embedding function GAT. We also include two related works: RALE (Liu et al., 2021) introduces hub nodes and learns both relative and absolute location node embedding; GPN (Ding et al. 2020) learns node importance by aggregating the importance score.
prototype. Meta-GCN Zhou et al. (2019) is previous
6.2 EXPERIMENT RESULTS
Table shows the performance comparison results on 5-way 3-shot and 5-way 5-shot problems on each dataset. We report the average performance of accuracy and Fl score after ten repetitions Among the GNNs, the typical methods DeepWall and node2vec are far inferior to other methods since they rely large number of labeled data learn good node representations. GCN and GAT
8

---

Under review as a conference paper at ICLR 2023
better than the previous two methods, but they still cannot achieve satisfying performance this few-shot problem. In terms of ProtoNet and MAML, although they have shown the ability to deal with few-shot problems of Euclidean data, they are hard to handle graph data without considering the graph structure, i.e. node dependency.
Due to the incorporation of both meta-learning and graph structure, the meta-learning GNN model outperforms the previous two types of models, which demonstrates that meta learning methods can effectively deal with the problem of few samples in graph data under GNN configuration. For the four basic Meta Learning GNN model: Meta-GCN, Proto-GCN, Meta-GAT and Proto-GAT, they all achieve similar performance. Our model NIML outperforms other baselines in each case. The advantage of NIML is slightly advanced in the 5-shot case than in the 3-shot case, thanks to better refinement of prototype calculation using the importance score in the case of additional nodes.
6.3 MODEL ANALYSIS
Methods of computing importance score. We implement abla- tion study to test the performance of different methods of comput- ing importance score and provide results of four models shown in
S-way 3-hot
80
YGAR
Figure 3 Proto-GCN compute prototype directly by mean func-
75
NML
tion; GPN train a score aggregation model; Proto-GCN+GAn use GAT to learn importance score for each node. The results in- dicate that distinguishing the importance of various nodes will have significant impact the model performance, and NIML closely connected with the theory conclusion, thus makes its advantages more significant.
70
65
60
DBLP
85
Pret-6GN
S-way
80
CPN
Effect of N-way/ k-shot/ m-query. We analyze the effect of number of class N, support set size i and query set size the accuracy of three datasets. The results each dataset are depicted in Figure 4 1) As N grows, the difficulty of predicting increases, resulting in a decline in performance. 2) The accuracy increasing, and the curves tend flatten in some instances. 3) The query set size m has the least impact on model accuracy of all variables. Larger m may result in decrease in performance, which may be due to the difficulty that larger query sets bring to parameter update.
75
NML
70
65
Amskzon
DRL.P
will always increase
Figure 3: Different methods of computing importance score
82
75
80
Amnzon-E E
Reddit
77.5
30.0
82.5
Apcuracy
80
76-
78
70-
75.0
65
72.5
70.0
70
67.5
68
10
10
15
20
N-way S-ebot
5-way I-shox
5-way 5-shot m- m-query
(a) N-way
(b) k-shot
(c) m--ueery
Figure 4: Effect of support set size is on three datasets
CONCLUSION
This work begins with theoretical analysis of the effect of node importance on the model, and con- cludes that providing a greater weight to the data point whose embedding closer to the expectation of same-class prototype would enhance the lower bound of model accuracy. This theory can also be applied to other domains, not just graph. Then we propose node importance meta learning (NIML) closely based theoretical conclusion. We construct an attention vector to represent the relation- ship distribution between node and its neighbors, and train a distance predictor to learn the distance between node embedding and approximation of prototype expectation. Experiments demonstrate the superior capability of our model in few-shot node classification. NIML has the potential to be utilized in any Proto-based fhw-shot node classification framework compute prototype.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 2013.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Tianshi Cao, Mare Law, and Sanja Fidler. A theoretical analysis of the number of shots in few-shot learning. arXiv preprint 19X9:: / 2019.
Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C Aggarwal, and Thomas $ Huang. Het- erogeneous network embedding via deep architectures. In Proceedings of the 2/th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 119-128, 2015.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Kaize Ding, Jundong Li, and Huan Liu. Interactive anomaly detection on attributed networks. In Proceedings of the twelfth ACM international conference on web search and data mining, pp- 357-365, 2019.
Kaize Ding, Jianling Wang, Jundong Li, Kai Shu, Chenghao Liu, and Huan Liu. Graph proto- typical networks for few-shot learning on attributed networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 295-304, 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learnin for fast adaptation of deep networks. In International conference on machine learning, pp. 1126-1
10--113. 135. PMLR, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh V Chawla. Few-shot graph learning for molecular property prediction. In Proceedings of the Web Conference 2021, pp. 2559-2567, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structured data. arXiv preprint arXiv: 1506.05 163, 2015.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: survey, arXiv preprint arXiv:2004. 204404000 2020.
Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. Advances in Neural Information Processing Systems, 33:5862-5874, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: (60.66690000771 2016.
Lin Lan, Pinghui Wang, Xuefeng Du, Kaikai Song, Jing Tao, and Xiaohong Guan. Node classifica- tion on graphs with few-shot novel labels via meta transformed network embedding. Advances in Neurul Information Processing Systems, 33: 16520-16531, 2020.
Hung-yi Lee, Shang- Wen Li, and Ngoc Thang Vu. Meta learning for natural language processing: A survey, 2022. URL htth::tttt///rttttt org abs
Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few- shot learning. arXiv preprint / 2017.
Lu Liu, Tianyi Zhou, Guodong Long. Jing Jiang, and Chenggi Zhang. Learning to propagate for graph meta-learning. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Under review as a conference paper at ICLR 2023
Zemin Liu, Yuan Fang, Chenghao Liu, and Steven CH Hoi. Relative and absolute location em- bedding for few-shot node classification on graph. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp- 4267-4275, 2021.
Debmalya Mandal, Sourav Medya, Brian Uzzi, and Charu Aggarwal. Metalearning with graph neural networks: Methods and applications. ACM SIGKDD Explorations Newsletter, 23(2):13- 22, 2022.
Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and com- plementary products. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 785-794, 2015.
Nikhil Mishra, Mostafa Rohaninejad, Xi Chen, and Pieter Abbeel. A simple neural attentive meta- learner. arXiv preprint arXiv:1707.0314. 2017.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701-710, 2014.
Yiyue Qian, Yiming Zhang. Yanfang Ye, Chuxu Zhang, et al. Distilling meta knowledge on hetero- geneous graph for illicit drug trafficker detection on social media. Advances in Neural Information Processing Systems, 34:2691 1109911-200 1-26923, 2021.
Sachin Ravi and Hugo Larochelle. Optimization as a model for few-shot learning. 2016.
Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua Tenenbaum, Hugo Larochelle, and Richard S Zemel. Meta-learning for semi semi-supervised few-shot classifica- tion. arXiv preprint arXiv: 18.3vv8800.000 803600676, 2018
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Ad- vances in neural information processing systems, 30, 2017.
Aravind Subramanian, Pablo Tamayo. Vamsi K Mootha, Sayan Mukherjee, Benjamin L Ebert, Michael A Gillette, Amanda Paulovich, Scott L Pomeroy, Todd R Golub, Eric S Lander, et al. Gene set enrichment analysis: knowledge-basse approach for interpreting genome-wide expres- sion profiles. Proceedings of the National Academy of Sciences, 102(43):1544-11555 2005.
Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. In Proceedings of the IEEE con- ference on computer vision and pattern recognition, pp. 1199-1208, 2018
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 990-998, 2008a.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 990-998, 2008b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /710. 10903, 2017.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Zonghan WU, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1))4-24, 2020.
Huaxiu Yao, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh Chawla, and Zhenhui Li. Graph few-shot learning via knowledge transfer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 6656-6663, 2020.
Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta- gnn: On few-shot node classification in graph meta-learning. In Proceedings of the 28th ACM International Conference Information and Knowledge Management, pp. 2357-2360, 2019.
11

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1
THEORY PROOF
Table 2: Notation list
Symbol
Definition
Symbol
Definition
C
Space of classes
C
Prototype representation in RM
T
Class probability distribution
L
Embedding Function
Space of input data
Me
Expectation of inputs that belong to class Expected intra-class variance of class c Expected variance between classes Number of data points for support set Number of data points for Q
N
Number of class in a task
Le
S
Support Set
Σ
Query Set
S
Support Set of class
m
A.1.1 PROOF OF LEMMA I
Consider space of classes C with sampling distribution т. a, b bd T. Let [s. S. = (a S. f..21..--,660 ba0k) k N is the shot number, and y(æ) a. Define Co and cb as shown in Equation( Then,
E [a = (Ma 14)) (Ma - 11b) + (2 + ob 2/pa)
ob + o% - -000
(19)
E,,,, |a] Tr(EE +o 0b oa
(20)
Ea, (ar(a | a, a, S + k
Tr (re 1 k
Ee + 2
+ ab + 00 0a)
(21)
where
a W2 allac
b022622 bw1661
0e
00b
all2 + a01
800 + 100
Proof: From the definition of prototype, we have:
Ca
W1
202
(aa22)
a 10 ta 00
a1 +a W2
a
W22
(Mo E1) +
(Mo + E2)
awl
+a W2
aWl +a W2
62 U02 Cla
Ma +
o 10 + a 222
We denote the second term as oa. thus Co = Mo + Ja and T6 = 1bb + ob.
Since = |
क|| - [ - l5 ?
Ex E,, S/. (1l - 211 - [p(x)) 2
Ez, - क - E,. [(z))))) m
We denote E,,,),,)ll((z)) - कه and ((lo0())))(( - --ll as and respectively. For a random vector X, the expectation of quadratic form is ||||X||| Tr(Var(X)) E thus,
Eg E,,, (1lxx)))))l - | -
ar (V)(((())) - m)) + El((x) - क. B((((>) (5.
Since Var(X) = E[X (B[X))?
Var(ő(x) (5) E[p(z) क5 (Ø(x) m)] B(p(z) /
=E(p(x) ... [((x)) T) (Na (1( T
= Ee + Hatla T + Eg + क,5"" POoT I T 1HOH T
T
POo0" -5p1 + +
k
1
= =(1+ EE
k
12

---

Under review as a conference paper at ICLR 2023
Since B[p(2) [b] 14a cb.
1
i = (1 +
Ee + (Jaa - "5)((a (
k
Enp + (J1a (a)=(1n (Ma (a) = =1+ 1 F + a
(1
h
Thus,
11 (Ha (6) T (11 (6) 0
o..00 oe
Ma pba - 1/ (14 + 0b) - (1b + 0b)² Ha + (mb + "0)""(( + 06)
0 Ja
= Ma Ma - 2/ pb -2paa do + u/ μb 2nd + o% 0 0a
and,
Ea,s/abba (Jaa mb)² (Ha pb) + (2 + ob - 24aa)² ob o 0a
Since s., E, (1a,, we have,
Ea, [a] laa.li - ii]
= =Eabbli 2/ μb + 1b ub + 214 0. - 22-2 σb + o% 0b - 0
oa 0a.
-Tr(E) - 11" 1 2p Tr(E) + + + 2n σb 2uron + o 06 oa 0a
-Tr((E) + 0% σb o 0a
Thus, s, = 2Tr(T)rr)))))))))))))))))) + of 0 a a.. Then we do an inequality scaling the variance of a.
Var(ala, b) Var(Il((z) कह lØ(x)
- m
= Var(ll(()) क| ?) + Var((l((()))))) m 2Coo(11((x) - T5 [1)())))))))))))) m))
S Var(ll((z) क| ) + Var((l(())) m 2 + 2 Var(1o(z)) - (0)(()(()==)()vvee Varlll(( - =
S 2VVrr(l0(zz) क5 1 + 2Vr((1d(x)) =
Given the theorem: given a random vector y N(n, F), A is symmetric matrix,
Var(y Ay) = 2Tr((AE)) + 4y AEAp
we can obtain that,
Var(lø(()) - 2 = 2(1 + (Tr(()) + +411+ + + ) - (o1a-)))a "clHa (5)
Var([o(()) - = 2(1 +
* (TT()) + 4(1 $ 20022000
1
Thus,
Ea (ar 0)] s (eVol2Var((llf) c, - 2Var(lló(x) - cal 3)]
Ea, + 1 (T + 8(1 + I( - क) (Ma - - -.ull
1
=8(1 + 1
T En, (T + 1 + Ea((uo T) (Ma - ( + o r.)))
8(1 + Tr Yr + + | + 2 + of oo + :o
A. 1.2 PROOF OF THEOREM
Under the condition where Lemma 1 hold, we have:
R(Ø)= > (2Tr(E) + of 2oTo--o'0 - - o0) fi σb) + f2(0., 0b)
(22)
13

---

Under review as a conference paper at ICLR 2023
where
fi 0b) = 0b) 12Tr(Ee( 12 + + az 0b) = b -a,b - 1b) (Na pb) + (2 + ab)² )
of + 0 oa))
From the three equations in Lemma 1, we plug in the result to Equation 7 and do an in- equality scaling as shown in below. Since we know:
Proof:
Var(a) E|a²] E[a]
Ea,b la. sss
Varaaaa + Ex,s/ala, 67²) E.,.aa
Then,
2Tr(E) + o -0- a.
R(6)= 2 fi 0b) En 14) (Ma Ub) + (2pb + σb 2/ 0. o oal7
2Tr(2) + tof σb of
fi σ6) + fz(oa.
where
h( 8(1 + } Tr(Eol 1+ K.
1 )) Ee + of + 0%¹ o.))
b.'
f2(0,, σb) Ba,b [o,a mb)
"Wo ub) + (2p4 + ob) o
In the 2-way 2-shot case talked about, 2.
A.1.3 EXTEND THE ALGORITHM TO N CLASS
Let and denote the pair of query set. Let = [|((z) - क| 11(((z) =yp hence R(Ø) Pro,,,(UU, 1, > 0).
By Frechet's inequality:
R(0)
Σ
Pr(a;> (N
After plug in the inequality of R(6) in Theorem the lower bound of accuracy for N classes problem can be obtained.
A.2
EXPERIMENT DETAILS
A.2.1 DATASET DESCRIPTION
Table 3: Statistic of datasets
Dataset
# of nodes
# of edges # of features
labels
train/val/test split
Reddit
232,965
11,606,919
602
41
16/10/15
42,318
43,556
8,669
167
90/37/40
DBLP
40,672
288,270
7,202
137
80/27/30
Reddit (Hamilton et al. 2017) is social network with data sampled from Reddit, where each node a discussion post and an edge between two nodes means that the two posts are commented by the same user.
Amazon-Electronic (McAuley et al. 2015) is a product network within electronic category of Ama- zon. Nodes represent products, and edges between two products exits if they bought together.
DBLP Tang et al. 2008a) is a citation network where each node is a paper and link is the citation relationship between papers.
We record the number of nodes contained in each category in these three datasets and show the results of Reddit dataset in the histogram.
14

---

Under review as a conference paper at ICLR 2023
25000
20000
Frequency
TetsT.
666E1
15000
16221
9UI21
80EOT
10000
2965
5000
2115
10t5
0960
8269
P58P
$/99
0153
6EZy
2029
0819
9909
2966
165E
055E
20E3
1962
9787
TELZ
6E92
9722
2112
9691
3651.
1001
Class
Figure 5: Histogram Reddit dataset
A.2.2 IMPLEMENTATION DETAILS
We implement the proposed framework in PyTorch. We the number of episode 500 with an early stopping strategy. The representation network fe(.), i.c. GCN, consists of two layers with dimension size and 16, respectively. Both of them are activated with ReLU function. We train the model using Adam optimizer, whose learning rate is set to be 0.005 initially with a weight decay of 0.0005. The size of query set is be 15 for datasets. The Proto-GCN and distance predictor are both learnt during meta-train phase. We also provide anonymous Github link in the supplementary file.
A.3 TECHNICAL EXPLANATION
Figure provides an illustration of difference between the Proto-based GCN and distance predic- tor, where the bottom right figure depicts the embedding space of prototypical network and the upper right figure the distance in the embedding space between a given node and its same-class prototype. The distance is equivalent to the length of gray arrow in bottom right figure.
A.4 DIFFERENCE BETWEEN NIML AND GPN
Even though, both NIML and GPN make an effort to compute weighted prototypes, the two meth- ods are designed with different intentions. NIML starts with theoretical analysis, quantify the node importance as the distance from the node to its same-class prototype expectation and conclude that assigning higher weights to nodes with closer distance will enhance the lower bound of model accuracy. After that, NIML adopts the idea that the distribution of the relationship between given node and its neighbors can reflect the node importance and then construct an attention vector that depicts the relationship distribution input predict the distance in supervised manner, further learning the node importance. While GPN adopts a different view that assumes the importance of aggregation mechanism
node is highly correlated with its neighbor's importance and derive
15

---

Under review as a conference paper at ICLR 2023
Distance Predictor
distance
Proto-based
GCN
Figure 6: Difference between Proto-based GCN model and distance predictor: distance predictor maps node of similar importance similar distance value regardless of node category, Proto-based GCN maps same-class nodes to close locations in the embedding space.
using GAT the backbone, which has similar characteristic to message passing that relies graph homophily, We think this is the main reason why NIML outperforms GPN as shown in Table
A.5 VISUALIZATION OF RELATIONSHIP BETWEEN SCORE AND DISTANCE
In order verify whether NIML follows the theory, we visualize the relationship between score and distance in figure 7 For selected category, we calculate the embedding of five nodes with the same label belonging to the support set and visualize them in the figure together with the prototype expectation (mean of all same-class embeddings) of that category. The shade of the color represents the score. The darker the color, the higher the score, where the darkest color is the prototype. The distance between points in the figure is consistent with the distance between node embedding. Here we present three groups of visualization. From the result, we find that our algorithm always assigns higher weights closer nodes, but very strict distinctions may not be made for certain cases where the distance relatively close. Although the detail some cases is inconsistent, the overall trend is consistent with the theory.
(a)
(b)
(c)
Figure 7: Visualization of the relationship between and distance
16


Reviews:
[{"review_id": "pQF-ME5j7ZQ", "reviewer": "Reviewer_meJA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This manuscript proposes NIML to investigate the node importance in node classification meta-learning tasks. Specifically, it theoretically demonstrates the node importance between neighbors can increase the lower bound of the model accuracy. Then it proposes the node importance meta-learning architecture to learn the importance score of each node and further train a weighted prototype for meta-learning. Extensive experiments on three benchmark datasets validate the superiority of NIML.", "summary_of_the_review": "This manuscript is well-written and easy to follow. Besides, it provides a detailed theoretical analysis of the influence of node weights on model performance, which is impressive. However, due to the limited novelty of the model design, gaps between theoretical proof and the model design, and unclear clarification of the model, I would suggest this paper further enhance the model design.", "strength_and_weaknesses": "Strength:\n\n1. This work provides detailed theoretical proof to demonstrate that assigning higher weights to the samples that have closer distances to the prototype expectation will increase the lower bound of the model accuracy.\n\n2. In general, this manuscript is well written with clear motivations, detailed related works, rigorous proofs, and relatively sufficient experiments, which is easy to follow.\n\nWeakness:\n\n1. There are some gaps between the theoretical analysis and the model design. The theoretical conclusion is that higher weights of samples will increase the lower bound of the model performance, which demonstrates that the model design of existing work Proto-GCN and the proposed model NIML are solid. This work proposes the category-irrelevant node attentions and further designs the weighted prototype based on the importance scores. However, the motivations of the proposed category-irrelevant node attentions (different from Proto-GCN) and the weighted prototype are not clearly discussed in this work. \n\n2. It claims that Proto-GCN as the input does not meet the expectations for distance predictor. But it does not provide a detailed explanation. Why is it necessary to design a category-irrelevant node information input? Why Proto-GCN is not suitable for your framework? What’s the main contribution of your model design?\n\n3. The model design is rather simple and not novel enough. The main idea of the model design is to calculate the attention scores between nodes and further learn a weighted prototype. The theoretical analysis is to prove that node importance can improve the lower bound of the model performance. From my perspective, there are some gaps between the model design and the theoretical proof. You should provide the theoretical analysis of your model design and validate that your model design is better than Proto-GCN.\n\n4. The discussion of related works is comprehensive, but some discussion about related works is a little bit vague and does not show the key idea of the related works. For instance, in section 2.3, “MetaHG presents a heterogeneous graph learning model for automatically detecting illicit drug traffickers on Instagram.” The main idea of this work is to design a meta-learning model on heterogeneous graphs to address the problem of the limited labeled drug traffickers on Instagram.\n\n5. The presentations of most equations need to be revised. For instance, there should have a comma between the equation and ‘where’ (e.g., equations 3, 4,6, and 10). There should have a period after the equation (e.g., equations 1,2,5).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "loxWrr5xae0", "reviewer": "Reviewer_QBCi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "To further improve the performance of few-shot graph neural networks (GNNs), the authors investigate the effect of node importance and theoretically demonstrate the effect of node importance on the lower bound of model performance. Then, based on the proposed theory, the authors propose a new method, named Node Importance Meta-Learning (NIML), for the few-shot node classification task. The empirical study shows the effectiveness of NIML. ", "summary_of_the_review": "Although this paper introduces a clear idea, it lacks more discussions on its core idea and some key experimental results.", "strength_and_weaknesses": "Strengths:\nS1, this paper is well presented and easy to understand and follow.\nS2, although there are some assumptions, the proposed method is based on a complete theoretical foundation.\nS3, the empirical study can demonstrate the effectiveness of NIML.\n\nWeakness:\n\nW1, the theory is based on one assumption that node distance is known. To solve this issue, the authors propose a simple but straightforward solution. It would be better if authors can conduct more experiments to show its eligibility.\n\nW2, as mentioned in Sec. 1, GPN considers the importance of nodes, but it is lack theoretical analysis. The authors are expected to explain why NIML outperforms GPN in Tab. 1 since it also introduces an importance mechanism. (Sec. 6.2 misses such analysis).\n\nW3, authors may need to explain where the results of baselines come from. For example, in the original paper, the acc of GPN in 5-way 5-shot at Reddit, Amazon-Elec, and DBLP are 68.4, 70.9, and 80.1 respectively. But in this paper, these results are 66.6, 70.3, and 78.6. Besides, why another benchmark data Amazon-Clothing is discarded in this paper?\n\nW4, it seems the results of the first part in Sec. 6.3 are copied from Tab. 1. Thus, it is redundant to mention them again. Especially, these baselines use different frameworks. It may be unfair to show the effectiveness of different important mechanisms built on different frameworks. Instead, the authors can implement various mechanisms under one framework, then report the findings of existing important mechanisms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P_v4rc_lxp", "reviewer": "Reviewer_gYK6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper mainly proposes NIML, a few-shot graph node classification method to predict nodes with novel labels. The method considers the node importance among different nodes in a task and neighborhood relationships for a given node. The paper theoretically analyzes the influence of the node importance and verifies the effectiveness of NIML in the experiment part.", "summary_of_the_review": "[Reject] I reject the paper because the main idea of the paper (node importance) has already been proposed in existing works(GPN) and the experiment for the method is not sufficient enough. ", "strength_and_weaknesses": "Strength:  \n\n1.The paper theoretically searches for the node importance in few-shot graph node classification problems and demonstrates that the node importance can help the model get a higher accuracy lower bound. \n\n2.The experiment shows that the proposed NIML performs better than other baselines.\n\nWeakness:\n\n1.I think the work is lack of novelty as the work GPN[1] has already proposed to add node importance score in the calculation of class prototype and the paper only give a theoretical analysis on it.\n\n2.The experiment part is not sufficient enough. \n(1) For few-shot graph node classification problem to predict nodes with novel labels, there are some methods that the paper does not compare with. For example, G-Meta is mentioned in the related works but not compared in the experiments. A recent work TENT[2] is not mentioned in related works. As far as I know, the above two approaches can be applied in the problem setting in the paper.\n(2) For the approach proposed in the paper, there is no detailed ablation study for the functionalities of each part designed. \n(3) It is better to add a case study part to show the strength of the proposed method by an example.\n\nConcerns:\n\n1.The paper consider the node importance among nodes with same label in support set. In 1-shot scenario, how node importance can be used? I also find that the experiment part in the paper does not include the 1-shot paper setting, but related works such as RALE have 1-shot setting, why?\n\n2.The paper says that the theory of node importance can be applied to other domains. I think there should be an example to verify that conclusion.\n\n3.In section 5.3, ‘we get access to abundant nodes belonging to each class’. I do not think this is always true as there might be a class in the training set that only has few samples given the long-tailed distribution of samples in most graph datasets. \n\n\n[1] Ding et al. Graph Prototypical Networks for Few-shot Learning on Attributed Networks\n\n[2] Wang et al. Task-Adaptive Few-shot Node Classification\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KnY4g3KmQ4a", "reviewer": "Reviewer_sckx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a meta-learning approach for few shot node classification on a graph. In particular, a ProtoNet metric-based approach is adopted. However, unlike traditional ProtoNet where the class prototypes are computed from class samples in an unweighted manner, this paper assigns different importance scores to different samples. The importance scores are derived from a distance prediction function, which is in turn based on an attention mechanism. The paper also analysed the theoretical properties, in which a weighted scheme can improve the lower bound on the accuracy, compared to the unweighted scheme. Experiments are conducted to evaluate the efficacy of the proposed approach.", "summary_of_the_review": "Overall, I think this is a good paper where the strengths overweigh the weaknesses.", "strength_and_weaknesses": "Strengths:\nS1. The paper is well balanced between model design, theoretical analysis and empirical results.\n\nS2. The paper is well written and well motivated.\n\nS3. The empirical results are promising.\n\nWeaknesses:\nW1. The theoretical analysis is based on the lower bound of the accuracy, which shows that a weighted strategy can increase the lower bound. However, there is still a gap between the lower bound and the true accuracy. Without analysing how tight the bound is, an increase in the lower bound may not necessarily imply the impact on the accuracy. Some discussion on the tightness of the bound can be beneficial. \n\nW2. Ablation study on the importance score: Compared to Proto-GCN, Proto-GCN+GAT can already improve the performance quite a lot, and the marginal benefit brought by the proposed method NIML is relatively small (note the y axis starts from 60. So do we really need the proposed importance calculation? What is the computational overhead compared to just using attention as the importance score?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KbtzT4_ejYv", "reviewer": "Reviewer_aDYS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper investigates the problem of few-shot node classification on graphs. To improve the performance, the authors find that the node importance in each task is very important and should be taken into consideration when generating the prototype of each class. In particular, the authors theoretically and empirically demonstrate their viewpoints.\n", "summary_of_the_review": "In summary, this paper provides the theoretical analysis to an existing simple approach, which I think is not quite sufficient enough, and not quite novel. The experiments are not sufficient, either.", "strength_and_weaknesses": "Strengths:\n\n1. Few-shot learning on graphs is an important and hot topic.\n\n2. Theoretical evidence is welcomed to verify the necessity of considering the node importance in the calculation of the prototype.\n\n\nWeaknesses:\n\n1. One of my main concerns is that, the idea of considering node importance in each task is not novel. The authors also mentioned that some work (e.g., Ding et al., 2020) has been proposed based on this point for few-shot classification. I feel this limits the contribution of this paper. Though theoretical analysis for this point is provided, in my opinion, only theoretical analysis is not sufficient enough for a paper. A better organizational form of a paper is to propose a novel/interesting model which is associated with the corresponding theoretical analysis. \n\n2. For the calculation of neighborhood weights, why need to fix the number of neighbors? Is it possible to use all neighbors, since neighborhood sampling may result in information loss?\n\n3. Eq.(15) does not employ $\\mu_c$ as input. So why it can calculate the distance between node $v$ and center $c$?\n\n4. From my view, I feel the experiments are not quite sufficient. It is better to provide more model analysis for demonstration.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject