Tackling Provably Hard Representative Selection via Graph Neural Networks
Authors: Mehran Kazemi
Anton Tsitsulin
Hossein Esfandiari
Mohammadhossein Bateni
Deepak Ramachandran
Bryan Perozzi
Vahab Mirrokni
Venue: Accepted by TMLR ()

Abstract: Representative Selection (RS) is the problem of finding a small subset of exemplars from a dataset that is representative of the dataset. In this paper, we study RS for attributed graphs, and focus on finding representative nodes that optimize the accuracy of a model trained on the selected representatives. Theoretically, we establish a new hardness result for RS (in the absence of a graph structure) by proving that a particular, highly practical variant of it (RS for Learning) is hard to approximate in polynomial time within any reasonable factor, which implies a significant potential gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model. We then study the setting where a (homophilous) graph structure is available, or can be constructed, between the data points. We show that with an appropriate modeling approach, the presence of such a structure can turn a hard RS (for learning) problem into one that can be effectively solved. To this end, we develop RS-GNN, a representation learning-based RS model based on Graph Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN on problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established baselines on a suite of eight benchmarks.

Published in Transactions on Machine Learning Research (07/2023)
Tackling Provably Hard Representative Selection via Graph
Neural Networks
Mehran Kazemi
mehrankasemiiggoogee com tsitsulin @google. com esfandiario Boggggeerggogg..oooo com bateni @ @google. com rumachand @google. com bperozzi Dramm. org morrokni mnrrokni@@oooge. com
Anton Tsitsulin
Hossein Esfandiari
MohammadHossein Bateni
Deepak Ramachandran
Bryan Perozzi
Vahab Mirrokni
Google Research
Reviewed OpenReview: https: https://openrevveau openreview. net/ forum? id= 3Lzg003e00
Abstract
Represenlative Selection (RS) is the problem of finding a small subset of exemplars from a dataset that is representative of the dataset. In this paper, we study RS for attributed graphs, and focus on finding representative nodes that optimize the accuracy of model trained on the selected representatives. Theoretically, we establish new hardness result for RS (in the absence of a graph structure) by proving that particular, highly practical variant of it (RS for Learning) is hard to approximate in polynomial time within any reasonable factor, which implics significant potential gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model. We then study the setting where a (homophilous) graph structure is available, or can be constructed, between the data points. We show that with an appropriate modeling approach, the presence of such a structure can turn hard RS (for learning) problem into one that can be effectively solved. To this end, develop RS-GNN, representation learning-based RS model based Graph Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established basclincs on a suite of cight benchmarks.
1 Introduction
In the age of massive data, having access to tools that can select exemplar data, points representative of an entire dataset is of crucial importance. Representative selection (RS) [Feldman 2020), finding small subset of exemplars from an unlabeled dataset that transmits maximal information for a certain objective, has numerous applications in summarization, active learning, data compression, model training cost reduction,
and many other domains (sce, e.g., (Bairi et al.] 2015 Kanshal et al. 2019 Liu et al. 2015 Wei et al. 2014
You al. 2020 Church ReVelle 1974; Killamsetty et al. 2021c
Feldman 2010)):
In this work, we study RS for attributed graphs. We first study the computational complexity of a specific but widely-applicable formulation of the RS problem in the absence of graph structure, where attempt to find fixed-size subset of representative exemplars from dataset that can be used to train model with the best possible accuracy on the entire dataset. We show it is impossible to provide polynomial-time RS algorithm with an approximation factor better than w(n-1/poly log log unless the Exponential Time Hypothesis (ETH) fails. ETH a widely- assumption in the domain of parameterized complexity which states that the 3-SAT problem cannot be solved in subexponential time the worst case. Note that w(nol//oly log 1) is almost polynomial, ruling out the existence of any constant approximation or even poly-logarithmic approximation.

---

Published in Transactions on Machine Learning Research (07/2023)
Our subconstant hardness result is of particular importance because several previous works find representatives by optimizing swrogale junctions-ther can be approxinated well in -nnry-dnstead of the actual model accuracy. For instance, they consider a submodular surrogate function which can be approximated within a factor 1-1/e in polynomial time [Guillory] 2012 Wei et al. 2015 Mirzasoleiman et al. 2020 Chen & Krause
2013 Eslandiari et al., 2021p. Our hardness result implies that, in the worst case, there is a significant gap between the optimum solution of such surrogate functions and the actual accuracy of the model, rendering the surrogate functions poor estimators for the quality of the model. To the best of our knowledge, this is the first subconstant hardness result for the RS problem. This motivates to deviate from directly defining proxy functions, and make use of learning-based based approaches that discover the hidden structure of the data to guide the selection. This is in line with the recent attempts to solve computationally hard problems with neural networks, e.g., (Wilder el al. 2019: Coleman el al. 2019).
We next study the setting where besides the node features, a (homophilous) graph structure between the data points is provided, which can help guide the selection process. We show empirically that with an appropriate modeling approach, the presence of such a graph utructure can turn an originally hard RS problem into one that can be effectively solved. To this end, we develop RS-GNN: learning- based model for Representatives Selection via Graph Neural Networks. We first demonstrate the effectiveness of RS-GNN for selecting representative nodes from datasets where a natural graph can be accessed, i.e., where edges may be specified by some natural property of the data (o.g., paper citations). Then, we demonstrate that even when a natural graph is not available but a similarity graph is believed to have some degree of homophily, creating a similarity graph of the input data points and applying RS-GNN can still select high-quality representatives. We conduct experiments on eight datasets with different sizes and properties, and in both settings where we have and do not have access to graph structure. Our results show that our model provides significant improvements over three kinds of baselines: 1) well-established baselines that optimize predefined surrogate functions, 2) learning-basse based methods utilizing graph ceastering/pooliggg and 3) baselines based on active learning.
Our main contributions arc: 1) Providing a hardness result cstablishing that, under a standard computational- complexity assumption, RS is hard to approxinate in polynomial time within any reasonable factor (this is the first subconstant hardness result for RS, to the best of our knowledge). 2) Demonstrating empirically that the existence of a homophilous graph structure between the data points can make hard RS problems effectively solvable, and 3) Developing RS-GNN for effective RS when one has access to such a graph structure and showing its merit for datasets with natural and/or similarity graphs.
2 Related Work
We group the main existing work from the literature that relates to our paper as follows. Further discussion and other categorics of related work can be found in Appendix
Active learning: In active learning [Settles 2009: Cohn et al., 1996 we have an unlabeled set of data points that we can request to label. Since labeling an expensive task, we usually have a limited budget, say, we can label up to & data points, which are then used to predict the labels of all data points. The goal is to select the set of data points to label in such way as to maximize the accuracy of the final model. The data points can be iteratively selected in mini-batches (select mini-batch, label the data points in the batch, update the model, and repeat), or in one-shot (Hoi et al., 2006 Guo & Schuurmans 2007 Chakraborty et al. 2014 Citovsky et al. 2021 Amin et al. 2020). The latter is typically used when model training is time-consuming. RS can be used in the context of one-shot active learning, or for selecting the first mini-batch in the context. of mini-batch active learning. In these contexts, a common approach to active learning is to use unsupervisod surrogate functions such as KMMdiod (Schubert & Rousseeuw 2019) and MaxCover (Hochbaum & Pathria 1998) to select set of data points that maximally cover the dataset with respect to some objective. Moreover, active learning models have been developed for attributed graphs both for mini-batched labeling (Cai et al.
2017 Gao et al.] 2018) and for one-shot (Wu et al., 2019b Zhang et al. 2021 We compare against many surrogate functions as well as one-shot graph active learning models in our experiments.
Hardness of Clustering: The hardness problem we study is distantly related to clustcring, which has come in many flavors and shapes: flat vs. hierarchical, partitioning vs. overlapping, graph-bascd vs. embedding- based vs. time-series- supervised unsupervised, etc. The interested reader may refer to references
2

---

Published in Transactions on Machine Learning Research (07/2023)
(e.g.: Hastie et al. 2009 : Kaufman & Roussceuw (2009) Gan et al. (2007): Xu & Wunsch 2005
; Jain & Dubes 1988) Xu & Tian (2015); Eaugwu et al. (2022) Silwal et al. (2023) for further information.
We do emphasize here, though, that the most similar clustering objectives to what we study here are the center-based clustering problems such as k-center and k-mcans. In these settings, the hardness results and known algorithmic guarantees (i.e., lower and upper bounds) are not far from each other. For example, while non-metric k-center cannot be approximated to within any constant, the metric special case (generalizing the ubiquitous Euclidean setting) admits 2-approximation (Gonzalez) 1985) and cannot be approximated to within better than factor 2 (Vazirani] 2013). On the other hand, the k-means objective admits a constant-factor approximation (Ahmadian et al. 2020; Kanungo et al. 2002) and the best hardness results are 1.0013 (Awasthi et al.) 2015 Lee et al.) 2017). In contrast to all these results, we present a superconstant hardness for the RS problem, stressing the big gap between any optimizable surrogate function and the true objective.
Graph clustering (community detection): Early approaches only considered the graph structure and disregarded the node features. These approaches typically learn an embedding for each node (e-g., the spectral features, random walk embeddings, or auto-encoder based embeddings) and then feed these node embeddings
into a clustering algorithm such as kmcans (sce, c.g., Cao et al. (2015); Nikolentzos ct al.
2017
Grover &
Leskovec (2016); Ye et al. (018)). ). Recently, approaches based on GNNs, which take both graph structure
and node features into account, have gained more popularity and success (Zhang et al.
2019 Peng et al.,
2021 Liu et al. 2022b Wang et al. 2019 Bo et al., 2020 Kamhoua et al. 2022 Tsitsulin et al. 2023 Graph
pooling and joint clustered representation learning approaches are also relevant (Liu al. 2022a Ding et al.,
2021 Van Den Oord et al. 2017). RS and clustering are two highly related tasks: many models developed for
RS can (in theory) be used for clustering and vice versa. However, due to the distinct propertics of the two lasks, a model that works well for one lask may not necessarily work well for the other. While our main focus is on RS, we also experiment with graph clustering and compare against several existing approaches. We also experiment with the relevant works from the graph pooling literature both for RS and clustering.
3 Notation& & Problem Definition
We use bold lowercase letters to denote vectors and bold uppercase letters to denote matrices. Let æ; represent the 7th element of and Mi represent the 7th row of M. For a function f A + B and a subset A' S A, we use m to represent the number
use fla to denote the restriction of the domain of f to A'. For dataset, of data points and n to represent the number of features. We use V = (ul.....uml to represent the set of data points and X E Rm*n to represent the feature matrix, such that X, corresponds to the features of v,. When data points have class labels, we use e to represent the number of classes. First, we define a general framework for Representative Selection (RS) as follows:
Definition 1 (RS). Given a set of data points V, their features X, a rumbee 0 << k S (V), and a utility function 2 ++ R. the representative selection problem is to select subset S C V of ls representatives that mazimize the ulility [
Note that the number of features n is unrelated to the number of data points m and the number of selected points k. The applicability and tractability of an RS problem depends on the utility function, u. Intuitively, u should capture the usefulness of the subset as a representative of V/ more precisely, if there is a particular application of the full dataset V, u quantifies the degree to which S can be used instead. This can vary with the iculir application considered; in this paper we are mostly concerned with particular utility model that associates representativeness with learnability. In the Representative Selection for Learning (RSL) problem, we get to see the labels of the selected representatives, based on which we aim to train classifier with highest predictive performance on the entire dataset.
Definition 2 (RSL). Let V be a set of data points with observed features X and with labels Y generated from on oracle function o² :V [l....,c), c), and be class of predictor functions (not necessarily containing o*) ). Given V, X, T. Φ², and number 0 < l S |V), the goal of RSL is to select subset S of k representatives from V such that training classifier & tb based on X and Yls (obtained by querying o²) marimizes the normalized uccuracy of & on the entire set V.
Note that V is implicit in the definition of u, hence in the definition of RS.
3

---

Published in Transactions on Machine Learning Research (07/2023)
The model class & defines suitable inductive hypothesis for the learning problem so that RS is well-defined. The predictor Φ is chosen to maximize the normalized accuracy, defined as Acc = c(accuracy 1/o), on the entire dataset; in other words it is transductive learning problem (Gammerman et al., 1998). RSL is a natural problem that has multiple real-world applications in dataset selection, active learning, efficient ML and other areas (see section 7 for examples). Further, it can be expected to correspond to a general notion of the representativeness of a subset, even outside a learning use case. In the rest of this paper we will focus on this version of the RS problem, and defer generalizations other utility models to future work.
We now define Graph RSL (GRSL), version of RSL for attributed graphs. We denote an attributed graph as 9 = (V, A, } where V {ui,..., Um represents the set of nodes, A E RR=m represents the adjacency matrix, and X E RmXx represents the matrix of node features (m nodes and n features).
Definition 3 (GRSL). Let g = AV be an attributed graph with node labels Y generated from on orucle function o² : VV (1, (1....,.), and + be a class of predictor funclions (not necessarily containing di ). Given 9, $ 6", and a number < S [V), the goal of GRST, is to select a subset of k representatives from V such that training a classifier
& based on X, A, and Yls (obtained by querying o*) marimizes the normalized accuracy of & on the entire set V.
4 Theoretical Findings: Hardness Results for RSL
We start by analyzing the hardness of the RSL problem. Our worst case results for RSL extend to GRSL because in the worst case, the graph can be random and provide no extra information.
We describe a theoretical finding that explains why the common practice of hand designing and optimizing surrogate functions may not be a good approach for RSL. In Definition 3 let. u(S) = Acc(o(S)) represent the normalized accuracy of the classifier & when trained on a subsct S of data points. Let S = arg max u(S) be the optimal set of representatives. Ideally, one would optimize u(S) and find St. This may, however, be impossible without a-priori having access to the labels for all data points. Alternatively, most existing works on RSL (and RS in general) focus on defining an intuitive surrogate function S2 and find a solution S by optimizing 2(S) in the hope that u(S²) is a good approximator for u(S*). In this section, we establish an inapproximability result demonstrating that u(S2) may not be a good estimator of u(S*) for any polynomial- wwwtoommil-tiiecoommme computale surrogate function Q. We do this by showing that there are naturally defined learning tasks for which there cxists significant gap between u(S²) and u(S*).
We start by studying the computational hardness of RST on an end-to-end binary classification task, from which the aforementioned claims follow. We say an RS algorithm A (e.g., optimizing surrogate function) approximates the optimal solution with an approximation factor a if we can establish that u(SA) is within a multiplicative factor a of the optimal solution u(S*) for any learning problem, where S is the output of the RS algorithm.
Under the Exponential- Timee Hypothesis (ETH) assumption, we show that there is no polynomial RS algorithm with an approximation factor better than wnn-1/pol logn). Exponential- Timee Hypothesis is assumption that is widely used in the domain of fixed-parameter tractability to prove hardness results
This assumption has also been used to show strong approximation gaps (Manurangsi (0117); Huchette et al. (2020)) The Exponential- Time Hypothesis is defined as follows.
Definition& 4 (Exponential-Time Hypothesis). There erists a posilive real number 5 such that 3-SAT con not be solved in O(22"poly(n)) time, where n is the number of parameters in k-SAT.
This is a stronger assumption than PANP. In simple words, P+NPP states that 3-SAT cannot be solved in polynomial time, while ETH states that 3-SAT cannot be solved in subexponential time.
Here, we show that there is an instance of RSL for which the gap between u(SA) and u(S*) for any polynomial- time RSL algorithm A is at least 1/poly log log"), unless ETH fails. A similar approximation gap exists between the best polynomial-time and best exponential-ting algorithm. Note that (( log log") is almost
polynomial, ruling out the existence of any constant approximation or even poly-oggarthhic approximation.
F..g., see Aggarwal& Stephens- Davidowitt) 2018): Braverman et al. 2017 2014
Chen et
2012 2021 Cygan al.
2015:; Jonsson el. al. (2033) f.okshtanov et 201T)
4

---

Published in Transactions on Machine Learning Research (07/2023)
Also note that the best solution may not give 100% accuracy, nor does it necessarily match the accuracy obtained by using all labels (since only use k).
Definition& 5 oF-t- (FoN) Learning Problem). We have m data points and n binary features. Each feature is associated with one of two types: red or blue. The types are generated independently and uniformly at random, they are consistent across data points, and are hidden from the algorithm. Each data point has value for two features and 0 for the resl. The label of a dala point if the type of its features of value are the same, and the label is 0 otherwise. The gool is to marimize the normalized accurocy for all the data points given labels only on selected data points.
Figure I visually presents an instance of the FoN problem. Each row represents data point and each column represents a feature. There are m 10 data points, each having n = 5 binary features. Each data point has a value of 1 exactly for two of the features, and a value of 0 for the rest. The types of the first and the third features are blue and the types of the other three features are red. These types are hidden from the algorithm. For the first data point, the two values of are for the first and second features. Since these features have different types, the label for this data point is O. For the second data point, however, the two values of 1 are for the first and the third features that have the same type, therefore the label for this data point is 1. The labels of the other data points are determined similarly.
n=5 binary features
Labels
1
0
0
0
0
1
0
0
1
1
points
0
0
0
1
0
1
m= 10
0
The goal of the algorithm is to select a subset with & < m data points in such a way that a model trained on the labels of those data points makes accurate predictions for all the m data points (i.e. it generalizes well to the other (m k) data points).
1
1
1
0
1
0
0 1
0
0
FoN can be naturally framed as RSL by defining the components from Defini- tion 3 as follows: let. V be the set of m data points, X E Ruxnn be the features matrix, & be the class of models that correspond to the data generation process in Definition 5 (constructed from particular partitions of features into red/blue etc.), be the budget for selecting representatives, and let the labels ø² be as defined above; the latent information consists of the types of the features. The simplicity of FoN shows that RS is hard in very broad form.
Figure 1: An instance of the FoN problem with m = 10 data points and n binary features.
Note that FoN is a basic artificial learning problem that we defined to show that there exists a hard RSL problem, and hence theoretically RSL in its most general form can not be solved in polynomial time. However, we can provide some semi-natural interpretation of this problem. Consider the following example. We have m users (corresponding lo points) and n political news articles (corresponding to features). Each article is generated by either a conservative perspective or liberal perspective. However, we are not aware of the perspective of each article. Note that each user selects two article their favorite. Each user can be represented by binary vector of features of length n, where their favorile articles are marked by 1. We say user is neutral if she likes two articles of different perspective (i.e. one conservative and one liberal). Otherwise, we say the user is supportive. The task of FoN is to learn whether a user is supportive or neutral.
The next theorem is the main result of this section.
time Theorem 1. There is no polyuomial time RSL algoritlem for FoN with an approzimation fuctor beller than w(n
1/poly -1/poll log n), unless the exponential-time time hypothesis fails.
The proof proceeds by reducing the densest k-subgraph problem to the FoN problem. In the densest k-subgraph problem, the goal is to find subgraph with l vertices and the marimum number of edges for an unweighted graph. We say an algorithm is an a-approcimation algorithm for the densest k-subgraph problem if it relurns a subgruph with k vertices where the number of edges is at least a times that of the densest k k-subgruph. It is known that there is no w boggooo) apprroiimation polmommial-time algorüthm for the densest k-subgraph problem unless ETH fails (Manurangsi, 2017).. We show how transform an input of the densest k-subgraph problem to an inpul of FoN, and then show how to transform an approrimate solution for FoN to an
Proof Sketch (See full proof in Appendix C)
5

---

Published in Transactions on Machine Learning Research (07/2023)
approzimate solution for the densest k-subgraph problem while only increasing the approzimation factor by constant. Therefore an w(n-1/poly log log ) japprrocimation polynomial-limee algorithm for the FoN implies an (fnn1/poly log log ") - -approzimation polynomial-ting time algorithm for the densest k-subgruph problem, which does not exist unless ETH fails.
To the best of our knowledge, this is the first subconstant hardness result for any RS problem. This is of particular importance because several previous works have chosen to optimize surrogate functions-these can be approximated well in theory theory-insteaad of the actual model accuracy. For instance, previous work considers a submodular surrogate function which can be approximated within factor 1/c in polynomial
time (Guillory 2012 Wei et al. 2015 Mirzasoleiman et al. 2020 Chen & Krause 2013 2021 Our hardness result implies the following.
Esfandiari et al.,
Corollary 1. In the worst case, there is significant gap of ((polyy log n) between u(S*) and the solution of any polynomial time approzimable surrogate function that estimates u(S*).
The corollary follows because such surrogate functions can be optimized or approximated in polynomial time, but Theorem [ shows that even for simple learning problems, approximating the accuracy is not possible in polynomial time (assuming the ETH); therefore, there are certain instances of the problem where optimizing for the surrogate functions does not optimize for the learning accuracy within the given approximation factor.
It is worth noting that many ML tasks are (known to be) hard to optimize, hence surrogate loss functions are commonly used in the context of deep learning: For example, finding a linear classifier with minimum 0-1 loss is NP-complete (Marcotte & Savard 1992), and convex relaxations of this loss are typically used surrogates in practice. What show in this section is that fairly simple and natural instances of the representation selection problem are not only NP-complete but also hard to approximate. Thus the optimal solution of any surrogate function will be far from the actual optimum. This gap is prominent especially when we discntangle the task of finding the set to label from the task of training a model. We will see in the next sections that combining the two remedies the problem and produces very good results, which is in line with the applicability of surrogate loss functions within deep learning models.
We would like to clarify that the above hardness result holds for the general version of the problem. In fact, this hardness result does not apply when there are some structural assumption about the model. For example this does not apply when the learning model is linear, or when the number of features in the model is a constant. Therefore, this hardness result does not contradict with the previous approximation algorithms with such structural assumptions or limitations.
5 RSL in Presence of a Graph Structure
In the previous section, we established the hardness of RSL by finding a natural problem called FoN for which RSL is hard to approximate in polynomial time within any reasonable factor. The hardness of RSL motivates sceking other sources of information about the problem that may help better guide the selection process. We next study whether the presence of graph structure in the case of GRSL can help tackle the hard RST. problem effectively, when the provided graph has degree of homophily; that is, nodes belonging to the same class are more likely to be connected to each other than nodes belonging to different classes. We present an algorithm for GRSL and provide an empirical study. Note that our theoretical finding in Section 4 is a worst-case analysis and extends to the case of GRST, because in the worst case the graph can be random and provide no extra information; connccting the hardness of GRSL to the degree of homophily of the provided graph is much more difficult problem and we leave it as future work.
Let us start by providing a visual understanding of the latent space of the FoN problem. We construct version of the FoN problem with m = 1000 data points n 10 features, where we assume the first 5 features have type red and the nexi 5 features have lype blue. For each data point, we select. two of its features uniformly at random and set their values to a number from [0.9, 1.0] (other values are 0). In Figure ((a). we present a visualization of the data points using t-SNE (Van der Maaten & Hinton 2008), where the colors represent the classes. From the visualization, we observe that there are 45 dense blocks of nodes (each having the same label) corresponding to (10) different ways of selecting the position for the non-zero elements. The
6

---

Published in Transactions on Machine Learning Research (07/202) 2023)
20-
-20
-50-
(b)
(c)
Figure 2: A t-SNE visualization of an instance of the FoN problem (the colors show the classes) when using
(a) the original features, (b) adding graph context and applying graph convolution, and (c) adding a graph context and applying variant of RS-GNN to embed the nodes and select representatives (the yellow stars represent the selected representatives).
blocks scattered in such way that it is difficult for RSL. algorithm to select a small subset such that model trained the labels of the nodes in that subset generalizes well to the other data points. This analysis is similar to the use of the contextual Stochastic Block Model (cSBM) (Deshpande et al. 2018) which has been used for understanding GNNs through both theoretical analysis (Chien et al. 2021 Baranwal et al.) 2021 2023) and empirical study (Palowitch et al. 2022 in the supervised learning setting. However unlike a cSBM, we do not have a prior distribution assumption on the node features.
We now consider a variant of the FoN problem where a homophilous graph structure between the data points is also available.
Definition 6 (GFoN). GFoN is variant of FoN where for euch pair of dala points add an edge belween them with probability p if they belong to the same class and p' if they belong to different classes. Letting >> p' ensures the graph has some degree of homophily.
Graph convolution is a popular modeling choice when a graph structure is available; it replaces the features for each node by a weighted average of the features of their neighbors, with weights proportional to the degrees. If we apply a graph convolution operation on GFoN with = 0.05 and p' = 0.01, we get the updated node features in Figure bb.. One can observe that the nodes from the two classes have high overlap and any RSL algorithm may still fail. To understand why this happens, consider four data points whose non-zero values are in positions and 2, 9 and 10, and 9, and 2 and 10 respectively. The first two nodes will have a label of 1 and the other two nodes will have label of O. However, if we disregard the node degrees, aggregating the first two nodes will give the same representation as aggregating the second two nodes.
The result in Figure bb) suggests that in presence of a graph structure, a naive application of graph convolution may not necessarily work best, and motivates the development of better modeling techniques. We show our experiments that this also holds for many existing graph dlusterin/ppoolie approaches.
To better (ake advantage of the graph structure, in the next section we develop an approach that works by learning mapping of the data points to latent space where 1- representatives that cover groups of nodes, and 2- we can better distinguish nodes belonging to each class. Figure c) shows a t-SNE visualization of the data points in the latent space and the selected representatives. One can observe that with appropriate modeling, the presence of a homophilous graph structure turns the provably hard FoN problem into an RSL problem that can be effectively solved.
group the nodes and select
We next describe our approach for leveraging the graph context for the GRSL problem. Our theoretical and empirical results motivate obtaining or constructing graph contexts for RSL problems when possible.
7

---

Published in Transactions on Machine Learning Research (07/2023)
6 RS-GNN: A Representation Learning Learning-based Model for GRSL
We observed that while a (homophilous) graph structure can be quite helpful for RSL and make hard problems effectively solvable, for this to happen one needs an appropriate modeling approach. To this end, in this section we develop RS-GNN, representation learning- maaiing-basddd approach for RS via GNNs.
Graph Neural Networks (GNNs) encode graph-structured data in continuous space (Chami et al. 2020). Graph convolutional networks (GCNs) (Kipf & Welling, 2016)
powerful variant of GNNs. Let G [V, A. X} } be an attributed graph, A = A +1 be the adjacency matrix of G with self-loops included, and D be the degree matrix of A, where D = Σj As and D,y = 0 for i + j. The 1th layer of an L-layer w(1)) can be defined as: H = o(D
GCN model with parameters θ= (W(1), where (()) represents node embeddings in the Ith layer (Hr()) = X); W is a weight matrix, and a an activation function. In the rest of the paper, we use GCN(G; θ) to show the application of a GCN function with parameters θ on graph G.
Deep Graph Infomax (DGI) (Velickovic al. 2019) an approach for unsupervised represenlation- learning in attributed graphs. Given attributed graph G, in each iteration DGI creates corrupted graph g' from G. Then, it computes node embeddings H and H' for the two graphs by applying a GNN model on them, and a summary vector s based on the node embeddings H. Finally, a discriminator is simultaneously trained to separate the node embeddings of the original graph (i.e., H) from those of the corrupted graph (i.e., H') based on the summary vector 8. We describe the details of each step later when we define our final model.
6.1 Representative Selection via GNNs
An attributed graph 9 (V, X) has two modalities, the node features X and the graph structure A. To be able to exploit both modalities in selecting good representatives, employ function EMB that combines the two modalitics into single embedding matrix of the graph. Concretely, EMB(G) = H, where H E Rn and d represents the embedding dimension. We also employ a disferentiable function SEL that receives H as input and selects & nodes as representatives. That is, SEL(H) S. The two functions are optimized in a multi-task sctting with the loss function
C= LEMB + ACSEL.
(1)
where LEMB encourages learning informative node embeddings and LSEl encourages selecting good representa- tives. One can create different RSL models with different choices of EMB, SEL, LEMB and LSEL GNNs have proved effective in learning node embeddings, so we use GNNs as our embedding function EMB. For LEMB, use the DGI objective which has shown to provide high-quality embeddings in unsupervised settings. For SEL, we consider representative embedding matrix R Rixd with learnable parameters where R is initialized randomly and RS represents the embedding for the jth representative. We let
CSEL =
= min, H. R,)),
(2)
where Dist(H,, R2) is the distance between the 7th node's embedding H; and the jth representative's embedding Ry. We use Euclidean distance as the distance function. We select the representative corresponding to each R, by finding the closest node embedding from H to Rj, i.c., argmin,(Dist H,, Rý)).
Observe that with the loss function of equation 1 the model can trivially reduce LSEL by making the values in H arbitrarily small. That is because multiplying H by a small constant may not change LEMB substantially, but can make the distances between the nodes arbitrarily small, resulting a low value for LSEL even for a random representative embodding matrix R. In the next subsection we describe normalization scheme, NonmerNorm, that is applied to H before H is used in equation 2 which helps avoid this problem.
8

---

Published in Transactions on Machine Learning Research (07 2022)
6.2 CenterNorm
As show in Appendix B using the DGI loss function results in corrupted node embeddings that form dense cluster in some part of the embedding space, and node embeddings (from the actual graph) that arrange themselves in subclusters around (and outside) this dense cluster of negative examples. Based on the this observation, we propose an & normalization of the node embeddings in H with respect to the center of the node embeddings:
HH. H. 5 H -IHH--I MlI, H = H -)/s,
(3)
where a is the center of the embeddings H, Ç is the le norms of the nodes with respect the center, and H represents the normalized embeddings. With CenterNorm, the model can no longer decrease LSEL simply by making the values H smaller. Note that since the embedding clusters in H are at large angle from cach other (cf. supplementary material), & normalization has low chance of collapsing two clusters. Furthermore, l normalization helps bring the nodes within one cluster closer to each other, which helps in identifying clusters and sclecting roprosentatives.
6.3 The Final Model: RS-GNN
The full RS-GNN model is described in Al- gorithm 1 The input is attributed graph G = (V, X) and a number & corresponding to the number of represenlative nodes that must be selected from the graph. The model initializes R (the reprosentative embeddings), θ (the GCN parameters), and U (the param- eters for the DGI discriminator). Lines 3 to compute node embeddings H using GCN model and compute DGI loss as LEMB- Here, bilinear H, 8; 8;U) = sigmoid U'*s) where H" indicates the transpose of H. Lines
Algorithm 1 The training procedure of RS-GNN.
Input: 9= = (V, A, X); A
1: Initialize R, θ, and U
2: for epoch=1 to #epochs do
3: g' (V, A, shufflee (X))
4: H GCN(S; θ) H' GCN(G';
5:
8 = sigmoid( "2 Σ: H,)
6:
p bilinear H. s; U), p' bilinear ( s;;U)
7: LEMB Σ (log(p) + log(1 pt))
8:
μ Σ, H, < H mll
9:
H CenterNorm H) (H 1)/5
CSEL E, min, Dist Dist H, Rj)
and 9 apply CenterNorm. Lines to 12 com- pute LSEL based on equation 2 and then L based equation and update the parame- ters accordingly.
11:
L = LEMB + X
12:
Compute gradients for L, upd. params. Let ft and H be the representative and normalized node
13:
embeddings with minimum L during training.
We keep track of the epoch with minimum joint loss L. Let R and H be the correspond- ing representative and normalized node em- beddings the best epoch. We select the jth representative be the node whose normalized embedding is closest to the jth representative embedding. Lines 13 to 15 select the representatives based on R and H.
14: for j=1 to k do
The 5th representative argmin, R2,
Generality: By pairing unsupervised learning approaches with appropriate normalization schemes (such DGI and CenterNorm in this paper), one extend the formulation in equation | to other unsupervised graph representation learning approaches and even to her data types (e.g., images or text). We leave this as future work.
6.4 RS-GNN for GFoN
In Figure c), we showed that RS-GNN can effectively solve the GFoN. To understand why this happens, notice that the discriminator in Algorithm I needs to distinguish the node embeddings H from H'. Since we
While GCN for direct comparability to cxisting work, note that
any other CNN model for RS-GNN. For
example, for the FoN problem Figure 2 c), used variant the GraphSage (Hamllton et 2017 model it better matched the problem.
9

---

Published in Transactions on Machine Learning Research (07/2023)
constructed homophilous graph structure, each embedding in H is the aggregation of set of nodes mostly belonging to one class, whereas each embedding in H' is the aggregation of a set of nodes that may belong to any of the classes. In order for the discriminator to be able to distinguish these two cases, the GNN model nceds to learn to map the data to a space where nodes belonging to each class are separate from each other; otherwise the aggregation of nodes (mostly) from one class may be similar to the aggregation of nodes from both classes. Moreover, the addition of LSEL motivates the model to group the nodes around a few center points giving rise the dense groups of same-class nodes in Figure] 2
7 Empirical Results
We describe our baselines, datasets, and metrics, and defer implementation details to supplementary material
Baselines: We compare against reprosentative set of baselines from different categorics, as described
below. The details for each baseline can be found in Appendix D
Random: Selects k nodes uniformly at random.
Popular: Selects the nodes with the maximum degree from the graph.
Surrogate functions on node features: We test representative set of surrogate functions: KMedoid, KMeans, Farthest First Search (FFS) You et al. 2020)] and (Greedy) MaxCover (Hochbaum & Pathria 1998). For KMeans, we select the closest node to each cluster center as a reprosentative. For FFS and MaxCover, we select representatives sequentially. In FFS, ; the next representative is the node farthest. away (by Euclidean distance) from the closest representative in the current set. In MaxCover the next representative is the node that increases the coverage of the non-selected nodes the most. For MaxCover, we experiment with RBF kernel and cosine similarities; we use MC-RBF and MC-Cos to refer to the two versions respectively. Note that the sequential nature of FFS and MC makes them less amenable to parallclization.
Surrogate functions on node embeddings: We use similar functions as above but apply them on DGI node embeddings as opposed to on the initial node features. Note that when we run these baselines using DGI embeddings as context, their selections are informed by both node features and the graph structure. Following the Spectral Clustering (Ng el. al. 2001) paradigm,, we also experiment with KMeans on spectral embeddings (i.e. top singular vectors) in two settings: 1- based on the graph Laplacian, and 2- based on the kNN affinity graph of the node similarities.
Graph posstring/pooliine rooling/uclive /ullvve learning: We compare against a number of graph clustering/ hatpnn//poooin//ccle /aclive learning approaches from different categories. Specifically, we compare against MinCut (Bianchi al.) 2020) which is a well-established pooling approach, FeatProp (Wu et al. 2019b) which is successful graph active learning approaches, SDCN (Bo et al. 2020) which is well-establish hed auto-encoder based graph clustering model, EGAE (eettal et al. 2022] and GCC (Fettal et al.) 2022) which are recent joint representation learning and clustering approaches, and DMoN (Tsitsulin et al. 2023 which is a state-of-the-ar graph clustering approach based on modularity maximization.
Datasets: We use eight established benchmarks in the GNN literature: three citation networks namely Cora, CiteSeer, and Pubmed Sen et al. (2008); Hu et al. (2020). a citation network named OGBN-Arxiv Hu et al. 2020 which is orders of magnitude larger than the previous three, two datasets from Amazon products (Photos and PC) Shehur et al. (2018), and two datasots from Microsoft Academic (CS and physics) Shchur et al. (2018). Supplementary material offers a more detailed description of datasets and their statistics. Our datasets have wide range in terms of the number of nodes (from 2K to 170K), edges (from 4.5K to 1.1M), features (from 100 to 8.5K) and classes (from 3 to 40).
We measure the quality of the selected representatives S C V using the following transductive semi-supervised node-classffication problem. We train a GCN model on the dataset where the parameters of the GCN are learned only based on the labels of the nodes in S. Note that this GCN is completely
Measures:
4The code available at: attps://githhn http::/d...nnoooogoeeeeeeeeeeeee
10

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 1:
For each dataset, each algorithm selects 2c representatives. Then, we train a GCN model on the labels of the selected representatives. The reported metric is the test accuracy of the GCN models. Bold numbers indicate statistically significant winner(s) following a t-test (p-value=0.05). The color-codes and symbols represent + surrogate functions features, + surrogate functions embeddings, and e attributed graph stustringgpoolling or active learning approaches.
Selector
Context
Cora
CiteSeer
Pubmed
Photos
Random
49.1
33.1
52.0=a.
70.2
Popular
A
59.2
35.520.5
63.3
34.910.5
+ KMeediid
X
53.7+5.4
40.3+
53.2+1a
65.8
KMeans
32.5+s.a
35.4+1.2
50.6+a.5
72.5+a.9
+ FFS
X
48.525.
39.31s.5
43.1
80.015.
MC-RBF
45.5227
25.823.7
53.019.2
78.411.2
4 MC-Cos
X
49.7+9.5
50.2+3.1
66.6+a.5
77.2+1.
KMedoid
DGI
48.424.4
31.111.9
60.925.3
81.5128
+ KMeans
DGI
62.6+9.3
42.7+6..
60.5+6.3
83.6+2.9
KMeans
Spectral(X)
48.8+0.4
19.9
45.1
81.8+0.5
+ KMeans
Spectral(A)
56.8+0.4
30.1
57.1
46.910.6
FFS
DGI
62.6+4.5
50.4+s.r
46.7+m.2
73.4+s.7
+ MC-RBF
DGI
66.3+2.
35.3+4.5
54.9+5.3
37.4+3.7
MC-Cos
DGI
67.3
49.0
67.311.
84.411.
MinCUT
X. A
51.9+7.5
37.3+s.0
59.5+a.1
14.4+7.5
FeatProp
X, A
56.6217
37.8
65.210.8
78.211.8
SDCN
X. A
41.619.
33.819.3
47.818.5
61.0210.8
EGAE
X, A
61.4138
15.0:s.s
57.715.1
83.513.0
GCC
X, A
68.7+2.2
49.326.0
63.9
84,2+1.4
DMoN
A
58.0+7.
40.527.4
55.347.5
78.629.a
RS-GNN
X,A
72.423.7
54.7.3.9
65.823.0
86.3
independent of the internal GCN model used in RS-GNN. We randomly split the remaining nodes into validation and test sets. The validation set is used for early stopping. The classification accuracy on the test set is used as the metric for mcasuring the quality of the selected representatives. Considering a validation set for early stopping reduces the chances of overfitting for the classifier and makes the reported test accuracy mainly a function of the quality of the selected representatives.
7.1 GRSL Empirical Results with Natural Graphs
The results presented in Table ! For the results in this table, set A for each dataset to be 2c, where represents the number of classes. We found this to be small enough number for meaningful comparison of the quality of the selected representatives D] and high enough for the classification GCN model to learn appropriate functions of the data. Since e is different for each dataset, making k a function also provides the opportunity to compare performance not only in terms of variation in the datasets, but also in terms of variation the number of selected representatives.
RS-GNN performs well across all datasets and consistently outperforms (or matches) the baselines (with the exception of Pubmed). It has low variance across different runs making it reliable model. Among the surrogate functions, MC-Cos and KMeans perform best. We found FFS to be sensitive to outliers. We also found it difficult to select a set of hyperparameters for MC-RBF that work well across datasets. Among graph clustering/ bustcring/pooling pooling and active lcarning approaches, we found GCC to perform best and be the only model that (overall) outperforms surrogale functions when applied on DGI embeddings. Many of the other graph clustering /pollino or active learning approaches even fall short of the MC-Cos model when applied on the node features alone, thus showing the importance of developing appropriate models for taking advantage
Note that if n, all models may perform equally well.
11

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 2:
For each dataset, each algorithm selects 2c representatives. Then, we train a GCN model on the labels of the selected representatives. The reported metric is the test accuracy of the GCN models. Bold numbers indicate statistically significant winner(s) following t-test (p-value=0.05). OOM indicates out of memory.
Selector
Context
PC
CS
Physics
Arxiv
Avg.
Random
65.4+6.1
72.9-6.0
73.6+a.s
49.0+14
58.2
Popular
A
49.9+2.1
73.1-111
50.5+0.0
31.3+0.8
49.7
KMedoid
X
66.9
51.8=1.6
66.6#1.
43.9+1.5
55.3
KMeans
70.9
66.5=0.0
7
48.4
56.2
+ FFS
71.5s3.4
54.6-2.2
76.6#2
45.2
57.3
+ MC-RBF
65.5+0.9
66.4-1.2
+8.1
51.4to.
55.5
+ MC-Cos
X
72.410.8
79.3_0.
88.311.0
50.010.5
66.7
KMedoid
DGI
69.8+3.4
82.5-2.9
81,2+7.0
OOM
+ KMeans
DGI
74.8+2.7
86.9-1.8
90.6+2.4
51.2+1.0
69.1
KMeans
Spectral(X)
68.312.3
68.5_1-1
87.710.2
OOM
KMeans
Spectral(A) (A)
51.111.5
76.8_0.3
50.520.0
OOM
FFS
DGI
63.5+6.4
84.8=6.3
83.4#6.0
48. 48.6+2.2
64.2
MC-RBF
DGI
50.7#2.5
65.2-1.2
59.8
41.2+1.6
51.4
MC-Cos
DGI
74.0
87.3-1.4
81.3+a.
47 47.6t1.
70.0
MinCUT
X, A
18.3
85.5=1.4
86.023.3
32.415.2
48.2
Feap
X.
68.5
=4.7
81.410.6
47.811.
63.8
SDCN
X, A
54.2+a.7
66.4-a.r
77.5+9.2
38,4+4.4
52.6
EGAE
X.
75.4+a.2
79.9-a.2
80,4+4.0
50.6+1.0
67.1
GCC
X. A
72.1
85.821.5
89.610.9
52.1114
70.7
DMoN
X.
70.3
84.321.1
85.923.
52.521.9
65.7
GN-G
X,A
74.3+17
89.3
90.0+2.6
52.6#1.2
73.2
Table 3: Classification accuracies when graph structure is not provided input. Selecting 5e representatives. Bold numbers indicate statistically significant winner(s) following a t-test (p-valuc=0.05).
Selector
Model
Cora
Citeseer
Pubmed
Photos
PC
CS
Physies
Avg.
Random
MLP
41.9+29
37.4+4.
51.9+5.
37.5+4.0
55. 2
76.1
7
56.7
Random
GCN
57.7+4.1
57.7 #4.5
6
79.2+a.4
71.8+44
84. 22.2
86.0+20
71.0
KMedoid
MLP
39.3
33.4
16.121.
40.6
47.520.
62.8
67.02a.
48.1
KMedoid
GCN
52.5
57.440.8
55.0za.7
72.3
63.4
66.2
70.8
62.5
KMeans
MLP
42.410.9
40.1
58.5
70.0.1.0
63. 73.72..
68.5
77.420.3
60.1
KMeans
GCN
56.510.
55.910.8
72.710.3
80.940.6
75.810.6
80.0
83.710.8
72.2
FFS
MLP
39.2+3.7
44.0+a.1
43.1+3.0
60.2+s.a
55.8+1.0
56.3+0.0
77.7+2.6
53.8
FFS
GCN
56.9+2.
62.3+a.7
48,8+3.9
80.7+2.0
74.8+2.5
59.8+2.5
84.0+2.1
66.8
MC-Cos
MLP
46.5122
17.522.
52.110.7
51.0124
58.211.2
83.01o.5
86.820.7
61.2
MC-Cos
GCN
62.021.7
63.0125
59.311.3
79.5
75.411.
87.620.3
92.810.3
71.2
RS-GNN
GCN
64.6+2.4
64.3+11
65.1+3.0
82, 82.2+2.0
75.5+2.1
88.3#1.
89.9+1.
75.7
of the graph structure and confirming our finding in Figure 2
MinCut produced degenerate solutions for Photos and PC datasets in many runs (assigning all nodes to one cluster), hence performing poorly on them.
7.2 GRSL Empirical Results with Similarity Graphs
In several applications, a natural graph may not be available. For semi-suporvised node classification, it has recently been shown that even without a natural graph, one can still leverage GNNs by learning both a graph structure and GNN parameters simultaneously (Fatemi et al. 2021
2023
We extend the aforementioned
12

---

Published in Transactions on Machine Learning Research (07/2023)
Table 4: Label coverage different RS algorithms when 2c. blue use DGI embeddings.
The surrogate function selectors marked in
Selector
Cora
CiteSeer
Pubmed
Photos
PC
CS
Physics
Arxiv
Random
86.4210.s
84.2
85.0
80.6
64.0+9.4
72.7 2..4
75.0
55.0
Popular
85.7
50.0#a.0
66.7
37.5+0o
30.0
66.7+0.0
20.0+a.0
15.0
KMedoid
100.0
100.0=a.0
66.720.
87.510.
80.0
73.32..0
60.0
50.0ao.
KMeans
100.0+o.0
83.3+0.0
100.0+a.0
75.0+o.0
70.0+o.0
46.7+0.0
60.0+a.0
65.0+o.0
FFS
84.3-11.3
88.3+..6
71.7+12.2
93.1+s.0
74.5+9.4
36.3+3.4
67.0+9.s
63.0+2.s
MC-RBF
100.0zo.
100.02o.0
66.71...
75.010.
60.02o.0
66.720.0
60.01..0
52.51o.
MC-Cos
97.1
98.325.1
100.020.9
75.020.
80.02o.o
66.720.0
100.02a.0
55.210.
KMedoid
79.3=11.8
58.3+10.1
13.3
100.0+0.0
80.0+9.2
S3.7+7.0
87.0+14.9
OOM
KMeans
100.0.o.0
90.02a.4
100.0:a.0
96.9
82.5
99.322.0
100.0
51.21s.0
FTS
96.4
86.7210.3
18.7
77.527.7
65.0
97.0
95.0ss.9
52.0
MC-RBF
71.4
81.726.1
66.710.
75.010.0
60.0
52.014.c
85.0as.a
28.1
MC-Cos
100.02o.0
100.0
100.0
87 87.520.0
82.526.
98. 1.1.5
85.0211.
37.5a2.4
MinCUT
78.628.7
83.3
95.0112.2
12.510.
10.020.
85.725.
99.0a..5
42.214.6
Peat
85. 7100
83.32..0
100.020.0
100.010.
70.020.0
60.020.0
80.01..
45, 45.010.0
SDCN
85.719.5
86.7110.5
13.3
82.518.7
67.5
72.7
87.5210-4
56.712.9
EGAE
98.6+4.6
93.3#s.6
86.7+17.2
88.8+4.0
85.0+s.6
76,7 76.7
86.0+9.7
59.2+o.8
GCC
100.0#0.0
95. 95.0=s.o
100.0#0.0
87.5+0.0
85.0#7.
92.7*a.8
100.0#0.0
72.5+a.4
DMcN
90.0
90.0210.0
91.7+14.8
87.52s.7
76.0
90.3
97.0+7.3
60.2
RS-GNN
100.0
90.02s.4
100.0
98.843.9
82.5.o.7
100.0
100.0
54.843.6
rsults to the RSL problem. In particular, we show that RS-GNN can be applied even when a natural graph structure is not available, but similarity graph of the nodes is expected to have some degrec of homophily. We assunne we have access only to the node features of our datasets, and not to their graph structures. The baselines select representatives only based on the node features. For RS-GNN, we first create a kNN similarity graph between the nodes and then run the model on the node features and the created graph. The kNN graph is computed once and then fixed during training; we leave further experiments with learning the graph structure as future work. We set the number of neighbors in kNN graphs to our experiments. Notice that all models have access the same context.
Once the representatives are selected, we train GCN classifiers the labels of the selected nodes. For the baselines, we run our classification GCN in two settings: (1) the only edges in the graph are self-loops, (2) the edges in the graph are those from a kNN similarity graph. We call the former multi-layer perceptron (MLP) and the latter a (KNN-)GCN. We report results for the top basclines that operate on node features only.
Since operating without graph structure reduces the signal the datasets, we allow each model to select representatives for the experiments in this section. The results are presented in Table K The results show that selecting representatives using RS-GNN performs consistently well on all datasets and provides boost compared to baselines many of the datasets. This confirms that even similarity graph can still be helpful in improving RSL and that RS-GNN is an effective RSL algorithm for datasets where a graph structure is not available.
We also verified the hardness the FoN problem (in the absence a graph) empirically by testing RS-GNN on the FoN problem Figure 2 where instead of the homophilous graph we use a similarity graph. For sanity check, we also tested KMeans on spectral features in this setting. Both models performed close random. These results provide empirical evidence for the hardness of RSL in the worst case.
7.3 Label Coverage
Once a set of representatives are selected from a dataset, we define a specific class label to be covered if least. one of the representatives belongs to that class. We define label coverage the percentage of class
13

---

Published in Transactions on Machine Learning Research (07/202) 2023)
Accuracy
0,0001
0,001
0.01
0.1
A
(b)
Figure 3: (a) UMAP visualization of the node embeddings and the selected representatives for Cora (colors represent the class to which the nodes modes/representatvve representatives belong), (b) RS-GNN results on Cora for different. values of X.
labels that are covered by the selected representatives. In Table 4 we report the label coverage results for the basclines and our model when selecting & = 2e representatives. RS-GNN performs well in terms of selecting points that cover all labels, with coverage of 100.0% four of the datasets. We observe an interesting phenomenon the Arxiv dataset where (unlike other datasets) many baselines outperform RS-GNN in terms of label coverage (especially GCC), but RS-GNN shows a higher accuracy compared to the baselines. We believe this is due to the high label imbalance in this dataset (the largest class has 27321 examples and the smallest has 29 examples). Tt. is also worth noting that Arxiv has the largest number of nodes, edges, and classes and the lowest number base features among our datasets. Future work can extend our work for optimizing macro accuracy across classes.
7.4 Visualization
In Figure 3 a)), we UMAP McInnes et al. (0088) to visualize the learned embeddings and the selected represcntatives of RS-GNN for the Cora dataset. The colors in the plot represent the class to which the node or the representative belongs. According to the visualization. the nodes from each class have formed one more dense clusters and our model has selected a representative from (almost all of) these dense regions of points. More visualizations can be found in supplementary material.
7.5 Time Complexity and Memory Usage
Let m represent the number of nodes, d represent the average degree of nodes, n represent the number of features (and, for simplicity, the embedding dimension), and k represent the number of representatives. The time complexity of each epoch in Algorithm [ is goverened by O(mnd) for computing graph convolusions, O(mn?) for computing node projections and bilinear functions, and O(mnk) for assigning nodes to represen- tatives. Overall, this gives time complexity of O(mn(d + n + k)) for each epoch. For large datasets where a large number of representatives is needed (i.e. k > n and k > d), the time complexity becomes O(mnk). The memory complexity is (mm) for constructing and storing the matrix distances from each node to its representatives.
When m and both large, Algorithm I may exhaust the accelerator memory due to its O(mk) complexity. To reduce the memory usage and allow for applying RS-GNN to such settings, modify Algorithm [ Algorithm 2 (in the Appendix). The main modifications include: 1- as is common in the GNN scalability literature (SCC, c.g., Frasca et al. (2020)), we replace the GCN modules with a SGC module (Wu et al. 2019a and pre-compule the graph convolutions F for the original graph, 2- we create corrupted graphs Corrapl times and pre-compute the graph convolutions F' for the corrupted graphs, 3- at the beginning of each epoch, we randomly seloct a subset F" of F' make the size match that of F, 4- we batch the data and compute the loss and gradients for each batch separately and then aggregate the gradients and update the parameters. Assuming the batch size is b, the memory complexity for Algorithm 2 reduces to ((hk) each batch can be
to
14

---

Published in Transactions on Machine Learning Research (07/2023)
Table Ablation study results for RS-GNN.
Ablation
Cora
CiteSeer
PubMed
Photos
PC
CS
Physics
Avg.
NoNorm
61.6177
41.52aa
59.6247
82.5
71.322a
86.6124
90.8
70.6
ConstNorm
59.3
44.3=42
61.7
84.2=1.4
75.0=a.1
86.7+1.a
90.5=2.1
71.7
Full Model
72.4+3.0
54.7=3.
65.8.a.0
86.3=1.4
74.3=1.7
89.3
90.0=2.
76.1
computed separately. Moreover, Algorithm 2 is also amenable to parallelization on multiple accelerators by distributing the batches across the accelerators.
Note that computing the loss separately for each batch corresponds to approximating s and μ with the batch data as opposed to the entire data, but the approximation is expected to be close to the true value the batch sizes are large enough. To this end, the batch size can be set to the largest number that does not exhaust the memory. We tested the Algorithm 2 version of RS-GNN on the Arxiv dataset when setting nCorrupt 10 and b m//s (distributing over 8 accelerators). In terms of performance, we obtained an accuracy of 52.9 + 1.6 (compared to 52.6 + 1.2 for the original algorithm) showing that the approximations do not result in performance degradation.
7.6 Ablation Study: CenterNorm and the Value of X
We conduct ablation study to verify the role of CenterNorm. To ablate CenterNorm, we our model under two settings: (1) we do not normalize (we refer to this as "NoNorm"), and (2) divide all the values in the embedding matrix by a constant number corresponding to the mean of the fn-norms of the embeddings (we refer to this as "Const.Norm"). According to the results in Table 5 our model benefits from CenterNorm and CenterNorm is more effective than ConstNorm bocause the per-node lz normalization of CenterNorm helps bring the nodes within one cluster closer to each other which helps in ideutifying clusters and selecting representatives.
To verify the sensitivity of RS-GNN to the value of X used in equation 1 we ran RS-GNN Cora with different values for X. The results are presented in Figure (()). When X = 0, the representalives will not receive gradients and hence the model ends up selecting random representatives. Therefore, the accuracy is quite low. For non-zero values of X, we observe that the model is not highly sensitive to the value of X and achieves good results for values in a large range. The model reaches its highest performance around A = 0.001, and then the performance starts slightly decrease for larger values of
8 Conclusion
In this paper, we studied the representative selection problem for attributed graphs theoretically and empirically. In the absence of a graph structure, we proved new hardness results showing is impossible to provide a polynomial-time algorithm for this problem with an approximation within any reasonable factor, unless the exponential time hypothesis fails. The hardness result explains the significant gap between the accuracy of models trained optimal representatives and the widely-used surrogate functions for RS problems, and, in turn, justifics new techniques to solve this problem. We then showed the existence of a homophilous graph structure can turn a hard representative selection problem into one that can be elfectively solved, when using an appropriate modelling technique. In light of this result we proposed RS-GNN to optimize the task of representative selection for attributed graphs via graph neural networks, and showed its effectiveness on suite of different datasets and tasks.
References
Zeinab Abbassi, Vahab Mirrokni, and Mayur Thakur. Diversity maximization under matroid constraints. In Inderjit S. Dhillon, Yehuda Koren, Rayid Ghani, Ted E. Senator, Paul Bradley, Rajesh Parekh, Jingrui He, Robert L. Grossman, and Ramasany Uthurusamy (eds.), The 19th ACM SIGKDD International
15

---

Published in Transactions on Machine Learning Research (07/2023)
Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11-14, 2013, pp. 32-40. ACM, 2013.
Divesh Aggarwal and Noah Stophens-Davidowve (gap/s) eth hardness of svp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 228 238, 2018.
Amir Hosein Khas Ahmadi. Memory-based graph networks. PhD thesis, University of Toronto (Canada), 2020.
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Comput., 49(4), 2020. doi: 00.1137/18M1177 URL https:///oi.orr//00 1t1.:////01.1117/11111122222
Kareem Amin, Corinna Cortes, Giulia DeSalvo, and Afshin Rostamizadeh. Understanding the effects of batching in online active learning. In International Conference on Artificial Intelligence and Statistics, pp- 3492. PMLR, 2020.
Martin Aumiller, Sariel Har-Peled Sepideh Mahabadi, Rasmus Pagh, and Francesco Silvestri. Fair near neighbor search via sampling. SIGMOD Rec., 50(1):42-45 49, 2021. doi: 00.1145/4471485.34777 URL
attps://doi.org// 110.001111//344455111
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. In International Symposium on Computational Geomelry, 2015.
Ramakrishna Bairi, Rishabh Tyer, Ganesh Ramakrishnan, and Jeff Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 553 563, 2015.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear scparability and out-of-distributiin generalization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 684-698 PMLR, 18-24 Jul 2021. URL https: 7/proceedings.o mlr.
html
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi- layer networks. In The Eleventh International Conference on Learning Representations, 2023. URL
https::/openreevie nett/forummddd2--333333a0
MohammadHosscin Bateni, Hosscin Esfandiari, and Vahab S. Mirrokni. Optimal distributod submodular optimization via sketching. Yike Guo and Faisal Farooq (eds.), Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pp. 1138 1147. ACM, 2018.
Aditya Bhaskara, Mehrdad Ghadiri, Vahab S. Mirrokni, and Ola Svensson. Linear relaxations for finding diverse elements in metric spaces. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Newral Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spoin, pp. 4098-4106, 2016.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In ICML, pp. 874 883. PMLR, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pp. 1400-1410, 2020.
Verónica Bolón-Canedo, Noelia Sânchez-Maroñio, and Amparo emerging challenges of feature selection in the context of big data. Knowl. Based Syst., 86:33 45, 2015.
Recent advances and
16

---

Published in Transactions on Machine Learning Research (07/2023)
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dongal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Mfine, and Qiao Zhang. JAX: composable transformations of Nuthon+Nummly programs, 2018. URL http::/github
com/google/jax /ttp:///ittibb.o//ggg///////////
Mark Braverman, Young Kun Ko, and Omri Weinstein. Approximating the best nash equilibrium in no (log n)-time breaks the exponential time hypothesis. In Proceedings of the twenty-siall annual ACM-SIAM sympostum on Discrete algorithms, pp. 970-982. SIAM, 2014.
Mark Braverman, Young Kun Ko, Aviad Rubinstein, and Omri Weinstein. Eth hardness for densest-k- subgraph with perfect completeness. In Proceedings of the Twenty-Eighe Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1326-1341. SIAM, 2017.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint XrXiv: 05085, 2017.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM, pp. 891-900, 2015.
Shayok Chakraborly, Vineeth Balasubramanian, and Sethuraman Panchanathan. Adaptive batch mode active learning. IEEE transactions on neural networks and learning systems, 26(8):1747- 1760, 2014.
Tnes Chami, Sami Abu-Fl-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprehensive taxonomy. arXio preprint arXiv:2005.000 2020.
Lin Chen, Hosscin Esfandiari, Gang Fu, Vahab S Mirrokni, and Qian Yu. Feature cross scarch via submodular optimization. arXiv preprint orXic:2107.021330 2021.
Yijia Chen, Kord Eickmeyer, and Jörg Flum. The exponential time hypothesis and the paramcterized clique problem. In International Symposium on Parameterized and Exact Computation, pp. 13 24. Springer, 2012.
Yuxin Chen and Andreas Krause, Near-optimal batch mode active learning and adaptive submodular optimization. In ICML, pp. 160 108-168.66 PMLR, 2013.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network, 2021.
Richard Church and Charles ReVelle. The maximal covering location problem. In Papers of the regional science association, volume 32, pp. 101-118. Verinner-Verly,, 1974.
Gui Cilovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning scale. Advances in Neural Information Processing Systems, 34, 2021.
David A Cohn, Zoubin Ghahramani, and Michael Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4:129 145, 1996.
Cody Coleman, Christopher Ych, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Elfficient data selection for deep learning. arXiv preprint Xie::1996. 1829, 2019.
Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipezuk, Michal Pilipezuk, and Saket Saurabh. Lower bounds based on the exponential-time hypothesis. In Parameterized Algorithms, pp. 467-521. Springer, 2015.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochas- tic block models. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (ods.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://procceddii www.gg....u..is...... wwteriisscccpppppee wwwpeecp.pppppeeeeeeeeceee..eeee http:ppp....pppp..llel//pp////// 0B52200ee22210013444400002022233
17

---

Published in Transactions on Machine Learning Research (07/2023)
Chris H. Q. Ding and Hanchuan Peng. Minimum redundancy feature selection from microarray gene expression data. In 2nd IEFE Computer Sociely Bioinformaties Conference, CSB 2003, Slanford, CA, USA, August 11-14, 2003, pp. 523 529. LEEE Computer Society, 2003.
Mucong Ding, Kezhi Kong, Jingling Li, Chen Zhu, John Dickerson, Furong Huang, and Tom Goldstein. Vq-gun: A universal framework to scale up graph neural networks using vector quantization. Advances in Neural Information Processing Systems, 34:6733 6746, 2021.
S Durga, Rishabh Tyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. In ICML, pp. 9202-9212. PMLR, 2021.
Hossein Esfandiari, Amin Karbasi, and Vahab Mirrokni. Adaptivity in adaptive submodularity, In Conference on Learning Theory, pp. 1846. PMLR, 2021.
Absalom E. Ezugwu, Abiodun M. Ikotun, Olaide O. Oyelade, Laith Abualigah, Jeffery O. Agushaka, Christopher I. Eke, and Andronicus A. Akinyelu. A comprehensive survey of clustering algorithms: State- of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743, 2022. ISSN 0952-1976. doi: https:/ /do./ooo/o///011/////// engappai.2022 0022.104743.
Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. In Neural Information Processing Systems (NeurIPS), 2021.
Bahare Fatemi, Sami Abu-al-Haija, Anton Tsitsulin, Mchran Kazemi, Dustin Zelle, Neslihan Bulut, Jonathan Halcrow, and Bryan Perozzi. Ugsl: A unified framework for benchmarking graph structure learning. 2023.
Dan Feldman. Coresets and Their Applications. Citesoer, 2010.
Dan Feldman. Core-sets: Updated survey. Tn Sampling techniques for superoised or unsupervised tasks, pp-
23 44. Springer, 2020.
Chakib Fettal, Lazhar Labiod, and Mohamed Nadif. Efficient graph convolution for joint node representation learning and clustering. In Proceedings of the Fifteenth ACM International Conference on Web Search and Dala Mining, pp. 289 297, 2022.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:8004.11198 2020.
A. Gammerman, V. Vovk, and V. Vapnik. Learning by transduction. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UA198,, pp. 148-155, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.
Guojun Gan, Chaoqun Ma, and Jianhong Wu. Data Clustering: Theory, Algorithms, and Applications. Society for Industrial and Applied Mathematics, 2007. doi: 10.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In internotional conference on machine learning, pp. PMLR, 2019.
Li Gao, Hong Yang, Chuan Zhou, Jia Wu, Shirui Pan, and Yue Hu. Active discriminative network representa- tion learning. In IJCAI, 2018.
Xing Gao, Wenrui Dai, Chenglin Li, Hongkai Xiong, and Pascal Frossard. ipool- infoonationn-aaeeeee pooling hierarchical graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Yunhao Ge, Yunkui Pang, Linwei Li, and Laurent Itti. Graph autoencoder for graph compression and representation learning. In Neural Compression: From Information Theory to Applieations-orrkeee Workshop@ ICLR 2021, 2021.
Jonathan Godwin*, Thomas Koek* Peter Battaglia, Victor Bapst, Thomas Kipf, Yujia Li, Kimberly Stachenfeld, Petar Veličković, and Alvaro Maachez-Gonzalerr Jraph: A library for graph neural networks in jax., 2020. URL http::ttt::/// httpt/thhh..cmm//maaaaaaa/aaapp
18

---

Published in Transactions on Machine Learning Research (07/2023)
Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer
Science, 38:293 306, 1985. ISSN 0304-3975. doi:
URL
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
Andrew Guillory. Active Learning and Submodular Functions. University of Washington, 2012.
Yuhong Guo and Dale Schuurmans. Discriminative batch mode active learning. In NIPS, pp- 593 600. Citeseer, 2007.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NewrIPS, 30, 2017.
T. Hastic, R. Tibshirani, and J.H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, 2009. ISBN 9780387848846.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1034, 2015.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee. Flax: neural network library and ecosystem for JAX, 2020. URL http:///itthbb.com
google/flax
Dorit S Hochbaum and Anu Pathria. Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics (NRL), 45(6):615 627, 1998.
Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Batch mode active learning and its application to medical image classification. In Proceedings of the 23rd international conference on Machine learning, pp- 417-424, 2006.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Calasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint (:Xi:2205.00087, 2020.
Joey Huchette, Haihao Lu, Hossein Esfandiari, and Vahab Mirrokni. Contextual reserve price optimization in auctions via mixed-integer programming. arXiv preprint arXix:2002.088/ 2020.
Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S. Mirrokni. Composable core-sets for diversity and coverage maximization. In Richard Hull and Martin Grohe (eds.), Proceedings of the 33rd RT Symposium on Principles of Dalabase Systems, PODS'1 Snowbird, UT, USA, June 22-27, 2014, pp. 100-106 ACM, 2014.
ACM
A.K. Jain and R.C. Dubes. Algorithms for Clustering Data. Prentice Hall advanced reference series. Prentice Hall, 1988. ISBN 9780130222787.
Peter Jonsson, Victor Lagerkvist, Gustav Nordh, and Bruno Zanuttini. Complexity of sat problems, clone theory and the exponential time hypothesis. In Proceedings of the twenty-fourth annual ACM-SIAM symposium Discrete algorithms,, pp. 1264-1277. SIAM, 2013.
Barakeel Fanseu Kamhoua, Lin Zhang, Kaili Ma, James Cheng, Bo Li, and Bo Han. Grace: A general graph convolution framework for attributed graph clustering. ACM Journal of the ACM (JACM), 2022.
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, SCG '02, pp. 10-18, New York, NY, USA, 2002. Association for Computing Machinery. ISBN 1581135041. doi: 10.1145/513400.51334 URL httpp:://oi.....
19

---

Published in Transactions on Machine Learning Research (07/2023)
L. Kaufman and P.J. Roussceuw. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley Series in Probability and Statistics. Wiley, 2009. ISBN 9780470317488.
Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrish- nan. Learning from less data: A unified data subset selection and active learning framework for computer vision. In 2019 IEEE Winter Conference Applications of Computer Vision (WACV), pp. 1289-1299, IEEE, 2019.
Krishnateja Killamsetty, Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad- match: Gradient matching based data subset selection for efficient deep model training. In ICML, pp. 5464-5474. PMLR, 2021a.
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Gener- alization based data subset selection for efficient and robust learning. In AAAI, volume 35, pp. 8110 8118, 2021b.
Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer. Retrieve: Coreset selection for efficient and robust semi-supervised learning. NewrIPS, 34, 2021c.
Thomas N Kipl and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar 1609 02907, 2016.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In NeurIPS, pp. 972 981, 2017.
Ziyi Kou, Yang Zhang, Lanyu Shang, and Dong Wang. Faircrowd: Fair human face dataset sampling via batch-level crowdsourcing bias inference. In 2021 IEEE/ACM 29th International Sympostum Quality of Service (IWQ0S), pp. 1-10, 2021. doi: 10. 24.1009/WNQ005522222000...000
Dongha Lee, Su Kim, Seonghyeon Lee, Chanyoung Park, and Hwanjo Yu. Learnable structural semantic readout for graph classification. In ICDM, pp. 1180-1185. TEEE, 2021a.
Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Information Processing Letters, 120:40 43, 2017. ISSN 0020-0190. doi: http:///dd..or/100111/////// 11.009.
Jae-Gil Lee, Yuji Roh, Hwanjun Song, and Steven Euijong Whang. Machine learning robust fairness, and their convergence. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao (eds.), KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pp. 4046 4047. ACM, 2021b. doi: 10.1145/3447548.37777 1145/3447548.34700
URL https::///// http:///oiooo//////
J.G. Lee and C.G. Chung. An optimal representative selection method. Information and Software Technology, 42(1):17 25, 2000. ISSN 0950-5849. doi: http::///doi.org/100011100 URL https:
Junhyun Lee, Inycop Lee, and Jacwoo Kang. Self-attention graph pooling. In International conference on machine learning, pp. 3734 3743. PMLR, 2019.
Chuang Liu, Yibing Zhan, Chang Li, Bo Du, Jia Wu, Wenbin Hu, Tongliang Liu, and Dacheng Tao. Graph pooling for graph neural networks: Progress, challenges, and opportunities. Xix preprint ar arXin:2204.0732 2022a.
Liang Liu, Zhao Kang, Jiajia Ruan, and Xixu He. Multilayer graph contrastive clustering network. Information Sciences, 613:256-267, 2022b.
Ning Liu, Songlei Jian, Dongsheng Li, Yiming Zhang, Zhiquan Lai, and Hongzuo Xu. Hicrarchical adaptive pooling by capturing high-order dependency for graph representation learning. IEEE Transactions on Knowledge and Data Fngineering, 2021.
20

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Yuzong Liu, Rishabh Iyer, Katrin Kirchhoff, and Jeff Bilmes. Svitchboard ii and fisver i: High-quality limited- complexity corpora of conversational english speech. In Sixteenth Annual Conference of the International Speech Communication Association, 2013.
Daniel Lokshtanov, Dánicl Marx, Saket Saurabh, et al. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, (105):41 72, 2011.
Pasin Manurangsi. Almost-polymomial ratio hardness of approximating densest k-subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 954-961, 2017.
Patrice Marcotte and Gilles Savard. Novel approaches to the discrimination problem. ZOR Models of Operations Research, 36, 1992.
Methods and
Leland Mclunes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint wxXi::1802.08426 2018
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In ICML, pp. 6950 6960. PMLR, 2020.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. Advances in neural information processing systems, 14, 2001.
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embeddings for graph similarity, In Phirty-first AAAI conference on artificial intelligence, 2017.
Jana Novovicová, Petr Somol, Michal Haindl, and Pavel Pudil. Conditional mutual information based feature selection for classification task. In Luis Rueda, Domingo Mery, and Josef Kittler (eds.), Progress in Puttern Recognition, Image Anolysis and Applications, 12th Iberoamericann Congress on Pottern Recognition, CIARP 2007, Valparaiso, Chile, November 13-16, 2007, Proceedings, volume 4756 of Lecture Notes in Computer Science, pD. 417 426. Springer, 2007.
John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp. 3691-3701, 2022.
Feng Pan, Wei Wang, Anthony K. H. Tung, and Jiong Yang. Finding representative set from massive data. In Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), 27-30 November 2005, Houston, Texas, USA, pp. 338 18-345. TEEE Computer Society, 2005.
Yunsheng Pang, Yunxiang Zhao, and Dongsheng Li. Graph pooling via coarsened graph infomax. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2177 2181, 2021.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early training. NewrIPS, 34:20596 20607, 2021.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathicu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Seikit-learn: Machine lcarning in python. JMLR, 12:2825-288 28300, 2011.
Tiago P Peixoto. Efficient monte carlo and greedy heuristic for the inference of stochastic block models. Physical Review E, (11):0114, 2014.
Zhihao Peng, Hui Liu, Yuheng Jia, and Junhui Hou. Attention-driven graph clustering network. In Proceedings of the 29th ACM International Conference on Mullimedia, pp. 935 943, 2021.
Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh. Fairbatch: Batch selection for model fairness. In ICIR, 2021.
21

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Erich Schubert and Peter J Roussceuw. Faster k-medoids clustering: improving the pam, clara, and clarans algorithms. In Similarily Search and Applications: 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2 4, 2019, Proceedings 12, pp. 171-187 18-1 Springer, 2019.
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Galligher, and Tina Fliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Burr Settles. Active learning literature survey. 2009.
Oleksandr Shchur and Stephan Günnemann. Overlapping community detection with graph neural networks. arXiv preprint arXiv: 10t:01009122,, 2019.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemman. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05800 2018.
Shubhanshu Shekhar, Greg Fields, Mohammad Ghavamzadeh, and Tara Javidi. Adaptive sampling for minimax fair classification. In A. Beygekimmer Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), NewrIPS, 2021. URL https: hatp:::://peerevieeeeee httpa/////eeeeeeeeeeeeee///////a http://eo/ooro/////d//////s.ee.
Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. Kwikbucks: Correlation clustering with cheap-weak and expensive-strong signals. In The Eleventh International Conference on Learning Representations, 2023.
Tom AB Snijders and Krzysztof Nowicki. Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of classification, 1997.
Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. JMLR, 2023.
Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete represcntation lcarning. Advances in newral information processing systems, 30, 2017.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. JMLR, 9(11), 2008
V.V. Vazirani. Approzimation Algorithms.. Springer Berlin Heidelberg, 2013. ISBN 9783662045637.
Petar Velickovic, William Fedus, William I, Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph inforax. ICLR, 2(3):4, 2019.
Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. Attributed graph clustering: A deep attentional embedding approach. arXiv preprint ar arXiv:1906.000 2019.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.
IEFE, 2014.
Kai Wei, Rishabh Iyer, and Jelf Bilmes. Submodularity in data subset selection and active learning. In ICML, pp. 1954-1963. PMLR, 2015.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision-rocused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1658 1665, 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 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 arXie: 1910. 1910.0077, 2019b.
Dongkuan Xu and Yingjie Tian. A comprehensive survey of clustering algorithms. Annals of Data Science, 2, 2015.
22

---

Published in Transactions on Machine Learning Research (07/2023)
Rui Xu and Donald Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3): 845-678, 2005. doi: (0009//NN.2005.84661
Fanghua Ye, Chuan Chen, and Zibin Zheng. Deep autoencoder-lik nonnegative matrix factorization for community detection. In Proceedings of the 27th ACM international conference information and knowledge management, pp. 1393 1402, 2018
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. NewrIPS, 31, 2018.
Chong You, Chi Li, Daniel Robinson, and Rene Vidal. Selfreepessenation based unsupervised exemplar selection in union of subspaces. IEEE Transactions on Paltern Analysis and Machine Intelligence, 2020.
Hao Yuan and Shuiwang Ji. Structpool: Structured graph pooling via conditional random fields. In ICLR, 2020.
Sepchr Abbasi Zadeh, Mchrdad Ghadiri, Vahab S. Mirrokni, and Morteza Zadinoghaddam,, Scalable feature selection via distributed diversity maximization. In Satinder P. Singh and Shaul Markovitch (eds.), AAAT, pp. 2876 2883, 2017.
Liang Zhang, Xudong Wang. Hongsheng Li, Guangming Zhu, Peiyi Shen, Ping Ti, Xiaoyuan Lu, Syed Afaq Ali Shah, and Mohammed Bennamoun. Structure- feature based graph self-adaptive pooling. In Proceedings of The Web Conference, pp. 3098-3104, 2020.
Wentao Zhang, Zhi Yang, Yexin Wang, Yu Shen, Yang Li, Liang Wang, and Bin Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. arXiv preprint Stt::108.002201 2021.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao-Ming Wu. Attributed graph clustering via adaptive graph convolution. arXiv preprint arXiv: 1T:::10060033 01210, 2019.
A
More results
Selecting more representatives: We already presented results for the case where we select 2c repre- sentatives from each dataset, where c is the number of classes. Here, we present more results for the case where we select 5c representatives from each class. We limit our baselines to the ones that were either more comperiiiive/iiformatii or took less time to run. The results are in Table G We can observe that the performance for all models improves when more representatives are selected. We can also observe that the gap between the models shrinks when more representatived are selected (even the random baseline now shows a competitive performance). Nevertheless, RS-GNN shows similar trend when selected 2c representatives and outperforms the baselines when averaged across datasets.
Visualization: In the main text, we visualized the learned embeddings and the selected representatives for the Cora dataset. In Figure aa,,, we provide a visualization for Citeseer. Similar behaviour as that of Cora can be obscrved for Citeseer, where node embeddings form clusters and a representative is selected from each of the dense cliusters.
Attributed Graph Clustering: RS-GNN can also be used for attributed graph clustering: we cluster the nodes in each dataset into groups (recall that is the number of classes) by assigning each node to its closest representative. While main motivation is RSL, for completeness
show the performance of our model for attributed graph clustering well. We note that different works on attributed graph clustering use different sellings that are not directly comparable (e.g., some works use the same hyperparameters for all datasets, whereas some other works optimize the hyperparameters for each dataset and report the best test performance). Since our setting similar to that of Tsitsulin et al.] (2023) and the results for many models have been provided in that work, we compare RS-GNN against the model proposed in (Tsitsulin et al. 2023) and their baselines. This includes KMeans, SBM (this works by estimating (Peixoto 2014)
23

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 6: For each dataset, each algorithm selects 5e representatives. Then, we train a GCN model on the labels of the selected representatives. The reported metric is the test accuracy of the GCN models. Surrogate function selectors mark in blue use DGI embeddings.
Selector
Cora
CiteSeer
Pubmed
Photos
PC
CS
Physics
Arxiv
Avg.
Random
6
47.3166
62.026a
84.02a.
83.912a
84.4gm.
54.621a
69.9
Popular
2..
43.2114
43.921.
24.1214
78.610.
50.520.
42.611.
55.0
KMedoid
6
42.1131
60.820
78.8
74.4=1a
63.911.7
64.320.
50.610.5
62.1
KMeans
66.7
53.811.3
71.620.
84.811.0
81.420.7
76.711.0
80.620.3
56.820.3
71.6
MC-Cos
71.3=2.
59.0128
64.820.
87.5104
78.320.7
88.410.2
92.420.
56.210.s
74.7
KMeans
74.9
54.314.
69.3
89.411.3
82.0=1.4
89.22o.8
02.1
55.1
75.8
MC-Cos
75.8=1.
59.8
70.622.4
90.0
82.3=1.1
89.4
86.1=1.
55.8
76.2
MinCUT
66.8
48.7 +
69.0+4.2
16.7+s..
16,5+10.2
88.6+1.2
92.3=1.p
55.3+7.
56.7
DMoN
70.1+a.a
54.9+4.6
70.2+4.0
86.7+2.4
74.8=s.a
89.7+0.7
90.9-1.s
57.1+10
74.3
RS-GNN
77.3+1.9
62.7+2.3
68. 7+2.4
90.6+0.s
83.0=1.a
90.1+o.8
92.4+o.s
56.6+1.2
77.7
Table 7: Normalized mutual information (NMT) scores between the ground-truth labels nodes and their cluster assignments. We take the results the baselines from Tsitsulin et al. (2023). Bold numbors indicate the winners. We use to indicate that the results were not reported (either because the model did not. converge, or because the model did not scale to the dataset, or because the model was tested on the datasct).
Selector
Context
Cora
CiteSeer
Pubmed
Photos
PC
CS
Physics
Avg.
KMeans
24.5
19.4
28.8
21.1
35.7
30.6
25.5
SBM
A
36.2
15.3
16.4
59.3
48.4
58.0
45.4
39.9
MinCut
X,
35.8
25.9
25.4
64.6
48.3
AGC
X, A
34.1
25.5
18.2
59.0
51.3
43.3
DAEGC
X,
8.3
4.3
4.4
47.6
42.5
36.3
SDCN
X, A
27.9
31.4
19.5
41.7
24.9
59.3
50.4
36.4
NOCD
X. A
46.3
20.0
25.5
62.3
44.8
70.5
51.9
45.9
DMoN
X, A
48.8
33.7
29.8
63.3
49.3
69.1
51.9
49.4
RS-GNN X,
55.4
41.3+1.0
26.1+s.a
58.3+1.6
50.1=0.9
75.8+1.2
56.9
52.0
constrained Stochastic Block Model (Snijders & Nowicki 1997) with given number of clusters), MinCut, AGC (Zhang et al. 2019h, DAEGC (Wang et al. 2019), SDCN, NOCD (Shchur & Günnemann 2019). and
DMoN Tsitsulin et al. 2023).
Table shows comparison of RS-GNN with the basclines in terms of the normalized mutual information (NMI) score (an established score for measuring and comparing clustering algorithms) between the cluster assignments and the node labels. From the results, can observe that RS-GNN also shows good performance for attributed graph clustering.
B CenterNorm Motivation
With the joint loss function used in the main text, the model can trivially reduce LSEL by making the values in the embedding matrix H arbitrarily small. That is because multiplying small constant to H may not change LEMB substantially, but it can make the distances bet ween the nodes arbitrarily small, resulting in a low value for CSEL even for a random representative embedding matrix R.
One way to avoid the aforementioned problem by normalizing the embedding matrix H before using it for selection. However, one should be careful about the choice of the normalization to avoid losing useful
24

---

Published in Transactions on Machine Learning Research (07/202) 2023)
(a)
(b)
Figure 4: (a) UMAP visualization of the node embeddings and the selected representatives for Citeseer. The colors represent the class to which the node or the representative belongs, (b) A UMAP plot of the DGT node emboddings for the nodes in the original graph of Cora (groen) and the nodes in corrupted Cora graph (red).
information. Before explaining how we normalize the embeddings, we describe property of DGT embeddings that motivates our normalization.
Figure [b)) shows UMAP plot of the DGI embeddings H for the nodes in the original graph of Cora and the embeddings H' for the nodes in corrupted Cora graph (red). The H' embeddings form large cluster that is mostly in between the H embeddings and the H embeddings form small size clusters that are placed around the large cluster of H'. To understand why this happens, notice that when we shuffle the node features for creating corrupted graphs for DGI training, the node features of the neighbors of each node are a random subsample of the node features the graph. Therefore, the GNN aggregation function appliod the projected node embeddings makes the embeddings go toward the mean of projected embeddings. This makes the corrupted node embeddings H' form large cluster in the middle and the embeddings H be placed outside and around this cluster.
Besides visual inspection, we also cluster the node embeddings H for Cora inlo 7 clusters using KMeans (7 is the number of classes in Cora; this provides good clusters with a normalized mutual information of 55.95 with the node labels). Then we compute the distance between each cluster center and the mean of these centers and obtain the following seven distances: 1.4, 1.2, 1.3, 1.2, 0.6, 1.4, 1.5. All cluster centers are at a good distance from the mean and, with the exception of one cluster, they are at similar distance from the mean. We then subtract the mean and compute the angle between the cluster centers. We observe that the minimum angle between two cluster centers is 60.1 degrees and the average angle is 76.6 degroes.
The above analysis motivates the CenterNorm normalization outlined in the main text. Furthermore, the analysis shows that DGI is a good candidate for RSL as it groups data points into small-sized dense clusters in the latent space, thus an RSL algorithu can select representalin atives from each of the dense clusters.
C Proof of the Theorem
Theorem 2. There is no polynomial-lime representative selection algorithm for FoN with an approzimation factor better than w(n" -1ppoly log logg, unless the ETH fails.
We start with two lemmas before proceeding to prove this result. We use (i.j) to represent data point in the FoN problem with value on features and j.
Lemma 1. Let S be the set of data points selected by an RSL algorithm. Let (1. be data point such that for all we have (i,t) & S, or for all we have (1,3) & S. Then the label of (i,5) is independent of the labels of S.
Proof. Let S be the of data points selected by an RSL algorithm. Let (i.j) be a data point such that for all I. we have (i,t) & S. This means that the labels of data points in S are independent of the type of feature
25

---

Published in Transactions on Machine Learning Research (07/2023)
i. Recall that the type of feature i is chosen independently and uniformly at random. Hence, conditioned on the labels in S, the label of (i. is 0 with probability 1/2 and 1 with probability 1/2. Similar argument holds when for all t we have (t) $ S.
]
Lemma 2. Let (fo, 11). (2), (f2, is)..... (i--1;4) it) be a sequence of data points such that for all E (I....,1} , we have (i) S. Given the labels of the data points in S we con infer the label of (io,
Proof. Consider two data points (1,5) and (j. t). If the labels of both data points are 1, then the features i, j and have the same type. Hence, the label of (). is 1 too. If the labels of both of them are 0, then the type of features i and j are different, and the type of features j and t are different. Hence, the type of features and are the same, which means the label of ti, is 1. A similar argument shows that if either (d.j) or (j, t) has label 1 and the other has label 0, then the label of (i. is O. Thus, knowing the labels of (i.j) and (j. t) determines the label of ti, Applying this inductively proves the lemma.
Proof of Theorem [ The proof goes by reducing the densest. k-subgraph problem to FoN. In the densest k-subgraph problem, we have an unweighted graph G, and the goal is to find a subgraph of G with & vertices and the maximum number of edges. We say an algorithm is an a-approximation algorithm for the densest, k-subgraph problem if it returns a subgraph with k vertices where the number of edges is at least a times that of the densest k-subgraph. It is known that there is no w(n l/poly log log ") >-apprxximation polynomial-time algorithm for the densest k-subgraph problem unless ETH fails Manurangsi (2017).
Next, we show how to transform an imput of the densest k-subgraph problem to an input of FoN, and then show how to transform an approximate solution for FoN to an approximale solution for the dens- est k-subgraph problem while only increasing the approximation factor by a constant. Therefore an (nnpool log # aapproximaaio polynomial-time algorithm for the FoN implics an w(n -1/poly log n) approximation polynomial-time algorithm for the densest. k-subgraph problem, which does not exist unless ETH fails.
Let G = (V, E) be an input to the densest k-subgraph problem for each edge in G we construct a data point. For each data point corresponding to an edge (u, v), the value of the features corresponding to vertices u and u are 1 and the value of all other features are 0. As defined in the FoN problem the type (red or blue) of each feature is chosen independently and uniformly at random.
d For cach vertex in G we define feature and
Let H = (VH, Eg) be a densest k-subgraph of G and let F be a maximal spanning forest of H. Note that since there is no cycle in F, the number of edges in IF is at most k 1. Moreover, since F is a maximal forest of HH for each edge in HI, there is path between the endpoints of in IF (otherwise we could add e to IF). Hence, if we query the data points corresponding to the edges of F, by Lemma 2 we can determine the label of all the edges in HI, which is an [e]
EEal
fraction of all data points. This gives us solution with Acc 2 2 Eg ).
Let 8 be the set of data points selected by an a-approximation RSL algorithm, and Vs be the set of vertices adjacent to the edges corresponding to the data points in S. By Lemma [ if the edge corresponding to a data point has one (or two) endpoints in V Vs. then the label of that data point is independent of the labels of S. Hence, the number of data points whose label is not independent of the labels in S is at most the number of edges induced by Vs. We denote this edge set by Es. Recall that S is an a-approximate solution, i.e., Esl = Exl). On the other hand, [S] < k and hence |Vsl S 2k. One can decompose the induced subgraph of Vs into (=) = 6 subgraphs each with k vertices, and pick the one with the maximum number of edges. This gives an 2(a) >approximate solution to the densest k-subgraph problem.
D Implementation Details
Basclincs: For KMeans, we select the closest node to each cluster center as a representative. For FFS and MaxCover, we select representatives sequentially. In FFS, the next representative is the node farthest away (by Euclidean distance) from the closest representative in the current set. In MaxCover, the next representative is the node that increases the coverage of the non-sclected nodes the most. Note that the
6 Note that graph G is not an attributed graph, rather simple graph which is an imput to the densest k-subgraph problem.
26

---

Published in Transactions on Machine Learning Research (07/2023)
sequential nature of FFS and MC makes them less amenable to parallelization. Also note that when run surrogate function baselines using DGT embeddings as context, their selections are informed by both node features and the graph structure. For the spectral embeddings, we used the top 100 singular vectors. For DMoN and MinCut models, we compute cluster centers by averaging the node embeddings with respect to the (hard) cluster assignments, and then select the closest point to each cluster center as a represenlative.
We implemented our model and the base- lines in Jax/Flax (Bradbury et al. 2018 Heek et al. 2020) and used the Jraph li- brary (Godwin* ct al., 2020) for our GNN operations. Our experiments were done on a TPU v2 for all datasets except for the Arxiv dataset where we used a TPU v3 as the experiments with the Arxiv dataset ro- quire more memory. For our DGI model, we used a single-layer GCN model with ScLU activations [Klambauer et al.) 2017 We set the learning rate to 0.001 and opti- mized all model parameters (inchuding the DGI parameters and the center parame- ters) jointly. For the experiments that had access to the original graph struc- ture, we sct the DGI hidden dimension to 512 for all datasets except for the Arxiv dataset where we set it to 256 to reduce memory usage. For the experiments with no access to the original graph structure, we set the DGT hidden dirnension to 128
Algorithm 2 Meeoory-Efficienn RS-GNN.
Input: 9 = (V, A, X), k 1: Initialize R, θ, and U
2: F = GC( F ==
3: for i=1 to nCorrupl do
4: g' (V, A, shuffle(
5: F' = concat(F", GC))")
6: for epoch=1 to #epochs do F" subsample( FF,, len F))
7:
8:
V -
for ( F(,,,(' F("") E batch (F, F") do
9:
H = WF((), H' = W FFt"
10:
11:
Compute LEMB basod on H and H' u - H;, S = | - ua||
12:
13:
H = CenterNorm( H) = (H - H)/C
14:
CSEL = E, min, Dist H, R2)
L = LEMB + ALSEL
16:
Compute gradients for L and add to V
17:
Update parameters based on V
18:
Let R and H be the representative and normalized node embeddings with minimum L during training.
as there exists less signal in this case. We trained the DGI models for 2000 epochs both for our model and the baselines. For
19:
for j=1 to k do
20: The 5th r =
(i,, R22)
KMeans and KMedoid, we used the implementation in scikit-learn (Pedregosa et al, 2011 and scikit-learn- extra respectively. To reduce the quadratic time complexity of MaxCover, we apply MaxCover on a k-nearest neighbors similarity graph in the input beatures/embeddee hyperparameters for the RBF kernel (in the case of MaxCover with RBF similarities) and kNN and reported the values that resulted in the best overall accuracy across models. For MinCUT and DMoN, we used the implementation from the DMoN paper. For our model, we set X in the main loss function 0.001 for all datasets. Also, for the experiments where graph structure is not provided as input, to create kNN graph we connect each node to its closest 15 nodes for all the datascts. For the one-shot graph active learning models, unfort unately we did not find the code to be able to test the models in our setting. Therefore, we re-implemented FeatProp (Wu et al. 2019b) and included the results of our implementation in the experiments. For SDCN, EGAE, and GCC, we used the public codes released by the authors to select representatives.
as opposed to the full graph. We used different
For the classification GCN model, we used a two-layer GCN model with PReLU activations (He et al. 2015 and with a hidden dimension of 32. We added dropout layer after the first. layer with drop rate of 0.5. The weight decay was set to 5e-4, The GCN is trained based on the nodes in the selected set S of representatives. We randomly split the remaining nodes in (V 1 S) into validation and test sets by selecting 500 nodes for validation and the rest for testing.
We ran all the experiments 20 times (except for Arxiv where we ran it 10 times) with different random seeds and reported the mean and standard deviation of the runs. Our code will be released upon the acceptance of the paper.
27

---

Published in Transactions on Machine Learning Research (07/2023)
Table 8: Dataset statistics.
Dataset
Nodes
Edges
Features
Classes
Cora
2,708
5,278
1433
7
Citeseer
3,312
4,536
3703
Pubmed
19,717
44,324
500
3
Amazon Photo
7,650
119,081
745
Amazon PC
13,752
245,861
767
10
Coauthor CS
18,333
81,894
6,805
15
Coanthor PHY
34,493
247,962
8,415
5
OGBN-Arxiv
169,343
1,157,799
128
40
E
Datasets
We used eight established benchmarks in the GNN literature. A summary of our dataset. statistics are provided in Table The first three datasets are Cora, Citeseer, and Pubmed (Sen et al.) 2008 Hu et al. 2020 These datasets are citation networks in which nodes represent papers, edges represent citations, features are bag-of-word abstracts, and the labels represent paper topics. The next two datasets are Amazon Photo and Amazon PC (Shchur et al., 2018). These two datasets correspond to photo and computers subgraphs of the Amazon copurchase graph. In these graphs, the nodes represent goods with an edge between two nodes representing that they have been frequently purchased together. Node features are bag-of-word reviews and class labels are product categories. The next two datasets are Coauthor CS and Coauthor Physics (Shchuur et al. 2018). These are co-authorship networks for the computer science and physics fields based the Microsoft Academic Graph respectively. The nodes in these two datasets represent authors, edges represent co-authorship, node features are collection of paper keywords from author's 's papers, and he class labels are the most common fields of study. Our last dataset is OGBN-Arxiv (Hu et al. 2020) which is also a citation dataset similar to Cora, Citeseer, and Pubmed, but orders of magnitude bigger than the three. The features in this dataset are average word embeddings of the paper abstracts.
F Extra Related Work
In what follows, continue our discussion of related work and provide description of categories of work that are also relevant to our work.
Feature selection: RS and feature seloction are transposed views of a similar problem when it comes to compressing or summarizing datasets. Both have been studied extensively via. filter and urapper methods: an evaluation based on final task performance or on some proxy metric such as correlation, redundancy, coverage (or more general submodular functions), or the distance of selected entities (Lec & Chung 2000 Pan et al. 2005 Bolón-Canedo et al. 2015 Bateni et al. 2018) as well their mutual information correlation with Novovicová et al. 2007). While these methods tackle the diversity
the prediction labels (Ding & Peng 2003
of the sample set (Abbassi et al. 2013 Indyk et al. 2014 Zadeh et al. 2017 Bhaskara et al., 2016), there
has also been extensive attention on taking fairness constraints into account as well (Kou et al. 2021 Roh
et al.
2021 Lee al. 2021b Shekhar et al. 2021
Aumüller et al. 2021).
Supervised data subset selection: Given large dataset of labeled training examples, class of RS models aim at selecting small representative set from the dataset to reduce training time without substantially sacrificing model accuracy (see, e.g., Killamsetty et al. (2021b Wei et al. 2015); Kaushal et al. (2019)
Durga et al. (2021); Paul et al. (2021) Mirzasoleiman et al. (2020) ). For example, Killansetty et al. (2021b) aim at selecting a set of training data points such that a model trained on these examples generalizes well to the validation set and |Mrzasoleiman et al.) (2020) aim at selecting a set of training data points whose gradients approximate the gradient of the full dataset. These models have been also appliod to mini-batch active learning where a small set of labeled data points are assumed to be initially provided and then the next. batches are selected based labudo-labels predicted by the model trained the data available
28

---

Published in Transactions on Machine Learning Research (07/2023)
far. While these models assume the data labels are available when selecting representatives, in this paper assume no labels are provided input.
Graph pooling: A technique commonly used in graph representation learning (especially for learning a representation for the entire graph) is graph pooling [Lu et al. 2022a), where the nodes of the graph are iteratively coarsened into "super-nodes". The parameters for the pooling operation are trained with the rest of the model parameters either to minimize a supervised loss (e.g., graph classification) or an unsupervised
loss (e.g., graph reconstruction) [Gao & Ji 2019 Ge et al., 2021]. Graph pooling techniques can be classified into two categories: 1- clustering pooling (these are in the same vein the graph clustering algorithms discussed carlier) and 2- node drop pooling. Clustering pooling approaches (Ying et al., 2018 Lee et al., 2021a; Yuan & Ji 2020: Ahmadi, 2020 Bianchi et al., 2020 Liu et al. 2021) employ a differentiable graph clustering algorithm and consider each cluster to be super-node; these approaches can be re-purposed for RS by selecting the node closest in the latent space each super-node as a representative. Node drop
clustcring approaches (Gao Ji. 2019 Lee al.) 2019 Pang et al.) 2021 Zhang al. 2020 Gao al.) 2021) operate by dropping unimportant nodes and relaining the important nodes the super-nodes. Graph pooling approaches have been mostly developed for smaller-sized graphs such as molecules that exhibit specific properties. For example, many of these approaches employ a GNN that assigns importance scores to each node, and then select the top-k most similar nodes. Such an approach assigns similar importance scores to highly similar nodes and results in sampling only from some parts of the graph. While this might a reasonable approach for molecule classification tasks (as makes the model focus on a few important sub-structures). may not select a subset of the nodes that cover the entire graph (which is the desired property in work). Nevertheless, in experiments, we compare against several graph pooling approaches from both categorics, both for RS and clustering tasks.
G Limitations
We identify the following limitations with our current work:
Both our model and baselines optimize for micro-average classification accuracy; optimizing for macro- average classification accuracy may require extra terms in the loss function or architectural modifications, While optimizing for micro-average accuracy is common in various domains, it raises the risk of being unfair to smaller cobbpopulations by not selecting any representatives from them. One must be cautious when using our model or any other model that optimizes for micro-average accuracy applications when such a fairness important.
29


Reviews:
[{"review_id": "ZNNeNuuiY1", "reviewer": "Reviewer_FGHE", "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- Interesting problem formulation which combines several related subproblems.\n- Theoretical results appear to be novel and correct.\n- Proposed algorithm is simple and practically motivated.\n- Good comparison to relevant baselines.\n\n### Weaknesses\n- Organization: The hardness result is based on the FoN Learning Problem, while the proposed RS-GNN is based on GFoN version of the problem. The theory and empirical contributions are only loosely connected because there are no theoretical results for the setting of the proposed method. Showing empirical performance of RS-GNN as a function of feature dimension might improve this.\n- Methodology:\n\t- Figure 4 shows that CenterNorm is quite important to the performance of the full model. Experiments would be more complete if they showed how CenterNorm can be applied to other representation learning methods (e.g. EGAE, GCC).\n\t- Visualizations use t-SNE in Figure 2 and UMAP in Figures 3-4. This should be explained or made consistent.\n- Results: \n\t- Graph-based evaluation (NMI) is less consistent/impressive than evaluating using Accuracy.\n\t- In addition to large class imbalance, it is also worth noting that Arxiv has the largest number of nodes/edges/classes and lowest number of base features.\n- Soundness: Previous work on example selection typically assumes the feature dimension $n$ is constant. This should be made very clear whenever the hardness result is compared to the constant $1 - 1/e$ approximation ratio, e.g. before Corollary 4.3.\n- Some missing optimization details (see below).\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 considers the problem of selecting representative examples from a dataset such that training a classifier on the representatives will result in a good classifier. First, the authors prove a hardness result by reduction to a special case of this learning problem to densest $k$-subgraph problem. This means that any polynomial time algorithm scales poorly in the number of features unless the Exponential-Time Hypothesis fails. Then, the paper proposes a variant of the problem in which labeled data is unavailable, but noisy graph information reveals whether two examples are likely to have the same label. It then proposes RS-GNN, a method which jointly selects representatives while learning an intermediate representation based on Deep Graph Infomax. Experimental results show that RS-GNN performs well on transductive node classification for standard GNN datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical\n- Clearly explain that $n$ is the number of features (dimension) and is unrelated to the number of candidate points $m$ or number of selected points $k$, and how this differs from related work.\n- Compute the hardness of approximation for the FoN instance shown in Figure 1.\n- Add more details/ablation about the optimization in Algorithm 1: learning rate parameters, joint vs alternating minimization.\n- In Section 7.2 mention that $k=15$ in the kNN graph (this important detail is in Appendix D).\n- Comment on whether other representation learning baselines can utilize CenterNorm, and run additional ablations if applicable.\n- Comment on drop in performance when evaluating with NMI instead of accuracy, and consider other evaluation metrics such as F1 score which better account for class imbalance. Are error bars missing from Table 7 because the results are from another paper?\n\n\n### Non-critical\n- Varying $k$ as a function of number of labels/clusters $c$ with each dataset makes sense. However, the authors should comment on what can be done when $c$ is not known in advance. Also it would be good to consider a higher number of representatives in the range $5c < k < \\min \\\\{m, n\\\\}$.\n- Mention additional related work on joint clustered representation learning: VQ-VAE [1] and a graph-based variant VQ-GNN [2].\n- Discuss/consider an appropriate regularization penalty in addition to CenterNorm and ConstNorm in Table 5.\n- Hardness results consider a problem instance where $m = 2n$. It would also be interesting to consider the case where $m \\gg n$ since this is common for many applications (including several datasets in Section 7).\n- Consider running experiments with fixed train/validation/test sets, and selecting representatives from the training set $\\mathcal{V}$. This is still a transductive learning problem, but every algorithm will be predicting on the same holdout set instead of $\\mathcal{V} \\setminus \\mathcal{S}$.\n- Figure 3(a) is less useful without comparing to baselines as in Figure 4(a)-(b). If there is not enough space, then Figure 3(a) can be moved to the Appendix.\n\n\n### Typos\n- Definition 3.2: $y$ should be $Y$\n- Section 6.2: \"have prove effective\" should be \"have proved effective\"\n- Table 4: colors are missing\n- Appendix D: \"Therefore, we For the\" should be \"Therefore, for the\"\n\n[1] van den Oord et al. [Neural Discrete Representation Learning](https://arxiv.org/abs/1711.00937), NeurIPS 2017.\n\n[2] Ding et al. [VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization](https://arxiv.org/abs/2110.14363), NeurIPS 2021. \n", "broader_impact_concerns": "Broader Impact statement sufficiently describes concerns about fairness across subpopulations.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rQtdynfseE", "reviewer": "Reviewer_STeE", "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* This manuscript studies an interesting problem, representative selection, which is of great importance from both theoretical and practical perspectives.\n* The authors theoretically proved a hardness result showing that RS is hard to approximate in polynomial time within any reasonable factor under the exponential time hypothesis.\n* The design of RS-GNN is simple yet effective. This paper further provides empirical evidence that shows the effectiveness of RS-GNN on various datasets and tasks, compared to existing methods.\n\nWeaknesses:\n* While I enjoyed reading this paper as it is almost clear everywhere, the related work section can be adjusted to be more concise. I agree that more discussion on related works could provide more background knowledge to the readers but the current version seems a little redundant, especially in comparison with the other parts of this manuscript. The authors might consider moving some of the discussions on the related works to the Appendix for a more concentrated demonstration.\n\n* It would be better to introduce more on the ETH assumption and the background of the Fit-or-Not learning problem as well as their relationship to the RS problem in previous literature. This could make the theoretical findings better understood by audiences that are not from this research direction. Meanwhile, the connection between the Fit-or-Not learning problem and the used benchmark datasets is unclear. The authors are suggested to justify this relation by analysis of synthetic datasets or discussing examples of how the Fit-or-Not learning problem is usually employed in practical scenarios.\n\n* The authors set the number to be $kc$ where $c$ is the number of classes from datasets. However, $c$ could be unknown in many applications. Could the authors provide more insights on how to select the number of representatives during practice? Potential sensitive analysis might help the authors to choose this hyperparameter.\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": "The paper tackles the problem of representative selection (RS), which is the problem of finding a small subset of exemplars from an unlabeled dataset, and has numerous applications in various domains. The paper focuses on finding representatives that optimize the accuracy of a model trained on the selected representatives. The paper studies RS for data represented as attributed graphs, where each node has a feature vector and a graph context specifying the connections between nodes. The paper develops RS-GNN, a representation learning-based RS model based on Graph Neural Networks (GNN). The paper demonstrates the effectiveness of RS-GNN on problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established baselines that optimize surrogate functions. The paper also establishes a new hardness result for RS by proving that RS is hard to approximate in polynomial time within any reasonable factor, which implies a significant gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model, and provides justification for the superiority of representation learning-based approaches such as RS-GNN over surrogate functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please kindly refer to Section Strengths and Weaknesses for detailed suggestions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GM17GygIgM", "reviewer": "Reviewer_Mgut", "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(+) Interesting hardness results for RSL.\n\n(+) Strong empirical performance of the proposed RS-GNN model.\n\n## Weaknesses\n\n(-) Lack of discussion and comparison to the relevant contextual stochastic block model literature.\n\n(-) The introduced side-information (homophilous graph) makes the RSL problem a different problem, and the hardness of this problem is unclear in this paper.\n\n(-) The hardness results kind of contradict the claim that RS-GNN can work without graphs (i.e., case of graphs induced from node features).\n\n(-) The experiments heavily rely on the graph models and graph datasets (even if the authors exclude the graph in some experiment). It should also be tested on standard classification benchmarks if graph is really a ``side-information``, especially RS-GNN is claimed to work when even when the graph does not exist.\n\n## Detail comments\n\nWhile I like the methodology of the paper and the interesting hardness result of RSL, I think the flow of the paper is problematic and misleading. Firstly, I feel the authors should directly start with the problem of RSL with graph instead of formulating the (homophilous) graph as the ``side-information`` of the original RSL problem. Note that all the downstream evaluation heavily relies on the (supervised) performance of GCN. I feel it is misleading to merely term the graph as a side-information, as it seems to be the ``main source’’ of information for the problem.\n\nIf we view the studied problem as RSL with graph, then it is natural to relate it to the contextual stochastic model (cSBM) literature [1]. In fact, the GFoN model given by the authors in section 5 is very similar to cSBM, except that there is no prior distribution assumption (gaussian in cSBM) on the node features. Note that cSBM emerges as an important attributed random graph model for GNN analysis in both theory and practice [2-4], albeit they focus on (semi-)supervised learning setting. Nevertheless, the cSBM paper [1] itself and its follow-up study the community detection problem and information theoretical limit is established. I think the authors should discuss the relation of their work to cSBM and use cSBM algorithms (or even SBM algorithms) as baselines in the experiments. For example, simple spectral clustering (instead of MinCUT) with Kmeans.\n\nFinally, I find the hardness results for RSL kind of **contradict** with the strong empirical performance of RS-GNN when the graph is induced from node features (Section 7.2). Note that in this case, the problem is exactly the RSL problem without any ``side-information``. Thus, the hardness result proved in Section 4 should still applied. In this point of view, I wonder how the RS-GNN can still perform well? Based on Theorem 4.2 (hardness result), there should be a hard example (as proposed by the author) that RS-GNN does not work in this case. I understand that RS-GNN without graphs may work well in practice but the flow of the paper is contradicting this fact. Also, I feel the authors should test RS-GNN without graphs on the hard example constructed in Section 4.\n\n\nMinor: why use $m$ instead of $n$ to denote the number of nodes? I don’t see any reason for detouring from the standard graph learning literature.\n\nIssue: The footnote on page 10 violates the double-blind policy of TMLR. Please make sure the paper is properly anonymized.\n\n## References\n\n[1] Contextual stochastic block models, Deshpande et al., NeurIPS 2018.\n\n[2] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization, Baranwal et al., ICML 2021.\n\n[3] Effects of Graph Convolutions in Multi-layer Networks, Baranwal et al., ICML 2023.\n\n[4] Adaptive universal generalized pagerank graph neural network, Chien et al., ICLR 2021.\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": "The authors study the problem of Representative Selection for Learning (RSL), which aims to learn a subset of points (in unsupervised setting) such that the downstream model trained on this subset of points (in supervised setting) has performance as good as possible. The authors first provide a hardness result of the problem, then introduce the homophilous graph as the side-information. Finally, the authors propose RS-GNN model for RSL and demonstrate strong empirical performance against baseline methods on eight benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discuss the relation to cSBM [1] and compare with methods that works well or achieves information limits for cSBM in unsupervised setting.\n\n2. Conduct experiments on synthetic datasets constructed as described in Section 5. Especially test RS-GNN without graph (induced by node features) on the hard example constructed therein and cSBM.\n\n3. Can we say anything about the GFoN problem in theory?\n\n4. Instead of termed graph as ``side-information``, I think it should be a new problem termed like RSL with graph or something similar. If the authors insist on calling the graph ``side-information’’, I feel the authors should justify that the graph is indeed not the major source of information.\n\n5. One way of resolving bullet 4 above is to conduct experiments on standard classification benchmarks using RS-GNN with node feature induced graph. If RS-GNN can still outperform baseline methods in standard classification benchmarks, then I guess calling the graph a ``side-information`` sounds more reasonable.\n", "broader_impact_concerns": "I do not aware of significant ethical or social impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See above.
Decision: Accept (poster)