Partition-Based Active Learning for Graph Neural Networks
Authors: Jiaqi Ma
Ziqiao Ma
Joyce Chai
Qiaozhu Mei
Venue: Accepted by TMLR ()

Abstract: We study the problem of semi-supervised learning with Graph Neural Networks (GNNs) in an active learning setup. We propose GraphPart, a novel partition-based active learning approach for GNNs. GraphPart first splits the graph into disjoint partitions and then selects representative nodes within each partition to query. The proposed method is motivated by a novel analysis of the classification error under realistic smoothness assumptions over the graph and the node features. Extensive experiments on multiple benchmark datasets demonstrate that the proposed method outperforms existing active learning methods for GNNs under a wide range of annotation budget constraints. In addition, the proposed method does not introduce additional hyperparameters, which is crucial for model training, especially in the active learning setting where a labeled validation set may not be available.

Published in Transactions on Machine Learning Research (03/2023)
Partition- Active Learning for Graph Neural Networks
Jiaqi Ma"
jiqqinaBilinnisseeee eduu
School of Information Sciences
University of Mlioois Urbona- Urbena-Champan Champoign
Ziqiao Ma*
marstin@umicck. edu
Deportment of Computer Science and Engineering University of Michigan
Joyce Chai
chaijy@umichhcom edu
Department of Computer Science and Engineering University of Michigan
Qiaozhu Mei
qmeiQuunich. edu
School of Information
Department of Computer Science and Engineering University of Michigan
Reviewed OpenReview: https: https:://ppereevieu
openreview. net/ str/formm? id= eOwaRy INuu
Abstract
We study the problem of semi-supervised learning with Graph Neural Networks (GNNs) in an active learning setup. We propose GraphPart, a novel partition-beat based active learning approach for GNNs. GraphPart first splits the graph into disjoint partitions and then selects representative nodes within each partition to query. The proposed method is motivated by novel analysis of the classification error under realistic smoothness assumptions the graph and the node features. Extensive experiments multiple benchmark datasets demonstrate that the proposed method outperforms existing active learning methods for GNNs under a wide range of annotation budget constraints. In addition, the proposed method does not introduce additional hyperparameters, which is crucial for model training, especially in the active learning setting where a labeled validation may not be available.
1 Introduction
Recently, Graph Neural Networks (GNNs) Kippf & Welling 2017 Hamilton et al. 2017 Wu et al. 2019a;
Veličković et al. 2018) have been drawing increasing research interest, due to its numerous successes in various applications. In particular, GNNs have shown superior performance in Graph- based Semi Semi-Superoise Learning (GSSL.), family of problems where individual samples inter-connected by underlying graph, and GNNs provide a flexible method to leverage the information stored in the graph assist learning.
In this paper, we investigate the problem of GSSL with GNNs in an active learning setup (Settles 2012 where one is allowed to actively query node labels on the graph given a limited annotation budget. The active learning setup particularly interesting in the context of GSSL as we usually have access to abundant unlabeled samples prior to learning and, in many cases (e.g., on a social network), we have the flexibility query the labels for small portion of the samples. Furthermore, since key advantage of GNN is the ability to utilize the relational information among the inter-connected samples, properly selecting nodes to annolate may further enhance GNN's performance.
"Equal contribution.

---

Published in Transactions on Machine Learning Research (03/2023)
However, directly adapting conventional active learning methods to GSSL may be sub-optimal due to the special structure of the problem and the GNN models. Indeed, utilizing proper smoothness properties of the data has been a key ingredient for the success of many active learning methods. For example, a commonly used assumption (which we call feature smoothness) is that samples with similar features have higher chances to fall into the same class. In addition to feature smoothness, real-world GSST, tasks often leverage multiple types of smoothness properties over the graph, spanning the spectrum between local smoothness and global smoothness (Zhou et al. 2004). Local smoothness usually relies on the pairwise Euclidean distance between node representations, which becomes less informative in nigh--dimensional space (Aggarwal et al., 2001). Global smoothness, on the other hand, is commonly seen phenomenon in graph-structured data and serves as a great supplement to the local smoothness. While there exist graph-based active learning methods utilizing some of these smoothness properties (Gu & Han, 2012 Ji & Han 2012 Dasarathy et al. 2015 Cai
et al. 2017 Wu et al. 2019b), methods that fully utilize feature and structural smoothness at the proper level are rarc.
We propose GraphPart, a Graph-Partition--bass active learning method for GNNs. The method is largely motivated by the community structures that are commonly present in real-world graphs. Node and struc- tural propertics often exhibit homogencity within a community and heterogencity across communitics. We formalize this observation with proper smoothness assumptions of the graph-structured data at community level (represented by partitions of the graph) and conduct a novel analysis of the GNN classification er- ror under such assumptions. The analysis further motivates the graph-partitioningg step in the proposed method, GraphPart In particular, GraphPart first splits the graph into several partitions based on modu- larity CCauuset et al., 2004) and then selects the most representative nodes within each partition to query. An important merit of the proposed method is that it does not introduce additional hyperparamcters, which is crucial for active learning setups as labeled validation data are often absent. Through extensive experi- ments, we demonstrate that the proposed method outperforms existing active learning methods for GNNs on multiple benchmark datasets for a wide range of annotation budgets. In addition, the proposed active learning method is able to mitigate the accuracy disparity phenomenon of GNNs (Ma et al. 2021).
2 Related Work
Active learning is a sub-field of machine learning that primarily concerns the bottleneck in expensive amno- tation and attempts to achieve high accuracy by querying as few labeled samples as possible. Early efforts in this field prior to the emergence of deep learning have been comprehensively summarized by (Settles) 2012).
Active Learning Setups. The classic active learning algorithms query one sample at time and label it. Such setting is inefficient for a deep learning model as it frequently retrains but updates little, and it is prone to overfitting (Ren et al.] 2020). Therefore, in deep active learning, the batch-mode setting, where a diverse set of instances are sampled and queried, is more often considered. In recent years, the optimal experimental design principle (Pukelsheim 2006: Allen-Zhu et al.] 20200) motivates the machine learning community to minimize the use of training resources and avoid tuning on validation set. Combining the scttings of onc-shot learning and batch-mode active learning, some recent studics (Contardo et al., 2017 Wu et al. 2019b) adopt one-step batch-mode active learning setting. In each run, the algorithm uses up the predefined budget to select batch of nodes to label. The querying process is done once and for all in order to minimize retraining. We focus on such one-step batch-mode setup as we concern with active learning for graph neural networks.
Active Learning on Graphs. Early works in active learning on graphs (Bilgic et al. 2010 Gu & Han 2012 Ji & Han 2012 Dasarathy et al.] 2015)) are designed specifically for non-deep-learning models and/or fail to take the node features into consideration. As deep geometric learning and GNNs become popular, iterative node selection criteria were designed upon the expressiveness of GNNs. In particular, AGE (Cai et al. 2017 evaluates the informativeness of nodes by lincarly combining centrality, density, and uncertainty. (Gao et al. 2018) further proposed ANRMAB, which extends this framework by dynamically learning the weights with a multi-armed bandit mechanism and maximizing the surrogate reward. Similarly, (Chen et al.) 2019) follows previous works and proposed ActivcHNE, which extends AL on non-i.i.d data and heterogencous networks. The above frameworks neglect interaction between nodes and suffer from sub-optimality due to short-term surrogate criteria. Upon this observation, Huu et al. 2020ah proposes GPA, which formalizes the AT. task
2

---

Published in Transactions on Machine Learning Research (03/2023)
Markov decision process and learns the optimal query strategy with reinforcement learning techniques. More recent works approached the problem by incremental clustering (Liu et al. 2020), and adversarial learning (Li et al. 2020). Yet, all of these models are based on an iterative setting. Given some efforts to avoid validation (Regol et al. 2020), iterative querying and retraining is still required.
approaches develops active learning algorithms by investigating the upper bounds of the classification loss. FeatProp (Wu et al. 2019b) is one of the state-of-the-art active learning approaches for GNNs, which derives an upper bound of the node classification error under smoothness assumptions over the label distributions and GNN models. The theoretical analysis by (Wu et al. 2019b) follows prior work, including ANDA (Berlind & Urner, 2015) which proves a finite sample bound on the expected loss of KNNs in the covariate shift setting, and Coreset (Sener & Savarese 2018) which conducts an analysis on Convolution Neural Networks. A common pattern of the active learning algorithms along this line that the algorithms seek select a set of nodes that achieves a good coverage of the space of sample features or hidden representations, and this is typically done via cortain clustering algorithms. Our work falls into this calegory. Compared to existing methods, our method utilizes both the local and global smoothness properties of graph-structured data, where the latter was largely missing in the literature active learning for GNNs so far.
Another line of coptimization-bass
3 Preliminaries
3.1 Notations
We start by introducing useful notations to characterize node classification with GNNs.
Attributed Graph The task of node classification is defined on an attributed graph. Define [n] n). (1,2,...
We denote a graph of size n as G = (V, A), where V = [m] is the set of nodes and A E {0, 1]mxn is the adjacency matrix. Each node E V is associated with a d-dimensional feature vector x; E X C Rd. and a label Y1 E y [C], where C' is the number of classes. Denote X E Rnxd as the feature matrix stacking each node feature. Given the original adjacency matrix A, the degree matrix D E Raxx is defined DH = E, Ar,. Vi V, and Dij 0, Vi V, # j. We denote S as the normalized adjacency matrix with added self-loops: S = (I + D) & (A D)-
Graph Neural Networks GNNs are a family of neural networks modeling graph-structured data. A GNN model is typically defined with two types of operations on the node representations: aggregation and transformation. For example, an L-layer Graph Convolution Network (GCN) (Kipf & Welling 2017 can be (I) recursively represented by a series of aggregation operations JGCN and transformation operations RGCN, for = lI....,,, L, defined as follows,
0 = (1) (CC((H (H""),,) == := ('"",,,,, and
00 = G (A = ReLU(((W)!)
where H)) X is the feature matrix, RcLU(.)) is the clement-wise rectified-lincar unit activation func- tion Nair & Hinton 2010), and W(O is the parameter matrix for the transformation operation G
Noticing that, in most GNNs, the prediction for each node only depends on a local neighborhood of that node, we can define general GNN as function that maps a local neighborhood of a node to its classification predictions. Define (t) as the set of all neighboring nodes of node that can be reached within L-hop on the graph (including itself), and G(f) as the subgraph of G restricted on (i). For each node i, define (L) = ((=))evuu G("), which is tuple including all the node features and the subgraph in node i's 0f
local neighborhood. Let (L)) be the space of such possible v0 Then we can define GNN as function
J: (()) - R
In our later analysis in Section we will consider a type of abstract GNNs in the form of f h ho where the aggregation operation g LL) Rdd and the transformation operation h Rdd - RRC are separated. Tn
3

---

Published in Transactions on Machine Learning Research (03/2023)
particular, can represent any types of feature aggregation the L-hop ego-network of node. And h is transformation function with learnable parameters, which is often modeled by Multi-Layer Perceptron (MLP). Some recently developed GNN models, such as SGC (Wu et al. 2019a) and APPNP (Klicpera et al, 2019), are special cases of this form.
In the rest of our paper, we omit the superscription (I. notations for simplicity.
Margin Loss Given some y 2 0, the margin loss (Neyshabur al. 2018 GNN classifier f:V R for given labeled sample (Ug, Ut) is defined as follows,
L.(f())))))) = (f(4 S max cgt
f(]]
(1)
where 1(-) the indicator function. When we set r = 0, Co corresponds to the 0-1 classification error.
3.2 Active Learning for Graph Neural Networks
In this work, we focus on the one-step batch-mode active learning setup (Contardo al. 2017 Wu et al, 2019b) for node classification using GNNss Suppose there is an attributed graph where the graph structure and the node features are known but the node labels are unobserved. We assunn that for each node i, the node label y/ is a random variable following a conditional distribution Pr(y: 2/]-
At the beginning learning, we are given a small Sy S V of nodes being labeled, which we call seed set. Given all the node samples fev and labels on the seed set {vi for a fixed annotation budget b >> 0, active learning algorithm aims to carefully select set of nodes 81 C V ss and |s1| S b, query the labels on $1, and train GNN model f based on the labeled data {14,, Melouss such that the expected classification error the remaining unlabeled set is small.
4 A Graph-Partiiion- Active Learning Framework
The key motivation of the proposed method is that many real-world graphs present community structures, which induces a proper level of smoothness properties in the graph-structured data. In this section, we first formalize this motivation through an analysis the GNN performance given proper smoothness assumptions, and then introduce the proposed graph-parttlion-basee active learning approach.
4.1 An Analysis of Expected Classification Error Under Smoothness Assumptions
The main result of our analysis is an upper bound (Proposition expected classification error for a node i and a fixed GNN model
I on the quantity E,, (v;),, v:), the
Assumptions We first state the set of assumptions in order establish the upper bound. Denote a K- K-partition of the graph as Tx T2, ,Tk), where Tı,.... Tk C V are disjoint partitions satisfying UK Th = V. Recall that we consider GNNs in the form of f a 9, where g aggregation function and h Rd' + RC is an MLP that takes the aggregated features as input and output the classification logits. We make the following two assumptions on the smoothness of the label distribution and the model.
Rd is a feature
Assumption 1 (Label Smoothness). Assume that Vc E [C], there exists function ne : V [0, 1] such that Pr(m: =c c vg] = ne(vi) for any i V. Moreover, Vk E [K], Vi,j Tk, assume that there erists constont 6, < 0o, such that
In((:)) ne(1y)) S 6yllg(vz) - g(1;)112-
Assumption (Model Smoothness). Assume that Ve,e RRd the MLP h satisfies |[((e) h(E')lloc S dalle e'll2 for some constant. on. oc.
4

---

Published in Transactions on Machine Learning Research (03/2023)
The Main Result We use T(i) to denote the partition where the node belongs to, and denote for convenience the training set Ser == so Us and the test set Ste == V Sty. We have the following result.
Proposition 1. For any fixed GNN model f, under Assumplions | and 2 for any i E Ste, if Str TT()) + 0, letting 7(i) == arg (T, [lg(v,) - g(vi)ll2, E == (lg(v)) - (V-(())) 112 and Y == 2dREs, then we have y. (C)((((()))) v.)] - C5 + Byro (C,, (f(r(()) (r(s))
:=
Proposition 1 provides an upper bound of the expected classification loss Ey,, [vo()(v)))))) for each node in the test set Ste. This upper bound is primarily dependent on the training node 7()) and their distance e on the aggregated feature space, where (i) is the closest training node to i among the ones residing in the same graph partition as i. Specifically, the first term is linearly proportional to E;; and the second term (the expected margin loss of r(i) is increasing with respect to %/2 and hence is also increasing with respect to e;. This upper bound motivates an active learning algorithm that selects the training set by minimizing Eiss, En which we will introduce in detail in Section 4.2
Remarks We make a few remarks on the bound (2) in comparison to relevant previous work. Our novel technical contributions in the analysis include that 1) we have weaker assumption on label smoothness; and 2) our proof (Appendix A.1 removes an unrealistic implicit assumption in previous work.
First, our analysis can be viewed as an extension of the results by (Sener & Savarese 2018) and (W et al, 2019b). One key difference between our analysis and theirs lies in the assumption on label smoothness [Assumption D Adapting the label smoothness assumption by (Sener & Savarese 2019b) into our notations gives the following Assumption
2018 and (Wu et al.
Assumption 3 (Tabel Smoothness by (Sener & Savarese 2018 and (u et al. 2019b Assume that Nc E [C], there erists a function Ne : V + +0,11 such that Pr e vi ne(v)) for any i E V. Moreover, Vi,j E V, assume that there erists a constant 8, < 00, such that
Inc(v:) ne(o;)] S K,llg(v)) g (l2))ll2-
The following fact indicates that Assumption I is weaker than Assumption
3
Lemma If Assumption holds, then there erists constant 6n S 8 satisfying Assumption i
Intuitively, our Assumption is weaker than Assumption 3 because the latter requires the smoothness condition to hold on the entire graph, while our Assumption I only requires the smoothness condition to hold within partitions of the graph. This difference also has a practical significance as Assumption [ allows the label distributions to have sharp changes across different partitions of the graph, which is more realistic than Assumption 3 that does not allow such sharp changes. In addition, the 8n in Assumption [ could be much smaller than the 8, Assumption 3 if the label distribution presents global smoothness over the graph (Zhou et al., 2004)) i.e., the distributions of node labels tend to be closer for nodes within a partition/ ccomuunit of the graph than for nodes reside in different partitions/commiiics ccommuntiiss.
Second, while the upper bounds on classification error given by (Sener & Savarese 2018) and (Wu el al., 2019b) seem to be tighter than our bound (2), we remark that they made an implicit assumption in the proofs that counter-intuitive. In particular, the implicit assumption that, the label distributions of the selected training samples are always concentrated on one class. This assumption is counter-intuilive as the selection of training samples alters the label distributions of those samples. We avoid such an assumption in our analysis at the expense of introducing extra margin loss term
Finally, we remark that while GCN cannot be written in the form of f = ho g as we assumed in our analysis, it has been shown by (Wu et al.] 2019b) that the difference between outputs of an T-layer GCN on two nodes i,j E can be upper bounded by dGoN [[(S*x): - (8* X)xll for some constant 0 < 6GGN < co. So the analysis in this section can be similarly applied to GCN.
4.2 The Proposed Graph Partition- Based Active Learning Framework
The General Framework Motivated by Proposition I we propose an active learning framework that selects the set of nodes to be labeled, $1, by solving the following optimization problem: for & as defined in
5

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm Graph-Partiiton-Basses Query
Input: A K --partition TK of the graph, budget b
Output: A subset of unlabelled nodes $1 of size b: V So and |11 = b
1: Set $1 = 0.
2: for Tæ E TK do
by - b//K.
To (s0 Us)).
E + fg(w:))een.
6:
by (ee)oidds(E))).
//Perform K-Medoids clustering on the set of data points Eg with by medoids returned
as 8.
7: S1 = $1 Us.
end for
return S
Proposition !
min Σ E min 91 91:
Σ min [19(1.) ((2))l2..
(3)
s::/0 Sb lev (in()(
VES.c
For any partition, T& E TK. if further specify budget by for the number of nodes to be selected from this partition, such that Σ by b, then as K separate optimization problems as follows: for l = I....,,,
approximately re-write the optimization problem (3)
min T
Σ min llg(v:) g(u))ll, jex."
(4)
(hhi ieT,
where the individual optimization problem problem with 6y medoids on the partition T.
4 is equivalent to minimizing the objective of K-Medoids
Given K-partition of the graph and a feature aggregation function g V- Rdd we summarize the proposed general framework, which call GraphPart (Craph-Partittonn-aaee query), in Algorithm I For the K-Medoids algorithm, in practice, apply efficient approximation by (Park & Jun 2009 by selecting nodes closest to K-Means centers. The aggregation function g should be chosen according to the GNN architecture that we will be training. For example, for 2-Layer GCN model, we set g(o;) = (S²X); for any i E V, since this lype of aggregation function effectively reflects the output difference of GCN as we remarked at the end of Section 411
The Graph-Partition Method We use modularity-baseed graph partition method, which is one of the most popular classes of methods for community detection (Newman 2004 Clauset al. [004]. Specifi- cally, we obtain K-partition of graph using the Clauset-Newman-Moonn tion (Clauset al. 2004] method. This method is bottom-up algorithm, which begins with communities containing every single node, and iteratively merges the pair of communities that increases modularity the most, until K communities are left. If no pairs of communities can be merged to increase modularity when more than K communities are left, we further use agglomerative hicrarchical clustering (Kaufman & Rousseeuw 2009) to iteratively merge small outlying communities until only K communities are left. Notably, we also propose a simple elbow method to automatically determine the number of partitions K without the need for node labels. Therefore the whole active node selection process hyperparameter-free.
greedy modularity maximiza-
Compensating for the Interference across Partitions One potential shortcoming of the proposed GraphPart method shown in Algorithm that it ignores the interference across partitions as it optimizes separate K-Medoids problems independently on each partition. The medoids selected on two different partitions may be close to each other, which compromisos the overall coverage of the unlabeled nodes. To compensate for this problem, we come up with a greedy correction that when selecting the medoids in
Omitting the seed set so, which in the one-step setting.

---

Published in Transactions on Machine Learning Research (03/2023)
the partition T&, penalize the nodes that close the medoids already selected in the partitions Ti, , 7- Instead of selecting nodes closest to K-Means centers, the distance function to minimize is penalized by the minimum distance to any selected node. We name this corrected variant of GraphPart as GraphPartFar, which makes sure that all the nodes returned to $1 are not too close and similar to cach other, increasing the diversity of the pool.
4.3 Complexity Analysis
We provide a complexity analysis as follows. In natural sparse networks, the number of edges m is often linear in the number of nodes n. Under this approximation, the complexity of Clauset-Newman-Moorr community detection is O(n log" n). The agglomerative hierarchical clustering after detection can be considered as O(1). Under a budget of and d hidden channels, the K-Mcans++ has a complexity of (bbdd/ ((bnd/K²) on each of the communities, adding up O(bnd/K), Overall, the complexity of the proposed methods is roughly lincar in terms of the number of nodes Nevertheless, note that in one-step active learning setup, the compulational complexity of the active learning algorithms is usually not the primary challenge. Instead, the cost of expert annotation is often the primary bottleneck problem.
Moore community
5 Experiments
5.1 Experiment Setup
We experiment on 7 benchmark datasets and compare the proposed methods against several state-of-the- art baseline active learning approaches on training different GNN models. Following (Wu al.) 2019b), evaluate each baseline with series of label budgets and report the Macro-F1 performance for node classification the full graph. Each experiment setting is repeated with 10 random seeds.
Dataset. We experiment on citation networks Citescer, Cora, and Pubmed (Sen et al. 2008). three standard node classification benchmarks. We also experiment. on Corafull (Bojchevski & Günnemann 2018) and Orxn-Arxiv (Hu et al. 2020b), for performance on denser networks with more classes, and on co-authorship networks (Shchur al. 2018 for diversity. The summary statistics of the datascts are provided in Table The homophily ratio delined following Zhu el al. (2020). To determine the best number of K communities in the graph, we find the elbow of the costs using the kneebow toolkit. The value of K for each dataset is illustrated in Figure 1
Marge Cost
Marge Cost
no Rota stedd
Marge Cost
#dusters
#dusters
#clusters
Optimal #Cluster
Optimal #Cuuster 14
Optimal Cluustrr
8
Balanced Aluustrr
#Cluster
#Cluster
(a) Cora
(b) Citeseer
(c) Pubmed
Cost
Rotated
Cost
10
10
20
100
Optimal
Optimal #Cluster
Optimal
#Cluster
Max Balanced #Cluster =
Max Balanced #Quster -
Max Balanced &lluster (f) Corafull
Max Balanced &Quustr
(d) Coauthor-CS
(e) Coauthor-Physics
(g) Ogbn-Arxiv
Figure 1: A summary of the number of partitions, automatically determined by the elbow method.
httpe://ppp..or//ppsjee//eeeee

---

Published in Transactions on Machine Learning Research (03/2023)
Table 1: Summary statistics of datasets.
Dataset
#Nodes
#Edges
#Features
#Claswss (C)
#Partitions (K)
Homophily
Cora
2,708
5,278
1,433
7
7
0.810
Citeseer
3,327
4,552
3,703
6
14
0.736
Pubmed
19.717
44,324
500
3
8
0.802
Co-CS
18,333
$1,804
6,805
15
0,808
Co-Physics
34,,993
247,962
2,000
0.931
Corafull 19,793
126,842
8,710
70
0.567
Ogba- Arxiv
169,343
1,166,243
128
40
0.655
GNN Modcls. We perform experiments over different popular GNN models, including a 2-layer GCN (Kipf & Welling 2017) with 16 hidden neurons, 2-layer GraphSAGE (Hamilton et al. 2017] with 16 hidden neurons and 2-layer GAT (Veličković al. 2018) with 8 attention heads with hidden neurons each. For Ogbn-Arxiv dataset, the number of hidden neurons is increased to 128. To train each model,
use Adam optimizer with an initial learning rate of 1 x 10-² and weight decay of x 10-4, As in the active learning setup, there should not enough labeled samples to be used as a validation set, we train the GNN model with fixed 300 epochs in all the experiments and evaluate over the full graph.
Baselines. We compare active learning methods that can be applied the one-step setting, divided into two categories: 1) general-purposs methods that are agnostic to the graph structure (Random, Density, Uncertainty, and CorcSet); and 2) methods tailored for graph-structured data (Centrality, AGE, FeatProp, GraphParl(Far).
Random: Chooses nodes uniformly at random.
Density (Cai et al. 2017]: First performs clustering on the hidden representations of the nodes, and then chooses nodes with maximum density score, which is (approximately) inversely proportional to the Lz-distance between each node and its cluster center.
Uncertainty Settles & Craven 2008 distribution.
Chooses the nodes with maximum entropy on the predicted class
Pperforms K-Center clustering over the hidden representations of nodes. Since the MIP optimized version is not scalable to large datasets, we use the time-efficient greedy approximation described in the original work.
CoreSet (enner & Savarese. 2018):
Centrality: Chooses nodes with the largest graph centrality metric value, which only considers only the graph structure, but not the node features. As is empirically validated by (Cai et al. 2017). contrality and PageRank contrality outperform other motrics.
Degree
AGE (Cai et al. 2017): defines the informativeness of nodes by linearly combining three metrics: cen- trality, density, and uncertainty. It further chooses nodes with the highest scores.
FeatProp Wu et al. 2019b): first performs K-Means on the aggregated node features, and then chooses the nodes closest to the cluster centers.
GraphPart and GraphPartFar: Two variants of the proposed method as described in Section 4.2
Active Learning Setup. In our one-step setting, we vanish the seed set sp to zero. Note that some baseline methods (Density, Uncertainty, CoreSet, and AGE) are intended for iterative settings and require an initial model trainod with the seed set Sp, as these methods rely on the hidden representations of nodes or the predicted class distribution returned by the initial model. For these baselines, we choose one-third of the budget as random initialization, and let the method select the other two-thirds. On smaller datasets with sparser networks and fewer classes, we test each active learning approach with the scries of budgets chosen as (,,1,223344 x 10. On the large datasets where the network is denser and the number of classes is drastically larger, the budgets are chosen as (33,6,5,677 x 10.
Implementation Details. We adopt Poror Geometric (ey & Lenssen and model construction in our experiments. For CoreSet (Sener & Savarese, 2018 since the MIP optimized version is not scalable to large datasets, we use the time-efficient, greedy approximation version by choosing
2019 for datasct preproccssing
8

---

Published in Transactions on Machine Learning Research (03/2023)
the node closest to the cluster centers. To adapt AGE Cai et al. 2017 for the one-shot setting, stick to the default parameters in the original work (7 = 0.3 for Citeseer, = 0.7 for Cora and 7 = 0.9 for Pubmed. For benchmarks not mentioned, we set = 0.8. For methods that depend on K-Medoids, we apply an efficient approximation by Park & Jun 2009 by initializing with +-Mcans++ (Arthur & Vassilvitskii, 2007 and selecting nodes closest. to centers.
5.2 Experiment Results on GCN
We provide the active learning results of GCN on each dataset in Figure 2 We further provide the exact average Macro-F1 scores and their standard errors in Table 2 For Ogbn-Arxiv, we reported both the Macro and Micro (Accuracy) F1 scores. Overall, we observe in Figure 2 and Table - that the proposed methods, GraphPart and GraphPartFar, outperform baseline methods in wide range of budgets before the performance saturates. On smaller datasets where the number of classes is relatively small, the proposed methods outperform baseline methods by a large margin under a moderate budget size. On Corafull and Arxiv where the number of classes is much larger, the proposed methods demonstrate advantages over bascline methods (in particular, FeatProp) in slightly later stage. This may be due to that some classes were not yel. fully visited so the model has not been learning reliably when the budget size is small. Indeed, methods and FeatProp not statistically significant until the budget size is at least 160. As can be seen in Tables on Ogbn-Arxiv benchmark, no statistically significant difference can be observed from the Micro-Fl evaluation among the active learning methods when the budget is larger than 320, but our methods significantly outperformed baselines on Macro-F1.
shown in Figure 2d
3a the difference between
Table 2: Summary of the performance of GCN on each benchmark. The numerical values represent the average Macro-F1 score of 10 independent trials and the error bar donotes the standard error the mean (all in %). For Ogbn-Arxiv, we also include the Micro-F1 score (accuracy) as standard practice. The bold marker denotes the best performance and the underlined marker denotes the second-best performance, Asterisk (*) means the difference between our strategy and the best baseline strateyy is statistically significant by a pairwise I-lest at significance level of 0.05.
Baselines
Cora 40
Citeseer 20
Pubmed
Budget
80
10
40
Random
49.7 = 9.7
60.7 + 8.7
71.6 5.0
23.4
12.6
37.6
6.7
48.9
5.8
49.1 + 11.
56.7 + 10.6
69.5 + 6.2
Uncertainty
37.6 8.2
55.2 + 10.0
70.1
6.1
18.8
+ 7.1
21.2
3.7
12.8
12.5
16.0
11.5
51.7 = 10.1
61.8 + 9.2
Deusity
49.8 8.6
58.7 + 5.5
73.14:1
41
22.6
1 7.5
37.8
9.0
47.5
6.4
43.6
- 9.8
52.1 8.0
68.7 + 5.3
CoreSet
50.6 1 6.2
64.1 5.3
73.4 1144::00 3.3
27.2
6.6
36,3
7.8
49.6
7.5
45.3
1 8.5
55.7 1 13.0
66.3 1 8.6
Degree
57.7
74.4
19.1
28.0
0.3
38.5
0.3
1.9
Pagerank
35.1 + 0.9
60.2 +
70.8
0.6
11.7
0.3
33.0
0.5
45.6
+ 0.9
45.5 + 0.6
51.0 0.6
66.4 0.1
AGE
50.3 = 5.0
66.7 4 4.1
74.2 + 2.7
20.9
6.3
35.5
9.2
45.2
7.7
47.2 - 9.9
66.2 - 8.3
70.3 + 8.0
PeatProp
71.0 1: 5.7
76.1 1. 2.5
79.9
0.9
27.9
5.5
42.9 1. 4.5
53.7 1. 4.5
59.1 1. 5.5
65.4 1: 5.2
75.1
1 2.8
GraphPart
76.1 + 2.7
78.1 1.5
80.3
1.6
45.0" 0
+ 0.7
45.4
+ 4.1
59.0*
+ 2.0
63.0 + 0.7
73.2*
+ 1.0
74.9
1.3
CraphPartFar
68.6 = 1.5
78.1 2.1
82.0*
0.7
35.1 + 0.6
55.2*
241
57.5* + 2.9
75.7*
0.3
67.5 = 0.5
76.2
0.9
Baselines
Co-CS
Cu-Physics 20
Cortfull
Budgel
80
640
Random
43.8 + 8.8
76.1 6.3
65.6
14.3
73.1
7.5
82.5
+ 7.6
23.8 + 2.0
33.2 + 1.8
43.2
+ 2.1
Uncertainty
32.4 = 8.0
51.6
+ 6.2
66.7
6.1
18.1
+ 12.6
56.3
9.3
75.8
9.2
17.3 - 1.7
28.1
= 2.1
39.1
+ 1.2
Density
34.2 + 8.0
49.1
4.6
60.1
+ 6.0
53.8
8.0
67.9
12.0
72.4
+ 8.8
21.3
1.1
29.0
+ 0.9
38.3
+ 1.1
CoreSet
32.6 + 4.3
50.3
4.8
63.4 63.4
43.8 + 15.3
56.2
+ 14.4
79.8
8.3
22.8
1.4
33.4
1.1
43.7
0.5
Degree
31.1 0.5
49.8
0.5
53.8
- 134
13.4
13.4
0.0
13.4
0.0
20.3
- 0.7
28.4
0.6
37.6
0.6
Pagerank
52.9 0.5
78.5 0.5
82.8
78.2
0.2
81.9
0.2
0.4
0.7
AGE
39.3 - 6.6
67.8 1 8.0
77.9 11.9:00
62.1
10.6
75.6
7.9
85.9 1 3.8
22.2
1.4
32.6
4 1.1
43.0 4 0.9
PeatPrup
60.6 1 3.6
77.2
3.2
0.6 84.5
79.7 1 1.9
88.6
1.7
90.6
1 0.4
29.6 1: 1.0
37.6
1 0.8
46.7 1 0.8
GraphPart
68.5 1 0.2
78.9 1: 2.7
86,2 1.2
84.8"
+ 0.2
86.1
1 0.1
89.3 1: 0.2
31.0*
- 1.3
41.2
1 1.4
48.6
1 0.5
GaaphPartPar
56.8 1 0.7
22.4 1 1.1
84.6 1.3
81.2
0.3
87.6
0.4
90.1 1. 0.3
28.0 1. 1.2
38.4
1 0.6
44.3 1. 0.7

---

Published in Transactions on Machine Learning Research (03/2023)
GraphPart
FeatProp
Degree
AGE
Uncertainty
GraphrartFar
Random
Pagerank
CoreSet
Density
0.8
00.6
MacrroF1
0.4
20.5
0.2
20
20
0.3
160
#Labeled Nodes
Labeled Nodes
#aabeed Nodes
(a) Cora
(b) Citeseer
(c) Pubmed
0.5
0.0
0.4
Socro-Fi
Macro-F1
0.6
0.3
0.2
0.1
60
160
320
640
1286
10 20
40
60
168
10
20
40
80
160
#labeled
#labeled Nodes
(d) Corafull
(e) Coauthor-CS
(1) Coauthor-Physics
Figure 2: Performance of GCN by budget, with training set selected by each active learning baseline in one shot, averaged from 10 different runs. Our methods are embolden. In each sub-figure, the Macro-F1 score is plottod against the budget in a logarithm scale.
Table 3: Summary of the performance GCN on Ogbn-Arxiv (Table Continued). Micro-F1 score (accuracy) standard practice.
We also include the
Baselines
Ogbu-Arxiv (Macro-F1)
Ogbu-Arxiv
(Micro-F1) 640
Budget
160
320
640
1280
160
320
1280
Random
21.9 +
27.6 1.5
33.0
1.4
37.2
0.8
56.4
0.8
60.0 0.7
63.5 + 0.4
Uncertainty
17.3 4 1.2
243
30.5
1.0
36.7 =
44.5
3.0
51.7
1.0
1.2
62.5 #
Density
16.3 + 1.6
20.7 + 1.4
24.8
0.7
29.5 +
46.3
+ 2.3
51.8
+ 1.4
56.0 + 1.1
60.2 0.5
CoreSet
19.5 1: 1.8
25.5 1 1.2
30.5
1: 1.2
35.0 1 0.9
47.6
1 2.9
53.2
1.4
58.1 1 0.8
61.3 1.3...3.. 0.3
Degree
8.0
12.0 = 0.4
12.0 + 0.3
15.4 0.3
29.2
+ 0.9
42.1
+ 0.5
42.9 0.9
48.5 4 0.5
Pagerank
20.4 0.6
28.9 = 0.1
34.0 + 0.2
38.2 + 0.1
50.8 + 1.6
56.8
0.1
60.8 + 0.2
64.2 0.0
AGE
25.9 = 1.1
31.7 0.8
0.8
36.4 0.8 0.8
48.3
1 2.3
54.9
1.6
60.0 0.7
63.5 0.3
FeatProp
24.0 0.7
28.5 = 0.6
33.6 4 0.4
0.4
39.1 = 0.8
51.9 1 1.1
66.3
60.
63.5 0.3
GraphPart
24.2
29.5* 1
36.4
0.5
41.0* +
63.6
CraphPart.ar
26.0* 1
30.2"
36.1 0.7
0.7
53.8
1.0
0.5
594
63.5 1
Fo 0.3
Accuracy
Macro-F1
0.5
0.2
0.4
#Labeled Nodes
#Labeled Nodes
(a) Ogbn-Arxiv by Macro-F1
(b) Ogbn-Arxiv Micro-F1
Figure 3: Performance of GCN on Ogbn-Arxiv (Figure 2 Continued).
10

---

Published in Transactions on Machine Learning Research (03/2023)
5.3 Generalizability to Other GNNs
We further the experiment results other GNN architectures (GraphSAGE and GAT) in Tables and Figure (Appendix). Overall, the superior performance of the proposed methods, especially against the
state-of-theard baseline Feat demonstrates that selecting training nodes within proper partitions of the graph significantly helps the active learning performance.
Table 4: Summary of the performance of GraphSAGE. All the markers follow Table 2
Baselines
Cura
Citeseer
Pubmed
Budgel
Random
36.0
9.6
49.1
+
40.6
13.0
52.3
66.3
Uncertainly
23.5 1: 5.0
38.3
1
10.6
58.6
7.8
17.6
1 6.3
25.1
35.7
4.4
35.2
6.6
50.5
10.1
64.1
10.5
Density
38.0 + 8.3
47.3
6.2
62.1
5.4
22.4
+ 9.1
35.1
+-1++:0
4.9
49.5
4.7
32.7
8.9
51.2 +
10.1
62.1
9.9
CoreSet
28.7 + 5.4
47.8
9.4
64.1
9.2
16.6
5.2
28.2
+ 7.4
39.0
7.4
32.9
+ 7.8
53.1
10.2
63.5
7.4
Degree
43.0 1 1.5
48.2
1.4
65.4
2.1
16.6
1 0.9
23.1
28.6
1.2
39.7
41.9
43.0
0.1
Pagezank
62.9
AGE:
38.2
8.0
56.9
+ 7.8
69.5
19.8
29.7
42.6 6.0
39.9
15.4
59.5
70.2
4.7
Prot
52.5 = 4.6
61.4 + 5.5
72.8 2.6
23.4 + 4.3
39.9
6.2
53.3 3.8
48.0
5.9
59.1
6.0
73.6
1.7
GraphPart
61.4* +: 4.7
70.0* +: 2.4
76.2* + 2.7
34.1 + 2.6
36.1 1: 6.4
54.0 = 4.6
52.0 = 0.8
71.5 1 0.5
74.6 = 1.1
CraphPartFar
57.9" + 2.8
69.7" + 4.2
78.6" + 1.5
30.2"
2.3
46.9 + 5.0
53.1 4.0
19.7 + 3.1
20.7' + 1.6
14.2
0.4
Baselines
Co-CS
Co- Ch-Plssies
Corafull
Budget
160
640
78.3
33.5
Uncertainty
36.5 6.3
56.0 +
72.5
3.5
44.9
10.6
50.6
70.5
15.3
27.0
1.9
39.7
1.1
Density
31.5 = 8.5
39.4
+ 6.2
51.3
3,3
55.8 + 7.9
56.8
11.5
77.8 8.9
13.0
1.2
19.7
0.4
30.6
1.0
CoreSet
25.0 = 6.5
10.8
+ 4.3
55.0
5.3
39.0 + 14.1
50.7 + 11.
75.6 9.5
12.2 2 1.2
19.7
0.6
31.2
0.7
Degree
23.1 : 5.2
33.1
5.1
44.9
3.0
13.4 1
13.4
13.4 0.0
10.6
16.7
0.7
26.8
0.7
Pagerank
0.8
19.4
30.3
AGE:
36.5 + 6.3
56.0
+ 9.4
72.5
63.7
71.0
82.4
13.5
21.4
33.1
1.0
Prop
55.9 + 3.2
68.6 + 3.2
74.1
1.7
77.0 + 2.4
85.2 + 2.2
90.0 + 0.7
18.7 + 0.8
25.8 4 0.7
35.0
1.6
GraphPart
62.9* + 1.4
71.8*
2.2
80.3*
1.3
76.8 + 2.7
85.8 + 0.3
88.9 0.3
19.7"
+ 0.9
28.3 + 0.7
36.1 1.0
GraphPartFar
51.9 + 1.9
73.3*
+ 2.2
81.5% + 2.4
78.5 +
87.6* + 0.9
88.8 0.5
17.5 1.0
26.2
1.4
34.1
0.9
GraphPart
FeatProp
Degree
AGE
Uncertainty
Graph PartFar
Random
Pagerank
CoreSet
Density
0.8
0.8
0.6
Hapro-F
0.6
Micro-FF
0.4
0.6
0.4
0.4
80
20
0.2
160
#Labeled Nodes
@Labeled Nodes
#aabeled Nodes
(a) Cora
(b) Citeseer
(c) Pubmed
0.5
0.8
0.3
Mecro-F7
Mocro.F:
0.2
0.4
0.0 50
160
320
640
1250
10
40
160
10
40
80
160
Nodes
(d) Corafull
(e)
Coauthor-CS
(f) Coauthor- Physics
Figure 4: Results of each baseline on benchmark datasets on GraphSAGE averaged from 10 different runs.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Table 5: Summary of the performance of GAT. All the markers follow Table 2
Baseliues
Com 40
Cilsseer 20
Pubmel
Budget
20
80
10
40
10
20
40
Random
41.2 1: 9.4
51.2
1:
62.3
1 4.3
27.1
+:
11.4
35.9
1:
4.9
46.7
1 5.3
41.6
=: 9.5
48.8
1:
11.6
64.5
1: 7.7
Uncertainty
23.2 4: 5.5
26.5
4.9
47.2
1 6.6
21.5
6.7
25.8
7.5
37.1
8.0
43.9
10.5
47.7
11.2
56.7
10.2
Donsity
9.7
47.7
62.8
CoreSet
29.1 = 6.2
44.9
9.1
61.5 6.9
44.3
1.3+550 5.6
12.9
54.6
10.2
60.4
13.0
Degree
39.3 = 3.5
17.1 = 2.3
61.333
15.9
= 1.2
20.0
4.0
30.6
2.0
11.3 = 8.4
39.9
+ 13
40.2
5.5
Pagerank
31.8 = 4.1
50.3 = 2.5
66.7 = 1.2
15.4
0.6
33.0
= 2.4
42.5
1.9
40.9 = 13
36.3
= 7.0
61.7
3.7
AGE
39.8 1: 5.5
56.5 1: 6.3
66.7
2.7
24.9
12.5
32.9 1: 7.8
51.0
5.0
42.0 2 13.4
51.1
9.7
64.8 9.6
Prap
GraphPart
63,9*
71.8
38.6
4.3
53.5
6.6
68.2
=: 2.2
08.4 8.3
GraphParttar
58.9
2.9
66.7"
1.7
73.8*
1. 2.2
31.6"
4.1
46.6" 1. 3.3
52.2
4.2
52.1
12.4
00.0
T.3
66.2
2.8
GraphPart
FeatProp
Degree
AGE
Uncertainty
GraphPartFar
Random
Pagerank
CoreSet
Density
0.8-
0.0
0.6
Facro.F
F7
0.66
Macro
0.2
0.2
10
20
40
80
160
0.0
10
20
40
80
160
0.2
10
20
40
80
160
#Labeled Nodes
#Labeled Nodes
#labeled Nodes
(a) Cora
(b) Cileseer
(c)
Pubmed
Figure 5: Results of each baseline on benchmark datasets GAT averaged from 10 different runs.
5.4 Mitigating Accuracy Disparity of GNNs
The GNN models are reported to be less accurate on nodes that are further away from the training nodes, which leads to potential fairness concerns (Ma al. 2021). As the goal of proposed active learning moth is to have the selected training nodes evenly distributed on the graph, we conduct an analysis on the accuracy disparity of the actively learned GNN models, following the study by (Ma et al. 2021
We analyze the generalization performances by splitting the test nodes into 10 subgroups according to their fggreuetedd-eatture distance to the 40 selected training nodes (320 for CoraFull), and report the test accuracy on each subgroup. As can be seen in Figure D While the GNNs learned by GraphPart and GraphPart are still less accurate for test nodes that are further away, the proposed active learning methods are able mitigate the accuracy disparity of GCN predictions compared training with random training nodes most datasets.
6 Conclusion and Discussion
In this work, we investigate the problem of active learning for GNNs. Inspired by the commonly seen local and global smoothness propertics on graph-structured data, we propose graph-partiiiin--aaad active learning framework for GNNs, with two variants of concrete algorithms. The proposed framework can be seen active training node selection algorithm that approximately optimizes upper bound of the expected classification error of unlabeled nodes. Through extensive experiments, we show that the proposed methods significantly outperform existing state-of-the-art. baseline active learning methods. Furthermore, the proposed active learning methods are able to mitigate the accuracy disparity phenomenon commonly seen in GNN models.
Similar previous work, e.g., FeatProp, one limitation of this work that their effectiveness relies on the smoothness assumptions to hold for the data of interest. Nevertheless, the proposed methods outperform
12

---

Published in Transactions on Machine Learning Research (03/2023)
previous approaches on many benchmarks, which suggests that it is likely to generalize to more real-world applications.
Broader Impact Statement
As a potential positive impact, our proposed methods has demonstrated superior label efficiency. When applied real-world applications, it significantly reduce the economic cost of annotations in machine learning tasks on graphs.
For the potential negative impacts, the active learning procedure might introduce potential biases into the construction of training data set, which remains underexplored in the literature. this work, we find that the proposed methods can actually reduce the accuracy disparity of GNN predictions compared to randomly selected training nodes. However, the consequences terms of other fairness metrics, such as equal opportunity, still require dedicated further investigations. Therefore applications of active learning high-stake scenarios should proceed with extra caution.
GraphPart
GraphPartFaa - Random
1.0
0.9
0.8
Accuracy
0.8
Accuracy
Accuracy
0.8
0.7
0.6
0.7-
0.5
0.5
2
3
4
6
7
8
9
10
0.4
1
2
5
6
7
9
10
0.6
7
10
Subgroup
Subgroup
Subgroup
(a) Cora
(b) Citeseer
(c) Pubmed
0.7
1.0
Accuracy
0.6
Accuracy
0.9
Accuracy
0.5
0.9
0.3
0.7
1
2
3
4
5
6
7
8
9
10
1
2
3
5
6
7
8
9
10
3
7
8
10
Subgroup
Subgroup
Subgroup
(d) Corafull
(e) Co-CS
(f) Co-Physics
Figure 6: Accuracy disparity across 10 subgroups. Increasing subgroup indices represent the increasing distance to the selected training set.
Acknowledgments
This work was partially supported by the National Science Foundation under grant numbers 1633370 and 1949634. The authors would like to thank the anonymons reviewers for their helpful comments.
References
Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. On the surprssing behavior of distance metrics in high dimensional space. In Database Theory-ICDT 2001: 8th International Conference London, UK, January 4-6, 2001 Proceedings 8, pp. 420-434. Springer, 2001.
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, pp. 1-40, 2020.
13

---

Published in Transactions on Machine Learning Research (03/2023)
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In Proceedings of the 18th Annual ACM-STAM Symposium on Discrete Algorithmss, SODA '07, pp. 1027-1035, USA, 2007. Society for Industrial and Applied Mathematics.
Christopher Berlind and Ruth Urner. Active nearest neighbors in changing environments. In International Conference on Machine Learning, pp. 1870-1879. PMLR, 2015.
Mustafa Bilgic, Lilyana Mihalkova, and Lise Getoor. Active learning for networked data. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, 10, pp. 79 86, Madison, WI, USA, 2010. Omnipress.
Alcksandar Bojchevski and Stephan Günnemann. Deep gaussian embodding of graphs: Unsupervisod induc- tive learning via ranking. In International Conference on Learning Representations (UCLR), 2018.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embodding. arviv preprinl or 1 050.5, 2017.
Xia Chen, Guoxian Yu, Jun Wang, Carlotta Domeniconi, Zhao Li, and Xiangliang Zhang. Activehne: Active heterogeneous network embedding. In Proceedings of the Sonetty-Eightte International Joint Conference on Artificial Intelligence, IJCAT-19, pp. 2123 2129. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E, 70(6), Dec 2004.
Gabriella Contardo, Ludovic Denoyer, and Thierry Artières. A meta-learning approach to one-step active learning. In International Workshop on Automatic Selection, Configuration and Composition of Machine Learning Algoritims,, volume 1998 of CEUR Workshop Proceedings, pp. 28 28-40, Skopje, Macedonia, 2017.
CEUR.
Gautam Dasarathy, Robert Nowak, and Xiaojin Zhu. S2: An efficient graph based active learning algorithm with application to nonparametric classification. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 503-522, Paris, France, 03 13-06 Jul 2015. PMLR.
Matthias Pey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network rep- resentation learning. In Proceedings of the Swentt-Sewenthh International Joint. Conference on Artificial Intelligence, IJCAI-18, pp. 2142 2148. International Joint Conferences Artificial Intelligence Organi- zation, 7 2018.
Quanquan Gu and Jiawei Han. Towards active learning on graphs: An error bound minimization approach. In 2012 IEEE 12th International Conference on Data Mining, pp. 882-887, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NIPS), volume 30. Curran Associates, Inc., 2017.
Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Marc-Alexandre Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. In Advances in Neural Information Processing Systems, volume 33, pp. 10174-10185. Curran Associates, Inc., 2020a.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint vrXiv:2005.00687 2020b.
Ming and Jiawei Han. variance minimization criterion to active learning on graphs. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pp. 556-564, La Palma, Canary Islands, 21-23 Apr 2012. PMLRR
14

---

Published in Transactions on Machine Learning Research (03/2023)
Leonard Kaufman and Peter Rousseeuw. Finding groups in data: introduction to cluster onalysis, volume 344. John Wiley & Sons, 2009.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICIRR, 2017.
Johannos Klicpera, Alcksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Leurning Represenlations (ICLR), 2019.
Yayong Li, Jie Yin, and Ling Chen. Seal: Semisupervised adversarial active learning on attributed graphs.
IEEE Transactions on Neural Networks and Learning Systems, 2020.
Juncheng Liu, Yiwei Wang, Bryan Hooi, Renchi Yang, and Xiaokui Xiao. Active learning for node classifi- cation: The additional learning ability from unlabelled nodes. arXiv preprint arXiv:2012.07000 2020.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mci. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems (NeurIPS) 34. Curran Associates, Inc., 2021.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Pro- ceedingg of the 27th International Conference on International Conference on Machine Learning, ICMT'100, pp. 807-814, Madison, WI, USA, 2010. Omnipress.
M. E. J. Newman, Fast algorithm for detecting community structure networks. Physical Review E, 69(6), Jun 2004.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations (ICLR), 2018.
Hac-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering. Erpert systems with applications, 36(2):3336-38)) 3341, 2009.
Friedrich Pukelsheim. Optimal Design of Experiments. Society for Industrial and Applied Mathematics (SIAM), 2006.
Florence Regol, Soumyasundar Pal, Yingxue Zhang, and Mark Coates. Active learning on attributed graphs via graph cogmizant logistic regression and preemptive query generation. In Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8041-8050. PMLR, 13-18 Jul 2020.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. arXiv preprint wwXiv:2009.00220 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Rad, Collec- tive classification in network data. AI magazine, 29(3):93 93, 2008.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference on Learning Representations (ICLR), 2018.
Burr Settles. Active learning. Synthesis lectures on artificial intelligence and machine learning, 6(1):1-114, 2012.
Burr Settles and Mark Craven. An analysis of active learning strategies for sequence labeling tasks. Tn Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP '08, pp. 1070-1079, USA, 2008. Association for Computational Linguistics.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NewrIPS, 2018.
15

---

Published in Transactions on Machine Learning Research (03/2023)
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph Attention Networks. International Conference on Leurning Representations (TCI.R) 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying
graph convolutional networks. In International Conference Machine Learning (ICMT.,, pp. 6861-6871. PMLR, 2019a.
Yuexin Wu, Yichong Xu, Aarti Singh, Yiming Yang, and Artur Dubrawski. Active learning for graph neural networks via node feature propagation. arXiv preprint arXiv:1910 0.0667, 2019b.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in newral information processing systems, pp. 321 321-328, 2004.
Jiong Zhu, Yujun Yan, Lingxino Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793- 7804, 2020.
16

---

Published in Transactions on Machine Learning Research (03/2023)
A
Appendix
A.1 Proof of Proposition 1
Before we start the proof of Proposition 1 we first introduce helpful lemma below.
Lemma 2. Under Assumption g for any i E Ste, if Str (T(() o 0, letting r(i) == arg min (lg(v;) g(vi) l22 and E, = [1g(v)) - g(vr()) 1l,, then we have
[1((s)) ((u(()))loo S ŌnEi.
(5)
Proof of Lemma
llf(e)) - f(rr())llo
[[(al((r))) - ((((+)))))l
<allo(((e)) - a(vr6))ll
(Assumption 2
ōnEi.
We now start the proof of Proposition
Proof of Proposition
We first consider the expected difference between the loss of i and Br(()
Eg (oo((())) v.)l Ev Ic,, (f(7())))))
Ee Plu, = (f
Den P(T+() = c (z
E Col(()) Ean CL
DE nelus) Colf(u)), C, (f(T())))))
+ Ee + (na(es) ne((ra)) (x)
By Assumption ! the second term can be bounded as:
D ne(U;)) ne( C, (f(v()))))
0 c=l ne(w)) ()(((()) (F(1))))) S D. ne(w)) ne(((()))
$
$ EC 8n 9(v)) s(u = -e dnei = Cd
We then prove that for = 28,5, the first term is non-positive. We prove it by discussing two cases:
1. fy (f((()) = 1: In this case Lo(s(w)) - Lyy, (J(((())) & 0 always holds and the first term is non- nos-posiiive.
2. C., ((((()) = 0: This situation only happens if f(v+())l > % + maxaşe ((+(0)) By Lemma we know that for any b = 1, 1,...,C: C.
f(v.)ld 2 (v)()) -5,5
and [(x) < (v)()) + 8,5;
17

---

Published in Transactions on Machine Learning Research (03/2023)
Therefore,
f(u:)ld - maxb f(e;)[b]
()(O)(O))L) onei) - (unaxs/e Ōnei)
=((r)())c) 28AE; maX64e
=((m()) (1x))
which implies Co(f(v;),)) O. Hence Therefore, for 7i- = 2, we have
and the first term is non-positive.
B En] v:)l S Cô.et + Exsco [C2n,e, (, (f(+())) (+()))
A.2 Addendum to Experiments
We further conduct sensitivity analysis for the proposed method. In particular, are interested in the effectiveness of the partition approach when combined with distance metrics on different node representations. Specifically, (1) Aggregation: aggregated node features S²X; (2) Embedding: the last hidden layer of GCN trained on one-third the budget; and (3) Feature: the original node features. As shown in Table the seaph-partition step is robustly effective when combined with various types of distance metrics. For each choice of distance, we evaluate the active learning performance with or without the graph-partition step. We perform the experiments on Cileseer, Pubmed, and Cora. On each dataset, evaluate each active learning method with a budget size of 20, 40, and 80. Each experiment is repeated with 10 random seeds.
As can be seen from Table 0 the graph-partition step is robustly effective when combined with various types of distance metrics. This suggests that the proposed graph-partition framework may be able to generalize to active learning for other graph representation learning methods. It is also interesting to observe that methods with a graph-partition step tend to have lower standard crrors.
Table 6: Summary of the performance of different combinations of distance metric on Citeseer, Pubmed and Cora datasets with or without using graph partition. The numerical values represent the average Macro-Fl score of 10 independent trials and the error bar denotes the standard error of the mean (all in %). The bold marker denotes the better performance between with and without using graph partition, and asterisk (*) means this difference statistically significant. by pairwise t-test at a significance level of 0.05.
Node Rep. With Budgen Partition
Coza
Citeseer
Pubmed
Aggregation
yes
76.1"
2.7
78.1 1. 1.5
80.3
1.6
45.4
1 4.1
59.0"
2.0
67.7 1. 1.5
73.2" 1.0
74.9
1.3
79.7 2.3
no
71.0
5.7
76.1
+ 2.5
79.9 + 0.9
42.9
4.5
53.7 + 4.5
67.4
2.0
65.4 + 5.2
75.1
+ 2.8
79.5 + 0.9
Embedding
yes
61.3*
4.8
69.4*
+: 3.9
76.7
3.4
43.9
: 7.1
54.4 2.8
61.1 4: 2.3
70.1 8.8
74.9
2.8
78.1 2.0
Do
51.5
Feature
yes
65.6"
2.6
71.0*
+ 2.1
77.2 + 1.3
15.7* + 0.9
33.1
54.4 1.8
56.6 2.1
67.1
77.1
DO
53.2 :: 5.2
64.0 1: 5.1
77.4
1.7
6.1 = 2.4
30.9 1: 4.5
54.0 4.1
64.3" 1 8.6
70.0 1 4.1
76.6 1: 0.9
18


Reviews:
[{"review_id": "N6WhgrLUOM", "reviewer": "Reviewer_NTPU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Overall the motivation for this problem is clear and active learning with structured input data such as graphs is indeed a worthwhile problem to tackle. I also found the writing and presentation to be of mostly high quality---outside of a few minor details that I will outline below. The experiments also seem exhaustive and it's important to see the proposed approach working well. Finally, I also checked the proof quickly but it seems correct.\n\n\nWeaknesses:\nI have a few concerns about this paper that I list below.\n- While the overall problem of active learning on graph data is interesting and well-motivated, the idea of partitioning the graph into disjoint sets is less developed. Indeed, there is a vast literature on how to do this but perhaps a more fundamental question one could ask is why do we want to do graph partitioning in the first place? For example, one could instead choose to do graph coarsening and consider each super node as its own disjoint partition. This would open up a huge variety of new methods that could be employed and this angle should be investigated a bit more. Specifically, how robust are the current results to the partitioning/graph coarsening strategy? \n\n- The paper makes a series of assumptions about label and model smoothness. These seem mostly important to prove Proposition 1. For label-smoothness it feels like you can actually empirically check this for different graphs by constructing $L$-hop neighborhoods and see to what extent real-world graphs or more specifically the ones in the datasets considered for the experiments.\n\n- I find the experimental settings to be a bit ad-hoc. The number of labeled nodes should be a percent of the training dataset size rather than an absolute number, otherwise, trends across datasets are misleading.\n\n- I found the comment about Assumption 3 in relation to Assumption 1 a bit confusing. It seems obvious that in Assumption 1 $\\delta$ can be smaller as it's a stronger assumption because we are operating on the partitions rather than the whole graph.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GraphPart a novel approach to a novel partition-based active learning\napproach for GNNs which is predicated on partitioning an input graph into disjoint sets and performs queries construction on the representation space of nodes on the aggregation function $g$.  The paper also has a theoretical result on the upper bound on the classification error under various smoothness assumptions. Finally, extensive experiments are conducted ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The biggest change or addition I would like to see is a detailed investigation of different strategies to create the partitions. In particular, trying some popular off-the-shelf graph coarsening algorithms would be a big plus.\n\nSecondly, an investigation into the label smoothness assumptions would strengthen the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uf70uOWaIS", "reviewer": "Reviewer_58wd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "When bounding the second term in the proof of Proposition 1, the first step does not hold.\n\nConsidering the case $\\eta_c\\left(v_i\\right)-\\eta_c\\left(v_{\\tau(i)}\\right)<0$ for $\\forall c$, you cannot get the first step. Therefore, Proposition 1 is not true. Then, the proposed method is not reasonable. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies active learning for graph neural networks. However, the fundamental theories are not correct. As a result, all methods that are based on this theoretical result are not reasonable. Thus, this paper needs a major revision to fix this fatal error. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are some errors when proving Proposition 1. ", "broader_impact_concerns": "Since there are some theoretical errors, it is no sense to discuss its broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kNgDQsclZ5", "reviewer": "Reviewer_PWue", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This submission is clear and easy to follow.\n\n2. The loss is motivated by theoretical analysis, which is reasonable. \n\nWeaknesses:\n\n1. In general, this paper does not give me an impressive feeling. Specifically, as the authors mentioned in Section 2, active learning on GNN has been explored in many existing works. The authors also mentioned using local and global smoothness to design the final learning objective, where global smoothness is largely missing in the literature on active learning for GNNs. However, it is not clear why this global smoothness is important. This motivation and significance should be further discussed in the method part and experimental part.\n\n2. I am very confused about Proposition 1. First, $\\epsilon$ is defined but not used in Eq. (2). In Appendix Lemma 2, $j(i)$ should be $\\tau (i)$. Second, the authors mentioned 'the second term (the expected margin loss of $\\tau (i)$) is increasing with respect to $\\xi_i$.' However, it is hard for me to get this finding from Eq. (2). I suggest the authors provide more evidence to support this conclusion. In addition, how to get a conclusion about 'This upper bound motivates an active learning algorithm that selects the training set by minimizing $\\sum_{i\\in S_{te}} \\xi_i$'? This should be further explained.\n\n3. The proof of Lemma 1 is missing. \n\n4. Some details are missing in experiments. For example, what are 20, 40, and 80 in Table 2 (for the Cora dataset)?\n\n5. My another major concern is the loss function.  In your submission, the theoretical results are based on the 0-1 loss assumption in Eq. (1). However, I checked your code, and you use cross-entropy loss to do all experiments. Therefore, there is a large gap between theory and experiments. I expect the authors can explain the reasons. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors proposed a partition-based active learning method called GraphPart for improving graph neural network predictions. The loss function is inspired by Proposition 1, which is obtained according to some existing results such as Sener& Savarese,2018 and Wu et al., 2019b.  Extensive experimental results on 7 datasets demonstrate the effectiveness of the proposed approach when compared with 8 baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See my comments on weaknesses. ", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a graph partition method for semi-supervised learning on graph data. The proposed method is well motivated and supported by both theoretical and thorough empirical analysis. There was a typo in the proof, but it was fixed after the reviewer pointed it out. 

The remaining concern from one reviewer is that the high-level idea of this paper is not very impressive, which I agree. However, given that this paper proposes a new method with good performance, as shown in the extensive experiments. 

Thus, I would suggest acceptance of this paper. Since This paper reviews and compares with a bunch of exisiting methods, I would recommend a "survey certification".
Decision: Accept (poster)