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

cs.LGSep 24, 2026

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

Authors: Zekai Chen, Jiayang Xing, Xun Wu, Miao Zhang, Xunkai Li, Kairui Yang, Zhengyu Wu, Xu Wang,

Organizations: Beijing Institute of Technology · Shandong University

Abstract

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.

Figures & tables

Figure 1: Cross-modal explanation gaps. The panels compare explanation gaps between known and unknown nodes with their cumulative distributions.

Figure 2: Semantic proposal ambiguity and class expansion. (a–b) Candidate evidence on proposal set

P

and validation set

V

; the in-panel statistics report multimodal support consistency on

V

. (c–d) Compression gains on proposal and validation evidence under different adaptation settings. Error bars denote standard errors across discovered regions.

Table 4

Category	Method	Semantic Label Quality (G-to-U $\uparrow$ / K-to-G $\downarrow$ )
Category	Method	Toys	Grocery	Reddit-S	Movies
	ORAL	53.17 $\pm$ 0.25 / 58.54 $\pm$ 1.11	58.42 $\pm$ 0.90 / 65.17 $\pm$ 0.78	79.40 $\pm$ 2.31 / 83.74 $\pm$ 0.76	60.96 $\pm$ 1.52 / 73.71 $\pm$ 0.86
OOD Annotation	OpenWGL	48.51 $\pm$ 3.31 / 60.83 $\pm$ 1.58	55.21 $\pm$ 0.93 / 67.25 $\pm$ 1.58	78.47 $\pm$ 3.83 / 83.81 $\pm$ 0.32	60.88 $\pm$ 0.31 / 73.22 $\pm$ 0.54
	OGA	53.86 $\pm$ 0.62 / 58.22 $\pm$ 0.86	58.78 $\pm$ 0.92 / 63.73 $\pm$ 0.66	79.46 $\pm$ 1.86 / 85.97 $\pm$ 1.08	60.01 $\pm$ 0.38 / 72.80 $\pm$ 0.58
MM-OOD	AHM	53.53 $\pm$ 2.70 / 60.64 $\pm$ 1.38	56.09 $\pm$ 1.08 / 67.10 $\pm$ 0.79	81.29 $\pm$ 0.73 / 82.33 $\pm$ 1.01	62.21 $\pm$ 0.58 / 73.29 $\pm$ 0.52
	CFC	57.00 $\pm$ 7.33 / 71.88 $\pm$ 12.48	60.64 $\pm$ 7.22 / 76.80 $\pm$ 11.70	77.30 $\pm$ 8.55 / 84.07 $\pm$ 6.95	64.50 $\pm$ 5.44 / 82.32 $\pm$ 8.74

Table 3: Semantic label quality in UCA. Each item is expressed as generated-to-unknown (G-to-U) similarity (

\uparrow

) / known-to-generated (K-to-G) similarity (

\downarrow

Category	Method	Toys		Grocery		Reddit-S		Movies
Category	Method	NC (Acc.)	MM	NC (Acc.)	MM	NC (Acc.)	MM	NC (Acc.)	MM
Reference	Lower bound	39.44 $\pm$ 0.55	-	32.38 $\pm$ 0.67	-	39.49 $\pm$ 1.11	-	39.57 $\pm$ 0.67	-
	ORAL	41.68 $\pm$ 1.98	79.52 $\pm$ 2.69	32.05 $\pm$ 0.79	76.74 $\pm$ 2.89	53.57 $\pm$ 2.94	68.16 $\pm$ 6.32	41.70 $\pm$ 0.68	49.25 $\pm$ 9.74
OOD Annotation	OpenWGL	39.70 $\pm$ 0.72	11.32 $\pm$ 2.69	29.85 $\pm$ 0.26	22.99 $\pm$ 6.84	43.09 $\pm$ 2.87	55.09 $\pm$ 1.44	42.26 $\pm$ 0.51	17.93 $\pm$ 2.17
	OGA	42.57 $\pm$ 0.55	72.70 $\pm$ 3.42	36.74 $\pm$ 1.21	83.76 $\pm$ 4.38	47.38 $\pm$ 4.33	82.61 $\pm$ 1.35	41.81 $\pm$ 0.60	38.77 $\pm$ 9.90
MM-OOD	AHM	38.58 $\pm$ 0.75	66.88 $\pm$ 6.41	29.57 $\pm$ 0.67	32.26 $\pm$ 1.77	50.24 $\pm$ 1.35	55.15 $\pm$ 8.36	42.16 $\pm$ 0.55	29.82 $\pm$ 4.05

Table 4: Downstream performance after UCA on node classification (NC) and zero-shot modality matching (MM) (

\%

\uparrow

). For NC, the lower bound uses no unknown-label annotation and the upper bound uses ground-truth unknown labels.

Variants	Toys		Grocery		Movies		Reddit-S
Variants	UCR (Cov./Prec.)	NC (Acc.)	UCR (Cov./Prec.)	NC (Acc.)	UCR (Cov./Prec.)	NC (Acc.)	UCR (Cov./Prec.)	NC (Acc.)
w/o CDM	70.65 / 80.68	44.66	62.34 / 88.73	32.49	36.89 / 29.79	45.59	92.31 / 91.64	52.45
w/o HCV	69.65 / 80.23	40.01	62.39 / 88.85	32.32	35.76 / 30.33	44.29	91.74 / 92.22	38.99
w/o GCE	68.39 / 80.55	44.82	62.25 / 88.78	36.77	34.48 / 30.42	45.86	86.23 / 92.42	53.12
w/o CSU	-/-	40.01	-/-	32.32	-/-	44.84	-/-	39.03
MOVE (full)	71.02 / 87.62	46.65	63.98 / 90.02	37.60	38.81 / 34.60	46.80	93.73 / 92.78	57.27

Table 5: Ablation study of MOVE on four datasets. UCR reports Coverage/Precision, and NC reports post-annotation GCN node-classification Accuracy (%).

Panel of Figure 4 — Figure 4: Hyperparameter robustness of MOVE. (a)–(b) Post-annotation NC accuracy under different knowledge-complexity penalty $\lambda$ and conditional semantic-complexity weight $\alpha$ . (c) Relative drop in post-annotation NC accuracy under changes to the semantic grounding weight $\beta$ . (d) Semantic label quality under changes to the unknown-anchor evidence threshold $\eta=\texttt{min\_unknown\_anchor\_fraction}$ ; solid and dashed lines denote G-to-U and K-to-G similarity, respectively.

Multimodal Graph Learning

Multimodal Graph Learning combines graph structure with text, images, signals, and other modalities for prediction, retrieval, and reasoning.

See all 110 papers

Mario: Multimodal Graph Reasoning with Large Language Models
Mar 5, 2026Yuanfu Sun, Kang Li, Pengkang Guo +2LLM Reasoning with Graphs Multimodal Reasoning
New York University Shanghai · New York University · Tsinghua University +1
Where LLM Annotators Fail: Label-Free Learning on Graphs with LLMs
May 27, 2026Safal Thapaliya, Jiatan Huang, Chuxu ZhangLLM-Assisted Annotation Text-Attributed Graph Learning
University of Connecticut, USA
GraphVLM: Benchmarking Vision Language Models for Multimodal Graph Learning
Mar 9, 2026Jiajin Liu, Dongzhe Fan, Chuanhao Ji +2Multimodal Graph Learning Multimodal Model Evaluation
NYU Shanghai · New York University · East China Normal University +1

Mar 5, 2026J/K move · Enter open · S save

Mario: Multimodal Graph Reasoning with Large Language Models

Yuanfu Sun, Kang Li, Pengkang Guo, Jiajin Liu+1

New York University Shanghai · New York University · Tsinghua University+1

LLM Reasoning with Graphs Multimodal Reasoning Multimodal Graph Learning Multimodal Large Language Models

Open paper AskPDF arXiv

Recent advances in large language models (LLMs) have opened new avenues for multimodal reasoning. Yet, most existing methods still rely on pretrained vision-language models (VLMs) to encode image-text pairs in isolation, ignoring the relational structure that real-world multimodal data naturally form. This motivates reasoning on multimodal graphs (MMGs), where each node has textual and visual attributes and edges provide structural cues. Enabling LLM-based reasoning on such heterogeneous multimodal signals while preserving graph topology introduces two key challenges: resolving weak cross-modal consistency and handling heterogeneous modality preference. To address this, we propose Mario, a unified framework that simultaneously resolves the two above challenges and enables effective LLM-based reasoning over MMGs. Mario consists of two innovative stages. Firstly, a graph-conditioned VLM design that jointly refines textual and visual features through fine-grained cross-modal contrastive learning guided by graph topology. Secondly, a modality-adaptive graph instruction tuning mechanism that organizes aligned multimodal features into graph-aware instruction views and employs a learnable router to surface, for each node and its neighborhood, the most informative modality configuration to the LLM. Extensive experiments across diverse MMG benchmarks demonstrate that Mario consistently outperforms state-of-the-art graph models in both supervised and zero-shot scenarios for node classification and link prediction. The code will be made available at https://github.com/sunyuanfu/Mario.

Abstract

Multimodal Graph Learning

Explore similar work

Mario: Multimodal Graph Reasoning with Large Language Models

Where LLM Annotators Fail: Label-Free Learning on Graphs with LLMs

GraphVLM: Benchmarking Vision Language Models for Multimodal Graph Learning