PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphDecide: Benchmarking System One Models on Graph Tasks

Xianliang Yang, Yapu Zhang, Li Zhao

arXiv:2610.06354v1cs.AI

TL;DR

System One models make graph decisions through supplied options, but their capabilities across graph-related tasks remain unclear. GraphDecide evaluates them with structural profiles, matched graph-text contrasts, and heuristic-proposal controls. Jev’s results show uneven structural performance, condition-dependent input benefits, and improved solutions with proposals that do not consistently surpass fixed rules.

  • Problem

    System One models’ capabilities across graph-related tasks remain unclear, including structural judgments, graph-text information use, and sequential decisions.

    Source: §1 · p. 1

  • Method

    GraphDecide is a model-independent benchmark combining structural task profiles, matched graph-text input comparisons, and candidate-pool controls for sequential construction.

    Source: §1 · p. 1

  • Results

    Jev shows uneven structural capabilities, condition-dependent benefits from relational input, and substantial improvements from heuristic proposals without consistently surpassing fixed rules.

    Source: §5.3 · p. 11

  • Takeaways & Limitations

    Graph decision performance should be assessed under the task, information, and candidate conditions in which evaluated configurations will be applied.

    Source: §5.3 · p. 11

    The findings cover limited public instances, small graph-cognition inputs, and specific construction tasks, and do not establish performance on larger or dynamic graphs.

    Source: §5.2 · p. 10

Abstract

from arXiv · show

Large language models (LLMs) are increasingly explored for graph understanding and decision-making, while System One models such as Jev select directly from supplied options. However, the capabilities of System One models on graph-related tasks remain unclear. We introduce GraphDecide, a model-independent benchmark that combines structural task profiles, matched graph-text input contrasts and heuristic-proposal controls to diagnose graph decision performance. We evaluate Jev and related choice-based models alongside language-model baselines, covering fourteen model-interface configurations. Jev's results illustrate the benchmark's central distinctions: accurate adjacency recognition does not guarantee broader structural correctness, joint graph-text input does not consistently improve prediction, and feasible construction does not establish high solution quality. Its task contracts, candidate interfaces and scoring rules support comparison across native selectors and language-model adapters. Code and aggregate results are available at https://github.com/VictorYXL/JevGraphBench.

1 Introduction

GraphDecide addresses uncertainty about System One models’ graph decisions by evaluating structural judgments, graph-text information use, and sequential optimization in distinct task families. Its diagnostic design combines task-level profiles, matched input contrasts, and candidate-pool controls.

1 Introduction

  • Task-level profiles, matched input conditions, and candidate-pool controls distinguish transfer across structural operations, added-input value, and selection quality relative to external proposals.A pooled accuracy or final objective can obscure these distinctions.Source: §1 · p. 1
  • GraphDecide evaluates graph understanding and decision-making through Graph Cognition, Graph-Text Decision-Making, and Sequential Decision-Making task families.The benchmark asks whether models understand structure, use graph and text information, and make sequential decisions for graph optimization.Source: §1 · p. 1, Figure 1 · p. 2
  • GraphDecide is model-independent: its task definitions and evaluator can be used with decision models beyond Jev through a common choice interface.The benchmark compares System One and other decision models with LLMs and classical controls.Source: §1 · p. 1
  • Matched graph-text conditions hold text and shared label anchors or candidate evidence fixed while assessing the addition of explicit edges for classification and retrieval.The comparison covers both node classification and candidate-based retrieval.Source: §1 · p. 1

2 Related Work

GraphDecide complements graph-learning, graph-reasoning, and decision-model evaluations with diagnostic comparisons across task profiles, input conditions, and proposal controls.

2.1 Benchmarks for Graph Learning and Reasoning

  • Existing graph benchmarks address graph learning, algorithm execution, natural-language graph reasoning, graph computation, and retrieval with textual and relational information.Examples include Open Graph Benchmark, CLRS [28], NLGraph, GraphArena, and STaRK.Source: §2.1 · p. 2
  • GraphDecide builds on established graph problems and public data, emphasizing diagnostic comparisons rather than new optimization objectives.Task profiles, matched input contrasts, and proposal-pool controls complement task-level benchmark scores.Source: §2.1 · p. 2

2.2 Language Models for Graph Understanding and Optimization

  • Related approaches include graph instruction tuning and graph-language integration [2], constructive policies, and LLM-assisted search or heuristic methods [31].Source: §2.2 · p. 2

2.3 System One Decision-Making and Evaluation

  • GraphDecide complements existing System One evaluations by combining structural correctness, graph-text information utility, and sequential solution quality in a choice-based framework.Related evaluations cover accuracy, calibration, and cost, Jev-guided route construction, and input perturbations [7].Source: §2.3 · p. 3

3 The GraphDecide Benchmark

GraphDecide separates benchmark specifications from model execution, then evaluates graph cognition, graph-text decisions, and sequential construction using task-specific inputs and scoring protocols.

3 The GraphDecide Benchmark

  • GraphDecide defines graph instances, answer spaces, reference evaluators, and scoring rules independently of the model adapter that supplies decisions.Jev is the main empirical case study, not a required component of the benchmark or evaluator.Source: §3 · p. 3

3.1 Tasks and Data Sources

  • Graph Cognition tests six structural query types on small induced graphs, while Graph-Text Decision-Making compares classification and entity selection under controlled textual and relational inputs.Graph Cognition uses 800 queries on graphs with 8–12 vertices; the primary graph-text panels include 100 classification targets and 100 selection queries.Source: §3.1 · p. 3
  • Sequential Decision-Making evaluates TSP, signed MaxCut, deterministic influence maximization, and binary modularity on ten public-data instances per task.Reference values use published optima for TSP, historical best-known values for MaxCut, enumerated optima for influence maximization, and solver-certified optima for modularity.Source: §3.1 · p. 3

3.2 Decision Interface and Input Conditions

  • Model-interface configurations map supplied inputs and candidate sets to choices; graph-text conditions vary evidence, while sequential modes compare direct construction with fixed-rule proposals.Sequential evaluation covers four tasks, ten instances per task, and two construction modes.Source: §3.2 · p. 4
  • Sequential decisions advance the evaluator’s state one action at a time, with later states and candidate sets depending on each model’s earlier choices.A trajectory continues until completion or failure.Source: §3.2 · p. 4

3.3 Evaluation Protocol

  • Graph-cognition scores use query accuracy, while graph-text evaluation reports classification accuracy and macro-F1 or entity-selection Hit@1 with paired condition comparisons.Invalid outputs count as incorrect; unsupported interfaces are reported separately.Source: §3.3 · pp. 4–5
  • Sequential evaluation reports completion coverage and mean gap over completed trajectories, with task-specific gaps measured against reference values and lower values indicating better quality.Failed and unsupported units remain in the coverage denominator; the mean gap is undefined when no trajectory completes.Source: §3.3 · p. 5

4 Experiments

Across the evaluated tasks, Jev's structural accuracy is uneven, graph-text combinations do not consistently improve predictions, and successful construction does not ensure strong solutions. Heuristic proposals improve Jev's results, but gains over direct choices do not consistently exceed fixed rules.

4.1 Experimental Setup

  • Fourteen configurations span native choice models, language-model baselines, candidate-token scoring, and a reasoning-enabled reference; the selection is complementary, not exhaustive.The configurations target different decision interfaces while retaining their interface limitations.Source: §4.1 · p. 5

4.2 Graph Cognition (RQ1)

  • Jev answers every adjacency query correctly, yet scores 67.80% on exact degree and 61.25% on articulation; Decider and Kev score only about 10% on exact degree.Jev exceeds both on five of six tasks, but Kev's articulation accuracy is slightly higher, 62.50% versus 61.25%. Jev outperforms smaller Qwen configurations and is competitive with larger Qwens, while remaining below GPT baselines.Source: §4.2 · p. 6

4.3 Graph-Text Decision-Making (RQ2)

  • Matched input conditions compare text, relations, and their combination for node classification and candidate retrieval, isolating whether added edges help when accompanying evidence is held fixed.Table 1 reports ogbn-arxiv accuracy and STaRK-Prime Hit@1 for the fourteen configurations.Source: §4.3 · pp. 6–7, Table 1 · p. 7

4.3.1 Node Classification

  • On ogbn-arxiv, Jev's G-A difference is +10 percentage points [+3,+18], while its TG-BAG difference is +1 point [-4,+7]; joint-input effects vary by configuration.Kev falls from 61% under G to 27% under TG, while Jev's TG accuracy is 58%.Source: §4.3.1 · p. 7

4.3.2 Candidate-Based Retrieval

  • On STaRK-Prime, Jev's T, G, and TG Hit@1 values are 48%, 47%, and 49%; its TG-BAG difference is +3 points [-6,+12].No supported configuration has a strictly positive TG-BAG interval in this panel.Source: §4.3.2 · p. 8

4.4.1 Direct Construction

  • Jev completes all TSP, MaxCut, and modularity instances, yet its mean TSP gap is 59.66%, and its mean MaxCut objective and modularity are zero.Its completed LT instances have a 52.84% gap; completion does not by itself establish solution quality.Source: §4.4.1 · p. 9

4.4.2 Heuristic-Proposal Selection

  • Proposal selection lowers Jev's gaps on all jointly completed instances, but it does not consistently beat fixed rules; on the same eight LT graphs, its 0.50% gap beats random-candidate 21.91% and classical 6.84%.The intervention supplies candidate actions, numerical features, rule identities, and sometimes forced transitions, so its benefit cannot be attributed solely to reducing options.Source: §4.4.2 · p. 9
  • Heuristic guidance substantially benefits Jev, but surpassing fixed rules is task-dependent; gains over weak direct policies do not necessarily yield strong final optimization.Related choice-based models likewise require separate comparisons against direct construction, random proposal selection, and fixed rules.Source: §4.4.2 · p. 10

5 Discussion and Conclusion

GraphDecide’s discussion finds that graph decision capabilities vary by operation, input condition, and task; success on one dimension does not establish success on another. The authors delimit these findings to the evaluated settings and call for assessing models under the conditions in which they will be applied.

5.1 Main Findings and Implications

  • Jev pairs strong edge recognition with weaker degree and articulation judgments, so capability should be assessed at the structural operation a task requires.Related choice-based models also show different profiles; a shared interface does not imply interchangeable graph capabilities.Source: §5.1 · p. 10
  • Relational input does not guarantee better graph-text predictions: gains vary by model and task, and matched contrasts measure the incremental value of added evidence.Jev benefits from relations over label anchors on ogbn-arxiv, while the additional benefit of explicit edges with text is less clear; STaRK-Prime does not reproduce the same relational-gain pattern.Source: §5.1 · p. 10
  • Heuristic proposals substantially improve Jev’s construction results, but outperforming a fixed rule is task-dependent and assistance does not uniformly yield strong solutions.Proposal selection changes candidate actions, features, forced transitions, and later histories together, so its mechanisms are not separately identified.Source: §5.1 · p. 10, §5.2 · p. 10

5.2 Scope and Limitations

  • The benchmark covers limited public instances, small graph-cognition inputs, and specific construction tasks; it does not establish performance on larger or dynamic graphs.ogbn-arxiv targets share context and label anchors, while STaRK-Prime tests selection within answer-containing candidate sets rather than end-to-end retrieval.Source: §5.2 · p. 10

5.3 Conclusion

  • GraphDecide separates structural judgments, graph-text information use, and sequential construction to compare System One models under task, information, and candidate conditions.Its task contracts and evaluator are model-independent, supporting use with future decision models as well as the configurations studied.Source: §5.3 · p. 11

Appendix A. Data and Task Specifications

The appendices specify the graph tasks, optimization settings, reference instances, model configurations, candidate rules, and scoring procedures used in the benchmark. Together, these details define the evaluation conditions and how coverage and outcomes are reported.

A.1 Structural Queries

  • Structural queries use six tasks on simple, undirected, unweighted induced graphs, with algorithmically computed answers and binary options except for degree.The tasks cover adjacency, degree, cycle existence, connectivity, distance thresholds, and articulation; graphs retain isolated vertices.Source: §A.1 · p. 13

A.2 Sequential Objectives and Feasibility

  • Sequential tasks define construction rules and objectives for TSP, signed MaxCut, deterministic LT, and binary modularity.LT uses two simultaneous seeds and a fixed-threshold process; its usual random-threshold approximation guarantee does not apply. The text also gives a deterministic example motivating empirical evaluation of marginal-cascade heuristics.Source: §A.2 · p. 13

A.3 Public Optimization Instances

  • The public-instance inventory lists RQ3 graphs, sizes, and edge counts, with references drawn from proven TSP optima, historical MaxCut best-known values, exact LT optima, and certified modularity values.The listed TSP, MaxCut, LT, and binary-modularity tables identify their respective reference or inventory roles.Source: §A.3 · p. 13, Table A.1 · p. 14, Table A.2 · p. 14

A.4 Reference Calculations

  • The appendix provides numerical certification for binary-modularity references and deterministic seed-pair enumeration with independent closure checks for LT.Both reference-calculation sections list all ten fixed-instance references.Source: §A.4 · p. 15

B.1 Model Configurations

  • Model configurations include native choice-based models, generation and candidate-scoring interfaces, and specified Qwen and GPT settings.The appendix records context and configuration details, including that Astra’s medium reasoning was observed in response metadata rather than explicitly set in its request.Source: Table B.1 · p. 15, §B.1 · pp. 15–16

B.2 Fixed Candidate Rules and Controls

  • Candidate controls compare direct construction with selection among actions proposed by fixed rules, alongside within-pool random and fixed-rule controls.Proposals merge duplicate actions while retaining rule identities; singleton actions are forced without a model call. Task-specific rules define candidate choices for TSP, partition tasks, and LT.Source: §B.2 · p. 16

B.3 Scoring, Statistics, and Coverage

  • Scoring uses paired target-bootstrap intervals for RQ2 and reports RQ3 means conditional on feasible completion, with coverage retaining scheduled trajectories.Intervals are pointwise and unadjusted for multiplicity; shared ogbn-arxiv contexts and anchors induce dependence beyond target resampling. The appendix also records unsupported configurations and four Jev LT failures caused by max_tokens_exceeded.Source: §B.3 · pp. 16–17, Table B.2 · p. 17, Table B.3 · p. 17

B.4 Complete GPT-5.4 RQ3 Results

The appendix presents complete GPT-5.4 no-reasoning trajectory tables for four construction tasks and lists selected episodes from the primary evaluation. It states that the GPT-5.4 tables contain eighty scheduled trajectories, all feasible with legal output.

B.4 Complete GPT-5.4 RQ3 Results

  • The GPT-5.4 TSP tables report direct-construction and heuristic-proposal-selection trajectories, with objectives and gaps rounded for display.The table descriptions identify each construction mode; TSP gaps are percentages.Source: §B.4 · p. 17, Table B.4a · p. 18, Table B.4b · p. 18
  • The GPT-5.4 signed-MaxCut tables report direct-construction and heuristic-proposal-selection trajectories; MaxCut gaps are percentages.The appendix states that every row is feasible with legal output.Source: §B.4 · p. 17, Table B.4c · p. 18, Table B.4d · p. 19
  • The GPT-5.4 deterministic-LT tables report direct-construction and heuristic-proposal-selection trajectories, including a zero-call proposal episode with forced singleton actions.LT gaps are percentages.Source: §B.4 · p. 17, Table B.4e · p. 19, Table B.4f · p. 19
  • The GPT-5.4 binary-modularity tables report direct-construction and heuristic-proposal-selection trajectories, with gaps expressed as absolute differences in Q.The appendix states that the table objectives and gaps are rounded only for display.Source: §B.4 · p. 17, Table B.4g · p. 20, Table B.4h · p. 20

B.5 Selected Episode Outcomes

  • Selected primary-evaluation episodes include context-expanded LT inputs, Jev’s input rejection, and listed model, graph, mode, feasibility, terminal, and call information.The appendix notes that these selected rows also contribute to aggregate results.Source: §B.5 · pp. 20–21, Table B.5 · p. 20

Appendix C. Complete RQ1 Results

The appendix describes aggregate RQ1 accuracy and response-coverage results, as well as task-size-averaged accuracy tables by source. It also reports GPT-5.4’s overall counts and degree accuracy under different averaging procedures.

Appendix C. Complete RQ1 Results

  • 91.4154% is GPT-5.4’s task-size-averaged degree accuracy, versus 91.0000% when pooling its 364 correct answers out of 400 degree queries.Across RQ1, GPT-5.4 returned 733 correct answers out of 800 legal answers.Source: Appendix C · p. 21
  • The aggregate table reports accuracy and response coverage, while the appendix states that all fourteen configurations are retained and task-size macro weights each task and size equally.Invalid choices count as incorrect.Source: Appendix C · p. 21, Table C.1 · p. 22

C.2. All four sources

  • The all-source table reports task-size-averaged accuracy across Facebook, ca-GrQc, Power Grid, and Human PPI.Its caption identifies the metric and source scope, not individual model outcomes.Source: Table C.2 · p. 22

C.3. Facebook

  • The Facebook table reports task-size-averaged accuracy for that source.Source: Table C.3 · p. 23

C.4. ca-GrQc

  • The ca-GrQc table reports task-size-averaged accuracy for that source.Source: Table C.4 · p. 23

C.5. Power Grid

  • The Power Grid table reports task-size-averaged accuracy for that source.Source: Table C.5 · p. 24

C.6. Human PPI

  • The Human PPI table reports task-size-averaged accuracy for that source.Source: Table C.6 · p. 24

C.7. GPT-5.4 Source and Size Counts

  • A separate GPT-5.4 table reports correct and scheduled query counts by source and size.Source: Table C.7 · p. 25

Appendix D. Complete RQ2 Results

Appendices D and E organize the complete matched-input and sequential-construction results by task, reporting performance, coverage, controls, and paired comparisons. The supplied passages specify table scopes and interpretation rules but do not provide most table cell values.

D.8. Independent 200-Target ogbn-arxiv Evaluation

  • The independent ogbn-arxiv evaluation reports accuracy on its own 200-target set and does not add targets to the primary paired comparisons.Its public-data evaluation is reported separately.Source: §D.8 · p. 30, Table D.8 · p. 30

E.1. TSP

  • The TSP tables report reference gaps, completion, paired changes, objectives, and matched controls for direct construction and heuristic-proposal selection.Paired changes compare modes on jointly completed graphs and are diagnostic rather than absolute-quality rankings.Source: Table E.1 · p. 31, §E.1 · p. 31, Table E.2 · p. 32

E.2. Signed MaxCut

  • The Signed MaxCut tables report reference gaps, completion, paired changes, objectives, and matched controls for both construction modes.Paired changes are diagnostics, not absolute-quality rankings.Source: Table E.5 · p. 33, §E.2 · p. 33, Table E.6 · p. 34

E.3. Deterministic LT

  • The Deterministic LT tables report reference gaps, completion, paired changes, objectives, and matched controls across the two construction modes.Paired changes compare heuristic-proposal selection with direct construction on jointly completed graphs.Source: Table E.9 · p. 35, §E.3 · p. 35, Table E.10 · p. 36

E.4. Binary modularity

  • The Binary modularity tables report reference gaps, completion, paired changes, objectives, and matched controls across the two construction modes.Modularity uses the rational Q* references; tiny signed residuals within the stated rounding range do not establish improvement over Q*.Source: Table E.13 · p. 37, Table E.14 · p. 38, Table E.15 · p. 38

E.5. Cross-Task Quality and Completion

The cross-task section presents reference gaps and completion for direct and heuristic-proposal construction, while the following interface specification distinguishes model readouts.

E.5. Cross-Task Quality and Completion

F.1 GPU Candidate Scoring and Interface Settings

  • The implementation distinguishes native selection, constrained generation, and candidate scoring as alternative readouts, not different task definitions.Candidate scoring selects by conditional argmax over supplied candidate-token probabilities; its generated token is counted but not used for the choice.Source: §F.1 · p. 40

F.2 Independent 200-Target ogbn-arxiv Protocol

The independent ogbn-arxiv evaluation fixes a separate 200-target protocol with shared text and graph evidence conditions. Its supporting results include paired comparisons, while separate public optimization studies specify their own instances and controls.

F.2 Independent 200-Target ogbn-arxiv Protocol

  • The independent evaluation samples 200 official test targets and uses fixed text, graph context, and label-anchor conditions for forty-class prediction.All five conditions share training-label anchors; target labels are withheld.Source: §F.2 · pp. 40–41
  • For GPT rows, “Medium” is observed response metadata rather than an explicitly submitted reasoning setting, and 4,096 is configured rather than a verified total reasoning-token limit.The token value is not a verified limit on total reasoning tokens.Source: §F.2 · p. 41
  • Nine supported configurations complete 60 validation and 1,000 test decisions each, while Laya is unsupported; validation checks are excluded from test accuracy.Jev's legal selected answers are retained despite some nonunit probability-vector sums.Source: §F.2 · pp. 41–42

F.3 Supporting Macro-F1 and Paired Intervals

  • The paired target-bootstrap intervals keep conditions paired, but the 1,408 test-anchor slots contain 1,321 distinct training anchors, so the intervals do not capture all network dependence.The analysis uses 1,000 target resamples.Source: §F.3 · p. 42
  • Jev's TG-BAG accuracy difference is +3.0 percentage points [-1.0, +7.0], leaving its explicit-edge benefit unresolved by that interval.Every G-A accuracy interval is positive, with point estimates from 8.5 to 21.0 percentage points; the passage identifies these contrasts as showing edge value when only label anchors are otherwise available.Source: §F.3 · p. 43

G.1 Three-Condition Public Protocol

  • The supporting optimization protocol uses seven TSPLIB EUC_2D instances and ten signed spin-glass graphs, with task-specific construction and control procedures.Tour distances use the nearest-integer convention; signed cuts use historical best-known references.Source: §G.1 · p. 43

G.2 Supporting Full-Action Results and Matched Subsets

The supporting optimization appendices report public-instance outcomes and completion separately from the primary evaluation. They also describe a proposal diagnostic whose arms can diverge in subsequent histories.

G.2 Supporting Full-Action Results and Matched Subsets

  • Across supporting full-action and model-expansion panels, 453/510 episodes complete, while 57 capacity exclusions remain in coverage.Kev has six unsupported tour conditions and Laya rejects all 51 conditions before inference; Jev's returned actions remain legal despite nonunit probability sums and one choice–argmax disagreement.Source: §G.2 · p. 44, Table G.1 · p. 44, Table G.2 · p. 44
  • The separate GPT panel uses its own graph sets, one-condition-per-graph schedules, and completion subsets, so its results are not pooled with primary estimates.Undefined denotes no feasible completion.Source: §G.2 · p. 45, Table G.4 · p. 45

G.3 Seven-Tour Anonymous/Named Proposal Diagnostic

  • In the seven-tour diagnostic, Jev Anonymous heuristic-proposal selection completes 20/21 episodes, while all other model-arm combinations complete 21/21.Of 126 new episodes, 125 complete.Source: §G.3 · p. 45
  • Named proposals improve mean paired quality for all three configurations, but the comparison reflects combined changes in rule information and subsequent decisions.Subsequent histories may diverge, so later inputs are not held fixed.Source: §G.3 · pp. 45, 47

G.4 Supporting Public Call and Token Accounting

  • Supporting public call accounting reports six pre-forward Kev rejections and 51 Laya pre-forward rejections, while the other three expansion configurations each have 6,684 successful forwards.Kev supports fifteen tour conditions in the original public expansion.Source: §G.4 · p. 47, Table G.10 · p. 47

G.5 Independent Three-Arm Public Extension

  • The independent three-arm extension compares direct construction, anonymous proposals, and named proposals on 51 public graph–condition pairs, with each arm following its own history.Its Qwen generation ceiling is 64 tokens, distinct from the seven-tour diagnostic's historical 16-token setting.Source: §G.5 · pp. 47–48

G.6 Additional Public Outcomes

  • The additional public-outcomes cohort is analyzed separately from the three-arm extension, its unattempted-slot cohort, and the primary paired panel.Its seven completion outcomes use 64 output tokens and a 40,960-token Qwen context.Source: §G.6 · p. 50, Table G.14 · p. 50

Appendix H. Reference Calculations for the Induced-Graph Tasks

  • The induced-graph reference calculations apply to the frozen benchmark instances, not the full source networks or other partition and diffusion variants.TSP retains published proven optima and MaxCut retains historical best-known values.Source: Appendix H · p. 51

H.1 Binary Modularity

This appendix reports model gaps against solver-certified binary-modularity references, then defines deterministic two-seed LT references through exhaustive enumeration.

H.1 Binary Modularity

  • Modularity maximization is converted to minimizing integer energy E=(V_A-m)^2+2mc using binary vertex assignments and auxiliary variables.The formulation linearizes the square and edge-crossing terms; empty communities remain legal, including the one-community partition with Q=0.Source: §H.1 · p. 51
  • All ten instances terminate with optimal status; numerical dual bounds and integer-energy checks certify optimality, while exact rational arithmetic evaluates the witnesses.Validation also compares small graph families against exhaustive binary assignments and checks witnesses against NetworkX modularity.Source: §H.1 · p. 51
  • Astra's mean gaps were 0.0002611075272071162 (direct construction; 8/10 optimal) and 0.012982818923280088 (heuristic-proposal selection; 1/10); GPT-5.4's were 0.4042398456 and 0.0422861571, with 0/10 and 1/10 optimal, respectively.All modularity references use Q*=1/2-E*/(2m^2).Source: §H.1 · p. 52

H.2 Deterministic LT Influence Maximization

  • For deterministic LT with two seeds, exhaustive enumeration evaluates all distinct seed pairs and identifies the global optimum by matching lower and upper bounds.The queue evaluation costs O(n(n-1)(n+m)/2) overall; listed witness IDs are local to the frozen graph, and a listed pair need not be unique.Source: §H.2 · pp. 52–53
Loading 2610.06354v1…