Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 in many real-world applications, 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 a distance metric. For example, it could lead to significantly improved classification accuracy for graph classification in many domains such as protein and drug discovery (Schölkopf et al., 2004; Dai et al., 2016), molecular property prediction (Duvenaud et al., 2015; Gilmer et al., 2017), and epidemic infectious pattern analysis (Derr et al., 2020; Oettershagen et al., 2020); it could also speed up the labeling of graph data in an active learning framework (Macskassy, 2009).
However, current graph metric learning methods (Shaw et al., 2011; Tsitsulin et 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 of temporal graphs, which may also provide insights for identifying the graph property (Isella et al., 2011). To best of our knowledge, there is currently no algorithm designed for learning metrics over temporal graphs to 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; Salakhutdinov & Hinton, 2007) have been extended to the few-shot learning by transferring the learned metric across different tasks (Vinyals et al., 2016; Snell 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 et al., 2020a;b; Qiu et al., 2020), especially for domain-specific applications such as biological graph data labeling (Zitnik 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 (Yao et al., 2020; Suo et al., 2020; Huang & Zitnik, 2020; Lan et al., 2020; Wang et al.,
2020; Ding et al., 2020), only a few nascent efforts focus on 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 observations bring three bottlenecks to present temporal graph metric learning algorithms: 1) How to learn a good metric over temporal graphs, especially on the entire graph level (i.e., accuracy 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 a distance metric only over fewer temporal graphs, which metric (as shown in Figure 1) could not only help accurately classify seen temporal 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 a few labeled examples.
Our main contributions can be summarized as:
• To describe the evolving graph in a fine-grained manner, we propose the streaming-snapshot 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 a bunch of streaming-snapshot modelled temporal graphs, we propose the prototypical temporal graph encoder to extract the lifelong evolution representation of a 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 a few examples, we introduce a meta-learner to transfer and tailor knowledge and encapsulate it with the prototypical temporal graph encoder into an end-to-end 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-art 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.

heading: 2 PRELIMINARIES
text: 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 D(xi,xj) between two input feature vectors xi ∈ Rm and xj ∈ Rm by computing D′(fθ(xi), fθ(xi)), where fθ is a learnable function mapping the input feature xi ∈ Rm into the latent feature hi = fθ(xi) ∈ Rf (Salakhutdinov & Hinton, 2007). The transformation function fθ could be linear or non-linear (Wang & Sun, 2015). When fθ is a linear function fθ(xi) = Wxi, learning a generalized Mahalanobis metric D can be expressed as follows.
D(xi,yj) = √ (xi − xj)>M(xi − xj)
= √ (xi − xj)>W>W(xi − xj)
= √ (Wxi −Wxj)>(Wxi −Wxj)
= D′(fθ(xi), fθ(xj))
(1)
where M is some arbitrary positive semi-definite matrix to be determined for the Mahalanobis metric D, and M can be decomposed as M = W>W. Then the Mahalanobis metric D on the input feature space is equivalent to the Euclidean metric D′ on the hidden feature space, such that
learning a undetermined metric D (e.g., Mahalanobis) on input feature is equivalent to learning hidden features on a fixed metric D′ (e.g., Euclidean) (Globerson & Roweis, 2005; Salakhutdinov & Hinton, 2007; Wang & Sun, 2015; Snell et al., 2017). Also, fθ can be a non-linear transformation for involving more parameters to model higher-order correlations between input data dimensions than linear transformations (Salakhutdinov & Hinton, 2007; Wang & Sun, 2015; Snell et al., 2017). 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 fθ of graphs in Euclidean space. The "goodness" is controlled by θ and we discuss how we define it in Section 3.

heading: 3 STREAMING-SNAPSHOT MODEL AND PROBLEM SETUP
text: 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(t). We use graph and network interchangeably in this paper.
Streaming-Snapshot Model. In the streaming-snapshot model, there exists two kinds of timestamps, te ∈ {0, 1, . . . , Te} denotes the edge timestamp and ts ∈ {0, 1, . . . , Ts} denotes the snapshot timestamp. To be specific, we describe a temporal graph G as a sequence of timestamped snapshots {S(ts)}Tsts=0, and each timestamped snapshot has a set of timestamped edges labeled as (vi, vj , te, ts). Note that, these two timestamps are different measures, they do not need to have the comparison relationship. In Figure 2, we provide a temporal graph example whose Te = 4 and Ts = 2.
The merits of describing the temporal graph within the streaming-snapshot 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 macroscopic view (Leskovec et al., 2005). If the input temporal graph has these two evolution patterns (i.e., edge timestamps and snapshot timestamps), our streaming-snapshot model could handle both of them simultaneously because streaming model could describe the interaction graph in a rapid and continuous manner and snapshots could compensate for the complement by modeling episodic, slowly-changing, and periodical patterns (Aggarwal & Subbian, 2014). If not, our streaming-snapshot is also viable by downgrading into a single streaming or a single snapshot model. 2) Saving computation memory. When we need to generate the graph-level embedding for a 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 a 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 et al., 2020; Xu et al., 2020; Beladev et al., 2020) that only focus on one time scale and ignore the whole lifetime evolution representation, our method can learn the lifelong evolution pattern of a temporal graph on different time scales.
As for the data structure, we store each edge as (vi, vj , te) and each snapshot adjacency matrix as A(ts) ∈ R|V (ts)|×|V (ts)|, i.e., V (ts) ⊆ V and |V (ts)| 6= |V (ts+1)| 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 ∈ Rn×m, such that the input node feature of temporal graph G is already time-aware, and n = |V | and m denotes the dimension of features. Problem Setup. With the streaming-snapshot modelled temporal graphs, our goal is to learn a parameterized metric that could accurately classify seen temporal graphs and also be smoothly
adapted to unseen temporal graphs. Based on above analysis, this problem can be solved by learning a "good" graph representation learning function fθ in Euclidean metric. To further achieve this "goodness" only with less labelled data, we formalize fθ into a bi-level meta-learning paradigm (Finn et al., 2017). Given the streaming-snapshot modelled temporal graphs and corresponding labels G̃ = {(G0, y0), (G1, y1), . . . , (Gn, yn)}, we split G̃ into G̃train for meta-training and G̃test for metatesting, where the testing set only has unseen graph labels from the training set. We shuffle the training set G̃train to sample graph metric learning tasks following a distribution Ti ∼ P (T ), where each graph metric learning task Ti is realized by a K-way N -shot temporal graph classification task based on the graph representation fθi(Gn). During each task Ti, we sample a support set G̃trainsupport and a query set G̃trainquery, such that the support set is used to train the graph representation function fθi 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., θi) to the meta-learner (i.e., Θ), then we update Θ a few times by classifying unseen temporal graphs on support set G̃testsupport, finally we report the classification accuracy of fine-tuned Θ on query set G̃testquery . The concrete objective and loss function of each graph metric learning task Ti, i.e., the "goodness", is mathematically expressed in Section 4.

heading: 4 METATAG FRAMEWORK
text: We illustrate METATAG with the proposed prototypical temporal graph encoder and meta-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., θi) in each graph metric learning task (i.e., Ti). Second, meta-learner Θ transfers the knowledge θi learned from each task Ti for the fast adaption on unseen temporal graphs classifications.

heading: 4.1 PROTOTYPICAL TEMPORAL GRAPH ENCODER
text: As stated in Eq. 1, the metric D is pair-wise. To save storage and computation complexity, learning D with labels involves the class representation concept (e.g., chunklet in (Bar-Hillel et al., 2005) and prototype in (Snell et al., 2017)), such that a sample should be close to its class representation and far from other class representations in metric D. In this paper, we follow (Snell et al., 2017) to name class representation as prototype. In each graph metric learning task Ti, 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.
Algorithm 1 Sample Time-Aware Adjacent Node Sequence N (te)v for Node v at Edge Timestamp te Input: node v at te, temporal graph G
1: for edge timestamp t < te do 2: if edge (v′, v, t) exists then B connected edges before time te 3: N (te)v appends X(v′, :)‖K(t, te) B concatenation of X(v′, :) ∈ Rm and K(t, te) ∈ Rd 4: end if 5: end for

heading: 4.1.1 MULTI-SCALE TIME ATTENTION MECHANISM
text: As shown in Figure 3, multi-scale time attention mechanism encodes the streaming-snapshot modeled temporal graph G 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 a time-aware adjacent node sequence Nv for each node v in the temporal graph G (as shown in Alg. 1), then we apply the node-level time attention mechanism to learn the time-aware embedding uv of node v from its previous connected nodes. However, self-attention mechanism has become the key component for representing sequential data (Vaswani et 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 K for our node-level time attention mechanism, which could map every observed time interval of node connections into a continuous differentiable functional domain, i.e., K : [te − l, te] → Rd. The intuition of involving K is that, suppose node v1 connects with node v2 at edge timestamp te − l, when we need to represent the node v2 at edge timestamp te, we wish the time-aware node representation u (te) v2 incorporates the temporal relationship K(te − l, te). This time function K could reflect the temporal relationship between u (te−l) v1 and u (te) v2 , and many previous work solve K with the kernel method (Zhou et al., 2013; Du et al., 2016; Xu et al., 2019; 2020; Zhang et al., 2020). For example, in (Xu et al., 2019; 2020),
K(te − l, te) = Ψ(te − (te − l)) (2)
and
Ψ(l) =
√ 1
d [cosω1(l), cosω2(l), . . . , cosωd(l)] (3)
where l = te − (te − l) denotes the input time interval, and {ω1, . . . , ωd} are learnable parameters.
After sampling the node time-aware adjacent node sequence N (te)v for node v, we next apply the node-level time attention on N (te)v to learn u (te) v by setting node v as the query node to query and aggregate attention weights from previously connected nodes in N (te)v . 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(te)v ∈ Rr can be computed as follows.
u(te)v = Attention(Q,K,V) = softmax( QK>√
r )V ∈ Rr (4)
where Q = [X(v, :)‖K(te, te)] ·WQ, K = N ·WK , and V = N ·WV . N ∈ R|N (te) v |×(m+d) is the matrix whose rows are [X(v′, :)‖K(t, te)] ∈ R(m+d) from the sequence N (te)v , and WQ,WK ,WV ∈ R(m+d)×r are three learnable weight matrices with r denoting the dimension of the time-aware node presentation vector u(te)v .
Intra-Snapshot Time Attention. After we learn the time-aware node embedding u(te)v that follows the streaming pattern based at the edge timestamp te, we also want the node in the snapshot S(ts) follows the snapshot pattern of A(ts) w.r.t snapshot timestamp ts. Therefore, intra-snapshot time attention is proposed to add constraints on node embeddings u(te)v in terms of ts timestamp by reconstructing A(ts) via a graph autoencoder.
First, we construct the snapshot feature matrix U(ts) ∈ R|V (ts)|×r whose rows are time-aware node embedding vectors. Note that, snapshot S(ts) may not have all nodes of the input temporal graph. For example, for the timestamped edge (v1, v2, te, ts), U(ts)(v1, :) = u (te) v1 and U(ts)(v2, :) = u (te) v2 . Interestingly, if there is also another edge (v1, v3, t′e, ts), we will sample the most recent edge timestamp. For example, if t′e > te, then U (ts)(v1, :) = u (t′e) v1 . The reason we adopt the latest node embedding is that, according to the sampling strategy shown in Alg.1, the latest node embedding will encode early node embeddings.
Then, with the adjacency matrix A(ts) and snapshot feature matrix U(ts), we add a reconstruction loss to learn latent intra-snapshot representation matrix H(ts) via the graph autoencoder model (Kipf & Welling, 2016). The snapshot reconstruction loss ` of the snapshot S(ts) is defined as follows.
`(A(ts),U(ts)) = ‖A(ts) − Â(ts)‖F (5)
where Â(ts) = GNNdec(H(ts))GNN>dec(H (ts)) is the reconstructed adjacency matrix computed as inner product of GNNdec(H(ts)) and its transpose, H(ts) = GNNenc(A(ts),U(ts)) ∈ R|V (ts)|×q denotes the intra-snapshot representation matrix, and ‖ · ‖F denotes the Frobenius norm. GNNenc and GNNdec are realized by GCN (Kipf & Welling, 2017) and Sigmoid function, respectively.
Given the extracted intra-snapshot representation matrix H(ts), we apply a Readout function to get the intra-snapshot representation vector h(ts) at each snapshot timestmap ts as follows.
h(ts) = Readout(H(ts)(v, :) | v ∈ {1, . . . , |V (ts)|} ∈ Rq) (6)
where Readout is a permutation-invariant function and could be instanced by many graph pooling layer models, such like Zhang et al. (2018); Ying et al. (2018).
Inter-Snapshot Time Attention. After we obtain the intra-snapshot representation vector h(ts) for each snapshot timestamp ts individually, we are not sure which one or ones should represent the temporal graph representation vector z to make it class-distinctive. To be specific, if a 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 a inter-snapshot time attention mechanism on the extracted intra-snapshot representation vectors h(ts) to obtain time attention weights for the final temporal graph representation vector z ∈ Rf . To be specific, the inter-snapshot time attention is realized through an attention pooling layer (Bahdanau et al., 2015) to get the attention weight W(ts) ∈ Rf×q for each time ts. Then, the inter-snapshot time attention is parameterized by the learned weight W(ts) as follows.
z = Ts∑ ts=0 (W(ts)h(ts)) ∈ Rf (7)

heading: 4.1.2 PROTOTYPE GENERATOR
text: Through the proposed prototypical temporal graph encoder, we could embed a temporal graph G into a representation z as shown in Figure 1. To make same class temporal graphs closer and different class graphs farther apart in the metric D, we 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 Ti, we set the support set G̃trainsupport and the query set G̃trainquery . The prototype learned on G̃trainsupport are used for predicting the class label of graphs in G̃trainquery . The prototype pk of the class k is expressed as follows.
pk = 1
Ck Ck∑ j (zj) , Gj ∈ G̃trainsupport and yj = k (8)
where Gj is the temporal graph with label yj , zj is the embedding of Gj extracted by the prototypical temporal graph encoder, and Ck denotes the number of k class temporal graphs in G̃trainsupport.
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 Θ B Θ denotes all parameters in the prototypical temporal graph encoder 2: while not done do 3: Sample task Ti ∼ P (T ) with support set G̃trainsupport and query set G̃trainquery 4: for support set of each task Ti do 5: Compute zj = fΘ(Gj) B Gj ∈ G̃trainsupport 6: Construct pk for each class k in G̃trainsupport according to Eq. 8. 7: Evaluate snapshot reconstruction loss∇Θ`Ti(fΘ) and classification loss∇ΘLTi(fΘ) 8: Compute parameter θi ← Θ− α(∇Θ`Ti(fΘ) + γ∇ΘLTi(fΘ)) 9: end for
10: Update Θ← Θ− β∇Θ ∑ Ti(`Ti(fθi) + γLTi(fθi)) B On query set G̃ train query 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 Ti to tune θi.
L =− Ck∑ j log exp(−dist(zj ,pk))∑ k′ exp(−dist(zj ,pk′)) ,
Gj ∈ G̃trainquery and yj = k
(9)
where pk denotes the k class prototype learned from G̃trainsupport, k′ denote the class other than k, dist(·) denotes Euclidean distance between two vectors, zj is the representation vector of Gj and Ck denotes the number of k class temporal graphs in the set G̃trainquery.

heading: 4.2 META-LEARNER
text: We have introduced the whole learning procedure and two loss functions (i.e., Eq. 5 and Eq. 9) for extracting knowledge θi from a single task Ti. Next, we need to break though the knowledge transfer and adaption cross tasks given only few-shot examples. Here, we introduce a meta-learner to transfer the learned knowledge θi and tailor the globally shared knowledge Θ, 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 in a bi-level paradigm (Finn et al., 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 1. Then, in each graph metric learning task Ti ∼ 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 6. In Step 8, we tune Θ to get θi for current task Ti. In Step 10, we aggregate the loss from each task Ti and fine tune Θ to end the meta-training process. After that, we can use the fine-tuned Θ as the initialized parameter in meta-testing stage for unseen graph metric learning tasks, aiming to the fast adaptation via only a few labeled samples.
The meta-testing phase of METATAG is very similar to Algorithm 2. After changing G̃trainsupport into G̃testsupport and G̃trainquery into G̃testquery, the only difference is that Step 10 directly reports the accuracy based on θi instead of getting new Θ.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 EXPERIMENT SETUP
text: Datasets. Our experiments conclude 12 temporal graph datasets from the biological domain (Fu & He, 2021), and 6 temporal graph datasets from the social network domain (Morris et 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 a protein, and timestamped edge stands for the interact of a pair of proteins. Each social network is a human-contact relation graph online and offline, where the edges between individuals stand for the online or offline contacts. The statistics of all network data are summarized in Table 1 and Table 2.
Baselines. The selection of baseline algorithms includes three factors, i.e., 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 (Borgwardt & Kriegel, 2005), Neighborhood Hash graph kernel (Hido & Kashima, 2009), Weisfeiler-Lehman Optimal Assignment kernel (Kriege et al., 2016), and Pyramid Match kernel (Nikolentzos 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., 2020), TGAT (Xu et al., 2020), and CAW (Wang et al., 2021). GL2Vec and NetLSD are static algorithms, tdGraphEmbed is a dynamic algorithm that could take a 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, we also include ProtoNet (Snell et al., 2017) and its special case k-NN method.

heading: 5.2 TEMPORAL GRAPH CLASSIFICATION
text: First, in the biological dataset, given the 12 classes we split 8 classes into the meta-training set G̃train and 4 classes into the meta-testing test G̃test. Note that G̃train and G̃test do not share any class label. In G̃train, we sample K-way N -shot graph metric learning tasks Ti ∼ P (T ), and each task has a support set G̃trainsupport and a query set G̃trainquery. Then, METATAG is trained on G̃train
based on Algorithm 2 and fine tune a few times on G̃trainsupport and report the accuracy on G̃trainquery. We shuffle G̃train and G̃test 4 times for cross-validation and report the average classification accuracy in Table 3, where our METATAG outperforms all the baseline algorithms. For example, in the 3-way 5-shot setting, our METATAG achieve 72.92% temporal graph classification accuracy, which is 5.44% higher than the second place. An intuitive explanation is that different class yeast cells (i.e., temporal graphs) has class-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 1, 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 in Appendix.

heading: 6 RELATED WORK
text: 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-learning strategy to adapt metrics across different tasks with only a 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 on learning the metric over nodes across different graphs (Yao et al., 2020; Suo et al., 2020; Huang & Zitnik, 2020; Lan et al., 2020; Wang et 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 et al., 2020; Chauhan et al., 2020). Currently, graph metric few-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,y) ≥ 0), coincidence (i.e., D(x,y) = 0 iff x = y), symmetry (i.e., D(x,y) = D(y,x)), and subadditivity (i.e., D(x,y) + D(y, z) ≥ D(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 K should be a 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., 2011). 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, 2015), the kernel is determined by learning the latent representation of substructures of input graphs.

heading: 7 CONCLUSION
text: In this paper, we first propose the streaming-snapshot 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-art baseline algorithms.
1The number of shots in the query set during meta-testing is 2.

Review summaries:
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. 

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: * 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). * 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$. * 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.  The MetaTag architecture has the following components:  * _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). - 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. * _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. * _Overall representation_ The overall representation for the time-varying graph is  weighted average using attention pooling (learnt parameter) of different snapshot representations.   This 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).   Experiments 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.  

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.