Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

Jiaqing Xie; Yanchao Li; Zhuo Yang; Yuxin Wang; Tianfan Fu; Yuqiang Li

cs.LGSep 26, 2026

Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

Authors: Jiaqing Xie, Yanchao Li, Zhuo Yang, Yuxin Wang, Tianfan Fu, Yuqiang Li

Organizations: Fudan University · Shanghai AI Lab · Shanghai Innovation Institute · Nanjing University ·

Abstract

Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal-Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster and recovering its training cost after a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph permutes the assignment and price states, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with disjoint train/validation/test splits, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4-8.6 accuracy points; after one second of refinement search, 2.5-3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks from social and protein graphs, the policy gains 9.1-17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.

Figures & tables

Panel of Figure 1 — Figure 1: NGA fits each query separately ( Ying et al., 2026 ) . ENPDA reuses a frozen equivariant policy, adapting bids and prices to return a matching and valid bounds. Symbols: $\theta$ denotes network parameters, $\boldsymbol{\lambda}$ target prices, $\mathbf{P}$ the returned matching, and $[L,U]$ the preserved-edge lower bound and valid upper bound (Section ).

Panel of Figure 2 — Figure 2: ENPDA inference. A frozen policy uses the ACG to initialize bids and guide four primal–dual updates. Hungarian projection returns a partial matching and its lower bound, and repairing the final prices gives a valid upper bound.

No search
Method	AIDS	MOLHIV	MCF-7
Analytic Core	49.78	55.36	59.19
ENPDA-Core	58.29	62.77	67.81
Nominal 60s
RASCAL	99.05	99.47	98.92
ENPDA	98.82	99.50	98.49

Table 1: MCES accuracy (%) without complete-ring filtering. (a) Local results; ENPDA averages three seeds. Nominal-60s settings are detailed in Table . (b) NGA-study reports ( Ying et al., 2026 ) under their original settings, not paired with (a). Bold highlights ENPDA’s best values within each group.

Figure 3: Four-round Core accuracy (left) and per-pair learning gains averaged over three seeds (right). More than half the pairs improve in each dataset; Table reports paired graph-cluster intervals.

Arm	AIDS	MOLHIV	MCF-7
Analytic	50.18	55.06	59.04
Initializer only	54.15	57.66	59.94
Dynamics only	55.84	60.10	64.88
Full without prices	56.60	62.31	68.26
ENPDA (full)	57.93	62.39	68.00

Table 2: Four-round component accuracy (a) and frozen transfer to 500 planted-optimum pairs (b), in percent. Settings, matched controls and paired intervals: Tables , and .

Dataset	Pairs	RASCAL	NGA	ENPDA-Solver
AIDS	100	86.85	78.46	89.73
MOLHIV	91	92.71	88.79	95.00
MCF-7	100	86.27	82.10	89.04

Table 3: Complete-aromatic-cycle reference recovery (%,

\uparrow

) relative to Table ’s unrestricted references. The 60s budget includes projection/scoring; neural seed 0, one NGA fit, RASCAL internal filter off (Appendix ).

Figure 6: MCF-7 pair 42 under the complete-cycle rule (Table ). Teal bonds are retained; orange dashed bonds are compatible matches removed by the rule.

Appendix figures & tables36 assets

Supplementary material from the paper’s appendix.

Appendix

Graphs and auction state		Network, training, and theory
$G_{a}=(V_{a},E_{a},\ell_{a},\xi_{a})$	labeled source graph ( $G_{b}$ analogously): vertices $V$ , edges $E$ , node labels $\ell$ , edge labels $\xi$	$\theta$ , $h$	frozen network parameters; hidden width
$n$ , $m$	source and target vertex counts, $n=\|V_{a}\|\leq m=\|V_{b}\|$	$c_{t,ij}$ , $a_{t,ij}$ , $b_{t,j}$ , $u_{t,i}$	neural correction; primal and dual multipliers; unmatched update
$p$ , $\bot$ , $C(p)$	partial injective map; unmatched marker; preserved-edge set	$\Pi_{[a,b]}$ , $[\cdot]_{+}$	clipping projection; positive part
$\mathcal{C}$ , $E_{\rm ACG}$	label-compatible node pairs; association-common-graph edges	$\mathbf{1}$ , $\mathbf{1}\{\cdot\}$ , $\operatorname{vec}(\cdot)$	all-ones vector; indicator function; row stacking
$\mathbf{A}$	sparse symmetric ACG adjacency on the $n{\times}m$ grid	$p^{\star}$ , $\mathcal{I}$ , $\mathcal{L}_{t}$	teacher mapping; active source rows; round- $t$ negative log likelihood
$\mathbf{S}_{t}$ , $\mathbf{P}$	soft assignment; hard partial-injection matrix	$\mathcal{L}_{\rm map}$ , $\mathcal{L}_{\rm rel}$ , $\mathcal{L}$	trajectory imitation, analytic-relative, and total losses

Appendix

Table 4: Notation summary.

Dataset	Train	Validation	Test	Test clusters
AIDS	19	11	100	21
MOLHIV	628	76	91	90
MCF-7	696	85	100	82

Appendix

Table 5: Graph-disjoint native scope. Exact node/edge-label-preserving isomorphism checks are global across datasets; every pair of splits has zero shared graph identities. Test pairs are unchanged by the training split construction.

Seed	Retrained no-price	ENPDA (full)
0	10	4
1	12	12
2	12	6

Appendix

Table 6: Validation-selected epochs after matched 12-epoch training. Each arm selects its own checkpoint; no native test inputs enter selection.

Arm / contrast	AIDS	MOLHIV	MCF-7
Sinkhorn	45.82	47.53	45.60
Gumbel–Sinkhorn (10)	39.51	44.83	46.30
ENPDA-Core	58.29	62.77	67.81
Full $-$ Sinkhorn	+12.47 [9.04, 15.42]	+15.24 [12.05, 18.39]	+22.21 [19.19, 25.42]
Full $-$ Gumbel–Sinkhorn	+18.77 [15.95, 21.33]	+17.94 [14.39, 21.68]	+21.52 [18.01, 24.91]
Sinkhorn time (s)	0.253	0.151	0.169

Appendix

Table 7: Train-once controls using the new graph-disjoint split and teacher. Accuracy (%), paired gain (pp) with 95% CI, and mean measured time. Gumbel–Sinkhorn selects the best exact hard score from ten samples.

Arm / contrast	AIDS	MOLHIV	MCF-7
Analytic	49.78	55.36	59.19
Retrained no-price	58.81	62.45	67.73
Full, prices removed	56.70	63.25	67.98
Analytic, no prices	48.32	54.16	55.96
ENPDA-Core	58.29	62.77	67.81
$\Delta$ : full $-$ analytic	+8.50 [5.89, 12.31]	+7.41 [4.32, 10.51]	+8.62 [5.83, 11.43]

Appendix

Table 8: Primary four-round, one-projection comparison, with no search. Accuracy is in percent; differences are percentage points with graph-cluster, paired-seed 95% CIs. Price removal uses the full checkpoint; retrained no-price is a separately optimized model.

Arm / contrast	AIDS	MOLHIV	MCF-7
Analytic	48.53	55.31	59.61
Retrained no-price	58.79	62.47	68.98
Full, prices removed	57.86	62.06	68.39
Analytic, no prices	47.18	54.57	55.89
Full	59.15	62.15	67.96
Full $-$ analytic	+10.62 [7.06, 14.63]	+6.84 [3.76, 9.83]	+8.35 [5.34, 11.46]

Appendix

Table 9: Deterministic arithmetic sensitivity: all 291 pairs and five arms across three seeds, with frozen full and no-price weights. Entries are accuracy (%) or paired differences (pp) with 95% CIs. These measurements supplement, rather than replace, the primary comparison.

Arm / contrast	AIDS	MOLHIV	MCF-7
Analytic	50.18	55.06	59.04
Initializer only	54.15	57.66	59.94
Dynamics only	55.84	60.10	64.88
Full without prices	56.60	62.31	68.26
Full	57.93	62.39	68.00
Initializer $-$ analytic	+3.96 [1.72, 6.47]	+2.60 [0.03, 5.16]	+0.89 [-1.93, 3.71]

Appendix

Table 10: Separate matched component evaluation at four rounds and one projection. Accuracy (%) and paired differences (pp), with 95% CIs; these inference interventions do not retrain the full checkpoint.

Dataset	Rounds	Difference [95% CI]	Analytic	ENPDA
AIDS	1	+1.83 [-1.41, 5.89]	41.33	43.16
AIDS	2	+2.87 [-0.39, 6.68]	46.15	49.02
AIDS	4	+9.05 [5.83, 13.10]	49.23	58.28
AIDS	8	+10.98 [8.47, 15.19]	60.68	71.65
AIDS	$8-4$	+13.37 [9.89, 17.73]	—	—
MOLHIV	1	+3.96 [1.16, 6.79]	43.40	47.36

Appendix

Table 11: Round-budget sensitivity of the same frozen policy. Accuracy (%) and learned-minus-analytic differences (pp), with 95% CIs. Rows marked

8-4

compare the learned eight- and four-round scores. Four rounds specify the deployment budget, not an optimal or converged trajectory.

Dataset	Rounds	Build	Trajectory	Projection	Total
AIDS	4	0.0204	0.2349	0.0005	0.2558
AIDS	8	0.0204	0.2396	0.0005	0.2606
MOLHIV	4	0.0140	0.1370	0.0004	0.1515
MOLHIV	8	0.0140	0.1420	0.0005	0.1565
MCF-7	4	0.0161	0.1503	0.0005	0.1669
MCF-7	8	0.0161	0.1551	0.0005	0.1716

Appendix

Table 12: Same-process H100 timing at four and eight rounds, after warmup; two repeats per pair/checkpoint. Mean seconds include ACG construction, synchronized trajectory, projection and hard scoring; disk loading is excluded.

Arm / metric	AIDS	MOLHIV	MCF-7
Analytic Core accuracy	49.69	54.90	59.09
Analytic Core mean s	0.25	0.15	0.16
Analytic Core P95 s	0.42	0.27	0.36
ENPDA-Core accuracy	57.97	61.80	67.87
ENPDA-Core mean s	0.26	0.16	0.17
ENPDA-Core P95 s	0.44	0.27	0.36

Appendix

Table 13: Deployment measurements on the same 291 native pairs. Core calls here are independent measurements of the primary four-round policy. Solver and NGA use different optimization procedures; NGA time includes all three fits. Accuracy is percent; times are seconds. Differences include paired 95% CIs.

Method	AIDS	MOLHIV	MCF-7
NeuroMatch	13.92	19.17	17.34
SimGNN	15.42	14.38	20.29
GMN	39.38	29.77	24.03
XMCS	36.42	21.47	32.22
INFMCS	25.18	16.39	31.12
NGA (literature)	1.13	0.66	0.99

Appendix

Table 14: Johnson-similarity MSE (

\times 10^{-3}

). The first six rows retain literature settings. Paired NGA and both Solver rows use verified similarities and the same sanitized native reference files.

Dataset	Search s	Difference [95% CI]	Analytic	ENPDA
AIDS	0	+8.78 [5.68, 13.37]	49.53	58.32
AIDS	1	+2.66 [0.16, 6.59]	83.79	86.44
AIDS	5	+0.24 [-0.47, 0.74]	96.21	96.45
AIDS	30	+0.29 [-0.07, 0.64]	98.39	98.69
MOLHIV	0	+7.08 [3.52, 10.60]	55.18	62.26
MOLHIV	1	+2.46 [0.64, 4.66]	91.29	93.76

Appendix

Table 15: Matched post-Core refinement. Budgets are additional search seconds, excluding Core. Accuracy (%) and paired learned-minus-analytic differences (pp), with 95% CIs.

Dataset	Analytic	Neural 0	Neural 1	Neural 2
AIDS	15	228	38	19
MOLHIV	5	228	27	13
MCF-7	16	225	34	25

Appendix

Table 16: Selected Solver stream over three seeds. Counts include ties, which retain the first candidate; these are selection frequencies, not causal attributions.

Figure 7: Saved seed-0 ENPDA-Solver correspondences on the fixed example paths. Red atoms and bonds form the compatible common-edge witness; matching integers identify corresponding atoms. All highlighted counts are recomputed from the saved maps.

Method	AIDS	MOLHIV	MCF-7
Analytic-Core	49.97 / 252.8	55.46 / 148.8	58.86 / 164.0
FMCS-0.10s	44.48 / 22.7	46.62 / 7.5	47.19 / 15.1
FMCS-0.16s	44.54 / 28.3	46.62 / 7.5	47.22 / 17.4
FMCS-0.60s	44.56 / 52.9	46.62 / 7.6	47.22 / 35.4
FMCS-matched	44.54 / 38.4	46.62 / 7.3	47.22 / 27.4
McSplit-0.10s	56.32 / 93.4	63.32 / 88.8	60.09 / 90.5

Appendix

Table 17: All native same-host short-budget controls. Entries are accuracy (%) / mean milliseconds. Neural inference uses H100; classical search uses one host CPU thread. Search objectives differ, and all returned maps are scored by unrestricted MCES.

Dataset	Reference	Gain [95% CI]	P95 ms	Overrun ms	Over %
AIDS	FMCS	13.10 [8.59, 19.89]	252.9	0.56	6.0
AIDS	McSplit	1.00 [-4.67, 6.00]	418.1	0.34	1.0
MOLHIV	FMCS	15.42 [10.42, 20.06]	17.0	0.00	0.0
MOLHIV	McSplit	-1.51 [-7.09, 4.04]	269.0	0.22	0.0
MCF-7	FMCS	20.82 [16.54, 24.79]	77.2	0.14	4.0
MCF-7	McSplit	7.24 [3.30, 11.18]	348.9	0.23	0.0

Appendix

Table 18: Per-pair Core-latency caps. Gain is Core minus the classical reference (pp) with 95% CI. P95 time and mean positive cap overrun are milliseconds; final column is the fraction exceeding cap by more than 1 ms.

Dataset	Pairs	Difference [95% CI]	Analytic	ENPDA
IMDB-BINARY	100	+9.07 [7.18, 11.07]	68.06	77.14

Appendix

Table 19: Frozen molecular-to-topology transfer under controlled 30% edge deletion and node permutation. Accuracy (%) uses the known planted optimum; differences (pp) have exact-identity-cluster, paired-seed 95% CIs.

Dataset	Pairs	Difference [95% CI]	Analytic	ENPDA
PROTEINS	200	+17.65 [16.36, 18.93]	38.33	55.98
ENZYMES	200	+17.55 [16.36, 18.74]	37.98	55.53

Appendix

Table 20: Frozen molecular-to-topology transfer under controlled 30% edge deletion and node permutation. Accuracy (%) uses the known planted optimum; differences (pp) have exact-identity-cluster, paired-seed 95% CIs.

Method	Accuracy range (%)	Mean ms	P95 ms	Gain 95% CI
Analytic-Core	[83.94, 89.63]	520.2	2663.3	[0.99, 4.66]
McSplit-0.10s	[77.79, 83.42]	45.3	100.5	[1.03, 13.44]
McSplit-0.16s	[77.82, 83.47]	69.8	160.6	[0.97, 13.38]
McSplit-0.60s	[78.23, 83.95]	221.3	600.6	[0.20, 12.95]
McSplit-matched	[78.04, 83.73]	198.3	390.8	[0.60, 13.12]
ENPDA-Core	[86.28, 92.18]	526.9	2800.7	—

Appendix

Table 21: All 100 natural IMDB pairs. Accuracy ranges reflect unresolved optima; CIs for Core minus the row method also resample the 54 exact-topology clusters and training seeds. Timing is H100 plus host CPU, in milliseconds.

Nodes	Grid (k)	Compat. (k)	Build s	Forward s	Peak GiB	$L/U_{0}$
63.5	4.0	0.2	0.19	0.88	0.045	0.171
111.0	12.3	0.6	0.58	2.58	0.073	0.183
188.5	35.1	2.3	2.15	8.49	0.152	0.215
310.5	95.8	5.2	5.71	25.15	0.360	0.211
501.0	249.0	13.9	14.59	62.48	0.886	0.242

Appendix

Table 22: Natural D&D scaling, five pairs per size bin and seed 0. Entries are medians. Forward time excludes projection; ACG build is separate.

L/U_{0}

is a lower-bound diagnostic, not exact MCES accuracy.

Figure 8: Natural D&D scaling. Candidate sparsity, feasible lower-bound quality and measured build/forward times are reported separately. Each point is a five-pair median, with seed 0.

Dataset	Difference [95% CI]	Mean seconds	RASCAL	ENPDA
AIDS	-0.23 [-0.65, 0.34]	16.52 / 60.27	99.05	98.82
MOLHIV	+0.03 [-0.43, 0.55]	9.94 / 60.15	99.47	99.50
MCF-7	-0.43 [-0.95, 0.11]	11.78 / 60.15	98.92	98.49
All	-0.22 [-0.50, 0.09]	12.83 / 60.19	99.14	98.92

Appendix

Table 23: Nominal 60-second per-pair stopping settings, retaining returned incumbents. Realized runtimes are reported; timing details appear in the accompanying text. Accuracy (%), paired difference (pp) with 95% CI, and mean realized seconds (RASCAL / ENPDA).

Cap s	Dataset	Pairs	Difference [95% CI]	RASCAL	ENPDA
60	AIDS	21	+3.32 [2.02, 4.33]	95.49	98.82
60	MOLHIV	11	+4.24 [1.88, 6.67]	95.64	99.87
60	MCF-7	18	+3.58 [0.10, 7.04]	94.00	97.58
60	All	50	+3.62 [2.21, 5.06]	94.99	98.60
900	AIDS	12	+1.34 [-0.79, 3.17]	96.83	98.16
900	MOLHIV	6	+2.24 [0.00, 5.17]	97.74	99.98

Appendix

Table 24: Frozen RASCAL-timeout subsets. ENPDA uses its full Solver settings, not the RASCAL cap. Accuracy (%) and paired differences (pp), with 95% CIs; the subset definition is conditional on RASCAL.

RASCAL cap	Dataset	RASCAL	ENPDA
60	AIDS	63.22 / 71.45	339.66 / 510.65
60	MOLHIV	65.24 / 73.26	176.88 / 256.90
60	MCF-7	61.01 / 61.03	281.55 / 443.14
60	All	62.87 / 71.72	282.93 / 497.95
900	AIDS	903.87 / 913.36	344.23 / 504.04
900	MOLHIV	903.54 / 908.22	183.29 / 245.54

Appendix

Table 25: Realized runtime on the fixed timeout subsets (seconds). Each entry is mean / P95. The two algorithms need not consume their nominal cap.

Method	AIDS (100)	MOLHIV (91)	MCF-7 (100)
RASCAL, internal filter off	23.04 / 16.48	18.92 / 8.75	16.78 / 12.26
RASCAL, internal filter on	17.63 / 10.06	18.16 / 6.57	15.49 / 10.72
NGA, one fit	20.36 / 19.11	18.09 / 17.45	16.17 / 16.75
ENPDA-Solver	24.12 / 60.36	19.38 / 59.56	17.63 / 59.79
ENPDA minus RASCAL (off), 95% CI	$[0.49,1.78]$	$[0.10,0.90]$	$[0.40,1.33]$
ENPDA minus NGA, 95% CI	$[2.90,4.68]$	$[0.98,1.65]$	$[1.07,1.89]$

Appendix

Table 26: Full-cycle comparison details. Each cell reports mean retained bonds / mean supervisor seconds. All output witnesses satisfy the same complete-cycle rule, including when RASCAL internal filtering is off. Difference rows give paired 95% bootstrap intervals for mean bond gains (10,000 pair resamples).

Figure 9: Selected molecular examples from the complete-aromatic-cycle evaluation. Teal bonds form the retained witness; dashed orange bonds are compatible under the same candidate atom map but removed by the output rule; other bonds are gray. Molecular coordinates are fixed across methods. The examples illustrate ring-fragment removal and include an NGA–ENPDA tie; they are not a random sample of test performance. All outputs satisfy the external 60-second cutoff. RASCAL uses its internal ring filter off; ENPDA and NGA use seed 0, with one NGA fit. Counts refer to retained bonds and complete aromatic cycles, not constrained optima.

Stage	Seed 0 s	Seed 1 s	Seed 2 s	Mean GPUh
Reference pretraining	5728.86	5297.39	5381.80	1.5193
Teacher generation	466.28	466.05	441.52	0.1272
Student optimization	696.99	712.68	673.19	0.1929
Setup overhead	0.74	0.83	0.67	0.0002
Complete startup	6892.87	6476.96	6497.19	1.8395

Appendix

Table 27: Complete startup cost of one deployable checkpoint. Per-seed values are synchronized seconds on one H100; the last column is mean allocated GPU-hours. Student timing includes validation. No-price ablation training and test evaluation are not required deployment stages.

Dataset	Prices	Mean gap	Median gap	Closed
AIDS	Zero	27.14	23.26	20/300
AIDS	Analytic	21.19	16.92	23/300
AIDS	Neural	16.67	15.34	31/300
MOLHIV	Zero	23.11	23.08	3/273
MOLHIV	Analytic	20.10	19.23	6/273
MOLHIV	Neural	18.70	18.87	17/273

Appendix

Table 28: Price-only ablation with identical Solver incumbents and row repair. Gaps are percentages, aggregated over three seeds; closed counts are seed–pair records with established optimality.

Dataset	Neural $-$ analytic	Neural $-$ zero
AIDS	-4.51 [-6.78, -1.36]	-10.47 [-14.64, -5.92]
MOLHIV	-1.40 [-2.43, -0.51]	-4.41 [-6.10, -2.92]
MCF-7	-2.59 [-4.11, -1.32]	-7.44 [-10.14, -5.19]

Appendix

Table 29: Paired price-only gap changes (pp), with graph-cluster and paired-seed 95% CIs. Negative differences mean tighter upper bounds.

Dataset	Pairs	Price gap	Closed	Combined gap	Closed
AIDS	100	15.04	11	7.93	28
MOLHIV	91	18.28	5	10.34	10
MCF-7	100	21.85	9	9.84	22

Appendix

Table 30: Seed-0 upper bounds over all native pairs, using the full Solver incumbent. Price repair requires no further search. Combined additionally intersects structural and exact incident-assignment caps; gaps are median percentages.

Figure 10: Seed-0 optimality-gap bounds. Price-only repairs learned prices; combined also uses independent structural and exact incident-assignment caps. Both use the same full Solver lower bound.

Budget s	Dataset	Pairs	Closed	Median gap	Mean gap
10	AIDS	25	5	33.67	28.63
10	MOLHIV	25	1	30.56	31.75
10	MCF-7	25	3	30.30	30.72
10	All	75	9	32.26	30.37
300	AIDS	25	14	0.00	13.81
300	MOLHIV	25	13	0.00	13.48

Appendix

Table 31: Independent lifted bounds compared with the frozen seed-0 Solver incumbent, on 25 fixed pairs per dataset. Bounds form an envelope over the current and smaller budgets. Gaps are percentages; newly discovered search incumbents receive no credit.

Figure 11: Retrieval MAP on identical candidate pools. Bars average three pools. Error bars bound unresolved oracle-label uncertainty. Hard-only results exclude the controlled positive variants.

Dataset	Method	MRR [bounds]	P@10 [bounds]	MAP [bounds]
MOLHIV	Size	0.026 [0.026, 0.026]	0.392 [0.392, 0.402]	0.345 [0.345, 0.356]
MOLHIV	WL	0.375 [0.375, 0.375]	0.980 [0.980, 0.980]	0.704 [0.695, 0.709]
MOLHIV	SimGNN	0.020 [0.020, 0.020]	0.442 [0.442, 0.455]	0.485 [0.484, 0.500]
MOLHIV	GMN	0.152 [0.152, 0.152]	0.688 [0.688, 0.705]	0.569 [0.563, 0.588]
MOLHIV	NeuroMatch	0.233 [0.233, 0.233]	0.763 [0.763, 0.778]	0.657 [0.651, 0.680]
MOLHIV	ENPDA-Fast	0.975 [0.975, 0.975]	0.998 [0.998, 0.998]	0.957 [0.940, 0.962]

Appendix

Table 32: Full-pool retrieval over three independently constructed pools. Entries are point estimates with bounds due to unresolved oracle labels, not confidence intervals. All six methods use identical query/candidate identities.

Dataset	Method	MRR [bounds]	P@10 [bounds]	MAP [bounds]
MOLHIV	Size	0.015 [0.014, 0.026]	0.305 [0.305, 0.325]	0.316 [0.316, 0.329]
MOLHIV	WL	0.414 [0.405, 0.418]	0.842 [0.842, 0.847]	0.630 [0.623, 0.638]
MOLHIV	SimGNN	0.015 [0.015, 0.029]	0.442 [0.442, 0.455]	0.474 [0.473, 0.490]
MOLHIV	GMN	0.146 [0.145, 0.149]	0.632 [0.632, 0.648]	0.537 [0.531, 0.557]
MOLHIV	NeuroMatch	0.147 [0.143, 0.158]	0.665 [0.665, 0.682]	0.606 [0.600, 0.632]
MOLHIV	ENPDA-Fast	0.776 [0.709, 0.788]	0.962 [0.962, 0.970]	0.946 [0.928, 0.954]

Appendix

Table 33: Hard-only retrieval over three independently constructed pools. Entries are point estimates with bounds due to unresolved oracle labels, not confidence intervals. All six methods use identical query/candidate identities.

Dataset	Seed	Timeouts / 10k	Wall s/query	Worker s/query
MOLHIV	0	106	57.78	456.55
MOLHIV	1	222	64.96	513.90
MOLHIV	2	78	65.22	515.30
MCF-7	0	1448	—	974.44
MCF-7	1	1831	132.90	1057.14
MCF-7	2	2060	148.17	1179.59

Appendix

Table 34: Complete-pool retrieval timing: evaluation wall seconds divided by 20 queries is batch throughput at eight workers, not serial-query latency. Worker seconds sum per-pair work. A dash marks an interrupted run whose final marker covers only the resumed suffix.

Graph Matching

Graph matching finds correspondences between nodes and edges to compare, align, or locate related structures in graphs.

See all 35 papers

Mar 18, 2026

Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

Approximate subgraph matching (ASM) is a task that determines the approximate presence of a given query graph in a large target graph. Being an NP-hard problem, ASM is critical in graph analysis with a myriad of applications ranging from database systems and network science to biochemistry and privacy. Existing techniques often employ heuristic search strategies, which cannot fully utilize the graph information, leading to sub-optimal solutions. This paper proposes a Reinforcement Learning based Approximate Subgraph Matching (RL-ASM) algorithm that exploits graph transformers to effectively extract graph representations and RL-based policies for ASM. Our model is built upon the branch-and-bound algorithm that selects one pair of nodes from the two input graphs at a time for potential matches. Instead of using heuristics, we exploit a Graph Transformer architecture to extract feature representations that encode the full graph information. To enhance the training of the RL policy, we use supervised signals to guide our agent in an imitation learning stage. Subsequently, the policy is fine-tuned with the Proximal Policy Optimization (PPO) that optimizes the accumulative long-term rewards over episodes. Extensive experiments on both synthetic and real-world datasets demonstrate that our RL-ASM outperforms existing methods in terms of effectiveness and efficiency. Our source code is available at https://github.com/KaiyangLi1992/RL-ASM.

Kaiyang Li, Shihao Ji, Zhipeng Cai +1

University of Connecticut, 352 Mansfield Road, Storrs, CT 06269, USA · Georgia State University, 33 Gilmer Street SE, Atlanta, GA 30303, USA

RL for Combinatorial Optimization

Ask PDF

Jun 23, 2026

Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index

Spectral filtering recently delivered substantial pruning for static subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate continuous subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained spectral bounds are infeasible exactly where spectral pruning has value: we characterize the tightest safe rule over a formalized perturbation relaxation and show that even it loses essentially all pruning power within four touching updates. Second, exact maintenance is affordable when selective: pruning utility and recomputation cost are anti-correlated across vertices -- hubs provably never prune -- so recomputing small-neighborhood spectra on touch sustains exact local spectra at microseconds per update, complete by construction. Third, integrated into a decoupled CSM benchmark against an identical-minus-spectra control, the tests remove up to

51\%

of candidates or safely skip up to

47\%

of update enumerations, yet enumeration intermediates remain unchanged -- beyond the gates' skipped first-level bindings, typically zero -- across two engines, four real graphs, two stream types, and

77

solved queries; a constructed radius-stratified workload confirms the instrument detects the exception when one exists (

-99.9\%

intermediates,

748\times

faster). Aggregate tests accelerate what scales with candidate sets -- construction, list scans -- never adjacency-guided exploration. We distill an intermediate-invariance methodology for evaluating CSM filters and release a reusable dynamic local-spectra index.

Minghao Chen, Jiale Zheng

Tencent Technology Shenzhen, China · HUAWEI Noah’s Ark Lab Shenzhen, China

Graph Matching Spectral Methods

Ask PDF

May 7, 2026

Towards Metric-Faithful Neural Graph Matching

Graph Edit Distance (GED) is a fundamental, albeit NP-hard, metric for structural graph similarity. Recent neural graph matching architectures approximate GED by first encoding graphs with a Graph Neural Network (GNN) and then applying either a graph-level regression head or a matching-based alignment module. Despite substantial architectural progress, the role of encoder geometry in neural GED estimation remains poorly understood. In this paper, we develop a theoretical framework that connects encoder geometry to GED estimation quality for two broad classes of neural GED estimators: graph similarity predictors and alignment-based methods. On fixed graph collections, where the doubly-stochastic metric

d_{\mathrm{DS}}

is comparable to GED, we show that graph-level bi-Lipschitz encoders yield controlled GED surrogates and improved ranking stability; for matching-based estimators, node-level bi-Lipschitz geometry propagates to encoder-induced alignment costs and the resulting optimized alignment objective. We instantiate this perspective using FSW-GNN, a bi-Lipschitz WL-equivalent encoder, as a drop-in replacement in representative neural GED architectures. Across representative baselines and benchmark datasets, the resulting geometry-aware variants significantly improve GED prediction and ranking metrics. A faithfulness case study of untrained encoders, together with ablations and transfer experiments, supports the view that these gains arise from improved representation geometry, positioning encoder geometry as a useful design principle for neural graph matching.

Jyotirmaya Shivottam, Subhankar Mishra

1National Institute of Science Education and Research (NISER), Bhubaneswar, India · 2Homi Bhabha National Institute, Mumbai, India

Graph Neural Networks Neural Representation Geometry Graph Matching

Ask PDF

Abstract

Graph Matching

Explore similar work

Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index

Towards Metric-Faithful Neural Graph Matching