MatchPeb: Learning Graph Edge Weights via Coupled Matching and Pebbling

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.