Metric Learning on Temporal Graphs via Few-Shot Examples
Authors: Dongqi Fu
Liri Fang
Ross Maciejewski
Vetle I Torvik
Jingrui He
Venue: ICLR 2022 Submitted (2022)
Keywords: Metric Learning
Few-Shot Learning
Temporal Graph

Abstract: Graph metric learning methods aim to learn the distance metric over graphs such that similar graphs are closer and dissimilar graphs are farther apart. This is of critical importance in many graph classification applications such as drug discovery and epidemics categorization. In many real-world applications, the graphs are typically evolving over time; labeling graph data is usually expensive and also requires background knowledge. However, state-of-the-art graph metric learning techniques consider the input graph as static, and largely ignore the intrinsic dynamics of temporal graphs; Furthermore, most of these techniques require abundant labeled examples for training in the representation learning process. To address the two aforementioned problems, we wish to learn a distance metric only over fewer temporal graphs, which metric could not only help accurately categorize seen temporal graphs but also be adapted smoothly to unseen temporal graphs. In this paper, we first propose the streaming-snapshot model to describe temporal graphs on different time scales. Then we propose the MetaTag framework: 1) to learn the metric over a limited number of streaming-snapshot modeled temporal graphs, 2) and adapt the learned metric to unseen temporal graphs via a few examples. Finally, we demonstrate the performance of MetaTag in comparison with state-of-the-art algorithms for temporal graph classification problems.

Under review as a conference paper at ICLR 2022
METRIC LEARNING ON TEMPORAL GRAPHS VIA FEW-SHOT EXAMPLES
Anonymous authors Paper under double-bling review
ABSTRACT
Graph metric learning methods aim to learn the distance metric over graphs such that similar graphs are closer and dissimilar graphs are farther apart. This is of critical importance many graph classification applications such as drug discovery and epidemics categorization. In many real-world applications, the graphs are typically evolving over time; labeling graph data is usually expensive and also requires background knowledge. However, state-of-the-art graph metric learning techniques consider the input graph as static, and largely ignore the intrinsic dynamics of temporal graphs; Furthermore, most of these techniques require abundant labeled examples for training in the representation learning process. To wish to learn distance metric only
address the two aforementioned problems, over fewer temporal graphs, which metric could not only help accurately categorize temporal graphs but also be adapted smoothly unseen temporal graphs. In this paper, we first propose the seaaminn-snapsht model to describe temporal graphs on different time scales. Then we propose the METATAG framework: 1) modeled temporal
learn the metric over limited number of streaming- graphs, 2) and adapt the learned metric to unseen temporal graphs via a few examples. Finally, we demonstrate the performance of METATAG in comparison with state-of-the-an algorithms for temporal graph classification problems.
INTRODUCTION
Metric learning aims to learn a proper distance metric among data items in the input space, which reflects their underlying relationship. With the prevalence of graph data many real-world appli- cations, it is of key importance to design a good distance metric function for graph data, such that the output value of the function is small for similar graphs and large for dissimilar ones. Many downstream tasks on the graph data can benefit from such distance metric. For example, it could lead to significantly improved classification accuracy for graph classification in many domains such protein and drug discovery (Schölkopf et al. 2004 Dai et al. 2016),, molecular property predic- tion (Duvenaud et al., 2013 Gilmer et al. (017)) and epidemic infectious pattern analysis (Derr et al.. 2020 Oettershagen et al. 2020)); could also speed up the labeling of graph data in active learning framework (Macskassy 2009).
However, current graph metric learning methods (Shaw et al. 2011 Tsitsulin al. 2018 Bai et al.) 2019 Li et al. 2019) Yoshida et al. 2019) assume the input graph data as static and ignore evolution patterns temporal graphs, which may also provide insights for identifying the graph property ([sella et al. 201T). To best of our knowledge, there is currently no algorithm designed for learning metrics over temporal graphs further involve evolution pattern consideration into the learned metric space. On the other hand, facing limited i.i.d. data, traditional metric learning methods (Goldberger et al.) 2004. (Salahuudinnv & Hinton 2007) have been extended the few-shot learning by transferring the learned metric across different tasks (Vinyals et al. 2016) (nell et al. 2017] Oreshkin et al.) 2018
Allen et al. 2019). Label scarcity problem also occurs in the graph research community, because labeling graph data is typically expensive and requires background knowledge (Hu al. 2020a bj Quu
ct al. 2020), especially for domain-specifti applications such as biological graph data labeling (Zimik et al. 2018 Inspired by that, graph metric learning via few-shot examples has recently attracted many nascent researchers' attention. But, the majority has been devoted to the node-level metric
learning (ao al. 2020 Suo al.) 2020 Huang & Zitnik 2020
[an al. 2020) Wang al.

---

Under review as a conference paper at ICLR 2022
2020;
Ding et al. 2020), only few nascent efforts focus the graph-level metrics (Ma et al. 2020 Chauhan et al. 2020), and all of them ignore the graph dynamics but take static graphs as input.
To wrap up. these discussed-above observa- tions bring three bottlenecks to present tempo-
ral graph metric learning algorithms: 1) How to learn a good metric over temporal graphs, especially on the entire graph level (i.e., accu- racy of metrics): 2) How to ensure the learning process only consumes less labelled temporal graph data; and 3) How to smoothly apply that learned metric to identify unseen graphs (i.e., flexibility of metrics). In this paper, we wish to learn distance metric only over fewer tempo- ral graphs, which metric (as shown in Figure I could not only help accurately classify seen tem- poral graphs during each metric learning task, but also be adapted smoothly to new metric learning tasks and converge fast (i.e., several training iterations) to classify unseen temporal graphs by consuming few labeled examples.
Graph from
Tempural Graph
Temporal Graph
Temporal
Learned Metric Temporal Graphs
t=
Figure 1: An example of metric learning several temporal graphs. In the right box, each 'x' denotes temporal graph representation, and each circle denotes a class representation.
Our main contributions can be summarized as:
To describe the evolving graph in fine-grained manner, we propose the streaming treeaming-snaphhot model that contains multiple time scales suitable for complex real-world scenarios and other merits are discussed in Section 3.
To learn the metric over bunch of greaminng-snaphhr modelled temporal graphs, we propose the prototypical temporal graph encoder extract the lifelong evolution repre- sentation of temporal graph with the proposed multi-scale time attention mechanism, such that temporal graphs from the same class share the similar encoded patterns; To make the extracted metric rapidly adapt to unseen temporal graphs with only few examples, we introduce a meta-leurner to transfer and tailor knowledge and encapsulate it with the prototypical temporal graph encoder into end-to-ens model, called METATAG.
We conduct the temporal graph classification experiments on biological network domain and social network domain, which show the effectiveness of METATAG compared with state-of-the-ar algorithms. Also, we analyze the convergence speed of METATAG during the meta-testing, the parameter sensitivity, and the ablation study of each part of METATAG.
PRELIMINARIES
Graph Metric Learning. Learning a distance metric is closely related to the feature extraction problem (Globerson & Roweis 2005 Salakhutdinov & Hinton 2007). To be specific, given any distance metric D. we can measure distance [xx,, Xy) between two input feature vectors x; E R and x, E R by computing IT> (fx(),,, so (x:)), where is learnable function mapping the input feature x; Th into the latent feature h, fo(x,) E R (Salakhutdinov & Hinton 2007). The transformation function fe could be linear or non-linear (Wang & Sun (0155). When fe is linear function fo Wx, learning a generalized Mahalanobis metrie be expressed as follows.
D(x,, = v (x: x;) TT) MM(x; -x,)
(x, x,) W W(x; Xj)
(Wxx Wxy) Wx,)
D'f((())), fo(xx))
where M is some arbitrary positive semi-definits matrix to be determined for the Mahalanobis metric D. and M can be decomposed as M WT T W. Then the Mahalanobis metric D on the input feature space is equivalent to the Fuclidean metric TY' the hidden feature space, such that
2

---

Under review as a conference paper at ICLR 2022
learning undetermined metric D (e.g.. Mahalanobis) input feature is equivalent to learning
hidden features on a fixed metric D (e.g.. Euclidean) GGloberson & Roweis 2005 Salakhutdinov & Hinton 2007 Wang & Sun 2015 Snell et al. 2017). Also, fo can be a non linar transformation for involving more parameters to model higher-order correlations between input data dimensions than linear transformations (Salakhutdinov & Hinton| 2007, Wang & Sun 2013 Snell et al. (017). Based on the above analysis, we are ready to model our graph metric learning problem: learning a "good" distance metric over pairs of graphs is to learn a "good" mapping function fe of graphs Euclidean space. The "goodness" is controlled by & and we discuss how we define it in Section 3.
non-liner
3 STREAMING-SNAPSHON MODEL AND PROBLEM SETUP
The table of symbols is summarized in Appendix. To specify, we use bold lowercase letters to denote column vectors (e.g. a). bold capital letters to denote matrices (e.g., A), and A (i,:) to denote the i-th row of matrix A. Also, we let the parenthesized superscript denote the timestamp like A (4), We use graph and network interchangeably in this paper.
Srreaming-Snapshot Model. In the arrammnggssnaphhe model, there exists two kinds of timestamps, te E {0, (0. Te} denotes the edge timestamp and t, E , Ta} denotes the snapshot timestamp. To be specific, we describe a temporal graph 9 as a sequence of timestamped snapshots (8(())? Jt,=0- and each timestamped snapshot has set of timestamped edges labeled as (#,, UJ Lep 4e (a)-
Note that, these two timestamps are different measures, they do not need to have the comparison we provide temporal graph example whose Te 4 and T' 2.
relationship. In Figure 2
The merits of describing the temporal graph within the
model include: 1) Carrying
multi-scale complex temporal information. Some social networks change rapidly in the microscopic view (Leskovec et al. 2008), while some graphs like yeast metabolic graph (Tu et al.) 2005) and repeating frames in video analysis (Li et al. 2020) change slowly in the macroscopie view (Leskoved) eet al. 2005). If the input temporal graph has these two evolution patterns (i.e., edge timestamps and snapshot timestamps). our
model could handle both of them simultancously because streaming model could describe the interaction graph in a rapid and continuous manner and snapshots could compensate for the complement by modeling episodic, howly-changing, and periodical patterns (Aggarwal & Subbian 2014). If not, our streaming treeaming-snapshot is also viable by downgrading into single streaming or single snapshot model. 2) Saving computation memory. When we need to generate the graph-level embedding for long lifetime temporal graph, we only need to load each snapshot embedding vector instead of loading every node embedding that appears in the whole temporal graph. (The detail of how to generate snapshot embedding through its relevant node embeddings is discussed in Section 4.1.1, i.e., Multi-Scale Time Attention Mechanism.) ) Beyond recent temporal graph representation learning methods (Pareja al. 2020; Xu et al.) 2020 Beladev jet al., 2020) that only focus on one time scale and ignore the whole lifetime evolution representation, method can learn the lifelong evolution pattern of temporal graph different time scales.
ty 0j 0.4
Cg
tg
C,
Cg
Figure 2: An example of a temporal graph described by the proposed streaming snaiinoo model. Each edge is labeled by two timestamps, i.e., (vi, Uy le, fx), ta E {0, 1, 2, 3, 4), and i, E (0,1,2)
As for the data structure, we store each edge as (v,, Uj te) and each snapshot adjacency matrix as A (ta) E g|v()) (x)V))))) i.c., v(t.) C V and [V(t)) き [v(+++)] is allowable. Although our method is readily designed for evolving input features according to different timestamps, for the notation clarity, we denote the node feature matrix X E R= such that the input node feature of temporal graph is already time-aware, and n |V] and denotes the dimension of features.
Problem Setup. With the streaming -naaiioo modelled temporal graphs, our goal is to learn a parameterized metric that could accurately classify seen temporal graphs and also be smoothly
3

---

Under review as a conference paper at ICLR 2022
adapted to unseen temporal graphs. Based above analysis, this problem can be solved by learning a " "good" graph representation learning function fo in Euclidean metric. To further achieve this "goodness" only with less labelled data, we formalize fo into a bi-level meta-learning paradigm (Finn) ee al., 2017). Given the streaming-snapshot modelled temporal graphs and corresponding labels G - (Gu. yo), (91, BI),..., (9n. }. we split 9 into Grrain for meta- meta-training and Grest for meta- testing, where the testing set only has unseen graph labels from the training set. We shuffle the training set Grrain to sample graph metric learning tasks following a distribution Ty ~ P(T), where each graph metric learning task Ti is realized by K-way N-shot temporal graph classification task based on the graph representation fo, (9.). During each task Tr, we sample support set Suupport and a query set Gueryy such that the support set is used to train the graph representation function So, to accurately predict the graph labels of the query set. At the meta-testing stage, we transfer the learned knowledge from each task (i.e., 0.) to the meta-learner (i.e., +), then we update O few times by classifying unseen temporal graphs on support set Support, finally we report the classification accuracy of fine-tuned è on query set Gueery. The concrete objective and loss function of each graph metric learning task Tr, i.e., the "goodness" is mathematically expressed in Section 4.
4 METATAG FRAMEWORK
We illustrate METATAG with the proposed protolypical temporal graph encoder and mela-learner. First, prototypical temporal graph encoder captures temporal graph lifelong evolution representations through the multi-scale time attention mechanism, which serves for learning the parameterized metric (i.e.. 0.) in each graph metric learning task (i.e.. T.). Second, meta-learner è transfers the knowledge 0, learned from each task T, for the fast adaption on unseen temporal graphs classifications.
(
r,=0
Snazshot Reconsorucdo Rasedion
(c,=0)
U (c==0)
(1,=0)
u1 (e:)
((pp
Weige Sthhssaa
z
((==1)
u
(1,=))
(1,1)
4,77
(te)
(te)
Allen tizn Weights
(()m2)
Connected
U (f)=
(ry=2)
Node-Iauel Time Artention
Intra Intra-Snapshot me Attantion
Inter-Snapchot Time Attention
Figure 3: The multi-scale time attention mechanism of the prototypical temporal graph encoder for encoding temporal graph representation vector z of input temporal graph G.
4.1 PROTOTYPICAL TEMPORAL GRAPH ENCODER
As stated in Eq. [ the metric ID is pair-wise, To save storage and computation complexity, learning ID> with labels involves the class representation concept (c.g., chunklet in (Bar-Hillo et al.) 2005) and prototype (Snell et al., (017)), such that sample should be close to its class representation and far from other class representations in metric ID. In this paper, we follow (Snell et al.] (017) to name class representation as prototype. In each graph metric learning task Tú, prototypical temporal graph encoder encodes class-distinctive lifelong evolution patterns within two steps. First, multi-scale time attention mechanism is responsible for learning a single temporal graph representation from different time domains, i.e., edge timestamps and snapshot timestamps. Second, prototype generator generates the prototype for the same class temporal graph representations, to ensure same class graphs share the same prototypical pattern.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Sample Time-Aware Adjacent Node Sequence No for Node Edge Timestamp te
Input: node te. temporal graph G 1: for edge timestamp < te do
2: if edge (v', v,t) exists then
> connected edges before time te P concatenation of X(v',)) E IRm and K(tt, E TRd
3: NoCe) appends (t((t))
4: end if
5: end for
4.1.1 MULTI-SCALE TIME ATTENTION MECHANISM
As shown in Figure multi-scale time attention mechanism encodes the streaming-snapshot modeled temporal graph 9 into the representation vector z through three components, i.e., node-level time attention, intra-snapshot time attention, and inter-snapshot time attention.
Node-Level Time Attention. Intuitively, this mechanism first uses edge timestamp te to learn streaming pattern of the input graph. We first need to sample time-aware adjacent node sequence N₂, for each node in the temporal graph ç (as shown in Alg. D.. then we apply the node-level time attention mechanism learn the time-aware embedding u, node from its previous connected nodes. However, self self-attention mechanism has become the key component for representing sequential data (Vaswani al. 2017), which itself could not deal with sequential information but rely on positional encoding function to map discrete position indexes into differentiable functional domain. Analogically, we need a time encoding function for our node-level time attention mechanism, which could map every observed time interval of node connections into continuous differentiable functional domain, i.e., : [te - [,te] + Rd. The intuition of involving is that, suppose node V1 connects with node U2 at edge timestamp te when need represent the node ty at
(fx) edge timestamp te. we wish the time-aware node representation u incorporates the temporal relationship K(tte t,t.). This time function K. could reflect the temporal relationship between
(c.-I) and Unz
(t.) and many previous work solve IC with the kernel method (Zhou et al. 2013 Du
Wej
ct al. 2016 Xu et al. 2019 2020; Zhang al.) (020). For example, in (Xu et al. 2019
2020).
K(le 1, (e) (le (le -))
1))
and
(1)
V [cos wi (I), cos (2) ..).................. cos wa(()]
(3)
where = (1e denotes the input time interval, and (wi are learnable parameters.
After sampling the node time-aware adjacent node sequence ((((e) for node v, we next apply the node-level time attention (te) to learn (..e)) by setting node the query node to query and aggregate attention weights from previously connected nodes in N(((e), Similar with self-attention
mechanism /Vaswani et al. 2017). we need form queries Q, keys K and values V, then the time-aware
node representation u (c) E R can be computed as follows.
QKT VER'
u (t,) Attention Q K, V) = softmax
(4)
where Q = [X(v,))|AC((e, [a)] Wo. K = N WK, and V N Wv. N N (m)+d) the matrix whose rows are [X(o',:) [)]][([ te)] E g(m+d) from the sequence N(((.) and W Q, WK, W,, Wy R(m+d)xr three learnable weight matrices with denoting the dimension of the time-aware node presentation vector u. (t+)
Intra-Snapshot Time Attention. After learn the time-aware node embedding (tte) that follows the streaming pattern based at the edge timestamp t., also want the node in the snapshot ((t)) follows the snapshot pattern of A (1x) w.r.t snapshot timestamp fg. Therefore, intra-snapshot time attention is proposed to add constraints on node embeddings u. (t.) in terms of t, timestamp by reconstructing A (t.) via graph autoencoder.
5

---

Under review as a conference paper at ICLR 2022
First, we construct the snapshot feature matrix U E R whose rows are time-aware node embedding vectors. Note that, snapshot 8t%)) may not have all nodes of the imput temporal graph.
For example, for the timestamped edge (v), v2, las (x), (vi)) = uei (fz) and (v2)) = uez (fc) Interestingly, if there is also another edge (v1, U3, le 42), we will sample the most recent edge
timestamp. For example, if l > le. then (u1,)) = u (t2) The reason we adopt the latest node embedding is that, according to the sampling strategy shown in Alg the latest node embedding will encode early node embeddings.
Then, with the adjacency matrix A (tx) and snapshot feature matrix U(C:), we add a reconstruction loss to learn latent intra-snapshot representation matrix H via the graph autoencoder model (Kipf & Welling 2016). The snapshot reconstruction loss é of the snapshot Sit,) defined as follows.
((A (1.) (lt))) | (c)
À 11
(5)
where (+)) GNN dec (H) GNNN dee (H))) is the reconstructed adjacency matrix computed as inner product of GNN deo (H (t)) and its transpose, H(()) = GNe (t.)), U(()) E gl denotes the intra-snapshot representation matrix, and || IIe denotes the Frobenius norm. GNN
and dec are realized by GCN (Kipf & Welling 2017) and Sigmoid function, respectively.
Given the extracted intra-snapshot representation matrix H we apply a Readout function to get the intra-snapshot representation vector (((,) at each snapshot timestmap t, as follows.
h (tx) = Readout H (tx) (u.:) v E (1,..../V((t)) E E?))
(6)
where Readout is permutation-invariiat function and could be instanced by many graph pooling layer models. such like Zhang et al. (2018); Ying al. (2018).
Inter-Snapshot Time Attention. After obtain the intra-snapshot representation vector h ((.) for each snapshot timestamp t, individually, we are not sure which one or ones should represent the temporal graph representation vector z to make it class-distinetive. To be specific, if certain snapshot S is shared by different classes of temporal graphs, then that snapshot is less representative and we should decrease its weight during the snapshots aggregation process, to make different class temporal graph representations different.
Therefore, we design inter-snapshot time attention mechanism on the extracted intra-snapshot representation vectors (f.) to obtain time attention weights for the final temporal graph representation vector z E R/. To be specific, the inter-snapshot time attention is realized through an attention pooling layer (Bahdanau et al. 2015) to get the attention weight (tt.) E R for each time t,. Then, the inter-snapshot time attention is parameterized by the learned weight ((t) as follows.
2 (wl))) ER
4.1.2 PROTOTYPE GENERATOR
Through the proposed prototypical temporal graph encoder, could embed a temporal graph into a representation z as shown in Figure [ To make same class temporal graphs closer and different class graphs farther apart in the metric IX, need to make same class graph representations closer to their own class prototype and farther from other class prototypes in the metric D' (i.e., Euclidean).
To this end, in each graph metric learning task T;, we set the support set suppoort and the query set Givain The prototype learned on Gtrpirrt are used for predicting the class label of graphs in Graaiy The prototype p& of the class & is expressed as follows.
Ce E(z)), Gj E Gtroin and y Ch
1
Pk
(8)
where Gj is the temporal graph with label yj. Z; is the embedding of Gj extracted by the prototypical temporal graph encoder, and C2 denotes the number of l class temporal graphs in Gtraón

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Meta-Training Process of METATAG
Input: graph metric learning task distribution P(T), step size hyperparameters and loss
balancing hyperparameter ?
1: Randomly initialize ④ @ denotes all parameters in the prototypical temporal graph encoder
2: while not done do
3: Sample task T: P(T) with support set Gtopin and query set 9
query
4: for support set of each task T; do
5:
Compute 2, - Se(G)
Gj
train support
6:
Construct Pи: for each class in Suppartt according to Eq.
7:
Evaluate snapshot reconstruction loss VoLT, (Se) and classification loss VeLT((e))
8: Compute parameter 0, + a(VolT((e)) +VVoLT((o))
9:
end for
Update + 3e. ET, +T
On query set Gquers
11:
end while
To help the the class prototype distinctive to each other, we design the temporal graph classification loss L in each graph metric learning task T; to tune 02.
C2
expl-dist (P))) C = Σ log
Σx exp(- disl pw:) Pk))
9j E G yuary and yj
where Pk denotes the & class prototype learned from Geupport denote the class other than k; dist(-) denotes Euclidean distance between two vectors, 2j the representation vector of Gj and Cj denotes the number of class temporal graphs in the set query"
4.2 META-LEARNER
We have introduced the whole learning procedure and two loss functions (i.e., Eq. and Eq. 9 for extracting knowledge 0g from a single task Tü Next, we need to break though the knowledge transfer and adaption cross tasks given only few-shot examples. Here, introduce meta-learner transfer the learned knowledge 0, and tailor the globally shared knowledge Q the theory behind is that transferring shareable knowledge could obtain the fast convergence on unseen tasks (Chauhan et al. 2020 Ma et al. 2020).
We formalize the meta-training process of METATAG a bi-level paradigm (Finn
2017). which is able to find meta-learner θ that could be fast converged in each graph metric learning task. As shown in Algorithm 2 we first randomly initialize θ in Step Then, in each graph metric learning task T, P(T), we obtain the temporal graph representation vector in Step 5 and build the class prototype for each class of the support set in Step In Step 10, we aggregate the loss from each task T, and fine tune θ to end the meta-training process. After that, we can use the fine-tuned as the initialized parameter meta-testing stage for unseen graph metric learning tasks, aiming to the fast adaptation via only few labeled samples.
Step 8, we tune θ to get 0, for current task T,
The meta-testing phase of METATAG is very similar Algorithm 2 After changing Gerpiorr into Grest and T querry into Squery the only difference is that Step 10 directly reports the accuracy based on 0g instead of getting new O
EXPERIMENTS
In this section, we test our METATAG in terms of temporal graph classifications comparing with state-of-the-art graph kernel and graph metric learning baseline algorithms. More experimental details about the implementation and the other extensive experimental results like convergence speed, parameter sensitivity, and ablation study can be found in Appendix.
7

---

Under review as a conference paper at ICLR 2022
5.1 EXPERIMENT SETUP
Datasets. Our experiments conclude 12 temporal graph datasets from the biological domain Pu & He 2.2T), and 6 temporal graph datasets from the social network domain (Morris al. 2020).
Each biological graph is a dynamic protein-protein interaction network, which describes the proteins interact of metabolic cycles of different yeast cells, where each node stands for protein, and timestamped edge stands for the interact of a pair of proteins. Each social network is a human-contact relation graph online and offlin,, where the edges between individuals stand for the online or offline contacts. The statistics of all network data are summarized in Table Table
Table 1: Statistics of Biological Temporal Graph Data
Griph
AClasses
KGngph
Toral Nodes
Tomal Edges
Iimesaapss
Graph
Emoos
Krraphs
Total Nodes
Toral Edges
Timestampe
Ueir
922
XT50
36
2356
8A3K
35
1,588
43,220
36
Gave
11
230
130000
36
1.211
33,13
36
MALDI
11
2099
76297
Yi
1,163
39,350
3,00
Lambert
Iarawwo
1,033
4826
Hazhon
145
1339
Table 2: Statistics of Social Temporal Graph Data
Graph rOnline)
Rilansss
Farghh
Tomal Nodes
Lonal Edges
Timestamps
Grapa rOllinn)
MClusss
PGrapes
Loial Nodes
Ioeal Edges
Timesiags
Intectios HighSchool
Tumbli
373
19811
74,520
180
9.418
98.066
DBLF
783
J0017
241.074
45
MDT
1310
142,00
5,376
The selection of bascline algorithms includes three factors, i.c., graph kernel or graph metric learning, few-shot learning or not few-shot learning, and static or dynamic. Graph kernel methods include: Vertex histogram kernel (Nikolentzos et al. 2019). Shortest Path kernel (Borgward) Kriegel 2005), Neighborhood Hash graph kernel (Hido Kashima 2009), Weisfeiler-Lehman
Baselines.
Optimal Assignment kernel (Kriege et al. 2016),, and Pyramid Match kernel (Nikolenzzos et al.)
2017). Graph metric learning or graph representation learning algorithms include: GL2Vec (Chen Koga 2019), NetLSD (Tsitsulin et al. 2018), tdGraphEmbed (Beladev et al. (020). TGAT (Xu et al. 2020). and CAW (Wang et al. 22221) GL2Vec and NetLSD are static algorithms, tdGraphEmbed is a dynamic algorithm that could take temporal graph as input and output graph embeddings of each snapshot, and TGAT and CAW are dynamic graph representation learning algorithms but focus on the node-level. To enable graph metric learning methods the few-shot learning capability, also include ProtoNet (Snell et al. 2017) and its special case k-NN method.
Table 3: Temporal Graph Classification Accuracy on Biological Temporal Graphs
Mcthods
way shot
way shot
way shot
way
shot
Srisseiler-Lehmane Opt
0.5025 1 0.353]
0.4625
0.3118
0.4350 1 0.2420
0,4250 1 0.2251
Graph
Vertex Histogram
0.3150 1 0.2466
0.2700
1818
0.1375 1 0.1314
0,3125 1 0.2413
Neighborhood Hash
0.4375 + 0.4058
0.4400
0.3697
0,2850 + 0.1815
0.4000 + 0.3175
Kernel
Pyramid Match
0.2500 1. 0.1971
1.133 0.2525
0,2325 0.1569
0.2950 0.2174
Shortest Path
0.2025 1 0.1477
0.2175 0.1314
0.1875 0.1325
0.1900 1 0.1329
GL2Vec KNN
0.1400 +: 0.0616
0.1925
0.0754
0.1175 +: 0.0689
0.1150 + 0.0591
NetLSD KNN
0.3600 = 0.2585
0.3650 = 0.2747
0.2000 = 0.0901
0.2625 = 0.1519
Graph
TGAT + KNN
0.2100 + 0.0817
0.1325 = 0.2217
0.1650 + 0.0387
0.0750 + 0.0208
Metric
udGraphEmbed + KNN
0,3200 + 0.1272
0.2275 - 0.1459
0.1750 + 0.0580
0.1875 + 0.0150
Learning
GL2Vec + ProtoNet
0.6083 = 0.0099
0.6541 0.0139
0.6542 = 0.1370
0.5583 = 0.1378
NetLSD ProtoNet
0.6916 0.1396
0.7145 0.139
0.6937 0.1674
0.6667 = 0.1372
TGAT + ProtoNet
0.2417 +: 0.0500
0.3083
0.0739
0.2917 + 0.1167
0.2417 1 0.0319
CAW ProtoNet
0.1496 + 0.0104
0,2113 = 0.0110
0.2404 = 0.0117
0.2842 + 0.0044
udGraphEmbed + ProtoNct
0.6562 + 0.1882
0.6791
0.1141
0.6271 = 0.1159
0.4229
+ 0.0463
MetaTaag (Ours)
0.7292 1: 0.0682
0.7917 1 0.1278
0,7062 + 0.0762
0.6833 11: 0.0589
5.2 TEMPORAL GRAPH CLASSIFICATION
First, in the biological dataset, given the 12 classes we split 8 classes into the meta-training set Etrain and 4 classes into the meta-testing test Gtest Note that ğtrain and Gleat do not share any class label. In Gtrain we sample K-way N-shot graph metric learning tasks Te ~ P(T), and each task has support set Coppport and query set Gyuerg- Then, METATAG is trained Girain
8

---

Under review as a conference paper at ICLR 2022
based on Algorithm 2 and fine tune few times on Geupio and report the accuracy on querry We shuffle Girain and Glest 4 times for cross-validation and report the average classification accuracy in Table D where our METATAG outperforms all the baseline algorithms. For example, in the 3 3-way 5-shot setting, our METATAG achieve 72.92% temporal graph classification accuracy, which 5.44% higher than the second place. An intuitive explanation is that different class yeast cells (i.e., temporal graphs) has glass-distinctive metabolic patterns (i.e., temporal patterns), capturing that pattern comprehensively is helpful in identifying class labels. Also, we observe other interesting patterns. First, graph kernel methods and KNN-based graph metric learning methods do not perform well and bear the larger standard deviation. A possible answer is that they do not have few-shot learning capability and could not transfer knowledge from seen cases to unseen cases. ProtoNet-based graph metric learning and our method enjoy the data augmentation property from the few-shot learning manner, thus they have better performance and smaller deviations. Second, our experiments shows that increasing the number of shots during the meta-training is not always the good choice for improving the performance of meta-testing[" [ because intra-class variances may be amplified (Cao et al., 2020). For the page limit, we place the experimental results of temporal graph classification on social network data Appendix.
6 RELATED WORK
Graph Metric Learning. Learning a good metric in the input feature can be transferred to learn proper graph representations in Euclidean space, then graph embedding based graph metric learning methods are proposed (Shaw et al. 2011 Bai et al., 2019 Li et al., 2019). Facing the label scarcity problem, many generic metric learning methods consider the few-shot learning or meta-lcarning strategy to adapt metries across different tasks with only few labeled sample in each task (Snell
et al. 2017] Oreshkin et al.) 2018 Allen et al. (2019). Inspired by that, some graph metric learning methods involve the few-shot learning manner, where the majority of these algorithms focus
learning the metric over nodes across different graphs (Yao et al. 2020 (uoo et al.) 2020: Huang
& Zitnik, 2020 Lan et al. 2020 Wang al., 2020 Ding et al. 2020). Only a few graph metric
learning methods learn the metric over the whole graphs to distinguish distance between graphs (Ma)
ct al. 2020; Chauhan et al., 2020). Currently, graph metric sew-shot learning methods ignore to consider the dynamics of graphs into the metric learning process. We are the first effort to involve the dynamics and temporal dependencies of input graphs into the learned metric. Graph Kernel. Given a distance metric D. it should maintain four properties: non-negativity (i.e., D)(x 2 0),
coincidence (i.c., D(x, y) = O iff = y). symmetry (i.c., (D = D(y, x)). and subadditivity (i.e., Dxx, y) + (D z) 2 IB (x, z)) (Wang & Sun 2015). While in graph kernel research, only the symmetry and non-negativity need to be hold for a kernel function, i.e., the symmetric graph kernel function IC should be positive semi-definite function /Vishwanathan et al. 2010). To measure the similarity among graphs, one category graph kernel methods explicitly define the kernel function from the graph topological view, such as Random Walk graph kernel (Vishwanathan et al.) 2010) and Weisfeiler-Lehman graph kernel (Shervashidze et al. 201T). To handle the evolving graph scenario, some methods map dynamic graphs into constant representations and then apply static graph kernel functions for dynamic node classification (Yao & Holder, 2014) and temporal graph classification (Oettershagen et al. 2020); On the other hand, some graph kernel methods learn the kernel function instead of hand-crafted designing it (Yanardag & Vishwanathan 2015) /Zhao & Wang 2019). For example, in (Yanardag & Vishwanathan (015)), the kernel is determined by learning the latent representation of substructures of input graphs.
CONCLUSION
In this paper, we first propose the dtreaming-snapstee model to describe a temporal graph, and then we propose the prototypical temporal graph encoder to capture temporal graph representation vectors. Last but not the least, we entitle the prototypical temporal graph encoder with a meta-learner into an end-to-end model, named METATAG, to transfer knowledge among different tasks for the fast adaption to unseen cases. We execute extensive experiments to show the effectiveness of our METATAG with different category state-of-the-as baseline algorithms.
'The number of shots in the query set during meta-testing is 2.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Charu Aggarwal and Karthik Subbian. Evolutionary network analysis: A survey. ACM Comput. Surv., 2014.
Kelsey R. Allen, Evan Shelhamer, Hanul Shin, and Joshua Tenenbaum. Infinite mixture prototypes for few-shot learning. In JCML., 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: neural network approach to fast graph similarity computation. In WSDM, 2019.
Aharon Bar-Hillel, Tomer Hertz, Noam Shental, and Daphna Weinshall, Learning mahalanobis metric from equivalence constraints. J. Mach. Learn. Res., 2005.
2005.
Moran Beladev, Lior Rokach, Gilad Katz, Ido Guy, and Kira Radinsky. tdgraphembed: Temporal dynamic graph-level embedding. In CIKM, 2020.
Karsten M. Borgwardt and Hans- Kriegel. Shortest-path kernels on graphs. In JCDM, 2005.
Tianshi Cao, Marc T. Law, and Sanja Fidler. A theoretical analysis of the number of shots in few-shot learning. In ICLR, 2020.
Jatin Chauhan, Deepak Nathani, and Manohar Kaul. Few-shot learning graphs via super-classes based on graph spectral measures. ICLR, 2020.
Hong Chen and Hisashi Koga. G12vec: Graph embedding enriched by line graphs with edge features. ICONIP. 2019.
Hanjun Dai, Bo Dai, and Song. Discriminative embeddings of latent variable models for structured data, In ICML, 2016.
Tyler Der. Yao Ma. Wenqi Fan, Xiaorui Liu, Charu C. Aggarwal, and Jiliang Tang. Epidemic graph convolutional network. In WSDM, 2020.
Kaize Ding, Jianling Wang, Jundong Li, Kai Shu, Chenghao Liu, and Huan Liu. Graph prototypical networks for few-shot learning on attributed networks. In CIKM, 2020.
Nan Du, Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Gomez- Rodriguez, and Le Song. Recurrent marked temporal point processes: Embedding event history vector. In KDD, 2016.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparrauure Iparraguirre, Rafacl Gómez-Bombbrele Bombarelli, Timothy Hirzel, Alán Aspuru Guzik, and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. NeurlPS, 2015.
Chelsea Finn, Pieter Abbecl, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In JCML, 2017.
Dongqi Fu and Jingrui He. DPPIN: A biological repository of dynamic protein-protiin interaction network data. CoRR, 2021.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In /CMI., 2017.
Amir Globerson and Sam T. Roweis. Metric learning by collapsing classes. In NeurlPS, 2005.
Jacob Goldberger. Sam T. Roweis, Geoffrey E. Hinton, and Ruslan Salakhutdinov. Neighbourhood components analysis. In NeurlPS, 2004.
Shohei Hido and Hisashi Kashima. A linear-time graph kernel. In ICDM, pp. 179-188, 2009.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang. Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Wei Chang, and Yizhou Sun. GPT-GNN: generative pre-training of graph neural networks. KDD, 2020b.
Kexin Huang and Marinka Zimik. Graph learning via local subgraphs. In NeurlPS, 2020.
10

---

Under review as a conference paper at ICLR 2022
Lorenzo Isella, Juliette Stchlé, Alain Barrat, Ciro Cattuto, Jean-François Pinton, and Wouter Van den Broeck. What's a crowd? analysis of face-to-face behavioral networks. Journal of theoretical biology, 2011.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, 2016.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Nils M. Kriege, Pierre-Louis Giscard, and Richard C. Wilson. valid optimal assignment kernels and applications to graph classification, In NewrIPS, 2016.
Lan, Pinghui Wang, Xuefeng Du, Kaikai Song. Jing Tao, Xiaohong Guan. Node classification on graphs with few-shot novel labels via meta transformed network embedding. In NeurlPS, 2020.
Jure Leskovec, Jon M. Kleinherg, and Christos Faloutsos. Graphs time: densification laws, shrinking diameters and possible explanations. KDD, 2005.
Jure Leskovee, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. Microscopic evolution of social networks. In KDD, 2008.
Mengtian Li, Yu-Xiong Wang, and Deva Ramanan. Towards streaming perception. In ECCV, 2020.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In JCMI,, 2019.
Ning Ma, Jiajun Bu, Jieyu Yang. Zhen Zhang, Chengwei Yao, Zhi Yu, Sheng Zhou, and Xifeng Yan. Adaptive- step graph meta-learner for few-shot graph classification. In CIKM, 2020.
Sofus A. Macskassy. Using graph-based metries with empirical risk minimization speed up active learning on networked data. In KDD, 2009.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: collection benchmark datasets learning with graphs CoRR, 2020.
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embeddings for graph similarity. AAAI, 2017.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey. CoRR, 2019.
Luiz Oettershagen, Nils Kriege, Christopher Morris, and Petra Mutzel. Temporal graph kemelss for classifying dissemination processes. In SDM, 2020.
Boris N. Oreshkin, Pau Rodríguez López, and Alexandre Lacoste. TADAM: task dependent adaptive metric for improved few-shot learning. In NeurlPS, 2018
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, B. Schardl, Charles E. Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In AAAI, 2020.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang, and Jie Tang. GCC: graph contrastive coding for graph neural network pre-training. KDD, 2020.
Ruslan Salakhutdinov and Geoffrey E. Hinton. Learning nonlinear embedding by preserving class neighbour- hood structure. AISTATS, 2007.
Bernhard Schölkopf, Koji Tsuda, and lean-Philippe Vert. Kernel Methods in Computational Biology. MIT press. 2004.
Blake Shaw, Bert Huang, and Tony Jebara. Learning a distance metric from network. In NeurlPS, 2011.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lhhman graph kernels. J. Mach. Learn, Res., 2011.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NeurIPS, 2017.
Qiuling Suo, Jingyuan Chou, Weida Zhong, and Aidong Zhang. Tadanet: Task-adaptive network for graph- enriched meta-learning. KDD, 2020.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander M. Bronstein, and Emmanuel Müller. Netlsd: Hearing the shape of graph. In KDD, 2018.
11

---

Under review as a conference paper at ICLR 2022
Benjamin P. Tu, Andrzej Kudlicki, Maga Rowicka, and Steven McKnight. Logic of the yeast metabolic cycle: Temporal compartmentalization of collular processes. Science, 2005.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention you need. In NeurlPS, 2017.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukeuoglu, and Daan Wierstra. Matching networks for one shot learning. NeurIPS, 2016.
S. V. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. J. Mach. Learn. Res., 2010.
Fei Wang and Jimeng Sun. Survey on distance metric learning and dimensionality reduction in data mining. Data Min. Knowl. Discov. 2015.
Ning Wang, Minnan Luo, Kaize Ding, Lingling Zhang, Jundong Li, and Qinghua Zheng. Graph few-shot learning with attribule matching. In CIKM, 2020.
Yanbang Wang. Yen-Ye Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. In ICLR, 2021.
Da Xu, Chuanwei Ruan, Evren Körpeaglu, Sushant Kumar, and Kannan Achan. Self-attention with functional time representation learning. In NeurlPS, 2019.
Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. In ICLR, 2020.
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In KDD, 2015.
Huaxiu Yao, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh V. Chawla, and Zhenhui Li. Graph few-shot learning via knowledge transfer. In AAAI, 2020.
Yibo Yao and Lawrence B. Holder. Scalable svm-based classification in dynamic graphs. In ICDM, 2014.
Zhitao Ying. Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hicrarchical graph representation learning with diffcrentiable pooling. In NeurlPS, 2018.
Tomoki Yoshida, Ichiro Takeuchi, and Masayuki Karasuyama. Learning interpretable metric between graphs: Convex formulation and computation with graph mining. In KDD, 2019.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to mnd-to-end deep learning architecture for graph classification. In AAAI, 2018.
Qiang Zhang, Aldo Lipani, Ömer Kirnap, and Emine Yilmaz. Self-attentive hawkes process. In JCML, 2020.
Qi Zhao and Yusu Wang. Learning metrics for persistence-baxe based summaries and applications for graph classification. In NewrlPS, 2019.
Ke Zhou, Hongyuan Zha, and Le Song. Learning triggering kemnlls for multi-dimennsonal hawkes processes. In JCML, 2013.
Marinka Zitnik, Rok Sosič, and Jure Leskovec. Prioritizing network communities. Nature communications, 2018.
12


Reviews:
[{"review_id": "RHdfey63AO", "reviewer": "Reviewer_sLfA", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "**Strengths:**\n\n- The idea of enriching a graph representation using knowledge of its temporal dynamics is quite nice. The authors split the time attention into three parts: node-level, intra-snapshot, and inter-snapshot. The node-level attention mechanism supplies temporal sensitivity to the node representations, the intra-snapshot mechanism adds in a graph autoencoder to learn how to reconstruct the adjacency matrix of a snapshot, and the inter-snapshot attention mechanism weights different snapshots according to discriminative power. The modular design is helpful in understanding how different aspects of the pipeline can be improved in future work.\n\n- The additional meta-learning module is a nice addition, and it is useful to see how to interface this module with learning dynamic graph representations.\n\n\n**Weaknesses/points to clarify:**\n\n\n- The use of $t_e \\in T_e$ is unclear from Figure 2. Could the authors please clarify how $t_e$ is obtained? Currently it seems that we have a set of edges at $t_s=0$ with $max_{t_e} = 2$, and that the new edges added at $t_s = 1$ have $t_e=3$, i.e. incremented by 1. Similarly, at $t_s=2$, the new edges are labeled with $t_e=4$. So the figure doesn't shed light into the differences between the two timescales $t_e$ and $t_s$ beyond \"increment by 1\". Section A.2 contains further mention of $t_e$ but without explanation, so I still don't fully understand how $t_e$ is generated. I think this issue can be fixed with a few lines of clarifying language.\n\n- In Section 4.1.1, where is the attention in the \"intra-snapshot time attention\" module? It seems that here we just learn how to reconstruct the adjacency matrix at each snapshot. Perhaps this can be clarified in the author response.\n\n- Possibly more seriously, I'm concerned about the **novelty** of the proposed framework. Consider references [A],[B] and the further references contained therein to attention-based models for learning dynamic graph representations. These do not appear as baselines in the current work, and in fact do not even appear as references. It seems that the meta-learning portion in the current work is new, but is that the only source of novelty? I hope the authors will be able to clarify these connections in their response.\n\n[A0] Sankar, A., Wu, Y., Gou, L., Zhang, W., & Yang, H. (2018). Dynamic graph representation learning via self-attention networks. arXiv preprint arXiv:1812.09430.\n\n[A1] Sankar, A., Wu, Y., Gou, L., Zhang, W., & Yang, H. (2020, January). Dysat: Deep neural representation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th International Conference on Web Search and Data Mining (pp. 519-527).\n\n- (A1 is an expanded version of A0)\n\n[B] Rossi, E., Chamberlain, B., Frasca, F., Eynard, D., Monti, F., & Bronstein, M. (2020). Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006.10637.", "summary_of_the_paper": "This paper introduces a methodology of graph learning for dynamic graphs, where the dynamics are encoded in the representation to obtain improved results on graph classification tasks. This framework includes a temporal graph encoder that uses attention mechanisms to generate representations, as well as a meta-learning component that ensures easy knowledge transfer. Experiments are carried out on two temporal graph datasets to show strong performance in graph classification. ", "summary_of_the_review": "I think the paper has good experimental results and that the incorporation of the meta-learning framework is useful. However, I am concerned that the authors have left out important references, and would welcome a thorough evaluation of these references (and ideally other important references contained therein) and how they compare to the current work. Currently I will lean toward reject, but welcome a discussion with the authors on the novelty of their work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "R81eL7ylOkE", "reviewer": "Reviewer_5yGt", "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": "\nThe strengths are:\n\n1. The problem considered in this paper is interesting and new. Specifically, the authors consider the graph metric learning but in the temporal setting.\n\n2. The authors proposed a new method, which includes two parts. To capture the temporal information, the key of the proposed is based on three different attentions. Previous works such as Xu et al, 2020 and Yang et. al., 2021 have demonstrated the power of time-related attention layers.\n\n3. The temporal graph classification experiments on two datasets demonstrate that the proposed method learns much better classifiers than other baseline methods.\n\nThe weaknesses are:\n\n1. The contribution of the streaming-snapshot model is not critically novel. The essential idea of the streaming-snapshot model is to combine the discrete-time dynamic graph (DTDG) and continue the time dynamic graph (CTDG) model together (see more details in [1]). The authors use both two models but may have different time granularity.\n\n2. The technical contributions are limited. The whole framework may look interesting and new but it is based on Finn et. al., 2017. The time attention layers are commonly used in temporal graphs which are also proposed in previous work.\n\n3. The experiments are limited. First of all, the run time analysis is missing from both theoretical and empirical perspectives. More explanations are needed on the results of GL2Vec + ProtoNet. The experimental setup and parameter settings are unclear.\n\n---\nMinors:\n1. It is a little bit unfair to directly use CAW and TGAT under the graph metric learning setting. What is the specific loss used for these two?\n2. Table 3, MetaTag → \\textsc{MetaTag}\n3. Why directly adding ProtoNet onto CAW and TGAT be a reasonable thing?\n4. I expect detailed experimental setups like parameter tuning in the appendix. Could you list the experimental details in the appendix?\n5. What is the scalability of this method compared with two strong baselines: 1) GL2Vec + ProtoNet and 2) tdGraphEmbed + ProtoNet? It seems that GL2Vec + ProtoNet is competitive on the social network datasets but bad on the bio-based datasets. Why is this case?\n\n[1] Kazemi SM, Goel R, Jain K, Kobyzev I, Sethi A, Forsyth P, Poupart P. Representation Learning for Dynamic Graphs: A Survey. J. Mach. Learn. Res.. 2020 Jan 1;21(70):1-73.\n\n", "summary_of_the_paper": "This paper considers the graph metric learning problem where the underlying graphs are temporal. The key idea of obtaining a higher classification accuracy is to use a bi-level meta-learning paradigm. It essential contains two parts: 1) prototypical temporal graph encoder where the model uses multi-scale time attention to capture temporal information; and 2) meta-learner where it uses bi-level paradigm proposed in Finn et al., 2017. The authors apply the proposed method to the task of graph classification on two real-world datasets. Compared with other baseline methods, MetaTag achieves better performance in terms of classification accuracy.", "summary_of_the_review": "In general, it is an interesting paper. The experimental results look promising. However, the overall quality is not strong enough for acceptance. There is space for improvement in experiments. For example, the comparison between the proposed method and baseline methods. More discussion on the experimental results is also needed.", "strength_and_weaknesses": "", "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": "NcjA0kmjtdA", "reviewer": "Reviewer_Qtrm", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The definition and example of the temporal graph are confusing. I could see that that a temporal graph consists of snapshots. I could not see why in snapshot, there are edge timestamps? Do you assume the node set fixed? Do you mean that a snapshot is also a temporal graph with edge appear and disappear at different times (a)? If yes, then I could not see it in the Figure 2. I could not see the meaning of t_e=0/1/2 in the figure. \n\nI'd be assuming (a), then the statements like \"previous methods only focus on one time scale and ignore the whole lifetime evolution representation\" are difficult to understand. I don't see why methods for temporal graphs do not take all the times of the graphs into account, i.e. do not take the whole graphs into account. \n\nThe method used in the paper is a combination of different standard methods available. There is nothing wrong with that, but it would be useful to prove the usefulness for each of these choices. \n\nOverall, I could see that the proposed method is supposed to be general with multi-scale timestamps and claim that, due to its generality, it is better than all other methods available out there. This kind of messages, in my opinion, needs to be more specific on when/why.", "summary_of_the_paper": "The paper proposed a method for metric learning for few-short examples, where each example is a temporal graph modeled with two timescales. ", "summary_of_the_review": "The problem is not clearly defined and hard to read. The method is general and claimed to be better than others due to its generality. I do not see too much novelty in the method. The results look good.  ", "strength_and_weaknesses": "", "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": "1xTIjToPhAS", "reviewer": "Reviewer_jL2u", "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": "\n# Strengths\n- First attempt to provide an end-to-end differentiable model for handling time-varying graphs \n- Addresses separate time-scales (using streaming/snapshot model)\n- Adapts and uses existing methodology where appropriate (GCNs/Readout) for snapshot representation, ProtoNets for few-shot learning, learnable time-kernels and attention for aggregating the time-aware influence of neighbouring node features into node representation. \n\n# Weaknesses\n1. The paper needs some rewriting starting with separate notions of time (streaming/snapshot) - classic stochastic theory handles this by consider $t_e$ as discrete time and ${\\cal S}^{(t)} |_{t=t_s}$ is the observation event (when we see the interactions).  As described by the authors, the snapshots model episodic, slow-changing, and periodical patterns. However, the model does not correspond to \"time elapsed\" between consecutive snapshots $(s-1), s, (s+1)$ beyond ordering. Further, it is not clear how to relate $t_s$ to $t_e$ (which is the 'real time').  I would recommend the authors call it \"k\" snapshots and not call it snapshot 'time' for clarity. \n\n2. The attention weighting across snapshots is agnostic to \"elapsed time\" meaning that few-shot learning results will work well if the time between consecutive snapshots is same across original task and new task (see point 3 below as well). \n\n\n3. The biological dataset [DPPIN, Fu and He, 2021] is not 12 separate time-varying graphs rather one large graph and a _single_ time-varying gene expression dataset from which dynamics are inferred over twelve different subgraphs. This means in the fine-tuning setting, the learnt weighting (equation 7) benefits from the fact that the temporal dynamics are representing the same underlying time-scale (snapshots in test and train correspond to real gene expression values in the same experiment at the same instant) which is why the attention weighting works well. I would be very interested in seeing how few-shot learning works when considering two different gene expression arrays for deriving the underlying dynamics.\n\n4. Would it make sense to re-order Algorithm 1 (lines 1-2) in terms of latest edge connecting to a node for a snapshot, i.e., to generate ${\\bf U}^{(t_s)}$, for each node $v$ select latest edge $(v, v', t')$ and use time-aware attention mechanism to get influence of pre-existing edges $(v, v'', t''), t'' \\le t'$  into its node representation. From a computational perspective, is only ${\\bf u}^{t'}_v$ computed or all ${\\bf u}^{t''}_v$ computed first and only the latest one selected in  ${\\bf U}^{(t_s)}$. \n\n5. (a) When computing ${\\bf U}^{(t_s)}$, suppose you have only the following edges $(v_1, v_2, 0)$, $(v_2, v_3, 1)$, $(v_3, v_4, 2)$ would the final ${\\bf U} = [ u_1^0, u_2^1, u_3^2, u_4^2]$? \n    (b) In Algorithm 1. Should $t < t_e$ be $t \\le t_e$ otherwise consider two edges $(x, y, t_e=3)$  and $(x, y', t_e=3)$ - then the influence of the other edge is missed. Further, how is this addressed in ${\\bf U}^{(t_s)}$.\n    An example in the text would clarify here.  \n\n6. In the appendix A.2, the lines \"For each temporal graph, 36 edge timestamps together describe three consecutive metabolic cycles. In each graph, we take a subgraph by extracting a interval of 5 edge timestamps every 3 edge timestamps. The subgraph shares the same class label with its original entire graph. Therefore, we have 11 temporal subgraphs per class.\" are directly copied from https://arxiv.org/pdf/2107.02168.pdf  \"in each graph, we take a subgraph by extracting the time interval of five timestamps every three timestamps. The subgraph shares the same class label with its original entire graph. Therefore, we have eleven temporal subgraphs per class.\" It is not clear to me how eleven (and not twelve) temporal subgraphs are obtained. Further, there is a mismatch in the Table 1 (#classes shown as 1) and section 5.2 Line 1 (given the 12 classes). The description of the dataset should be expanded upon and made consistent. \n\n# Minor corrections\n- Equation 1. ${\\bf y}_j$ should be ${\\bf x}_j$\n- In section 3, the authors should define a time-stamped edge $(v_i, v_j, t_e, t_s)$. My understanding is that this means an edge between nodes $v_i$ and $v_j$ that formed at \"microscopic\" time scale $t_e$ and is present whenever the $t_s^{th}$ snapshot was taken (clearly sometime after $\\max \\{ t_e | (v_i, v_j, t_e, t_s) \\in S^{(t_s)} \\}$).  \n\n- Page 9, Line 1: \"and fine tune a few times on $\\tilde{G}^{train}\\_{support}$  and report the accuracy on  $\\tilde{G}^{train}\\_{query}$\". Should this be \"fine tune a few times on $\\tilde{G}^{test}\\_{support}$ and report the accuracy on  $\\tilde{G}^{test}\\_{query}$\"? \n- On page 3, it should be made clear whether ${\\bf A}^{(t_s)}$ the snapshot adjacency matrix is just the presence of an edge at that instant (regardless of when it was created) i.e., $(i, j, t_e) \\in E^{(t_{s})} \\Rightarrow A_{ij}^{(t_s)}=1$.\n\n", "summary_of_the_paper": "This authors present a novel method for learning representations for time-varying graphs which allows for incorporating information at different time-scales using their streaming-snapshot model. The streaming-snapshot model has the following parts:\n* Each snapshot $S^{(t_{s})} = (V^{(t_{s})}, E^{(t_{s})})$ has edges of the form $(v_i, v_j, t_e) \\in E^{(t_{s})}$ where $t_e$ denotes the time at which edge was formed (and is present since then).\n* The snapshots $S^{(t_{s})}$ are at a different time-scale ($t_e$ and $t_s$ are not comparable) with the overall learning representation being ${\\cal S} \\to \\Re^f$.\n* Learning this representation is used for downstream few-shot classification task (for dynamic graphs) and is evaluated on two scenarios - time-varying biological (protein-protein interaction) networks and time-varying social networks.\n\nThe MetaTag architecture has the following components:\n\n* _Time-aware node representation_ The edge creation time $t_e$ is used to learn a time-aware node representation ${\\bf u}^t_e$ using attention-based weighting of neighbouring nodes features concatenated with a learnable time kernel (Algorithm 1).\n- The snapshot feature matrix $U^{(t_{s})}$ takes the node representation by consider the latest edge for node $u$ and using attention mechanism above to get influence of earlier edges.\n* _Intra-snapshot representation_ This is constructed using standard representation loss using a GCN-based encoder-decoder architecture followed by permutation-invariant readout to obtain vector representation for snapshot.\n* _Overall representation_ The overall representation for the time-varying graph is  weighted average using attention pooling (learnt parameter) of different snapshot representations. \n\nThis representation is used downstream for classification task (classification-head) based on prototypical approach [Snell+, 2017] resulting in overall end-to-end differentiable model with weighted average of reconstruction loss and classification loss. Further, the model allows adaptation to new tasks (with different classification labels) by fine-tuning on small test set (few-shot learning). \n\nExperiments are shown on biological and social network datasets (in appendix) showing efficacy of the approach compared to static graph representation methods as well as tdGraphEmbed (doc2vec style method for embedding temporal graphs) including augmentation with ProtoNet for few-shot learning comparison. \n", "summary_of_the_review": "The current paper addresses an important problem using a smart approach but requires significant rewriting as well as better empirical evaluation. Results on social network data are only marginally better than a much simpler approach (GL2Vec+ProtoNet) while the biological time-varying graph dataset is not actually different tasks since the underlying dynamics for all the 12 networks are learnt from a single gene-expression dataset which means train and test settings share the same underlying biological process and time-scale. I do not believe the paper is ready for publication in the present form. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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:

Meta-review: The paper proposes a new method for representation learning of time-varying graphs which uses a streaming-snapshot model to describe graphs on different time scales and meta-learning for adaption to unseen graphs. Reviewers highlighted as strengths that the paper proposes an interesting approach for modeling temporal dynamics in graphs which of interest to the ICLR community. However, reviewers raised also concerns regarding the novelty of contributions, the empirical evaluation (also with regard to related work), as well as the clarity of presentation. In addition there was no author response. All reviewers and the AC agree therefore that the paper is not yet ready for publication at ICLR at this point.
Decision: Reject