Adjusted Count Quantification Learning on Graphs
Authors: Clemens Damke
Eyke Hüllermeier
Venue: NeurIPS 2025 poster ()
Keywords: quantification learning
graph neural networks
distribution shift
Primary area: general_machine_learning
TL;DR: We extend Quantification Learning to graphs and propose two new structure-based extensions to the Adjusted Count approach.

Abstract: *Quantification learning* is the task of predicting the label distribution of a set of instances.
We study this problem in the context of graph-structured data, where the instances are vertices.
Previously, this problem has only been addressed via node clustering methods.
In this paper, we extend the popular *Adjusted Classify & Count* (ACC) method to graphs.
We show that the prior probability shift assumption upon which ACC relies is often not applicable to graph quantification problems.
To address this issue, we propose structural importance sampling (SIS), the first graph quantification method that is applicable under (structural) covariate shift.
Additionally, we propose Neighborhood-aware ACC, which improves quantification in the presence of non-homophilic edges.
We show the effectiveness of our techniques on multiple graph quantification tasks.

Adjusted Count Quantification Learning on Graphs
Clemens Damke LMU Munich, MCML cl clemens. daw.eeiifiiiiii.. 1mm.mmmeee de
Eyke Hüllermeier LMU Munich, MCML, DFKI eyke@lmu.de dee
Abstract
Quantification learning is the task of predicting the label distribution of set of instances. We study this problem in the context of graph-structured data, where the instances are vertices, Previously, this problem has only been addressed via node clustering methods. In this paper. we extend the popular Adjusted Classify & Count (ACC) method to graphs. We show that the prior probability shift as- sumption upon which ACC relies is often not applicable to graph quantification problems. To address this issue, propose structural importance sampling (SIS), the first graph quantification method that is applicable under (structural) covariate shift. Additionally, we propose Neighborhood-aware ACC, which improves quan- tification in the presence of non-homophilic edges. We show the effectiveness our techniques on multiple graph quantification tasks.
Introduction
We consider the task of quantification learning (QL) on graph-structured data. This term was first coined by Forman [8, 10] and is used describe the task of estimating label prevalences via supervised learning. A QL method receives a set of training instances with known labels, which is used train a quantifier. The quantifier is then used predict the label distribution of set of test instances. Unlike standard instance-witg classification, QL does not concern itself with predicting an accurate label for each test instance but rather with predicting the overall prevalence each label across all instances. QL can thus be seen dataset-level prediction task, where single prediction made for population of instances.
Quantification problems naturally arise in polling and surveying, where the goal is to estimate the proportion of population that has a certain property holds certain opinion. Examples include estimating the proportion of voters who support a certain political party or the proportion of cus- tomers who are satisfied with product. Similarly, QL can be applied epidemiology or ecological modelling to estimate the prevalence of diseases or species in given population. We refer to Esuli al. [5] for comprehensive overview of the applications of quantification.
Typically, QL is studied in the context of tabular data, where each instance x E X'= RRd is repre- sented by feature vector. In this setting, instances assumed be independent, i.e., the label distribution P(Y) X= applications. this independence assumption does hold. Consider the example of estimating the proportion of voters supporting a certain party. Assume we have access to a social network where each node represents voter and each edge represents social connection. In this case, the label distribution of voter, i.e., their political preferences, may depend not only on their own features but also on the features of their social connections. Incorporating this relational information into the quantification process can lead to more accurate estimates.
= x)) is fully determined by the instance x. However, many real-world
Generally speaking, QL methods aggregative. Aggregative quantifiers rely upon an instance-wise label estimator, i.e., a regular clas- sifier; the instance-level label estimates are then aggregated obtain dataset-level label prevalence
be divided into two categories: aggregative and non-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

estimates. Non- Von-aggregative quantifiers, on the other hand, directly estimate dataset-level label preva- lences without first predicting labels for each instance. In this paper. we focus on aggregative quan- tification methods, which are more common and have been studied more extensively. An intuitively plausible aggregative method to simply estimate the prevalence of a label as the fraction of test instances that are predicted to belong to that label by the classifier. This method is known as Classify & Count (CC) and, given a perfect classifier, it will yield perfect quantification results. However, in practice, classifiers are not perfect, and even a good but not perfect classifier can lead to poor quan- tification results. Conversely, even a bad classifier can yield good quantification results. The reason for this disconnect is that the optimization goals of classification and quantification More specifically. while a good binary classifier should minimize the total number of misclassifica- tions, i.e., (FP + FN), a good binary quantifier should minimize |FP- FNJ. If FP FN, even classifier with a high misclassification rate will yield perfect quantification results.
misaligned.
This misalignment is commonly addressed by the family of Adjusted Classify & Count (ACC) meth- ods, which use an estimate of the classifier's confusion matrix to adjust the predicted label preva- lences [35, 29, 8]. ACC has been shown to estimate the true test label prevalences in expectation if the so-called prior probability shift (PPS) assumption holds [33].
In this paper, we investigate ACC in the context of graph-structured data and describe why it is oftentimes ill-suited to tackle graph quantification problems. To solve this problem, we propose two novel methods for graph quantification learning: Structural importance sampling (SIS) and Neighborhooddawarr ACC (NACC). First, SIS generalizes ACC to the (structural) covariate shift setting; to our knowledge, this is the first quantification method that tackles covariate shift systemat- ically. Second, NACC further improves the quantification performance of ACC in the graph domain by improving class identifiability in the presence of non-homophilic edges. We begin with brief formal description of the general quantification problem in Section 2. In Section 3 we then consider graph quantification and introduce our novel SIS and NACC methods. In Section 4, the proposed methods are evaluated on a series of datasets under different shift assumptions. Last, we conclude with brief outlook in Section
2 Quantification Learning
Let X denote the instance space and y {I,..., K} the (finite) label space. In QL we assume to be given a training set of labeled instances Dr C X' x y drawn from a distribution P with corresponding density p. Additionally, there a set of labeled instances Du S X x y drawn from a test distribution Q with corresponding density Let X and Y denote random variables (RVs) that project the joint instance-label space to the instance and label spaces, respectively. The goal of QL is to estimate the pushforward measure Q(Y) given samples Dr, and X/ = {x (z, y) E Du }. If P = Q, i.e., the training and test data are drawn from the same distribution, the quantification problem is trivially solved via maximum likelihood estimate of the label distribution on Dz:
@MLPE =i) [Del (x.9)ED2
1
Σ1yy=1]
where [-] denotes the indicator function. This Maximum Likelihood Prevalence Estimation (MLPE) approach [1. 5] is akin to the majority classifier in classification in the sense that predicts the most likely distribution in the absence of test data Ny. However, if the training and test data are not identically distributed, the quantification problem becomes more challenging. A quantification approach has to account for the distribution shift between P and Q to provide accurate estimates of Q(Y). Depending on the nature of this distribution shift, different quantification methods may be more or less suitable.
2.1 Types of Distribution Shift
If the train and test distributions differ, one should ask whether learning from the training data is still feasible. Certainly, if P and Q are completely unrelated, any information learned from D2 is useless for predicting QYY). Quantification approaches, therefore, typically assume that P and Q are related in some way. The applicability of a quantification method then depends on whether those assumptions hold true for the given problem. First, note that Q can be expressed as
Q(X,Y) Q( [x)((X) = Q(x ()Q())

---

By fixing one of the factors in the two right-hand terms, we obtain three types of distribution shifts [5]:
1. Concept Shift: The conditional label distribution changes, but the distribution of the in- stances remains the same, i.e., Q(Y X) + P(Y X)) while Q(X) = P(X). This type of shift, also referred to as concept drift, can occur in domains with classes that are defined relative to some frame of reference.
2. Covariate Shift: The distribution of the instances changes, but the conditional label dis- tribution remains the same, i.e., Q(X) o P(X), while Q(Y | X) = P(Y X). This is common in domain adaptation, where the training and test data are drawn from different but related domains. For example, assume the task is predict the prevalence of a certain sentiment or opinion in social media posts, The training data may be drawn from one social media platform, while the test data is drawn from another. Given a post æ, the probability of it expressing a certain sentiment y is likely the same on both platforms, but the distribution of posts may differ.
3. Prior Probability Shift:
The label distribution changes, but not the class-conditional in- stance distribution, i.e., Q(Y) * P(Y), while Q(X Y) = P(X Y). Similar to covariate shift, prior probability shift (PPS) occurs between domains that share the same label concepts. For example, consider the task of predicting the percentage of a population that has a certain disease. The training data may come from a case-control study consist- ing of an equal proportion of healthy and infected individuals, while the test data drawn from the general population. Given y (infected, healthy); }. the feature distribution of an individual r should be the same between training and test, whereas the prevalence of the disease will likely not be.
We do not consider the case where Q(Y) = P(Y), as this would imply that the label distribution remains unchanged, in which case the quantification problem is trivially solved by MLPE. Note that the difference between covariate shift and PPS is subtle. Whether it is P(X) or P(Y) that changes between training and test is mostly a matter of the assumed causal relation between instances and labels, i.c., whether it in the direction X' + y or y + X' [6. 30. 18]. In QL. PPS is commonly assumed, as there are many y + X' domains in which this is reasonable [15]. Generally speaking, quantification under concept or covariate shift is more challenging and often requires additional assumptions or domain knowledge. We will get back to the question of which shift assumptions are appropriate for a given domain in Section 3.
2.2 Adjusted Count
We will now describe the Adjusted Classify & Count (ACC) method, a popular approach to quan- tification under PPS [8]. As mentioned in the introduction, the naive Classify & Count method (incorrectly) assumes that the predicted label prevalences of a classifier h h: - y equal the true label prevalences, i.e., that Q(Ý) = Q(Y), where y = h(X) is RV representing the predicted label. Under this assumption, the label prevalences can be estimated
Q = i) = Q(Ý = [e
Σ1((()) = ViEy.
TEAU
However, since h trained on data drawn from P, the estimated propensity scores (CC will be biased towards P(Y) in practice. ACC removes this bias by adjusting the predicted label prevalences based on an estimate of the classifier's confusion matrix. To understand ACC, note that the PPS assumption implies that for any measurable mapping X + Z, we have P(Z Y) QZ Y) where = x(X) [19]. This allows us to factorize Q(Z) as follows:
K
K
Q(Z) = Σ
= PPS Q(Z) = Σ = =)
(3)
1=1
Let δ i... Z Y; then, we can plug the estimate of Q(Ý) from Eq. (2) and the estimate
Σ 1(h(2)) Ag 2]
-(= jj jill =) P( = =jly= 1((x,)) E EDr, = i}
(..N)ED.
Vi.j e
(4)
3

---

of Q(9 Y) into Eq. (3). This yields system of equations which can be solved to obtain estimates
of Q(Y) [29]. Let C [0, 1]Kx4 x be the estimated confusion matrix of the classifier h on Q, i.e.,
C₁, = = Y = =). Then, the ACC estimates of Q(Y) are given by
QACO(Y) = Č- Q()).
(5)
While the binary version of ACC goes back at least to Gart and Buck [11], it was first described as quantification method by Vucetic and Obradovic [35]. Tasche [33] showed that ACC is an unbiased estimator of the true test label prevalences if the PPS assumption holds.
Note that there are two practical problems with Eq. (5): First, if C is not invertible, there might be no or multiple solutions for (Y). Second, the adjusted label prevalences may not be a valid distribution over V' i.e., they could lie outside [0, 1] or not sum to one. Possible reasons for this are that the PPS assumption might not be (fully) satisfied or simply that the estimates Ć and Q(Ý)) are noisy, e.g., due to small sample sizes. A number of solutions to these problems have been proposed in the literature, including clipping and rescaling the estimates [10], adjusting the confusion matrix [19), using the pseudo-inverse of C, or replacing the system of equations with constrained optimization problem [3]. In this work, we will use the latter approach, i.e., constrained optimization, solve Eq. (5):
QXCO = arg min qeAx
C c- Q
(6)
where Ag denotes the unit (K- - s)-simplex. This problem can be solved numerically, e.g., using (quasi-Newtonian method such Sequential Least Squares Quadratic Programming. Bunse [3] has shown that this approach is a sensible default choice, as it generally performs well in practice.
In addition to the CC and ACC methods described above, which use hard classifier h X' + y, one can also use probabilistic classifier h2 : X + k [2]. Analogous to CC, Probabilistic Classify & Count (PCC) is defined as
Iha(a)) (1) X xENU
Likewise, Probabilistic Adjusted Classify & Count (PACC) estimates Q(Ý) and p(ý Y) using predicted label probabilities. The motivation for using soft classifier instead of hard one is that predicted label probabilities can be more informative than hard labels. Whether this is truly the case groblem--ependenn and depends on the quality of the predicted probabilities.
3 Graph Quantification Learning
We now turn to the problem of quantification learning on graph-structured data. In Section 2, we assumed that the instances in Dr and Dy are i..dd wrt. P and Q respectively. This assumption does not hold for graph-structured data, where the instances are the vertices of a graph and the labels are associated with the vertices. More specifically, let g (V,E) be a graph with vertex set V and edge set 3 C V x V. Each vertex U/ E V is associated with a feature vector 2; E X and label Y/4 E Y. We use (v;s)) = {u, I (v,, E E} to denote the set of neighbors of e;- The edges in G are used to encode homophily between vertices, i.e., similar vertices are more likely to be connected, Formally, an edge (v,, v2y) E E should indicate that P(y; = Uy) 2 e, with being either graph-specific constant or a function of an edge weight Wiyj RR Since homophily is symmetric by definition, G is undirected, i.c., uy) E E + (v),0)) U.) E E. Such homophilic graphs are commonly used to represent social networks, citation networks, co-purchase graphs, or the World Wide Web. Figure 1 shows one such graph, namely the Amazon Photos co-purchase graph [32], where vertices represent products, edges indicate that two products are frequently bought together, and labels represent product categories. Due to homophily, the product categories form separate densely connected clusters, while cross-category edges are sparse.
Analogous to the tabular case, in graph quantification learning (GQL) we are given a training set of labeled vertices D,, C V x y drawn from a distribution P and our goal is to estimate the label distribution of the vertices in test set Vo drawn from a distribution Q(V), with denoting RV mapping the joint measure space V y to V. Given some vertex classifier h V + Y, the GQL

---

Figure 1: The Amazon Photos co-purchase graph. Colors indicate vertex labels (K 8). The highlighted vertices are misclassifications by an APPNP classifier.
problem is, in principle, amenable standard aggregative quantification methods, such ACC or PACC. As discussed Section 2.2, those adjusted count methods assume PPS, which in turn assumes
domain. This means that, both, the training and the test data are assumed to be generated by sampling from some fixed distribution P(V = i) for all E y. We argue that this often not realistic for graph-structured data.
Consider the example of estimating the proportion of users holding a certain opinion. Here, the training data D2 may come from social network where (non-representative) local subset of users was sampled. The test data Dy. on the other hand, may come from the entire social network possibly some local subcluster of interest. In this setting, it is the instance distribution P(V) that changes, while P(Y | V) remains fixed, i.e., covariate shift. More generally, for a sampling process that is structure dependent, for example, by sampling local training test neighborhoods, the covariate shift assumption is more appropriate than PPS. We will now discuss how such structural biases be accounted for in the quantification process.
3.1 Structural Importance Sampling
ACC depends on being able estimate the test confusion matrix C from training data. As de- scribed, this is trivial under PPS. We will now introduce structural importance sampling (SIS), novel generalization of graph quantification learning to covariate shift. First, note that Cj, can be expressed as
Cj. I(h(v) jldQ(v = v i) = 1[h(v) 5] QVIY (v ii) VEV
dP(V = 1 Y =) (8)
Pvly (1
VEV
=Pyly (v18)
with Qvly dQ(VlY) and Pvly dP(V du denoting the Radon-Nikodym derivatives of Q and P and μ a (counting) measure on i.e.e their probability density functions (PDFs), and Pvir denoting the ratio between those PDFs. Using the covariate shift assumption, we get
du
(V v) = (v v) dr ())p()))r(
(v v) PrIv(y ())g(()))()) pv(u) (x)
(9)
Thus, C can be obtained by reweighting the vertices:
C₁,+ (i) Jv (h()) (VV(()) =olY=
( = (pr
(10)
(1) Jy pv (b)dP(VV = Y
Given Dr, we can obtain an unbiased estimate of C₁,² Q(Ý = j =):
Σ1((v)) AAy (v)
0 = (Ma))D)
(11)
m = (v
(v.g)eD,
5

---

Note that this is essentially weighted version of Eq. (4), The problem with this formulation is that it requires Pv pv'
gy which cannot be computed since. both, P(V) and Q(V) are unknown. We do, however, have access to samples from both distributions, i.e.. D,, and Vy- Using suitable vertex kernels kng kp V x V + R. we can thus obtain estimate of the PDFs via kernel density estimation:
iv (v) = |Vol
Σ (u, 0') N'eVV
and Pv(c)= = IDEl
knp(,,) (w'N))DD
(12)
The suitability of the kernels depends on the nature of the distribution shift. Intuitively, h (v, v²) and kp(v, v²) should be proportional to the probability of sampling vertex u from Q(V) and P(V), spectively, given that o' has been sampled. For example, the constant kernel k2 (v. 0') describes sampling process where the probability of sampling is independent of v'. Using Kg k, 11, Eq. (11) simplifies to standard ACC (cf. Eq. (4)), i.e., SIS is a generalization of ACC.
Under (structural) covariate shift, ky and kp should be chosen in accordance with the sampling process. Since the family of structural shifts is broad, there is no single, generally applicable kernel. Nonetheless, if the shift is induced by a localized sampling process where vertices are sampled via random walks (RWs), the probability of sampling u given is proportional to the number of RWs between both vertices. This probability can be computed via the personalized page-rank (PPR) algorithm [26]:
EyPR(";, 15) TTiy where II = (1-[+(1))AA)
(13)
Here, A = AD-1 is the normalized adjacency matrix of the graph, E (0, 1) is teleportation parameter and L is the number of steps in the random walk. We found that kppR is good default for localized structural shifts. Nonetheless, depending on the problem domain, other choices might be more appropriate. more in-depth discussion of the kernel selection can be found in Appendix B. 1. A formal analysis of the computational complexity of SIS under different kernel choices is provided in Appendices C.1 and C.2.
To summarize, SIS enables graph quantification under covariate shift by estimating Q(Ý Y) using kernel density estimates of the vertex distributions P(V) and Q(V). Using these estimates, the adjusted label prevalences can be computed using Eq. (6).
3.2 Neighborhood-awaree Adjusted Count
In the previous section, we extended GQL to covariate shift. Next, we will address another or- thogonal problem of ACC: Class identiftability. Consider classifier h that unable to distinguish between two classes i and j. i.e., it predicts the same label for both. In this case, C., = C.j² thus, there is unique solution for Eq. (5). This can lead to poor quantification results if the prediction vector Q(Y) has large overlap with, both, C.,, and C.,,, since any distribution of probability mass between both classes may then be returned. To address this issue, we propose Neighborhood-aww aware ACC (NACC), which uses the neighborhood structure of the graph to improve class identifiability.
First, note that Eq. (6) can be understood as finding a mixture of the columns of C that best approx- imates Q(Y). In the case of collinear columns, this mixture is not unique. A simple way to break such symmetries is to set Z = YYx in Eq. (3), where Ýx² is a RV representing tuple of the predicted label of a vertex and the majority predicted label of its neighbors:
= =(xx=(),))) = Σ QPP~ - (1,A) Y = 1) 00 =
Using this decomposition of Q(Êx)), Q(Y) can be estimated using ACC and, possibly, SIS. Intu- itively, this approach uses homophily information to improve class identifiability. Consider Fig. 1, where a vertex is highlighted if misclassified by an approximate personalized propagation of neural predictions (APPNP) classifier [12]. Note that the vertices with label 7 (dark green) are often confused with vertices of label (blue) or 6 (orange) because there are many non-homophilic edges between those classes. Using ACC, this would imply that the row vectors of labels 7, and 6 are collinear, i.e., C.7 R a C.1 + (1 - a) C. for some a E [0, 1). Using the neighborhood struc- ture, NACC can break this symmetry. For labels and 6, the majority of predicted neighbors will

---

nearly always be of the same label due to homophily, whereas for label 7, both, YN (1,6) and YN- (6. 1) are common. With this information, NACC is able to distinguish the confusion profile of label 7 from those of labels and 6.
In principle, one could extend NACC to use even more neighborhood information, e.g., by consid- ering the majority label of the neighbors of neighbors or by considering the second-most predicted neighboring label. However, given finite training set Dr., by making the confusion profiles more fine-gra sine-grained, the confusion estimate Ć will become noisier, counteracting the potential gains of ad- ditional information. We found that using the 1-hop majority label a good trade-off between class identifiability and confusion estimate noise. An analysis of the computational complexity of NACC can be found in Appendix C.3.
Evaluation
We assess the performance of SIS and NACC on series of graph quantification tasks using, both, PPS and covariate shift. The quantifiers are applied to the predictions of a set of node classifiers As a baseline we compare our proposed GQL methods with MLPE, (P)CC and (P)ACC. We build upon the QuaPy Python library (BSD 3-Clause). Further details can found Appendix A.
4.1 Experimental Setup
Quantification Metrics There is a large number of metrics to evaluate quantification methods [5]. We use Absolute error (AE) and relative absolute error (RAE):
1
9. qel
AE(g. 9)
q
qul
RAE ②)
(14)
K
qi
AE penalized all errors equally, whereas RAE [16] penalizes errors on rare labels more heavily.
Datasets Since the literature on GQL is scarce, there are no established benchmark datasets for this task. For this reason, synthetically generate quantification tasks from the following five node classification datasets: 1. CoraMI, 2. CiteSeer, 3. PubMed, 4. Amazon Photos and 5. Amazon Computers [21, 14, 13, 31, 25, 20, 32]. The first three datasets are citation networks, where the nodes are documents and the edges represent citations between them. The two Amazon datasets product co-purchasing graphs, where the nodes are products and the edges represent that often bought together. All nodes are labeled with the topic or product category they belong to. All reported results were obtained by averaging over 10 random splits of the node set into classifier- rain//quanifferr-tainneeess with sizes of 5%/15%/80% respectively.
Additionally, conduct study the "Twitch Gamers" dataset [28]; it consists of about 168k vertices and 6.8 million edges, where vertices represent Twitch accounts and edges represent fol- lowership relations. Each vertex is annotated with the language of the corresponding user, whether the user streams explicit content, and a number of other features. This social network dataset is good source of real-world structural distribution shifts, since, for example, users from the same language community tend to form more densely connected subgraphs than users from different lan- guage communities (see Fig. 2). We select 10% of the users uniformly at random classifier-train nodes with a binary target label indicating whether a given user streams explicit content, From the remaining nodes, another 10% are selected
muantifier-trin nodes, i.c., as Dr. Last, the then re- maining nodes are partitioned into top-5 languages spoken by the users: English (74%), German (5%), French (4%), Spanish (3%) and Russian (2%); users outside of those languages are discarded. For each of the five partitions, the (binary) quantification task is to estimate the prevalence of explicit content streamers.
Distribution Shift For the synthetic quantification experiments, we introduce shifts in the test par- titions, while the training data is sampled uniformly random from the training split. We consider three types of test distribution shifts:
1. PPS: To simulate PPS, we first sample 10 K target label distribution y E Ax from Zipf distribution over the labels [27]. For each sampled target distribution, we then sample 100 vertices such that the target label frequencies are reached.
7

---

DE
EN
FR
ES
Figure 2: Visualization of the "Twitch Gamers" dataset [28]. Vertices represent Twitch users, edges represent follower relationships. Colors indicate the primary language of each user.
2. Structural covariate shift via breadth-firs search (BFS): For each label, we select corre- sponding vertices and starting at each of those vertices we sample 100 nodes via BFS.
3. Structural covariate shift via RWs: Analogous to the BFS setting, we sample 100 nodes random walks of length 10 with teleportation parameter 0.1.
For the real-world "Twitch Gamers" dataset, no synthetic distribution shifts are introduced; instead we use the natural covariate shift occurring when partitioning users by language. This allows to compare the applicability of the shift assumptions made by different quantification approaches.
Classifiers We use four different node classifiers to predict the labels of the vertices: A structure- unaware Multilayer Perceptron (MLP), Graph Convolutional Network (GCN) [17], Graph Atten- tion Network (GAT) [34], and APPNP [12]. All models are trained using the same training splits and hyperparameters, and two hidden layers/convolutions with widths 64 and ReLU activations. Each model is trained ten times on each of the ten splits per dataset, totalling 100 models per dataset, with which each quantifier is evaluated. Additionally, we evaluate the previously proposed Ego-network Quantification (ENQ) GQL method by Milli et al. [22]. ENQ uses simple neighborhood majority classifier combined with (standard) ACC; in addition, we evaluate it using NACC and SIS.
We evaluate SIS and NACC and compare them against standard (P)ACC and (P)CC. For SIS, we use kig k2, with ky being an interpolated version of the PPR kernel from Eq. (13):
Quantifiers
(x v') AkpPR(U, o') + (1-A). A)
where [0, 1] is a hyperparameter that controls the minimum weight that should assigned to each vertex. In the following, we report results for X 0.9; evaluations with different À param- cterizations and an alternative shortest shorrest-path-eeee path-based vertex kernel can be found in Appendix B. For the kernel density estimation (KDE) estimate of py, use the constant kernel kp k1, since the training data sampled uniformly at random without being subject to synthetic distribution shift in setup. This implies PV qv, simplifying the SIS estimation.
4.2 Discussion of Synthetic Distribution Shift Results
Table 1 compares the quantification performance of PCC, PACC and our extensions of the latter, i.e., SIS and beighborhood-award PACC under synthetically induced distribution shifts. Additionally, the last block of columns shows the average rank of each quantifier across all datasets. Bold numbers indicate that there is statistically significant difference between the reported mean and the best mean within a given block, determined by the 95th percentile of a one-sided t-test. Standard emros not reported for visual clarity and space reasons, since they are mostly very close zero.

---

Table 1: Quantification using probabilistic classifiers (absolute error and relative absolute error).
Model
CoraMI.
CiteSeer
A. Photos
A. Computerrs
PuhMed
Avg. Rank
Shif
Quantifier
AE
RAE
AE
RAE
AE
RAE
AE
RAE
AE
RAE
AE
RAE
PPS
MLPE
.0903
.692
| .0469
.2623
.0924
.6600 | 1,0700
.3588
.1268
.3948
PCC
.0429
.3543
0480
1.319
0445
-2977
.1159
.474
4.2
EgoNet
PACC
0848
.863
.0977
.5928
.0314
.3881
.034
3437
.0833
.3222
4.4
4.0
NEIGH PACC
.0519
4397
.594
.3791
.0277
.3265
.0588
2693
.0373
.1376
2.2
2.0
PPS
SIS PACC
.0837
.632
.0966
.5871
0313
.325
0333
3433
.0817
.3183
3.4
3.4
NEIGH PACC
4369
.027
.3300
.0288
2691
.0371
.174
PCC
.0877
.8555
.0361
.782
.497
1.105
0533
6342
.0470
.1870
5.0
5.0
MLP
PACC
.481
.091
.0366
0134
3690
.0811
.0649
PPS
SIS PACC
NEIGH PACC
0486
.0366
.437
.2865
.0:27
0288
.2118
1908
.0192
.0633
.2881
.395
0065
03388
2936
3708
.0179
.1877
.641
.649
2,4
3.4
2.6
2.8
SIS NEIGH PACC
.0320
.2847
.0271
.1799
.0122
.3345
.0263
.2913
.0178
.6166
1.0
1.4
PCC
.479
5323
.0219
1573
.0314
9570
0398
4674
.9463
.191
5.0
5.0
GAT
PACC
.0977
.6600
.0192
. 1262
.0447
.2766
0217
2326
.0176
.0335
3.2
2.8
PPS
SIS PACC
NEIGH PACC
.2900
2635
.0811
1200
1307
.0146
.0148
.2901
3249
0211
0214
2299
2271
.0167
.0922
.6994
9606
2.6
2,4
2.0
SIS NEIGH PACC
.0279
.2414
.0187
.1355
.0146
3466
.0007
.2388
01811
.0655
1.8
2.2
PCC
0438
.697
.0221
.1574
0335
8508
03991
4667
.D005
.1665
5.0
5.0
GCN
PACC
0246
.216
.1190
.259
.0122
.0566
0228
2411
.1611
0591
3.0
3.0
PPS
NEIGH PACC
PACC
.0.39
.1633
.2033
.0178
.0888
.253
.0224
0133
2295
2920
0223
.0911
.0544
2386
.0151
.0811
.0555
.659
2.0
3.0
2.6
SIS NEIGH PACC
.0332
.2073
.0176
.1177
.0135
.3529
.0888
.2029
.0168
.0613
2.0
2.2
PCC
.318
.995
0,90
4657
.1664
APPNP
PACC
.217
.1986
.0184
.211
.0124
.2442
0256
2638
.0165
.0597
2.6
2.8
PPS
SIS PACC
NEIGH PACC
.0003
0224
.1926
.1943
.0171
.0184
.1122
1222
.0139
.0.30
3133
3058
.0211
0249
24411
2566
.0154
D187
.0588
0676
3.4
1.6
3.2
1.6
SIS NEIGH PACC
.0214
.1939
.0172
.1149
.0143
3780
.0226
.2424
.0175
.6642
2.4
2.4
BFS
ML.PE
.1839
8.185
.2676
15.22
11622
9.313
11880
5.666
.30034
5.067
PCC
.1400
8.886
.2374
22.27
0566
3.686
04455
2.274
.2313
26.15
5.0
5.0
EgoNet
PACC
.0055
5.140
1908
17.87
0388
1,112
0419
1.190
.1108
24.61
3.6
2.6
NEIGH PACC
.8255
4.300
.1552
14.32
0359
1,151
.084
1.136
.6055
18.38
2.0
2.0
BFS
SIS PACC
1003
5.196
.1099
17.93
0385
1.125
0413
1.192
2119
24.96
3.4
3.6
SIS NEIGH PACC
.0813
4.244
.1531
14.12
.037
1.165
.0379
1.162
.1003
18.37
1.0
1.8
PCC
1243
7.212
.1588
14.84
0668
4.028
.0662
3.635
.8800
10.44
4.4
5.0
MLP BFS
PACC
.6455
3,508
11.58
10.63
0237
9928
0392
1.608
.8166
7.663
3.0
2.8
PACC
NEIGH PACC
.0777
3.008
.0944
8.845
0290
1.237
0400
1.817
0878
6.787
3.4
2.6
SIS PACC
0637
3.46
1162
10.74
.022
.9799
.330
1.509
.776
7.827
2.0
2.6
SIS NEIGH PACC
.0560
2.972
.994
8.699
0266
1.097
.0375
1.694
.8800
6.833
2.2
2.0
PCC
.0741
4.840
.0820
7.349
0291
1.757
0445
2.415
.6650
9.922
4.2
5.0
GAT
PACC'
0561
2.533
.666
5.347
0243
7255
0331
9463
.9930
6.906
2.6
2.4
BFS
SIS PACC
NEIGH PACC
.0577
.0500
2.265
2.548
.6116
.0702
5.880 886
5.015
0226
0240
.7147
8623
.312
0363
9381
1.234
.891
.1011
6.881
8.096
4.2
4.0
SIS NEIGH PACC
.0502
2.179
.0621
5.134
0264
8488
0343
1.223
0962
7,892
2.8
2.4
PCC
3.489
7.060
02:56
1.513
9418
2.255
.0573
9.553
GCN
PACC
0488
2.093
0637
267
0241
0401
9320
0888
6.713
3.4
2.2
BFS
SIS PACC
NEIGH PACC
.0415
0474
2.020
1.943
.0618
0653
5.132
5.428
00207
0261
3932
6773
0379
.0388
9569
9846
.840
0977
6.727
7.994
4.0
1.8
3.4
1.8
SIS NEIGH PACC
.0402
1.786
.0595
4.910
00240
7070
.0511
1.004
.024
7.723
2.6
PCC
.0469
3.074
.0737
6.609
.271
1.492
0468
2.339
.0569
9.867
4.2
5.0
APPNP
PACC
4.944
0225
.5311
0430
9227
.927
7.449
2.8
2.0
BFS
SIS PACC
NEIGH PACC
.380
0450
1.910
1.729
0633
.0744
4.705
5.243
.0213
0260
.5823
6585
.0395
0435
9331
9606
.1017
0874
7.372
8.673
4.2
1.6
3.6
1.8
SIS NEIGH PACC
.0378
1.615
.0562
4.600
.0256
.6993
04406
.947
.9622
8.440
2.2
2.6
RW
MLPE
.1832
6.430
| ,26511
15.07
.1594
8,278
[11.58
4.466
.3025
3.073
PCC
1355
6.275
.2237
21.00
.0538
2,895
00449
1 1,703
.2171
4.937
4.6
5.0
EgoNet RW
PACC
.0733
2.916
.1477
13.48
.476
1.061
0481
1.052
.1506
1.716
3.8
1.2
NEIGH PACC
.9900
3.201
.1476
0418
1.165
0437
1.091
.1419
1.996
2.0
3.2
SIS PACC
0971
2.939
.1484
13.55
0474
1,076
0478
1.058
.1508
1.756
3.6
2.4
SIS NEIGH PACC
.0887
3.101
.1455
13.29
.0416
1,173
0424
1.100
.1416
2.003
1.0
3.2
PCC
.1263
5.275
.1494
13.84
0727
3,820
0718
3,224
0013
1.376
4.8
5.0
MLP
RW
PACC
SIS PACC
NEIGH PACC
.644
0733
.0743
2.417
2.3
2.347
.0824
.869
.0899
7.766
7.105
7.425
.0332
.0326
.0115
1.144
1.251
1. 1,369
0471
0434
0450
1.765
1,859
1.837
.0822
0915
.7580
.7422
7066
2.8
3.4
2.8
3.0
2.8
SIS NEIGH PACC
.0620
2.040
.0798
6.894
.0303
1.201
.0406
1.735
.8880
.6960
PCC
3.555
6,693
03400
1.689
05000
2.195
.0691
.7488
GAT
PACC
.610
1.648
.594
4,563
0293
-7767
0382
.9699
0952
.6084
3.2
2.2
RW
SIS PACC
NEIGH PACC
.0550
.617
1.427
1.836
0554
0644
4,201
184
0300
.027
9098
.6664
0394
0366
1.19]
9656
0930
.077
.6001
6290
4.2
1.4
4.0
1.2
SIS NEIGH PACC
.0540
1.496
0564
4.432
0299
.8266
03766
1.185
.0951
.6238
2.0
2.6
PCC
.0339
2.085
0694
5.0
0276
1.247
0451
1.961
.0566
.4972
3.6
4.2
GCN RW NEIGH PACC
PACC
4.204
.1011
0428
8952
.0156
.5915
.0511
1,311
0588
4.687
02266
.6622
0403
9491
0964
6260
388
3.8
SIS PACC
.494
1.089
.0277
4.001
0266
.5993
0392
9029
0925
5778
2.0
1.6
SIS NEIGH PACC
.0461
1.034
.0524
4.049
.0256
.6682
.0375
9611
.934
.6161
1.4
3.0
PCC
0465
1.750
.0659
3.638
0293
1197
0504
2.016
.0546
.4160
3.8
4.2
APPNP RW
PACC
.0277
1.12.
0541
4.060
0282
.5726
D452
8693
.079
.9588
3.8
244
NEIGH PACC
.0512
1.229
.0833
4.580
0276
6387
0456
9643
.0999
.302
4.0
3.8
SIS PACC
.0501
3,738
.0258
.5650
.4188
8731
.0944
.5821
SIS NEIGH PACC
.0425
.8951
.0508
3.873
.0261
.687
.0424
9700
.0655
.6157
2.0
3.0
9

---

Table 2: Quantification results on the "Twitch Gamers" dataset with real- covariate shift.
English
German AE
French AE
Spanish AE
Russian AE
Avg.
Rank
Model
Quantifier
AE
RAE
RAE
RAE
RAB
RAE
AE
RAE
014
-257
.115
-122
.055
MLP
SIS ACC
ACC
.23
030
.047
.000
.002
003
028
.044
.107
.094
.201
.288
.254
.262
.699
.699
.066
080
.172
.211
2.2
2.8
2.8
2.2
SIS NEIGH ACC
.008
.016
.388
.977
.032
.069
.168
.408
.207
.544
2.2
2.2
CC
.004
.008
.19
255
1115
.246
.210
-12
.177
.465
2.4
2.4
APPNP
ACC
.21
.011
.042
011
0233
.116
.089
.90
.190
.244
595
.069
.0800
.210
.233
2.4
2.4
SIS NEIGH ACC
.096
.191
.399
858
.177
.379
.040
.097
.25
.671
3.4
3.4
In summary, considering the average ranks, our experiments show that both SIS and NACC are able to improve quantification results under PPS and covariate shift. The results are consistent across all classifiers, quantifiers, and types of distribution shifts, with either SIS the combination of SIS and NACC performing best.
Influence of the Classifier Unsurprisingly, the choice of classifier has significant impact on the quantification performance. Even though a good classifier h is not required by QL to obtain an unbiased estimate of the label prevalences, the quality of this estimate is still correlated with the classifier's s accuracy. Overall, the naive neighhorhood- ENQ performs worst, followed by the structure-unaware MIP, while APPNP performs best.
Influence of the Type of Distribution Shift The SIS kernels used in the experiments are based on the assumption that the distribution shift is induced by sampling localized random walks. In the RW covariate setting, this assumption is satisfied by definition, while in the BFS setting, the PPR kernel does, at least in theory, not fully capture the underlying sampling behavior. Nonetheless, SIS is able to improve quantification results in both cases. Interestingly, even in the PPS setting, where SIS is not necessary to account for the shift, observe clear improvement over ACC.
Experimental results for different kernel choices and hyperparameter settings can be found in Ap- pendix B. Additionally, in Appendix D, we demonstrate the importance of using structural kernel by comparing against a feature-based variant of SIS that does not consider structural information.
4.3 Discussion of Real-world Covariate Shift Results
Table 2 shows the quantification results on the real-world "Twitch Gamers" dataset. Here, the advan- tage of SIS and/or NACC over standard ACC and CC less pronounced compared to the synthetic experiments. For the English language community, which also constitutes 74% of the training data, SIS performs worse than standard approaches likely because there is only a small distribution shift compared to the training data for this community. However, for the other language communities, which are more strongly affected by distribution shift, SIS generally outperforms standard ACC and CC given an APPNP classifier. Using weaker, structure-unaware MLP classifier, SIS is not able to significantly improve quantification results. This highlights the importance of a sufficiently accurate base classifier for effective aggregative quantification.
5 Conclusion
We have introduced two novel graph quantification methods, SIS and NACC; to our knowledge, this is the first work to investigate classifier- based graph quantification and the (structural) covariate shift problem. SIS enables quantification under covariate shift via kernel density estimates of the instance distributions. NACC uses the neighborhood structure of the graph to improve class identifiability. The effectiveness of our approach was demonstrated on multiple graph benchmark datasets.
We envision two lines of future research. First, in this work, we focused on extensions of ACC to the graph setting. Another family of methods are the so-called distribution matching quantifiers, e.g., DMy [16] or KDEy [24]. An extension of distribution matching approaches to GQL would be interesting. Second, there are no true graph quantification benchmark datasets currently, which is why we resorted to introducing synthetic dataset shifts to node classification benchmarks. Creating a true graph quantification dataset, e.g., using social media data, would be a valuable next step to assess the performance of SIS and NACC in the real-world.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge the support the Munich Center for Machine Learning (MCML), and the German Research Center for Artificial Intelligence (DFKI), We also thank the reviewers for their valuable and constructive feedback, which helped improve our work.
References
[1] Jose Barranquero, Pablo González, Jorge Díez, and Juan José del Coz. On the study of nearest neighbor algorithms for prevalence estimation in binary problems. Pattern Recognition, 46(2): 472 482, 2013. ISSN 0031-3203. doi: 10. 10.1016/j ppt.pp..tt...... 02..2......
[2] Antonio Bella, Cesar Ferri, José Hernández-Oralle and María José Samirez-Quintann Quan- tification via Probability Estimators. In 2010 IEEE International Conference on Data Mining, pages 737-742, 2010. doi: 10. (09/ICDM.2000.))
[3] Mirko Bunse. On multi-class extensions of adjusted classify and count. In Proceedings of the 2nd International Workshop on Learning to Quantify (LQ 2022), pages 43-50, 2022.
[4] Clemens Damke and Eyke Hüllermeier. Linear Opinion Pooling for Uncertainty Quantification on Graphs. In The 40th Conference on Uncertainty in Artificial Intelligence, Barcelona, 2024.
[5] Andrea Esuli, Alessandro Fabris, Alejandro Moreo, and Fabrizio Sebastiani. Learning to Quantify, volume of The Information Retrieval Series. Springer. Cham, 2023. ISBN 978-3- 031-20467-8.
[6] Tom Fawcett and Peter A. Flach. A Response to Webb and Ting's On the Application of ROC Analysis to Predict Classification Performance Under Varying Class Distributions. Machine Learning. 58(1):33-33 38, 2005. ISSN 1573-0565, doi: 10. 10.1007/s10994-00 009444955550---4444 5256-4.
[7] Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with PyTorch Geo- metric, 2019.
[8] George Forman. Counting positives accurately despite inaccurate classification. In Pro- ceedings of the 16th European Conference on Machine Learning, ECML'OS pages 564- 575, Berlin. Heidelberg, 2005. Springer-Verlag. ISBN 978-3-540-22244-22 doi: 10.1007/ 11564096 55.
[9] George Forman. Quantifying trends accurately despite classifier error and class imbalance. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '06, pages 157-166, New York, NY, USA, 2006. Association for Computing Machinery. ISBN
doi: 10. 145/1 150402.1100222..
[10] George Forman. Quantifying counts and costs via classification. Data Mining and Knowledge Discovery, 17(2):164-206 2008. ISSN 1573-756X. doi: 10.10/7/s 1001111000000----1
[11) John J. Gart and Alfred A. Buck. Comparison of screening test and a reference test in epi- demiologic studies. II. A probabilistic model for the comparison of diagnostic tests. Amer- ican Journal of Epidemiology, 83(3):593-6d) 602, 1966. ISSN 1476-6256, 0002-9262. doi:
10. 1o.1003/ofoordooumaaaaaa.aaaaa
[12] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then Propa- gate: Graph Neural Networks meet Personalized PageRank. In International Conference on Learning Representations, 2018
[13] Lise Getoor. Link-based Classification. In Sanghamitra Bandyopadhyay. Ujjwal Maulik, Lawrence B. Holder, and Diane J. Cook, editors, Advanced Methods for Knowledge Discov- ery from Complex Data, Advanced Information and Knowledge Processing, pages 189-207. Springer, London, 2005. ISBN 978-1-84628-28444 doi: 10. (00771188628-284--
[14] C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. CiteSeer: An automatic citation indexing system. In Proceedings of the Third ACM Conference Digital Libraries, DL '98, pages 89- 98, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 978-0-89791- 965-4. doi: 10.1145/2766552776683
[15] Pablo González, Alejandro Moreo, and Fabrizio Sebastiani. Binary quantification and dataset shift: An experimental investigation. Data Mining and Knowledge Discovery, 38(4): 1712, 2024. ISSN 1573-756X. doi: 10. 102-00011180220011----

---

[16] Víctor González- Rocío Alaiz-Rodriguez and Enrique Alegre. Class distribution es- timation based on the Hellinger distance. Information Sciences, 188-146166, 2013. ISSN 0020-0255. doi: 10. 10.101 6/f..ins.2012.05.022..
[17] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference Learning Representations, 2017.
[18]
Meelis Kull and Peter A. Flach. Patterns of dataset shift. 2014.
[19]
Zachary Lipton, Yu-Xiang Wang. and Alexander Smola. Detecting and Correcting for Label Shift with Black Box Predictors. In Proceedings of the 35th International Conference Machine Learning, pages 3122-3130. PMLR, 2018.
[20] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-Basee Based Recommendations on Styles and Substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '15, pages 43-52, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 978-1-4503- 3621-5. doi: 10.1 145/27664462227777555
[21] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the Construction of Internet Portals with Machine Learning. Information Retrieval, 3(2):127- doi: 10. 10093//:10009538818 4988.
163, 2000. ISSN 1573-7659.
[22] Letizia Milli, Anna Monreale, Giulio Rossetti, Dino Pedreschi, Fosca Giannotti, and Fabrizio Sebastiani. Quantification in social networks. In 2015 IEEE International Conference on Data Science and Advanced Analytics (DSAA), pages 1-10, 2015. doi: 10.1109/DSAA.2015 7 7344845.
[23] Alejandro Moreo, Andrea Esuli, and Fabrizio Sebastiani. QuaPy: A Byython-Basee Framework for Quantification. In Proceedings of the 30th ACM International Conference on Information
& Knowledge Management, CIKM '21, pages 4534-4543, ciation for Computing Machinery. ISBN 978 118-1--4003-444-44 doi: 10. 10.1 141114/445967..44444 33.8200..
New York, NY, USA, 2021. Asso-
[24] Alejandro Moreo, Pablo González, and Juan José del Coz. Kernel density estimation for multiclass quantification. Machine Learning, 114(4):1-38, 2025. ISSN 1573-0565. doi:
10.10077:10944-04--06722
[25] Galilco Namata, Ben London, L. Getoor, and Bert Huang. Query-driven Active Surveying for Collective Classification. In Proceedings of the Workshop on Mining and Learning with Graphs (MLG-2012), Edinburgh, Scotland, UK, 2012.
[26] Lawrence Page, Sergey Brin, R. Motwani, and Winograd. The PageRank Citation Ranking Bringing Order to the Web. In The Web Conference, 1999.
[27] Lei Qi, Mohammed Khaleel, Wallapak Tavanapong, Adisak Sukul, and David Peterson. A Framework for Deep Quantification Learning. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML. PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part I. pages 232-248. Berlin, Heidelberg, 2020. Springer- Verlag. ISBN 978-3-030-66755--5. doi: 10.
Opringer-Verlag.
[28] Benedek Rozemberezki and Rik Sarkar. Twitch Gamers: Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings, 2021.
[29] Marco Saerens, Patrice Latinne, and Christine Decaestecker. Adjusting the Outputs of a Clas- sifier to New a Priori Probabilities: A Simple Procedure. Neural Computation, 14(1):21-41, 2002. ISSN 0899-7667. doi: 10.1 11111/899976622232844444
[30] Bernhard Schölkopf, Dominik Janzing, Jonas Peters. Eleni Sgouritsa, Kun Zhang, and Joris Mooij. On causal and anticausal learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICMIL'12, pages 459-466, Madison, WI, USA, 2012. Omnipress. ISBN 978- 978-1-4503-1285.1
[31] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective Classification in Network Data. Al Magazine, 29(3):3393, 2008. ISSN 2371-9621. doi: (t6609/aima..22933.222
[32] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation, 2019.
[33] Dirk Tasche. Fisher consistency for prior probability shift. J. Mach. Learn. Res., 18(1):3338-
3369, 2017. ISSN 1532-4435.
12

---

[34] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Rep- resentations, 2018.
[35] Slobodan Vucetic and Zoran Obradovic. Classification on Data with Biased Class Distribution. In Luc De Raedt and Peter Flach, editors, Machine Learning: ECMI. 2001, pages 527-538, Berlin, Heidelberg, 2001. Springer. ISBN 978-3-540-4479555 doi: 10. 10.100773-540-447955.. 45.
13

---

Appendix for "Adjusted Count Quantification Learning on Graphs"
A Further Details on the Implementation
In our implementation, we use torch-geometric [7] (MIT license) for the graph neural network (GNN) models, while the QuaPy Python library (BSD 3-Clause) was used for the quantification methods. Additionally, graph traversal and distance computation, e.g., to create were conducted on a single machine with an AMD Ryzen 9 5950X CPU, 64GB RAM and an Nvidia RTX 4090 GPU with 24GB VRAM. Our code is available at https: / /eg//gitttt github...... com com/Cortys/ graph-quant wittigguunttiiaiiiooi it includes a versioned list of all dependencies that were used.
used Nvidia's cuGraph library (Apache 2.0 license) for GPU-based
covariate shift. All experiments
B
Kernel Selection & Influence of Kernel Hyperparameters
In Section 4.1, we defined the interpolated PPR kemel
(x(2, r') MM v²) + (1-
(15)
All reported results for SIS use this kernel with À 0.9. In this section, we will explain why this particular kernel was chosen.
B.1 On Kernel Selection for SIS
As described in Section 3.1, SIS uses vertex kernels, k, and hig to estimate the densities py and gv of the training and test vertices, respectively. Depending on the type of distribution shift and other available domain knowledge, different kernels can be used. Overall, found that the PPR kernel is a good choice for structural covariate shift.
Recall that the kernels are used estimate the density ratio pv (v) for each training vertex Those density ratios are then used to reweight the training vertices in the confusion matrix estimate Čj, i.e., a high weight is assigned to training vertices from Dr that "look like" they have been sam- pled from the same distribution QVV) the unlabeled test vertices Ve (see Eq. (11)). Assuming structural covariate shift between P and Q, the probability of sampling vertex v given that v' was sampled should depend on some measure of the structural distance between and v'. Since there are many different ways to define such vertex distance (shortest path, random walk, graph spectrum, etc.), there are many potential SIS kernels.
we do not have any prior knowledge about the distribution shift, other than that it is structural and that the underlying graph homophilic, the problem of estimating the probability of sampling a vertex v given that v' was sampled is ill-posed. Fortunately, we do not need to derive a perfect kernel obtain good quantification results. Instead, note that:
1. The kernel-based estimates are used to reweight the training vertices in the confusion matrix estimate Cj,; such that vertices that are close the test distribution have higher influence on the estimate than those that are not.
2. Standard (homophilic) GNN models consist of stack of graph convolution layers, each of which essentially multiplies the vertex features with the graph adjacency matrix, thereby propagating the features of vertex to its neighbors [17, 34, 12]. For APPNP this hold especially true since the embedding vector of a vertex is defined as weighted sum over the embeddings of its neighbors, where the weights are defined to be PPR probabilities (cf. Eq. (13)). Overall, ignoring the nonlinearities between convolutions, for GNN models, kppR (v, v') can be interpreted as an approximation of how similar the predictions of a GNN h will be for two vertices v, v'.
Combining both points, the PPR kernel reweights vertices based on how similar the predictions of a GNN will for them, i.e., SIS with PPR focuses on the region of the training data, where the predictive behavior of h is similar to the test data. Empirically, we found that this works well for different combinations of models, datasets and types of distribution shifts. However, in principle, given additional knowledge, one could also design domain specific kernels.
14

---

Chdser
APAs
1.00
0008
Figure 3: Quantification performance of SIS (with NACC) with the PPR kernel for different values
of X.
B.2 Hyperparameter Evaluation the PPR Kernel
As noted above, we use the interpolated PPR kernel from Eq. (15) with À = 0.9 for all experiments. Intuitively, controls the influence training vertices Dr that are far-away from the test vertices Vv- If À = 1, far-away vertices are effectively ignored. If X 1, all vertices are considered at least to some degree, but the influence of far-away vertices is reduced. advantage of reducing the influence of irrelevant or misleading vertices from different regions of the graph. However, if too many vertices are excluded, the effective sample size for the confusion matrix estimate is reduced, making it more noisy, which can, in turn, degrade performance.
large can have the
Figure shows the quantification performance of SIS with the PPR kernel for different values of A. For CoraML and CiteSeer, À < clearly outperforms À = 1, with À se 0.9 performing very well. For the Amazon Photos and Computers datasets, À performs best. Interestingly,
CoraMI. and CiteSeer, the quantification performance for À = is significantly worse than for À < 1, while for the Amazon datasets, = performs better than À < The reason for this discrepancy that the CoraML and CiteSeer graphs contain multiple small components that are disconnected from the main connected component; for structurally shifted test distributions that lie within one those small components, the PPR-based confusion matrix estimates then based on very few vertices, making it very noisy and thereby degrading performance. By assigning at least a small weight to all vertices, e.g., via À 0.9, the effective sample size is increased, which leads to better estimates those datasets. For this reason, we found that a value of À that slightly smaller than works well for most datasets, which is why chose À 0.9 as default.
B.3 Evaluation of the Shortest path Kernel
For comparison, we also evaluated an alternative to the PPR kernel. This alternative kernel is based the shortest path (SP) distance between vertices instead of RW probabilities. We define this chortest-patle kernel as
ksr(w, v') cxp(-> (1,
(16)
where dep (v) is the length of the shortest path length between and o' and > tunable hyperparameter.
Figure 4 shows the quantification performance of SIS with the chortest-path kemnel for different values of y. Under PPS, increasing y leads a decrease in performance on all datasets except Cite- Seer. Under covariate shift (both, BFS and RW), increasing generally improves the quantification performance.
This is plausible, since under PPS, all training vertices are equally important, while under covariate shift, the training vertices that are close to the test vertices are more important than those that are far away. By increasing 7, the kernel becomes more peaked around close vertices. Under covariate shift, where far-away vertices are less important, this leads better quantification performance, while under PPS more aggressive reweighting decreases performance.
15

---

Table 3: Comparison of SIS quantification with the SP and the PPR kernel.
Model
CoraMI AE
CiteSeer
A. Photos
A. Computers
PubMed
Arg, Rank
& Shift
Quantifior
RAE
AE
RAE
AE RAE
AE
RAE
AE
RAE
| AB RAB
PPS
MLPE
.0903
5692
.0469
.2623
.0924
.6600
.0770
.1268
.3948
PCC
.0277
8565
.0361
.2722
0497
1.105
.0533
.342
.0470
.1870
5.6
5.8
PACC
4186
.036
.2271
0191
.3036
.0344
MLP
NEIGH PACC
.326
.2655
02888
.1908
.0133
3595
.265
.2936
.0187
.0649
2.2
2.6
PPS
SP PACE
.6556
.5871
.0733
.9166
0235
3243
0106
.4778
.0296
.1129
5.0
4.4
SP NEIGH PACC
.041
.4114
0400
.2022
0194
3575
0283
.1778
.0327
.1253
4.0
3.8
PPR NEIGH PACC
.0300
.2847
.0711
.1799
.0622
.3445
.0263
.2913
.6166
PCC
0479
-5333
00219
.1573
.314
.570
.0398
4674
.0433
.191
5.6
5.6
PACC
0297
.0922
.1622
.0177
.2766
0211
NEIGH PACC
0287
2438
.0199
.1307
.0446
3249
.2111
.2711
.0922
.694
2.4
2.4
PPS
SP PACC
.0375
.3481
.0332
.1922
0202
.594
02399
2683
.0309
.146
5.0
4.8
SP NEIGH PACC
.069
32522
0321
.1311
0195
5628
.0007
2426
.034]
.1778
4.0
4.6
PPR NEIGH PACC
.0299
.2414
.0187
.1235
.0146
3466
.0207
.2238
.6655
1.4
PCC
0438
.4697
.0211
.1574
0315
8508
.0391
.6677
.0405
.1655
5.6
5.6
PACC
0246
2216
.1900
.1259
.0122
.056
0228
.2111
.0611
GCN
NEIGH PACC
02.39
.2073
.0188
.1553
00.34
.920
.191
2054
.0881
.6559
2.2
2.0
PPS
SP PACC
0315
.3089
03002
.2445
.1122
3994
0279
3051
0298
.1766
5.0
4.8
SP NEIGH PACC
.3388
2862
.3001
.2033
.181
.5700
0223
2436
.0119
.1366
4.2
4.6
PPR NEIGH PACC
.0322
.2073
.0176
.1177
.0135
3329
.0188
.2029
.0188
1.6
PCC
0374
.4124
.0214
.1509
.3318
.9795
.0390
.4557
.039%
.1664
5.6
5.6
PACC
0217
.1986
0184
.2111
.0224
.2442
0256
.0997
APPNP
NEIGH PACC
0224
.1943
.0184
.1222
00.39
3133
.0311
.2411
.0887
.676
2,6
2.4
PPS
SP PACC
0286
.2933
0293
1969
.0181
.6573
0332
3970
.3002
1284
4.4
4.6
SP NEIGH PACC
.292
.2723
0300
.1993
.192
7014
0262
2859
.0332
.144
5.0
4.8
PPR NEIGH PACC
.0114
.1939
.0722
.1149
.0143
3780
.0226
.2424
.0755
.0442
1.6
BES
MLPF
.1899
8.185
.2676
15.22
1622
9,313
1180
5.666
.30044
5.067
PCC
1243
7.212
.1588
14.84
0668
4.028
.0662
3.635
.0800
10.44
5.0
5.4
PACC
0645
3,508
1158
10.63
.037
.9288
0392
7.663
2.2
MLP
NEIGH PACC
0577
3,008
.984
0290
1,237
0400
1.817
0878
6.787
BES
SP PACC
.787
4.803
2134
36
0272
1,477
0350
1.736
.783
12.26
3.6
5.0
SP NEIGH PACC
0715
4.636
2080
19.92
0294
1.519
0342
1.682
.0756
10.20
3.2
4.0
PPR NEIGH PACC
.0560
2.972
0964
8.699
0266
1.097
.0775
1.694
.8400
2.4
1.8
PCC
.0711
4.840
.0820
7.349
.291
1.757
.0455
2.415
.6650
9.922
4.6
5.4
PACC
0561
2.533
0656
5.347
0243
.255
0331
9463
.930
GAT
NEIGH PACC
0577
0702
0280
8623
0000
12334
101
8.096
BES SP PACC
0618
3.745
.0588
19.24
.032
9479
06200
1.922
0784
9.279
3.0
4.0
SP NEIGHT PACC
.616
3.667
.2030
19.24
0266
1.108
0311
1.143
.875
10.40
3.6
5.2
PPR NEIGH PACC
.0502
2.179
.0621
5.134
.0644
8485
.0443
1.223
.0962
7,892
2,8
1.8
PCC
.0339
3,489
07783
7.060
0256
1,513
0418
2.255
.0533
9.553
4.0
5.0
PACC
0488
2.093
0637
267
0241
5966
1400
9320
0888
6.713
GCN BES
NEIGH PACC
0474
2.020
0653
5.828
026
6773
0179
9846
0977
7.994
SP PACC
.0611
3.503
2083
19.70
.0330
8628
1300
1,051
0785
10.40
3.4
5.0
SP NEIGHT PACC
.0541
3,276
.053
19.45
0255
1.013
.0322
1.104
.8555
11.08
3.6
5.0
PPR NEIGH PACC
.4422
1.786
.0595
4.910
.0240
7070
.0511
1.004
.0924
7.723
2.4
2.0
PCC
0469
3.074
J0737
6.609
.071
1.492
.4468
2.339
.0569
9.867
4.2
4.8
PACC
0457
1.881
.0503
4.9 4.44
.0255
.5311
.0430
.9277
.0927
7.449
2.8
1.4
APPNP
NEIGH PACC
0459
1,910
0633
5.243
0260
6585
0435
.606
.017
8.673
BES
SP PACC
.0531
3.327
2081
19. 54
.0233
8863
.0300
1.045
.0799
10.94
3.2
5.0
SP NEIGHT PACC
.0515
3.140
.2037
19.29
0261
1.037
0344
1.148
.0872
11.60
4.0
5.2
PPR NEIGH PACC
.0378
1.615
.0562
4.600
.0256
.6993
.0406
.9.47
.0962
8.440
2.6
2.0
RW
MLPE
.1832
6.430
.26511
15.07
.1594
8.278
.1158
4.466
.3025
3.073
PCC
1263
5.275
.1494
13.84
.0727
3,820
.0718
3.224
.0913
1.376
5.0
5.6
PACC
.0.33
2.347
.8669
7.425
0333
1.251
.0471
1.857
.0882
.7452
3.0
2.6
MI.P
NEIGH PACC
.824
0326
1.360
.0134
1.859
RW
PACC
0923
3.841
2081
19.71
0354
1,805
19171
2.046
0926
18547
5.2
5.0
SP NEIGH PACC
0798
3.580
.0122
19.07
03:40
1.670
.0408
1.863
1949
8579
4.2
4.4
PPR NEIGH PACC
.0620
2.040
.0798
6.894
.0303
1.201
.0406
1.735
.0880
.6960
1.0
L.0
PCC
.799
3.555
.0766
6.693
.330
1.689
.0500
2. 2.195
.0691
77488
4.6
5.6
PAOC
.610
1.648
.0594
4,563
.029
.7767
0382
.6339
.0952
.6084
2.8
16
GAT
NEIGH PACC
0617
0644
0308
.098
.094
1.191
RW
PACC
0713
2.994
.1955
61
.0296
1,062
.0370
1.235
0908
.995
SP NEIGH PACC
.021
3.175
1996
18.79 79
0306
1.225
0380
1.211
09588
7424
4.6
5.2
PPR NEIGH PACC
.0540
1.496
.0564
4,432
.0290
8826
.0776
1.185
.0951
.6238
1.6
1.8
PCC
.0539
2.085
_0694
5. 5.990
0276
1.247
D441
1.961
.0566
.472
3.4
4.2
PAOC
.071
1.267
.0554
4.204
.299
.6001
0428
.952
.0956
.5915
4.4
L8
GCN
NEIGH PACC
0558
0276
6622
0403
9491
RW
PACC
0646
2.515
.1995
18.76
0291
8745
0358
1,048
.0888
.576
4.2
4.2
SP NEIGH PACC
0648
2.689
1971
18.63
0275
1,003
.0344
1.555
0913
7050
3.4
5.4
PPR NEIGH PACC
.061
1,034
.0524
4.0449
.0256
.6682
.375
9611
.0944
.6161
1.8
2.4
PCC
0465
1.750
.0659
5.638
0293
1.197
.0504
2.016
.0546
.4160
3.8
4.2
PAOC
0527
1.121
.0541
4,060
.282
.7266
.0452
.693
.0979
.5958
3.6
L8
APENP RW
NEIGH PACC
1.229
.0583
0276
.387
.0156
PACC
0602
2.352
.2005
18.83
0285
8829
.0398
1.089
.073
.390
3.8
4.2
SP NEIGH PACC
0609
2.53
1972
18.66
0283
1,074
.0402
1.237
0914
6818
4.0
5.4
PPR NEIGH PACC
.0425
.951
.0508
3,873
.0261
.6887
.0424
9700
.9K5
.157
2.0
2.4
16

---

LPP
Araact Compuzars
0.90
Figure 4: Quantification performance of SIS (with NACC) with the shortest-path kernel for different
values of 7
Table 3 compares the quantification performance of SIS with the SP and the PPR kernel. Since large values generally lead to better performance under (structural) covariate shift, we used 3 as default for the reported SP kernel results. Overall, we find that the PPR kernel outperforms the SP kernel. Looking at the average ranks, we find that the SP kernel performs worst under PPS and best under BFS covariate shift. This is plausible, since the BFS- -rS-iiddeed covariate shift samples vertices based on their distance to some root vertex, the test vertex density gv thus depends on SP distances. Nonetheless, the PPR kernel is still a better default choice.
C Runtime Analysis of SIS and NACC
Here, we analyze the runtime complexity of SIS for the PPR and SP kernels and provide additional information on their implementation. Additionally, we describe the complexity of NACC.
The main difference between standard ACC and ACC with SIS is the reweighting of training in- stances to account for covariate shift. Given a reweighted confusion matrix estimate, label preva- lences are estimated using constrained optimization as described in Eq. (6), just like in standard ACC. The computational complexity of SİS thus is fully determined by the cost of computing pv (v) for all D,, (see Eq. (11)). As defined in Eq. (12), (v is estimated via KDE.
As explained in Section 4.1, we use the constant kernel kp = k1 to estimate py, since the training data is sampled uniformly at random in experiments and only the test data is sub- ject to distribution shift. The computational complexity of SIS is thus determined by the time takes to compute the kernel values ky. Let Tj be the time it takes to compute the kernel values (ky(u, 2²) (v. y) E DL, o' E Vu Based on those values, the time complexity of computing all weights p(v) thus is T O + [Dzl VVel). Here, Tj depends the choice of the kernel k.
C.1 Complexity of the PPR Kernel
For the PPR kernel from Eq. (13), the random walk probabilities II, have to be computed, where L is the length of the random walk. The matrix 11 E x||x//11 is defined as
rT' aI ( (1I+
where D is the normalized (random- walk)) adjacency matrix of the graph and a E |0, 1] is the probability not moving a given step of the random walk. Naively, _ can be computed via standard dense matrix multiliccation in (()))3 "), 2.807 logg !), using Strassen's 's algo- rithm. Since matrix multiplication is very parallelizable, this naive strategy can sufficient, even for medium to large graphs. The experiments on the PubMed dataset, which is the largest dataset with synthetic shifts, with roughly 20k vertices, were conducted using dense matrix multiplication on the described hardware (sce Appendix A).
17

---

If dense multiplication is not feasible and the adjacency matrix is sparse (which is typically the case for large real-world graphs). the PPR kernel can still be computed using sparse matrix mul- tiplications. Since the sparsity of IT decreases with increasing L, simply applying sparse matrix multiplication I times not feasible, as the resulting matrices quickly become dense. One way to tackle this "densification" problem has been proposed by Damke and Hüllermeier [4]. They propose to ensure a certain level of sparsity after each multiplication by pruning entries below a threshold 6. This approximation allows for an efficient computation of 11 even for large graphs. We used this approach for the experiments with the "Twitch Gamers" dataset (over 168k vertices).
C.2 Complexity of the Shortest path Kernel
For the SP kernel from Eq. (16), we need to compute the distances from the vertices in D,. to the vertices in Vy. Given an undirected graph without edge weights, the distance from any node v to all other nodes v' can computed via BFS in O(EE), where & is the edge set of the graph. Since node distances are symmetric in undirected graphs, we can thus simply run BFS for each node in D2 or in Vy. Starting the BFS traversals from the nodes in the smaller set, one then gets Th = O (min((DE) [Vol) (8)).
On a more practical note, when one wants to quantify label prevalences for many test sets sampled from the same graph, it is best compute the entire all-pairs shortest path distance matrix D NO N in advance and to then use as lookup table for each quantification task. If the graph is sparse, i.e., |8| < [V]2, D can be computed fairly efficiently. Additionally, distance computation in graphs lends itself well to parallelization. For our implementation, we used the Python bindings of Nvidia's libcugraph library, which provides a fast implementation of BFS for GPUs!.
C.3 Complexity of NACC
The primary difference between standard ACC and Neighborhood-awwrr ACC (NACC) is the con- fusion matrix estimate Ò and the distribution of predictions Q(Ý) used in Eq. (6).
ACC uses a square K x K confusion matrix and a K K-dimensional predictive distribution vector; both can be computed in C(IV) + K²) via single pass over the vertices to count predicted label frequencies, followed by normalization. The objective of the constrained optimization problem from Eq. (6) can then be evaluated in ((K3). The number of required objective evaluations depends on the used optimization algorithm; since the objective is quadratic, the number of optimizer evalua- tions can, however, be assumed to be in ((1) when using (quasi-) Newtonian method. The number of parameters to the optimization problem is K, a quasi-Newtonian optimizer can thus compute and store estimates of the Hessian in O(32). Overall, the time complexity of ACC is thus O(V]+ + K²).
NACC uses an overdetermined system of equations with a rectangular K² x K confusion matrix estimate and K dimeennnil predictive distribution vector. NACC computes the prediction fre- quencies of all class pairs (j, k) E ) where the first class is the predicted label of a class and is the predicted majority label in its neighborhood. The majority label for all neighborhoods can be computed in ((E)). Combining this with the increased size of the confusion matrix, NACC thus has an overall time complexity of O(V) + |3] + K If the graph is sparse and the number of classes K is relatively small, NACC scales well even to large graphs.
D Feature-based Importance Sampling for Graph Quantification
In Section 3.1, we introduced SIS method account for structural covariate shift in graph quantification. SIS is hased on the assumption that the marginal densities pv and qv of the training and test vertices can be estimated using vertex kernels kp and k, that capture structural similarity between vertices. While this is a reasonable assumption under structural covariate shift, one could, in principle, use other types of kernels to estimate vertex similarity. One natural alternative to the structural kernels (Eqs. (15) and (16)) are non-structural kernels that only consider vertex features. In homophilic graphs, the features of neighboring vertices tend to be similar, indicating that feature similarity could be used as proxy for structural similarity.
'https://docs rapids a1/ httpa///wgggggee//////////////// bfs/
18

---

Table 4: Comparison of SIS with the PPR kernel and an inner product feature kernel.
Model
CoraMI
CiteSeer
Photos A.
A. Computers
PuhMed
Avg.
Rank
& Shift
Quantifier
AB
RAE
AE
RAE
AE
RAE
AE
RAE
AE
RAE
AE
RAE
PCC
.827
8865
.9661
.2782
.0497
1,105
.0533
.6342
.0470
.170
PACC
0481
.186
.0336
-2211
.0191
.336
[0334
.3690
.0181
0649
4,4
4.2
MLP
NFIGH PACC
.0326
.2865
.0888
.908
.0163
.3595
.9265
.2936
.0187
.6-99
3.0
3.0
PPS
PPR PACC
PPR NEIGH PACC
.0300
0486
.2847
.437
.0711
0527
.1799
2218
.0162
0192
.2681
3345
.0233
03388
.2913
.3708
.0178
.0179
.0641
.0616
FEATURE PACC
.0877
.4387
.0326
.2133
.0911
.3378
.0326
.655
.0181
0658
4.6
5.2
FEATURE NEIGH PACC
.0344
.3061
.0297
.2201
.0165
.4188
.0260
.2939
.0184
.1641
3.0
3.6
PCC
0438
.697
.0221
.174
.0315
8508
.0391
4667
.4405
1665
7.0
7.0
PACC
0246
.2216
.0190
1259
.0122
.2056
.0228
2411
.0161
0591
4.2
4.0
GCN
NEIGH PACC
.0.39
.2073
.0188
.1253
.0134
.9200
.0191
.0554
.0181
.6:59
4.2
3.6
PPS
PPR NEIGH PACC
PPR PACC
.0334
.0232
.2073
.2163
.0178
.0176
.1177
.1186
.0124
.0135
.295
.3329
.0188
0223
2029
.386
.0151
.1188
0613
2.4
2.6
3.0
FEATURE PACC
.0237
.2176
.0189
1312
.0123
.2103
.0224
2374
.0157
.1572
3.4
3.6
FEATURE NEIGH PACC
.0236
.2064
.0911
.1328
.0134
.3049
.0189
.2038
.0174
.0629
4.2
3.8
PCC
.0374
.4124
.0214
.1509
.0318
.995
.0390
4657
.0398
1664
7.0
7.0
PACC
.0117
.1986
.0184
.1211
.0124
.2442
.0256
.638
.0165
.0977
3.8
3.8
APPNP PPS
NEIGH PACC
0024
.1943
.0184
.1222
.0139
.3.33
.0311
.2471
PPR PACC
.0003
.1926
.0171
.1132
.0.30
3058
.0249
25666
.0544
.0558
2.0
2.0
PPR NEIGH PACC
.0214
.1939
.0172
.1149
.0143
3780
.0266
.2444
.0775
06-42
3.2
3.2
FEATURY PACC
.0212
.1978
.0183
.1259
.0124
.2517
0255
.2114
.0159
.0574
2.6
3.8
PEATURE NEIGH PACC
.0188
.1298
.0140
.341
.0229
.2449
PCC
.243
7.212
.1888
14.84
0668
4.
D662
3 3.635
0800
10:44
6.2
PACC
0645
3,508
1158
10.63
0257
99/28
0392
16688
0816
6.663
3.2
MLP BFS
NFIGH PACC
.0577
3.008
.0984
8.845
0790
1.237
0400
18817
0678
6.787
4.6
3.0
PPR PACC
.0637
3,461
1162
10.74
.0223
9079
.337
1.509
0786
7.827
2.6
3.2
PPR NEIGH PACC
.0560
2.972
.994
8.699
.0266
1,097
.0375
1.694
0840
6.833
2.6
2.4
FEATURE PACC
0628
3,573
.1563
14.82
0244
.0997
1.761
.0780
7.685
FEATURE NEIGH PACC
.0560
3,053
.1409
13.39
.0298
1.345
.0399
1.937
00447
6.814
4.8
4.4
0539
3,489
.0783
7.060
0256
1.513
.0488
2.255
0573
9.553
PACC
0488
2.093
.0637
5.267
0041
5966
0401
.320
0888
6.713
4.6
2.8
GCN
NEIGH PACC
0477
2.020
06653
5.428
.0261
6773
.0379
98466
0977
7.994
5.2
4.2
PPR PACC
.0415
1,943
.0618
5.132
.0207
.5932
.0358
.569
0840
6.727
1.8
2.2
NEIGH PACC
1.786
.0595
0240
.0770
.0351
7.723
FEATURE PACC
.0476
2.067
.1020
9.30]
.024
.5944
.4000
.359
0870
6.723
4.4
3,4
FEATURE NEIGH PACC
.4660
1.990
1020
9.358
.0259
.6811
.0377
.9999
0957
8.058
5.0
5.2
PCC
0469
3.074
.0737
6.609
.0271
1.492
D416
2.339
0569
9.867
5.4
6.6
PACC
.0557
1.881
06603
4.944
.0225
.5331
.430
.9277
0927
7.449
3.8
2.8
APPNP BFS
NEIGH PACC
.0459
1,910
.0633
5,243
.0260
6585
.0355
.6666
.1017
8.673
5.8
4.6
PACC
.0544
4.705
.0233
.5223
.0955
.931
PPR NEIGH PACC
.0378
1.615
.0562
4.600
.0256
6993
.406
.747
0962
8,440
2.6
3.6
FEATURE PACC
0443
1.852
.985
8.937
.0220
.5707
0425
.9178
0909
7.475
3.4
2.8
FEATURE NEIGH PACC
.0444
1.869
.0992
9.057
.0257
.6778
.0430
.9647
.099
8.750
5.4
5.4
PCC
.1263
5,275
14494
13.84
.0727
3.820
.0718
3 3,224
.0913
1,376
6.8
7.0
PACC
0733
2.347
0866
7.425
0352
1,251
.477
1.837
.0882
.7452
NEIGH PACC
0644
2.153
.0824
7.105
0326
1,369
0915
-7066
RW
PPR NEIGH PACC
PPR PACC
.0620
.0743
2.040
2.417
.0798
.8899
6.894
7.766
.015
.0303
1,144
1,201
JM06
1450
1.765
1.735
.984
JISHO
.7580
.6960
3.6
1.4
3.4
1.2
FEAT URE PACC
.0740
2.445
.1275
11.62
.0341
1.341
.0479
1.970
.8588
.6622
4,8
5.6
FEATURE NEIGH PACC
.0644
2.229
.1202
10.98
.031
1,456
.0434
PCC
.0539
2.085
.699
5. 5.900
.0276
1.247
.0451
1,961
.0566
.497
4.4
5.4
PACC
1.267
0584
4,204
0298
.1111
.4288
.852
0956
5915
GCN RW
NEIGH PACC
0541
1.311
.5888
4.637
0276
.622
.4403
9499
0964
6260
4.8
5.0
PPR PACC
.0994
1.089
0027
4,001
.0266
.993
.0392
.9029
0925
5778
2.0
1.8
PPR NEIGH PACC
.0461
1.034
.0524
4.049
.0256
.6682
.0375
.661
.934
.6161
1.4
4.0
FEATURE PACC
.0559
1,234
0767
6.490
0298
.6110
.0426
.862
FEATURE NEIGH PACC
.0266
1.267
.0796
6.913
.0733
6644
.0401
.552
.948
6226
.0465
.655
5.638
.023
1.197
U504
2,016
PACC
.0277
1.121
.0541
4.060
.0282
.726
.4552
.8633
.0999
.958
5.2
3.2
APPNP RW
NEIGH PACC
.0512
1.229
.0583
4.580
.0276
6387
.456
9643
0999
6302
5.2
5.0
PPR PACC
.0448
.9489
.0501
3.735
.0255
.5650
.418
.8711
.044
.5211
1.4
1.8
NEIGH PACC
.0425
.8951
.0588
3,873
.0611
6387
.424
9700
FEATURE PACC
.0515
1,090
07744
6.225
0279
5711
0450
8672
0968
5911
4.8
3.0
FEATURE NEIGH PACC
.0498
1.189
.076
6.666
0273
6427
0052
9674
0983
6241
4.8
5.8
One advantage of a caature-based kernel is that it can be applied even in the absence of a graph struc- ture, i.e., when only vertex features are available. Second, even if the graph structure is available, feature-based kernels can be more efficient to compute than structural kernels, especially on large graphs. To evaluate the suitability of feature-based kernels for graph quantification under structural covariate shift, we implemented a feature-based version of SIS using the inner product between ver- tex features as kernel. Table 4 compares the quantification performance of this feature-based SIS variant with with SIS+PPR. Overall, we find that the feature-based SIS performs significantly worse than SIS with the PPR kernel across models and datasets. This demonstrates that frruttur-bbsed vertex kernels are better suited to account for structural covariate shift in graph quantification than a purely feature- based kernel.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract claims that we propose two novel techniques for quantifica- tion learning on graphs, Structural importance sampling and Neighborhood-aware ACC, which improve quantification under covariate shift and in the presence of non-homophilic edges, respectively. Both approaches are described in Sections 3.1 and 3.2 and evaluated in Section 4. Our experiments demonstrate the claimed advantages of our methods over (standard) ACC and PACC on five graph datasets and using multiple base GNN classifiers.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: First, our work focuses, by design, on tackling structural covariate shift in graph quantification learning; our knowledge, are the first consider this problem. We discuss other types of distribution shifts (c.g.. concept shift) in Section 2.1 and explain why focus on covariate shift in particular. Second, our proposed SIS method requires at least some knowledge about the data sampling process; in scenarios where little to no information about the origin of the data is available, SIS may be applicable.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
20

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The theoretical derivation of SIS is provided in Section 3.1.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe all key aspects of our experimental setup and of our approach. Additionally, our code available https://github. cww/ con/Ctrts///// graph-quantifican -uaataaiiaaatiinnn...mmmm It contains instructions on how to reproduce our results. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, deseribing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
21

---

(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. the case of dlosed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code is available at https://gitee com/ Cortys/ graph-quantification It contains instructions how to reproduce results. The code is released under the MIT license.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.ccco wwwpc//pwllcgucueeeeeeeeooceeeee Coaeee//ddeeuemme ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All relevant aspects of the experimental setup are described Section 4.1. The supplement provides additional details. The provided code can be used to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
22

---

Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We do report standard errors in Tables 1, 2. 3 and 4 because the errors very close to zero and therefore not very informative. Instead, as described in Section 4.2, we conduct statistical significance tests compare the performance different quantifiers.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should cxplain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: YYs]
Justification: We describe our experimental setup, including the used compute resources, in the supplement.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httppp////aarrps..cpppp/////ccet otw.lliiieetiicccccceeeeeeeeeeee
Answer: [Yes]
Justification: We carefully read the Code Ethics and hereby confirm that our research conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
23

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: In our work, we consider the general GQL problem under covariate shift without focus particular domain. While there are applications of GQL which could have a societal impact (c.g., voting outcome prediction), we do not evaluate our methods in such domains. Generally, since quantification learning is about predicting the distri- bution of classes in a population, the risks of quantification to the individual are limited. Additionally, we do not release any pretrained models that could be misused.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not include any data or models that have a high risk for misuse. The considered quantification domains citation networks and co-purchasing graphs which do not contain any sensitive information. We do not release any pretrained models, but provide the code to reproduce results.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
24

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: For our implementation, we use parts of the QuaPy library (BSD 3- Clause) [23], additionally, we use five common node classification datasets and cite papers in which they were introduced. The datasets are publicly available and can, for example, be downloaded via the well-known torch-geometric library (MIT license).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification:
We release the code for our new methods under the MIT license. The code is com/Cortys graph quantificatiii with basic docu-
available
mentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemmodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: All experiments were conducted using pre-existing datasets. No new data collected from human subjects.
Guidelines:
25

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: All experiments conducted using pre-existing datasets. No new data was collected from human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs were only used to check and improve the writing of the paper. The core methods in this research and their development do not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve L.MMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : //tp:///ee...peeeee /t/CCoaferenccee222///////// for what should or should not be described.
26


Reviews:
[{"review_id": "BwbGcrqFqV", "reviewer": "Reviewer_KYhC", "summary": "The paper develops a method to estimate the label distribution in a node classification graph problem, under covariate shift.\nTwo adjustments that are tailored to graph data are given. One applies a density ratio correction based on a kernel density estimator, where the kernel is derived from the graph. The second applies an adjustment to label distributions based on homophily between neighboring vertices, in order to alleviate collinearity of label distributions. These adjustments are applied on top of standard adjustments applied for label shifts.\n\nExperiments on several node classification datasets using various classifiers are given, under label shift, and two types of covariate shifts induced by sampling using random walks on the graph. The methods show an overall improved performance over the baseline estimation method.", "questions": "I've listed my suggestions in the strengths and weaknesses part. Otherwise, the paper is well written and I appreciate presentation.\nMore compelling datasets and baselines could make me consider raising my score, though it will still be a borderline case in my opinion.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is nicely written, self contained and the methods are principled, simple, and seem effective. Experiments are compelling as they cover a nice variety of settings.\n\nWeaknesses:\n\nApplying a density ratio correction to adjust for covariate shift is a rather basic technique and even though the paper gives a nice presentation and a solid solution, I am not sure its novelty merits a publication at NeurIPS.\nAt the very least, I would expect a baseline that applies a density ratio correction not based on random walks, e.g. one that learns a probabilistic model to distinguish between the features of the source and target dataset. Even if the suggested method outperforms such a baseline, it wouldn't be surprising since the covariate shift induced in the experiments is tailored to the kernel in proposed method. A much more compelling experiment would consider a covariate shift that occurs naturally in graph data, e.g. by considering two different datasets. It is understandable that it may be difficult to find such data, but there should be a through discussion about it with experiments that examine baselines that handle covariate shift and datasets with shifts that do not adhere to the assumptions underlying the kernel.", "was_revised": true, "final_justification": "Following the author response, which includes additional experiments to address concerns raised in the reviews, I've decided to raise my score. My confidence in this score is not high, as I am not an expert on the topic, but I believe the score is justified.", "rebuttal": "We thank the reviewer for their constructive feedback!\n\n### Inclusion of a feature-based baseline\n\n> I would expect a baseline that applies a density ratio correction not based on random walks, e.g. one that learns a probabilistic model to distinguish between the features of the source and target dataset.\n\nThank you for the suggestion! The goal of SIS is to address *structural covariate shift*; a density ratio correction based on vertex features therefore would not be well-motivated from a theoretical perspective.\n\nNonetheless, we agree, that a feature-based importance sampling approach is an interesting additional baseline.\nTo this end, we have conducted additional experiments with a simple feature-based reweighting approach using the cosine similarity between vertex feature vectors as the kernel $k$.\n\nThe following table compares the AE of this feature-based quantifier (*SIS-Feat*) with other quantifiers using an APPNP model (best results highlighted in **bold**):\n\n| Model & Shift | Quantifier      | CoraML    | CiteSeer  | A. Photos | A. Computers |\n| ------------- | --------------- | --------- | --------- | --------- | ------------ |\n| APPNP PPS     | PCC             | .0374     | .0214     | .0318     | .0390        |\n|               | PACC            | .0217     | .0184     | **.0124** | .0256        |\n|               | SIS-PPR PACC    | **.0203** | **.0171** | .0130     | **.0249**    |\n|               | *SIS-Feat PACC* | .0212     | .0183     | **.0124** | .0255        |\n| APPNP BFS     | PCC             | .0374     | .0737     | .0271     | .0468        |\n|               | PACC            | .0217     | .0603     | .0225     | .0430        |\n|               | SIS-PPR PACC    | **.0203** | **.0574** | **.0213** | **.0395**    |\n|               | *SIS-Feat PACC* | 0.212     | .0985     | **.0220** | .0425        |\n| APPNP RW      | PCC             | .0465     | .0659     | .0293     | .0504        |\n|               | PACC            | .0527     | .0541     | .0282     | .0452        |\n|               | SIS-PPR PACC    | **.0448** | **.0501** | **.0255** | **.0418**    |\n|               | *SIS-Feat PACC* | .0515     | .0744     | .0279     | .0452        |\n\nThe structure-unaware *SIS-Feat* baseline (generally) performs worse than the structure-aware SIS-PPR.\nUnsurprisingly, this confirms that structure-based vertex kernels are better suited than feature-based kernels to account for (structural) covariate shifts.\n\n### Evaluation of \"real\" covariate shift\n\n> A much more compelling experiment would consider a covariate shift that occurs naturally in graph data, e.g. by considering two different datasets. It is understandable that it may be difficult to find such data [...]\n\nSince existing node-classification benchmark datasets generally do not provide enough information to extract \"natural\" structural shifts, a more realistic evaluation is indeed not trivial; in our experiments, we therefore induced different distribution shifts synthetically on real datasets.\n\nUsing two (disjoint) training and test datasets as a source of natural covariate shifts is, unfortunately, not feasible because SIS relies on kernel density estimates across the training and test.\nIf the training and test vertices are not connected, no meaningful structure-based vertex kernel can be defined.\n\nFollowing your suggestion, we thought about other potential sources of realistic structural covariate shifts and found social network datasets to be promising candidates.\nThe \"Twitch Gamers\" dataset [1] is one such dataset; it consists of ~168k vertices and ~6.8 million edges where vertices represent Twitch accounts and edges represent followership relations.\nEach vertex is annotated with the language of the corresponding user, whether the user streams explicit content and a number of other features.\n\nTo provide further insights into the effectiveness of SIS under \"real\" covariate shift, we have now conducted additional experiments using the \"Twitch Gamers\" dataset.\nWe induced covariate shift by using a random subset of all users as training data and then selected different random subsets of the remaining users as test data where each test sample only contains users speaking a single language (EN, DE, FR, RU).\nSampling the test data based on language induces a natural structural covariate shift, since users tend to follow users speaking the same language.\nWe use the binary \"explicit content\" feature of the users as the target.\nThe following table shows the AE achieved by different quantifiers on different language-filtered test splits.\nAll quantifiers use an APPNP node classifier as their base model.\n\n|              |        EN |        DE |        FR |        RU |\n| ------------ | --------: | --------: | --------: | --------: |\n| CC           | **.0040** |     .1187 |     .1147 |     .1771 |\n| ACC          |     .0208 |     .0108 | **.0888** |     .0887 |\n| SIS-PPR ACC  |     .0107 | **.0076** |     .0899 | **.0801** |\n| SIS-PPR NACC |     .0958 |     .3991 |     .1768 |    0.2553 |\n\nSince EN is the majority language in the dataset, there is barely any distribution shift between training and the EN test set; therefore, the unadjusted CC approach performs best.\nFor all other languages, quantification performance is significantly improved via ACC.\nSIS with the PPR kernel further improves performance for the DE and RU test sets; on the FR test set, standard ACC performs slightly better than SIS.\nAdding NACC increases the quantification error; class identifiability is not really an issue in binary quantification.\nOverall, this experiment indicates that SIS can also deal with real-world structural covariate shift.\n\n### On kernel selection\n\n> there should be a through discussion about it [datasets and kernels?] with experiments that examine baselines that handle covariate shift and datasets with shifts that do not adhere to the assumptions underlying the kernel\n\nA discussion of kernel selection and its influence on the effectiveness of SIS can be found in Section B of the supplementary PDF.\n\nThe effectiveness of SIS does not strictly depend on the accuracy of the density estimate $\\hat{q}$; more precisely, the confusion matrix estimate $\\hat{C}$ can be accurate, even if $\\hat{q}$ deviates from $q$.\nUltimately, we are only interested in whether the predictive quality of the classifier $h$ on $\\hat{q}$ is similar to the predictive quality of $h$ on $\\hat{q}$.\nFrom this perspective, we argue that the PPR kernel can be seen as a good \"default\" choice because it (approximately) describes the GNN prediction similarity between vertices.\n\nFurther details on this can be found in the supplement (see Table S1).\nWe compared PPR against an alternative shortest-path-based kernel, which, at first glance, might appear to be a better match than PPR for the BFS-based covariate shift.\nDespite the apparent mismatch between PPR and BFS sampling, the PPR kernel outperforms the shortest-path kernel.\n\n### Novelty\n\n>  even though the paper gives a nice presentation and a solid solution, I am not sure its novelty merits a publication at NeurIPS\n\nWe appreciate the feedback! While the general idea of importance sampling is, of course, not novel by itself, its application in the context of quantification learning is.\n\nTo our knowledge, we are the first to systematically solve the quantification problem in the presence of covariate shift; prior work in the field of quantification learning is mostly concerned with prior probability shift (PPS).\nMoreover, the ideas described in this paper could, in principle, be extended to address covariate shift in quantification problems outside of the graph domain by defining an appropriate kernel for density estimation.\nOverall, we thus believe that our contribution is of relevance not only for graph quantification learning but for the field of quantification learning as a whole.\n\nWe hope that we were able to answer your questions. Thank you, once again, for your comments!\n\n---\n\n1. Rozemberczki, B., Sarkar, R.: Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings (2021)."}, {"review_id": "bpYN5VpfJP", "reviewer": "Reviewer_GwGf", "summary": "The paper tackles the problem of estimating label prevalences on graph-structured data (graph quantification learning) where prior work was confined to simple node-clustering heuristics. It extends the Adjusted Classify & Count (ACC) family beyond the prior probability shift regime by introducing **Structural Importance Sampling (SIS)**, a covariate-shift-aware reweighting scheme that builds a kernelised confusion matrix using personalised PageRank densities so each training vertex votes in proportion to how likely it would have been sampled in the test graph. To resolve the class-identifiability failures that arise when non-homophilic edges blur decision boundaries, the authors add **Neighborhood-aware ACC (NACC)**: every prediction is paired with the majority label of its 1-hop neighbourhood, enlarging the observable confusion signature without retraining the base classifier. Both upgrades drop straight into the standard constrained least-squares ACC solver and gracefully collapse back to vanilla ACC when the shift is pure PPS.\n\nEmpirically, SIS and NACC are plugged on top of four backbones (MLP, GCN, GAT, APPNP) and evaluated on five benchmark graphs (CoraML, CiteSeer, PubMed, Amazon-Photos, Amazon-Computers) under three shift scenarios - prior-probability, BFS-induced covariate, and random-walk covariate. Across 36 model-shift combinations they achieve the best or tied-best average rank in 32 cases, cutting Absolute Error by up to 30-50% relative to Probabilistic ACC.\n\nOverall, by marrying structural reweighting with neighbourhood cues, the paper shows that ACC can be re-tooled to deliver reliable, shift-robust quantification on real-world graphs, establishing SIS + NACC as the first practical framework for graph quantification under covariate shift.", "questions": "1. Could you (a) add at least one naturally shifted graph - e.g. a time-stamped social network split by month, or a sampled Web graph - and (b) report SIS + NACC performance there?\n2. Is it possible to add a sensitivity study ($\\lambda$, L, alternative kernels)?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n**First to tackle covariate-shifted graph quantification:** The paper is the first to lift Adjusted Classify & Count (ACC) from the prior-probability-shift regime to full (structural) covariate shift on graphs, filling a clear gap in quantification research.\n\n**Elegant ACC generalisation (SIS):** Structural Importance Sampling rewrites the test-set confusion matrix as a covariate-shift re-weighting and estimates the density ratio with personalised-PageRank kernels, gracefully collapsing to vanilla ACC when constant kernels are used.\n\n**Neighbourhood cue for identifiability (NACC):** Appending the majority 1-hop label breaks class-confusion collinearity without retraining the base classifier, neatly exploiting homophily yet reverting to standard ACC in purely homophilic graphs.\n\n**Plug-and-play, classifier-agnostic design:** SIS + NACC drop straight into the standard constrained-least-squares ACC solver and work on four very different backbones (MLP, GCN, GAT, APPNP) without any model-specific tuning.\n\n**Consistent empirical gains across shifts:** On five benchmarks and three synthetic shift types, the new quantifiers attain the best or tied-best average rank in 32 / 36 model–shift combinations, cutting Absolute Error by up to 30–50 % over Probabilistic ACC.\n\n**Graceful degradation & interpretability:** Because both upgrades reduce to classic ACC when their extra signal is irrelevant, they inherit ACC’s transparent confusion-matrix interpretation and do not hurt performance under pure PPS.\n\n---\n\n## Weaknesses\n\n**Synthetic evaluation only:** All shifts are injected (Zipf PPS, BFS, RW) on node-classification datasets; the authors explicitly note the absence of real graph-quantification benchmarks, so external validity remains uncertain.\n\n**Kernel sensitivity and hyper-parameter exposure:** SIS assumes a local random-walk sampling process and relies on a PPR kernel with a user-set $\\lambda$ and walk length L; in BFS shifts the kernel is acknowledged to be a mismatch, hinting that performance may hinge on careful kernel engineering.\n\n**Homophily dependency and noise trade-off:** NACC presumes that neighbours share labels; on heterophilic or sparsely connected graphs its extra confusion features may be noisy, and the authors concede that adding deeper-hop information quickly degrades estimates.\n\n**Scalability not analysed:** Computing PPR densities for every training vertex can be $O(|V|^3)$ in the worst case; the paper gives no runtime or memory study, leaving open whether SIS is feasible for million-node graphs.\n\n**Baseline breadth limited:** Comparisons stop at CC/ACC and ENQ; distribution-matching quantifiers and recent deep quantification methods are only mentioned as future work, so the empirical case is incomplete.", "was_revised": true, "final_justification": "* **Overall reaction**\n\n  * Thanks for the thorough rebuttal; most of my methodological concerns are now well-addressed.\n  * The added Twitch-Gamers experiment and kernel-sensitivity appendix materially strengthen the empirical story.\n  * One issue - breadth of baselines - remains only partially resolved.\n\n* **Positives after rebuttal**\n\n  * *Real-world shift*: New Twitch results show SIS can help under natural covariate shift; this boosts confidence in external validity.\n  * *Kernel robustness*: Section B’s $\\lambda$-sweep and alternative-kernel study demonstrate that PPR is a reasonable default and that performance is not hyper-fragile.\n  * *Scalability*: Complexity analysis plus the 168k-node run suggest practicality for medium-sized graphs.\n  * *Clarified assumptions*: Explanation of how NACC copes with local heterophily clarifies when it helps and when it can hurt.\n\n* **Residual concerns / suggestions**\n\n  * *Baseline scope*: I still believe at least one distribution-matching or deep-quantification baseline would make the empirical claim more compelling. Even a compact ablation on one dataset would suffice.\n  * *Appendix reliance*: Key evidence (kernel study, scalability) lives only in the supplement. A short summary in the main paper would aid readers.\n  * *Binary vs. multi-class*: Twitch experiment is binary; it would be nice to confirm gains on a multi-class natural shift, though I acknowledge space limits.\n\n* **Recommendation update**\n\n  * I raise my overall score to **Accept**- the new evidence tips the balance in favor of the paper, despite the still-narrow baseline comparison.", "rebuttal": "Thank you for the the well-structured and constructive review! We will go over the mentioned weaknesses in order.\n\n### Synthetic evaluation only (Q1)\n\nSince existing node-classification benchmark datasets generally do not provide enough information to extract \"natural\" structural shifts, a more realistic evaluation is indeed not trivial; for this reason we decided to induce different distribution shifts synthetically on real datasets.\nDespite these difficulties, we will now attempt to provide at least some evidence towards external validity.\n\nSocial network datasets are a promising source of realistic structural covariate shifts.\nThe \"Twitch Gamers\" dataset [1] is one such dataset; it consists of ~168k vertices and ~6.8 million edges where vertices represent Twitch accounts and edges represent followership relations.\nEach vertex is annotated with the language of the corresponding user, whether the user streams explicit content and a number of other features.\n\nTo provide further insights into the effectiveness of SIS under \"real\" covariate shift, we have conducted additional experiments using the \"Twitch Gamers\" dataset.\nWe induced covariate shift by using a random subset of all users as training data and then selected different random subsets of the remaining users as test data where each test sample only contains users speaking a single language (EN, DE, FR, RU).\nSampling the test data based on language induces a natural structural covariate shift, since users tend to follow users speaking the same language.\nWe use the binary \"explicit content\" feature of the users as the target.\nThe following table shows the AE achieved by different quantifiers on different language-filtered test splits.\nAll quantifiers use an APPNP node classifier as their base model.\n\n|              |        EN |        DE |        FR |        RU |\n| ------------ | --------: | --------: | --------: | --------: |\n| CC           | **.0040** |     .1187 |     .1147 |     .1771 |\n| ACC          |     .0208 |     .0108 | **.0888** |     .0887 |\n| SIS-PPR ACC  |     .0107 | **.0076** |     .0899 | **.0801** |\n| SIS-PPR NACC |     .0958 |     .3991 |     .1768 |    .2553 |\n\nSince EN is the majority language in the dataset, there is barely any distribution shift between training and the EN test set; therefore, the unadjusted CC approach performs best.\nFor all other languages, quantification performance is significantly improved via ACC.\nSIS with the PPR kernel further improves performance for the DE and RU test sets; on the FR test set, standard ACC performs slightly better than SIS.\nAdding NACC increases the quantification error; class identifiability is not really an issue in binary quantification.\nOverall, this experiment indicates that SIS can also deal with real-world structural covariate shift.\n\n### Kernel sensitivity and hyper-parameter exposure (Q2)\n\nWe fully agree that the kernel selection problem deserves further attention.\nFor this reason, we included an extended discussion of the influence of the vertex kernel and its hyperparameters in Section B of the supplement PDF.\n\nThere, we evaluate the influence of $\\lambda$ on the PPR kernel and explain why a value of $\\lambda$ slightly below $1$ tends to perform best (Section B.2).\nAdditionally, we explain why the PPR kernel is a good \"default\" choice for SIS (Section B.1).\n\nThe general appropriateness of the PPR kernel is supported empirically by Table S1 of the supplement.\nThere, we compare PPR against an alternative shortest-path-based kernel, which, at first glance, might appear to be a better match than PPR for the BFS-based covariate shift.\nDespite the apparent mismatch between PPR and BFS sampling, the PPR kernel outperforms the shortest-path kernel.\n\nLast, an evaluation of the influence of the hyperparameters of the shortest-path kernel is provided in Section B.3 of the supplement.\n\n### Homophily dependency and noise trade-off\n\nWhile, both, SIS and NACC are designed for quantification problems on graphs that are (mostly) homophilic, no strict formal assumptions on homophily are made.\nIn fact, NACC is motivated by the fact that even homophilic graphs can have non-homophilic subgraphs.\n\nIn such non-homophilic subgraphs (see, for example, class/cluster 7 in Figure 1 of the main paper), columns in the confusion matrix $C$ can become collinear, turning quantification into an ill-posed problem.\nNACC addresses this issue by incorporating neighborhood information; this effectively allows NACC to distinguish between homophilic and heterophilic subgraphs.\n\nTo summarize, while we assume homophily in general, NACC can help with local violations of this homophily assumption.\n\nLast, to avoid confusion, we want to clarify that the reason why second- or third-order vertex neighborhoods in NACC can degrade performance is not due to homophily or heterophily but because of the resulting sample sizes for the confusion matrix estimate.\n\n### Scalability not analysed\n\nAn analysis of the runtime of SIS and NACC was omitted from the main paper due to the page limit.\nWe discuss the time complexity and scalability of our approach in Section C of the appendix.\n\nNaively, the PPR densities can be computed in $O(|V|^{3 \\log_2 L})$.\nTo apply SIS with the PPR kernel to large graphs, there are multiple options:\n1. The kernel is not evaluated for all vertex pairs. Thus, computing a power of the entire adjacency matrix is not necessary. Instead, only train-test-pairs have to be computed. If either the training or the test data is small, one can compute the relevant kernel values in $O((|V|^2 \\cdot \\min ( |D_L|, |\\mathcal{V}_U|))^{\\log_2 L})$.\n2. For densely connected graph, matrix multiplication can be sped up using Strassen's algorithm.\n3. For sparse graphs, performance can be further improved via sparse-sparse or sparse-dense matrix multiplications. Combined with option 1, the relevant part of the PPR kernel can be computed in $O((|\\mathcal{E}| \\cdot \\min ( |D_L|, |\\mathcal{V}_U|))^{\\log_2 L})$ via sparse-dense matrix multiplications.\n\nUsing these optimizations, we were able to apply SIS to a graph with ~168k vertices (see rebuttal to KYhC) on a consumer PC with 64GB memory.\nAssuming sparsity, computing a kernel for a graph with over 1 million vertices is feasible.\n\n### Baseline breadth limited\n\nWe did not include quantification results for other quantification methods to allow for a fair comparison.\nTo demonstrate the effectiveness of SIS and NACC, which are extensions of (P)ACC, they should be compared against their respective \"base\" quantification method.\n\nNonetheless, we agree that an extension of our work to other quantification methods, like distribution matching, would indeed be interesting.\nIn fact, since the submission, we have finished a follow-up work which generalizes SIS to the distribution matching setting.\nOverall, we found, that SIS also performs strongly in the distribution-matching setting.\n\nWe hope that we were able to answer your questions and address your suggestions. Thank you for your time and effort!\n\n---\n\n1. Rozemberczki, B., Sarkar, R.: Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings (2021)."}, {"review_id": "Ozah8CRXk9", "reviewer": "Reviewer_ohSm", "summary": "This paper studies the quantification learning problem in the context of graph-structured data. The quantification learning aims to predict the label distribution of a set of instances. Compared to previous clustering based models, this paper extends the popular Adjusted Classify & Count (ACC) method to graphs, and proposes structural importance sampling (SIS) for covariate shift and Neighborhood-aware ACC to improve the quantification in the presence of non-homophilic edges.", "questions": "see above", "limitations": "see above", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The strengths are as follows:  \n1.Clear problem demonstration. The definition of quantification learning on graphs is well demonstrated, including its necessity, potential application, difference from traditional instance classification on graphs.  \n2.Good background writing. The types of distribution shift, like concept shift, covarite shift and prior probability shift are well illustrated.  \n\nThe weakness are as follows:  \n1.Although the quantification learning sounds a reasonable research prolem on graphs, I still think the instanece classification on graphs, together with aggregation models can well handle this problem. To be specific, the instance classification on graphs is well studied and many works can reach high performance on the used datasets, Citeseer, Pubmed and so on. Also, the results in Table 1 with AE and RAE seem not good metrics for researchers to understand how good the performance is. Any other metrics like classification acc?  \n2.The used datasets are limited. Any true benchmark datasets for this quantification task? Not the generated datasets from common GNN datasets.  \n3.The experiments are simple and monotonous, which is not convincing to illustrate the model's effectiveness.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for sharing your concerns! We will address them in order.\n\n### 1. Why quantification? Why AE and RAE?\n\n> I still think the instanece classification on graphs, together with aggregation models can well handle this problem\n\nAs described in the introduction, while a perfect classifier also solves the quantification problem perfectly, a classifier that is \"just\" good, but not perfect, can be a poor quantifier and vice versa (a poor classifier can be a good quantifier).\nSee Esuli et al. [1, Section 1.2] for a more in-depth explanation of why classification and quantification are two distinct tasks.\n\nIn practice, vertex classifiers are rarely perfect. Consider Table 1, the *PCC* rows show the quantification performance of a naive classification-based quantification without any adjustments for different combinations of GNN-based classifiers and datasets.\nThe *PACC* rows show the quantification performance of the classifiers with quantification-specific adjustments.\n\nIf we compare PCC and PACC, PACC consistently and significantly outperforms PCC across classifier-types and datasets (both, in terms of absolute error and relative absolute error).\nThe absolute error of PCC is oftentimes more than twice as large as that of the quantification-specific PACC approach.\nEven for the APPNP classifier, which is the most accurate among the evaluated ones, PACC outperforms PCC.\n\nOverall, this is very strong empirical evidence for usefulness of quantification in the graph setting.\nFrom this perspective, standard classification approaches cannot handle this problem well.\n\n> AE and RAE seem not good metrics for researchers to understand how good the performance is. Any other metrics like classification acc?\n\nIn the literature on quantification, AE and RAE are among the most commonly used metrics to evaluate quantification performance. See Esuli et al. [1, Section 3.1] for an overview.\n\nTo avoid misunderstandings, note that quantification and classification are two distinct tasks.\nIn quantification, our goal is to predict a class distribution for a given dataset; in classification we want to predict a class for each instance in a given dataset.\nThus, quantification can be seen as a dataset-level task, while classification is an instance-level task.\n\nFor example, in binary quantification we might be interested in predicting the percentage of a population with a given disease (e.g., 23% have the disease, 77% do not).\nIf our quantifier now predicts that only 21% of the population has the disease (79% do not), AE measures the quantification error as $\\frac{1}{2}(|0.21 - 0.23| + |0.79 - 0.77|) = 0.02$.\n\nClassification metrics, such as accuracy, cannot be used to evaluate quantification performance.\n\n### 2. More realistic evaluation\n\nSince existing node-classification benchmark datasets generally do not provide enough information to extract \"natural\" structural shifts, a more realistic evaluation is not trivial; for this reason we decided to induce three different types of distribution shifts synthetically on real datasets.\nTo further strengthen our claim that SIS is effective at tackling structural covariate shift, we have created a more realistic graph quantification task.\n\nSocial network datasets are a promising source of realistic structural covariate shifts.\nThe \"Twitch Gamers\" dataset [2] is one such dataset; it consists of ~168k vertices and ~6.8 million edges where vertices represent Twitch accounts and edges represent followership relations.\nEach vertex is annotated with the language of the corresponding user, whether the user streams explicit content and a number of other features.\n\nTo provide further insights into the effectiveness of SIS under \"real\" covariate shift, we have conducted additional experiments using the \"Twitch Gamers\" dataset.\nWe induced covariate shift by using a random subset of all users as training data and then selected different random subsets of the remaining users as test data where each test sample only contains users speaking a single language (EN, DE, FR, RU).\nSampling the test data based on language induces a natural structural covariate shift, since users tend to follow users speaking the same language.\nWe use the binary \"explicit content\" feature of the users as the target.\nThe following table shows the AE achieved by different quantifiers on different language-filtered test splits.\nAll quantifiers use an APPNP node classifier as their base model.\n\n|              |        EN |        DE |        FR |        RU |\n| ------------ | --------: | --------: | --------: | --------: |\n| CC           | **.0040** |     .1187 |     .1147 |     .1771 |\n| ACC          |     .0208 |     .0108 | **.0888** |     .0887 |\n| SIS-PPR ACC  |     .0107 | **.0076** |     .0899 | **.0801** |\n| SIS-PPR NACC |     .0958 |     .3991 |     .1768 |    .2553 |\n\nSince EN is the majority language in the dataset, there is barely any distribution shift between training and the EN test set; therefore, the unadjusted CC approach performs best.\nFor all other languages, quantification performance is significantly improved via ACC.\nSIS with the PPR kernel further improves performance for the DE and RU test sets; on the FR test set, standard ACC performs slightly better than SIS.\nAdding NACC increases the quantification error; class identifiability is not really an issue in binary quantification.\nOverall, this experiment indicates that SIS can also deal with real-world structural covariate shift.\n\n### 3. Monotonous experiments\n\n>The experiments are simple and monotonous, which is not convincing to illustrate the model's effectiveness.\n\nWe appreciate the feedback!\nFor space reasons, we found a large table to be most space-efficient to represent our empirical results.\nWhile the presentation might be visually monotonous, our experiments do cover three different types of distribution shift across all combinations of 5 classifiers, 5 datasets and 5 quantification approaches.\n\nTo quickly get an overall idea of the effectiveness of SIS and NACC, we included the column *Avg. Rank* which ranks the different quantification approaches for each shift setting and classifier from best (typeset in **bold**) to worst.\nOverall, either our proposed *SIS PACC* or our proposed *SIS NEIGH PACC* (SIS combined with NACC) achieves the best average quantification performance in all settings, showing that they are, indeed, effective.\n\nTo make the date more digestible, we could split up the three shift settings into separate tables and, if the space permits, add some plots to make general trends in the data more visually apparent.\n\nLast, we want to note that you can find additional experimental evaluations in the *supplementary PDF*. There, we included plots evaluating the effect of kernel hyperparameters on quantification performance, along with a more in-depth analysis of the results.\n\n\nWe hope that we were able to address your concerns and that you find these additional explanations helpful.\n\n\n---\n1. Esuli, A. et al.: Learning to Quantify. Springer, Cham (2023).\n2. Rozemberczki, B., Sarkar, R.: Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings (2021)."}, {"review_id": "rILpSk1sNn", "reviewer": "Reviewer_ZwZ8", "summary": "This paper tackles the problem of quantification learning (QL), that is, estimating label distributions instead of individual labels using the  graph-structured data. This problem is not explored for graph data yet. The authors identify limitations of existing approaches, particularly the adjusted classify & count (ACC) method under prior probability shift assumptions and this usually fails in graphs due to structural covariate shifts. Accordingly, the authors propose two key innovations:\n(a) Structural Importance Sampling (SIS), which generalizes ACC to handle covariate shifts using kernel density estimation, and\n(b) Neighborhood-aware ACC (NACC), which leverages neighborhood structure to improve class distinguishability in non-homophilic graphs. \nThe authors also conducted thorough experiments using 5 graph datasets and 3 types of distribution shift (PPS, BFS-based, and RW-based covariate shift) and demonstrated that their approaches outperform the existing baselines (measured using 2 metrics: absolute error (AE) and relative absolute error (RAE)).", "questions": "Please answer the following questions:\n\n(a) SIS requires an estimate of the sampling distribution, which in practice assumes knowledge of the structural data generation or sampling process. This is a non-trivial requirement in real-world applications. How to address this challenge? With this, the potential impact of the proposed approach becomes limited. What are the alternatives to avoid this? Any thoughts?\n\n(b) SIS depends on graph kernels and density estimation. They are typically compute heavy tasks and may not scale to large graphs. How to address this computational scaling issue?\n\n(c) The authors work with synthetically induced distribution shifts on standard node classification datasets. These artificial or generated distribution shifts might not capture realistic scenarios as they are more complex in practice. How would you tackle this limitation in your experiments?", "limitations": "Below are my key comments and concerns on this paper:\n\n(a) SIS requires an estimate of the sampling distribution, which in practice assumes knowledge of the structural data generation or sampling process. This is a non-trivial requirement in real-world applications. How to address this challenge? With this, the potential impact of the proposed approach becomes limited. What are the alternatives to avoid this? Any thoughts?\n\n(b) SIS depends on graph kernels and density estimation. They are typically compute heavy tasks and may not scale to large graphs. How to address this computational scaling issue?\n\n(c) The authors work with synthetically induced distribution shifts on standard node classification datasets. These artificial or generated distribution shifts might not capture realistic scenarios as they are more complex in practice. How would you tackle this limitation in your experiments?", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Below are my key comments and concerns on this paper:\n\n(a) SIS requires an estimate of the sampling distribution, which in practice assumes knowledge of the structural data generation or sampling process. This is a non-trivial requirement in real-world applications. How to address this challenge? With this, the potential impact of the proposed approach becomes limited. What are the alternatives to avoid this? Any thoughts?\n\n(b) SIS depends on graph kernels and density estimation. They are typically compute heavy tasks and may not scale to large graphs. How to address this computational scaling issue?\n\n(c) The authors work with synthetically induced distribution shifts on standard node classification datasets. These artificial or generated distribution shifts might not capture realistic scenarios as they are more complex in practice. How would you tackle this limitation in your experiments?", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the constructive feedback by the reviewer and will address the raised points individually.\n\n### (a) Kernel-selection\n\nWe fully agree that the relation between the data generating process and the kernel selection deserves further attention.\nTo understand this relation, we will proceed in two steps:\n1. What can and should one know about the data generating process?\n2. How close does the kernel have to be aligned with the data generating process?\n\nUltimately, the difficulty of determining whether a kernel is appropriate for a given problem depends on the amount of information available about the instance sampling process, i.e., about $P(V)$ and $Q(V)$.\nIn practice, it is not unrealistic to assume that at least some information about those distributions is given.\n\nFor example, consider a setting where the test nodes represent the social circle of a randomly selected person from a given community.\nSuch test sets are natural if, for example, one wants to estimate the homogeneity of opinions among the friends (or friends of friends) of a person.\nIf we know that the test sets consist of such connected social circles, this knowledge can be used to design a kernel, i.e., to estimate how likely it is that a given labeled vertex $v$ from $\\mathcal{D}_L$ is sampled via the test distribution $Q(V)$, given samples $\\mathcal{V}_U$.\nFor this example, the probability of sampling $v$ corresponds to the probability of $v$ being part of the given social circle, which, in turn, depends on the distance between $v$ and the samples $\\mathcal{V}_U$.\nA shortest-path kernel, as described in Eq. (S2) of the supplement, or some variant of it, is a reasonable choice in this case, as it determines the likelihood of a sample based on the distance between vertices.\nThe parameterization of such a distance-based kernel then depends on properties of the social network, e.g., average node degrees and edge homophily.\nThe kernel parameters should be treated as hyperparameters that need empirical tuning.\n\nWhile it is unrealistic to analytically derive an \"optimal\" kernel for real-world quantification problems, we hope that the above example illustrates that $k$ can be chosen in an informed manner without relying on pure trial-and-error.\n\nHowever, even if we have incomplete or incorrect information about the data generating process, SIS can be effective.\nNote that the effectiveness of SIS does not strictly depend on the accuracy of the density estimate $\\hat{q}$; more precisely, the confusion matrix estimate $\\hat{C}$ can be accurate, even if $\\hat{q}$ deviates from $q$.\nUltimately, we are only interested in whether the predictive quality of the classifier $h$ on $\\hat{q}$ is similar to the predictive quality of $h$ on $\\hat{q}$.\nFrom this perspective, the PPR kernel can then be seen as a good \"default\" choice because it (approximately) describes the GNN prediction similarity between vertices.\nSee Section B of the supplementary PDF for further discussion of this.\n\nThe general appropriateness of the PPR kernel is supported empirically by Table S1 of the supplement.\nThere, we compare PPR against an alternative shortest-path-based kernel, which, at first glance, might appear to be a better match than PPR for the BFS-based covariate shift.\nDespite the apparent mismatch between PPR and BFS sampling, the PPR kernel outperforms the shortest-path kernel.\n\nLast, an evaluation of the influence of the hyperparameters of the shortest-path kernel is provided in Section B.3 of the supplement.\n\n### (b) Computational complexity\n\nAn analysis of the runtime of SIS and NACC was omitted from the main paper due to the page limit.\nWe discuss the time complexity and scalability of our approach in Section C of the appendix.\n\nNaively, the PPR densities can be computed in $O(|V|^{3 \\log_2 L})$; this does not scale to large graphs.\n\nTo apply SIS with the PPR kernel to large graphs anyway, there are multiple options:\n1. The kernel is not evaluated for all vertex pairs. Thus, computing a power of the entire adjacency matrix is not necessary. Instead, only train-test-pairs have to be computed. If either the training or the test data is small, one can compute the relevant kernel values in $O((|V|^2 \\cdot \\min ( |D_L|, |\\mathcal{V}_U|))^{\\log_2 L})$.\n2. For densely connected graph, matrix multiplication can be sped up using Strassen's algorithm.\n3. For sparse graphs, performance can be further improved via sparse-sparse or sparse-dense matrix multiplications. Combined with option 1, the relevant part of the PPR kernel can be computed in $O((|\\mathcal{E}| \\cdot \\min ( |D_L|, |\\mathcal{V}_U|))^{\\log_2 L})$ via sparse-dense matrix multiplications.\n\nAs described in (c), we have conducted an additional experiment on the large-scale Twitch Gamers dataset, containing ~168k vertices.\nUsing the techniques described above (partial kernel eval, sparse matrix multiply), computing the PPR kernel is feasible even for large graphs.\n\n### (c) Synthetic evaluation only\n\nSince existing node-classification benchmark datasets generally do not provide enough information to extract \"natural\" structural shifts, a more realistic evaluation is not trivial; for this reason we decided to induce three different types of distribution shifts synthetically on real datasets.\nTo further strengthen our claim that SIS is effective at tackling structural covariate shift, we have created a more realistic graph quantification task.\n\nSocial network datasets are a promising source of realistic structural covariate shifts.\nThe \"Twitch Gamers\" dataset [1] is one such dataset; it consists of ~168k vertices and ~6.8 million edges where vertices represent Twitch accounts and edges represent followership relations.\nEach vertex is annotated with the language of the corresponding user, whether the user streams explicit content and a number of other features.\n\nTo provide further insights into the effectiveness of SIS under \"real\" covariate shift, we conducted additional experiments using the \"Twitch Gamers\" dataset.\nWe induced covariate shift by using a random subset of all users as training data and then selected different random subsets of the remaining users as test data where each test sample only contains users speaking a single language (EN, DE, FR, RU).\nSampling the test data based on language induces a natural structural covariate shift, since users tend to follow users speaking the same language.\nWe use the binary \"explicit content\" feature of the users as the target.\nThe following table shows the AE achieved by different quantifiers on different language-filtered test splits.\nAll quantifiers use an APPNP node classifier as their base model.\n\n|              |        EN |        DE |        FR |        RU |\n| ------------ | --------: | --------: | --------: | --------: |\n| CC           | **.0040** |     .1187 |     .1147 |     .1771 |\n| ACC          |     .0208 |     .0108 | **.0888** |     .0887 |\n| SIS-PPR ACC  |     .0107 | **.0076** |     .0899 | **.0801** |\n| SIS-PPR NACC |     .0958 |     .3991 |     .1768 |    .2553 |\n\nSince EN is the majority language in the dataset, there is barely any distribution shift between training and the EN test set; therefore, the unadjusted CC approach performs best.\nFor all other languages, quantification performance is significantly improved via ACC.\nSIS with the PPR kernel further improves performance for the DE and RU test sets; on the FR test set, standard ACC performs slightly better than SIS.\nAdding NACC increases the quantification error; class identifiability is not really an issue in binary quantification.\nOverall, this experiment indicates that SIS can also deal with real-world structural covariate shift.\n\nWe would like to thank the reviewer once again for their constructive critique of our work! We hope that we were able to answer your questions and clear up any concerns.\n\n---\n1. Rozemberczki, B., Sarkar, R.: Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings (2021)."}]

Author rebuttal:

Meta-review: This paper studies quantification learning (i.e., predicting the label distribution of a set of instances) for graphs (where instances are the graph nodes). This paper extends the adjusted classify and count (ACC) method for graph inputs with structural importance sampling. Notably, the method is effective under structural covariate shift. The second contribution is neighborhood-aware ACC, which improves quantification for non-homophilic graphs.

The paper received mixed reviews. However, those leaning towards rejection are based on a misunderstanding of the paper context and purpose. The remaining concerns were successfully addressed by the authors. Overall, I find that this paper tackles an under-researched but important problem (quantification on graphs) with a sufficiently innovative methodology. Therefore, I recommend acceptance, provided that all the reasonable suggestions made by the reviewers are implemented in the revised version.
Decision: Accept (poster)