MetaGL: Evaluation-Free Selection of Graph Learning Models via Meta-Learning
Authors: Namyong Park
Ryan A. Rossi
Nesreen Ahmed
Christos Faloutsos
Venue: ICLR 2023 poster (2023)
Keywords: evaluation-free model selection
automatic graph learning
link prediction
meta-learning

Abstract: Given a graph learning task, such as link prediction, on a new graph, how can we select the best method as well as its hyperparameters (collectively called a model) without having to train or evaluate any model on the new graph? Model selection for graph learning has been largely ad hoc. A typical approach has been to apply popular methods to new datasets, but this is often suboptimal. On the other hand, systematically comparing models on the new graph quickly becomes too costly, or even impractical. In this work, we develop the first meta-learning approach for evaluation-free graph learning model selection, called MetaGL, which utilizes the prior performances of existing methods on various benchmark graph datasets to automatically select an effective model for the new graph, without any model training or evaluations. To quantify similarities across a wide variety of graphs, we introduce specialized meta-graph features that capture the structural characteristics of a graph. Then we design G-M network, which represents the relations among graphs and models, and develop a graph-based meta-learner operating on this G-M network, which estimates the relevance of each model to different graphs. Extensive experiments show that using MetaGL to select a model for the new graph greatly outperforms several existing meta-learning techniques tailed for graph learning model selection (up to 47% better), while being extremely fast at test time (∼1 sec).

Published as a conference paper at ICLR 2023
METAGL: EVALUATION-FREB SELECTION OF GRAPH LEARNING MODELS VIA META-LEARNING
Namyong Park
Ryan Rossi Adobe Research
Carnegie Mellon University namyongpe cs cmu. edu
ryross eerasss@aaaii @adobe com
Nesreen Ahmed
Christos Faloutsos
Intel Labs
Carnegie Mellon University christosécs cmu. edu
nesreen. k. awmed@inteeleee
ABSTRACT
Given a graph learning task, such as link prediction, on a new graph, how can we select the best method well its hyperparameters (collectively called model) without having to train or evaluate any model on the new graph? Model selection for graph learning has been largely ad hoc. A typical approach has been apply popular methods to new datasets, but this is often suboptimal. On the other hand, systematically comparing models on the new graph quickly becomes too costly, or even impractical. In this work, we develop the first meta-learning approach for evaluation-free graph learning model selection, called METAGI,, which utilizes the prior performances of existing methods various benchmark graph datasets to automatically select an effective model for the new graph, without any model training or evaluations. To quantify similarities across wide variety of graphs, we introduce specialized meta-graph features that capture the structural characteristics of graph. Then design G-M network, which represents the relations among graphs and models, and develop a graph-based meta-learner operating on this G-M network, which estimates the relevance of each model to different graphs. Extensive experiments show that using METAGL to select model for the new graph greatly outperforms several existing meta-learning techniques tailed for graph learning model selection (up to 47% better), while being extremely fast at test time (~/ sec).
INTRODUCTION
Given a graph learning (GI.) task, such as link prediction, for new graph dataset, how can we select the best method as well as its hyperparameters (HPs) (collectively called model) without performing any model training or evaluations on the new graph? GL has received increasing attention recently (Zhang et al. 2022), achieving successes across various applications, e.g., recommendation
and ranking (Fan et al. 2019 Park et al.) 2020), traffic forecasting (Jiang & Luo| 2021). bioinformat- ies (Su et al. 2020). and question answering (Park et al. (022).. However, GL methods continue to be developed, it becomes increasingly difficult to determine which model to use for the given graph.
Model selection (i.e., selecting method and its configuration such as HPs) for graph learning has been largely ad hoc to date. A typical approach, called "no model selection". is to simply apply popular methods new graphs, often with the default HP values. However, it is well known that there is no universal learning algorithm that performs best on all problem instances (Wolpert & Macready 1997), and such consistent model selection is often suboptimal. At the other extreme lies "naive model selection" (Fig. [b), where all candidate models are trained on the new graph, evaluated on a hold-out validation graph, and then the best performing model for the new graph selected. This approach is very costly as all candidate models are trained when a new graph arrives. Recent methods on neural architecture search (NAS) and hyperparameter optimization (HPO) of GL. methods, which we review in Section 3 adopt smarter and more efficient strategies, such as Bayesian optimization (Snock et al., 2012 Tu et al. 2019), which carefully choose a relatively small number of HP settings to evaluate. However, they still need evaluate multiple configurations of each GL method on the new graph.
Evaluation-free model selection is yet another paradigm, which aims to tackle the limitations of the above approaches by attempting to simultaneously achieve the speed of no model selection and the accuracy of exhaustive model selection. Recently, a seminal work by Zhao et al. (202I) proposed a technique for outlier detection (OD) model selection, which carries over the observed performance of

---

Published as a conference paper at ICLR 2023
Proposed
No model training/ evaluation
M
Port.Sparsity=0.00
Pert.Sparsity=
Po
best
model
ATSAC
ONC
-GB-Avgerrf
MetaGL Model
DAS
e MetaOD Bvg-Ayg
s2
ALORS
inferred model performances
MRR of Baseline Meta- Learner
new graph
0.3
(a) MetaGL infers the best model with model training/evaluttion..
+17%
Existing
train models
evaluate models
M best model
0.2
+47%
M2
+-3 %
0.1
model
M
new graph
performances
MetaGG wins
Validation
0.1
0.2
Graph G"
MRR of MetaGI.
(b) Existing model selection methods train/ovaluate multiple models. (e) MetaGL consistently performs the best.
Figure 1: (a) Given an unseen graph G and a large space M of models to search over, METAGL efficiently infers the best model M E M without having to train a single model from M on the new graph G. (b) Existing approaches, by contrast, need to train and evaluate multiple models M; E MM to be able to select the best one. (c) Given observed performance with varying sparsity levels, METAGL consistently outperforms existing meta-leamers, with up to 47% better model selection performance.
OD methods on benchmark datasets for selecting OD methods. However, it does not address the unique challenges GL model selection, and cannot be directly used to solve the problem. Inspired by this work, systematically tackle the model selection problem for graph learning, especially link prediction. We choose link prediction as a key task for graph-structured data: It has many applications (e.g., recommendation, knowledge graph reasoning, and entity resolution), and several inference and learning tasks can be cast as a link prediction problem (.d..e & Haeri (2019)). In this work, develop METAGL, the first mela-learning framework for evaluation-free selection of graph learning models, which finds an effective GL model to employ for a new graph without training or evaluating any GL model on the new graph, as Figure [ illustrates. METAGL satisfies all of desirable features for GL model selection listed in Table ! while no existing paradigms satisfy all.
The high-level idea of meta-learingg based model selection
estimate a candidate model's perfor- mance on the new graph based on its observed performances on similar graphs. Our meta- meta-learning problem for graph data presents a unique challenge of how model graph similarities, and what characteristic features (i.e., meta- (eta--catures) of graph to consider. Note that this step is often not needed for traditional meta-learning problems on non-graph data, as features for non-graph objects (e.g., location, age of users) are often readily available. Also, the high complexity and irregularity of graphs (e.g., different number of nodes and edges, and widely varying connectivity patterns among different graphs) makes the task even more challenging. To handle these challenges, we design specialized meta-graph features that can characterize major structural properties of real-world graphs.
Then to estimate the performance of candidate model given graph, METAGL learns to embed models and graphs in the shared latent space such that their embeddings reflect the graph-to-model affinity. Specifically, we design multi-relational graph called G-M network, which captures multiple types of relations among models and graphs, and develop a meta-learner operating on this G-M network, based on attentive graph neural network that is optimized to leverage meta-graph features and prior model performance into producing model and graph embeddings that can be effectively used estimate the best performing model for the new graph. METAGL greatly outperforms existing meta- learnrrs in GL model selection (p). In sum, the key contributions of this work are as follows.
Problem Formulation. We formulate the problem of selecting effective GL models an evaluation-free manner (i.e., without ever having train/evaluate any model on the new graph), To the best of our knowledge, we are the first to study this important problem.
Meta-Learning Framework and Features. We propose METAGL, the first meta-learning frame- work for evaluation-free GL model selection. For meta-learning on various graphs, we design meta- graph features that quantify graph similarities by capturing structural characteristies of graph. Effectiveness. Using METAGL for GL model selection greatly outperforms existing meta-learning techniques (up to 47% better, Fig. [T), with negligible runtime overhead test time (~~ sec).
Benchmark Data/Code: To facilitate further research on this important new problem, we release code and data at https::: // wiigituub hubb com/ Namy ark Met aGL, including performances of 400+ models on 300+ graphs, and 300+ meta- peta-graph features.
2

---

Published as a conference paper at ICLR 2023
Table I: The proposed METAGL wins features in comparison to existing graph learning (GL) model selection (MS) paradigms, all of which fail to satisfy some of desirable properties for GL MS.
GL Model Selection (MS) Paradigms
Graph HPO/NAS
No model
Naive model
METAGL
AutoNE. AGNN:
selection selection (Fig.
3nd Fig. OOurs, Fig.
Desiderata for Graph Leaming (GI.) MS
See See
Evaluation-Fra free GL model selection Cupable of MS from among multiple GL algorithms
Cupitalizing on graph similarities for GL MS
Estimating model performance based on past observations
2 PROBLEM FORMULATION
Given a new unseen graph, our goal is to select the best model from a heterogeneous set of graph learning models, without requiring any model evaluations and user intervention. In comparison to traditional meta-learning problems where a model denotes a single method and its hyperparameters, model in the graph meta-learning problem is more broadly defined be
model M {ggaph embedding method, hyperparameters), (predictor, hyperparameters)),
as graph learning tasks usually involve two steps: (1) embedding the graph using graph representation learning method, and (2) providing node embeddings to the predictor of a downstream task like link prediction. Both steps require learning a method with specific hyperparameters. Thus, there can be many models with the same embedding method and predictor, which have different hyperparameters. Also, the M of models may contain many different graph representation learning methods (e.g.. node2vec (Grover & Leskovec, 2016), GraphSAGE (Hamilton et al. 2017). DeepGL. (Rossi et al. 2020 to name few), as well multiple task sssk-specffie predictors, making M heterogeneous.
Given training meta-corpus of n graphs g = {G and m models M {M}}ī= for GL tasks, we derive performance matrix P _ where P.j is the performance (e.g., accuracy) of model on graph Our meta-learning problem for evaluation-free GL model selection is defined as follows.
Problem 1 (Evaluation-FFree Graph Learning Model Selection).
Given
an unseen test graph Gusd & g, and potentially sparse performance matrix P E R= of m heterogeneous graph learning models .M {M,....,MA. Mm) on n graphs g (G1....,
Select
the best model M M to employ on Gust without evaluating any model in M on Grest-
RELATED WORK
majority works on GL focus on developing new algorithms for certain graph tasks and applica- tions (Xia al. 2021 Zhang al. 2022). In comparison, there exist relatively few recent works that address the GL model selection problem (Zhang et al., 2021). They mainly focus on neural architecture search (NAS) and hyperparameter optimization (HPO) for GL models, especially graph neural networks (GNNs). Toward efficient and effective NAS and HPO in GL, they investigated several approaches, such Bayesian optimization (AutoNE by Tu al. (201)), ), reinforcement learn- ing (GraphNAS by Gao et al. (2020), AGNN by Zhou et al. (2019). PNNicy-GNN by Lai et al. (2020)). hypernets (ST-GCN by Zhu et al. (20TT)) and evolutionary algorithms (Bu et al. (2021). 1) as well as techniques like subgraph sampling (AutoNE by Tu et al. (2019), ). graph coarsening (JITuNE by Guo let al. (202T). ) and hierarchical evaluation (HESGA by Yuan et al. (20TT). However, as summarized in Table I these methods cannot perform iiltuuatioo-free GL model selection (Problem []]. since they need to evaluate multiple configurations of each GL method on the new graph for model selection. Further, they are limited to finding the best configuration of a single algorithm, and thus cannot select a model from a heterogeneous model set M with various GL models, as Problem T requests. An earlier work on GNN design space You et al. 2020) is somewhat relevant, proposes approach to quantify graph similarities, which can be used to find an observed graph similar to the test graph, and select model that performed best on it. However, their approach evaluates a of anchor models on all graphs, and computes similarities between two graphs based on anchor models' performance on them. As it needs to run anchor models on the new graph, it is inapplicable Problem [ For the first time, METAGI. enables evaluation model selection from heterogeneous set of GL. models.
3

---

Published as a conference paper at ICLR 2023
Meta-Graph Features
MetaGL Model f
G
M *
best model
new graph
inferred performances
meta-graph features
Figure 2: Given graph G, METAGL extracts meta meta-graphe graph features, and applies a meta- model to them, which efficiently infers the best model M E EM for G, with no model evaluation.
FRAMEWORK
In this section, we present METAGL, our meta-learning based framework that solves Problem I by leveraging prior performances of existing methods. METAGL consists of two phases: (1) offline meta-training phase (Section 4.1 that trains a meta-learner using observed graphs g and model performances P. and (2) online model prediction phase (Section 4.2). which selects the best model for the new graph. A summary of notations used in this work is provided in Table 3 in the Appendix.
4.1 OFFLINE META-TRAINING TRAINING
Meta-learning leverages prior experience from related learning tasks do better job on the new task. When the new task is similar to some historical learning tasks, then the knowledge from those similar tasks can be transferred and applied to the new task. Thus effectively capturing the similarity between an input task and observed ones is fundamentally important for successful meta-learning. In meta-learning, the similarity between learning tasks is modeled using meta-features, i.e., characteristic features of the learning task that can be used to quantify the task similarity.
Meta- Features. Given the graph learning model selection problem (where new graphs correspond to new learning tasks), METAGL captures the graph similarity by extracting meta-graph features such that they reflect the structural characteristies of a graph. Notably, since graphs have irregular structure, with different number of nodes and edges, METAGL designs meta-graph features to be of the same size for any arbitrary graph such that they can be easily compared using meta- graap features. We use the symbol m Rd denote the fixed-size meta-graph feature vector of graph G. We defer the details of how METAGL computes m to Section
Model Performance Estimation. To estimate how well a model would perform on a given graph, METAGL represent models and graphs in the latent k-dimensional space, and captures the graph- to-model affinity using the dot product similarity between the two representations hG, and hM, of the i-th graph G; and j-th model M,. respectively, such that Pij ~ (hG., hM,) where Pij is the performance of model M, on graph G.. Then to obtain the latent representation h, we design a learnable function f(-) ) that takes in relevant information on models and graphs from the meta- graph features m and the prior knowledge (i.e., model performances and observed graphs G). Below in this section, we focus on the inputs to the function f(-), and defer the details of f((-) to Section 4.4
We first factorize performance matrix P into latent graph factors U Bank and model factors V m and take the model factor V, E IR (the j-th row of V) as the input representation of model My. Then, METAGL obtains the latent embedding hM, of model Mj by hM, = f(V;) 3). For graphs, more information is available since graph factors U. However, while we have the same number of models during training and inference, observe new graphs during inference, and thus cannot obtain the graph factor Utest for the test graph as for the train graphs since matrix factorization (MF) is transductive by construction (i.e., existing models' performance on the test graph needed get latent factors for the test graph directly via MF). To handle this issue, we learn an estimator Φ IRd + R& that maps the meta-graph features m into the latent factors of meta-train graphs obtained via MF above (i.e., for graph G, with m, ((m) = Ü, R U.) and use this estimated graph factor. We then combine both inputs ( (m;; ó (m)) Rd+ and apply linear transformation to make the input representation of graph G; to be of the same size as that of model My, obtaining the latent embedding of graph G; to be he. = f(W m: ((m))) where W E R R is weight matrix. Thus in METAGL, the performance Piş of model M, on graph G; with meta-graph features m estimated as
have both meta-graph features and meta-train
Pij 2 P.j = (J [m; (())),
Meta- Learning Objective. For tasks where the goal is to estimate real values, such as accuracy, the mean squared error (MSE) is typical choice for the loss function. While MSE is easy to optimize and
4

---

Published as a conference paper at ICLR 2023
effective for regression, it does not directly take the ranking quality into account. By contrast, in problem setup, accurately ranking models for each graph dataset is more important than estimating (oobuessfocuees
the performance itself, which makes MSE suboptimal choice. In particular, finding the model with the best performance on the given graph. Therefore, we consider rank-based learning objectives, and among them, we adapt the top-1 probability the proposed Problem a follows. Let P, E R be the i-th row of P (i.e. estimated performance of all m models on graph G.). Given P., the top-1 probability Peopl (j) of j-th model M, in the model set M is defined to be
((p)) Piop1 (i) _k=1 T (Pik)
P.
exp(p.))
2k=1 exp(pix)
where π7 iT-) is increasing, strictly positive function, which we define to be exponential function.
Theorem 1 (Cao al. (2007)). Given the performance P. of all models graph Gi, Propl (i) represents the probability of model Mj to be ranked at the top of the list (i.e., all models in M).
Px
Top-1 probabilities Propi (j) for all j = 1,...,m. m form a probability distribution over m models.
Based on Theorem I we obtain two probability distributions by applying top-1 probability to the true performance P, and estimated performance P, of m models, and optimize METAGL such that the distance between the two resulting distributions gets decreased. Using the cross entropy as the distance metric, we obtain the following loss over all n meta-train graphs G:
L(P, - Σ>
-
P. Peop1 (i) log (phops (i)
(4)
When P is sparse, meta-training can be performed via slightly modified Eqs. and in App. G.2 4.2 ONLINE MODEL PREDICTION
In the meta veta-training phase, METAGL learns estimators f()) and Φ(-). as well as weight matrix W and latent model factors V. Given new graph Grest, METAGL first computes the meta-graph features Must E IRd as we discuss in Section 4.3 Then Maest is regressed to obtain the (approximate) latent graph factors Ürest Φ (M E R Recall that the model factors V learned in the meta-training stage can be directly used for model prediction. Then model Mj's performance on test graph Grest. can be estimated by applying Equation (2) with Mues and di Muest. ). Finally, the model that has the highest estimated performance is selected by METAGL as the best model M iee.
M
arg max (f(W(ma))))) [Mrest o )I), f(Vs))
MyEM
Note that model selection using Equation depends only on the meta-graph features meett of the test graph and other pretrained estimators and latent factors that METAGL lermedd in the meta-training phase. As no model training or evaluation is involved, model prediction by METAGL much faster than training and evaluating different models multiple times, our experiments show in Section 5.4 Further, model prediction process fully automatic since does not require users to choose or fine-tune any values at test time. Figure 2 shows an overview of the model prediction process, and Algorithm D in the Appendix lists steps for offline meta-training and online model prediction.
4.3 STRUCTURAL META-GRAPII FEATURES
Input Graph G
Meta-graph features are a crucial component of our meta- learning approach METAGL since they capture important struc- tural characteristics of an arbitrary graph. Meta- grapa features enable METAGL. to quantify graph similarities, and utilize prior experience with observed graphs for GL. model selection. is important that a sufficient and representative set of meta-graph features are used to capture the important structural properties of graphs from wide variety of domains, including biological, technological, information, and social networks to name a few.
y
yb
122
+
Meta- Graph
Σ
Features m
In this work, we not able leverage the commonly used simple statistical meta-feature used by previous work on model selection-basee meta-learning, as they cannot be used directly
Figure 3: Meta-graph features in METAGL are derived in two steps. See Section 4.3 for details.
5

---

Published as a conference paper at ICLR 2023
over irregular and complex graph data. To address this problem, introduce the notion of meta- meta-graph features and develop general framework for computing them on any arbitrary graph.
Meta-graph features in METAGL derived in two steps, which is shown in Figure 3 First, apply a set of structural meta-feature extractors V/- = {wi...., 4g to the input graph G. obtaining (G() { | (G),.... (G)) Applying // V G yields vector
distribution of values for the nodes (or edges) in the graph, such as degree distribution and PageRank scores. That is, in Figure 3 x/1 can be a degree distribution, t/2 can be PageRank scores of all nodes, and so on. Specifically, we use both local and global structural feature extractors. To capture the local structural properties around node or an edge, we compute node degree, number of wedges (i.e., path of length 2), triangles centered at each node, and also frequency of triangles for every edge. To capture global structural properties of a node, we derive eccentricity, PageRank score, and k-core number of each node. Appendix D summarizes meta-feature extractors used in this work.
Let db denote the local structural extractors for nodes. Given a graph G; (V;; E,) and 1h we obtain an VVll-dimeniional node vector (G,). Since any two graphs G. and G₁ are likely to have a different number of nodes and edges, the resulting structural feature matrices (G,)) and (G,)) for these graphs are also likely to be of different sizes as the rows of these matrices correspond to nodes or edges of the corresponding graph. Thus, in general, these structural caature-based representations of the graphs cannot be used directly to derive similarity between graphs.
Now, to address this issue, we apply the set Σ of global statistical meta-graph feature extractors to every (G)) Vi .. which summarizes each (G) to fixed-size vector. Specifically, (())(G)) applies each of the statistical functions in Σ (e.g.. mean, kurtosis, etc) to the distribution (G), which computes real number that summarizes the given feature distribution (G) from different statistical point of view, producing vector (G)) R Then we obtain the meta- graph feature vector m of graph G by concatenating the resulting meta-graph feature vectors:
[E(h (G)) I()((G)) Rd.
Table in Appendix D lists the global statistical functions Σ used in this work to derive meta- graph features. Further, in addition to the node- and edge-level structural features, we also compute global graph statistics (scalars directly derived from the graph, e.g., density and degree assortativity coefficient), and append them to m, i.e., the node- or edge-level structural features obtained above.
Most importantly, given any arbitrary graph G', the proposed approach guaranteed to output a fixed d-dimensional meta- grta-graph feature vector characterizing G". Hence, the structural similarity of any two graphs G and G" can be quantified using a similarity function over m and m', respectively.
4.4 EMBEDDING MODELS AND GRAPHS
Given an informative context (i.e., imput features) of models and graphs that METAGL learns from model performances P and meta-graph features M (Sections 4.] and 4.3), y how we use it to effectively learn model and graph embeddings that capture traph-to-mode affinity? We note that similar entities can make each other's context more accurate and informative. For instance, in our problem setup, similar models tend to have similar performance distributions over graphs, and likewise similar graphs are likely to exhibit similar affinity to different models. With this consideration, we model the task as graph representation learning problem, where we construct a graph called G-M network that connects similar graphs and models, and learn the graph and model embeddings over
G-M Network. We define G-M network to be a multi-relational graph with two types of nodes (i.e., models and graphs) where edges connect similar model nodes and graph nodes. To measure similarity among graphs and models, we utilize the latent graph and model factors (U and V, respectively) obtained by factorizing P, as well as the meta-graph features M. More precisely, we use the estimated graph factor U instead of U to let the same graph construction process work for new graphs. Note that this gives us two types of features for graph nodes (i.e., Ô and M), and one type of features for model nodes (i.e., V). To let different features influence the embedding step differently as needed, we connect graph nodes and model nodes using five type of edges: M-g2g, P-g2g, P-m2m, P-g2m, P-m2g where g and m denote the type of nodes that an edge connects (graph and model, respectively), and M and P denote that the edge is based on meta-graph features and model performance, respectively. For example, M-g2g and P-g2g edges connect two graph nodes that are similar in terms of M and U, respectively. Then for each edge type, we construct a A-NN graph by connecting nodes to their top-k similar nodes, where node-to-node similarity is defined as the cosine similarity between the

---

Published as a conference paper at ICLR 2023
corresponding node features. For instance, for P-g2m edge type, graph nodes and model nodes are linked based on the similarity between U and V. Fig. in the Appendix illustrates the G-M network.
Learning Over G-M Network. Given the G-M network Grain with meta-train graphs and models, graph neural networks (GNNs) provide an effective framework embed models and graphs via (weighted) neighborhood aggregation over Gerain However, since the structure of G-M network induced by simple k-NN search, some of the neighbors may not provide the same amount of information as others, or may even provide noisy information. We found it helpful to perform attentive neighborhood aggregation, so more informative neighbors can be given more weights. To this end, we choose to use attentive GNNs designed for multi-relational networks, and specifically use HGT (Hu et al. 2020). Then the embedding function f() in Section 4. is defined to be f(x) = (GT Gorain) during training, which transforms the input node feature x into embedding via attentive neighborhood aggregation over Grrain Further details of HGT are provided in Appendix G.4
Inference Over G-M Network. For inference at test time, we extend Guesnn to be larger G-M network Grest that additionally contains test graph nodes, and edges between test graph nodes, and existing graphs and models in Gusinn The extension is done in the same way as in the training phase, by finding top-k similar nodes. Then the embedding at test time can be done by fxx = HGT(x, Grest).
5 EXPERIMENTS
5.1 EXPERIMENTAL SETTINGS
Models and Evaluation. A model in our problem (Eqn. consists of two components. The first component performs graph representation learning (GRL), and the other component leverages the learned embeddings for downstream task of interest. In this work, we focus on link prediction, which is key task for graph-structured data as we discuss in Section I We evaluate the performance of selecting link prediction model for new graphs without any model evaluation. For the first component, we use 12 popular GRL methods, and for the second component for link scoring, we use simple estimator that computes the cosine similarity between two node embeddings. This results in a model set M with 423 models. The full list of models is given in Table in Appendix C
For evaluation, mance matrix. We construct the performance matrix by evaluating each link prediction model in M on the graphs in the testbed, in terms of mean average precision score. Then we evaluate METAGL and baselines via 5-fold cross validation where the benchmark graphs are split into meta- train Guain and meta-test Geett graphs for each fold, and meta-leamers trained over the meta-train graph data are evaluated using the meta-test graph datasets. Thus, model performances over the meta-test graphs Grest and the geta- features of Guest were unseen during training, but used only for testing.
create testbed containing benchmark graphs, meta-graph features, and perfor-
Since model selection aims to accurately predict the best model for new graph, we evaluate the top-1 prediction performance in terms of MRR (Mean Reciprocal Rank), AUC, and NDCG (Nor- malized Discounted Cumulative Gain). To apply MRR and AUC, we label models such that the top- 1 model (i.e., the model with the best performance for the given graph) is labeled as 1, while all others are labeled as O. For NDCG, we report NDCG@1 1, which evaluates the relevance of top-1 predicted model. All metrics range from 0 to 1, with larger values indicating better performance.
Table 2:
The proposed METAGL outper- forms existing meta-learners, given fully ob- served performance matrix. Best results are in bold, and second best results are under- lined.
notation (e.g., METAGL_SS indicate that the baseline meta- learner uses METAGI.'s 's meta-graph features.
Method
MRR AUC NDCG@1
Random Selection
0.011
0.490
0.745
Global Best-AvgPert
0.163 0.877
0,932
Simple
Global Best-AvgRank
0.103
0.867
0.930
Baselines. Being the first work for evaluation-free model selection in GL, we do not have immedi- ate baselines for comparison. Instead, we adapt baselines used for OD model selection (Zhao et al.) 202I) and collaborative filtering for our problem
METAGL_AS
0.222
0.905
0.947
METAGL_ISAC
0.202 0.887
0,939
Optimization- bused
METAGL.
0,170 0.910
0,945
METAGL ALORS
0.190 0.897
0,950
METAGL NCF
0.140
0.869
0.934
setting. In Appendix A, we describe baselines in de- tail. Baselines are grouped into two categories: (a)
MetaGD
0.075 0.599
0.889
METAGL
0.259 0.941 0.962
Simple meta-learners select model that performs
generally well, either globally or locally: Global Best (Gg)-AvgPerf. GB-AvgRank, ISAC (Ka
dioglu et al. 2010), and ARGOSMARI RT (AS) (Nikolić et al. 2013); (b) Optimization-basee meta-
7

---

Published as a conference paper at ICLR 2023
learners learn to estimate the model performance by modeling the relation between meta features and model performances: Supervised Surrogates (S2) (Xu et al. 2012), ALORS (Misir & Sebag 2017). NCF (He al.) 2017), and MetaOD (Zhao et al. 2021). We also include Random Selection
(RS) as a baseline to see how these methods compare to random scoring.
Note that, except the simplest meta-learners RS and GB, no baselines can handle graph data, and thus they cannot estimate model performance on the new graph on their own. In that sense, they are not direct competitors of METAGL. We enable them to be used for GL model selection by providing the proposed meta-graph features. MetaOD, which was originally designed for OD model selection, also given the same meta-graph features to perform GL model selection. We denote baselines either by combining METAGL with their names (e.g., METAGL S2) to clearly show that they use METAGL''s meta-graph features, or using their name alone (e.g., R S2) for simplicity.
5.2 MODEL SELECTION ACCURACY
Fully Observed Performance Matrix. In this setup, meta-learners are trained using full perfor- mance matrix P with no missing entries. The model selection accuracy of all meta-learners in this setup is reported in Table 2 where METAGL achieves the best performance in all metrics, with 77% higher MRR than the best baseline (AS).
Among simple meta-learners, Global Best meta-learners, which simply average model performance or rank over all observed graphs, are outperformed by more sophisticated meta-lcarners AS and ISAC, which leverage dataset similarities for model selection using meta-graph features. For optimization- based meta- meta-learners, it is important to be aware of how models and graphs relate to each other, and have high flexibility to capture that complex relationship. In methods like ALORS and MetaOD, relations between models and datasets (i.e., relative position of models and datasets the embedding subspace) are learned rather indirectly via reconstructing the performance matrix. METAGL, in contrast, directly captures graph-to-model affinity by modeling their relations via employing flcxible GNNs over the G-M network, as well as reconstructing the performance matrix. As result, METAGL consistently outperforms other optimization-ban based leaa--esrssrs.
are trained using a sparse performance matrix P. obtained by randomly masking out full P. Figure reports results obtained with varying sparsity, ranging up to 0.9, In this more challenging setup, METAGL consistently performs the best across all levels of sparsity, achieving up to 47% higher MRR than the best baseline.
Partially Observed Performance Matrix. In this setup,
With increased sparsity, nearly all meta-learners perform increasingly worse, as one might expect. While AS was the best baseline given full P, its accuracy decreased rapidly sparsity increased. Since AS selects a model based on the INN meta-train graph, it is highly sensitive to P's sparsity. Baselines such as the Global Best baselines are more stable as they average across multiple graphs. Optimization-ben baseed methods like METAGL and S2 perform favorably to simple meta-learners in sparse settings as they learn to reconstruct P by modeling the relation between graphs and models.
* MetaGL (Ours)
ISAC CAS
S2
ONCF
MetaOD
ALORS
O GB-AvgPrr & GB-Avgaa
0.35
Better
Belter
0.95
0.20
0.8-
Better
NDCG@1
MRR
AUC
0.93.
0.15
0.7
0.92
0.91-
0.90-
0.05
0.1
0.3
0.5
0.7
0.9
0.1
0.5
0.7
0.9
0.1
0.3
0.5
0.9
Sparsity Performance Matrix P
Sparsity of Performance Matrix
Sparsity of Performance Matrix P
Figure 4: METAGL consistently performs the best, as the sparsity of performance matrix P varies. METAGL and all baseline meta-learners used the same meta-graph features proposed in this work.
5.3
EFFECTIVENESS OF META-GRAPH FEATURES
In Figure evaluate how the performance of meta-learners obtained with the proposed meta- graph feature (Section 4.3) compares to that obtained with existing graph-level embedding (GLE) techniques, GI.2Vec (Chen& & Koga 2019), Vraph2 (Narayanan et al. 2017), and GraphLoG (Xu et al. 2021).
8

---

Published as a conference paper at ICLR 2023
* MetaGL (Ours)
A ISAC
AS
S2
NCF
+ MetaOD O PALORS
0.3
0.3
0.3
MRR w/ Graph2Vee
MRR w/ GraphLof
MRR w/ G1.3Ver
0.2
0.2
0.2
24
0.1-
0.1
MetaGI wins
MetaGI wins
MetaGI wins
0.0
0.0
0.1
0.2
0.3
0.1
0.2
0.3
0.1
0.2
0.3
MRR w/ MetaGL''s Features
MRR w/ MetaGli's Features
MRR w/ MetaGL'ss Features
Figure 5: Using the proposed meta-graph features (Section 4.3). all meta-learners nearly consistently perform better points are below the diagonal) than with existing graph-level embedding methods.
Figure 8 in App. provides results for three other GLE methods, WaveletCharacteristic (Wang et al.
2021 SF (de Lara & Pineau 2018). and LDP (Cai & Wang 2019).
Most points are below the diagonal Figure 5 i.e., all meta-learners nearly consistently perform
better when they use METAGL's 's meta-graph features than when they use existing GLE methods.
This shows the effectiveness of METAGL's 's features for the proposed task of GL model selection.
METAGL performs the best, whether METAGL's features or existing GLE methods are used.
5.4 MODEL SELECTION EFFICIENCY
To evaluate how efficient METAGL's model selection is, we measure its runtime (i.e., the time create meta- graph features for the new graph at test time, plus the time to predict the best model), and compare it with the time to train a GL. model. Figure 6 shows the distribu- tion in box plots, where red and green lines denote the median and mean, respectively.
Better
0.5s METAGL's 's runtime (scconds) test time.
1.bs
1.5s
2.0s
2.5s
3.0s
Better
0%
30%
40%
50%
60%
70%
(b) METAGL's runtime Time to train GL mod- els for 5% of their potential settings (in pct.).
Results show that METAGL is fast, and incurs negligible runtime overhead: its runtime is just around seconds or less in most cases (Figure (a). Notably, compared to training each GL model for only 5% of its available model configurations, METAGI. takes considerably less time, i.e., median of 5% and mean of 11 % of the time required for model training (Figure (b)) Given large-scale test graphs in practice, the speed-up enabled by METAGL will be greater than that reported in Figure 6b. due to the increased training time such graphs. Also, METAGL's L's model selection process can be further streamlined, e.g., e. by parallelizing meta-feature generation process. We provide additional results the runtime of METAGL and naive model selection in Appendix [.2
Figure 6: METAGL is fast (~1 sec.), and in- curs negligible overhead. Red and green lines denote the median and mean, respectively.
5.5 ADDITIONAL RESULTS
We present ablation study in Appendix L.3 which shows the effectiveness METAGL's proposed components, e.g., the meta-lcarning objective, G-M network, and the graph encoder used by METAGL. We evaluate the sensitivity of model selection approaches to the variance of performance matrix P in Appendix I.4 and compare the predicted model performance with the actual best performance in Appendix
6 CONCLUSION
As more and more GL models are developed, selecting which one to use is becoming increasingly hard. Toward insaanttttts,s,ss, automatic GL model selection, we make the following contributions,
Problem Formulation. We present the first problem formulation to select effective GL models in an evaluation-fii free manner (i.e., without ever having to train/evaluate any model on the new graph). Meta-Learning Framework and Features. We propose METAGL,, the first meta-learning frame- work for evaluation-free GL model selection, and meta-graph features to quantify graph similarities. Effectiveness. Using METAGL for model selection greatly outperforms existing meta meta-lea techniques (up to 47% better), while incurring negligible runtime overhead at test time (~1 sec).

---

Published as a conference paper at ICLR 2023
REFERENCES
Salisu Mamman Abdulrahman, Pavel Brazdil, Jan N. van Rijn, and Joaquin Vanschoren. Speeding up algorithm selection using average ranking and active testing by introducing runtime. Mach. Learn., 107(1):79-108, 2018.
Nesreen K Ahmed, Theodore I. Willke, and Ryan Rossi. Estimation of local subgraph counts, In 2016 IEEE International Conference on Big Data (Big Data), pp. 586-595. IEEE, 2016.
Nesreen K. Ahmed, Ryan A. Rossi, John Boaz Lee, Xiangnan Kong. Theodore L. Willke, Rong Zhou, and Hoda Eldardiry. Learning role-based graph embeddings. CoRR, abs/ 1as//8002.0296 2018.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Mach. Learn. Res., 13:281-305, 2012.
Chenyang Bu, Yi Lu, and Fei Liu. Automatic graph learning with evolutionary algorithms: An experimental study, In PRICAI (1), volume 13031 of Lecture Notes in Computer Science, pp. 513-526. Springer, 2021.
Chen Cai and Yusu Wang. A simple yet effective baseline for non-attributed graph classification. In 2019 ICLR Workshop: Representation Learning on Graphs and Manifolds, 2019.
Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, and Haifeng Chen. Structural temporal graph neural networks for anomaly detection in dynamic graphs. In CIKM, pp. 3747-3756. ACM, 2021.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM, pp. 891-900. ACM, 2015.
Zhe Cao, Tao Qin, Tie- Yan Liu, Ming-Fent Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In ICML, volume 227 of ACM International Conference Proceeding Series, pp. 129-136. ACM, 2007.
Hong Chen and Hisashi Koga. Gl2vec: Graph embedding enriched by line graphs with edge features. In ICONIP (3), volume 1995 of Lecture Notes in Computer Science, pp. 3-14. Springer, 2019.
Nathan de Lara and Edouard Pineau. A simple baseline algorithm for graph classification. 2018.
Seyed Amin Fadaee and Maryam Amir Haeri. Classification using link prediction. Neurocomputing, 359:395 407, 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: robust and efficient hyperparameter optimiza- tion scale. In ICML, volume of Proceedings of Machine Learning Research, pp. 1436-1445. PMLR, 2018
Wenqi Fan, Yao Ma. Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In wwW, pp. 417-426. ACM, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 1135-1135. PMLR, 2017.
Yang Gao, Hong Yang. Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In IJCAI, pp. 1403-1409, 2020.
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D. Sculley, Google vizier: A service for black-box optimization. In KDD, pp. 1487-1495, ACM, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp. 855-864. ACM, 2016.
Mengying Guo, Tao Yi, Yuging Zhu, and Yungang Bao. JITuNE: Just-in-time hyperparameter tuning for network embedding algorithms. CoRR, 02//2211006222 2021.
10

---

Published as a conference paper at ICLR 2023
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS, pp. 1024-1034, 2017.
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In wWW, pp. 173-182. ACM, 2017.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In WWW, pp. 2704-2710. ACM CCM/IW/) IW3C2, 2020.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. CoRR, abs/2101. 11112100111114,, 2021.
Di Jin, Mark Heimann, Ryan A. Rossi, and Danai Koutra. node2bits: Compact time- and attribute- aware node representations for user stitching. In ECML/PKDD (1), volume 11906 of Lecture Notes in Computer Science, pp. 483-506. Springer, 2019.
Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tiemny. ISAC instance-specific algo- rithm configuration. In ECAI, volume 215 of Frontiers in Artificial Intelligence and Applications, pp. 751 751-756. IOS Press, 2010.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net, 2017.
Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu, Policy-gnn: Aggregation optimization for graph neural networks. In KDD, pp. 461-471. ACM, 2020.
Junying Li, Deng Cai, and Xiaofei He. Learning graph-level representation for drug discovery. CoRR, abs/1700 7197079971111 2017a.
Lisha Li, Kevin G. Jamieson, Giulia DeSalvo, Afshhn Rostamizadeh, and Ameet Talwalkar, Hyper- band: A novel bandit-based approach to hyperparameter optimization. J. Mach. Learn, Res., 18: 185:1- 2017b.
Petro Liashchynskyi and Pavlo Liashchynskyi. Grid search, random search, genetic algorithm: A big comparison for NAS. CORR, abs/1912.06059, 2019.
Bin Luo, Richard C. Wilson, and Edwin R. Hancock. Spectral embedding of graphs. Patlern Recognit, 36(10):2213-23300 2003.
Mustafa Misir and Michèle Sebag. Alors: An algorithm recommender system. Artif. Intell., 244:
291-314, 2017.
Annamalai Narayaman, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. In Proceedings of the 13th International Workshop on Mining and Learning with Graphs (MLG), 2017.
Mladen Nikolić, Filip Marić, and Predrag Janičić. Simple algorithm portfolio for sat. Artificial Intelligence Review, 40(4):457-465 2013.
Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos. Multimport: Inferring node importance in knowledge graph from multiple input signals. In KDD, pp. 503-512, ACM, 2020.
Namyong Park, Fuchen Liu, Purvanshi Mehta, Dana Cristofor, Christos Faloutsos, and Yuxiao Dong. Evokg: Jointly modeling event time and network structure for reasoning over temporal knowledge graphs. WSDM, pp. 794-803 ACM, 2022.
Bryan Perozzi, Rami A1-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In KDD, pp. 701-710. ACM, 2014.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL.nttp://nstworrregpsss
com.
Ryan A. Rossi, Nesreen K. Ahmed, and Eunyee Koh. Higher-order network representation learning. In WWW (Companion Volume), pp. 3-4, ACM, 2018.

---

Published as a conference paper at ICLR 2023
Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. Deep inductive graph representation learning. IEEE Trans. Knowl. Data Eng.. 32(3):438 -400443884222, 2020.
Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In CIKM, pp. 3125-3132. ACM, 2020.
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, volume 10843 of Lecture Notes Computer Science, pp. 593-607. Springer, 2018.
Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. Practical bayesian optimization of machine learning algorithms. In NIPS, pp. 2968, 2012.
Chang Su, Jie Tong, Yongjun Zhu, Peng Cui, and Fei Wang. Network embedding in biomedical data science. Briefings Bioinform., 21(1): (2): 2020.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. In wwW, pp. 1067-1077. ACM, 2015.
Ke Tu, Jianxin Ma, Peng Cui, Jian Pei, and Wenwu Zhu. AutoNE: Hyperparameter optimization for massive network embedding. In KDD, pp. 216-225, ACM, 2019.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR (Poster). OpenReview.net, 2018.
Lili Wang, Chenghan Huang, Weicheng Ma, Xinyuan Cao, and Soroush Vosoughi. Graph embedding via diffusion cttituuiionwwvvlttss.s. wavelets-basee node feature distribution characterization. In CIKM, pp. 3478-3482. ACM, 2021.
Xuanhui Wang, Cheng Li, Nadav Golbandi, Michael Bendersky, and Mare Najork. The lambdaloss framework for ranking metric optimization. In CIKM, pp. 1313-1322. ACM, 2018.
David H. Wolpert and William G. Macready. No free lunch theorems for optimization. IEEE Trans. Evol. Comput., 1(1):67-82, 1997.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019a.
Jia Wu, Xiu- Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparameter optimization for machine learning models based on bayesian optimization. Journal of Electronic Science and Technology, 17(1):26-40, 2019b.
Fen Xia, Tie-Yan Liu, Jue Wang. Wensheng Zhang, and Hang Li. Listwise approach to learning to rank: theory and algorithm. In ICML, volume 307 ACM International Conference Proceeding Series, pp. 1192-1199. ACM, 2008.
Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. Graph learning: A survey. IEEE Trans. Artif. Intell., 2(2):109-12)) 127, 2021.
Lin Xu, Frank Hutter, Jonathan Shen, Holger H Hoos, and Kevin Leyton-Brown. Satzilla2012: Improved algorithm selection based on cost-sensitive classification models. Proceedings of SAT Challenge, pp. 57-58, 2012.
Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph-level representation learning with local and global structure. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 11548-11558. PMLR, 2021.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In NeurIPS, 2020.
Yingfang Yuan, Wenjun Wang, George M. Coghill, and Wei Pang. A novel genetic algorithm with hierarchical evaluation strategy for hyperparameter optimisation of graph neural networks. CoRR, 0as/2101109300 2021.
12

---

Published as a conference paper at ICLR 2023
Ziwei Zhang, Xin Wang. and Wenwu Zhu. Automated machine learning graphs: A survey. In IJCAL, pp. 4704 471044711, 2021.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Trans. Knowl. Data Eng., 34(1):249-270, 2022.
Yue Zhao, Ryan Rossi, and Leman Akoglu. Automatic unsupervised outlier model selection, In NeurlPS, pp. 4489-4502, 2021.
Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. Auto-GNN: Neural architecture search of graph neural networks. CoRR, abs/ 199,.03144, 2019.
Ronghang Zhu, Zhiqiang Tao, Yaliang Li, and Sheng Li. Automated graph learning via population based self-tuning GCN. In SIG/R, pp. 109002000. ACM, 2021.
13

---

Published as a conference paper at ICLR 2023
In Appendix. provide description of the baselines (Appendix Aj. notations used in this work (Appendix B). and the model set (Appendix C). and present a summary of meta- graph features (Appendix D) details of graph datasets in the testbed (Appendix ED, and experimental details (Appendix Fp. We then provide additional details and analysis of METAGL. (Appendix (G), e.g. the
G-M network and the embedding function f(.) discussed in Section 4.4
well additional results
(Appendix [ e.g., ablation studies and sensitivity analysis.
A BASELINES
Being the first work for evaluation-free model selection in graph learning (GL), we do not have immediate baselines for comparison. Instead, adapt baselines used in MetaOD (Zhao al. 202T for outlier detection (OD) model selection as well as collaborative filtering for our problem setting. The baselines used in experiments can be organized into the following two categories.
(a) Simple meta-learners select model that performs generally well, either globally or locally.
Global Best (GB)-AvgPerf selects the model that has the largest average performance over all meta-train graphs.
Global Best (GB)-AvgRank computes the rank of all models (in percentile) for each graph, and selects the model with the largest average ranking over all meta-train graphs.
ISAC [Kadioglu et al. 2010) first clusters meta-train datasets using meta-graph features, and at test time, finds the cluster closest the test graph, and selects the model with the largest average performance over all graphs in that cluster.
ARGOSMART (AS) NNikolić et al. 2013) finds the meta-train graph closest to the test graph (i.e., INN) in terms of meta-graph feature similarity, and selects the model with the best result on the INN graph.
(b) Optimization meta-learners learn to estimate the model performance by modeling the relation between -rata features and model performances.
Supervised Surrogates (S2) (Xu et al. 2012) learns a surrogate model (a regressor) that maps meta-graph features model performances.
ALORS Miisir & Sebag 2017) factorizes the performance matrix into latent factors on graphs and models, and estimates the performance to be the dot product between the two factors, where a non-linear regressor maps meta-graph features into the latent graph factors.
NCF (He et al.) 2017) replaces the dot product used in ALORS with more general neural architecture that estimates performance by combining the linearity of matrix factorization and non-linearity of deep neural networks.
MetaOD (Zhao et al. [021] pioneered the field of unsupervised OD model selection by designing meta-features specialized capture the outlying characteristies of datasets, as well as improving upon ALORS with the adoption of an NDCG-based meta-training objective, We enable MetaOD to applicable to our problem setting, by applying our proposed meta-graph features to MetaOD.
In addition, we also include Random Selection (RS) as a baseline, to see how meta-learners perform in comparison to random scoring. Note that among the above approaches, only GB-AvgPerf and GB-AN AB-AAyRank do not rely on meta-features for model selection. All other meta-learners make use of the proposed meta-graph features to estimate model performances on an unseen test graph.
B NOTATIONS
Table 3 provides a list of notations frequently used this work.
C MODEL. SET
model the model set M refers to a graph representation learning (GRL) method along with its hyperparameters settings, and predictor that makes downstream task-specific prediction given the node embeddings from the GRL method. In this work, we use a link predictor which scores a given link by computing the cosine similarity between the two nodes' embeddings.
the
14

---

Published as a conference paper at ICLR 2023
Table 3: Summary of notations.
g
set of graphs (G1,...,Ca } in the training set
number of graphs in training set n = [
Grest
new unseen test graph Gtest E g
M
model set {M]..... Mm to search over
m
number of models to search over m = [M]
V
set of structural meta- meea-nooe/eddge feature extractors set of meta-graph feature extractors
Σ
M
meta-graph feature matrix where M E Raxd
number of meta-graph features
M Mtest
meta-graph feature vector for the new unseen test graph Gtest
embedding size
P
performance matrix of m models on graphs
U
latent graph factors obtained by factorizing P (P UVT)
V
latent model factors obtained by factorizing P (P = UVT)
f()
learnable embedding function for models and graphs
Table 4: Graph representation learning (GRL) models and their hyperparameter settings, which collec- tively comprise the model set M with 423 unique GRL models. For details of the hyperparameters, please refer the cited paper.
Methods
Hyperparameter Settings
Count
SGC Wu et al.
2019a
(number of) hops C (1,2,3)
GCN Kipf & Welling 2017
layers L 21,2,3). 3). epochs 10]
GraphSAGE
Hamilton al.
2017
layers (1,2,3), # epochs 10), aggregation functions
18
E [mean, gen, lstm)
node2vec
Grover & Leskovec
2016
p.g (1,2,4)
role2vec Ahmed al.
2018)
P.q {0.25, 1,4), a (0.01.0.1 0.100..1,.033 0.5.0.9.0.88 0.999. motif combinations # ((i).HH, H3), (H2, H3. H4, Ha, Ha), (H1, H2...., H&}}
180
GraRep et al.
2015
& (1,2)
2
DeepWalk Perozzi et
2014
p=1,g=1 k (1,2), Diecal 8, 16), variant == (1,2,3,4,5)
HONE Rossi et
2018
node2bits Jin
2019
walk wn E (5. 10, 20), walk len wy {5, 10, 20), log base
36
(2,4,8, 10). feats f (16)
DeepGL Rossi 2020
eps tolerance (0.1.0.3.0.5007.0.33
motif size f0.01, 0.01,,..5.00.1 0.13, relational (fm), (p), {s}, (v), {m. p). {m, v), {s, m), (8.P), (s, where m, p. s, denote mean, product, sum, hops/order k (1,
(4).
135
aggr.
LINE Tang 2015
Spectral Emb.
(Luo et al.
2003
tolerance t {0.001}
Total Count
423
complete list of 12 popular GRL methods and their specific hyperparameter settings, which compose 412 unique models in the model set M. Note that the link predictor is omitted from Table 4 since employ the same link predictor based on cosine similarity to all GRL. methods.
D META-GRAPH FEATURES
Structural Meta-Feature Extractors. To capture the local structural properties around node or an edge, we compute the distribution of node degrees, number of wedges (i.e., a path of length 2), triangles centered at each node, well the frequency of triangles for each edge. To capture the global structural properties of a node, we derive the eccentricity, PageRank score, and k-core number of each node. We also capture the global graph-level statistics (i.e,, different from local
15

---

Published as a conference paper at ICLR 2023
node/edge-level structural properties), such as the density of A and AA' where A is the adjaceney matrix, and also the degree assortativity coefficient r.
Global Statistical Functions. For each of the structural property distributions (degree, k-core num- bers, and so on) derived by the above structural meta-feature extractors, we apply the set Σ of global statistical functions (Table 5) over it to obtain fixed-length vector representation for the node/edge//raphh-eee structural feature distribution.
After obtaining set of meta- meta-graph features, concatenate all of them together to create the final meta-graph feature vector m for the graph.
Table 5: Summary of the global statistical functions E for deriving set of meta-graph features from a graph invariant (e.g., k-core numbers, node degrees, and so on). Let x denote an arbitrary graph invariant vector for some graph G; (V,, E,) and x =xx) is the sorted vector of x. Note x can be any representation, egg. node degree vector (value for each node in G;) or a degree distribution vector.
Name
Equation
Num. unique values Density
card(x) nnz(x)/|x)
Q1. Q3
median of the |x /2 smallest (largest) values
IQR
Q3 Q1
Outlier LB a E (1.5,)
Σ I( < -
Outlier UB E [1.5.3
I(,;>> 11
Total outliers a (1.5.3)
Σ, <x
(a-std) outliers a E (2
Px 100
Spearman (p. p-val)
spearman(x, (x, (x))
Kendall (T, p-val)
kendall( x, n (x))
Pearson (r, p-val)
pearson (x, π Txx)
Min, max
min(x). max
Range
max(x) min(x)
Median
(ed(x)
Geometric Mean
X
24
Harmonic Mean
X
Σ
Mean, Stdev, Variance
Skewness
3(x px)
Kurtosis
B(x
Quartile Dispersion Coeff.
Qa-Qu
Qa Q2
Median Absolute Deviation
med x med(x)) (x)l)
Avg. Absolute Deviation
? x uxl
Coeff. of Variation
6x/px
Efficiency ratio
2//12
Variance-to-mean ratio
2/px
Signal-to-noise ratio (SNR)
P2/03
Entropy
H(x)
E; 24 log x:
Norm. entropy
#(x)/108214
Gini coefficient
Quartile max gap
max(Qu+1 - Qi)
Centroid max gap
maxij |0: Czl
Histogram prob. dist.
Pj hee (with fixed # of bins)
h.
16

---

Published as a conference paper at ICLR 2023
E
GRAPH DATASETS
The testbed used in this work comprises 301 graphs that have widely varying structural characteristics. Table 6 provides list of all graph datasets the testbed. All graph data are from (Rossi & Ahmed 2015 they are publicly available under the Creative Commons Attribution-SaarAAlii
License.
Table 6: Summary of the 301 graph datasets that comprise the testhed.
Graph
# Nodes
Edges
Graph
# Nodes
Edges
BA 1_
804
46410
1.2
enzymes, 297
121
149
2
BA-I_II_
917
35860
153
enzymes_gaa 3449
64
118
BA-1 BA-1_12_11 12_10
enzymes, g355
66
112
4
BA-1_13_10
1043
10375
155
enzymes_grr _0004
66
120
5
B4-1_14_40
829
32340
156
enzymes.gga _553
48
111
BA-1_16_44
1126
44220
157
enzymes g526
58
110
7
BA-I_17_10
895
8895
158
enzymes_gsh _527
57
107
8
BA-1_18. 18 40
1141
44820
1559
enzymes, mmz3mes_g_532
74
120
9
BA-I_ __
862
8565
160
enzymes _
51
110
10
BA-1 20_10
830
8245
161
enzymes, g578
60
103
BA-1_22_10
1094
10885
162
enzymes g594
52
114
12
BA-1_24_40
946
37020
163
enzymes
52
116
13
BA-L_3400
1017
39860
164
enzymes_gsy g598
55
100
970
37980
enzymes 88
88
15
BA-L_5100
1050
10445
166
ER-I_II_
917
20841
16
BA- 60
803
46350
167
FR- FR-1_14.5
829
17092
BA-1_7_40
32460
ER-1_15_5
18
BA-1_8 1_100
1040
10345
169
ER IR-1_24_5
946
22383
19
bio-CE-GN
2220
53683
170
ER-1-_55
970
23747
bio-CE-GT
924
3239
171
ER-2_6_5
8115
16868
21
Hi-
2617
2985
172
inf-curoroud
1174
1417
bio-CE-LC
1387
1648
173
inf-openftights
2939
15677
23
CF.G
1871
47754
174
EPGM-Iogg10 ri-lll
845
7194
24
bio DM -X
4040
76717
175
KPGM- 10-10-urial2
830
7265
-i--DM-HT
KPGM log 10-10-000m
7251
26
bio-DM-LC
658
1129
177
PPGiM-oog0--12--1
845
8467
27
bio-DR-CX
3289
84940
178
KPGM-log 10- 2-trial2
864
8339
28
hlo-grid-issionyver
2026
KPGM--lg 1ir---oogg-----riiiiaea
8393
29
bio-HS-CX
4413
1088 8
180
KPGM-log 10-4-trral2
885
9405
30
hio HT
2570
13691
181
KPGM-log 10 10-8-triall
824
6055
31
bio-HS-LC
4227
39484
182
KPGM-log 10-8-trri22
796
6040
32
bio SC-
2223
34879
183
KPGM log 10 8 trial3
813
6052
33
bio-SC-GT
1716
33987
184
KPGM-log&- 1o-M--oog-----ralll
220
1502
34
bio-SC-HT
2084
63027
185
KPGM-llgg-10-mm
220
1518
35
bio-SC-LC
2004
20452
186
KPGM-llog-10--me
224
1520
bio-SC-TS
636
3959
187
KPGM-log&-
224
1729
37
bingrid human
2005
3959
188
KPGM 100M-loo8-112.00 12-trill2
229
1756
38
biogrid-mouse
1450
1636
189
XPGM-logg-12-tmin
230
1761
hiogrid plant
838
KPGM-logg trial
40
biogrid-worm biogrid yeast
1930
3576
191
JPGM--lo8-144trid
233
1950
41
836
1049
192
KPGM log8: 14-tria13
230
1943
ba-cat-mixed- saaa-miied--spcccs--railee species-brainl
730
KPGM--log8-6-ttaal
2117
43
fity-drosophin--medde
1781
9016
194
JPGM-log8-16-trin
230
2152
44
ha macaque rhesus brain!
242
3054
195
KPGM log8 trial3
235
2178
45
bn-macaque-rhese wewannuueeeeeuuuuuiiiee brain2
582
JPGM-log8-8-rrin
223
1324
46
ba macaque thesus cerebral cortex
91
1401
197
KPGM log8 8 trial2
218
1312
47
ba- ae--nacaqu--rheeee teee-rhhess--eeee thesus-interrrral-oooo interareal-corticaa..
93
2262
198
KPGM-Jog8-8-tialB
215
1303
48
bu mouse brainl
213
16242
199
mcil ncil_g1677
102
106
49
ba- re--mous-kkstturr kasthu--
1029
1559
200
ncil ncil_g1863
107
111
bn-mouse- moose--osuull--eeeeee cosualllll-cc
193
214
201
ncil_ ncil_g1893
96
102
51
ca-AstroPh
17903
196972
202
ncil_g1894
104
108
52
ca-CondMat
21363
91286
203
ncil. g2279
88
103
cora
g2082
86
54
ca-CSphhd
1882
1740
205
ncil _ei__
106
107
55
ca: ca-DBLP -ann
2879
11326
206
mcil mcil_g222 g2228
92
98
56
ca-Erdos992
5094
207
ncil_g2229
92
57
ca-GrQue
4158
13422
208
ncil le143
91
97
ca-HepPh
11204
117619
209
ncil_ nci1_g2255
90
96
59
ca-netscience
379
914
210
ncil ncil_g3139
107
112
60
ca sandi- auths
86
123
211
ncil_ mcil_g3141
92
98
C1.-1000-1d7
928
ncil n311_
62
CL-10000-ld7-tra
932
4888
213
mcil_g3444
93
102
63
11-1000-1d7-tian
938
4840
214
ncil ncil_g3349
95
99
TL-1000-1d8-tam
925
mcil_g3585
65
CL-1000- I0-i0o0--d8-trial2
930
4136
216
ncil_g33700
111
119
Continued page
17

---

Published as a conference paper at ICLR 2023
Table 6- Continued from the previous poge
Graph
Nodes
Edges
||
Graph
# Nodes
Edges
CL-1000-1d8-tiaa3
925
3714
217
ncil_ nci1_g33111
89
106
67
CL-1000-1d9-trin
928
3510
218
ncii_g3901
93
102
68
C1.-1000 1-100000-d9 1d9 trial2
912
3053
219
ncil ncil_g77900
90
105
C1-11000-dd--tria
932
ncil _$4094
90
70
C1.-1000 2d0 trial
909
2795
221
power: 1138. bus
1138
2596
71
1L-1000-2d0-trial
899
2941
222
power-194--bus
494
1080
-1-1000-200-
916
3010
power-662-bor
73
CL-1000 -0-1000-2d--riial
903
2430
224
power-685-bus
685
1967
74
10-11000-2d-tii
911
2734
225
power-bespwr(99
1723
4117
1000 tria3
power 176
1176
9864
76
DD_gl
327
899
227
rec-amazon
91813
125704
77
DD g1_
146
328
228
rec movielens tag movies 10m
16528
71081
DD_g100
349
read-chesapeake read ChicagoRegiunal
39
170
79
DD_g1000
183
408
230
1467
1298
DD-g1001
203
231
road-cureroad mad-luxeebburgg-e
1174
1417
81
DD DD_g1002
104
255
232
114599
119666
82
DD_g1001
53
116
233
road-mioncsota
2642
3303
DD g0041004
230
road-usrodds-48
161950
84
DD 1000
370
903
235
ri zi-retweet
96
117
85
DD DD-g1006
246
568
236
rttwitter-copeu
761
1029
DD0g1007
309
732
(Lulwelay
7063
87
DD_g1008
109
304
238
rt_asad rt. bahrain
2139
2788
88
DD DD_9
129
272
239
4676
7979
89
DD_s101
306
728
240
barackobama
9631
9775
90
DD_g1010
157
363
241
rt. d.dmmacuuus IL dash
3052
3869
91
DD 1001
47
136
242
6288
7436
92
DD_ 10_2
146
365
243
ggaanwss
8373
8721
93
DD g013
93
211
244
4687
5529
DD g0-41014
119
273
rt_htip
8917
10314
95
DD_g1015
102
244
246
st. rLislam
4497
4616
96
DD DD_g1016
113
291
247
It rLisrael
3698
4165
g017
98
DD
296
680
2499
rl IL_ia rt_ Jolooop
5067
S541
99
DD g019
131
353
250
9765
10075
DD DD_g102
561
3212
3423
101
DD_g1020
228
541
252
It rtocccuyy
3225
3944
102
DD-g1021
329
787
253
#Loccupywallsteg
3609
3833
103
DD_g1022
294
730
254
It_oman
4904
6230
104
DD DD_g1023
172
425
255
IT o_.edirrection
7987
8103
DD_g1024
160
rt.2 ri PLSaudi rtut
4902
6018
106
DD g0025
205
2557
7252
8061
107
DD DD02
247
578
258
4547
5503
D002
3665
4475
109
DD_g1028
72
137
260
5248
6387
110
DD DD_g1029
99
215
261
rt_ F_voooonedirection
2280
2464
DD g038
sc
112
DD_g1030
136
351
263
soc-advogato
6551
43427
113
DD g104
372
999
264
dolphins
62
159
DD DD_g
soc-firm-hi-teed
33
115
DD g106
574
1355
266
soc gplus
23628
39194
116
DD DD_g107
130
292
267
soe-hamsterster
2426
16630
117
DD DD__
483
268
soc-highschool-morrs
70
274
118
DD_g109
132
315
269
soc-physicians
241
923
DD_gll gll
312
soc-sign- bee--igg-bitconalpha
3783
120
DD gl18
394
1137
271
student coup
185
311
121
DD_gl11
483
1520
272
soc-wiki- Vote
889
2914
122
DD 1D_g
2235
123
DD DD_gI13
347
853
274
Bofbl-Bowdoin77
2252
84387
124
DD gD_
334
761
275
socfb-Caltech
769
16656
125
DD DD11
336
946
276
Hartb-Hamiloo46
2314
96394
126
cco-everglades eco florida hoo-frowee--hng eco foodweb boadweb-baywel wey sco-mangwet ecu-stmaars mmail-dae-corcciiice
69
885
277
socfb-Havee Haverford76
1446
59589
127
128
2075
278
soefb nips ego
2888
2981
128
128
2106
279
fefb-Oherlin44
2920
89912
129
128
2075
280
socfb Reed9g
962
18812
130
1446
281
nocfb-Simmons81
1518
32988
131
54
353
282
socfb Solb-Smmiho00
2970
97133
132
906
10429
283
socfb-Sw Sucb-Swarthmoro42
1659
61050
email-dre
socth- Trinity
1199
134
email-caron-on))
143
623
285
soctb-USFCA72
2682
65252
135
email-Ftt
32430
54397
286
soeth. Vassar85
3068
119161
email radostaw
socib Villanova62
314989
137
email-univ
1133
5451
288
socfb- Wellesley22
2970
94899
138
enzymes_gllt
115
289
Delb--Wiliaamm000
2790
112986
139
enzymos_gl18
121
290
toch-routers-ff
2113
6632
Continued next page
18

---

Published as a conference paper at ICLR 2023
Table 6- Continued from the previous poge
Graph
Nodes
Edges
||
Graph
# Nodes
Edges
140
enzymes_gta
90
127
291
tech-routers-rf
2113
6632
enzymes_ee _999
108
292
web-BerkStan web edu
12305
19500
142
enzymes g204
57
105
293
3031
6474
enzymes g209
101
web-EPA
144
enzymes, g215
48
104
295
web gougle
1299
2773
145
enzymes_gg2 g224
54
105
296
web-indachina-2004
11358
47606
146
enzymes g279
107
297
web-polblogs
2280
147
enzymes_ 1291
62
104
298
web-spam
4767
37375
148
enzymes__aa F292
60
100
299
web-weebuse-2200
16062
25593
enzymes 2293
web aech-wikiich chameleon
150
enzymes_ 299
123
139
301
web-wikii-croooff
11631
170918
151
enzymes, 296
125
141
F EXPERIMENTAL DETAILS
F.1 EXPERIMENTAL. SETTINGS
Software. We used PyTorch for implementing the training and inference pipeline, and used the DGL's implementation of HGT For MetaOD (Zhao et al. 2021), we used the implementation provided by the authors We used the Karate Club library (Rozemberczki et al. 2020) for the implementations of the following graph-level embedding (GLE) methods, Graph2 Vec (Narayanan al. (0177). GL2Vec (Chen & Koga 2019). WaveletCharacteristie (Wang al., 2021). D, SF (de Lara & Pineau 2018). and LDP (Cai & Wang 2019). For GraphLoG et al. 2021). we used the authors'
implementation We used open source libraries, such as Network meta-graph feature extractors.
NumPy for implementing
Hyperparameters. We set the embedding size 32 for METAGL and other meta-learners that learn embeddings of models and graphs. For METAGL, we created the G-M network by connecting nodes their top-30 similar nodes. As an the embedding function f(-) in METAGL, we used HGT (Hu et al. (020) with 2 layers and 4 heads per layer. HGT is included in the Deep Graph Library (DGL), which licensed under the Apache License 2.0. For training, we used the Adam optimizer with a learning rate of 0.00075 and weight decay of 0.0001. For GLE approaches, we used the default hyperparameter settings specified in the corresponding library and GitHub repository.
Link Prediction Model Training. Given graph G, we first hold out 10% of the edges in graph G to be used for evaluation, and train GL models with the resulting subgraph for link prediction. The performed by sampling 20 negative edges per positive edge, computing the link score by applying a dot product between the two corresponding node embeddings, followed by sigmoid function, and then optimizing binary cross entropy loss for the positive and negative edge scores. For evaluation, we randomly sampled the same number of negative edges as the positive edges, and evaluated the predicted link scores in terms of mean average precision.
training of GL models
F.2 EVALUATION OF MODEL SELECTION ACCURACY (SECTION 5.2)
In our evaluation involving a partially observed performance matrix, we extended baseline meta- learners follows they operate in the presence of missing entries in the performance matrix.
Global Best-AvgPerf averaged observed performance entries alone, ignoring missing values. an average performance cannot be computed for some model (which the case when model has no observed performance entries for all graphs), we use the mean of averaged performance for other models in its place.
https::/pytorch...
https: wwtp:://w.wgll..///
https://hetworkx.or
https://numpyoorg.
19

---

Published as a conference paper at ICLR 2023
Global Best-AvgRank computed the model rankings for each graph in percentile, the number of observed model performances may be different for different graphs, and averaged the rank percentiles for observed cases only, as in Global Best-AvgPerf.
ISAC handled the sparse performance matrix in the same way as Global Best-AvgPerf, except that only subset of graphs, which is similar to the test graph, is considered in ISAC.
ARGOSMART (AS) computed the mean of observed performance entries of the INN graph, and used this quantity in place of missing values.
ALORS factorized the sparse performance matrix using a missing value-aware non-negative matrix factorization algorithm.
Supervised Sur. (S2), NCF, and MetaOD performed optimization by only considering observed performance values in the loss function, while skipping over missing entries. Early stopping based on the validation performance was also done with respect to the observed performances alone.
F.3 EVALUATION OF META-GRAPH FEATURES (SECTION 5.3
Except for WaaveetCharactteristcc and GraphLoG, we applied graph-level embedding (GLE) ap- proaches all graphs in our testbed, and meta-learners were trained and evaluated using the rep- resentations of all graphs via 5-fold cross validation. Since WaveletCharacterristic and GraphL.oG could scale up some of the largest graphs in the testbed (e.g.. g. due out-of-memory error), we excluded 9% and 27% largest graphs for GraphLoG and WavcleCCharacteristic respectively, and evaluated meta-learners using the resulting subset of graphs. Note that, in these cases, METAGL was also trained and evaluated using the same subset of graphs.
G ADDITIONAL DETAILS AND ANALYSIS OF METAGL
G.1 METAGL ALGORITIIM AND META-GRAPII FEATURES
Algorithm I provides detailed steps of METAGL, for both offline meta-training (top) and online model selection (bottom). In METAGL, we frg-transform the meta- graph features, and extend the meta-graph features with them, as helps with model selection. We use the notation m Algorithm as well as in the text to refer to these meta-graph features used by METAGL.
G.2 META-LEARNING OBJECTIVE FOR SPARSE PERFORMANCE MATRIX
Given sparse performance matrix P. meta-training of METAGL can performed by modifying the top-1 probability (Equation (3)) and the loss function (Equation (4) ) such that the missing entries in P are ignored as follows:
Peopl (i) Ip., (T(()))) Ekz k= Ipc (p(x))
I,, (exp(pu))
En Ipn (xxp(Px)))
L(P, P)
P. Peopp (o)log log (Peops (i) (i))
(8)
where Ip., (.) is defined
if Piy exists in the observed performance matrix P. t0 if Pij is missing in the observed performance matrix P.
Ip (x)
Thus the supervision signal for each graph comes only from the model performances observed on it. an entire row in P is empty, the loss terms for the corresponding graph are dropped from Equation (8)
G.3 G-M NETWORK
Figure illlstrates the G-M network (graph-model network) (Section 4.4). which is a multi-relational bipartite network between graph nodes and model nodes. In the G-M network, model and graph nodes are connected via five types of edges (e.g., P-m2m, P-g2m, M-g2g), which shown as edges with distinct line styles and colors. Note that while Figure 7soows only edge per edge type, in the G-M network, each node is connected to its top-k similar nodes.
20

---

Published as a conference paper at ICLR 2023
P-g2m
m
ga
P-m2m
M-g2g
p-g2g
P-m2g
mj
9b
: models
: graphs
Figure 7: An illustration of the G-M network (Section 4.4), which is multi-relational bipartite network between model nodes and graph nodes that are connected via five types of edges (e.g.. P- m2m. M-g2g), Note that only subset of the edges in the G-M network is shown here for illustration purposes. See Section 4.4 for more details.
G.4 ATTENTIVE GRAPH NEURAL NETWORKS AND HETEROGENEOUS GRAPH TRANSFORMER
The embedding function f(-) in METAGL (Section 4.4 produces embeddings of models and graphs via weighted neighborhood aggregation over the multi-relationa G-M network. Specifically, we define f(-) using Heterogeneous Graph Transformer (HGT) (Hu al. 2020), which relation- aware graph neural network (GNN) that performs attentive neighborhood aggregation over the G-M network. Let xf denote the node l's embedding produced by the f-th HGT layer, which becomes the
Algorithm 1: METAGL: Offline Meta- Training (Top) and Online Model Selection (Bottom)
Input: Meta-train graph database 9, model set M,, embedding dimension k
Output: Meta-leamnr for model selection
1 (Offline) Meta-Learner Training (Sec. 4.1
Train & evaluate models in M on graphs in G to get performance matrix P
Extract meta-graph features M for each graph G;
(Sec. 4.3)
Factorize P to obtain latent graph factors U and model factors V. i.e., P 2 UVT
Learn an estimator (--) such that of m
Ü, x U,
Create meta train graph Strain (Sec. 4.4
while not converged
for i 1, 1,....,77 do
Get embeddings f[W(m) [m; (mm)) of train graph G; on Grrain for j 1,... m do
Get embeddings f(V,) of each model My on Gurain Estimate Piş (f(W m ((m))) f(V,) (Eqn. 2
11
end end
Compute meta veta-training loss L(P, P) (Eqn. and optimize parameters
14
15 end
Input: new graph Gtest
Output: selected model M for Grest
(Online) Model Selection (Sec.
Extract meta-grapa graph features Mjst t (Gtest)
17 Estimate latent factor Ü = (mm for test graph Guett
Create the test G-M network Grest by extending Gurain with new edges between test graph node and existing nodes in Grrain (Sec. (44)
19
Get embeddings f(W [testi rest.] of test graph on Grest
20 Get embeddings f(V,) of each model M, on Grest
Return the best model M <- arg M, (S(W(m) (mmessst Ü I(V,))
21

---

Published as a conference paper at ICLR 2023
imput of the (e + 1)-th 11-th the output from the last layer, i.e., z," In general, node embeddings z; produced by the f-th layer in an attention-base based GNN, such HGT, can be expressed as:
layer. Given L total layers, the final embedding h, of node t is obtained to be
z
Aggregate (sEN())
(Attention(s, Message(s))
(10)
where s and are source and target nodes, respectively; (t) denotes all the source nodes of node and (s,, 1) denotes all edges from node assigns different weights to neighbors based on the estimated importance of node s with respect to target node t: Message, which extracts the message vector from the source node s; and Aggregate, which aggregates the neighborhood messages by the attention weight.
There are three basic operators: Attention, which
HGT effectively processes multi-relational graphs, such as the proposed G-M network, by designing all of the above three operators to be aware of node types and edge types, e.g., by employing distinct set of projection weights for each type of nodes and edges, and utilizing node- and edge-type dependent attention mechanisms. We refer the reader to (Hu et al., (200)) for the details of how HGT defines the above three operators. In summary, METAGL computes the embedding function f fx;) by providing node l's input features X as the initial embedding (i.e. 2.) to HGT, and returning z the output from the last layer, which is computed over the G-M network via relation-awe aware attentive neighborhood aggregation.
G.5 TIME COMPLEXITY ANALYSIS
We now state the time complexity of our approach for inferring the best model given new unseen graph G' = (V", E"). Let G (V, E) be the G-M network, which is comprised of model nodes and graph nodes, and induced by c-NN (nearest neighbor) search (Section 44. and Appendix G.3). Let
denote the embedding size, and h be the number of attention heads in HGT (Appendix G.4 The time complexity of METAGI. is
(11) where q is the number of meta-graph feature extractors, and |E' is the number of edges in the new unseen graph G'. Note that both q and are small and thus negligible. Hence, METAGL fast and efficient.
Ogq|E'IA+ + |Mck2/1 /h)
Meta-Graph Feature Extraction: The first term of the above time complexity includes the time required to estimate the frequency of all network motifs with {2, 3, 4)-nodes, which is O(E')A) in the worst case where A a small constant representing the maximum sampled degree which can be set by the user. See Ahmed et al. (2016) for further details. The other structural meta-fcature extractors such as PageRank all take at most O( E"l) time. Furthermore, our approach is flcxible and supports any set of meta-graph feature extractors. Thus, it is straightforward achieve a slightly better time by restricting the set of such meta-graph feature extractors to those that can be computed in time that is linear in the number of edges of any arbitrary graph. Hence, in this case, the A term is dropped and we have simply O(g E*| + |Vick// /h). Also, note that feature extractors are independent of each other, and thus can be run parallel.
see that can
Embedding Models and Graphs: To augment the G-M network G given a new graph G', we find a fixed number of nearest neighbors for G", which takes ((V))) time. Then we embed models and graphs by applying HGT over the G-M network G = (V, E). Assuming an HGT with h attention heads, the time to employ HGT over G is ( 2 + [E|k /h). More specifically, the time taken for Attention(.) and Message(-) functions is O 2 + [gjk2/h) where (( is for feature transformation by h heads for all nodes, and (( /h) is for message transfornatiio//atentiion computation over each edge. Similarly, Aggregate()) step takes O(D)) + (E(k) time. Assuming k²/h k,, the time for Aggregate(-) can be absorbed into the time for other steps. Further, given that the G-M network is induced by c-NN search, we have that O(EE)) Occ\V)), and thus the time complexity for embedding models and graphs is O(V)ck?//h)
H ADDITIONAL RELATED WORK
H.1 1 MODEL SELECTION IN MACHINE LEARNING
In this section, we provide a further review of model selection in machine learning, which we group into two categories.
22

---

Published as a conference paper at ICLR 2023
Evaluation- Based Model Selection: A majority of model selection methods belong to this category.
Representative techniques used by these methods include grid search (Liashchynskyl & Liashchynskyi
2019), random search (Bergstra & Bengio, 2012), early stopping- -aased (Golovin et | (017)) and
bandit-based (Li et al. 2017b) approaches, and Bayesian optimization (BO) (Snoek et al. 2012 Wu
et al. 2019b Falkner al. 2018). Among them, BO methods are more efficient than grid random search, requiring fewer evaluations of hyperparameter configurations (HCs), as they determine which HC to try next in a guided manner using prior experience from previous trials. Since these methods perform model training or evaluation multiple times using different HCs, they are much less efficient than the following group of methods.
Evaluation- Frret Model Selection: Methods in this category do not require model evaluation for model selection. simple approach (Abdulrahman al. 2018) identifies the best model by considering the models' rankings observed on prior datasets. Instead of finding the globally best model, ISAC (Kadio) glu et al. 20T0) and AS (Nikolić et al.) 2013) select a model that performed well on similar datasets, where the dataset similarity is modeled in the meta- retaure space via clustering (Kadioglu al.
2010) or k-nearest neighbor search (Nikolić et al.) 2013). A different group of methods perform optimization-basee model selection, where the model performance is estimated by modeling the relation between meta-features and model performances. Supervised Surrogates (Xu et al.) (012) learns a surrogate model that maps meta-features model performance. Recently, MetaOD (Zhao eet al. 2021) outperformed all of these methods in selecting outlier detection algorithms. As method in this category, the proposed METAGL builds upon MetaOD and extends it for an effective and automatic GL model selection. Most importantly METAGL selects graph learning model (e.g., link predictor) for the given graph, while MetaOD selects an outlier detection (OD) model for the given dataset (n-dimensional input features). To this end, METAGL designs meta features to capture the characteristies of graphs, while MetaOD designs meta features specialized for OD tasks. Also, they adopt different meta-training objectives: METAGL adapts the top- 1 probability for meta-training, whereas MetaOD uses an NDCG-based objective. Furthermore, METAGL learns the embeddings of models and graphs by applying heterogeneous GNN over the G-M network, which allows flexible modeling of the relations between different models and graphs. By contrast, in MetaOD, the embeddings of models and datasets are optimized separately, where the relations between models and datasets are modeled rather indirectly via reconstructing the performance matrix. Note that all of these earlier methods, except the first simple approach, rely meta-features, and they focus on non-graph datasets. By using the proposed meta-graph features, they could be applied to the graph learning model selection task.
H.2 COMPARISON WITH MODEL-AGNOSTIC META- LEARNING (MAML) FINN ET AL. 2017
MAML employs meta-learning train a model's initial parameters such that the model can perform well on a new task after the parameters have been updated via few gradient steps using the data from the new task. In other words, given a model, MAML initializes one specific model's 's parameters via meta-learning over multiple observed tasks, such that the meta-trained model can quickly adapt to a new task after learning from a small number of new data (i.e., few-shot learning). On the other hand, METAGL employs meta-learning to carry over the prior knowledge of multiple different models' performance on different graphs for evaluation- -ortatttio---eeeeeeee selection of graph learning algorithms.
Since MAML meta-trains specific model for fast adaptation to new dataset, it is not for selecting model from a model set consisting of a wide variety of learning algorithms. Further, MAML fine-tunes meta-trained model in shot learning setup. whereas in our problem setup, no training and evaluation is to be done given a new graph dataset. Due to these reasons, MAML is not applicable to the proposed evaluation-free GL model selection problem (Problem 1..
I ADDITIONAL RESULTS
1.1 EFFECTIVENESS OF META-GRAPII FEATURES
Figure 8 Showw how accurately meta-learners can perform model selection when they use the proposed meta-graph features (Section 4.3) vs. six state-of of-te----thh-an
fh-thh-art art graph-level embedding (GLE) techniques, i.e, GL2Vec (Chen & Kogal 2019). Graph2 Vec (Narayanan al. (017). GraphLoG (Xu et al. (021)) WaveletCharacteristic (Wang et al. 2021), SF (de Lara & Pineau 2018). and LDP (Cai & Wang all meta-learners achieve a higher model selection accuracy nearly
2019). As discussed in Section 5.3
23

---

Published as a conference paper at ICLR 2023
MetaGL (Ours)
A ISAC
CAS
0
S2
NCF
@ MetaOD
O ALORS
0.3
0.3
0.3
MRR w/ Graph2Yee
MRR GraphLoG
MRR GL2Vee
0.2
*
0.2
0.2
Q1
0.1
0.1
1P
MetaGL wins
MetaGL wins
MetaGL wins
0.0
0.0
0.1
0.2
0.3
0.1
0.2
0.3
0.1
0.2
0.3
MRR MetaGL's Features
MetaGL's Features
MRR w/ MetaGL's Features
MRR WaveletChar.
MRR w/ SF
MRR LDP
0.2-
0.2-
Doo
0.2
0
0.1
0.1
MetaGL wins
MetaGL wins
MetaGL wins
0.0
0.1 MRR w/ MetaGL's Features
0.3
0.0
0.1
0.2
0.1
0.3
MRR w/ MetaGL's Features
MRR w/ MetaGL's Features
Figure 8: Using the proposed meta-graple features (Section 4.3). all meta-lcarners nearly consistently perform better than when they use existing graph-level embedding methods (most of the points are below the diagonal).
consistently by using METAGL's 's meta-graph features than when they use these GLE techniques, and METAGL outperform all meta-learners, regardless of which features used.
Table 7: METAGL fast and incurs negligible overhead. The runtime (in secs) of naive model
selection (i.e., training each method using all configurations in the model set M), versus the runtime of METAGL, i.e. the time to generate meta-graph features (the penultimate row) plus the time taken for model prediction on average (the last row). Datasets are taken from (Rossi & Ahmed 2015).
soc-wiki- Vote
ia- reality
tech- routers-rf
ca-cora
power- US-Grid
web-EPA
socfb- Caltech
tech-pgp
line
5.45
5.85
5.40
6.47
8.23
7.28
8.19
10.15
node2vec
65.28
504.38
154.54
159.32
315.35
317.55
184.09
722,66
deepwalk
7.03
55.01
16.89
17.95
35.62
33.09
18.24
84.35
HONE
203.71
53.15
552.31
276.11
127.4
882.35
737.49
2082.06
node2bits
64.85
113.06
92.22
211.3
117.55
106.66
284.42
deepGL
145.93
633.44
331.87
504.2
1027.25
880.03
445.89
2349.3
GraphSage
272.97
1451.87
513.18
283.35
115.86
1020.30
2586.93
1171.54
GCN
26.30
57.10
45.64
52.96
57.38
66.12
94.65
163.4
(meta feat. gen.)
0.16
0.97
0.36
0.4
1.07
0.78
0.61
2.05
METAGL
(model pred.)
0.39
I.2 MODEL SELECTION TIME
Table 7 shows results comparing the runtime (in seconds) for naive model selection with the runtime of METAGL. Note that naive model selection requires training and eval- uating each method in the model set, while in METAGL, the runtime involves only the time to generate meta- meta-graph feature (penultimate row) and predict the best model via a forward pass (last row). Results show that METAGL is fast, and incurs negligible computational overhead.
50%
100%
150%
200%
250%
Figure 9: Distribution of the time for METAGL make prediction the time to create meta-grape features (in percent- age). Red and green lines denote the me- dian and mean, respectively.
24

---

Published as a conference paper at ICLR 2023
Figure 9 shows the distribution of the time taken for METAGL to predict the best model, divided by the time taken by METAGL for creating meta-graph features (in percentage). On average, it takes 200% less time for METAGL to make inference than to generate meta- geeta-graph features.
2 MetaGI.
MetaGL MetaCL-MSE
O MetaGL-MLL
MetaGL-SingteTyp
8 MeraGLllambda
MetaGI-NN GM
0.96
Better &
Better
0.94
A
0.92
A
0.92
AUC
AUC
0.88
0.90
0.86-
0.88
0.84
0.10
0.15
0.20
0.25
0.200
0.225
0.250
MRR
MRR
(a) Meta-learning objective.
(h) G-M network.
MetaGL-GCN MetaGL-RGCN
MetaGL.
MetaGL
MetaGLLoo(m
X MetaGL-GAT
MetaGL-m
Better
Better
*
0.94
AUC
0.93
0.92
0.70-
0.0
0.1
0.2
0.3
0.200
0.225
0.250
MRR
MRR
(c) Graph neural networks.
(d) Input for embodding graphs.
Figure 10: Ablation study METAGL on several components that METAGL uses for meta-learning The proposed METAGL achieves the best performance, in comparison the variants that adopt different modeling choices.
1.3 ABLATION STUDY
Figure 10 presents ablation studics on several components of METAGL for meta-learning, namely. meta-learning objective, the G-M network, the GNN encoder, and the input for embedding graphs. To that end, we compare METAGL against several variants that differ from METAGL in just one aspect, which we explain below. In Figure 10 METAGL refers to the proposed meta-leamnr described in Section
I.3.1 META-LEARNING OBJECTIVE
To optimize the framework such that it can find the best model, METAGL employs the top-1 probability as its meta- learnin objective (see Section 4.I). We evaluate how METAGL's performance changes when it uses different loss functions for meta-training, METAGL-MSE uses mean squared enror (MSE), METAGL-MLE employs ListMLE (Xia et al. 2008). and METAGL-lambth uses LambdaLoss (Wang et al. 2018). Figure T0al shows that METAGL with the top-1 probability most effectively identifies the top- perfeerforing model for the new graph, while variants that employ different learning objectives obtain suboptimal results in terms of both MRR and AUC.
25

---

Published as a conference paper at ICLR 2023
1.3.2 G-M NETWORK
To learn the embeddings of models and graphs, METAGL uses a G-M network (GM), which a multi- relational network containing multiple types of nodes and edges (see Section 4.4 and Appendix G.3). METAAL--SingleTye G.M is a variant of METAGL that uses single-relation where all of the nodes and edges in the original G-M network have been converted to be of the same type. METAGI--T GM is another variant where METAGI. does not use the G-M network at all; instead, the input features of models and graphs, which are normally provided input the GNN in METAGL, were directly taken to be the final model and graph embeddings. Figure [ob shows that METAGL with the multi-relational G-M network is the most effective, and in utilizing the G-M network, it is helpful to be able to distinguish between the multiple types of nodes and edges. Further, in comparison METAGL-No GM, learning the embeddings of graphs and models via the G-M network greatly improves the model selection performance.
and G-M network,
1.3.3 GRAPH NEURAL NETWORKS
To effectively learn the embeddings of models and graphs over a multi-relational G-M network, METAGL utilizes attentive, heferogeneous graph neural network (GNN) as its graph encoder (see Section 4.4Jand and appendix G.4), which can adaptively determine the aggregation weight of the neighbors (thus attentive), while being aware of and utilizing the multiple node and edge types in learning the embeddings (hence heterogeneous). To see how helpful attentive, heterogeneous GNNs are in learning effective model and graph embeddings, here we create the following variants of METAGL, which use GNNs that are not attentive and/or not heterogeneous (i.e., mechanism to handle different node and edge types). METAGL-RGCN uses RGCN (Schlichtkrull et al., (0018). which is heterogeneous GNN, but is not attentive. METAGL-GAT uses GAT (Velickovic et al., 2018), which is an attentive GNN, but is not heterogeneous. METAGL-GCN uses GCN Kipf & Welling (2017), which is neither heterogeneous is achieved by METAGI. that uses heterogeneous and attentive GNNs, while the lowest performance obtained when it uses GCN, which is not attentive nor heterogeneous. Both the ability to perform attentive neighborhood aggregation, and to be able to distinguish between and utilize different node and edge types are essential in effectively capturing the complex relations between graphs and models.
attentive. In Figure [0cl the highest performance
1.3.4 INPUT FOR EMBEDDING GRAPHS
We have sources of information for graphs: one is the performance matrix P, and the other is graph data. Meta-graph feature m captures the information from the graph data, while e(-) captures the information from the performance matrix by estimating the latent graph factor obtained by
factorizing P. Therefore, the two terms m and d(m) in Equation 2 aim to incorporate two different sources of information. Here we create the following two variants of METAGL: In Equation (2). METAGL-m uses m alone, and similarly METAGL-Ø(m)) uses only á (m). Figure 10d shows that they provide complementary information, and using both leads the best result.
1.4
SENSITIVITY TO THE VARIANCE OF THE PERFORMANCE MATRIX
* MetaGL (Ours) ISAC
CAS
S2
ONCF
MetaOD
ALORS O GBB-AgPerrf & GB-Avgaank
0.25
Better
0.96-
Better
0.9
0.20-
0.8
Better
NDCG@1
0.92.
MRR
AUC
0.15
0.7
0.10
0.88
0.6
0.05
0.0% 3.0% 6.0% 9.0% 12.0% Performance Perturbation Rate
15.0%
0.0%
3.0%
6.0% 9.0% 12.0% 15.0%
0.0%
3,0% 6.0% 9.6% 12.0% 15.0% Performance Perturbation Rate
Performance Perturbation Rate
Figure 1I: Across varying performance perturbation rates, METAGL consistently improves upon existing model selection approaches, achieving up to 53% higher MRR than the best baseline.
26

---

Published as a conference paper at ICLR 2023
We evaluate how sensitive METAGL and baselines the variance of the performance matrix P. which can be introduced due to the non-detemiinistic nature of model training and evaluation. For evaluation, perturb all entries of the fully-observed performance matrix P to varying degrees, and measure the model selection performance using the perturbed performance matrix P. Specifically, given performance perturbation rate r (r 2 0), we replace each performance entry in P with the perturbed performance n, which uniformly randomly sampled from [n(1 1/2), n1 + r/2)], bounded by 0 and 1. For instance, given perturbation rate of 0.2, mean average precision of 0.5 is perturbed by sampling from [0.45, 0.55]. As result, higher perturbation rate makes the perturbed matrix more random, and thus harder to predict. Figure shows that while an increased perturbation rate indeed makes model selection harder for all methods, METAGL consistently outperforms baseline model selection approaches across varying performance perturbation rates, obtaining up to 53% higher MRR than the best baseline.
1.5
COMPARISON WITH THE ACTUAL BEST PERFORMANCE
Between Actual Best and Predicted Best
0.25
Better
Performance Difference
0.15
0.10
0.05
0.00
MetaGL ALORS NCF (Ours)
S2
MetaOD
AS
ISAC
GB- AvgRank
GB-
Figure 12: The smallest performance difference between the actual best and predicted best models is obtained with METAGL (27% and 20% less than the second smallest difference obtained by ALORS in terms of median and mean, respectively). METAGL's distribution is also much tighter than others.
Here we compare the actual best performance observed for each graph against the performance the model chosen by different model selection approaches. Figure 12 box plot showing how those performance differences are distributed. Figure 12 shows that using METAGL leads to the smallest performance difference between the actual best and the predicted best models (27% and 20% less than the second smallest difference obtained by ALORS in terms of median and mean, respectively). Further, the performance difference distribution obtained with METAGL is much tighter than that of baselines.
27


Reviews:
[{"review_id": "kf9giYxBFt", "reviewer": "Reviewer_GdF8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors provide the meta-learning framework for graph learning models that estimates the model performance based on the meta-graph features such as network structures. The proposed method optimizes the numerical performance values based on the top-1 probability based cross-entry loss function. Experimental results show that the proposed method can be robustly optimal for various datasets.", "summary_of_the_review": "While GNN becomes popular in the ML area, it often requires a lot of resource to train on large datasets and chooses the best working model. The proposed meta-learning will provide the opportunity to produce more reliable results in a more productive fashion. Also, the thorough study for the given MetaGL provides understanding and confidence of the proposed model.", "strength_and_weaknesses": "* Strength\n- The proposed meta-learning estimates the performance and leverages the predictive power for more robustly good model learning.\n- The proposed method is a novel way of ensembling graph learning algorithms.\n- The small initial overhead results in more reliable performance.\n\n* Weakness\n- The model performance matrix P is a random matrix since the performance is not deterministic. It would be great to study the sensitivity to the variance of the performance matrix P, not just the observation rate.\n- It would be great if the proposed meta-learning is not only used for the model selection, but also for the insights about the performance characteristics of each graph model algorithm -- such as some algorithm working better for a homophily networks or clustering the similar flavor of algorithms, and so on.\n- It would be interesting to compare the performance from MetaGL with the actual best performance. Since we have a fixed set of algorithms and perform training for each method, we are able to compare with the \"optimal\" selection.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GxNbCAE4LXo", "reviewer": "Reviewer_P6vP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel framework to conduct evaluation-free model selection for graph learning models, i.e., without having to train/evaluate any model on the new graph. The framework learns latent embeddings for observed models and the corresponding performance on observed graphs. Moreover, meta-graph features are computed for each graph based on specific structures so that the graph similarity can be measured. The extensive experiments demonstrate the effectiveness of the proposed framework.", "summary_of_the_review": "The paper solves a novel and crucial problem of evaluation-free model selection for graph learning. The experimental results are comprehensive. However, the major drawback lies in the lack of other graph mining tasks except for link prediction. The design is somewhat novel while also lacking theoretical analysis.", "strength_and_weaknesses": "Strengths:\n1. The framework solves the novel problem of evaluation-free model selection in graph learning, which is crucial and challenging in real-world scenarios.\n2. The experimental results are comprehensive and adequate. The authors also provide additional results regarding the effectiveness of each module and the efficiency of the framework.\n3. The paper is well organized and easy to follow.\n\n\n\n\nWeaknesses:\n\n1. The structural information in each graph seems to be only incorporated via the meta-graph features. However, this can also be achieved by a specific GNN with a readout function. That being said, the improvement of the proposed framework is hardly believed to result from the incorporation of structural information.\n2. The input for computing the latent embedding of a graph to function f() is not rational. If φ(m) is solely dependent on m, why the input of f() is a combination of m and φ(m), instead of only m or φ(m)? In this way, the information of m can also be preserved. On the other hand, combining both will seem redundant.\t\n3. The experimental part only includes the link prediction task. Although this task is important in graph mining, the proposed method should be capable of various graph mining tasks (considering that the scenario will generally be applications). However, the lack of evaluation on other graph mining tasks will cause the paper to be less convincing.\n4. The paper lacks sufficient theoretical analysis to support the claim of efficacy and efficiency. The empirical results are plentiful, while further analysis would be beneficial.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A1Abkxbbm4", "reviewer": "Reviewer_3hVZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of how to select an effective GL model for link prediction task on a new graph without training/evaluating process. To deal with this problem, the authors propose a meta-learning based matrix factorization (MF) approach MetaGL. MetaGL adopt the meta graph features to represent graphs, which can convert the transductive MF to an inductive manner for a new graph.\nThe proposed method is evaluated on 301 graphs via 5-fold cross validation with 412 candidate models.\n", "summary_of_the_review": "The paper considers a new problem of selecting effective GL models in an evaluation-free manner and proposes an effective approach to handle this problem with solid experiments. However, there are some issues with the scalability and limited GRL methods in the model set. \n", "strength_and_weaknesses": "### Strengths:\n1. This paper first considers how to select an effective GL link prediction model for a new graph without searching process. It is a new and meaningful problem. \n\n2. The experiments are solid and can support the contributions: effectiveness of the meta-learning framework and global statistical features.\n\n3. The construction of G-M Network makes sense and further improves the performance. \n\n### Weaknesses:\n1. It seems that the extracting of some meta-features (e.g., triangles and Page Rank score) is time-consuming which limits the application on the large-scale graph.\n\n2. The GRL methods in the model set are limited and the model set may not contain some new GRL methods in recent years.\n\n3. It seems to be missing the training details and metrics of the link prediction subproblem.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0SMh3qt01Y", "reviewer": "Reviewer_uUz4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work focuses on graph model selection without training by matching the meta-feature and model representations. Extensive experiments are conducted to demonstrate the effective and efficiency of the proposed method. Basically, the overall idea has close relation to pioneering work MetaOD. By comparison, this work adopts the key idea to explore the graph model selection task with meta-knowledge.", "summary_of_the_review": "This work attempts to facilitate model selection just by matching the meta-knowledge extracted from graph data and the trained models. It's a very interesting idea. But graph data raises unique challenges over the knowledge transferring across different graphs. Considering this point, it's difficult to believe the generalization of the proposed method.  ", "strength_and_weaknesses": "Strength:\n1. The presentation and writing are good enough for clearly presenting the motivation and corresponding solution.\n2. Meta-features for graph data are clearly defined by fully extracting the graph structural knowledge.\n3. Extensive experiments are conducted to demonstrate the superiority of proposed method to state-of-the-art meta model selection method.\n\nWeakness:\n1. The novelty is limited to applying the principles of MetaOD to graph data by matching meta-features of graph data with model representations. It's interesting to compare the way to run \"meta-learning\" in this work with the optimization-based meta-learning methods like MAML [1]. The common thing shared by them is that finally selected model should have impressive prediction performance. The principles emphasized in this work pays attention to select the best one from the stored models which are trained on historical data. While optimization-based meta-learning can capture the unique knowledge existing in the input data just by fine-tuning models. I strongly suggest to have a discussion on the difference between them and make a comparison over their prediction performance.\n\n2. Though the proposed method can fast search one model from the candidates, it's still difficult to believe that only comparing the meta-features extracted from graph structures can select the exact model for the input data. What if the extracted meta-feature can not represent the node features distribution differences existing in the graphs? Is it still the best choice for model selection? or is the learning-free model selection suitable to deal with the knowledge gap between the new graph and those graphs in the data pool?\n\n3. Last but not least, I still have concern on the generalization of the proposed method. It's well known that graph consists of unique node sets. How is possible that the models trained on different graphs can be applied to a graph with totally different nodes? Maybe authors should present some concrete applications that are suitable to be applied the proposed method.  \n\n\nReferences:\n1. Finn, Chelsea, Pieter Abbeel, and Sergey Levine. \"Model-agnostic meta-learning for fast adaptation of deep networks.\" In International conference on machine learning, pp. 1126-1135. PMLR, 2017.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster