PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-Classical Link Prediction on Dark Web Hyperlink Graphs

Vojtěch Novák, Radovan Rečka, Ondřej Knebl, Aktham Youssef, Ivan Zelinka

arXiv:2610.32510v1cs.NIcs.LG

TL;DR

Link prediction on crawled Tor graphs can be strongly affected by endpoint degree, so the study evaluates withheld hyperlinks with degree-matched negatives and compares graph, content, and quantum–classical models. It finds predictive signal in combined graph and content features, while the compact VQCs remain close to matched classical controls and do not establish a general quantum advantage.

  • Problem

    Endpoint-degree differences can inflate link-prediction scores when positive and negative examples have different degree distributions, motivating evaluation with degree-matched negatives.

    Source: §1 · p. 2

  • Method

    The study combines semantic analysis with degree-controlled link prediction and compares compact VQCs with classical models using matched inputs, training data, and evaluation conditions.

    Source: §1 · p. 2

  • Results

    Under disjoint-pair evaluation, multimodal logistic regression reaches about 0.672, GAE about 0.899, and VGAE about 0.906 ROC-AUC; best exact VQC mean AUC is about 0.549 versus 0.551 for matched RBF SVC and 0.573 for a 16-parameter MLP.

    Source: §5 · p. 11

  • Takeaways & Limitations

    The results support predictive signal in combined graph/content features after degree control, while the quantum–classical benchmark does not establish a general quantum advantage.

    Source: §5 · p. 11

    Repeated holdouts of one graph quantify split variation rather than generalization across crawls, and the quantum models use strongly compressed features, small training subsets, and shallow circuits.

    Source: Limitations · p. 10

Abstract

from arXiv · show

We analyze HTML content and hyperlinks from an offline Tor crawl containing 383 onion hosts and 2,067 directed cross-host links. The study combines semantic analysis with degree-controlled quantum--classical link prediction. Two directory groups emit 94.8\% of the observed host links. Directed preferential attachment reaches ROC-AUC 0.976 with random non-edges, but falls to $0.550\pm0.014$ under source-conditioned target-degree matching. With disjoint training and test pairs, multimodal logistic regression reaches $0.672\pm0.021$, GAE $0.899\pm0.016$, and VGAE $0.906\pm0.016$. A four-qubit variational quantum classifier (VQC) comparison tests two encodings across 20 disjoint-pair graph splits under exact and 1,024-shot simulation, with classical controls using the same inputs and training examples. Its best exact mean ROC-AUC is $0.549\pm0.023$, compared with $0.551\pm0.016$ for RBF SVC and $0.573\pm0.029$ for a 16-parameter MLP on the same inputs and training examples. These results support predictive signal in combined graph/content features and show why degree control, feature compression, and optimization conditions matter in quantum--classical comparisons.

1 Introduction

The study asks whether graph and content features predict withheld Tor hyperlinks when evaluation controls for endpoint degree. It combines crawl-content analysis with a degree-controlled link-prediction benchmark and matched quantum–classical comparisons.

1 Introduction

  • Prior Tor studies examined connectivity, content categories, community structure, and influential domains, while this study tests prediction of withheld links under reduced degree advantage.The related work includes Tor connectivity and directories, topic and hyperlink analysis [6], and ToRank.Source: §1 · p. 1
  • Because verified malware, activity, or service labels are unavailable, observed hyperlinks define the study’s self-supervised prediction targets.Prior supervised studies used activity labels or manually ranked services.Source: §1 · p. 2
  • Degree-matched negatives address how endpoint-degree differences can inflate link-prediction scores, a concern especially relevant to crawled graphs with hubs and directories.The study measures this bias directly and uses degree-matched negatives for its main comparison.Source: §1 · p. 2
  • Quantum feature maps introduce nonlinear interactions, but compact circuits require compressing graph and content features; matched classical controls test what signal the circuits retain.The comparison also examines encoding, optimization, and finite-shot measurement.Source: §1 · p. 2
  • The benchmark uses a directory-dominated Tor graph, disjoint training and test pairs, and classical controls sharing the quantum models’ inputs and training data.Additional comparisons account for parameter count and optimization budget.Source: §1 · p. 2
  • The study combines semantic analysis of the crawl with degree-controlled link prediction, evaluating content and graph models on withheld links and comparing compact VQCs with classical controls.The comparisons account for input representation, training data, parameter count, and optimization.Source: §1 · p. 2

2 Methods

The methods construct host-level graph and content representations from an offline Tor crawl, then evaluate withheld hyperlinks with disjoint pairs and degree-matched negatives. The quantum comparison uses compressed pair features and matched classical controls across graph splits.

2.1 Data and content analysis

  • The crawl analysis induces a 383-host graph with 2,067 distinct directed cross-host edges after collapsing pages by hostname and removing within-host links.The analyzed page-level graph contains 998 pages and 13,515 directed page-level hyperlinks.Source: §2.1 · p. 2, Table 1 · p. 3
  • Offline HTML processing creates three text views, embeds host text with 32-dimensional TF–IDF/SVD features, and uses static HTML counts descriptively because malware ground truth is unavailable.The views differ in boilerplate and token porn removal.Source: §2.1 · p. 2
  • Content-to-community agreement is assessed by comparing seven Louvain communities with k-means partitions, while an exploratory semantic partition uses cleaned text and k-means over 4–12 clusters.The exploratory partition uses 64-dimensional SVD features and selects descriptive groups at k = 12, the tested range’s upper boundary.Source: §2.1 · p. 3

2.2 Link-prediction evaluation

  • Testing withholds about 20% of eligible undirected host dyads while protecting a spanning tree; both directions of a held-out dyad are removed to prevent reverse-edge leakage.The experiment is transductive: hosts remain known while edges are withheld.Source: §2.2 · p. 3
  • Primary negatives keep each positive’s source and match the absent target’s training in-degree, with reserved test negatives disjoint from training pairs.When a source exhausts unique non-edge targets, training negatives use directed degree-corrected sampling as a fallback.Source: §2.2 · p. 3
  • The benchmark evaluates degree, graph, content, and multimodal logistic-regression features alongside directed GAE/VGAE models, reporting ROC-AUC and average precision over 20 primary splits.Filtered all-target ranking is also reported for preferential attachment, multimodal logistic regression, and GAE/VGAE refits.Source: §2.2 · pp. 3–4

2.3 Quantum comparison and resource accounting

  • Pair features are standardized and PCA-reduced using training data; the primary quantum comparison uses four inputs from clean eight-component exports across 20 splits.The primary circuits test product Ry and one-repetition linear ZZ encodings; exact probabilities and 1,024-shot parity sampling are compared under a 200-function-evaluation limit.Source: §2.3 · p. 4
  • Classical controls share the quantum comparison’s four inputs, preprocessing, training draws, and test pairs, including a 16-parameter MLP trained with both gradient-free and L-BFGS methods.A supplementary optimizer study uses a fixed dataset and supports only within-dataset comparisons because 4.9% of evaluation negatives recur in training on average.Source: §2.3 · pp. 4–5

3 Results

The results characterize a directory-dominated host graph and show that degree control substantially changes heuristic scores. Under disjoint-pair tests, graph autoencoders lead the primary benchmark, while four-qubit VQCs remain close to matched classical controls.

Observed graph and semantic structure.

  • At seven clusters, boilerplate cleaning raises NMI from 0.126 to 0.175 and AMI from 0.096 to 0.145, while ARI stays close to zero.The exploratory semantic partition labels sampled pages in groups including drug storefronts, OnionMail, and Tor search and navigation directories; supervised activity labels were unavailable.Source: Observed graph and semantic structure · p. 5
  • The two directory groups emit 1,959 of 2,067 distinct directed host links (94.8%), while several specialized groups have no observed outgoing cross-host weight.The 47-host search/link-directory group keeps 6.4% of outgoing hyperlink weight within its group; the navigation-directory group keeps none.Source: Observed graph and semantic structure · p. 5

Degree bias in sampled link prediction.

Models under degree control.

Quantum comparison.

  • With all four inputs and 16 parameters active, the best exact VQC mean AUC is 0.549, close to RBF SVC at 0.551 and below the 16-parameter MLP’s 0.573.On the same clean four-component inputs and 256 training examples, RBF SVC scores 0.551 ± 0.016 ROC-AUC and the L-BFGS-trained 16-parameter MLP scores 0.573 ± 0.029.Source: Quantum comparison · pp. 8–9

4 Discussion

The discussion interprets link-prediction performance through degree bias, directory-centered structure, and complementary content and topology. It also shows that quantum-classical comparisons depend on compression and optimization, within a crawl and evaluation setting with explicit scope limits.

Graph structure and domain interpretation.

  • Random and conventional hard negatives create a large degree mismatch that makes preferential attachment appear nearly perfect; source-conditioned target-degree matching reduces this shortcut, while multimodal GAE/VGAE retain signal on disjoint training and test pairs.Capacity-matched encoders without message passing reproduce sampled-pair AUC (about 0.900) but have lower MRR (0.157/0.152) than GAE/VGAE refits.Source: Graph structure and domain… · p. 9
  • Directory and search services link outward across content groups, while many specialized services are mainly destinations, helping explain weak agreement between semantic clusters and Louvain communities.Content and topology describe different aspects of the crawl; the observed asymmetry is consistent with sparse linking and directory-centered structure reported in earlier crawls [5].Source: Graph structure and domain… · p. 10

Classical and quantum comparison.

  • Exact ZZ–COBYLA fits reached mean training AUC 0.717 versus 0.549 held out; four-qubit circuits stayed close to matched RBF control and below the mean parameter-matched MLP trained by L-BFGS.The tested ZZ features gave a modest benefit at the cost of six additional CNOTs. Under shot-based training, exact held-out mean AUC fell to 0.531; resampling exact-fit predictions gave AUC SD about 0.003.Source: Classical and quantum comparison · p. 10

Limitations.

  • The crawl is a connected BFS component, so seed choice and traversal affect observed degree and content distributions; repeated holdouts measure split variation, not generalization across crawls.Temporal forecasting would require repeated snapshots, and the GAE/VGAE setting is transductive; semantic groups are exploratory and do not provide verified activity classes or prevalence estimates.Source: Limitations · p. 10

5 Conclusion

The conclusion describes directory/search groups as gateways in the observed crawl and reports predictive signal in combined graph/content features after degree control. The quantum comparison places the tested VQCs near the matched RBF control and below the gradient-trained MLP, without establishing general quantum advantage.

5 Conclusion

  • Directory/search groups act as outward gateways across content groups, while content and topology show weak community agreement and are treated as complementary views.The crawl analysis covers 383 hosts and 2,067 directed cross-host links.Source: §5 · p. 10
  • 0.976 ROC-AUC for directed preferential attachment with random non-edges falls to 0.550 after source-conditioned degree matching; under disjoint-pair evaluation, logistic regression, GAE, and VGAE reach 0.672, 0.899, and 0.906 ROC-AUC.The controlled test pairs match source out-degree and target in-degree.Source: §5 · p. 11
  • The best exact VQC mean AUC is about 0.549, near the matched RBF control at 0.551 and below the 16-parameter gradient-trained MLP at 0.573.The comparison comprises 320 four-qubit fits across 20 disjoint-pair graph splits under exact and finite-shot simulation.Source: §5 · p. 11

Data and ethics statement

The statement flags potentially sensitive or illicitly advertised content and describes how reporting and interpretation are bounded. Aggregate reporting avoids publishing onion addresses, while semantic labels and static HTML indicators are not claims of malicious behavior.

Data and ethics statement

  • The dataset may contain sensitive or illicitly advertised content, so results are reported at aggregate level and onion addresses are not published.Source: Data and ethics statement · p. 11
  • Semantic labels summarize unsupervised groups, and static HTML indicators are not used to claim malicious behavior.Source: Data and ethics statement · p. 11

Related papers

Loading 2610.32510v1…