{"id":"3f173bba-1473-4e33-b02d-3ad0cd00c8c9","arxiv_id":"2411.11149","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A prime-number encoding of multi-relational graphs is extended with a lossless k-hop chaining algorithm and a Bag of Paths feature method that matches or beats GNN baselines on several benchmarks.","lead":"The paper encodes each relation type in a multi-relational graph as a prime number, so a single matrix entry can store all relations between two nodes as a product. It then defines a lossless k-hop version of this encoding and a feature extraction scheme called Bag of Paths, and shows simple classifiers on those features are competitive with graph neural networks on several benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Relation prediction results in Table 4 may leak test edges: Section 3.2 builds P from an unspecified graph; if test triples are included, the 1-hop PAM already encodes the ground-truth relation.","rationale":"The reader's verdict correctly identifies the relation-prediction masking protocol as the pivotal uncertainty. The whole empirical case for the lossless algorithm (the paper's central new contribution) rests on Table 4, and that table is only meaningful if the graph used to compute the 1-hop PAM excludes the test edge. The paper's silence on this point is not a minor omission: because P[h,t] directly contains the prime for any relation present between h and t, including the test edge in P makes the task almost trivial for a 1-hop BoP feature. I agree with the reader's assessment. I also checked for other weaknesses: the lossless algorithm's proof in Appendix B is structurally sound under the stated assumptions (distinct primes per path, factorization), though it inherits a factorial blowup in |R|^k that the authors acknowledge; the BoP tokenization (Eq. 10) collects whole cell values rather than individual path primes, which makes the 'each feature is a single path' claim in Section 2.6 inaccurate for cells containing multiple paths, but this is a presentational issue that does not invalidate the empirical comparisons. The node classification and graph regression tasks do not use the lossless variant, so they are unaffected by the masking concern; however, they also lack error bars, as the reader notes. Overall, the central load-bearing concern remains the leakage ambiguity, which a simple code inspection can settle. No change to the reader's CONDITIONAL verdict is warranted.","tokens_in":23869,"tokens_out":10188,"duration_ms":93159,"concrete_test":"Inspect the released code (github.com/kbogas/PAM BoP) for the relation prediction data preparation: verify whether the adjacency matrix P is constructed only from Etrain, or whether test/validation triples are included. Then rerun the BoP (lossless) model on WN18RR with a version of P built only from Etrain and compare MRR/Hit@3 to Table 4. If the results drop materially (e.g., by more than 5 points), the reported numbers reflect leakage; if they are unchanged, the masking was already correct.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing concern is the masking protocol for the relation prediction experiments in Section 3.2. The paper states that evaluation follows Wang et al. (2021), but it never states whether the graph G used to build P (and its powers P^k) is the training graph (Etrain only) or the full graph including validation/test triples. In Appendix C.2, the BoP feature for a test pair (h,t) is F(h,t) = concatenation of P^n[h,t] for n=1..k (Eq. 29). If P is built from the full graph, then for a test triple (h,r,t), the entry P[h,t] contains the prime φ(r) assigned to relation r (Eq. 2). A k-NN classifier over such features can trivially rank r first or near-first, making the MRR/Hit@3 values in Table 4 reflect leakage rather than path-based reasoning. The same ambiguity affects the validation-based hyperparameter selection in Table 9, since validation triples must also be held out of the graph during selection to avoid optimistic k and N. Because the lossless BoP variant is the paper's flagship empirical contribution, this unstated protocol decision is the single most load-bearing point: if the mask is absent, Table 4's headline numbers are invalid; if it is present, the paper simply needs to say so explicitly.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the Prime Adjacency Matrix (PAM) framework for multi-relational graphs in three ways: a lossless algorithm for computing k-hop matrices whose nonzero cells encode relational chains as products of path-primes, a Bag of Paths (BoP) feature extraction methodology producing tf-idf-weighted histograms of path values at node, edge, and graph level, and a GraphBLAS implementation with reported speedups. The BoP features are evaluated with simple classifiers (CatBoost, k-NN) on node classification (AIFB, MUTAG, BGS, AM), relation prediction (WN18RR, NELL995, DDB14), and graph regression (ZINC, AQSOL, Peptides-struct), claiming performance comparable to or better than several neural baselines while using CPU only and no trainable parameters.","tokens_in":24095,"tokens_out":6109,"duration_ms":54456,"significance":"If the evaluations are valid, the paper offers a fast, interpretable, CPU-only alternative to trained GNNs for several graph-analysis tasks, with the notable strengths that the lossless construction is simple and correct for relational chains, the code is released, and the interpretability analysis (e.g., Table 6) is concrete and falsifiable. The lossless property is essentially built into the definition via the Fundamental Theorem of Arithmetic, but that is a sound construction rather than a damaging circularity. The main weaknesses are empirical: the relation-prediction protocol leaves open a possible leakage of test edges into the PAM construction, and the headline tables lack error bars, so the strength of the empirical claims is not yet fully established.","major_comments":[{"comment":"The paper nowhere states whether the graph G used to build P and P^k includes the validation and test triples. Since the pair feature F(h,t) concatenates P^n[h,t] for n=1..k (Eq. 29), a test triple (h,r,t) present in G makes P[h,t] = phi(r), so a k-NN over these features can rank r trivially. This would invalidate the MRR and Hit@3 numbers in Table 4 and also the hyperparameter selection in Table 9. Please state explicitly that P and P^k are built from the training edges only, with validation and test edges masked before any PAM computation; if that is not the case, the experiments must be rerun with the held-out edges removed.","section":"Section 3.2 / Appendix C.2, Eq. (29)"},{"comment":"The lossless claim is for relational chains (sequences of relation types), not for node-level paths. In the Aggregation Process, phi_k maps a path to a prime based only on the relation sequence (r1,...,rk), and the cell value P^k[i,j] does not encode the intermediate node identities. Consequently, two node-level paths that share the same relation chain are represented by the same prime with multiplicity, and the nodes visited cannot be recovered from the matrix value. This is internally consistent with the paper's own definition of 'path' in Eq. (4), but the abstract and several later passages say 'paths' without this qualification. Please revise the wording to 'relational chains' consistently, or explain how intermediate nodes are recovered.","section":"Section 2.5, Eq. (6), footnote 3"},{"comment":"The empirical comparisons are reported without any measure of uncertainty. Table 2 reports averages over 5 runs, Table 5 averages over 4 runs, and Table 4 gives single numbers, while several margins are small (e.g., BoP lossless 0.874 vs DistMult 0.847 on WN18RR MRR; BoP 92.22 vs R-GCN 95.83 on AIFB). Without standard deviations, confidence intervals, or seed counts, the claims of 'outperforms' and 'competitive performance' are hard to assess. Please report variance information for all three tables.","section":"Tables 2, 4, 5"},{"comment":"The default BoP variant uses P+ (Eq. 3), whose powers are sums of products of relation primes, so a cell value such as 24 in the running example does not have a unique prime factorization into a path multiset. This limits the 'interpretable by design' claim for the default variant: a feature value cannot in general be uniquely traced back to a set of relational chains without additional computation. Please either restrict the interpretability guarantee to the lossless variant and to the targeted path-extraction procedure described in Section 2.5, or explain how the default variant resolves the ambiguity in feature-to-path mapping.","section":"Section 2.4 / Section 2.6 / Table 6"}],"minor_comments":[{"comment":"The ZINC training-set size is printed as '1,0000', which appears to be a typo for 10,000.","section":"Table 5"},{"comment":"The visual layout of the AP/CP steps is dense and the notation is hard to follow; in particular, Algorithm 1 line 4 passes the product Pk[i,nc] * P[nc,j] to ChainingProcess, and the reader must infer that both operands are lossless products and that factorization precedes concatenation. Renaming the variable or adding a comment would clarify this.","section":"Figure 3 and Algorithm 1"},{"comment":"The paper says the evaluation follows Wang et al. (2021) but does not specify the candidate-ranking protocol, e.g., whether inverse triples are filtered out or whether all relations are candidates for every (h,t) pair. Please state this explicitly.","section":"Section 3.2"},{"comment":"The claim that the BoP model 'takes less than a minute on average across all datasets' should state whether this includes P^k construction, feature extraction, tf-idf computation, and hyperparameter selection.","section":"Section 3.1"},{"comment":"The tf-idf pre-filtering rules (skip paths in fewer than 2 nodes, skip paths in more than 99% of nodes) are applied to node features; it would be useful to state whether analogous filters are applied to edge and graph features.","section":"Appendix C.1"}],"recommendation":"major_revision","confidential_remarks":"The relation-prediction masking question in Section 3.2 is the single most important issue: if the target and validation edges are not masked before building P and P^k, Table 4 is invalid. If they are masked, the paper needs to say so explicitly; I would accept that correction. The lack of error bars is a second issue that should be fixed before publication. The paper's fits the journal's scope well, and the lossless construction is sound for the restricted notion of relational chains."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid extension of the authors' existing PAM framework, with a mathematically correct lossless k-hop algorithm and a simple, fast feature representation. The paper deserves a proper refereeing, but the relation prediction section needs one explicit sentence before the numbers mean anything.\n\nWhat's new: the lossless chaining/aggregation procedure in Section 2.5 is real. It computes P^k cells as products of primes assigned to k-hop relational chains, so factorization recovers the exact multiset of chains (with multiplicity) between a node pair. That is a genuine improvement over the lossy P+ matrix powers. The BoP representation is straightforward — collect non-zero PAM cells, tf-idf them, feed to CatBoost/k-NN — and the paper shows it is competitive on node classification, relation prediction, and graph regression, in minutes on CPU. The GraphBLAS speedups in Appendix A are also useful. Credit where due: the authors are honest that the lossless version is too slow for large graphs and that they are not claiming state of the art.\n\nSoft spots. Most important: the relation prediction protocol. Section 3.2 says evaluation follows Wang et al. (2021), but never states whether the graph used to build P (and P^k) is the training graph only. If test triples are in the graph, then for a test pair (h,t) the 1-hop cell P[h,t] already contains the prime for the ground-truth relation, and the k-NN has a trivial leaked feature. Table 4's MRR/H@3 would be invalid. I think the authors probably built P from Etrain, but 'probably' is not good enough for a flagship empirical claim. They need to state the masking rule and make sure validation triples are equally held out during hyperparameter selection. Second, Tables 2, 4, and 5 report averages without spread. Some of the differences (Peptides-struct 0.250 vs 0.253) are within noise; without error bars the comparison with GNNs is under-evidenced. Third, the 'lossless' claim is scoped to relation chains, not node-level paths. The paper says that, mostly, but should be explicit in the abstract and contributions, because 'path' usually includes intermediate nodes. Fourth, BoP features are literally non-zero cell values, which in multi-path cells are products of path primes, not individual paths. The interpretability story holds for single-path cells, but the 'each feature is a path' statement is too strong in general.\n\nWho it's for: practitioners who want a fast, CPU-only, interpretable alternative to GNNs, and researchers working on graph kernels/path features. The math checks out, the code is available. It deserves a serious referee, and conditional acceptance after the masking question is answered.","headline":"Solid extension of the PAM framework with a correct lossless k-hop algorithm; the relation prediction protocol needs a clear masking statement before Table 4 can be trusted.","tokens_in":24699,"tokens_out":6073,"would_cite":true,"duration_ms":59106,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Prime-coded paths let simple models match or beat graph neural networks on three graph tasks.","keywords":["multi-relational graphs","prime adjacency matrices","bag of paths","knowledge graphs","node classification","relation prediction","graph regression","interpretable path features"],"falsifier":"Rerun the relation-prediction experiments with every test triple's edge removed from the graph before $P$ and $P^k$ are computed; if MRR or Hit@3 drops materially, the reported numbers depended on the target edge being present in the path matrices.","tokens_in":23596,"feed_emoji":"🔗","tokens_out":9613,"duration_ms":84201,"temperature":0.7,"pith_summary":"The paper claims that a multi-relational graph can be compressed into one adjacency matrix whose entries are products of prime numbers, one prime per relation type, and that powers of this matrix track all multi-hop relational chains. It adds a lossless algorithm that builds $P^k$ so that each non-zero cell factorises back into the exact set of $k$-hop paths between the two nodes, and a Bag of Paths feature representation that turns those values into interpretable histograms for nodes, edges, and whole graphs. With these features, an out-of-the-box tree classifier or a nearest-neighbor model matches or beats trained graph neural networks on node classification, relation prediction, and graph regression benchmarks, while running on CPU in minutes and using no trainable parameters. A reader should care because the same feature can be read two ways: as a number in a matrix and, by prime factorisation, as a specific relational chain, which makes the model's decisions inspectable.","feed_headline":"Prime-number paths rival or beat graph neural nets","feed_subtitle":"CPU-only histograms of factored path values match or outperform trained models on node, edge, and graph tasks.","key_machinery":"The central object is the Prime Adjacency Matrix (PAM), an $N\\times N$ matrix in which entry $P[i,j]$ is the product (or, in the lossy variant, the sum) of the primes assigned to the relations on the edge $i\\to j$; unique prime factorisation lets the entry record exactly which relations occur. The lossless $k$-hop extension replaces matrix multiplication's multiply-and-add with a chaining step (factorise the $k$-hop value and the final 1-hop value, map primes back to paths, concatenate them) and an aggregation step (map each distinct path to a new prime and multiply), so $P^k[i,j]$ factorises into the exact multiset of $k$-hop paths between the two nodes. The Bag of Paths (BoP) representation then concatenates the non-zero entries of $P^1,\\dots,P^k$ for the cells relevant to a node, an edge, or a graph, applies tf-idf weighting, and feeds the resulting histogram to a simple classifier or regressor.","core_discovery":"On the paper's own terms, the central discovery is that the ordinary matrix-power operation, which loses information when entries are products or sums, can be replaced by a two-step lossless pipeline: chain a $k$-hop path with a final 1-hop relation by factorising the two matrix entries, recovering the paths, and concatenating them; then aggregate the resulting collection of $(k+1)$-hop paths by assigning each distinct path a fresh prime and multiplying those primes. The Fundamental Theorem of Arithmetic guarantees that the resulting cell value decomposes uniquely, so $P^{k+1}[i,j]$ is exactly the multiset of $(k+1)$-hop relational chains from $i$ to $j$. Built on this, the Bag of Paths features—concatenated non-zero entries from $P^1,\\dots,P^k$ with tf-idf weighting—let simple, parameter-free predictors match or beat neural baselines in the reported experiments, and any important feature can be factored back into the underlying path.","pith_inferences":["An implication the paper leaves implicit is that the default sum-based powers are lossy: distinct path multisets can collide to the same numeric value, so deployments that need exact path counts should use the lossless algorithm and accept its higher runtime.","Because BoP features are just histograms over path symbols, the same feature vectors could be fed to other classifiers, and ablating tf-idf, neighborhood aggregation, and hop count would show which design choice carries the performance.","A testable extension for true link prediction is to mask the candidate edge before building the PAMs; the paper's relation-prediction protocol follows a prior setup but does not state that masking explicitly, so re-running with masking would settle whether the scores reflect path reasoning rather than the target edge's presence.","The prime assignment is arbitrary, so scores should be invariant under renumbering of relations; running the pipeline with several random prime assignments would provide a cheap stability check."],"forward_implications":["On node-classification benchmarks, BoP features plus a gradient-boosted tree outperform all compared models on MUTAG and AM and finish in under a minute per dataset on CPU.","On relation prediction, the lossless BoP variant reaches the best Hit@3 on all three knowledge graphs while using zero trainable parameters.","On graph regression, BoP beats GAT and GIN on ZINC, AQSOL, and Peptides-struct and matches or beats a graph transformer on two of the three datasets.","The interpretability claim is concrete: a feature value like $77$ factorises as $7\\times 11$, mapping to the two-hop chain C-Single-C-Double-C, so task-important paths can be reported directly.","The paper's discussion implies that rule mining and path-guided reasoning reduce to lookups over $P^k$ and $P$ once the matrices are built."],"supporting_citations":[{"why":"It defines the original Prime Adjacency Matrix representation and the PAM-kNN baseline that this work extends and improves.","marker":"(Bougiatiotis and Paliouras, 2023b)"},{"why":"It supplies the relation-prediction experimental setup and the PathCon baseline whose scores the BoP variants are compared against.","marker":"(Wang et al, 2021)"},{"why":"It provides the ZINC and AQSOL graph-regression benchmarks and the GNN baseline scores used in Table 5.","marker":"(Dwivedi et al, 2023)"},{"why":"It provides the Peptides-struct long-range benchmark and the graph-transformer comparison used in the graph-regression experiments.","marker":"(Dwivedi et al, 2022)"},{"why":"It introduces the WN18RR knowledge graph used in the relation-prediction experiments.","marker":"(Dettmers et al, 2018)"},{"why":"It introduces the NELL995 knowledge graph used in the relation-prediction experiments.","marker":"(Xiong et al, 2017)"},{"why":"It provides the sparse-matrix backend used to compute PAM powers quickly in the released implementation.","marker":"(Welch et al, 2024)"},{"why":"It provides the R-GCN baseline used in the node-classification comparison.","marker":"(Schlichtkrull et al, 2017)"},{"why":"It provides the gradient-boosting classifier used to turn BoP features into node and graph predictions.","marker":"(Hancock and Khoshgoftaar, 2020)"}],"fun_headline_variants":["Prime paths from lossless hops outdo graph neural nets","Bag of Paths: CPU-only features rival neural graph models","Lossless prime factorization speeds graph analysis, beats NNs","From primes to paths: fast interpretable graph features win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The relation-prediction numbers assume that the true edge being predicted is not already sitting in the graph when the path matrices are built.","fun_headline_variants_meta":{"raw":{"variants":["Prime paths from lossless hops outdo graph neural nets","Bag of Paths: CPU-only features rival neural graph models","Lossless prime factorization speeds graph analysis, beats NNs","From primes to paths: fast interpretable graph features win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1566,"prompt_tokens":920,"completion_tokens":646,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":536,"completion_tokens_details":{"reasoning_tokens":578}},"tokens_in":536,"tokens_out":646,"duration_ms":6999,"temperature":1.0,"reasoning_tokens":578,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T18:52:11.800784+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Rerun the relation-prediction experiments with every test triple's edge removed from the graph before $P$ and $P^k$ are computed; if MRR or Hit@3 drops materially, the reported numbers depended on the target edge being present in the path matrices.","supporting_citations":[{"cited_title":"In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining","cited_arxiv_id":null,"evidence_quote":"It supplies the relation-prediction experimental setup and the PathCon baseline whose scores the BoP variants are compared against."},{"cited_title":"Journal of Machine Learning Research 24(43):1--48","cited_arxiv_id":null,"evidence_quote":"It provides the ZINC and AQSOL graph-regression benchmarks and the GNN baseline scores used in Table 5."},{"cited_title":"Advances in Neural Information Processing Systems 35:22,326--22,340","cited_arxiv_id":null,"evidence_quote":"It provides the Peptides-struct long-range benchmark and the graph-transformer comparison used in the graph-regression experiments."},{"cited_title":"In: Proceedings of the AAAI Conference on Artificial Intelligence","cited_arxiv_id":null,"evidence_quote":"It introduces the WN18RR knowledge graph used in the relation-prediction experiments."},{"cited_title":"arXiv preprint arXiv:170706690","cited_arxiv_id":null,"evidence_quote":"It introduces the NELL995 knowledge graph used in the relation-prediction experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the sparse-matrix backend used to compute PAM powers quickly in the released implementation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the R-GCN baseline used in the node-classification comparison."},{"cited_title":"Journal of big data 7(1):94","cited_arxiv_id":null,"evidence_quote":"It provides the gradient-boosting classifier used to turn BoP features into node and graph predictions."}],"review_version":1}