No-Free-Graph: Learning When Multimodal Data Should Be Graphified

Zekai Chen; Kai Hu; YuXin Zeng; Xunkai Li; Xun Wu; Yinlin Zhu; Zhengyu Wu; Xu Wang

cs.LGOct 2, 2026

No-Free-Graph: Learning When Multimodal Data Should Be Graphified

Authors: Zekai Chen, Kai Hu, YuXin Zeng, Xunkai Li, Xun Wu, Yinlin Zhu, Zhengyu Wu, Xu Wang,

Organizations: Beijing Institute of Technology · Sun Yat-sen University · Shandong University

Abstract

Multimodal graph learning has recently emerged as an effective paradigm for in corporating inter-entity relationships into multimodal representations. Existing studies have made substantial progress on how to construct and optimize graphs, but rarely consider a more fundamental question: whether additional relational structures should be introduced for a given dataset and task. Through empirical studies across diverse datasets, tasks, and graph constructors, we reveal that graphification is not consistently beneficial: introducing relational structures can provide substantial improvements in some cases, while offering limited or even negative gains. This observation motivates a new perspective that graph construction should be treated as a selective decision based on its expected utility rather than a default preprocessing step. To address this issue, we propose MAG-SCOUT, a pre-construction graph assessment framework that estimates whether introducing graph structures is beneficial before generating the complete topology. MAG-SCOUT collects limited relational evidence, analyzes its potential taskspecific contribution, and estimates the expected utility of graphification together with construction cost to make a build-or-skip decision. Extensive experiments across six multimodal datasets, three downstream tasks, and diverse graph constructors demonstrate that MAG-SCOUT effectively identifies when graph structures should be introduced, saving 33.1% of task-macro graph work while retaining 96.7% of held-out positive-gain mass under the pre-registered floor.

Figures & tables

Constructor	Node classification (Acc)		Link prediction (AUC)		Cross-modal retrieval (R@5)
	Toys	Grocery	Bili Music	DY	QB	Bili Cartoon
kNN-GCN	+0.58 ±0.31	+2.25 ±0.30	-4.17 ±1.34	-3.77 ±0.61	-3.65 ±2.03	-0.08 ±2.54
MM-kNN-GCN	+0.92 ±0.36	+1.93 ±0.08	-3.89 ±1.27	-2.39 ±0.49	+0.33 ±0.82	-0.34 ±1.34
AutoG	+4.26 ±0.19	+2.92 ±0.16	-0.87 ±0.49	-3.80 ±0.62	-2.41 ±1.14	+1.56 ±0.96
AutoGraph	+7.27 ±0.60	+6.79 ±0.60	+2.02 ±0.49	-2.13 ±1.41	-3.26 ±0.70	-0.34 ±1.37
auGraph	+5.11 ±0.29	+4.97 ±0.27	+1.23 ±0.92	-2.81 ±1.08	-4.31 ±1.83	-0.30 ±1.26

Table 1: GraphGain relative to RawOnly across six multimodal benchmarks, in percentage points (

\Delta\equiv 0

). Cells report five-seed means with standard deviations. All nine constructors are included. The Average row is their unweighted mean on each dataset.

Figure 1: Overview of MAG-Scout : (1) Relational encoding on $\mathcal{P}$ yields compact sketch $\mathcal{S}_{B}$ ; (2) Tri-bottleneck reasoning ( $\mathbf{e}_{N},\mathbf{e}_{C},\mathbf{e}_{U}$ ) estimates value $\mu_{V}$ and scale $\sigma_{V}$ ; (3) Cost-aware gating uses calibrated scale $\tilde{\sigma}_{V}$ to render Build/Skip decisions.

Panel of Figure 2 — Figure 2: Macro prediction quality across five methods and three task families on the 13 parent sources. Panels report Spearman correlation, Kendall correlation, and gain MAE.

Predictor	Spearman rank correlation ( $\rho\uparrow$ )			Kendall rank correlation ( $\tau\uparrow$ )			Gain error ( $\text{MAE}\downarrow$ )
	NC	LP	CMR	NC	LP	CMR	NC	LP	CMR
MAG-Scout	0.417 ±0.05	0.383 ±0.06	0.276 ±0.06	0.362 ±0.03	0.331 ±0.03	0.253 ±0.08	1.63 ±0.17	6.83 ±0.45	3.97 ±0.29
NetInfoF	0.358 ±0.11	0.429 ±0.08	0.099 ±0.13	0.318 ±0.07	0.295 ±0.06	0.074 ±0.06	2.14 ±0.24	8.48 ±1.53	5.22 ±0.53
WDGH	0.336 ±0.12	0.414 ±0.07	0.079 ±0.12	0.294 ±0.11	0.282 ±0.06	0.068 ±0.08	2.39 ±0.22	8.74 ±1.36	4.82 ±0.79
GLEMOS-S2	0.182 ±0.08	0.342 ±0.11	0.059 ±0.08	0.155 ±0.08	0.279 ±0.08	0.046 ±0.06	2.89 ±0.28	7.94 ±0.93	5.70 ±0.72
MetaGL	0.167 ±0.09	0.298 ±0.10	0.037 ±0.12	0.132 ±0.11	0.246 ±0.10	0.027 ±0.09	3.45 ±0.59	7.54 ±1.18	4.76 ±0.67

Table 2: Pre-construction prediction quality across the 13 parent sources. Cells report task-family means with seed-level standard deviations; bold and underline indicate the best and second-best values.

Ablation Variant	Spearman $\rho$ ( $\uparrow$ )			Kendall $\tau$ ( $\uparrow$ )			Gain error (MAE $\downarrow$ )
	NC	LP	CMR	NC	LP	CMR	NC	LP	CMR
Full MAG-Scout (Reference)	0.418 ±0.058	0.379 ±0.047	0.276 ±0.071	0.361 ±0.034	0.324 ±0.041	0.238 ±0.052	1.716 ±0.112	6.748 ±0.418	3.964 ±0.346
Frozen Heuristic Sketch	0.396 ±0.041	0.351 ±0.053	0.241 ±0.036	0.342 ±0.039	0.297 ±0.046	0.209 ±0.033	1.893 ±0.168	7.164 ±0.514	4.218 ±0.431
w/o Necessity ( $\mathbf{e}_{N}$ )	0.361 ±0.064	0.341 ±0.049	0.208 ±0.043	0.312 ±0.058	0.286 ±0.051	0.174 ±0.064	2.163 ±0.246	7.514 ±0.581	4.581 ±0.374
w/o Constructability ( $\mathbf{e}_{C}$ )	0.347 ±0.057	0.328 ±0.038	0.239 ±0.082	0.301 ±0.043	0.274 ±0.067	0.206 ±0.072	2.087 ±0.138	7.628 ±0.894	4.443 ±0.476
w/o Utility ( $\mathbf{e}_{U}$ )	0.339 ±0.046	0.286 ±0.054	0.214 ±0.051	0.287 ±0.031	0.241 ±0.063	0.183 ±0.038	2.458 ±0.184	8.247 ±0.512	4.916 ±0.467

Table 3: Matched component-ablation results on the separate rebuilt source bank across node classification, link prediction, and cross-modal retrieval. Cells report means with seed-level standard deviations; bold marks the best value in each column.

Figure 4: Build/Skip comparison across five predictors: threshold trade-offs, retained-gain floors, and warm decision latency.

Figure 5: One-factor retained mass at a zero threshold, the threshold trade-off, and gain error under input perturbations.

Dimension	Pts	$t=0$ Ref.	$t=0$ Best (Spread)	Perturbation	$\Delta$ Ret.	$\Delta$ Build	Flips
Learning Rate	3	81.9	83.6 (1.7)	Rewiring	$-0.4$	$-7.1$	2/13
BCE Loss Weight	3	96.2	96.5 (0.3)	Relation Collapse	$-0.8$	$-7.1$	2/13
Relation Budget	3	87.8	88.2 (0.4)	Single-Modal Dominant	$-1.6$	$-14.3$	3/13
Utility Head Width	3	93.0	93.4 (0.4)	Relation-Bank Partition	$-0.1$	$-0.2$	0/13

Table 4: Zero-threshold sensitivity (left) and frozen-policy evidence corruption (right) on 13 parent sources. Each factor has its own reference. Best (Spread) is the grid maximum and its difference from that reference.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{D}=(\mathcal{V},\{\mathcal{X}^{(m)}\}_{m\in\mathcal{M}})$	multimodal dataset: entity set $\mathcal{V}$ (cardinality $N=\|\mathcal{V}\|$ ) with modality tensors $\mathcal{X}^{(m)}$
$\mathcal{M}$	set of observed modalities (text, visual, and auxiliary attributes)
$\mathcal{T}$ , $\mathcal{C}$	downstream task and candidate graph constructor
$\mathcal{C}(\mathcal{D})=(\mathcal{V},\mathcal{E}_{\mathcal{C}},\mathbf{A}_{\mathcal{C}})$	graph induced by constructor $\mathcal{C}$
$\mathbf{H}=\{\mathbf{h}_{i}\}_{i=1}^{N}\in\mathbb{R}^{N\times d}$	frozen multimodal entity representations ( $E_{\mathrm{mm}}$ )
$\mathbf{h}_{i}^{(m)}$	modality- $m$ representation of entity $i$

Appendix

Table 5: Notation used throughout the methodology. Dimensions are for a single source; the encoder width is

d

and the reduced projection width is

d^{\prime}\ll d

Task	Nominal	Raw coverage	Calibrated coverage	Raw width	Calibrated width	Raw / calibrated NLL
NC	80%	72.5	77.4	4.69	3.66	1.48 / 1.22
NC	90%	82.9	87.6	6.02	4.70	1.48 / 1.22
NC	95%	88.1	92.7	7.17	5.60	1.48 / 1.22
LP	80%	70.8	76.8	6.84	5.33	1.74 / 1.42
LP	90%	81.2	87.0	8.78	6.84	1.74 / 1.42
LP	95%	86.4	92.1	10.46	8.15	1.74 / 1.42

Appendix

Table 6: Source-held-out uncertainty diagnostics before and after scale calibration. Coverage is reported at each nominal interval level; width is in GraphGain percentage points.

\mathbf{z}_{ij}=\phi_{\theta}([\mathbf{h}_{i}\,\|\,\mathbf{h}_{j}\,\|\,\mathbf{h}_{i}\odot\mathbf{h}_{j}\,\|\,|\mathbf{h}_{i}-\mathbf{h}_{j}|\,\|\,\mathbf{t}\,\|\,\mathbf{c}]).

Appendix

Table 11

Benchmark	Downstream Task	Entities ( $\|\mathcal{V}\|$ )	Source Edges	Modalities	Dims (T/V)	Classes / Targets	Split (Train/Val/Test)
Toys	Node Classification	20,695	126,886	Text, Visual	768 / 768	18 categories	60% / 20% / 20%
Grocery	Node Classification	17,074	171,340	Text, Visual	768 / 768	20 categories	60% / 20% / 20%
Bili Music	Link Prediction	6,038	21,592	Text, Visual	768 / 768	Binary interaction	70% / 10% / 20%
DY	Link Prediction	8,299	35,627	Text, Visual	768 / 768	Binary interaction	70% / 10% / 20%
QB	Cross-modal Retrieval	6,121	24,145	Text, Visual	768 / 768	Query-Item Pairs	60% / 20% / 20%
Bili Cartoon	Cross-modal Retrieval	4,724	18,660	Text, Visual	768 / 768	Query-Video Pairs	60% / 20% / 20%

Appendix

Table 7: Source benchmark statistics for the six datasets. Source edges are published graph counts. Feature dimensions correspond to frozen text and visual encoders; split ratios specify the evaluation protocol, including a held-out-edge split for link prediction.

Ablation Variant	$\Delta$ Spearman $\rho$			$\Delta$ Kendall $\tau$			$\Delta$ MAE
	NC	LP	CMR	NC	LP	CMR	NC	LP	CMR
Frozen Heuristic Sketch	$-0.022$	$-0.028$	$-0.035$	$-0.019$	$-0.027$	$-0.029$	$+0.177$	$+0.416$	$+0.254$
w/o Necessity ( $\mathbf{e}_{N}$ )	$-0.057$	$-0.038$	$-0.068$	$-0.049$	$-0.038$	$-0.064$	$+0.447$	$+0.766$	$+0.617$
w/o Constructability ( $\mathbf{e}_{C}$ )	$-0.071$	$-0.051$	$-0.037$	$-0.060$	$-0.050$	$-0.032$	$+0.371$	$+0.880$	$+0.479$
w/o Utility ( $\mathbf{e}_{U}$ )	$-0.079$	$-0.093$	$-0.062$	$-0.074$	$-0.083$	$-0.055$	$+0.742$	$+1.499$	$+0.952$
Uniform Bottleneck Gates	$-0.137$	$-0.105$	$-0.085$	$-0.115$	$-0.095$	$-0.071$	$+0.625$	$+1.158$	$+0.765$

Appendix

Table 8: Component ablations on the rebuilt 11-source bank, reported as differences from Full MAG-Scout in Table 6.3 . Rank correlations are subtracted from Full. MAE differences are positive when absolute error increases. The bank has 5 node-classification, 4 link-prediction, and 2 cross-modal sources, with three model seeds.

Method	Held-out Retained Gain Mass (%)					Avoided Graph Work (%)
	90%	92.5%	95%	97.5%	99%	90%	92.5%	95%	97.5%	99%
MAG-Scout	96.7	96.7	96.7	96.8 ∗	96.8 ∗	24.2	24.2	23.6	19.6	18.4
NetInfoF	96.3	96.4	96.4	96.4 ∗	97.6 ∗	24.3	23.5	23.2	22.6	21.8
WDGH	85.4 ∗	90.5 ∗	90.5 ∗	90.5 ∗	90.5 ∗	25.0	23.8	23.5	22.3	22.3
GLEMOS-S2	60.0 ∗	60.2 ∗	60.5 ∗	60.9 ∗	64.2 ∗	34.8	32.9	30.3	28.6	24.1
MetaGL	80.2 ∗	80.2 ∗	80.2 ∗	80.4 ∗	83.5 ∗	32.6	32.6	32.6	29.7	25.9

Appendix

Table 9: Build/Skip policies at five retention floors on 13 parent sources. An asterisk ( ∗ ) marks a held-out retention below the floor named in that column.

Retained-fraction $\times$ loss-weight interaction grid (all four cells)
Configuration	Grid Points	Retained (%)	$\Delta$ ref (percentage points)
Selected setting in Figure 6.5 (a)	4	81.9 / 96.2 / 87.8 / 93.0	0
Learning Rate ( $0.001\rightarrow 0.004$ )	3	83.6	+1.7
BCE Loss Weight ( $0.0\rightarrow 1.0$ )	3	96.5	+0.3
Relation Budget ( $0.50\rightarrow 0.75$ )	3	88.2	+0.4
Utility Head Width ( $16\rightarrow 48$ )	3	93.4	+0.4

Appendix

Table 10: One-factor sensitivity at a fixed zero threshold, followed by the budget

\times

loss-weight grid. Retained mass is task-macro positive-gain mass. One-factor differences use that factor’s reference: 81.9, 96.2, 87.8, and 93.0. Interaction differences use the 90.5 grid reference.

Perturbation Family	Scope	$\Delta$ Ret.	$\Delta$ Build	Flips
Rewiring	Macro (13)	$-0.4$	$-7.1$	2/13
	Node classification (5)	$-0.7$	$-13.4$	1/5
	Link prediction (5)	$-0.3$	$-4.7$	1/5
	Cross-modal retrieval (4)	$-0.2$	$-2.2$	0/4
Relation Collapse	Macro (13)	$-0.8$	$-7.1$	2/13
	Node classification (5)	$-1.4$	$-12.1$	1/5

Appendix

Table 11: Frozen-threshold evidence corruption on 13 parent sources. The predictor and threshold are frozen before perturbation.

\Delta

Ret. is the task-macro change in retained positive-gain mass;

\Delta

Build is the build-rate change in percentage points. Macro flips count parent sources. Task rows count evaluations: the books parent contributes one node-classification evaluation and one link-prediction evaluation.

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

TMTE: Effective Multimodal Graph Learning with Task-aware Modality and Topology Co-evolution
Mar 29, 2026Yinlin Zhu, Xunkai Li, Di Wu +3Multimodal Graph Learning Graph Structure Learning
Sun Yat-sen University, Guangzhou, China · Beijing Institute of Technology, Beijing, China
ReCoG: Reciprocal Co-Evolution for Multimodal Graph Learning
Aug 24, 2026Rui Xue, Tianfu WuMultimodal Graph Learning Graph Structure Learning
Department of Electrical and Computer Engineering (ECE) North Carolina State University, Raleigh, NC 27695, USA
RoleMAG: Learning Neighbor Roles in Multimodal Graphs
Apr 14, 2026Yilong Zuo, Xunkai Li, Zhihan Zhang +2Multimodal Graph Learning Graph Neural Networks
Beijing Institute of Technology, Beijing, China

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

TMTE: Effective Multimodal Graph Learning with Task-aware Modality and Topology Co-evolution

Yinlin Zhu, Xunkai Li, Di Wu, Wang Luo+2

Sun Yat-sen University, Guangzhou, China · Beijing Institute of Technology, Beijing, China

Multimodal Graph Learning Graph Structure Learning Cross-Modal Representation Learning Multimodal Fusion

Open paper AskPDF arXiv

Multimodal-attributed graphs (MAGs) are a fundamental data structure for multimodal graph learning (MGL), enabling both graph-centric and modality-centric tasks. However, our empirical analysis reveals inherent topology quality limitations in real-world MAGs, including noisy interactions, missing connections, and task-agnostic relational structures. A single graph derived from generic relationships is therefore unlikely to be universally optimal for diverse downstream tasks. To address this challenge, we propose Task-aware Modality and Topology co-Evolution (TMTE), a novel MGL framework that jointly and iteratively optimizes graph topology and multimodal representations toward the target task. TMTE is motivated by the bidirectional coupling between modality and topology: multimodal attributes induce relational structures, while graph topology shapes modality representations. Concretely, TMTE casts topology evolution as multi-perspective metric learning over modality embeddings with an anchor-based approximation, and formulates modality evolution as smoothness-regularized fusion with cross-modal alignment, yielding a closed-loop task-aware co-evolution process. Extensive experiments on 9 MAG datasets and 1 non-graph multimodal dataset across 6 graph-centric and modality-centric tasks show that TMTE consistently achieves state-of-the-art performance. Our code is available at https://anonymous.4open.science/r/TMTE-1873.

Abstract

Multimodal Graph Learning

Explore similar work

TMTE: Effective Multimodal Graph Learning with Task-aware Modality and Topology Co-evolution

ReCoG: Reciprocal Co-Evolution for Multimodal Graph Learning

RoleMAG: Learning Neighbor Roles in Multimodal Graphs