Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

On the $(k,\ell)$-multiset anonymity measure for social graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper argues that an active attacker's knowledge of a victim should be modeled as the unordered multiset of distances to the attacker nodes, and develops the resulting (k,ℓ)-multiset anonymity measure with exact values for several…

desk verdict The multiset-anonymity idea is new and worth a look, but the ILP does not actually compute the stated measure, so the computational claims only hold for a relaxation. read the letter →

arxiv 2507.08433 v1 pith:Y5EOG7MK submitted 2025-07-11 math.CO cs.ITmath.IT

Alejandro Estrada-Moreno , Elena Fernández , Dorota Kuziak , Manuel Muñoz-Márquez , Rolando Trujillo-Rasua , Ismael G. Yero This is my paper · ORCID
classification math.COcs.ITmath.IT MSC 05C1205C7668R1068P2768M25
keywords k-multisetantidimensionantiresolvingsets(kℓ)-multisetanonymityactiveattackssocialgraphsmetricdimensionintegerlinearprogrammingk-metric
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

Active attacks re-identify users in published social graphs by planting attacker nodes and later matching victims' connection patterns to those nodes. This paper argues that the standard model, which gives the attacker an ordered vector of distances, is unrealistically strong after anonymization by perturbation; instead the attacker should know only the multiset of those distances. On that basis the paper defines $(k,\ell)$-multiset anonymity via $k$-multiset antiresolving sets, computes the minimum number of attacker nodes needed to break a given privacy level $k$ for trees, complete bipartite graphs, wheels, and binary trees, and provides an integer linear program that computes this $k$-multiset antidimension exactly. If the multiset adversary model is accepted, the paper gives privacy analysts the tools to compute the true resistance of a small social graph to active attacks.

What carries the argument

The load-bearing object is the multiset representation $m(v|S) = \{\{ d_G(v,s) : s \in S \}\}$ and the equivalence relation $R_S$ that identifies two vertices when these multisets coincide; the anonymity set of $v$ is its class under $R_S$, and $S$ is a $k$-MARS exactly when every such class has size at least $k$. The parameter $\kappa(G)$, the largest $k$ for which some $k$-MARS exists, sets the ceiling on achievable anonymity, and the companion ILP in Section 4 searches for a smallest $k$-MARS using binary variables for membership in $S$, binary variables for class membership, integer variables $t_{ur}$ counting how many vertices of $S$ lie at each distance $r$ from $u$, and $\delta$-variables that force distinct classes to have different distance-count profiles.

What would settle it

Run the active-attack retrieval from the paper's motivating scenario on a perturbed graph where the vector and multiset anonymity sets differ, and record how often the attacker recovers the attacker nodes in their true order; if the correct order is recovered with probability close to 1, the multiset model's central premise fails, while near-random ordering supports it.

Watch

Extended reading notes

Core claim

The paper's central discovery is that replacing the ordered distance vector with the unordered multiset of distances qualitatively changes the privacy measure: a vertex set $S$ is a $k$-multiset antiresolving set ($k$-MARS) when $k$ is the largest integer such that every vertex outside $S$ shares its multiset-of-distances fingerprint with at least $k-1$ other vertices. Every vector-based $k$-antiresolving set is also a $k'$-MARS for some $k' \geq k$, so the multiset measure never reports worse anonymity than the vector measure, and there are graphs, such as the one in Figure 2, where the multiset measure doubles the maximum anonymity level from $\Delta$ to $2\Delta$. The paper determines $\kappa(G)$ and the $k$-multiset antidimension $\mathrm{msad}_k(G)$ exactly for complete bipartite graphs, wheel graphs, paths and trees (with complete binary trees partially), showing for example that every tree has $\kappa(T) \geq 2$ while complete bipartite graphs can have no $k$-MARS at all for certain parity mismatches. Finally, it formulates the search for a smallest $k$-MARS as an integer linear program and solves it exactly on benchmark graphs with up to 100 vertices, finding that most such random graphs satisfy only $(2,2)$-multiset anonymity.

Load-bearing premise

The measure's correctness rests on the assumption that after anonymization an active attacker can retrieve the set of attacker nodes but cannot order them; if a real attacker retains the ordering, the multiset measure overstates the anonymity.

Editorial extensions

If this is right

  • Under the multiset model, every tree with at least three vertices has $\kappa(T) \geq 2$, so no tree exhibits the vector model's worst-case 1-privacy.
  • For complete bipartite graphs $K_{r,t}$, values of $k$ exist where no $k$-MARS exists, meaning $\mathrm{msad}_k(K_{r,t}) = \infty$ and the graph cannot offer that anonymity level at any attack size.
  • Because every $k$-antiresolving set is a $k'$-MARS with $k' \geq k$, the multiset measure always reports anonymity at least as high as the vector measure for the same set of attacker nodes.
  • Wheel graphs $W_{1,n-1}$ attain $\kappa = n-1$, and their exact $k$-multiset antidimension is given by the parity-split formulas of Theorem 17.
  • The ILP solves all tested 50-vertex instances and several 100-vertex instances to proven optimality, with instances whose optimum is 1 being easy and others often hitting the time limit.

Reading between the lines

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

  • If the open conjecture $\kappa(G) \geq 2$ for all connected graphs holds, then under the multiset model every connected social graph guarantees at least pairwise indistinguishability against a single attacker, and the vector model's '1-metric antidimensional' graphs would no longer be the worst case.
  • The paper's motivation suggests a direct empirical check: measure both vector and multiset anonymity on graphs after a perturbation-based anonymization and compare them with actual sybil-retrieval success rates; the multiset measure should match real attack success if its modeling premise is right.
  • The ILP's difficulty on dense 100-vertex graphs indicates that scaling this exact measure to realistic networks will require either a proof of NP-hardness for $k$-MARS with dedicated heuristics, or a relaxation of optimality; the vector counterpart is already NP-hard, so the multiset version plausibly inherits intractability.
  • The multiset model makes unique re-identification harder, since a victim is unique only when its distance multiset is unique, so practitioners re-running k-anonymity audits under this model will tend to see larger anonymity sets and may need to re-evaluate graphs previously deemed unsafe.
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 / 4 minor

Summary. The paper introduces the (k,ℓ)-multiset anonymity measure for social graphs, in which an active adversary's knowledge of a victim is modeled as the multiset of distances to the attacker set rather than the ordered vector used in the original (k,ℓ)-anonymity. The central objects are k-multiset antiresolving sets (k-MARS) and the k-multiset antidimension msad_k(G). The authors prove structural results for complete bipartite graphs, paths, trees, complete binary trees, and wheel graphs, bounded by the parameter κ(G), and they propose an integer linear programming formulation F intended to compute msad_k exactly. The formulation is implemented and tested on sparse, dense, and cycle benchmark graphs.

Significance. If correct, the paper would contribute a natural relaxation of the standard active-attack privacy model and provide both theoretical and computational tools for assessing k-multiset anonymity. The conceptual move from ordered distance vectors to multisets is well motivated by prior work on perturbation-resistant active attacks, and the definitions are self-contained with no fitted parameters. The graph-family results are of independent interest in metric graph theory. However, the central algorithmic claim is not correct as stated: the ILP does not enforce that the minimum equivalence class size equals k, and consequently the reported computational values in Section 5 are not msad_k values. Several proofs in Section 3.2 also contain fixable but nontrivial errors. The multiset-adversary modeling assumption is plausible but is not empirically validated in this paper.

major comments (3)
  1. [Section 4.1, Eq. (6)] The formulation F does not enforce the defining property of a k-MARS. By Definition 2 and the remark in Section 2.2, a set S is a k-MARS exactly when the minimum size of an equivalence class in Z_S equals k. Constraint (6) only imposes |class| ≥ k for every class, so F minimizes over all sets whose minimum class size is at least k. This is a strictly larger family, and it falsifies the claim that F computes msad_k exactly. For K_{1,3} with k=2, S={center} is feasible for F (the only class has size 3, which is at least 2), so F returns 1, whereas Proposition 8(iii) and direct inspection give msad_2(K_{1,3})=2. Since Tables 1–3 are produced with this formulation, the reported "|S|" values and the conclusions in Section 5.1 are not values of msad_k. The model must be amended (for example by requiring at least one class of size exactly k) or the claims about computing msad_k must be withdrawn.
  2. [Section 3.2, Proposition 14] The proof does not establish the stated bound for msad_k. The set S described as containing the root r and all vertices at distance at most log2 k has equivalence classes of sizes 2^{log2 k+1}, ..., 2^d, so it is a (2k)-MARS, not a k-MARS; the proof itself later says "S is a 2k-MARS." Moreover, the formula |S| = Σ_{i=1}^{log2 k} d^{i-1} is inconsistent with the example k=4, where the literal reading of "distance at most log2 k" gives |S|=7, while the text claims S is formed by r and its two children, which has size 3. Replacing the construction by "root plus levels up to log2 k − 1" and the summand d^{i-1} by 2^{i-1} would give a valid k-MARS of size k−1, but as written the proposition's proof is invalid.
  3. [Section 3.2, Proposition 8(ii)] The proof of the r>t case chooses z ∈ V, the smaller bipartition. Then V \ {z} has cardinality t−1 = k−1, so {z} is not a k-MARS. The argument works if z is chosen in U, since then V is a class of size t = k and U \ {z} has size r−1 ≥ k. The claimed value appears correct, but the proof must be corrected.
minor comments (4)
  1. [Section 3.2, Lemma 13] Lemma 13 states a nontrivial structural claim about k-MARS in trees for k ≥ 3, but no proof is supplied; the sentence "by using similar arguments as the ones used in Lemma 10" is not a proof. Please provide a proof or a precise reference.
  2. [Definition 2] The multiset notation m(v|S) = { |d_G(v,s_1), ..., d_G(v,s_r)| } is nonstandard and easy to confuse with a set of absolute values; using double braces (e.g., {{...}}) would improve clarity.
  3. [Section 5, Table 3] The table header "C37 C40" with alternating |S| and CPU columns is difficult to read when one of the two cycle instances has no entry in a row; please restructure the table or add explicit subheadings.
  4. [Throughout] There are several typographical and wording issues, e.g., "traduced" should be "translated" in Section 2.1, and the sum in Proposition 14 is written as "Plog2 k" without proper summation limits. A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new definitions and ILP are self-contained; the ILP exactness gap (>=k instead of exactly k) is a correctness issue, not a circular reduction.

full rationale

The derivation chain is definitional and self-contained. The concepts of k-MARS, (k,ell)-multiset anonymity, and msadk(G) are introduced as new definitions, and the observation in Section 2.2 that any set S is a k-MARS with k equal to the minimum equivalence-class size is a restatement of Definition 2 rather than an input that generates the later results. The ILP in Section 4 is built directly from the equivalence-class partition induced by multiset representations, with no fitted parameters, no subset of data used to tune a prediction, and no output quantity that is equal by construction to an input. The appeal to reference [16] to motivate replacing ordered distance vectors with multisets is background justification for the modeling choice; although [16] shares an author with the present paper, the formal contributions (kappa(G), msadk for paths, trees, complete bipartite graphs, and wheels, plus the optimization formulation) do not reduce to that citation or to any other self-citation. One correctness caveat, which is outside the scope of circularity: constraint (6) only enforces that each equivalence class has size at least k, whereas Definition 2 requires the minimum class size to be exactly k, as the paper itself states in Section 2.2; consequently the formulation can accept a set whose classes all exceed k as a k-MARS, potentially understating the true msadk. That is a modeling/correctness gap, not a circular dependence.

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

The paper's central claims rest on standard graph theory, a domain assumption about the adversary model, and the connectedness of the graphs. No parameters are fitted to data; the ILP uses a fixed big-M upper bound (n-k) rather than a learned quantity. No physical or ad hoc entities are postulated; the new k-MARS notion is a mathematical definition supported by examples and proofs.

assumptions (3)
  • domain assumption Connectedness of the social graph G (finite distances).
    Definitions use geodesic distances; throughout the paper graphs are assumed connected without explicit restatement.
  • domain assumption An adversary's knowledge of a victim is the multiset of distances to the attacker set S, and the attacker can retrieve S but not order its elements.
    Introduced in Section 1 before Definition 2 as the modeling rationale for the new measure.
  • standard math Standard background results on metric dimension, k-metric antidimension, and multiset dimension are accepted.
    Used in Sections 2 and 3 to position and prove results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the $(k,\ell)$-multiset anonymity measure for social graphs." pith.science (2026). https://pith.science/paper/Y5EOG7MK

@misc{pith2026250708433,
  author       = {Pith},
  title        = {Pith review of: On the $(k,\ell)$-multiset anonymity measure for social graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y5EOG7MK}},
  note         = {Machine review of arXiv:2507.08433}
}
abstract

The publication of social graphs must be preceded by a rigorous analysis of privacy threats against social graph users. When the threat comes from inside the social network itself, the threat is called an active attack, and the de-facto privacy measure used to quantify the resistance to such an attack is the $(k,\ell)$-anonymity. The original formulation of $(k,\ell)$-anonymity represents the adversary's knowledge as a vector of distances to the set of attacker nodes. In this article, we argue that such adversary is too strong when it comes to counteracting active attacks. We, instead, propose a new formulation where the adversary's knowledge is the multiset of distances to the set of attacker nodes. The goal of this article is to study the $(k,\ell)$-multiset anonymity from a graph theoretical point of view, while establishing its relationship to $(k,\ell)$-anonymity in one hand, and considering the $k$-multiset antiresolving sets as its theoretical frame, in a second one. That is, we prove properties of some graph families in relation to whether they contain a set of attacker nodes that breaks the $(k,\ell)$-multiset anonymity. From a practical point of view, we develop a linear programming formulation of the $k$-multiset antiresolving sets that allows us to calculate the resistance of social graphs against active attacks. This is useful for analysts who wish to know the level of privacy offered by a graph.

Figures

Figures reproduced from arXiv: 2507.08433 by the authors.

Figure 1
Figure 1. Bold vertices form a 1-MARS in (a); a 2-MARS in (b); and a 6-MARS in (c). such that there exists a k-multiset antiresolving in a graph G. This parameter is relevant, as it bounds the maximum level of privacy that a graph can offer, when there is no limit on the number of attacker nodes. We study the k-multiset antidimension of various graphs families, such as trees, wheels, and bipartite graphs. The k-multiset antid… view at source ↗
Figure 2
Figure 2. The graph G∗ with adim4(G∗ ) = 2 and msad8(G∗ ) = 2. On the other hand, it was noted in [24], that for any graph G of maximum degree ∆ it holds that κ ′ (G) ≤ ∆. One could think that an analogous situation could occur for κ(G). However, this is far from the reality. Consider for instance the graph G∗ given in [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The multiset representations of the vertices with respect to the set of red-coloured [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Multiset resolvability parameters in graphs: A survey with new results and open problems

    math.CO 2026-07 accept novelty 5.0 of 10

    Multiset resolvability parameters are surveyed; sharp outer-multiset lower bounds for diameter-two and join graphs are proved, and block graphs with local multiset dimension two are characterized.

Reference graph

Works this paper leans on

28 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [1]

    Backstrom, C

    L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. InProceedings of the 16th Inter- national Conference on World Wide Web, WWW ’07, page 181–190, New York, NY, USA,

    work page

  2. [2]

    Chatterjee, B

    T. Chatterjee, B. DasGupta, N. Mobasheri, V. Srinivasan, and I. G. Yero. On the computa- tional complexities of three problems related to a privacy measure for large networks under active attack.Theoretical Computer Science, 775:53–67, 2019

    work page 2019

  3. [3]

    Burning some myths on privacy properties of social networks against active attacks

    S. Cicerone, G. Di Stefano, S. Klavžar, and I. G. Yero. Burning some myths on privacy properties of social networks against active attacks, arXiv:2504.16944 [cs.SI], 2025

    work page Pith review arXiv 2025

  4. [4]

    DasGupta, N

    B. DasGupta, N. Mobasheri, and I. G. Yero. On analyzing and evaluating privacy measures for social networks under active attack.Information Sciences, 473:87–100, 2019

    work page 2019

  5. [5]

    J. Díaz, O. Pottonen, M. Serna, and E. J. van Leeuwen. Complexity of metric dimension on planar graphs. Journal of Computer and System Sciences, 83(1):132–158, 2017. 23

    work page 2017

  6. [6]

    S. H. Erfani and R. Mortazavi. A novel graph-modification technique for user privacy- preserving on social networks.Journal of Telecommunications and Information Technology, 3:27–38, 10 2019

    work page 2019

  7. [7]

    Fernández, D

    E. Fernández, D. Kuziak, M. Muñoz Márquez, and I. G. Yero. On the (k, ℓ)-anonymity of networks via theirk-metric antidimension. Scientific Reports, 13(1), 2023

    work page 2023

  8. [8]

    Gil-Pons, Y

    R. Gil-Pons, Y. Ramírez-Cruz, R. Trujillo-Rasua, and I. G. Yero. Distance-based vertex iden- tification in graphs: The outer multiset dimension.Applied Mathematics and Computation, 363:124612, 2019

    work page 2019

Show all 28 references
  1. [9]

    Hakanen and I

    A. Hakanen and I. G. Yero. Complexity and equivalency of multiset dimension and id- colorings. Fundamenta Informaticae, 191(3-4):315–330, 2024

    2024

  2. [10]

    Harary and R

    F. Harary and R. A. Melter. On the metric dimension of a graph.Ars Combinatoria, 2:191– 195, 1976

    1976

  3. [11]

    Klavžar, D

    S. Klavžar, D. Kuziak, and I. G. Yero. Further contributions on the outer multiset dimension of graphs. Results in Mathematics, 78(2):50, 2023

    2023

  4. [12]

    Kratica, V

    J. Kratica, V. Kovačević-Vujčić, and M. Čangalović.k-metric antidimension of some gener- alized petersen graphs.Filomat, 2019

    2019

  5. [13]

    Kuziak and I

    D. Kuziak and I. G. Yero. Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 [math.CO], 2021

    2021 arXiv

  6. [14]

    S. Mauw, Y. Ramírez-Cruz, and R. Trujillo-Rasua. Anonymising social graphs in the presence of active attackers.Trans. Data Priv., 11(2):169–198, 2018

    2018

  7. [15]

    S. Mauw, Y. Ramírez-Cruz, and R. Trujillo-Rasua. Conditional adjacency anonymity in social graphs under active attacks.Knowl. Inf. Syst., 61(1):485–511, 2019

    2019

  8. [16]

    S. Mauw, Y. Ramírez-Cruz, and R. Trujillo-Rasua. Robust active attacks on social graphs. Data Min. Knowl. Discov., 33(5):1357–1392, 2019

    2019

  9. [17]

    S. Mauw, Y. Ramírez-Cruz, and R. Trujillo-Rasua. Preventing active re-identification attacks on social graphs via sybil subgraph obfuscation.Knowl. Inf. Syst., 64(4):1077–1100, 2022

    2022

  10. [18]

    S. Mauw, R. Trujillo-Rasua, and B. Xuan. Counteracting active attacks in social network graphs. In Silvio Ranise and Vipin Swarup, editors, Data and Applications Security and Privacy XXX - 30th Annual IFIP WG 11.3 Conference, DBSec 2016, Trento, Italy, July 18-20, 2016. Procee...

    2016

  11. [19]

    Samarati

    P. Samarati. Protecting respondents identities in microdata release.IEEE Transactions on Knowledge and Data Engineering, 13(6):1010–1027, 2001

    2001

  12. [20]

    Simanjuntak, P

    R. Simanjuntak, P. Siagian, and T. Vetrik. The multiset dimension of graphs, arXiv:1711.00225 [math.CO], 2019. 24

    2019 arXiv

  13. [21]

    P. J. Slater. Leaves of trees.Congressus Numerantium, 14:549–559, 1975

    1975

  14. [22]

    J.-H. Tang, T. Noreen, M. Salman, M. Rehman, and J.-B. Liu.(k, ℓ)-anonymity in wheel- relatedsocialgraphsmeasuredonthebaseof k-metricantidimension. Journal of Mathematics, 2021:1–13, 09 2021

    2021

  15. [23]

    R. C. Tillquist, R. M. Frongillo, and M. E. Lladser. Getting the lay of the land in discrete space: A survey of metric dimension and its applications.SIAM Review, 65(4):919–962, 2023

    2023

  16. [24]

    Trujillo-Rasua and I

    R. Trujillo-Rasua and I. G. Yero. k-metric antidimension: A privacy measure for social graphs. Information Sciences, 328:403–417, 2016

    2016

  17. [25]

    Trujillo-Rasua and I

    R. Trujillo-Rasua and I. G. Yero. Characterizing 1-metric antidimensional trees and unicyclic graphs. The Computer Journal, 59(8):1264–1273, 08 2016

    2016

  18. [26]

    Fico® xpress solver

    Xpress. Fico® xpress solver

  19. [27]

    Zhang and Y

    C. Zhang and Y. Gao. On the complexity ofk-metric antidimension problem and the size of k-antiresolving sets in random graphs. In Yixin Cao and Jianer Chen, editors,Computing and Combinatorics, pages 555–567, Cham, 2017. Springer International Publishing. 25

    2017

  20. [2007]

    Association for Computing Machinery

Pith tools

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