PaperlayerView exact revision on arXiv

Source-linked AI summary

ReCoG: Reciprocal Co-Evolution for Multimodal Graph Learning

Rui Xue, Tianfu Wu

arXiv:2608.22786v1cs.LG

TL;DR

Multimodal graph learning commonly separates topology learning from multimodal representation learning, despite noisy or semantically misaligned observed edges. ReCoG couples both through a multimodal graph refiner and cross-modal message passing, and it consistently outperforms strong baselines across node classification and link prediction benchmarks. The paper also notes that the residual refiner's extra expressiveness does not by itself guarantee better task performance.

  • Problem

    Existing multimodal GNNs generally use fixed or weakly adapted graph structures, while graph structure learning methods refine topology without modeling cross-modal evidence.

  • Method

    ReCoG jointly refines topology and learns multimodal representations through a cross-modal graph refiner and coupled intra- and inter-modality message passing.

  • Results

    ReCoG consistently outperforms strong multimodal and graph foundation model baselines across nine benchmarks spanning node classification and link prediction.

  • Takeaways & Limitations

    The results support reciprocal co-evolution of graph structure and multimodal semantics as important for effective multimodal graph learning.

  • Takeaways & Limitations

    The residual refiner's greater expressiveness does not ensure better task performance; its advantage emerges only when coupled with cross-modal propagation.

Abstract

from arXiv · show

Multimodal graph learning requires jointly training over graph structure and heterogeneous node attributes, yet existing methods largely decouple these processes: prior multimodal graph neural networks (GNNs) focus on aligning modalities in a shared embedding space while operating on fixed or weakly adapted graph structures, and graph structure learning approaches infer topology from unimodal node representations without accounting for multimodal interactions. This separation fundamentally limits the ability of GNNs to capture semantically meaningful relationships in multimodal settings, where observed edges are often noisy, incomplete, or misaligned with underlying semantics. We propose ReCoG (Reciprocal Co-Evolution for Multimodal Graph Learning), a new learning paradigm that tightly couples graph structure learning and multimodal representation learning through end-to-end reciprocal interaction. Concretely, ReCoG integrates (i) a multimodal graph refiner that infers and corrects edges using cross-modal semantic evidence, and (ii) a coupled cross-modal message passing mechanism that performs joint intra- and inter-modality propagation over the refined graph. This unified design yields greater expressiveness than decoupled or two-stage formulations and allows dynamic interaction between topology and representation learning. Across diverse benchmarks for node classification and link prediction, ReCoG consistently outperforms strong multimodal graph structure learning baselines, including graph foundation models. Our results demonstrate that reciprocal co-evolution of structure and semantics is important for effective multimodal graph learning, challenging the prevailing separation between topology and representation learning.

1 Introduction

ReCoG addresses the separation between multimodal representation learning and graph structure learning by jointly evolving topology and semantics end-to-end. It combines cross-modal topology refinement with coupled propagation and reports consistent gains across nine node-classification and link-prediction benchmarks.

  • Motivation: Existing multimodal GNNs align modalities while using fixed or weakly adapted graphs, whereas graph structure learning methods typically refine topology from unimodal representations.This separation does not model cross-modal evidence in either topology refinement or propagation.
  • Proposed framework: ReCoG jointly learns graph structure and multimodal representations through reciprocal end-to-end interaction.The framework treats updated representations as signals for topology refinement and the refined graph as the basis for subsequent propagation.
  • Proposed framework: Its multimodal graph refiner uses cross-modal semantic signals to denoise observed topology and recover missing semantically meaningful connections.The refiner is paired with a coupled cross-modal message-passing mechanism.
  • Proposed framework: Coupled propagation performs joint intra- and inter-modality information exchange over the evolving graph at every layer.This design enables fine-grained interaction between modalities during message passing.
  • Empirical findings: ReCoG consistently improves over strong multimodal GNN and graph structure-learning baselines across nine benchmarks for node classification and link prediction.The reported comparisons include graph foundation model baselines.
  • Analysis: The framework also provides a supergraph spectral characterization of modality coupling coefficients and a depth-wise contraction bound motivating shared weights.These analyses accompany the unified learning framework.

2 Methodology

ReCoG jointly refines graph topology using multimodal semantics and propagates information across modalities over the evolving graph. Its end-to-end loop combines interpretable or expressive refinement, coupled propagation, adaptive fusion, and efficient implementation.

  • Framework overview: ReCoG combines a multimodal graph refiner, cross-modal message passing, and adaptive modality fusion in an end-to-end closed loop.Updated representations guide topology refinement, while the refined graph shapes subsequent propagation.
  • Graph refinement: The refiner combines observed topology with learned multimodal edge scores to denoise existing edges and recover semantically meaningful connections.The cosine variant uses a learnable convex combination of modality-specific similarities and preserves the original graph as a structural prior.
  • Graph refinement: Target-centric candidate selection restricts refinement to supervised seed-node pairs and uses coarse-to-fine scoring to reduce computation for large sampled subgraphs.The candidate complexity is reduced from O(N^2) to O(BN_B), with low-dimensional coarse filtering followed by fine MLP scoring.
  • Graph refinement: The residual refiner uses pairwise dimension-wise interactions and signed MLP scores, supporting edge strengthening or removal beyond cosine-based refinement.Its induced function family strictly contains that of the similarity refiner under the stated bounded-correction assumption.
  • Empirical and theoretical properties: Refinement selectively adds edges in high-similarity regions with reduced overlap, while adaptive fusion combines the resulting modality-specific representations according to node-specific relevance.The residual refiner’s extra expressiveness does not itself guarantee better performance; its advantage emerges only when coupled with cross-modal propagation.
  • Cross-modal propagation: Coupled propagation jointly exchanges intra- and inter-modality information over the refined graph, with an implementation that halves calls per layer while preserving linear-aggregation equivalence.The optimized implementation reduces the cost from four to two calls per layer.

3 Theoretical Analysis

Theoretical analysis characterizes why coupled propagation enables cross-modal information flow and how its spectral behavior is controlled. It also establishes a contraction property for cross-modal discrepancies under shared weights.

  • Layerwise Cross-Modal Information Flow: For coupled models with ρ > 0 or γ > 0, the cross-modal Jacobian is generically nonzero at every layer.The result formalizes that coupling creates layerwise cross-modal dependence absent from decoupled updates.
  • Layerwise Cross-Modal Information Flow: Coupled propagation enables cross-modal information flow at every layer, unlike decoupled architectures regardless of per-modality parameterization or capacity.This distinguishes per-layer coupling from late fusion, which cannot use one modality’s graph-neighbor information to refine the other during propagation.
  • Spectral Characterization: The supergraph formulation provides a spectral characterization of coupled propagation through the eigenvalues of the refined adjacency.The coupling coefficients reshape the effective frequency response of the propagation operator.
  • Spectral Characterization: The learned coefficients ρ and γ amplify symmetric modes and attenuate anti-symmetric modes.These modes correspond respectively to aligned and opposing text–vision components.
  • Cross-Modal Consistency: After L layers, the cross-modal discrepancy contracts exponentially when the contraction condition holds.This supports convergence of text and vision embeddings toward a shared representation space.

4 Experiments

ReCoG is evaluated across nine multimodal graph datasets and multiple encoder and backbone configurations for node classification and link prediction. It consistently improves over multimodal and graph structure learning baselines, with gains linked to reciprocal topology refinement and cross-modal propagation.

  • Experimental Setup: Nine multimodal graph datasets cover node classification and link prediction across product-review, e-commerce, social-interaction, and Amazon co-purchase graphs.Node classification uses seven datasets, while link prediction uses Amazon-Sports and Amazon-Cloth.
  • Node Classification Results: ReCoG consistently outperforms baselines across datasets, encoders, and backbone architectures, especially on large and structurally complex graphs.The reported pattern indicates greater benefit when observed graphs are noisy or incomplete.
  • Node Classification Results: 90.98% on Goodreads-NC: ReCoG-res exceeds PLANET at 84.16%, while Reddit-M improves over GCN by more than 15%.These gains are attributed to down-weighting noisy edges and introducing semantically coherent connections.
  • Node Classification Results: +6.10% on Reddit-S and +17.28% on Reddit-M: ReCoG improves over already aligned QWen and LLaVL VLM embeddings.The result indicates that learned graph-level alignment can add to encoder-level multimodal alignment.
  • Link Prediction Results: 38.57% MRR on Amazon-Sports and 28.73% on Amazon-Cloth: ReCoG-res with GCN exceeds the strongest SAGE baseline on both datasets.On Amazon-Sports with ImageBind, ReCoG-res reaches 75.60% Hits@10 versus 65.61% for GCN.
  • Ablation Studies: Removing either topology refinement or cross-modal message passing degrades performance, while removing both produces the largest drop.The ablation supports complementary contributions from both components.
  • Ablation Studies: With cross-modal interaction enabled, the residual refiner consistently performs best; without coupling, similarity and residual refiners are comparable.This interaction supports the claim that the more expressive refiner benefits from cross-modal propagation.
  • Sensitivity Analysis: Performance changes only slightly across a reasonable range of candidate K values, indicating stable top-K selection.The sensitivity analysis covers both refiner variants.

5 Conclusion

ReCoG jointly refines graph topology and learns cross-modal node representations end-to-end, improving multimodal graph learning across diverse tasks while introducing bias and privacy risks.

  • ReCoG jointly refines graph topology and learns cross-modal node representations end-to-end for multimodal attributed graphs.
  • Its multimodal graph refiner and cross-modal message passing mutually reinforce structure and embeddings throughout training.
  • ReCoG consistently improves over classical and recent state-of-the-art baselines across nine datasets spanning node classification and link prediction.
  • The framework can complement, and sometimes substitute for, the alignment quality of jointly pretrained vision-language models.
  • Topology modification may introduce spurious or biased connections when multimodal features are noisy or misaligned, potentially amplifying existing biases.
  • Inferring latent relationships from multimodal signals raises privacy concerns and may enable misuse in surveillance or user behavior modeling.

C Results for Link Prediction

Link prediction experiments and optimization analyses evaluate ReCoG on Amazon graphs, showing stable refiner performance for moderate candidate pools and implementation-specific efficiency trade-offs.

  • Top-K selection: Performance improves as K increases from 1 to around 3–5, then gradually degrades at K = 12 across both refiners and all datasets.
  • Top-K selection: Performance remains relatively stable for K = 3 to K = 5, balancing missing semantic-neighbor recovery against spurious-edge noise.
  • Supergraph reformulation: Decomposing the supergraph update halves the node count per call and avoids constructing the supergraph edge index.
  • Linear merging: For linear-aggregation GNNs, merging Terms 1 and 3 reduces per-modality aggregation and transformation costs, whereas GAT requires the decomposed implementation.

F Topology–semantics Misalignment

The observed topology only partially aligns with multimodal semantics: connected and disconnected pairs overlap in similarity, while refinement concentrates added edges among more semantically similar pairs.

  • The analysis computes textual and visual cosine similarities for node pairs in Reddit-M and Movies using CLIP-encoded features.
  • Connected pairs generally have higher multimodal similarity, but overlapping distributions reveal noisy edges and missing semantic neighbors.
  • The refiner’s newly added edges concentrate in a higher similarity range than original connected pairs, with substantially less overlap with disconnected pairs.
  • These findings motivate preserving observed connectivity while suppressing noisy edges and recovering missing semantic neighbors using joint textual and visual evidence.

G Complexity Analysis.

The complexity analysis characterizes ReCoG’s per-batch cost using sampled-subgraph size, candidate selection, feature dimensions, and GNN depth.

  • Per-batch complexity is analyzed in terms of N nodes, B seed nodes, E edges, k new edges per seed, candidate ratio r, feature dimensions d and d_h, and L layers.
  • Table 7 reports the per-batch computational complexity of ReCoG’s major components.

H Proof of Proposition 1 (Strict Generalization of Residual Refinement)

The proof shows that residual refinement strictly contains similarity-based refinement: similarity scores can be represented by a sufficiently wide residual MLP, while dimension-wise pair interactions enable functions similarity refinement cannot express.

  • Inclusion: Residual refinement can realize or approximate every similarity-based edge-scoring function on the fixed candidate set.The proof constructs a continuous residual target and invokes universal approximation by an MLP.
  • Strictness: Similarity refinement assigns identical scores to node pairs sharing the same text similarity, vision similarity, and original adjacency.Its shared global linear rule depends only on those three quantities.
  • Strictness: Residual refinement preserves richer pair features, including concatenated node features, Hadamard products, and modality-specific absolute differences.These features are passed to an MLP rather than collapsed into a scalar similarity.
  • Strictness: A concrete pair construction yields equal similarity statistics but different Hadamard products, producing distinct residual scores.An MLP can assign different outputs to the resulting unequal pair features.
  • Scope: The proposition establishes expressiveness, not improved generalization or task performance.The residual refiner’s performance advantage emerges only when coupled with cross-modal message passing in the reported ablations.

I Proof of Proposition 2 (Joint Optimization Contains Non-Reciprocal Alternatives)

The joint optimization space contains every fixed-refiner alternative, including identity and frozen two-stage refiners, so its objective cannot be worse than those restricted alternatives.

  • Feasible-set containment: The full parameter space Θref × Θgnn contains the restricted space formed by fixing refiner parameters.Therefore, optimizing jointly cannot have a higher infimum objective than optimizing only the GNN with a fixed refiner.
  • Examples: The fixed-refiner alternatives include the identity refiner Arefine = Aorig and any frozen two-stage refiner.These alternatives are included whenever the identity refiner belongs to the refiner parameter space.

J Proof of Theorem 1 (Cross-Modal Information Accessibility)

The theorem contrasts decoupled and coupled multimodal GNNs: decoupled updates structurally eliminate cross-modal dependence, whereas coupled updates preserve nonzero cross-modal information flow across depth.

  • Decoupled model: Decoupled modality streams have zero cross-modal Jacobian for any per-modality weights, activation, or graph.This zero dependence follows from the update rule itself, not from particular parameter choices.
  • Coupled model: Coupled updates introduce cross-modal terms into each modality’s propagation rule.The coupled text-stream update explicitly depends on the other modality through the coupling mechanism.
  • Coupled model: When coupling is active, the layerwise cross-modal Jacobian is generically nonzero, including at deeper layers.The first-layer contribution is generically nonzero, and subsequent layers accumulate cross-modal paths through composition.

K Proof of Corollary 1 (Spectral Characterization)

The coupled propagation admits a block-spectral decomposition whose eigenvalues expose how cross-modal coupling and self-injection alter graph modes, while the analysis also derives a contraction bound for modality differences.

  • Spectral decomposition: The support matrix Asup can be diagonalized through the eigendecomposition of Arefine because its blocks commute.The resulting eigenvectors combine corresponding graph eigenvectors across modalities.
  • Spectral characterization: The coupled support operator has eigenvalues {(1 + ρ)µi + γ}N for the corresponding symmetric modes.Here µi denotes an eigenvalue of Arefine, while ρ and γ control coupling and self-injection.
  • Interpretation: Cross-modal coupling amplifies symmetric graph spectral components by a factor (1 + ρ) relative to the decoupled case.The self-injection γ adds a frequency-independent boost to symmetric modes.
  • Contraction analysis: The contraction analysis bounds the modality difference by propagating it through graph mixing, coupling, self-injection, and the 1-Lipschitz activation.The bound is obtained by taking differences, applying the Lipschitz inequality, and telescoping across layers.
Loading 2608.22786v1…