Pith. sign in

REVIEW 3 major objections 6 minor 44 references

Differentially Private Multi-objective Selection: Pareto and Aggregation Approaches

T0 review · 3 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper introduces two differentially private mechanisms, PrivPareto and PrivAgg, that select near-Pareto-optimal candidates under multiple competing objectives, with local-sensitivity versions that stay accurate at privacy budgets as…

desk verdict Useful mechanism-level ideas for DP multi-objective selection, but the experimental privacy accounting and a key proof step are not sound as written. read the letter →

arxiv 2412.14380 v2 pith:QK4FP7DK submitted 2024-12-18 cs.CR

Victor A. E. Farias , Felipe T. Brito , Cheryl Flynn , Javam C. Machado , Divesh Srivastava This is my paper · ORCID
classification cs.CR
keywords differentialprivacymulti-objectiveselectionParetooptimalitylocalsensitivityglobalexponentialmechanismdecisiontreesinfluentialnode
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Existing differentially private selection mechanisms handle a single objective, but many real problems—medical diagnosis, network influence, decision-tree construction—require balancing several competing objectives at once. The paper closes that gap with two mechanisms: PrivPareto, which scores each candidate by how many other candidates dominate it and privately selects a point near the Pareto frontier, and PrivAgg, which privately selects by a weighted sum of the objectives. The core technical contribution is a way to compute the sensitivity of these composite scores from the sensitivities of the individual utility functions, supporting both global and local sensitivity. Experiments on cost-sensitive decision trees and top-k influential node selection show that the local-sensitivity versions achieve utility close to non-private baselines at epsilon in [0.01, 1], where global-sensitivity versions need far larger budgets.

What carries the argument

The load-bearing object is the admissible sensitivity function, a computationally efficient upper bound $\delta_u(x,t,r)$ on element local sensitivity that satisfies two conditions: it dominates the actual sensitivity at $t=0$, and it does not increase too fast as the database moves to a neighbor at distance $t$. The paper proves that this property is preserved under the two composite scores: for the Pareto score, $\delta_{PS}(x,t,r) = |dom^-_{x,t,r}| + |ndom^+_{x,t,r}|$ counts how many candidates could change domination status within distance $t$; for the weighted sum, the weighted combination of admissible per-objective functions is again admissible. This lets a data analyst provide only per-objective sensitivities, and the machinery composes them automatically for use in a single-objective DP selector.

What would settle it

Run DP-MOET with s=3, k=3, and output size 3 and count the calls to DP_MOSelection: three selections per generation for three generations plus one final selection, so ten calls. Feed that count into the sequential composition theorem to compute the total budget as 10 x epsilon; then compare output utilities at epsilon=0.01 and 0.1 under this accounting and audit privacy loss empirically on a neighboring dataset to determine whether the reported epsilon is the per-call or total budget.

Watch

Extended reading notes

Core claim

The central claim is that multi-objective private selection can be reduced to single-objective private selection by defining a composite score whose sensitivity is algorithmically derivable from user-supplied sensitivities. For PrivPareto, the Pareto score $PS(x,r) = -|\{r' \in R : r' \succeq_x r\}|$ counts how many candidates dominate $r$; the paper proves that $\delta_{PS}(x,t,r) = |dom^-_{x,t,r}| + |ndom^+_{x,t,r}|$ is an admissible sensitivity function, making the local-sensitivity version differentially private. For PrivAgg, the weighted sum $u_{agg} = \sum_i w_i u_i(x,r)$ has global sensitivity bounded by $\sum_i |w_i| \Delta_{u_i}$ and an admissible local-sensitivity function $\delta_{u_{agg}}(x,t,r) = \sum_i |w_i| \delta_{u_i}(x,t,r)$. With these compositions, any single-objective selection mechanism—exponential, report-noisy-max, permute-and-flip, or local dampening—can be dropped into the selection step. The paper also derives admissible sensitivity functions for true positive rate, true negative rate, degree centrality, and egocentric density, and embeds the mechanisms in evolutionary algorithms for decision trees and top-k node selection.

Load-bearing premise

The experiments report epsilon as if it were the total privacy budget for the whole evolutionary algorithm, although the algorithm calls the private selection step many times, so the true total budget is larger than the reported value.

Editorial extensions

If this is right

  • Data analysts can apply differentially private multi-objective selection to a new problem by supplying only the utility functions and their per-objective sensitivities; the composite sensitivity is computed automatically.
  • Local-sensitivity versions achieve substantially better utility than global-sensitivity versions in both applications, and in most experiments match non-private baselines at epsilon in [0.01, 1].
  • The mechanisms are composable building blocks: DP-MOET for cost-sensitive decision trees and DP-MOTkIN for top-k influential node selection are built from the same selection step, so the same machinery can be embedded in larger private algorithms.
  • The sensitivity framework covers both node-based utilities (true positive rate, true negative rate) and edge-based utilities (degree centrality, egocentric density), spanning at least two common privacy models.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because admissibility is preserved when per-objective sensitivity functions are composed, the same construction extends beyond the paper's two examples: any composite score built from monotone operations on admissible sensitivity functions could be plugged into PrivPareto or PrivAgg.
  • The paper's per-run privacy accounting is ambiguous: DP-MOET invokes the private selector $s$ times per generation for $k$ generations plus one final call, so under sequential composition the total budget is a multiple of the reported epsilon; a clean end-to-end guarantee would require either splitting epsilon across calls or reporting the total.
  • The Pareto-score mechanism requires no weights, so it may be the better fit when objectives are incommensurate or when the analyst cannot justify a weighting; PrivAgg remains the tool when weights are known.
  • A natural stress test is to compare the two mechanisms' regret against the true Pareto set on synthetic fronts where the optimum is known, isolating score quality from sensitivity estimation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes two mechanisms for differentially private multi-objective selection: PrivPareto, which scores candidates by how dominated they are in a Pareto sense, and PrivAgg, which selects according to a weighted sum of utility functions. For each mechanism the paper develops global- and local-sensitivity versions, with theorems showing how to compose sensitivities of the individual utility functions. The mechanisms are instantiated in two end-to-end frameworks, DP-MOET for cost-sensitive decision trees and DP-MOTkIN for influential node selection, and evaluated on several datasets. The paper claims that the local-sensitivity variants have strong utility for privacy budgets epsilon in [0.01, 1].

Significance. If the local-sensitivity theory were fully correct, this would fill a genuine gap: a general primitive for multi-objective selection under differential privacy with composable sensitivity bounds, plus two concrete application families and a public artifact link. The aggregation sensitivity theorems are simple and essentially correct in substance, and the experimental study is extensive. However, the local-sensitivity admissibility proofs and the end-to-end privacy accounting currently do not support the headline claims, so the contribution is conditional on substantial repairs.

major comments (3)
  1. [§6.2.1, §7.2; Theorem 2.2; Tables 1–2 and Figures 2–3] The value called epsilon in the experimental sections is not the total privacy budget of the end-to-end algorithms. In Algorithm 1, line 4 passes the same epsilon to DP_MOSelection, and Section 6.2.1 states that DP_MOSelection invokes the underlying PrivPareto/PrivAgg mechanism s times; line 15 adds a further selection of o items. For the Section 6.3 parameters (s=3, k=3, o=3) this is at least 12 calls, and for the Section 6.4 parameters (s=20, k=2, o=1) it is 41 calls. The DP-MOTkIN family (Section 7.2) similarly calls the private selection mechanism k times. By Theorem 2.2, the total privacy loss is the sum of the per-call budgets, yet the paper does not split epsilon across calls nor report the total. Therefore the claim that local-sensitivity mechanisms achieve strong utility at epsilon in [0.01, 1] is unsupported, and the comparisons with single-call baselines such as LocalDiffPID3 are not made at equal privacy. The authors should divide the budget across calls and report the total, or clearly report both per-call and total budgets and re-evaluate utility at fixed total epsilon.
  2. [Appendix A.1, proof of Theorem 4.7] The proof that delta_PS is admissible contains an incorrect inequality. In the analysis of the first term of Eq. (11), the proof states that for neighboring x and y, u_i(x,r) >= u_i(y,r) + delta_{u_i}(y,0,r). Admissibility and the definition of local sensitivity give |u_i(x,r) - u_i(y,r)| <= LS_{u_i}(y,0,r) <= delta_{u_i}(y,0,r), so the correct lower bound is u_i(x,r) >= u_i(y,r) - delta_{u_i}(y,0,r), not with a plus sign. The set-containment argument in that step uses the incorrect direction. Since admissibility of delta_PS is exactly what licenses the local PrivPareto mechanism's epsilon-DP guarantee, this is a load-bearing gap. A corrected proof is needed.
  3. [Section 6.2.3 and Appendix A.2, Lemma 6.1] The function delta_TPR is not admissible as defined. The proof correctly derives LS_TPR(x,0,tau) = max( (P-TP)/(P(P-1)), TP/(P(P-1)) ). However, for t=0 the branch condition "t <= P-TP" is always true because P-TP >= 0, so the definition yields delta_TPR(x,0,tau) = (P-TP)/(P(P-1)) only. When TP > P/2 this is strictly smaller than LS_TPR; for example, P=10, TP=9 gives LS_TPR = 0.1 but delta_TPR = 1/90. Thus condition 1 of Definition 2.7 fails. Because delta_TPR and delta_TNR are the admissible sensitivity functions used as inputs to delta_PS and delta_uagg in the local versions of DP-MOET, the privacy guarantees of those instantiations are not established. The definition should be changed to the maximum of the two branches, or to a true upper bound, and the admissibility proof reworked.
minor comments (6)
  1. [Definition 4.3 and Example 4.4] Definition 4.3 defines the Pareto score as -|{r' in R : r' >=_x r}|, which includes r itself since u_i(x,r) >= u_i(x,r). This makes every Pareto score at most -1, contradicting Example 4.4, where Pareto-optimal candidates receive score 0, and the subsequent discussion of global sensitivity in Section 4.2. The definition should exclude the candidate itself, i.e., use r' in R \ {r}.
  2. [Theorem 5.4 proof] The proof of Theorem 5.4 contains a false equality: after applying the triangle inequality, the text writes "= LS_{u_agg}(x,0,r)" for an expression involving |w_i|. The correct step is sum_i |w_i| LS_{u_i}(x,0,r) >= max_{y: d(x,y)<=1} |sum_i w_i (u_i(x,r)-u_i(y,r))| = LS_{u_agg}(x,0,r). This is a fixable presentation error, but the current chain is mathematically incorrect.
  3. [Definition 4.5] The shorthand u^{+t}_i(x,r) is defined as u_i(x,r) + sum_{i=0}^t delta_{u_i}(x,i,r), reusing the index i for both the utility-function index and the summation index. This should be written with a separate summation index, e.g., sum_{j=0}^t.
  4. [Appendix A.1] In the decomposition of Line 11, the text writes "ndom_{y,r} = (ndom_{x,r} ∩ dom_{y,r}) ∪ (ndom_{x,r} ∩ dom_{y,r})"; the second term should be (ndom_{x,r} ∩ ndom_{y,r}).
  5. [Section 7.3] The proposed delta_egodensity(G,t,v) can exceed the global sensitivity: for |N_G(v)| = 3 and t = 0, the formula gives 2/(3-0-2) = 2, while the egodensity is in [0,1] and Delta_egodensity is 1. If the paper's stated goal of staying below Delta_u is intended, the function should be capped.
  6. [Table 2 caption] The caption says epsilon = {10^{-1}, 10^0, 10^1, 10^2, 10^3}, but the table rows include 0.1, 0.5, 1.0, 2.0, 5.0, 10.0, 20.0, 50.0. The caption and table should be aligned.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Pareto-score and weighted-sum sensitivity functions are derived from the underlying utility sensitivities, not assumed as predictions.

full rationale

The paper's central derivation chain is the construction of admissible sensitivity functions for the new multi-objective mechanisms: Definition 4.5 and Theorem 4.7 for the Pareto score, Theorems 5.3 and 5.4 for the weighted aggregate, Lemma 6.1 for TPR/TNR, and Lemma 7.2 for egocentric density. In each case the sensitivity function is defined from the user-supplied admissible sensitivity functions of the underlying utility functions, and the admissibility proofs in the appendix reduce explicitly to properties (1) and (2) of Definition 2.7; the target privacy guarantee is not an input to the definition. The weights used in the aggregation experiments (w_tpr=3, w_tnr=2; w_degree=1, w_egodensity=100) are stated user choices, not parameters fitted to force the reported utility, and the utility comparisons are measured against non-private baselines such as NODP-MOET-Pareto and NODP-MOET-Agg. The only notable self-citation is the local dampening mechanism [5,12], which is used as a single-objective building block; its differential-privacy guarantee is a published theorem with stated assumptions that do not include the multi-objective results of this paper, so the self-citation is not load-bearing circularity. The skeptic's concern that DP-MOET and DP-MOTkIN reuse the same epsilon per call without explicit sequential-composition accounting is a privacy-accounting or correctness issue, not a case where a reported result reduces by construction to its inputs, so it does not raise the circularity score. I found no passage in which a prediction is equivalent to a fitted parameter, a definition is circular, or an omitted proof conceals an assumption of the target result.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The mechanisms rest on standard DP definitions (Section 2), the admissibility framework of the authors' prior Local Dampening work, and the choice of utility functions for the two applications. The only free parameters are the user-assigned weights in the aggregation experiments. No new entities are introduced.

free parameters (2)
  • w_tpr, w_tnr (aggregation weights for decision trees) = 3, 2
    User-assigned weights in the PrivAgg experiments (Section 6.4). They encode the relative importance of TPR over TNR and directly determine the aggregate utility; results in Figure 2 depend on this choice.
  • w_degree, w_egodensity (aggregation weights for graph) = 1, 100
    User-assigned weights in the DP-MOTkIN-Agg experiments (Section 7.5). w_egodensity=100 dominates degree centrality, so the 'multi-objective' selection is effectively driven by egodensity; results in Figure 3 are sensitive to this.
assumptions (3)
  • standard math Differential privacy definition and sequential composition theorem (Theorem 2.2) hold as stated.
    Invoked throughout, e.g., in Section 2.1 and used implicitly in the privacy accounting of the applications.
  • domain assumption The admissibility definition (Definition 2.7) is a valid sufficient condition for epsilon-DP of the local dampening mechanism.
    Taken from the authors' prior work [5,12] (Local Dampening); the paper relies on it to claim that admissible delta functions make PrivPareto/PrivAgg local private.
  • domain assumption TPR, TNR, degree centrality, and egocentric density are the appropriate utility functions for the two applications.
    Assumed in Sections 6.1 and 7.1; the sensitivity analyses and experiments are built on these choices, but other objectives could be used.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Differentially Private Multi-objective Selection: Pareto and Aggregation Approaches." pith.science (2026). https://pith.science/paper/QK4FP7DK

@misc{pith2026241214380,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Multi-objective Selection: Pareto and Aggregation Approaches},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QK4FP7DK}},
  note         = {Machine review of arXiv:2412.14380}
}
abstract

Differentially private selection mechanisms are fundamental building blocks for privacy-preserving data analysis. While numerous mechanisms exist for single-objective selection, many real-world applications require optimizing multiple competing objectives simultaneously. We present two novel mechanisms for differentially private multi-objective selection: PrivPareto and PrivAgg. PrivPareto uses a novel Pareto score to identify solutions near the Pareto frontier, while PrivAgg enables privacy-preserving weighted aggregation of multiple objectives. Both mechanisms support global and local sensitivity approaches, with comprehensive theoretical analysis showing how to compose sensitivities of multiple utility functions. We demonstrate the practical applicability through two real-world applications: cost-sensitive decision tree construction and multi-objective influential node selection in social networks. The experimental results showed that our local sensitivity-based approaches achieve significantly better utility compared to global sensitivity approaches across both applications and both Pareto and Aggregation approaches. Moreover, the local sensitivity-based approaches are able to perform well with typical privacy budget values $\epsilon \in [0.01, 1]$ in most experiments.

Figures

Figures reproduced from arXiv: 2412.14380 by the authors.

Figure 1
Figure 1. Example Pareto scores for 5 elements and 2 utility [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Mean fitness/utility score 𝑢𝑎𝑔𝑔 = 𝑤𝑡𝑝𝑟 · 𝑇 𝑃𝑅 + 𝑤𝑡𝑛𝑟 · 𝑇 𝑁 𝑅 for 𝑤𝑡𝑝𝑟 = 3, 𝑤𝑡𝑛𝑟 = 2 and 𝜖 ∈ {0.01, 0.05, 0.1, 0.5, 1.0, 2.0}. 7.2 Private Mechanism We provide two main strategies to solve this problem: a Pareto based approach and a aggregation based approach. We first provide a base private algorithm that computes a set of 𝑘 nodes of 𝑉 that maximizes the two utility functions. Then our proposed algorithms are based … view at source ↗
Figure 3
Figure 3. Mean recall for DP-MOTkIN-Agg methods where [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 32 canonical work pages

  1. [1]

    Catherine L Blake and Christopher J Merz. 1998. UCI repository of machine learning databases

    work page 1998

  2. [2]

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2013. Differentially private data analysis of social networks via restricted sensitivity. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science. ACM, 87–96

    work page 2013

  3. [3]

    Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. 1984. Classification and regression trees . CRC press

    work page 1984

  4. [4]

    Felipe T Brito, André LC Mendonça, and Javam C Machado. 2024. A Differentially Private Guide for Graph Analytics.. In EDBT. 850–853

    work page 2024

  5. [5]

    Victor A. E. de Farias, Felipe T. Brito, Cheryl Flynn, Javam C. Machado, Sub- habrata Majumdar, and Divesh Srivastava. 2020. Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity. Proc. VLDB Endow. 14, 4 (2020), 521–533. https://doi.org/10.14778/3436905.3436912

    arXiv 2020

  6. [6]

    Saghaian N

    Zeyu Ding, Daniel Kifer, Sayed M. Saghaian N. E., Thomas Steinke, Yuxin Wang, Yingtai Xiao, and Danfeng Zhang. 2021. The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise. CoRR abs/2105.07260 (2021). arXiv:2105.07260 https://arxiv.org/abs/2105.07260

    arXiv 2021

  7. [7]

    David Durfee and Ryan M. Rogers. 2019. Practical Differentially Private Top-k Se- lection with Pay-what-you-get Composition. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Sys- tems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada , Hanna M. Wallach, Hugo Larochelle, Alina Beygelzi...

    work page 2019

  8. [8]

    Cynthia Dwork. 2011. Differential privacy. Encyclopedia of Cryptography and Security (2011), 338–340

    work page 2011

Show all 44 references
  1. [9]

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 486–503

    2006

  2. [10]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Cali- brating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265–284

    2006

  3. [11]

    Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differen- tial privacy. Foundations and Trends in Theoretical Computer Science 9, 3-4 (2014), 211–407

    2014

  4. [12]

    Victor AE Farias, Felipe T Brito, Cheryl Flynn, Javam C Machado, Subhabrata Majumdar, and Divesh Srivastava. 2023. Local dampening: Differential privacy for non-numeric queries via local sensitivity. the VLDB Journal 32, 6 (2023), 1191–1214

    2023

  5. [13]

    Sam Fletcher and Md Zahidul Islam. 2019. Decision tree classification with differential privacy: A survey. ACM Computing Surveys (CSUR) 52, 4 (2019), 1–33

    2019

  6. [14]

    Nermin Hamza, Hesham A Hefny, et al. 2013. Attacks on anonymization-based privacy-preserving: a survey for data mining and data publishing. (2013)

    2013

  7. [15]

    Jane Henriksen-Bulmer and Sheridan Jeary. 2016. Re-identification attacks—A systematic literature review. International Journal of Information Management 36, 6 (2016), 1184–1192

    2016

  8. [16]

    Zhanglong Ji, Zachary C Lipton, and Charles Elkan. 2014. Differential privacy and machine learning: a survey and review.arXiv preprint arXiv:1412.7584 (2014)

    2014 arXiv

  9. [17]

    Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, and Xiuzhen Cheng

  10. [18]

    Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev

  11. [19]

    Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2013. Analyzing graphs with node differential privacy. In Theory of Cryptography Conference. Springer, 457–476

    2013

  12. [20]

    Sotiris B Kotsiantis, I Zaharakis, and P Pintelas. 2007. Supervised machine learning: A review of classification techniques. Emerging artificial intelligence applications in computer engineering 160 (2007), 3–24

    2007

  13. [21]

    Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data

    2014

  14. [22]

    Bo Liu, Ming Ding, Sina Shaham, Wenny Rahayu, Farhad Farokhi, and Zihuai Lin. 2021. When machine learning meets privacy: A survey and outlook. ACM Computing Surveys (CSUR) 54, 2 (2021), 1–36

    2021

  15. [23]

    Wentian Lu and Gerome Miklau. 2014. Exponential random graph estimation under differential privacy. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . ACM, 921–930

    2014

  16. [24]

    Kenneth G Manton. 2010. National Long-Term Care Survey: 1982, 1984, 1989, 1994, 1999, and 2004. Inter-university Consortium for Political and Social Research (2010)

    2010

  17. [25]

    Peter V Marsden. 1993. The reliability of network density and composition measures. Social Networks 15, 4 (1993), 399–421

    1993

  18. [26]

    Ryan McKenna and Daniel R Sheldon. 2020. Permute-and-Flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems 33 (2020)

    2020

  19. [27]

    Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). 94–103. https://doi.org/10.1109/FOCS.2007.66

    2007 doi

  20. [28]

    Arvind Narayanan and Vitaly Shmatikov. 2016. How to break anonymity of the netflix prize dataset (2006). arXiv preprint cs/0610105 (2016)

    2006 arXiv

  21. [29]

    Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing . ACM, 75–84

    2007

  22. [30]

    Sancheng Peng, Yongmei Zhou, Lihong Cao, Shui Yu, Jianwei Niu, and Weijia Jia. 2018. Influence analysis in social networks: A survey. Journal of Network and Computer Applications 106 (2018), 17–32

    2018

  23. [31]

    Ross Quinlan

    J. Ross Quinlan. 1986. Induction of decision trees. Machine learning 1, 1 (1986), 81–106

    1986

  24. [32]

    J Ross Quinlan. 2014. C4. 5: programs for machine learning . Elsevier

    2014

  25. [33]

    Integrated Public Use Microdata Series. 2015. Version 6.0.Minneapolis: University of (2015)

    2015

  26. [34]

    Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. 2017. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP) . IEEE, 3–18

    2017

  27. [35]

    Christine Task and Chris Clifton. 2012. A guide to differential privacy theory in social network analysis. In 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining . IEEE, 411–417

    2012

  28. [36]

    Jun Zhang, Graham Cormode, Cecilia M Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2015. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD international conference on management of data. ACM, 731–745

    2015

  29. [37]

    Jun Zhang, Xiaokui Xiao, Yin Yang, Zhenjie Zhang, and Marianne Winslett

  30. [38]

    Huimin Zhao. 2007. A multi-objective genetic programming approach to de- veloping Pareto optimal decision trees. Decision Support Systems 43, 3 (2007), 809–826

    2007

  31. [39]

    Tianqing Zhu, Gang Li, Wanlei Zhou, and S Yu Philip. 2017. Differentially private data publishing and analysis: A survey. IEEE Transactions on Knowledge and Data Engineering 29, 8 (2017), 1619–1638

    2017

  32. [40]

    Eckart Zitzler, Kalyanmoy Deb, and Lothar Thiele. 2000. Comparison of multiob- jective evolutionary algorithms: Empirical results. Evolutionary computation 8, 2 (2000), 173–195. A PROOFS A.1 Proof of Theorem 4.7 Theorem 4.7. Given utility functions𝑢1,··· ,𝑢𝑚, admissible sen- s...

    2000

  33. [44]

    Therefore, in general, we have that𝐴(𝐺,𝑣)≤ 𝐴(𝐺′,𝑣)≤ 𝐴(𝐺,𝑣)+| 𝑁𝐺(𝑣)| and|𝑁𝐺(𝑣)|≤| 𝑁𝐺′ (𝑣)|≤ |𝑁𝐺(𝑣)|+ 1

    The case where 𝑢 ≠ 𝑣 and𝑤 = 𝑣 is symmetric to the previous one. Therefore, in general, we have that𝐴(𝐺,𝑣)≤ 𝐴(𝐺′,𝑣)≤ 𝐴(𝐺,𝑣)+| 𝑁𝐺(𝑣)| and|𝑁𝐺(𝑣)|≤| 𝑁𝐺′ (𝑣)|≤ |𝑁𝐺(𝑣)|+ 1. Therefore, we calculate and upper bound for both inner maximum functions: 2.𝐴(𝐺,𝑣) |𝑁𝐺(𝑣)|.(|𝑁𝐺(𝑣)|− 1)− 2.𝐴(𝐺...

  34. [2011]

    PVLDB 4, 11 (2011), 1146–1157

    Private analysis of graph structure. PVLDB 4, 11 (2011), 1146–1157

    2011

  35. [2013]

    In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

    Privgene: differentially private model fitting using genetic algorithms. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 665–676

    2013

  36. [2021]

    IEEE transactions on knowledge and data engineering 35, 1 (2021), 108–127

    Applications of differential privacy in social network analysis: A survey. IEEE transactions on knowledge and data engineering 35, 1 (2021), 108–127

    2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.