acceptodds
Withdrawn from ICLR 2027

GraphSelect for Budgeted Representation Selection in Multimodal Graph Inference

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Multimodal graphs describe connected entities through relations, text, and images. Predictors that combine these sources support recommendation, retrieval, and node classification, but their encoded inputs can exceed the cache, transfer queue, or accelerator space available for a later inference stage. When the graph and trained predictor remain unchanged, the system must decide which node text and image representations to retain under separate capacity limits. We formulate this decision as budgeted representation selection. Given an encoded graph, candidate node representations, and two capacities, the task selects a joint subset to preserve the classes predicted when every candidate is available. Graph propagation makes each contribution depend on the neighboring and cross modal representations already retained, while existing attribution methods usually rank candidates at a single input state. Exact studies on six graphs show that deletion scores can miss the best addition, prediction agreement often stops distinguishing candidates, and reference state gains become stale as the subset grows. Guided by these results, GraphSelect first fills both modality budgets with exact addition gains. It then recomputes removal and addition scores for the current subset and tests promising within modality exchanges with the unchanged predictor. Under a shared selection protocol, GraphSelect achieves lower selection loss than six published attribution and explanation procedures. Tests on nine trained graph and multimodal architectures further show that increasing capacity moves recovery and downstream predictions toward the corresponding full input result. At 20% capacity per modality, the mean accuracy gap is 0.10 percentage points. Together, these results show that GraphSelect selects a small joint input and yields predictions close to those of the same trained model with complete candidate input.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
multimodal graph learning, efficient inference, representation selection, subset selection, model efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_hg5UOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes GraphSelect, a representation selection framework for budget-constrained multimodal graph inference. Through an empirical study, the authors demonstrate that different candidate subsets favor different prediction targets, highlighting the relationship between candidate expressiveness and learned graph representations. Building on this observation, GraphSelect employs an iterative selection-and-screening procedure that evaluates candidate replacements and progressively refines the selected subset through recursive exchanges. Experiments across multiple multimodal graph benchmarks demonstrate strong objective recovery and robustness, particularly under restrictive capacity budgets.

Critical strengths

The authors introduce a novel problem formulation for multimodal attributed graph inference: capacity constraints are enforced per modality, node-level candidate representations (text/image vectors) act as decision units, and the goal is to retain full-input predictions. Within this setup, multi-granularity empirical analyses are provided in the paper.

Critical weaknesses
  1. The research lacks adequate motivation and in-depth analysis. Building upon the finding that different input modalities contain overlapping information, the authors put forward an algorithm for the selection of useful input signals. The authors need to highlight and empirically verify which practical benefit the proposed approach delivers: improved accuracy, higher efficiency, or better interpretability. If reduced capacity yields higher model efficiency, relevant efficiency metrics such as memory footprint, model size, and inference speed should be adopted to quantify these gains. In addition, the baselines do not include relevant works published in the past two years. The authors need to clarify the core contributions of this study and identify its true competitors.

  2. Insufficient computational complexity analysis. Although Appendix C.1 briefly discusses computational costs, a rigorous complexity analysis remains missing. In particular, the impact of recursive replacement and screening steps on the overall time complexity, number of objective evaluations, and memory overhead is not sufficiently characterized. A clearer analysis of how these costs scale with candidate pool size, selection budget, and search depth would strengthen the efficiency claims.

Questions for authors
  1. Practical motivation and baselines. What problem is this work targeting: improved accuracy, efficiency, or interpretability? Are there relevant contemporary studies published in the past two years?
  2. Objective recovery exceeding 100%. In Figure 5, GraphSAGE appears to achieve an objective recovery rate exceeding 100%. Could the authors clarify the definition and normalization of this metric and explain under what circumstances recovery can exceed 100%? Does this indicate that the selected subset outperforms the reference configuration?
  3. Modality-specific selection and cross-modal interactions. The empirical study establishes that different candidate subsets can produce substantially different prediction outcomes. However, it remains unclear how GraphSelect distinguishes the contributions of candidates from different modalities or accounts for their complementary and potentially redundant information. Could the authors elaborate on how the proposed selection mechanism captures cross-modal interactions and whether modality-aware selection could further improve its effectiveness?
7 comments

Thank you for the questions about the practical goal, computation, and cross-modal selection.

W1&Q1. Goal, measured benefit, and competitors. Our goal is to preserve near-full predictive performance with fewer retained original representations under modality budgets. In the expanded six-graph test, replacing approximately 40% of all original graph vectors yields 75.72% mean test accuracy versus 76.32% for complete input: 99.21% retained, with a 0.605 pp drop. Random obtains 71.87%. Objective recovery is 51.16%. New Sec. 5.4/Table 3 compares all methods with frozen additive predictors, seed44, 10%/50% candidate coverage, and 20% within-pool quotas; App. E.3, Tables 13-15, gives detailed results.

Budgeted long-term storage is one application: complete inputs guide planning, then selected historical vectors serve later queries. On four larger neural-pool settings (Grocery/RedditS, GCN/MMGCN, seed44, 10% coverage, 20% within-pool quotas), actual stores save 79.88% of candidate bytes and 7.87% of whole-graph representation bytes, including indices and means. GraphSelect/Random recover 86.44%/26.01%, with accuracy drops of 0.542/1.687 pp. Dense inference fills omitted slots with means. In the original small-pool resource study on shared GPUs, model size, dense input size, and peak GPU allocations were unchanged; the median selected/full-input latency ratio of 0.999 shows no consistent speedup. The benefit is persistent storage reduction with predictive information retained. Sec. 5.4 and App. E.4 add these resource measurements.

Table 1 now compares recent published ANFS [1] and GeoXGNN [2] under the same fixed predictor and whole-vector budgets on six graphs/three splits. At 20%, they recover 45.22%/43.07%, versus GraphSelect's 48.30%. We reimplemented ANFS's published permutation-importance and iterative-pruning procedure using teacher-class loss and whole-vector quotas. GeoXGNN adapts its public geometry and mask-learning pipeline with vector gates. Section 2 adds contemporary related work; App. E.2 specifies the adaptations.

W2. Complexity, search depth, and memory. Each round screens candidates and jointly evaluates shortlisted exchanges; accepted exchanges trigger fresh scores. Let NN be candidates per modality, qq the common quota, LL screen width, rr attempted rounds, and BB the query allowance. Initialization takes 2N+12N+1 trials. Each round screens at most 2N2N changes and tests at most 2p2p pairs, where p=min⁡(L,q)min⁡(L,N−q)p=\min(L,q)\min(L,N-q). Thus

Q≤min⁡{B,2N+1+r(2N+2p)}.Q\leq\min\{B,2N+1+r(2N+2p)\}.

Screening is linear in pool size, pair evaluation is quadratic in shortlist width, and rounds account for search depth. Nonlinear trials run a forward pass; additive trials update affected logits and sum cached target risks. Nonlinear search-state memory is O(Qq+N+B)O(Qq+N+B), including selected-set keys and the evaluation trace. App. C.1 now derives time/memory bounds with class count, affected-row supports, and caches. In 18 matched settings, internal Forward/GraphSelect average 0.377/0.865 s and 3,881/8,511 actual evaluations (App. E.1). At 50% coverage, GraphSelect averages 94.68 million sparse evaluations (App. E.3). This cost plans a stored subset for reuse.

Q2. Recovery above 100%. Yes, the selected subset can outperform full input on the stated objective. Recovery is

100 R(∅)−R(S)R(∅)−R(E).100\,\frac{R(\varnothing)-R(S)}{R(\varnothing)-R(E)}.

RR is cross-entropy to the full-input predicted classes; EE contains all candidates. All evaluated denominators are positive. GraphSAGE/RedditS/seed44 at 20% has reference/full/selected losses of 1.964669/1.963063/1.962647, giving 125.90%. This means greater geometric mean probability for the original classes; true-label accuracy is measured separately. Sec. 3.2 states the normalization; App. D.5 now adds this numerical example and interpretation.

Q3. Modality contributions and interactions. Each candidate is scored with both retained modalities present. An image is evaluated alongside retained text and graph context, and vice versa; separate quotas enforce each modality's budget. Joint replacement loss captures overlapping or complementary effects at common prediction targets, and an accepted exchange triggers rescoring of both modalities. Even additive logits interact through cross-entropy. SAGE [3] also motivates measuring contributions alongside other features. We clarify these conditional scores and joint tests in Secs. 4.2-4.3; Sec. 4.4 gives the additive mechanism. Learned modality-specific proposals could further improve shortlisting while retaining joint loss as the exchange criterion.

References

[1] M. Navarro et al. Adaptive Node Feature Selection for Graph Neural Networks. ICML, 2026.

[2] M. Diao et al. Local Geometry Improves Explanation Robustness for Graph Neural Networks. IJCAI, 2026.

[3] I. Covert et al. Understanding Global Feature Contributions With Additive Importance Measures. NeurIPS, 2020.

---1. I would like to confirm the target application scenario: privacy preservation, efficiency improvement, memory reduction, or accuracy gain. For a memory-reduction objective, GPU memory utilization must be adopted to enable fair evaluation against the baselines.

---2. I cannot locate the work "Adaptive Node Feature Selection for Graph Neural Networks" by M. Navarro et al. in the ICML 2026 accepted papers. Please verify this citation.

Thanks for following up.

  1. Our goal is to keep fewer node-level text/image representations while preserving performance close to full input. The intended application is storing a compact set of useful historical representations for later graph inference. For example, we can temporarily access complete representations, select which vectors to retain under a storage budget, and then use them for future queries—including new nodes whose predictions could not have been cached beforehand.

    The resource we reduce is the amount of original representation data kept in storage. GPU working memory is a separate quantity: our current implementation fills omitted slots with modality means and still uses dense inference, so we do not claim GPU-memory savings. Our comparison with baselines therefore asks which selection preserves more predictive performance at the same representation-storage budget. This captures the value of selecting useful representations while keeping less historical feature data.

  2. Here’s the official ICML 2026 proceedings entry for the cited paper.

Reviewer_1uC8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies selecting node-level text and image representations under modality budgets to preserve a fixed graph model’s predictions. It proposes GraphSelect, which initializes a subset using individual gains and refines it through screened exchanges with updated scores. Experiments on six graphs compare selection quality, while evaluations across nine architectures on two graphs report a mean accuracy drop of 0.10 percentage points when retaining 20% of candidate representations per modality.

Critical strengths

The paper is well written, with well-designed experiments and clear figures and tables. Some details still require clarification or improvement, as outlined in the questions below.

Critical weaknesses
  1. Could the authors expand the “Modality Selection and Acquisition,” “Attribution and Graph Explanation,” and “Prediction-Preserving Input Subsets” in Section 2 to discuss relevant work from year 2026? These comparisons would help readers better understand the need for the research problem and the paper’s distinct contributions.
  2. The baselines appear somewhat dated, with all published in 2024 or earlier. Could the authors include some relevant baselines from 2026 to provide a more up-to-date comparison?

Overall, I lean toward weak rejection, primarily because the baselines are dated and the practical applications of the task remain unclear. If the authors adequately address these concerns in their rebuttal, I would be open to raising my score to borderline (between 2: Weak rejection and 3: Weak acceptance).

Questions for authors
  1. My understanding is that this paper selects a subset of already encoded text and image representations under separate modality budgets to preserve a fixed graph model’s full-input predictions, while keeping the graph structure and representations outside the candidate pool unchanged. Could the authors clarify the practical usage of this task and provide concrete use cases, particularly given that the complete candidate representations and full-input predictions are already available before selection? Experimental evidence supporting these use cases would further strengthen the paper, although I understand that time constraints may make such additional analysis difficult.
  2. Could the authors clarify the complete selection and inference pipeline? Is my following interpretation correct?
    • The full graph contains 17,074 nodes, with 17,074 text vectors and 17,074 image vectors, totaling 34,148 representations.
    • Only 220 nodes form the candidate pool, contributing 220 text vectors and 220 image vectors. The other 16,854 nodes retain all 33,708 of their original representations throughout selection and inference.
    • At a 20% budget, 44 text vectors and 44 image vectors are retained from the candidate pool. The remaining 176 text vectors and 176 image vectors are replaced by modality means.
    • Consequently, the final input still contains all 17,074 nodes and 34,148 representation slots: 33,796 original vectors and 352 mean replacements.
2 comments

Thank you for the precise pipeline question and suggestions on contemporary work and practical use.

W1&W2. Recent published work and matched baselines. We added published ANFS [2] and GeoXGNN [3] comparisons to Table 1. At 20% capacity, their mean recovery is 45.22% and 43.07%, versus 48.30% for GraphSelect. These use the original six graphs, three split seeds, the same 220 candidates, full-input classes, training means, and 5%/10%/20% quotas. GraphSelect has lower teacher-class loss than both adaptations in all 54 graph/split/budget comparisons.

We reimplemented ANFS from its published permutation-importance and iterative-pruning procedure, scoring and pruning whole vectors and recomputing importance after pruning. Teacher-class loss replaces validation accuracy, and the predictor stays fixed. GeoXGNN adapts its public geometry construction, discriminative projection, regularized mask training, and final selection, replacing edge gates with whole-vector gates under the same objective and modality quotas. This compares selection under our fixed-predictor task; retraining would change the predictor whose outputs must be preserved. App. E.2 details both adaptations. New Table 3 extends all methods to 10%/50% candidate coverage on the same six graphs (seed44, 20% within-pool quotas); at 50%, GraphSelect/ANFS/GeoXGNN recover 51.16%/48.18%/42.56%.

Section 2 now expands all three requested discussions: active acquisition [1], training-time feature selection [2], and geometry/multi-scale graph explanation [3,4]. These clarify how retaining encoded vectors for a fixed predictor differs from acquiring unknown inputs, pruning during training, and explaining individual predictions.

W3&Q1. Practical goal and why complete planning input is useful. The goal is to preserve near-full predictive performance using fewer retained original representations under separate modality budgets. In the six-graph, 50%-coverage test, approximately 40% of all original graph vectors are replaced. GraphSelect achieves 75.72% mean test accuracy versus 76.32% for complete input (99.21% retained; a 0.605 pp drop), compared with 71.87% for Random. New Sec. 5.4/Table 3 reports this quality/input-reduction tradeoff; detailed results appear in App. E.3, Tables 13-15.

A concrete application is budgeted long-term storage: temporarily access complete representations to select historical vectors, then retain only the selected candidates for later queries. Cached old predictions cannot answer for a newly arriving product and its new graph edges; those predictions use historical neighborhood information [5]. We tested this on Grocery/RedditS and three splits: remove 200 test nodes and their edges before planning, retain 20% of a 1,000-node historical pool, freeze the plan, restore the new nodes/edges, and evaluate only new nodes. Objective recovery on these new nodes is 52.05% for GraphSelect versus 19.84% for Random. App. E.4 adds this future-query test and all selection controls.

Actual serialized stores provide complementary storage evidence. On four larger neural-pool settings (Grocery/RedditS, GCN/MMGCN, seed44, 10% coverage, 20% within-pool quotas), they save 79.88% of candidate bytes and 7.87% of whole-graph representation bytes, including indices and means, while GraphSelect achieves 86.44% objective recovery. The stores reconstruct the selected/mean-replaced inputs exactly. Sec. 5.4 and App. E.4 add these measurements. Together, these results support retaining predictive historical representations for budgeted storage and subsequent inference.

Q2. Complete selection and inference pipeline. Yes, your accounting for the original Grocery setting is correct. All 17,074 nodes and 34,148 vector slots remain. Of the 220 candidates, 44 text and 44 image vectors are retained; 176 per modality use training means. The other 33,708 vectors stay unchanged. The final input has 33,796 original vectors and 352 mean replacements (1.03% of slots). We first obtain full-input classes, select one shared subset, and evaluate the resulting input with the same model. Sec. 3.1 defines this within-pool budget; we corrected the sampling description in App. D.1 and added Sec. 5.4/Table 3 to test substantially broader coverage.

References

[1] L. Aronsson et al. A Survey on Active Feature Acquisition Strategies. IJCAI, 2026.

[2] M. Navarro et al. Adaptive Node Feature Selection for Graph Neural Networks. ICML, 2026.

[3] M. Diao et al. Local Geometry Improves Explanation Robustness for Graph Neural Networks. IJCAI, 2026.

[4] L. Wu et al. Multi-scale Explainer for Graph Neural Networks. ICML, 2026.

[5] W. Hamilton et al. Inductive Representation Learning on Large Graphs. NeurIPS, 2017.

Dear Reviewer 1uC8,

With the rebuttal deadline approaching, we wanted to ask whether you have had a chance to read our response.

Could you let us know if the updated baseline comparisons and clarified selection and deployment protocol address your concerns?

We are happy to provide any further clarification. Thank you for your time.

Reviewer_F88rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the problem of "Budgeted Representation Selection" in multimodal graph inference. Given a trained multimodal graph predictor and separate capacity constraints for text and image modalities, the goal is to select a subset of candidate feature vectors that aims to maximally preserve the model's predictions obtained from the full candidate input. The authors first conduct an empirical study to analyze the impact of scoring context, prediction objectives, and score updates on selection quality. Based on these findings, they propose GRAPHSELECT, an algorithm that initializes with individual gains and iteratively refines the subset through jointly evaluated screened exchanges. Furthermore, an exact sparse evaluation method is derived for additive graph predictors. Experiments across six multimodal graph datasets and nine GNN architectures demonstrate that the proposed method achieves higher mean objective recovery than various adapted attribution baselines, with relatively small drops in downstream accuracy when retaining 20% of the features.

Critical strengths

The concept of budgeted representation selection is interesting and well-motivated, highlighting the potential impact of feature redundancy in multimodal graph models. The experiments cover six multimodal graph datasets and nine different GNN/MMGCN architectures, which provides a solid foundation for the claims.

Critical weaknesses
  1. While the paper demonstrates that retaining 20% of the candidate features generally maintains downstream accuracy, the underlying mechanism for this robustness is not fully explored. Intuitively, replacing a large portion of the input with modality means alters the data distribution, which may introduce unexpected biases. For instance, if the feature space is naturally highly concentrated around the mean, the perturbation caused by mean substitution might be minimal. In such scenarios, simpler baselines like random sampling could potentially achieve comparable results, which would raise questions regarding the practical necessity of the computationally heavier joint search in GRAPHSELECT.
  2. The main comparison in Table 1 evaluates GRAPHSELECT against several complex attribution and explanation methods, however, it appears to omit a random selection baseline. Including a simple random sampling baseline is often considered a standard sanity check in feature selection tasks. If random selection yields a comparable downstream accuracy drop, the additional computational overhead of GRAPHSELECT might be difficult to justify from a cost-effectiveness perspective.
  3. The primary experiments restrict the candidate pool to a deterministic set of the first 220 nodes, whereas the full datasets contain between 15,000 and 97,000 nodes. Consequently, only a small fraction (approximately 1%) of the nodes are subject to the budget constraints, while the rest retain their full inputs. This fixed truncation may not fully reflect the combinatorial challenges inherent in global graph selection. Additionally, relying on a deterministic subset rather than randomly sampled candidate pools avoids the variance introduced by graph sampling, but it also raises potential concerns regarding selection bias. It remains somewhat unclear how the algorithm would scale or perform on randomly sampled subgraphs that are more representative of real-world large-scale scenarios.
Questions for authors
  1. Could the authors provide the performance of a random selection baseline (randomly sampling KmK_m candidates while replacing the rest with modality means)? This would help clarify whether the observed robustness is primarily driven by the GRAPHSELECT algorithm or by the inherent redundancy and distribution characteristics of the feature space.
  2. Could the authors further elaborate on the underlying reasons why the model remains robust when a large portion of the candidate inputs are replaced by modality means? For example, an analysis of the feature space variance or the redundancy among candidate embeddings would be highly valuable for substantiating the core premise of the budgeted selection problem.
3 comments

Thank you for the questions about Random selection, mean replacement, and candidate sampling.

W1&W2&Q1. Random baseline and selection benefit. Random does not match GraphSelect under the same quotas and replacements. We sample 30 independent uniform subsets without replacement per modality and average them within each setting. At 20% capacity across nine architectures, two graphs, and three splits:

MethodObjective recovery (%)Accuracy drop (pp)
All candidates replaced by means0.000.287
Random22.100.225
GraphSelect77.610.100

Recovery measures improvement in cross-entropy to full-input predicted classes; accuracy drop is full-input minus selected-input test accuracy. GraphSelect has lower teacher-class loss than Random in all 54 settings. Thus background robustness explains much of the stable hard-label accuracy, while informed selection preserves substantially more support for the model's original decisions. Random requires no search; GraphSelect averages 0.865 s in the separate 18-setting additive timing study. The selection-time computation improves prediction preservation at the same stored-vector budget. Table 1 now includes Random; App. E.3 adds these neural controls, and App. E.1 reports additive planning cost.

W1&Q2. Why mean replacement can preserve accuracy. The limited original intervention and text-feature concentration both help explain robustness. In the original Grocery setting, 352 of 34,148 vector slots are replaced (1.03%). On 4,000 sampled embeddings per graph/split, residual energy is 3.40%/4.89% for Grocery/RedditS text but 46.68%/52.83% for images. Here residual energy is mean squared distance to the training mean divided by mean squared feature norm. Mean substitution therefore makes a much smaller relative change to text than to images.

We also test dependence on the replacement reference [1]. Holding selected masks and teacher classes fixed on GCN/MMGCN, both graphs, and three splits, GraphSelect/Random accuracy drops are 0.040/0.241 pp with means and 0.229/0.422 pp with sampled training-vector replacements. Informed selection improves preservation under both replacement choices. App. E.3 now includes the concentration and replacement analyses.

W3. Candidate sampling and larger-scale selection. The implementation uses seeded random sampling, not the first nodes in dataset order. The original 220 candidates are uniform positions from a seeded random 1,000-node pool, chosen before inspecting test membership. App. D.1 now specifies this sampling procedure. Three additional pools per graph/split give 54 settings: Random/our internal Forward control/GraphSelect recover 22.58%/47.45%/47.78% at 20%. GraphSelect has lower teacher-class loss than Random in all 54 settings.

We also expanded every Table 1 method to uniformly sampled pools covering 10% and 50% of all six unchanged graphs, with frozen additive predictors, seed44, and 20% within-pool quotas. Pool sizes are 1,590-9,777 and 7,947-48,883. GraphSelect/ANFS/Random recover 48.98%/46.22%/23.03% at 10% coverage and 51.16%/48.18%/24.72% at 50%. At the latter coverage, approximately 40% of all original graph vectors are replaced, yet mean test accuracy is 75.72% versus 76.32% for complete input: 99.21% retained, with a 0.605 pp drop. Random obtains 71.87%. This shows that selected representations preserve important predictive information beyond the small original pool. New Sec. 5.4/Table 3 presents all methods; App. E.3, Tables 13-15, provides detailed budgets, controls, and per-graph results.

For randomly sampled subgraphs, we additionally test six uniform 4,000-node induced graphs, retaining 20% of representations across all surviving nodes against each subgraph's full-input teacher. GraphSelect/Random recover 41.95%/23.73%, with accuracy drops of 7.79/27.22 pp. Thus informed selection preserves substantially more predictive information than uniform retention even when the entire sampled graph is budgeted. App. E.3 reports all controls and costs for these topology-changing tests separately from the unchanged-graph comparison.

References

[1] I. Covert et al. Explaining by Removing: A Unified Framework for Model Explanation. JMLR, 2021.

Dear Reviewer F88r,

The rebuttal period will end soon, so we would appreciate your feedback on our response.

We hope the random-baseline comparisons and explanations of mean replacement and scalability have addressed your concerns. Please let us know what you think.

If you have any further questions, we would be happy to discuss them.

Thanks for your reply. The rebuttal addressed several of my concerns, especially regarding random selection and candidate sampling. I noticed that in the appendix, GraphSelect achieves 52.05% recovery, slightly below Forward (52.12%) and singleton ranking (52.75%). Since supporting future graph queries is an important practical motivation for persistent representation selection, this result raises further questions about the benefits of the additional exchange refinement. Overall, the relatively small improvements over Forward, together with the substantially higher selection cost, leave me unconvinced that the added algorithmic complexity is sufficiently justified.

Reviewer_Dk8nOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies budgeted representation selection for multimodal graph inference. It proposes GraphSelect, which refines an initial subset through screened exchanges to preserve the predictions of a trained model. Experiments on six graphs and nine model architectures evaluate selection quality and downstream prediction preservation.

Critical strengths
  1. The paper formulates a clear representation selection problem with separate budgets for different modalities.

  2. The experiments cover multiple datasets, budgets, and model architectures, with additional component analyses.

  3. The paper is generally well organized, and its figure help explain the motivation and experimental findings.

Critical weaknesses
  1. The main algorithm combines individual-gain initialization, candidate screening, and local exchange search, but the paper does not establish a sufficiently distinctive algorithmic contribution beyond this combination.

  2. On the six-graph study, GraphSelect improves mean objective recovery over Forward from 48.0% to 48.3% at 20% capacity, leaving the practical significance of the exchange stage unclear, i.e., Small gains over a strong selection baseline.

  3. The main experiments restrict a fixed pool of 220 candidate nodes while retaining representations outside that pool, so the reported 20% capacity and small accuracy drop do not establish comparable preservation when a large fraction of the entire graph’s inputs is unavailable.

Questions for authors
  1. What is the main algorithmic distinction between GraphSelect and existing greedy selection methods with local exchange, and which part contributes most to its performance?

  2. How should the small average gain over Forward be interpreted in terms of absolute prediction quality and additional computational cost?

  3. How does the method perform when the candidate pool covers a substantially larger proportion of the graph, or when the full candidate representations are unavailable before selection?

2 comments

Thank you for recognizing the formulation and experimental coverage. We address the algorithmic contribution, the Forward ablation, and candidate coverage below.

W1&Q1. Algorithmic distinction and component contribution. GraphSelect couples current-subset screening with exact joint exchanges and graph-dependent sparse evaluation. It first fills both quotas using singleton gains. It then scores removals and additions with the other retained vectors present, jointly tests shortlisted replacements, and refreshes both screens after each accepted exchange. This accounts for overlapping contributions at shared prediction targets. For additive predictors, unchanged target-loss terms cancel exactly, allowing sparse evaluation of the same objective (Secs. 4.2-4.4).

Forward is our internal construction ablation: conventional forward greedy updates addition gains but cannot revise earlier choices. Full GraphSelect starts from Static, our singleton-ranking control. At 20% capacity on six graphs/three splits, Static supplies 46.87% recovery and exchanges raise it to 48.30%: initialization contributes most recovery, while exchanges improve the quota-filled subset. At 50% candidate coverage, exchanges raise Static's recovery from 48.90% to 51.16% and test accuracy from 75.32% to 75.72%. In the 126-setting neural ablation, removing exchanges increases mean loss by 4.60e-4; freezing scores increases it by 0.76e-4. Against complete one-swap search from the same initialization, screening retains 99.7% of its mean refinement using 3.6% of its objective trials in the 18 original settings at 20%. App. E.1 adds this direct exchange comparison; App. E.3 reports the larger-pool controls.

W2&Q2. Increment over Forward and its cost. Exchanges improve support for the original decisions at the same retention budget. In the original 18 settings at 20%, Forward/GraphSelect recover 48.00%/48.30%, with a paired gain of 0.295 pp (95% CI 0.208 to 0.390) and a 1.74e-5 lower teacher-class loss. Test accuracy changes little: the gain is 0.0043 pp (CI -0.0033 to 0.0113). At 50% candidate coverage on six graphs, Forward/GraphSelect recovery is 50.76%/51.16% and mean test accuracy is 75.60%/75.72%.

Across the original 18 settings with three timing repeats, Forward/GraphSelect average 0.377/0.865 s and 3,881/8,511 actual evaluations. At 50% coverage, Forward averages 13.70 million sparse evaluations and GraphSelect 94.68 million. The tradeoff is one-time planning cost versus retained prediction quality: Forward offers a lower-cost internal construction variant, while full GraphSelect spends more computation on exchanges to obtain stronger class support and higher mean accuracy in the broader-coverage test under the same storage budget. App. E.1 adds the paired quality/runtime analysis; App. E.3 reports the larger-pool costs.

W3&Q3. Larger coverage and unavailable inputs. GraphSelect preserves 99.21% of full-input test accuracy while replacing approximately 40% of all original graph vectors. We expanded every Table 1 method to uniformly sampled pools covering 10%/50% of all six unchanged graphs, with frozen additive predictors, split seed44, and 20% within-pool quotas:

Pool coverageCandidate nodesGraphSelect recovery (%)ANFSRandom
10%1,590-9,77748.9846.2223.03
50%7,947-48,88351.1648.1824.72

At 50% coverage, mean test accuracy is 75.72%, versus 76.32% for complete input (a 0.605 pp drop), and 71.87% for Random. These retained representations preserve important predictive information under substantially broader removal. New Sec. 5.4/Table 3 presents the comparison; App. E.3, Tables 13-15, gives detailed results. The original 0.10 pp accuracy drop refers to 220-node pools with outside inputs retained.

GraphSelect addresses temporary complete access followed by budgeted retention: complete candidate vectors guide planning, after which only the selected candidate vectors are stored. If vectors are initially unavailable, acquisition [1] or graph-based imputation [2] could supply planning inputs; preservation would then be relative to that completed input, with fidelity to unknown original predictions depending on the upstream stage. App. D.8 states this information assumption. The retained historical vectors can support later queries: App. E.4 demonstrates prediction for nodes absent during planning, which cached planning predictions cannot provide.

References

[1] L. Aronsson et al. A Survey on Active Feature Acquisition Strategies. IJCAI, 2026.

[2] D. Malitesta et al. Training-Free Graph-Based Imputation of Missing Modalities in Multimodal Recommendation. IEEE TKDE, 2026.

Dear Reviewer Dk8n,

As the rebuttal period is coming to an end, we wanted to follow up on our response.

Could you let us know whether the comparison with Forward and the larger-scale results address your concerns?

We would be happy to answer any further questions. Thank you for your time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.