acceptodds
Under review as a conference paper at ICLR 2027

Edge-Private Matching Kernels Through Local Decoding

Abstract

A matching is a set of edges with no shared endpoints. We study how participants can retain useful matching structure when each knows its own relationships but those relationships are sensitive to outside observers. Our protocols publish a pure edge-differentially-private record of coordination messages. Each participant combines that record with its private neighbor list to obtain a shortlist of relationships; the two endpoints agree on every selected relationship. For a graph with vertices, the main protocol uses communication rounds, and its completed public record can be stored in bits. Let be the privacy budget, the allowed failure probability, and , with , the approximation factor. For a universal constant , a per-vertex capacity of at least suffices for two guarantees to hold together with probability at least : the selected graph retains a fraction of the best edge count under the same capacity, and it contains an ordinary matching of at least that fraction of the original maximum. The key property is that every omitted edge touches a vertex whose shortlist is nearly full. We also prove lower bounds explaining why local decoding and a probabilistic capacity guarantee are needed, characterize a class of consistent local decoders, and give parallel and insertion-only streaming extensions. The released public messages satisfy differential privacy; the selected relationships remain a secret at their endpoints.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
matching, differential privacy, local edge differential privacy

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_YqHQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies private coordination of bounded reciprocal neighbor shortlists. A pure edge-private public transcript defines a candidate graph; each vertex intersects its private adjacency list with that graph. The sequential protocol establishes near-capacity saturation and, for capacity of order log(n/rho)/(eta epsilon), simultaneously approximates the optimum same-capacity edge count and preserves an ordinary matching within a factor 2+eta. It uses O(n) rounds, with an O(n log n)-bit encoding of the completed unit-step transcript. Lower bounds distinguish explicit candidates, almost-sure degree caps, and probabilistic local decoding. A representation theorem characterizes deterministic, valid, endpoint-consistent local decoders under the stated pure-privacy assumptions. Parallel and insertion-only streaming variants are also presented. Validation is theoretical.

Critical strengths
  1. Theorem 3 gives both same-capacity approximation and matching preservation on one success event. Proposition 7 and Theorem 8 explain the importance of probabilistic feasibility and establish a capacity obstruction in the main fixed-accuracy regime. This is more informative than an isolated approximation algorithm.

  2. Theorem 9 shows that intersection decoding captures a broader class of deterministic consistent local rules, subject to its explicit input and state restrictions. It helps distinguish a convenient construction from a property forced by the chosen privacy and consistency requirements.

Critical weaknesses
  1. Appendix G.4 treats reciprocal standby-directory planning as the completed task, which is a legitimate boundary. However, each site already stores its entire eligibility row. Merely marking a bounded subset does not save storage of the underlying relationships. The paper needs to identify what scarce resource b actually limits and what decision the shortlist enables. Reservations, maintenance, or downstream computation could supply such a role, but the current workflow does not make one concrete. It also does not sufficiently connect same-capacity edge count and matching containment to success in that decision. This matters because the b >= n−1 case is trivial with zero privacy loss: the value of private truncation depends on a reason to require smaller directories.

  2. A private protocol need not solve activation or release a final matching to be valuable, and I do not require deployment or new experiments from a theory paper. Nevertheless, the paper should explain why this decoder class is the right abstraction for a named class of consequential coordination tasks, or why its explicit/implicit and zero-failure separations settle an important question independently of the application. The unresolved eta dependence and the distinction between quadratic online messages and compact stored history further limit conclusions about the useful operating regime. These are scope and significance concerns, not counterexamples to the theorems.

Questions for authors
  1. In the standby-directory application, what resource does the capacity b constrain, and why does marking a subset of an already-stored eligibility row relieve an actual bottleneck?
  2. What concrete decision uses the shortlist, and how do the two approximation guarantees translate into a success criterion for it? Which relationship disclosures are permitted at activation, and why is the planning-stage protection boundary appropriate for that need?
  3. Can the paper articulate the significance of the representation and separation results independently of this application, with the relevant decoder restrictions kept explicit?
Reviewer_qbWBOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a differential private algorithm for constructing matching kernels. The algorithm uses O(n) communication rounds and its completed public record can be stored in O(n log n) bits, for which the authors analyzed theapproximation factore under given failure probability and privacy budget, moreover they discussed lower bounds.

Critical strengths

This paper proposes an interestin differential private protocol for an important problem in graph DP theory. The authors achieved near-capacity saturation under pure edge privacy. It is good that they distinguish the public transcript and candidate graph from the privately decoded selected graph, which could have flexibilities in the actual applications. Usage of privacy budget based on Above Threshold is not trivial and interesting. It is also very good that they also give the negative results.

Critical weaknesses
  • Per-vertex computation time/space complexities are not discussed, though communication complexity and space of the public record are given.
  • It would be better if the authors mentions that the O(n log n) bit representation does not mean the size of the selected graph is in that size.
  • The authors should discuss differences from related works in more details.
Questions for authors
  • Can the authors add discussion on per-vertex computation time/space complexit (in the unit-step construction)?
  • In G3, the authors mentions that a transport with silence for unchanged outputs can omit flags. Does it apply to unit-step cases?
Reviewer_7TgkOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors answer the key question of “Can differentially private communication coordinate small, mutually consistent shortlists that preserve many possible disjoint assignments?” Their approach enables this by limiting every shortlist to b neighbors, retaining a fraction of the best capacity-b edge count, and preserving a fraction of the largest 1-matching inside the selected graph. The authors use the notion of b-matching in their approach. The paper is well written and provides enough details about the problem and their approach.

Critical strengths
  • The parallel and streaming extensions broaden the theoretical contribution.
  • Lower bounds explain the cost of public sparse outputs and zero-failure degree guarantees.
  • The representation theorem clarifies when intersection decoding captures all deterministic, valid, endpoint-consistent local decoders.
Critical weaknesses
  • One question I have is that why not use the notion of k-disjoint matching [A] that will easily provide the best such approximation guarantee for identifying the subgraph? [A] SM Ferdous, Bhargav Samineni, Alex Pothen, Mahantesh Halappanavar and Bala Krishnamoorthy. “Semi-Streaming Algorithms for Weighted k-Disjoint Matchings.” Embedded Systems and Applications (2023).
  • A further limitation of this work is that there is no empirical evaluation of the proposed method.
  • The result assumes that a large matching exists in the selected subgraph. However, it does not itself produce a particular matching or publicly reveal selected relationships. This needs further clarification/distinction.
Questions for authors
  • Can you use the notion of k-disjoint matching [A]? [A] SM Ferdous, Bhargav Samineni, Alex Pothen, Mahantesh Halappanavar and Bala Krishnamoorthy. “Semi-Streaming Algorithms for Weighted k-Disjoint Matchings.” Embedded Systems and Applications (2023).
  • Which guarantees are likely to be useful at realistic n,ϵ,ρ,ηn,\epsilon,\rho,\eta?
  • Can you provide a representative parameter regime beyond the worst-case scenario?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions to the paper

We thank the reviewers for their time, questions, and helpful comments. Below, we summarize the changes we made to our revision of the paper (uploaded as the newest revision in this submission). The reviewer requesting the corresponding change is given in parentheses, eg. (Reviewer X).

  1. Discussion and analysis of the per-vertex computation time and space complexity has been added to Appendix G.2 (Reviewer qbWB).
  2. Discussion of Ferdous et al. for non-private k-disjoint matchings has been added to the Introduction and to the new Appendix I discussing related works in more detail (Reviewer 7Tgk).
  3. Added Appendix J which discusses significance and scope of the representation and separation results (Reviewer YqHQ).
  4. Clarifications on what the algorithm outputs and what matching preservation means has been added to the Introduction and Section 1.1 (Reviewers 7Tgk and qbWB).
  5. More detailed discussions of related works has been added to Appendix I (Reviewer qbWB).
  6. Added sentences that distinguish transcript storage from storage of the selected graph to the Introduction and Appendices G.2–G.3 (Reviewer qbWB).
  7. Added silence-based communication bounds and their assumptions to Appendices G.2-G.3 and Table 2 (Reviewer qbWB).
  8. Addressed all reviewer questions on the Reciprocal standby directories application by revising Appendix G.4 (Reviewers YqHQ and 7Tgk).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.