acceptodds
Under review as a conference paper at ICLR 2027

MatchPeb: Learning Graph Edge Weights via Coupled Matching and Pebbling

Abstract

Learning meaningful edge weights on unweighted graphs is a fundamental open problem: weights that are locally selective, placing mass only on semantically coherent neighbors, need not produce globally coherent communities, and vice versa. We present MATCHPEB, a framework that learns a single scalar weight w(u, v) per edge to simultaneously satisfy a fractional matching constraint for local selectivity and serve as the conductance of a personalized PageRank diffusion for global coherence. MATCHPEB turns edge-weight learning into a differentiable algorithmic prior, marrying neural representation learning with two classical graph procedures. A normalizing-flow density model on subgraph centroids then regularizes the manifold of learned communities. On the Cora citation benchmark, MATCHPEB achieves precision@10 of 0.853, an +8.7 pp- improvement over uniform-weight PPR for seed-based community retrieval, and clustering NMI 0.636 when the learned diffusion operator assigns nodes to communities versus 0.345 for k-means on the same embeddings (1.85× higher, and roughly 5× more stable across seeds). On knowledge-graph link prediction, a relation-conditioned extension of the pebbling operator improves a DistMult backbone (filtered MRR 0.377 on FB15k-237; a +4.4% relative tail-MRR gain on WN18RR). We further characterize when this structural prior helps and when it impacts a stronger ComplEx+DURA backbone.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Edge Weight, Edge Weight Assignment, Graph Matching, Graph Pebbling, Matching, Pebbling, Page Rank, Community Detection, Graph Embeddings, GNN, GCN, KGE

Reviews

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

MatchPeb combines a GNN encoder, a symmetric edge scorer, differentiable personalized PageRank (PPR), and a normalizing-flow density model. The learned edge weights enter both a penalty encouraging incident weights to sum to one and the PPR transition matrix. Additional losses encourage community agreement, internal connectivity, and high density of community centroids. The experiments cover Cora community retrieval and classification, plus knowledge-graph link prediction.

Critical strengths
  1. The shared-weight design is interpretable and potentially useful. Using the same edge weights for regularization and diffusion creates a direct connection between the learned local graph structure and downstream propagation. Freezing these weights for use in other graph models is a sensible practical objective.
  2. The paper reports informative ablations and negative results. The three-seed Cora experiments reveal a trade-off between label agreement and conductance. The knowledge-graph experiments also acknowledge that diffusion can hurt stronger backbones. These disclosures help identify the method’s limitations, although they substantially narrow the positive claims.
Critical weaknesses
  1. The stated objective contains consequential mathematical problems. Equation (8) uses KL(πs ∥ qs)\mathrm{KL}(\pi_s \,\|\, q_s), although qsq_s assigns zero probability outside the target community or top-kk set; the loss is infinite whenever PPR places positive mass outside that support. Any smoothing or alternative implementation is unspecified. Moreover, Equation (5), with temperature one and k=20k=20, assigns every node a mask weight of at least σ(−1/20)≈0.4875\sigma(-1/20)\approx 0.4875. Consequently, the purported community centroid is almost a global average, undermining the density model’s intended role. These issues affect central components and require implementation verification and potentially revised experiments.
  2. The evaluation does not establish an independent test of generalization. Appendix B.2 explicitly selects λ5=1.15\lambda_5=1.15 using test-seed retrieval and clustering results, making the reported performance subject to test-informed hyperparameter selection. The manuscript also does not clarify whether held-out node labels enter the supervised community targets or whether the transferred MatchPeb checkpoint excludes downstream classification test labels. These protocol concerns materially weaken the reported gains and require a complete label-access specification and reevaluation with validation-only selection.
Questions for authors
  1. How is Equation (8) computed when the target has zero entries? What smoothing, masking, normalization, or KL direction is actually used?
  2. Does the implementation use Equation (5) with temperature one on normalized PPR scores? What are the observed mask sums and distances between community centroids and the global centroid?
  3. Was λ5\lambda_5 selected using test metrics as Appendix B.2 states? Which node labels were accessible during target construction and pretraining for the downstream classification experiment?
  4. After correcting these issues and matching the supervision budget, does the full model improve over supervised learned PPR without the matching and density components?
1 comment
AuthorsOpenReview ↗

Response to Reviewer bHBk

Thank you for the deep implementation-level reading of the paper, and for acknowledging the shared-weight design and our negative results. Your two mathematical concerns are the most important in the batch; we treat them directly.

Eq. (8) — "the loss is infinite whenever PPR places mass outside the target support." This is the one place we must respectfully correct the review. The implementation clamps q_s (and π_s) to ε = 1e-12 before the log, so the KL is finite; off-support mass incurs a large but bounded penalty π_s(v)·log(π_s(v)/ε), in the direction KL(π_s‖q_s). The paper failed to state this, which is our fault; the objective as implemented is well-defined. Full specification (clamping, direction, numerical constants) will be added. See also tLRw Q1.

Eq. (5) — the soft mask makes μ_H almost a global average, undermining the density model. You are correct, and this is the key finding of the review. At the submitted temperature T = 1 the mask is ≈ 0.5 for essentially all nodes (our diagnostic: only 0.75% of mask weight lands on the true top-k), so μ_H is near-global and the density term is effectively inert — which is precisely why its ablation shows almost no effect. We detail the correction (scale-aware temperature / π-normalization) and the honest re-evaluation plan in SR1. We will verify the corrected mask sums and the distance between per-seed centroids and the global centroid, and report them.

Protocol — test-informed λ₅ selection; label access for targets and transfer. Accepted; see SR2. We will provide a complete label-access specification and re-run with validation-only selection and training-only targets.

Q — After correcting these issues and matching the supervision budget, does the full model beat supervised learned PPR without matching and density? This is the decisive question and we will answer it empirically rather than rhetorically. With the corrected mask, validation-only selection, and training-only targets, we will report the full model against a supervised learned-PPR baseline with the matching and density terms removed, under a matched supervision budget. If the matching and density components do not earn their place, we will drop them from the claimed contribution and present the shared-weight supervised-diffusion formulation — the part you identified as interpretable and practically useful — as the core result.

Reviewer_tLRwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

this paper proposes a framework for learning edge weights on unweighted graphs by coupling a fractional-matching-inspired regularizer with differentiable personalized PageRank (PPR) diffusion. Experiments on the Cora citation network report improvements in community retrieval over uniform-weight PPR and feature-based nearest-neighbor retrieval.

Critical strengths
  1. Promising improvements in Cora community retrieval.
  2. Extensive ablation and sensitivity analyses.
Critical weaknesses

1.The primary evaluation concerns community retrieval on Cora, where the seven citation categories are treated as ground-truth communities. The paper states that validation and test seed nodes are held out. However, holding out nodes as query seeds is not equivalent to withholding their class labels from the training objective. If the supervised target for a training seed is constructed using the labels of all nodes belonging to its class, then the loss may incorporate the ground-truth labels of validation or test nodes, even when those nodes are not selected as training seeds. 2. Appendix B.2 describes selecting the pebbling loss coefficient λ5 through extensive sweeps that evaluate test-seed retrieval and clustering performance. However, if these metrics were computed on the held-out test set and subsequently used to choose λ5, the test set would effectively become part of the model-selection procedure.

Questions for authors
  1. How is KL(\pi_s || q_s) implemented when q_s assigns zero probability to nodes outside the target community? What smoothing or numerical stabilization is used?
  2. Since removing matching improves precision and NMI, and removing density has almost no effect, what evidence supports the necessity of the complete coupled architecture?
1 comment
AuthorsOpenReview ↗

Response to Reviewer tLRw

Thank you — and we appreciate that you found the presentation clear and the analyses extensive.

W1 — Held-out seeds vs. withheld labels (target leakage). Valid; see SR2(2). We will fully specify label access and re-run with training-only targets.

W2 — λ₅ selected using test-seed metrics (Appendix B.2). Valid; see SR2(1). We will re-select on validation and report the corresponding test numbers.

Q1 — How is KL(π_s‖q_s) implemented when q_s is zero outside the target support? What smoothing/stabilization is used? This is a point we under-specified in the paper, and we want to correct the resulting impression that the loss is ill-defined. The implementation clamps both distributions to ε = 1e-12 before taking logs and evaluates the KL in the direction KL(π_s‖q_s):

L = Σ_v π_s(v) · [log(max(π_s(v), ε)) − log(max(q_s(v), ε))].

Because q_s is clamped to ε, off-support mass is penalized by a large but finite term π_s(v)·log(π_s(v)/ε); the loss is never infinite. Functionally this acts as a strong coverage penalty that drives π_s onto the target community. We will state the clamping, the direction, and this interpretation explicitly in the revised objective, and we thank you for surfacing the ambiguity.

Q2 — Given the ablation, what supports the full coupled architecture? See SR3 and SR1. Short version: the supervised diffusion term is the primary driver; matching is a trade-off knob; density is being re-evaluated under the corrected mask and will be retained only if it helps.

Reviewer_viPTOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of learning meaningful edge weights on unweighted graphs to improve community discovery. The authors propose MatchPeb, a framework that combines fractional matching constraints with differentiable personalized PageRank to jointly optimize local edge selectivity and global community coherence. A normalizing-flow-based regularizer is further introduced to model community representations.

Critical strengths

S1. The proposed framework offers an interesting approach to combining fractional matching constraints with differentiable PPR.

S2. The experiments demonstrate improvements in community retrieval and clustering over the selected baselines.

Critical weaknesses

W1. My main concern is the practical significance of the proposed approach. Modern GNNs and Graph Transformers can already learn adaptive neighbor importance through attention mechanisms, raising the question of whether explicitly learning a separate set of edge weights is necessary. It is unclear what practical advantages MatchPeb offers, especially given the additional costs of edge-weight learning, differentiable PPR, and density modeling. Moreover, the paper lacks systematic runtime and memory comparisons. I suggest the authors provide stronger empirical evidence demonstrating the key advantages of MatchPeb over existing modern graph learning methods in terms of effectiveness and computational efficiency.

W2. The claim that MatchPeb learns edge weights that produce coherent communities is not fully convincing, as the experiments only compare against Uniform-PPR and Feature-kNN, without comparisons to representative classical or state-of-the-art community detection methods.

W3. As shown in Table 5, the performance improvements appear to be primarily driven by the supervised pebbling objective. Removing the fractional matching loss even improves P@20 and NMI, while removing the density regularizer has almost no effect. These results raise questions about the necessity of the proposed coupling of matching, diffusion, and density modeling.

Questions for authors

See W1-W3

1 comment
AuthorsOpenReview ↗

Response to Reviewer viPT

Thank you for the review and for pressing on practical significance — this sharpened how we must position the work.

W1 — Why learn a separate edge weight when attention already adapts neighbor importance; and missing runtime/memory comparison. Two distinct points.

Positioning. Attention coefficients are recomputed inside every layer and are trained end-to-end for one supervised task; they are not a standalone object that can be frozen and reused. MatchPeb produces a single, frozen, task-agnostic edge-weight field that is computed once and then dropped, unchanged, into other models and tasks. Our knowledge-graph experiments use exactly this transfer: the frozen weights are consumed by a separate backbone without retraining. We will make this the explicit axis of comparison with attention in the introduction and related work, since it is the practical advantage and the current framing underplays it. Cost. We agree the paper lacks a runtime/memory comparison and are adding one. The relevant accounting: edge-weight learning, differentiable PPR, and density modeling are one-time offline training costs; at consumption time the frozen weight is a static weighted sparse graph, so inference cost is that of a single weighted PPR — essentially identical to Uniform-PPR and with no per-query learning. We will report wall-clock and peak memory for training and inference against the baselines.

W2 — Only Uniform-PPR and Feature-kNN; no classical/SOTA community detection. Accepted. Uniform-PPR and Feature-kNN were chosen to isolate the contribution of the learned weight versus the diffusion mechanism and versus feature similarity, but they are not an adequate community-detection comparison. We are adding Louvain, Leiden, spectral clustering, and a learned GNN-clustering method (DMoN / MinCutPool) under the same retrieval/clustering protocol.

W3 — Necessity of the matching/diffusion/density coupling. See SR3 (and SR1 for why density currently appears inert). We will narrow the claims to what the corrected experiments support.

Comments on the paper

1 comment
AuthorsOpenReview ↗

MatchPeb: Author Response (ICLR 2027, Submission 61535)

We thank all three reviewers for their careful and technically engaged reviews. Two reviewers read our equations against our ablations and identified a real implementation issue that we confirm below; we address it directly rather than around it. We also correct two points where the stated objective was misread, and we list the concrete additions we are making during the discussion period. Our guiding principle in this response is to concede what is correct, correct what is not, and not overclaim.

A few points recur across reviews (the ablation in Table 5, the soft top-k mask, and the model-selection protocol); we give the full treatment once in the Shared Response and reference it from each reviewer block.

Shared Response - SR (referenced by all three reviews)

SR1 — The soft top-k mask temperature, and why the density term looks inert (bHBk W1b; all reviewers' W3) Reviewer bHBk is correct. Our differentiable mask is m_v = σ((π_v − τ_k)/T) with a default temperature T = 1. Because personalized PageRank values are small (seed mass ≈ 0.15, median mass ≈ 1e-4), the argument (π_v − τ_k)/T is near zero for almost all nodes, so the mask is ≈ 0.5 everywhere. Our own diagnostic on a Cora-scale PPR vector confirms the magnitude of the problem:

Temperature | mask range | fraction of mask weight on true top-20

T = 1 (submitted default) | [0.494, 0.531] | 0.75%

T = 0.1 | [0.44, 0.78] | 0.9%

T = 0.01 | [0.08, 1.00] | 5%

T = 0.001 | [0.00, 1.00] | 91%

At the submitted temperature, the centroid μ_H is therefore close to a global average of node embeddings, and is nearly the same for every seed. This explains the ablation result that all three reviewers correctly flag: removing the density regularizer has almost no effect because, at T = 1, the density model receives a near-constant input and cannot contribute. This is an artifact of the mask temperature, not evidence that a community-density prior is intrinsically useless.

Correction and re-evaluation (in progress for the camera-ready/next revision): we replace the fixed-temperature sigmoid with a scale-aware mask (temperature set relative to the per-seed PPR range, equivalently normalizing π by its maximum before the sigmoid), which recovers a genuine top-k mask (91% of mask weight on the true top-k, bottom row above). We will then re-run the Cora ablation with the corrected mask and report the outcome truthfully: if the density term contributes under a working mask, we will show it; if it does not, we will remove the density component from the claimed contributions rather than defend it. We are grateful this was caught, because it localizes exactly which component is load-bearing.

SR2 — Model selection and label access (tLRw W1, W2; bHBk W2) We accept both protocol concerns and are fixing them:

λ₅ selection. Appendix B.2 reported the λ₅ sweep against test-seed metrics, which makes the reported operating point test-informed. We are re-selecting λ₅ using validation-seed metrics only, from the sweep data we already have, and will report the test numbers for the validation-selected λ₅. We will state the final selection rule unambiguously in the main text.

Label access in the supervised target. The reviewers correctly note that holding out seed nodes is not the same as withholding their labels: our target q_s is uniform over all members of the seed's class, which can include validation/test nodes. We will (a) give a complete label-access specification for both the retrieval objective and the transferred-checkpoint classification experiment, and (b) re-run with supervised targets constructed from training-node labels only, reporting whether the gains persist. We expect a reduction but will report the measured effect, not an assertion.

SR3 — What the ablation actually supports (viPT W3, tLRw Q2, bHBk Q) With SR1 and SR2 understood, our honest reading of Table 5 is:

The supervised pebbling KL (λ₅) is the dominant driver (zeroing it drops P@20 by 12.3 pp, NMI by 18.1 pp, ARI by 24.1 pp, coverage 0.914 → 0.775). We do not dispute this. Matching trades label agreement for boundary tightness: removing it can raise P@20/NMI slightly while loosening subgraph boundaries (higher conductance). This is a controllable selectivity/conductance trade-off, and we will present it as such rather than as a uniform improvement. Density's apparent null effect is, at least in part, the SR1 mask artifact; we will re-evaluate and reframe per SR1. We will revise the contribution claims so that they match the evidence: a shared-weight formulation whose supervised-diffusion component is the primary driver, with matching offering a tunable trade-off, and density retained only if it demonstrably helps under the corrected mask.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.