Tolerance-Aware Ranking for Retrieval of Graphs with Continuous Attributes

Chemists searching a molecule database rarely want "the same graph." They want candidates that share a large piece of the query's structure and whose atoms along that shared piece also agree in their real-valued properties, such as partial charge or inter-atomic distance, to within a tolerance the chemist chooses. Neural graph retrieval models already learn to rank database graphs by how much structure they share with a query. The strongest of them, however, ignore continuous attributes entirely, and they are trained to regress similarity scores rather than to get the ordering right. Methods that do handle continuous attributes well are graph kernels built for classification, and they have no notion of a user-chosen tolerance.

We propose a retrieval model that ranks attributed graphs by a tolerance-dependent common-substructure score and is built on three pieces. First, it matches nodes with a smooth, tolerance-conditioned gate on attribute distance instead of binning the attributes. Second, it takes the tolerance as an input at query time, so a single trained model serves strict and loose searches. Third, it is trained with a pairwise ranking loss whose margin is proportional to the gap between the true scores of the two candidates. The claim is that this model ranks better than the same architecture trained with regression, better than models that bin the attributes, and better than non-learned continuous-attribute kernels. We also claim its advantage grows exactly where the other methods should break: near bin boundaries, and when most of the database is irrelevant.

Core Claim and What Is New

The closest existing work is Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks. It ranks database graphs by approximate maximum common subgraph size. To do so it builds a soft one-to-one node alignment with Gumbel-Sinkhorn, a differentiable relaxation of a permutation matrix. It evaluates with Kendall's tau, a rank correlation, but trains with mean squared error against true subgraph counts, and its authors state as a limitation that it "focuses heavily on structure" and should "better incorporate complex node and edge attributes." Our work supplies the method it leaves open, and it changes both the relevance definition and the training objective.

We define relevance as tolerance-constrained maximum common edge subgraph, written $r_\epsilon(q, g)$. This is the largest number of edges preserved under a one-to-one node map from query $q$ to candidate $g$, where mapped nodes must share a discrete type and differ in continuous attributes by at most $\epsilon$. For graphs with distance matrices such as BZR-MD, mapped edges must also differ in length by at most $\epsilon$. This target is combinatorial and depends on $\epsilon$ in a thresholded way. A fixed continuous similarity such as a Wasserstein distance between node sets cannot reproduce it, which is what keeps the problem from reducing to an existing kernel.

The model scores node pairs inside the alignment. Each pair's score is a learned structural affinity multiplied by a soft gate:

$$\sigma\big((\epsilon - \lVert a_u - a_v \rVert)/\tau\big).$$

Here $a_u, a_v$ are the continuous attributes of query node $u$ and candidate node $v$, $\epsilon$ is the query tolerance, $\tau$ is a learned temperature, and $\sigma$ is the logistic function. The model is trained with a relevance-scaled pairwise hinge loss:

$$\mathcal{L} = \sum_{q}\sum_{i,j:\, r_\epsilon(q,g_i) > r_\epsilon(q,g_j)} \max\big(0,\; \gamma\,[r_\epsilon(q,g_i) - r_\epsilon(q,g_j)] - [s(q,g_i) - s(q,g_j)]\big).$$

In this loss, $s$ is the model's score and $\gamma$ converts relevance gaps into score margins. The margin idea comes from Graph Attention Collaborative Similarity Embedding for Recommender System. That paper makes BPR margins adaptive using discrete topological overlap and reports that removing the adaptive margin costs up to 15%. We ground the margin in the continuous, tolerance-dependent target itself rather than in item co-occurrence.

Research Program

The first step is building ground truth. For COX2, PTC, MSRC-21 and DD we reuse the retrieval splits of the subgraph retrieval paper, and we add BZR and BZR-MD for their charges and 3D distances. For each query–candidate pair we compute $r_\epsilon$ at five tolerances with an exact integer-program solver under a time limit. Pairs that hit the limit are logged and excluded, and we report the resulting coverage. The molecules are small enough (tens of nodes) that offline computation is feasible, but we treat solver cost as a real risk. If coverage falls below roughly 90% on a dataset, we drop that dataset rather than train on bounds.

The second step is the model. We extend both the late-interaction design, which embeds each graph separately, and the early-interaction design, which aligns during message passing. We add the tolerance gate to the alignment cost and feed $\epsilon$ as a scalar input to the node encoders.

The third step is training. We use the loss above, with negatives drawn preferentially from candidates whose relevance is close to the positive's. This follows the lesson from Attribute-Enhanced Similarity Ranking for Sparse Link Prediction that uniform negatives are uninformative when relevant items are rare. Gelato obtains hard negatives with graph partitioning; we obtain them from the known relevance scores.

The analysis asks where each ingredient matters. We stratify errors by how far the attribute differences in the true optimal alignment lie from $\epsilon$. We also stratify by the fraction of the database with $r_\epsilon = 0$, which is where regression should waste capacity. The "pointwise mismatch" argument of Neural Collaborative Filtering predicts that waste, and Revisting Node Affinity Prediction In Temporal Graphs observed a related failure when cross-entropy replaced a ranking loss.

Baselines

The naive reference point uses the unmodified structure-only early-interaction model from the subgraph retrieval paper. It is trained on attribute-free maximum common subgraph targets and evaluated against $r_\epsilon$. Beating it only shows that attributes matter at all, which is the minimum bar.

The strongest existing competitor is the same early-interaction network retrained with mean squared error on $r_\epsilon$ and given the continuous attributes as extra node features. This is exactly what that paper's authors would do next. It shares our alignment machinery, so any gain isolates the gate and the loss. We run it with the same encoder width, the same number of epochs and an equal hyperparameter search budget, which we fix at 30 configurations per method on the validation queries. For its performance on this task there is no reported result found on Lacuna. The paper reports Kendall's tau for structure-only targets, but the file gives no per-dataset numbers, only that XMCS is "3x faster than GMN while being more accurate." We will rerun it ourselves. Beating it means higher Kendall's tau and higher NDCG@10 averaged over five seeds, with non-overlapping 95% bootstrap intervals over queries, on at least four of the six datasets.

The strongest non-learned continuous baseline ranks candidates by the distance from Wasserstein Weisfeiler-Lehman Graph Kernels.. That kernel averages attributes over neighborhoods and compares the resulting node sets with earth mover's distance. It reports 84.42% classification accuracy on BZR and 78.29% on COX2, which are classification numbers rather than retrieval numbers. We also run GraphHopper from Scalable kernels for graphs with continuous attributes, which compares attributes along shortest paths. For both, we tune the kernel's width, depth and λ per tolerance on validation queries, which gives them a tuning advantage we accept.

A binning baseline quantizes attributes into bins of width $\epsilon$ and feeds the resulting discrete labels to the structure-only model. We run it with randomly shifted bins averaged over several shifts, in the spirit of Faster Kernels for Graphs with Continuous Attributes via Hashing.

Three ablations isolate the key ingredients: a constant margin in place of the relevance-scaled one, a hard 0/1 gate, and separate models trained per $\epsilon$ in place of one tolerance-conditioned model. We also include a listwise variant using LambdaLoss, as in NAVIS.

Why not just…?

Why not just regress the relevance score with mean squared error, as the retrieval paper already does? This is the most serious alternative, because it is simple and uses a target that already contains the ordering. The evidence against it comes from other settings. Gelato reports 138% and 125% Hits@1000 gains on CORA and CITESEER when ranking losses and realistic negatives replace classification-style training. NAVIS reports a +12.8% gain on tgbn-trade over TGNv2 after switching to ranking losses. Neither result is on graph retrieval. Our stratified analysis tests the mechanism directly: if regression's deficit is concentrated at the top of the list and grows with the fraction of irrelevant candidates, the argument holds. If the deficit is flat or absent, we will report that regression suffices for this task.

Why not just bin the attributes and reuse a discrete model? In classification, binning has failed badly when fine attribute differences matter. GraphHopper reports 86.6% on its SYNTHETIC benchmark against 46.1% for the discretized PROP-diff and 43.3% for WL. Single-pass hashing reached about 50% on SYNTHIE while multi-iteration hashing reached about 96.7%, which shows that averaging over hashes recovers much of the loss. The shifted-bin baseline gives binning that best case. We predict binning errors will spike specifically when true attribute differences fall within a small fraction of $\epsilon$ of the threshold, and our tolerance sweep measures exactly that.

Why not just rank by a Wasserstein or GraphHopper distance with no training? This is a genuine threat on datasets where shared substructure is small and attribute distributions alone separate candidates. Earth mover's distance between node sets does not enforce a connected, edge-preserving one-to-one map, and it changes smoothly rather than with a threshold in $\epsilon$. Those properties should matter most at small tolerances and on the larger DD graphs. If the kernel matches our model at every tolerance, the conclusion is that a learned alignment adds nothing here, and we would report it that way.

Why not a listwise loss over the whole candidate list? From Pairwise to Ranking: Climbing the Ladder to Ideal Collaborative Filtering with Pseudo-Ranking finds listwise training degrades beyond lists of about 4–5 synthetic ranks. Our lists are real and graded, though, so that failure may not transfer. The LambdaLoss variant tests this directly, and if it wins we adopt it.

Decisive Checks

We evaluate with Kendall's tau per query and NDCG@10, plus precision@10 at each of the five tolerances. We report latency per query against the kernel baselines, because hashing methods show large speed gaps between approaches (about 197 seconds against over 16,000 on FRANKENSTEIN).

The proposal succeeds if three things hold. First, the relevance-scaled pairwise model beats the retrained regression network on most datasets. Second, the constant-margin ablation loses a measurable part of that gain. Third, a single tolerance-conditioned model stays within noise of per-tolerance models, including at a held-out tolerance between the trained values.

The decisive failure signatures are as follows. If the Wasserstein ranking ties our model, attributes are being handled well enough without learned alignment. If regression ties it, the loss is not the bottleneck. If binning ties it even near thresholds, smooth gating is unnecessary. Each outcome would redirect the work, and each is measured directly.