PaperlayerView exact revision on arXiv

Source-linked AI summary

MOVE: Multimodal Open-world Verification and Expansion for Graph Learning

Zekai Chen, Jiayang Xing, Xun Wu, Miao Zhang, Xunkai Li, Kairui Yang, Zhengyu Wu, Xu Wang, Rong-Hua Li, Guoren Wang

arXiv:2610.00268v1cs.LG

TL;DR

Existing approaches do not determine whether current classes can explain unknown nodes or whether generated classes are reliable enough to add. MOVE identifies unresolved nodes through visual, textual, and graph evidence, verifies multimodal-LLM candidates, and selectively expands the class space. It reports an 11.87% average improvement in unknown-concept semantic similarity and best performance across four benchmarks and two downstream tasks.

  • Problem

    Open-world multimodal graph learning must determine whether existing classes can explain post-deployment nodes and whether generated class descriptions are reliable enough to justify expanding the class space.

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

  • Method

    MOVE jointly uses visual tokens, textual tokens, and graph context to identify unresolved nodes, ground multimodal-LLM class candidates, and selectively expand the class space.

    Source: §1 · p. 2, §5.1 · p. 4

  • Results

    MOVE improves unknown-concept semantic similarity by 11.87% on average and achieves best performance across four multimodal attributed graph benchmarks and two downstream tasks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Open-world multimodal graph learning can be treated as progressive knowledge evolution from identifying unresolved observations to discovering and selectively incorporating reliable concepts.

    Source: §2 · p. 2, §7 · p. 10

Abstract

from arXiv · show

Multimodal graph learning faces a fundamental challenge: new classes may emerge after deployment, while models are trained with a fixed label space. Existing approaches typically detect unknown nodes and use LLMs to generate candidate class descriptions, but they do not determine whether existing classes are insufficient to cover these nodes or whether a generated class is reliable enough to expand the class space. Our empirical study reveals three challenges: multimodal information beyond individual modalities is required for unknown-node identification, LLM-generated class descriptions may not fully capture multimodal class characteristics, and directly adding candidate classes can introduce redundant categories. Based on these observations, we propose MOVE, a multimodal open-world class verification and expansion framework. MOVE identifies nodes that cannot be assigned to existing classes by jointly considering visual tokens, textual attributes, and graph context, leverages a multimodal LLM to generate candidate classes, and selectively expands the class space only when candidates are consistently supported by multimodal evidence without introducing unnecessary categories. Experiments demonstrate that MOVE achieves an average improvement of 11.87\% across unknown recognition, open-domain annotation, and downstream graph learning tasks.

1 INTRODUCTION

Open-world multimodal graph learning must decide both when existing classes cannot explain a node and when a proposed class merits admission. MOVE unifies multimodal unknown-node identification, candidate induction, and selective expansion.

1 INTRODUCTION

  • Unknown-node discovery can fail when a node resembles known classes in one modality but cannot be explained by visual, textual, and graph evidence jointly.The introduction frames this as a reason not to rely on similarity in a single modality.Source: §1 · p. 1
  • Plausible multimodal-LLM descriptions are only candidates, since different visual, textual, and neighboring-node clues can support competing class descriptions.Descriptions should be mapped back to multimodal representations and checked against the corresponding nodes.Source: §1 · p. 2
  • Adding a candidate that fits its generating observations can still split an existing class unnecessarily and create redundant categories.The introduction motivates validating candidates beyond the observations used to generate them.Source: §1 · p. 2
  • MOVE jointly models visual tokens, textual tokens, and graph context to identify nodes that cannot be assigned to existing classes, then grounds and selectively admits candidate classes.A multimodal LLM proposes descriptions, but candidates are checked against multimodal evidence and filtered for redundancy and interference.Source: §1 · p. 2
  • MOVE frames the problem as deciding when the class space is insufficient and when a new class should be introduced, with multimodal LLMs serving as candidate generators rather than final decision makers.Experiments across four multimodal attributed graph benchmarks and two downstream tasks report best performance and a 11.87% average improvement in unknown-concept semantic similarity.Source: §1 · p. 2

2 PROBLEM FORMULATION

Open-world multimodal graph learning is formulated as progressive knowledge evolution: identify observations unresolved by current concepts, infer coherent concepts, and selectively incorporate reliable ones.

2 PROBLEM FORMULATION

  • The graph contains visual and textual node attributes together with graph topology, and only a labeled subset is available during training.Training labels belong to the known concept set; after deployment, remaining nodes may represent known or previously unseen concepts.Source: §2 · p. 2
  • Given the graph and current concept knowledge, the learner must identify observations existing concepts cannot explain while preserving known-class recognition.Source: §2 · p. 2
  • The formulation requires inferring coherent concepts for discovered unknown observations, then selectively incorporating reliable concepts to update the knowledge state.The paper describes this as a progression from knowledge insufficiency through semantic discovery to knowledge evolution.Source: §2 · p. 2

3 RELATED WORK

Prior open-world graph work moves from unknown-node rejection toward novel-class discovery and LLM-assisted annotation and updating, while multimodal graph methods largely assume predefined concepts. MOVE addresses evolving class spaces.

3 RELATED WORK

  • Open-world graph learning progressed from rejecting nodes beyond known labels to novel-class discovery and OGA's LLM-assisted unknown recognition, semantic annotation, and model updating.Earlier work explored uncertainty, neighborhood information, and structure-aware decision boundaries.Source: §3 · pp. 2–3
  • Existing methods separate discovery, annotation, and updating with different criteria, whereas MOVE unifies these decisions under a shared compression-based knowledge-evolution principle.Source: §3 · p. 3
  • Multimodal graph learning and foundation models improve alignment and transferable representations, but mainly focus on existing semantic spaces and assume concepts are predefined.MOVE instead considers when the semantic space becomes insufficient and whether new concepts merit incorporation.Source: §3 · p. 3

4 EMPIRICAL STUDY

The empirical study examines three potential failure points in open-world multimodal graph learning: joint unknown-node identification, evidence for generated concepts, and reliable class expansion.

4 EMPIRICAL STUDY

  • The study tests whether unknown concepts require joint multimodal explanation, semantic proposals are reliably grounded, and plausible concepts deserve expansion.Source: §4 · p. 3

4.1 MULTIMODAL ASSIGNMENT FAILURE

  • 13.8% of unknown nodes remain close to known concepts in at least one modality but show larger joint explanation gaps.This supports identifying novelty through multimodal explanation failure rather than isolated anomalies.Source: §4.1 · p. 4

4.2 AMBIGUOUS CLASS INDUCTION

  • Only 19.4% of linguistically plausible candidate concepts receive consistent multimodal evidence support.The study motivates verifying generated hypotheses against multimodal evidence rather than treating semantic generation alone as sufficient.Source: §4.2 · p. 4

4.3 UNRELIABLE CLASS EXPANSION

  • Generic concepts reduce local fitting error by 1.9%, but their gain decreases on independent evidence.The study concludes that expansion should test transferable explanatory value rather than improved fit on the observations used to generate a candidate.Source: §4.3 · p. 4

5 METHODOLOGY

MOVE couples multimodal unknown-node identification, evidence-grounded candidate class induction, and selective class expansion in one framework.

5.1 OVERVIEW

  • MOVE’s three coupled stages identify nodes existing classes cannot explain, verify candidate classes with multimodal evidence, and selectively expand the class space.Expansion also considers redundant categories and interference with existing classes.Source: §5.1 · p. 4

5.2 UNCERTAINTY-AWARE MULTIMODAL CLASS CODING

  • MOVE identifies unknown nodes by jointly evaluating visual, textual, and graph-context information rather than relying on similarity in one modality.High coding cost indicates that existing classes cannot represent a node; only identified unknown nodes are used to discover classes, while pending nodes provide supporting evidence.Source: §5.2 · p. 5

5.3 EVIDENCE-GROUNDED CLASS INDUCTION

  • A multimodal LLM proposes candidate descriptions, which MOVE grounds in a shared semantic space and checks against multimodal evidence.Proposal and validation subsets separate candidate generation from testing whether candidates generalize beyond the observations used to generate them.Source: §5.3 · pp. 5–6

5.4 SELECTIVE CLASS EXPANSION

  • MOVE admits a candidate only when it improves class assignment on validation evidence while controlling redundancy and interference with existing-node assignments.Validation filters candidates that fit only the generation nodes; the admission decision is based on reliable improvement.Source: §5.4 · p. 6

6 EXPERIMENTS

Across unknown-class rejection, annotation, and downstream tasks, MOVE performs strongly against compared methods. Additional experiments examine component contributions, robustness, efficiency, convergence, and scalability.

6.1 EXPERIMENTAL SETUP

  • Experiments span four multimodal attributed graphs and evaluate unknown-class rejection, unknown-class annotation, and downstream graph- and modality-level tasks.The comparisons include OOD detection, OOD annotation, multimodal OOD, and open-world methods.Source: §6.1 · p. 7, §6 · p. 7

6.2 PERFORMANCE COMPARISON (Q1)

  • MOVE achieves top known-class recognition, strong unknown-node rejection, the best generated-label similarity pattern, and leading downstream performance across the evaluated datasets.It has the best known-class Accuracy on all four datasets, and its generated concepts support node classification and modality matching.Source: §6.2 · pp. 7–8, Table 4 · p. 8

6.3 ABLATION ANALYSIS (Q2)

  • Removing HCV or CSU reduces Reddit-S node-classification Accuracy by more than 18 percentage points; CDM and GCE mainly benefit unknown-class rejection.HCV and CSU are especially important for downstream learning.Source: §6.3 · p. 8, Table 5 · p. 8

6.4 ROBUSTNESS ANALYSIS (Q3)

  • MOVE remains stable across complexity controls and key hyperparameters, while default η = 0.5 provides a robust trade-off between G-to-U and K-to-G similarity.On Grocery, it maintains strong Coverage and Precision as the unknown-node ratio rises from 10% to 80%, even as known-class supervision becomes more limited.Source: §6.4 · pp. 8–9, Figure 4 · p. 9, Figure 5 · p. 9

6.5 EFFICIENCY COMPARISON (Q4)

  • MOVE has the lowest annotation-stage runtime across datasets, runs 14.1×–18.1× faster than the fastest baseline, and uses only 3–25 LLM calls.The MDL/UCR gate and compact candidate grouping avoid unnecessary queries by validating coherent candidate regions before expansion.Source: §6.5 · p. 9, Figure 6 · p. 9

6.6 CONVERGENCE AND SCALABILITY ANALYSIS (Q5)

  • MOVE achieves the highest post-annotation NC accuracy at every training-progress point, with overall improvement as training proceeds.Figure 7 compares MOVE and annotation-capable baselines across normalized upstream training progress.Source: §6.6 · p. 9, Figure 7 · p. 10
  • At full scale, runtime remains below 4.2 seconds and peak GPU memory below 1.5 GiB; Accuracy is 37.60%–57.27% across complete class configurations.Accuracy generally decreases as the number of classes increases.Source: §6.6 · p. 9

7 CONCLUSION

MOVE treats open-world multimodal graph learning as progressive knowledge evolution: it identifies unresolved nodes, induces candidate concepts, and selectively expands the class space. Its diagnostic study finds that joint multimodal evidence and independent support checks matter for deciding whether candidates should be accepted.

7 CONCLUSION

  • MOVE identifies unresolved observations through multimodal coding, induces candidate concepts with evidence grounding, and selectively adds reliable, non-redundant concepts to the evolving class space.The conclusion reports improvements in unknown-class recognition, semantic annotation, and downstream graph learning.Source: §7 · p. 10

A EMPIRICAL STUDY IN DETAIL

  • The diagnostic study isolates three failure modes and fixes thresholds using known-class data before evaluating candidates on independent unknown-class evidence.Unknown-class identities are not used for region discovery, candidate generation, selection, threshold calibration, or support decisions.Source: A EMPIRICAL STUDY IN DETAIL · p. 11, §A.1 · p. 11

A.2 OBS. 1: CROSS-MODAL EXPLANATION GAP

  • Across four datasets, 11.7% of unknown test nodes and 9.9% of known test nodes were single-source familiar but jointly unexplained.The unknown/known rates were higher on each dataset: Toys 13.7%/10.0%, Grocery 13.4%/9.4%, Movies 15.2%/10.1%, and Reddit-S 9.9%/6.2%.Source: §A.2 · p. 12

A.3 OBS. 2: MULTIMODAL EVIDENCE AND LINGUISTIC PLAUSIBILITY

  • For each unresolved region, Qwen3-VL-Flash generates five descriptions from representative visual and textual evidence; graph context is reserved for verification.The candidate descriptions are encoded with the CLIP ViT-L/14 text encoder.Source: §A.3 · p. 12
  • Only 6 of 31 highly plausible candidates met all three multimodal support conditions, a reported support rate of 19.4%.The study uses proposal and validation pools formed from disjoint unknown-node splits, separating candidate generation from independent testing.Source: §A.1 · p. 11, §A.3 · p. 13

A.4 OBS. 3: PROPOSAL FIT AND INDEPENDENT EXPANSION EVIDENCE

The study tests whether proposal-set reconstruction gains justify adding a candidate class. It compares language-based candidates and controls on proposal evidence and independent validation evidence.

A.4 OBS. 3: PROPOSAL FIT AND INDEPENDENT EXPANSION EVIDENCE

  • The four candidate constructions are P-selected, Generic, Swapped, and Centroid, representing proposal-based selection, broad semantics, region-mismatched semantics, and direct local fitting.Centroid candidates are constructed from modality-specific proposal centroids without natural-language semantics.Source: §A.4 · p. 13
  • Locally adapted Generic candidates gain 1.9% compression on proposal evidence but only 0.8% on independent validation evidence.Average proposal-to-validation gain reductions are 6.36 percentage points on Movies and 5.61 percentage points on Toys.Source: §A.4 · p. 14
  • Proposal-set improvement alone is not a reliable admission rule because extra representational capacity can improve local reconstruction without transferable explanatory value.The same candidate is evaluated on the proposal region and its independent validation region.Source: §A.4 · p. 14

B METHODOLOGY IN DETAILS

MOVE encodes visual, textual, and topology-conditioned graph evidence, then uses that shared multimodal information to identify unresolved nodes, propose grounded classes, and decide which candidates to admit. Admission combines independent validation with redundancy, complexity, and interference controls.

B.1 MULTIMODAL GRAPH ENCODING

  • MOVE encodes visual and textual inputs separately, fuses them, and propagates the fused representation over graph topology to form neighborhood-aware context.The resulting visual, textual, and graph-context representations feed uncertainty-aware class coding.Source: §B.1 · p. 14

B.2 UNCERTAINTY-AWARE MULTIMODAL CLASS CODING

  • Node-specific modality distributions and reliability weights let MOVE account for uncertainty, while class compatibility and cross-modal disagreement jointly determine assignment cost.Lower-uncertainty modalities receive larger reliability weights; pending nodes do not initiate new classes.Source: §B.2 · pp. 14–15

B.3 EVIDENCE-GROUNDED CLASS INDUCTION

  • MOVE groups unknown nodes by their fused evidence distributions, gives the MLLM multimodal evidence to propose descriptions, and treats those descriptions as proposals rather than admission decisions.Proposal and validation subsets are disjoint; the validation subset is withheld from candidate construction.Source: §B.3 · p. 16
  • A candidate prior is updated with pooled proposal evidence to form a grounded candidate distribution, but proposal-set support is not an admission probability.The candidate prior expresses the MLLM-generated description's position in the shared latent space before proposal evidence is observed.Source: §B.3 · pp. 16–17

B.4 SELECTIVE CLASS EXPANSION

  • MOVE admits a candidate only when its held-out gain outweighs redundancy, complexity, and interference costs; accepted candidates are processed sequentially against the updated class space.The held-out gain uses a one-sided lower confidence bound, and groups must pass an unknown-anchor evidence gate to become eligible for admission.Source: §B.4 · pp. 18–19

B.5 TRAINING AND DEPLOYMENT PROCEDURE

MOVE trains its coding model using labeled known-class nodes, then applies it to unlabeled deployment nodes and uses separate proposal and validation subsets for candidate construction and admission. Its data flow connects multimodal encoding, unknown-node identification, candidate induction, and selective expansion.

B.5 TRAINING AND DEPLOYMENT PROCEDURE

  • The trainable encoders, distribution heads, and known-class representations are optimized only on labeled known-class training nodes, without unknown-class labels.At deployment, only high-confidence unknown nodes seed discovery, while candidate admission uses disjoint validation subsets and a trusted old-class buffer.Source: §B.5 · p. 19
  • The deployment flow moves from topology-conditioned multimodal representations to unresolved-node coding, grounded candidate induction, and selective expansion.Expansion filters for candidates that are sufficiently general, non-redundant, and non-interfering.Source: §B.5 · p. 19

C THEORETICAL ANALYSIS

  • The theoretical analysis examines whether compression-based admission distinguishes reusable concepts from explanations that improve only local fitting.It frames the analysis around MOVE’s counterfactual knowledge-evolution criterion.Source: C THEORETICAL ANALYSIS · p. 19

C.1 CONSISTENCY OF COMPRESSION-BASED CONCEPT ADMISSION

MOVE’s admission analysis formalizes when a candidate concept should reduce coding cost enough to justify expanding the codebook, and how finite validation evidence affects that decision. Its multimodal coding analysis shows when adding a modality can separate unexplained from explainable observations.

C.1 CONSISTENCY OF COMPRESSION-BASED CONCEPT ADMISSION

  • MOVE’s ideal admission rule accepts a candidate when its expected explanatory gain exceeds the additional knowledge complexity, while its empirical score uses finite validation evidence.The candidate’s population compression gain is defined over unresolved observations, with coding cost measured by MOVE’s conditional coding cost.Source: §C.1 · p. 20
  • Theorem 1 bounds the probability of an incorrect concept-admission decision under bounded coding gains and independently drawn validation samples; the error probability decreases as validation evidence increases.The analysis concludes that the probability of accepting a spurious concept or rejecting a genuine one decreases exponentially with independent validation evidence.Source: §C.1 · p. 20

C.2 CONSISTENCY OF UNCERTAINTY-AWARE MULTIMODAL CODING

  • The coding analysis distinguishes explainable observations, whose evidence sources remain close to an existing concept, from unexplained observations with a non-zero multimodal mismatch margin.The concept-conditioned energy uses evidence distributions for visual, textual, and graph modalities.Source: §C.2 · p. 21
  • Theorem 2 shows that adding a modality increases the coding-cost gap between unexplained and explainable observations when its nonnegative increments satisfy the stated conditions.For unexplained observations, mismatch of at least δr′ across classes carrying total assignment mass ρ yields a gap increase bounded by the theorem; the same bounds hold in expectation when conditions hold almost surely.Source: §C.2 · p. 21

D EXPERIMENT IN DETAILS

MOVE is evaluated on four multimodal attributed graph datasets under an open-world protocol, with tasks spanning unknown-node rejection, class annotation, and downstream graph learning. The experimental design also compares representative baselines and ablates four functional components.

D EXPERIMENT IN DETAILS

  • MOVE is tested on Toys, Grocery, Movies, and Reddit-S, which cover product, multimedia recommendation, and social graph scenarios with multimodal attributes and relations.The evaluation includes textual attributes, visual content, and graph connections across these datasets.Source: D EXPERIMENT IN DETAILS · p. 22
  • The protocol treats 50% of classes as known during training and the remaining 50% as unknown at evaluation, then compares unannotated, MOVE-annotated, and ground-truth-annotated graphs downstream.Training uses only known-class nodes; the model must recognize known nodes, identify unknown nodes, infer potential classes, and decide whether to incorporate new classes.Source: D EXPERIMENT IN DETAILS · p. 22
  • MOVE is compared with OOD detection, structural open-world, multimodal open-world, and recent topology-aware open-world methods; methods lacking native annotation or expansion are evaluated only on supported tasks.OpenWGL and ORAL receive an LLM-based semantic-label adaptation for annotation metrics, without changing their original unknown-node predictions.Source: D EXPERIMENT IN DETAILS · p. 22
  • The three evaluation perspectives are unknown-class rejection, unknown-class annotation, and downstream graph learning, with metrics covering known accuracy, unknown coverage and precision, label similarity, classification accuracy, and zero-shot modality matching.For annotation, higher G-to-U similarity indicates better alignment with unknown labels, while lower K-to-G similarity indicates fewer redundant expansions; downstream classification uses unannotated and ground-truth-labeled graphs as lower and upper bounds.Source: D EXPERIMENT IN DETAILS · p. 23
  • The ablations test cross-modal disagreement modeling, held-out candidate validation, graph-context encoding, and class-space updates by removing each component in turn.The variants respectively omit modality-disagreement evidence, held-out generalization testing, graph-context evidence, or incorporation of admitted classes into the evolving class space.Source: D EXPERIMENT IN DETAILS · p. 23

Related papers

Loading 2610.00268v1…