Nyström Landmarks for Cross-Graph Merging with Optimal Transport

Many multimodal prediction problems naturally give rise to *multiple graphs*—one per modality—yet learning is often performed on each modality graph separately, with cross-modal interaction occurring only indirectly. We study unsupervised structural graph merging for multimodal prediction: given modality-specific graphs associated with a supervised target, we construct a *sparse* set of cross-graph edges so that information can propagate directly across modalities during message passing. Our approach first learns *commensurate* node embeddings via self-supervision. It then constructs Nyström-style node-to-landmark fingerprints and an $N$-way low-rank landmark tensor that produces structured cross-modal context embeddings. Finally, for each modality pair, we instantiate cross-graph edges by solving an Earth Mover's Distance (optimal transport) problem between node distributions in this embedding space and extracting the support of the optimal coupling. The edge-construction procedure does not use downstream labels. We target the common setting of a small, fixed collection of complementary modalities and evaluate two- and three-modality configurations. Across heterogeneous multimodal graph classification settings, the resulting merged graphs can improve downstream performance, motivating sparse cross-graph structure as a first-class component of multimodal modeling.