PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphSelect for Budgeted Representation Selection in Multimodal Graph Inference

Xu Wang, Xunkai Li, Yinlin Zhu, Rong-Hua Li

arXiv:2609.33561v1cs.LG

TL;DR

The paper asks which candidate text and image representations are needed to preserve a trained multimodal graph predictor’s decisions under separate modality budgets. GraphSelect refines an initial subset through jointly evaluated exchanges and score updates. It achieves the highest mean objective recovery in a six-graph comparison, and retaining 20% per modality yields a mean accuracy gap of 0.10 percentage points across nine trained architectures.

  • Problem

    The paper asks which encoded text and image representations should remain available to preserve a trained graph predictor’s decisions under limited input capacity.

    Source: §1 · p. 1

  • Method

    GraphSelect starts from individual candidate gains, screens promising removals and additions, and refines the subset through jointly evaluated exchanges and score updates.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    GraphSelect achieves the highest mean objective recovery in a six-graph comparison; at 20% capacity per modality, the mean accuracy gap is 0.10 percentage points across nine trained architectures.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The results show that joint selection can preserve classification performance under a limited candidate representation budget.

    Source: §6 · p. 9

    The experiments measure gaps to full input but do not establish statistical equivalence, global optimality, or deployment savings.

    Source: §D.8 · p. 23

Abstract

from arXiv · show

Multimodal graph predictors combine text, images, and relations to classify connected entities. How much of this input is needed to preserve their predictions? We study budgeted representation selection, which chooses a subset of candidate text and image vectors under a separate capacity for each modality. Predictions from the complete candidate input define the classes to preserve. The challenge is that a representation's contribution depends on the other selected inputs, while graph propagation extends its effects across nodes. Our empirical study shows that candidate rankings change with the selected input, while predicted probabilities remain informative after the class stops changing. Updating scores improves selection, and exchanging inputs can improve a subset whose capacity is already filled. These findings lead to GraphSelect, which starts from individual candidate gains and refines the subset through jointly evaluated exchanges. It screens promising removals and additions, accepts an exchange when it reduces the prediction loss, and updates the scores. Experiments on six graphs show higher mean objective recovery than six attribution and explanation methods adapted to the selection task. Across nine trained architectures on two graphs, retaining 20% of the candidate representations per modality gives a mean accuracy drop of 0.10 percentage points relative to full candidate input, preserving classification performance with substantially fewer text and image representations.

1 Introduction

The paper studies which text and image representations to retain under separate modality budgets while preserving a trained graph predictor’s decisions. Because representations interact within the selected subset and graph propagation extends their effects across nodes, GraphSelect refines an initial selection through exchanges and score updates.

Motivation

  • A neighboring image can support a target’s predicted category even when the target keeps its own text and image inputs.In the Grocery example, exchanging the fern image for the neighbor’s image restores most of the lost confidence at the same budget.Source: §1 · p. 1, Figure 1 · p. 2

Empirical findings

  • The study finds that candidate scores should reflect the input being assembled, reward the original predicted classes, and change as the subset changes.Revising earlier choices improves the completed selection.Source: §1 · p. 2

Method

  • GraphSelect refines an initial subset by jointly evaluating promising exchanges and updating scores after an improvement.Forward updates addition gains but keeps every earlier selection.Source: §1 · p. 2

Contributions

  • GraphSelect achieves the highest mean objective recovery in a six-graph comparison, while 20% capacity per modality yields a mean accuracy gap of 0.10 percentage points across nine trained architectures.The comparison includes six attribution and explanation methods adapted to the selection task.Source: §1 · p. 2

2 Related Works

Related work spans multimodal graph learning, modality and data selection, attribution and graph explanation, and prediction-preserving input subsets. This paper selects node-level text and image representations jointly under separate capacities and evaluates their effects on graph predictions.

Multimodal graph learning

  • Multimodal graph research combines heterogeneous node attributes with relations for tasks including recommendation, matching, and node analysis.Recent directions include graph propagation, neighbor roles, generative tasks, global transformers, and unified embeddings.Source: §2 · p. 2

Modality selection and acquisition

  • Modality selection estimates the value of information sources, while data selection chooses training examples; this paper instead selects encoded node representations under separate modality capacities.The decision unit is one node’s encoded text or image representation, evaluated for its joint effect on graph predictions.Source: §2 · pp. 2–3

Attribution and prediction-preserving subsets

  • Attribution and graph explanation scores offer starting points for selecting a common subset, while prediction-preserving subset methods differ in their target and selection setup.GraphSelect optimizes probability assigned to full-input classes and revises a common subset through jointly evaluated exchanges.Source: §2 · p. 3

3 Problem Formulation and Empirical Study

The paper formulates selection over candidate text and image representations with separate quotas, using full-input predicted classes as targets. Its empirical probes show that scores depend on the current subset, predicted-class probability remains useful after hard agreement saturates, and score updates improve selection.

3.1 Problem Formulation

  • The selection problem changes only candidate availability while keeping the graph, encodings, and predictor fixed, and uses the full-candidate predictions on target nodes as reference classes.Candidate and target nodes may overlap; representations outside the candidate pool retain their observed values.Source: §3.1 · p. 3
  • Each candidate representation is a node’s text or image vector, and separate modality capacities specify how many of each can be retained.Unselected candidates use their modality’s mean training representation; the objective remains sensitive to probability changes even when the predicted class is unchanged.Source: §3.1 · pp. 3–4

3.2 Empirical Study

  • The controlled probes vary candidate scoring input, prediction objective, and score updates while holding the graph, predictor, candidates, targets, references, budgets, and tie rule fixed.The comparison spans five graphs for ranking probes and six graphs, 54 graph-seed-budget combinations, for objective and update comparisons.Source: §3.2 · p. 4
  • CE deletion’s mean Spearman correlation with first-addition gains is 0.950, versus 0.791 for TV deletion, yet CE deletion misses the best addition in 11 groups.Deletion scores reflect full input, whereas construction scores reflect the subset being assembled.Source: §3.2 · p. 4
  • At 20% capacity, pooled recovery is 42.3% for predicted-class cross-entropy, 36.1% for KL divergence, and 23.6% for prediction agreement.Hard agreement gives zero gain at 1,877 of 2,772 selected steps, while cross-entropy continues to reward more probability assigned to the target class.Source: §3.2 · p. 4
  • Updating gains lowers loss in all 54 comparisons with the initial-gain ranking, with mean recovery improvement rising from 0.2 percentage points at 5% capacity to 0.9 at 20%.At 20% capacity, pooled recovery is 42.3% for Forward and 41.4% for the initial-gain ranking.Source: §3.2 · p. 4, Figure 2 · p. 5
  • Propagation expands a candidate representation’s effect from its own node to an average of 127.2 target nodes.Removing feature and label propagation reduces mean full-input accuracy from 76.38% to 70.41%, with lower accuracy on five of six datasets.Source: §3.2 · pp. 4–5
  • The probes motivate exchanges that revise earlier choices when another representation becomes more useful within the current subset, while preserving both modality quotas.Exchange controls find replacements that improve some completed Forward subsets.Source: §3.2 · p. 5

4 Methodology

GraphSelect initializes a feasible subset from candidate gains, screens possible removals and additions, and jointly evaluates exchanges. Accepted improvements preserve both modality quotas and trigger refreshed scores; additive predictors can evaluate changes only on affected target rows.

4.1 Overview

  • GraphSelect fills both modality quotas from an initial ranking, then evaluates proposed exchanges jointly over target nodes and updates scores after an accepted improvement.For additive graph predictors, calculations can be restricted to affected nodes.Source: §4.1 · p. 5

4.2 Initialization and Current State Screening

  • Initialization selects the highest-gain candidates at the reference input within each modality, then shortlists low-removal-loss and low-addition-loss candidates for joint evaluation.The shortlist scores identify inputs the current subset can most readily give up and candidates that improve its present predictions.Source: §4.2 · p. 5

4.3 Exact Screened Exchange

  • Each exchange replaces a selected representation with an unselected representation of the same modality, and an improving exchange triggers refreshed shortlists.Accepted exchanges preserve both quotas and strictly lower loss; the budgeted comparison limits shortlist width to L ≤ 8 and evaluations to ⌊0.35Qforward⌋.Source: §4.3 · p. 6

4.4 Exact Evaluation for Additive Predictors

  • For additive predictors, additions and exchanges change logits only on affected target rows, so unchanged loss terms cancel exactly; nonlinear predictors use complete forward passes.An addition uses the candidate’s logit change, while an exchange uses the added candidate’s change minus the removed candidate’s change.Source: §4.4 · pp. 6–7

5 Experiments

The experiments compare budgeted selectors under shared modality quotas, then test GraphSelect’s refinement components and the prediction quality retained at different capacities. GraphSelect leads the six-graph comparison, while larger subsets improve probability recovery and preserve accuracy closely.

5.1 Experimental Settings

  • The additive comparison uses six graph benchmarks, three split seeds, 220 candidate nodes, and 5%, 10%, and 20% capacities; nonlinear tests cover nine architectures on Grocery and RedditS.Selectors share the candidate pool and modality quotas; test-set membership and labels are unavailable during selection.Source: §5.1 · p. 7, Figure 4 · p. 8

5.2 Comparison Under the Shared Protocol

  • 17.9%, 29.9%, and 48.3% mean objective recovery at 5%, 10%, and 20% capacity exceed Feature Ablation’s 15.2%, 26.0%, and 43.9%.GraphSelect leads across all three capacities and all six dataset means at 20%.Source: Table 1 · p. 7, §5.2 · p. 8, Figure 4 · p. 8
  • Compared with Forward, budgeted GraphSelect gives lower loss in 46 of 54 settings, ties in five, and higher loss in three; mean recoveries reach 48.3% and 48.0% at 20% capacity.Source: §5.2 · p. 8

5.3 Search Ablations and Capacity Analysis

  • Exchange refinement raises loss in 112 of 126 settings when removed; keeping initial scores during exchange raises loss in 62, ties in 62, and improves it in two.The controls indicate that both revising the initial subset and recomputing scores contribute to selection quality.Source: §5.3 · p. 8
  • At 20% capacity, mean accuracy and Macro-F1 drops are 0.100 and 0.065 percentage points, while mean objective recovery reaches 77.6%.Across 54 architecture, graph, and seed settings, recovery rises from 37.6% at 5% capacity to 77.6% at 20%.Source: §5.3 · p. 8, Table 2 · p. 9, Figure 5 · p. 9
  • At 20% capacity, graph architectures recover 91.0%–97.9% of the objective gap, versus 50.5%–86.6% for multimodal graph architectures.Changes in class probabilities need not change the most likely class, so small accuracy gaps can coexist with larger objective gaps.Source: §5.3 · p. 9

6 Conclusion

The paper presents GraphSelect as a method for preserving multimodal graph predictions under separate text and image budgets. It reports the strongest mean objective recovery in a six-graph comparison and describes supporting comparison, alignment, and reproducibility materials.

6 Conclusion

  • GraphSelect jointly evaluates exchanges and updates scores to preserve multimodal graph predictions under separate text and image representation budgets.Across nine trained architectures, retaining 20% of candidate representations per modality gives a mean accuracy gap of 0.10 percentage points to full input.Source: §6 · p. 9

AI use statement

  • The authors state that generative AI assisted with writing and polishing, and that they reviewed the work and verified the final text against reported claims.They take responsibility for the final content.Source: AI use statement · p. 10

Reproducibility statement

  • The reproducibility statement identifies the formulation, method, appendix, mathematical analysis, and complete results as sources for implementation and evaluation details; code will accompany the preprint.The listed materials cover operators, objectives, candidate construction, protocol, method adaptations, assumptions, ablations, and computational cost.Source: Reproducibility statement · p. 10

A.1 Comparison Methods and Controls

  • The comparison methods and controls cover alternative representation-scoring approaches and tests of scoring input, prediction objective, construction, exchange, and score updates.Table 3 summarizes how each method selects representations.Source: §A.1 · p. 12, Table 3 · p. 13

A.2 Deletion and Addition Alignment

  • Across 6,600 candidate representations, CE deletion identifies the best first addition in 19 of 30 groups, but candidate value can change between full and reference input.CE and TV deletion have mean Spearman correlations with addition gains of 0.950 and 0.791, respectively.Source: §A.2 · p. 13

A.3 Comparison with Full Input at Six Capacities

The appendix compares selectors against full input across capacities and architectures, tests reference and search controls, and details the exchange procedure. It also reports exact-optimum results on small pools and evaluation savings on larger candidate pools.

A.3 Comparison with Full Input at Six Capacities

  • GraphSelect has the highest mean objective recovery at every capacity, and from 10% onward the smallest mean accuracy and Macro-F1 gaps.Forward is slightly closer to full input on accuracy and Macro-F1 at 2.5% and 5%.Source: §A.3 · p. 14, Figure 6 · p. 14
  • Increasing capacity from 20% to 30% brings most architectures closer to full-input results, but the architecture with the highest recovery need not have the smallest accuracy gap.At 20%, GAT has the highest recovery; MGAT leads full-input Grocery accuracy and Macro-F1, while DGF leads both metrics on RedditS.Source: §A.3 · pp. 14–15, Figure 7 · p. 14

A.4 Reference and Search Controls

  • GraphSelect has lower mean loss than the initial-gain ranking under all four reference rules, although selected sets vary across references.Mean Jaccard overlap with the training-mean selection is 0.879 for median, 0.348 for nearest-to-mean, and 0.538 for zero.Source: §A.4 · p. 15
  • Across 126 settings, GraphSelect beats Forward in 57, ties in 68, and loses in one; score updates improve 62 settings and tie in another 62.It uses 43.60% of the full forward passes available under the matched evaluation budget; gains from score updates are largest for MMGCN, MGAT, and GSMN.Source: §A.4 · pp. 15–16, Table 7 · p. 16, Figure 8 · p. 16

A.5 Algorithm Details

  • GraphSelect initializes by ranking individual candidate gains within each modality, then screens removals and additions and jointly evaluates feasible exchanges.It accepts the best exchange only when its gain exceeds ε, then recomputes both rankings or stops if no pair improves loss.Source: §A.5 · pp. 16–17

A.6 Exact Optima and Larger Candidate Pools

  • On predefined eight-node pools, Forward achieves 99.44%, 99.77%, and 99.46% of reference-to-oracle improvement at quotas of one, two, and three per modality.Exact set matches occur in 88.9%, 91.1%, and 74.4% of settings; an exact optimum is unavailable for the larger N = 220 pools.Source: §A.6 · p. 17
  • With 1,000 candidate nodes and quotas of 50, 100, and 200 per modality, Forward beats the initial-gain ranking in all 54 settings; sparse evaluation avoids 85.75% of exact marginal evaluations.End-to-end runtime was not measured in this test.Source: §A.6 · p. 17

B.1 Task and Search Rule

The task preserves full-input predicted classes under exact per-modality quotas, using exchanges to lower selection loss. Screening can miss improving exchanges, so the guarantees stop short of optimality.

B.1 Task and Search Rule

  • Selection evaluates selected-input probabilities against full-input predicted classes while keeping exact modality quotas through same-modality exchanges.The graph, predictor, and representations outside the candidate pool remain unchanged.Source: §B.1 · p. 17
  • Accepted exchanges strictly lower loss and terminate under a finite evaluation cap, but screening guarantees neither local nor global optimality.Screening can omit an improving exchange.Source: §B.1 · p. 17

B.2 A Deletion Ranking Counterexample

  • A deletion ranking can select a candidate with zero addition gain even when the best addition has positive gain, so deletion alone has no positive constant-factor guarantee.The counterexample demonstrates that rankings can depend on whether a candidate is removed from full input or added to the reference input.Source: §B.2 · p. 18

B.3 Finite Transition Identities

  • Summing finite transition gains cancels intermediate losses, and the loss is the negative logarithm of the geometric-mean probability assigned to full-input classes.The identities apply to additions, removals, and exchanges.Source: §B.3 · p. 18
  • A class disagreement requires assigned class probability at most 1/2, so selected-input error is bounded by full-input error plus disagreement rate, without a subset approximation ratio.The bounds also relate selection loss to a low-confidence rate.Source: §B.3 · p. 18

C Exact Sparse Evaluation

For additive predictors, sparse changes in candidate logits permit exact evaluation on affected target rows; nonlinear predictors instead require full forward passes.

C Exact Sparse Evaluation

  • For additive predictors, each candidate changes logits on sparse target rows, so addition and exchange gains need evaluation only on affected rows.Rows outside the affected sets cancel exactly, and an inverted index maps target rows to the candidates that affect them.Source: C Exact Sparse Evaluation · p. 19
  • One additive candidate addition costs O(Cse), while one exchange costs O(C|Tr ∪Ta|) after current logits are available.These arithmetic counts apply to the additive model; nonlinear objective evaluations require a full forward pass.Source: C Exact Sparse Evaluation · p. 19

C.1 Implementation and Computational Cost

  • The sparse implementation caches candidate contributions, current logits, and dependent gains, recomputing every gain affected by an accepted update before reuse.The nonlinear implementation constructs each candidate input and evaluates it with a full predictor pass; both implementations follow the same selection rule.Source: §C.1 · p. 19

D.1 Datasets and Splits

The evaluation uses prescribed transductive graphs, trained predictors, and candidate text and image representations under separate modality budgets. Selectors are compared using full-input predicted classes, with test labels withheld during selection.

D.1 Datasets and Splits

  • The main studies use the first 220 candidate nodes across three split seeds, with 11, 22, or 44 selected representations per modality at 5%, 10%, or 20% capacity.The larger-scale comparison uses all 1,000 candidate nodes; the full capacity sweep also includes 2.5%, 15%, and 30%.Source: §D.1 · pp. 19–20

D.2 Predictors and References

  • The study evaluates an additive predictor and nine trained nonlinear architectures using stored encodings, with the modality mean of training representations as the main fixed reference.Models are evaluated without retraining or selecting checkpoints based on subset results.Source: §D.2 · p. 20

D.3 Selection and Evaluation Procedure

  • Full candidate input determines target classes before selection; selectors use no test membership or labels, and test nodes are evaluated afterward.Search parameters are tuned on predefined Grocery settings, with the remaining Grocery settings and all RedditS settings reserved for disjoint evaluation of the selected width.Source: §D.3 · p. 20

D.4 Comparators

  • Six attribution and explanation methods are adapted to select whole representations under the same predictor, candidate pool, target classes, and modality quotas.Controls vary scoring input, objective, or score updating, including deletion scores, initial gains, Forward construction, and exchanges with or without score updates.Source: §D.4 · pp. 20–21

D.5 Metrics and Statistical Units

  • The primary objective is cross-entropy to full-input predicted classes, while objective recovery measures loss reduction relative to reference and full input.Tables report mean ± population standard deviation over repeated settings, with hierarchical uncertainty intervals and paired win/tie/loss counts.Source: §D.5 · p. 21

D.6 Reproducibility Details

  • The source package includes experiment configurations, commands, environment details, individual results, and aggregation scripts that pair methods by setting.Figures and tables are derived from the paired results.Source: §D.6 · p. 21

D.7 Graph Ablation Study

Graph ablations separate candidate propagation from other graph terms. Exchanges improve selection across all three predictor conditions, while propagation changes candidate effects across target nodes.

Ablation design

  • The ablation retains noncandidate graph context and label propagation when removing candidate-deviation propagation, then removes both feature and label propagation in the third condition.The three conditions share encodings, splits, candidate sets, and probe-training procedures; each defines target classes using its own full candidate input.Source: §D.7 · p. 21

Graph ablation results

  • Graph terms improve mean full-input test accuracy by 5.97 percentage points across five datasets, but removing them raises EleFashion accuracy from 80.06% to 82.21%.The graph ablation compares predictor conditions with each condition's own full-input target classes.Source: §D.7 · p. 21
  • Exchanges lower selection loss versus the initial-gain ranking in 51–54 of 54 settings across all three graph conditions, and versus Forward in 45–47 settings.Table 10 averages 18 graph and seed settings per condition; the remaining comparisons are ties or losses as reported for each condition.Source: Table 10 · p. 22, §D.7 · p. 22
  • Removing candidate propagation changes mean accuracy by less than 0.01 percentage points, although propagation affects 17.4–277.3 targets per candidate and creates shared affected targets in 12.1% of candidate pairs.Without propagation, each candidate affects one target and no candidate pairs share affected targets.Source: §D.7 · p. 22

Illustrative exchange

  • In the Grocery example, an exchange replaces a fern image with a neighboring jicama image at unchanged capacity, raising the target-class probability from 47.5964% to 53.0059%.The predicted category remains Produce throughout, compared with 53.4605% under full input.Source: §D.7 · p. 22

D.8 Scope and Limitations

The reported measures capture different aspects of preservation, and aggregate results can conceal variation. The evaluated workflow leaves cost-based savings, broader architecture analysis, and global optimality unresolved.

D.8 Scope and Limitations

  • Objective recovery and test accuracy or Macro-F1 measure different aspects of preservation, and a high recovery ratio need not imply the smallest accuracy gap.An aggregate mean can conceal this variation.Source: §D.8 · pp. 22–23
  • The workflow uses complete candidate representations during selection, while byte, latency, or energy costs require weighted costs and system measurements.Reconstruction of missing modalities and transfer to future models involve additional modeling choices.Source: §D.8 · p. 23
  • The graph ablation covers only the additive predictor; extending it to nine nonlinear architectures would test how architecture changes the propagation–selection relationship.Source: §D.8 · p. 23
  • Screening can miss improving exchanges, and experiments measuring gaps to full input do not establish statistical equivalence or global optimality.Deployment savings also require further investigation.Source: §D.8 · p. 23

Related papers

Loading 2609.33561v1…