acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 -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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
multimodal graph learning, graph neural networks, optimal transport, graph merging, Nyström methods, multiway tensor methods

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_uHqYOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1(−1)
Read review
Paper summary

This paper provides a graph merging method for multimodal graphs. By selecting landmarks as reference points, it constructs node representations using similarities between each node and its intra-graph landmarks, together with a cross-graph landmark similarity tensor. It then uses optimal transport to add cross-graph edges wherever the corresponding entries in the transport plan are nonzero. The resulting merged graph retains the original nodes and edges and is used for downstream classification.

Critical strengths
  • The paper explicitly constructs sparse cross-graph edges, enabling information exchange between modalities during message passing without requiring node-level correspondence labels.
  • Experiments cover medical and remote-sensing tasks, with strong three-modality results among the evaluated baselines. Component ablations provide supporting evidence for the contributions of multiway landmark context and optimal transport.
Critical weaknesses
  • It is unclear how the self-supervised encoder establishes a common coordinate system. Particularly in Eq. 9, the representations of the two graphs are indexed by different landmark sets.
  • On TCGA-BRCA the method does not provide an explicit description on how to create initial graphs, including node definitions, features, edge-construction rules, and distance metrics.
  • Uniform transport marginals require every node to participate in cross-modal connections, but some nodes may have no meaningful counterpart in another modality, whether it can introduce uninformative edge remains unclear
  • Figure 1 is too abstract to clarify how node features become landmark fingerprints, transport plans, and final cross-graph edges. Several mathematical constructions precede their intuitive motivation, making the method difficult to follow.
Questions for authors
  1. How is GraphMAE trained across modalities, and what ensures that its output coordinates are comparable? In Eq. (9), how are distances computed between representations indexed by different landmark sets? How are unequal landmark counts handled?
  2. For TCGA-BRCA, what exactly do nodes and edges represent in each modality graph? Could the authors specify the node features, preprocessing, graph-construction metrics, and downstream GNN architecture?
  3. What motivates uniform, balanced transport when modalities may contain unmatched or modality-specific information? Have the authors considered partial or unbalanced transport?
  4. The “No OT” ablation uses greedy kNN. How is k selected, and how do its edge counts compare with those produced by EMD? Does the benefit of OT persist when the methods use comparable edge budgets?
  5. How many landmarks are used per modality, how are these counts selected, and do the reported repetitions include independent landmark sampling?
Reviewer_t41SOpenReview ↗
Rating
2(−2)
Confidence
2
Informativeness
2
Presentation
2
Soundness
1(−2)
Read review
Paper summary

This paper studies cross-modal interaction in multimodal graph learning and proposes a label-free method for constructing cross-graph edges. Specifically, the method first obtains node representations via self-supervised learning, then combines node-to-landmark similarities with a multi-modal landmark tensor to build context representations, and finally uses optimal transport to generate sparse cross-graph edges so that information can be passed directly across modalities on the merged graph. The authors evaluate the method on remote sensing land-cover classification and breast cancer subtype classification tasks, reporting performance gains in the tri-modal setting over the compared graph-alignment baselines.

Critical strengths
  • The research problem is practical and well-motivated. Multimodal data can naturally be modeled as multiple graphs, and finding effective ways for these graphs to interact is a worthwhile question. Supporting cross-modal message passing through explicit cross-graph edges is a clear goal with good practical potential.

  • The overall presentation of the pipeline is coherent. The paper provides a systematic formalization covering node representations, landmark context construction, optimal transport edge induction, and downstream evaluation. Putting these components together into a cross-graph structure construction pipeline is a sensible direction to explore, though I have not fully checked the exact novelty of each piece relative to prior work.

Critical weaknesses
  • The organization of the main text and the experimental analysis could be improved. The method section takes up a lot of space, while the related work and experimental discussions are quite brief. Key ablation studies and the full bimodal results are left mainly in the appendix, and the main text does not sufficiently explain how these results support the role of each component or what the applicable scope is across different modality combinations. I suggest bringing the most important ablation takeaways and key observations from the different modality combinations into the main paper, and connecting them directly to the motivation behind the method design. This would help readers better judge the actual gains and boundaries of the approach.

  • In addition, although the paper provides detailed mathematical descriptions, I still had some trouble following the exact relationship between the landmark fingerprints, the multiway tensor, and the final node representations. A simple walkthrough example or intuitive illustration connecting these steps would make the core idea much easier to grasp. To be clear, this reflects my own difficulty in following this part rather than a claim that the method is technically flawed.

Questions for authors
  1. Could you provide a simplified example walking through how the node-to-landmark similarities are transformed via the multiway tensor into the final representations, and explain how these representations from different modalities are used to compute cross-graph distances? This would help me understand what extra information this stage provides compared to using the self-supervised node embeddings directly.

  2. Based on the existing ablation studies and results across different modality combinations, could you more explicitly summarize the respective gains brought by the landmark/tensor context and the optimal transport edge construction, and discuss under what conditions cross-graph merging offers smaller benefits?

Reviewer_YfmGOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies unsupervised structural merging of modality-specific graphs. It combines landmark-based context embeddings with optimal transport to construct sparse cross-graph edges, and evaluates the resulting merged graphs on two multimodal graph classification benchmarks.

Critical strengths
  1. The paper addresses a relevant problem by constructing explicit connections between modality-specific graphs for cross-modal message passing.

  2. The use of optimal transport provides a globally constrained mechanism for inducing cross-graph edges.

Critical weaknesses
  1. The modality-specific context embeddings are indexed by landmarks from different graphs and may even have different dimensions, yet the paper does not clearly justify how distances between them are defined in a common coordinate space; this affects the validity of the subsequent transport costs.

  2. The fingerprint stability result assumes corresponding latent nodes and landmarks under near-isometric transformations, whereas the practical setting allows heterogeneous node semantics and uses randomly sampled landmarks; moreover, the result does not establish the validity of the complete tensor-and-transport pipeline.

  3. The method combines existing representation learning, landmark, tensor, and optimal transport components, while comparisons with simple fusion, random cross-graph edges, and carefully edge-budget-matched alternatives are insufficient to isolate the contribution of each design choice. There is a significant lack of necessary experiments to prove the effectiveness of the proposed components.

Questions for authors
  1. How are the modality-specific context embeddings mapped to a common coordinate system before distance computation, especially when their landmark counts or landmark orderings differ?

  2. How do the assumptions of Proposition 3.3 relate to randomly sampled landmarks and heterogeneous modality graphs, and what do they imply for the complete tensor-and-OT procedure?

  3. How does the method compare with no cross-graph edges, random edges, simple multimodal fusion, and edge-budget-matched pairwise alternatives?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.