REVIEW 2 major objections 4 minor 54 references
Data Pricing for Graph Neural Networks without Pre-purchased Inspection
T0 review · 2 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read The paper claims that graph data for GNN training can be priced and procured through a structural-importance auction that is incentive-compatible, individually rational, and budget-feasible, without any pre-purchase inspection.
desk verdict New problem and solid experiments, but the central incentive-compatibility theorem is false; the mechanism is not IC as stated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the structural importance score $\phi_v = (1-\alpha)\phi_v^{\mathrm{rep}} + \alpha \phi_v^{\mathrm{info}}$ for each node $v$. Here $\phi_v^{\mathrm{info}}$ is the normalized marginal structural entropy of $v$, the relative drop in structural entropy when $v$ is moved out of its cluster (lower means more informative), and $\phi_v^{\mathrm{rep}}$ is $v$'s PageRank centrality rank within its cluster (higher means more representative). The clusters themselves are learned by an unsupervised graph auto-encoder that approximately maximizes structural entropy. These scores are then combined with reported costs in a per-cluster budget-feasible auction with threshold pricing, and the procured data is completed with feature propagation and edge augmentation before the GNN is trained.
What would settle it
Take a two-owner graph where owner A holds two nodes and owner B holds one node, with structural scores and B's cost chosen so that A's reported cost determines whether B is the first fully unselected owner. Compute A's utility when reporting truthfully and when reporting a slightly lower cost for one node; if the lower report raises A's total payment minus true cost, Theorem 4.2's incentive-compatibility claim is false.
Extended reading notes
Core claim
The paper's central claim is Theorem 4.2: the SIMT mechanism is incentive compatible, individually rational, and budget feasible. The mechanism splits nodes into structural clusters, sorts each cluster's nodes by the ratio of structural importance score to reported cost, buys the top k nodes until the cluster budget is exhausted, and pays each selected node the smaller of a proportional share of the cluster budget and the price implied by the first owner with no selected data. Because the structural score of a node comes from graph topology alone and is independent of anyone's reported cost, the authors argue that this payment rule induces truthful per-node valuations, guarantees non-negative utility to every participant, and keeps the total payment at or below the budget. The same structural scores are then validated empirically: across five datasets, SIMT's purchased data yields higher per-node contribution to classification accuracy than data chosen by greedy or reconstruction-loss baselines.
Load-bearing premise
The proof that SIMT is incentive-compatible assumes that when one data owner changes her reported price, the first fully unselected owner and the number of purchased items stay the same; this is true when each owner sells one node, but for owners holding several nodes a single report can move the cutoff and change the owner's total payment.
Editorial extensions
If this is right
- Data owners in a model marketplace can be paid for their graph data without ever disclosing it, removing the main practical obstacle to pre-purchase inspection.
- A buyer with a fixed budget can purchase only the most structurally informative and representative nodes and still train a competitive GNN, since each purchased node contributes more to accuracy than nodes chosen by cost alone.
- The mechanism's guarantees are per-node: truthful reporting is an equilibrium, no participant is made worse off, and the total payment never exceeds the budget, so a consumer can set a budget in advance and be certain of the spend.
- The structural-importance scoring is computable before any data is seen, using only the known edges between and within subgraphs, so the approach is applicable in privacy-conscious or federated settings.
Reading between the lines
- Editor's inference: the same structural-importance auction template could be applied to other relational data marketplaces—recommender systems, supply-chain graphs, or protein interaction networks—wherever structure is observable before content is paid for.
- Editor's inference: the paper's proof treats the threshold owner and cutoff k as fixed when one owner changes her report; this is guaranteed when every owner holds one node but is open to question when a single owner holds many nodes, so extending IC to multi-node owners would require a separate argument or a modified payment rule.
- Editor's inference: a natural testable extension is an adaptive version that re-clusters and re-scores after each round of purchases, which the paper lists as future work and which could buy more informative data at the same budget.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes SIMT, a two-phase mechanism for trading graph-structured data in a model marketplace without pre-purchased inspection. In the procurement phase, a structural importance score is computed from clustering, marginal structural entropy, and PageRank, and an auction selects nodes by descending importance-to-reported-valuation ratio within each cluster. Payments are capped by a budget-share term and a threshold term based on the first owner with no selected node. The paper claims that SIMT is incentive compatible, individually rational, and budget feasible (Theorem 4.2), and it reports experiments on five datasets showing accuracy gains over baselines. The central theoretical claim is the focus of this review.
Significance. If Theorem 4.2 were correct, the paper would address a genuine and timely gap: pricing graph-structured data for GNN training without requiring data owners to disclose data before payment. The empirical study is fairly extensive, covering multiple datasets, budgets, ablations, and GNN architectures, and the proposed structural-importance scoring is a reasonable heuristic. However, the mechanism's stated guarantee of incentive compatibility is the load-bearing theoretical contribution, and that guarantee is false. The paper's advertised contribution as a mechanism with IC/IR/BF therefore does not stand, even though the empirical pipeline may still have heuristic value.
major comments (2)
- [Section 4.3, Theorem 4.2] The IC proof is invalid because the statement 'the payment of i for v is independent from i's report' in case (1) is false when owner i controls multiple nodes. A single reported theta_i enters every ratio phi_v/theta_i for all nodes owned by i, so i's report changes the cutoff k, the identity of the first fully unselected owner j, and all payments to i simultaneously. The proof treats k and j as fixed, which is only legitimate when each owner supplies at most one node.
- [Section 4.2/4.3, Theorem 4.2]
minor comments (4)
- [Section 4.2, Algorithm 1 line 8] The expression 'theta_k <= phi_k / sum_{u<=k} phi_u * beta/T' should be parenthesized as (phi_k / sum_{u<=k} phi_u) * (beta/T); as written the precedence is ambiguous.
- [Section 4.2, payment definition] The definition of j as 'the first data owner who has not had any data selected' requires a tie-breaking rule for equal ratios and a precise rule for owners with multiple nodes whose nodes are interleaved in the sorted order; the current text does not fully specify this.
- [Definition 4.1 and Appendix A] The term for the number of incident nodes inside the cluster is denoted n_{v,t} in Definition 4.1 but x_{v,t} in the appendix calculation; the notation should be unified.
- [Section 4.3, IR proof] In the individual-rationality proof, the assertion that the selected-node utility min{...} - theta_i is nonnegative is stated without derivation; a short argument using the sorting and the cutoff condition would make the proof self-contained.
Circularity Check
No significant circularity; the Theorem 4.2 proof gap is a soundness issue, not a circular reduction.
full rationale
The paper's central claims are empirical and theoretical, and neither reduces to its own inputs. The structural importance score (Eq. 1) is computed from graph topology via clustering, marginal structural entropy, and PageRank, without using the target features or labels; the experimental comparisons in Table 1 use standard datasets with a 15% test set untouched during data procurement, so the reported performance gains are not fitted to the evaluation data. The proof of Theorem 4.2 derives IC, IR, and BF from the mechanism's own definitions rather than importing a conclusion from prior work. The self-citations [25], [43], and [49] are background references for structural entropy, unsupervised GNN-based clustering, and earlier auction work; none is used as a uniqueness theorem or as an ansatz that defines the target result, so they are not load-bearing. The proof of Theorem 4.2 does contain a genuine correctness gap: the sentence 'the payment of i for v is independent from i's report' is false when one owner controls multiple nodes, because changing that owner's report can change the cutoff k and the threshold owner. That is a soundness flaw, not a circularity, because the proof does not assume the conclusion it is trying to establish, and the empirical claims are independently benchmarked against held-out test sets. Accordingly, there is no significant circularity; the score of 1 reflects only the presence of minor, non-load-bearing self-citations.
Assumptions & free parameters
free parameters (3)
- alpha_balance =
unclear formula: stated as 0.5*(1 + beta/(n*theta)) - T
- PageRank damping factor gamma =
not stated
- contrastive temperature tau =
not stated
assumptions (5)
- domain assumption Graph homophily holds: nodes with similar labels and features are more likely to be connected.
- domain assumption Structural clusters approximate true classes.
- domain assumption Each data owner values all her nodes equally, giving linear total valuation.
- domain assumption Cross-subgraph edges are known to the model consumer.
- domain assumption The VGAE-based clustering produces a partition close enough to the true classes.
Cite this review
Pith. "Pith review of Data Pricing for Graph Neural Networks without Pre-purchased Inspection." pith.science (2026). https://pith.science/paper/4O6SLHCL
@misc{pith2026250208284,
author = {Pith},
title = {Pith review of: Data Pricing for Graph Neural Networks without Pre-purchased Inspection},
year = {2026},
howpublished = {\url{https://pith.science/paper/4O6SLHCL}},
note = {Machine review of arXiv:2502.08284}
}
abstract
Machine learning (ML) models have become essential tools in various scenarios. Their effectiveness, however, hinges on a substantial volume of data for satisfactory performance. Model marketplaces have thus emerged as crucial platforms bridging model consumers seeking ML solutions and data owners possessing valuable data. These marketplaces leverage model trading mechanisms to properly incentive data owners to contribute their data, and return a well performing ML model to the model consumers. However, existing model trading mechanisms often assume the data owners are willing to share their data before being paid, which is not reasonable in real world. Given that, we propose a novel mechanism, named Structural Importance based Model Trading (SIMT) mechanism, that assesses the data importance and compensates data owners accordingly without disclosing the data. Specifically, SIMT procures feature and label data from data owners according to their structural importance, and then trains a graph neural network for model consumers. Theoretically, SIMT ensures incentive compatible, individual rational and budget feasible. The experiments on five popular datasets validate that SIMT consistently outperforms vanilla baselines by up to $40\%$ in both MacroF1 and MicroF1.
Figures
Reference graph
Works this paper leans on
-
[1]
Jacob Abernethy, Yiling Chen, Chien-Ju Ho, and Bo Waggoner. 2015. Low- cost learning via active data procurement. In Proceedings of the Sixteenth ACM Conference on Economics and Computation . 619–636
work page 2015
-
[2]
Anish Agarwal, Munther Dahleh, and Tuhin Sarkar. 2019. A marketplace for data: An algorithmic solution. In Proceedings of the 2019 ACM Conference on Economics and Computation. 701–726
work page 2019
-
[3]
Dimitrios Bechtsis, Naoum Tsolakis, Eleftherios Iakovou, and Dimitrios Vlachos
-
[4]
Béla Bollobás. 1998. Random graphs. Springer
work page 1998
-
[5]
Steven L Brunton and J Nathan Kutz. 2022. Data-driven science and engineering: Machine learning, dynamical systems, and control . Cambridge University Press
work page 2022
-
[6]
John Burkardt. 2014. The truncated normal distribution. Department of Scientific Computing Website, Florida State University 1 (2014), 35
work page 2014
-
[7]
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2017. Active learning for graph embedding. arXiv preprint arXiv:1705.05085 (2017)
arXiv 2017
-
[8]
Akshay L Chandra, Sai Vikas Desai, Chaitanya Devaguptapu, and Vineeth N Balasubramanian. 2021. On initial pools for deep active learning. In NeurIPS 2020 Workshop on Pre-registration in Machine Learning . PMLR, 14–32
work page 2021
Show all 54 references
-
[9]
Mingshu Cong, Han Yu, Xi Weng, Jiabao Qu, Yang Liu, and Siu Ming Yiu. 2020. A VCG-based Fair Incentive Mechanism for Federated Learning. (2020)
2020
-
[10]
Pranav Dandekar, Nadia Fawaz, and Stratis Ioannidis. 2012. Privacy auctions for recommender systems. In Proceedings of the 8th international conference on Internet and Network Economics . Springer-Verlag, 309–322
2012
-
[11]
Amirata Ghorbani and James Zou. 2019. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning. PMLR, 2242–2251
2019
-
[12]
Arpita Ghosh and Aaron Roth. 2011. Selling privacy at auction. In Proceedings of the 12th ACM conference on Electronic commerce . 199–208
2011
-
[13]
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)
2017
-
[14]
Judd Randolph Heckman, Erin Laurel Boehmer, Elizabeth Hope Peters, Milad Davaloo, and Nikhil Gopinath Kurup. 2015. A pricing model for data markets. IConference 2015 Proceedings (2015)
2015
-
[15]
Rui Hu and Yanmin Gong. 2020. Trading data for learning: Incentive mecha- nism for on-device federated learning. In GLOBECOM 2020-2020 IEEE Global Communications Conference. IEEE, 1–6
2020
-
[16]
Jeevan Jaisingh, Jack Barron, Shailendra Mehta, and Alok Chaturvedi. 2008. Privacy and pricing personal information. European Journal of Operational Research 187, 3 (2008), 857–870
2008
-
[17]
Spanos, and Dawn Song
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J. Spanos, and Dawn Song. 2019. Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms. Proceedings of the VLDB Endowment (2019)
2019
-
[18]
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
2016 arXiv
-
[19]
Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016)
2016 arXiv
-
[20]
Avanish Kushal, Sharmadha Moorthy, and Vikash Kumar. 2012. Pricing for data markets. online] https://courses. cs. washington. edu/courses/cse544/11wi/projects/kumar_kushal_moorthy. pdf (2012)
2012
-
[21]
Vito Latora, Vincenzo Nicosia, and Giovanni Russo. 2017. Complex networks: principles, methods and applications . Cambridge University Press
2017
-
[22]
Angsheng Li and Yicheng Pan. 2016. Structural information and dynamical complexity of networks. IEEE Transactions on Information Theory 62, 6 (2016), 3290–3339
2016
-
[23]
Katrina Ligett and Aaron Roth. 2012. Take it or leave it: Running a survey when privacy comes at a cost. In International Workshop on Internet and Network Economics. Springer, 378–391
2012
-
[24]
Jinfei Liu. 2020. Dealer: end-to-end data marketplace with model-based pricing. arXiv preprint arXiv:2003.13103 (2020)
2020 arXiv
-
[25]
Yiwei Liu, Jiamou Liu, Zijian Zhang, Liehuang Zhu, and Angsheng Li. 2019. REM: From structural entropy to community structure deception. Advances in Neural Information Processing Systems 32 (2019)
2019
-
[26]
Nan Ma, Jiancheng Guan, and Yi Zhao. 2008. Bringing PageRank to the citation analysis. Information Processing & Management 44, 2 (2008), 800–810
2008
-
[27]
Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology 27, 1 (2001), 415–444
2001
-
[28]
Olga Ohrimenko, Shruti Tople, and Sebastian Tschiatschek. 2019. Collaborative machine learning markets with data-replication-robust payments. arXiv preprint arXiv:1911.09052 (2019)
2019 arXiv
-
[29]
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. 2018. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748 (2018)
2018 arXiv
-
[30]
Javier Parra-Arnau. 2018. Optimized, direct sale of privacy in personal data marketplaces. Information Sciences 424 (2018), 354–384
2018
-
[31]
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. 2021. A survey of deep active learning. ACM computing surveys (CSUR) 54, 9 (2021), 1–40
2021
-
[32]
Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. 2022. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. In Learning on Graphs Conference . PMLR, 11–1
2022
-
[33]
Aaron Roth and Grant Schoenebeck. 2012. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference on Electronic Commerce . 826–843
2012
-
[34]
Lloyd S Shapley. 1951. Notes on the n-person game—ii: The value of an n-person game. (1951)
1951
-
[35]
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018)
2018 arXiv
-
[36]
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. 2020. Collaborative machine learning with incentive-aware model rewards. In International conference on machine learning . PMLR, 8927– 8936
2020
-
[37]
Yaron Singer. 2010. Budget feasible mechanisms. In 2010 IEEE 51st Annual Sym- posium on foundations of computer science . IEEE, 765–774
2010
-
[38]
Indro Spinelli, Simone Scardapane, and Aurelio Uncini. 2020. Missing data imputation with adversarially-trained graph convolutional networks. Neural Networks 129 (2020), 249–260
2020
-
[39]
Peng Sun, Xu Chen, Guocheng Liao, and Jianwei Huang. 2022. A profit- maximizing model marketplace with differentially private federated learning. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications . IEEE, 1439–1448
2022
-
[40]
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. 2021. Graph convolutional net- works for graphs containing missing features. Future Generation Computer Systems 117 (2021), 155–168
2021
-
[41]
Bisheng Tang, Xiaojun Chen, Shaopu Wang, Yuexin Xuan, and Zhendong Zhao
-
[42]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017)
2017 arXiv
-
[43]
Yifei Wang, Yupan Wang, Zeyu Zhang, Song Yang, Kaiqi Zhao, and Jiamou Liu
-
[44]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)
2018 arXiv
-
[45]
Lei Xu, Chunxiao Jiang, Yan Chen, Yong Ren, and K. J. Ray Liu. 2015. Privacy or Utility in Data Collection? A Contract Theoretic Approach. IEEE Journal of Selected Topics in Signal Processing 9, 7 (2015), 1256–1269
2015
-
[46]
arXiv preprint arXiv:2302.05889 (2023)
User: Unsupervised structural entropy-based robust graph neural network. arXiv preprint arXiv:2302.05889 (2023)
2023 arXiv
-
[47]
Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. 2021. A survey on federated learning. Knowledge-Based Systems 216 (2021), 106775
2021
-
[48]
Jingwen Zhang, Yuezhou Wu, and Rong Pan. 2021. Incentive mechanism for hori- zontal federated learning based on reputation and reverse auction. In Proceedings of the Web Conference 2021. 947–956
2021
-
[49]
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. 2021. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems 34 (2021), 16104–16117
2021
-
[50]
Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. 2021. Alg: Fast and accurate active learning framework for graph convolutional networks. In Proceedings of the 2021 International Conference on Management of Data . 2366– 2374. Table 4: The impact of different st...
2021
-
[52]
Mengxiao Zhang, Fernando Beltran, and Jiamou Liu. 2020. Selling Data at an Auction under Privacy Constraints. In Conference on Uncertainty in Artificial Intelligence. PMLR, 669–678
2020
-
[54]
The configuration of these architectures are the same as that of GCN as shown in GNN models part in Sec
and have gained widespread acceptance within the GNN com- munity. The configuration of these architectures are the same as that of GCN as shown in GNN models part in Sec. 5.1. To eliminate the randomness induced by subgraphs, we conduct experiments on the case where all data o...
-
[2022]
International Journal of Production Research 60, 14 (2022), 4397–4417
Data-driven secure, resilient and sustainable supply chains: gaps, oppor- tunities, and a new generalised data sharing and data monetisation framework. International Journal of Production Research 60, 14 (2022), 4397–4417
2022
-
[2023]
Neural Networks (2023)
Generalized heterophily graph data augmentation for node classification. Neural Networks (2023). https://doi.org/10.1016/j.neunet.2023.09.021
2023 doi
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.