acceptodds
Under review as a conference paper at ICLR 2027

Markovian Semantic Transport for Heterogeneous Graph Learning

Abstract

Heterogeneous graphs contain multiple node and relation types, and predictive information often depends on long-range semantic dependencies formed by se- quences of different relations. Existing heterogeneous GNNs typically capture such structure through predefined meta-paths or by repeatedly stacking local message-passing and attention layers, which increases computational cost, can amplify hub-dominated propagation, and makes deep models susceptible to over- smoothing. We propose MC-HGNN, a Markovian semantic transport frame- work that interprets relation-aware graph attention as conditional typed transi- tions and couples them through learned node-dependent relation selection. A hub-aware correction limits excessive transport toward highly influential nodes, while relation-dependent continuation allows different semantic channels to learn different propagation ranges. The resulting all-hop transport implicitly aggregates variable-length heterogeneous paths without explicit meta-path enumeration and decouples transport depth from neural-network depth. Theoretically, we establish adaptive meta-path composition, exponentially convergent finite transport approx- imation, distance-decaying robustness to localized perturbations, and quantitative resistance to over-smoothing. Experiments on seven heterogeneous graph bench- marks show that MC-HGNN consistently improves predictive performance while maintaining favorable memory and computational efficiency.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Graph Neural Network

Reviews

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

The paper proposes a high-order mechanism to explore the multihop relationships in a heterogeneous graph, where edges may indicate a multitude of relationships, allowing for nuanced causal chains that reflect reasoning. The authors propose MC-HGNN, a GNN approach that relies on a Markov process to transition over this state space, for example, by allowing selection of which relational edge type to transition along. These meta-paths capture the higher-order relationships of each graph.

Critical strengths
  1. The goal of finding meta-paths to capture higher-order relationships specifically in a heterogeneous graph, is an active field of research. Adaptive edge-relation is a potentially interesting idea that goes beyond some existing methods. Further, using a Markov process has strong ties to the estimation of probability distributions, though this topic was not as thoroughly explored. Overall, I think the key research question has a solid grounding.
Critical weaknesses
  1. The validity of the central claims of the paper is lacking.

First, it is my observation that large parts of the introduction are currently written in passive voice. The introduction also lacks key literature from the corpus of work surrounding higher-order GNNs. Though the introduction highlights the importance of higher-order relationships, it does not cite any work investigating existing walk, hypergraph or geometric deep learning, for example, making it hard to contrast the contributions with what has already been done. In terms of claims made in the introduction, not all GNNs will recompute the self-attention matrix, see GRAND, for instance, and it is often ideal not to do so. This contrasts with the claims made in the second and third paragraph, which asserts that interpreting a normalised matrix as a transition matrix is both a new insight and central to the novelty of the method. This is problematic, given that it is in fact long existing.

The connection between Markov processes, node hubs and attention matrix is therefore not clear, and appears ad-hoc and incremental.

Oversmoothing was a central topic. Therefore, In addition to these things, I would also recommend the authors connect the oversmoothing problem with existing work done in that field, such as NeuralODEs, e.g. HDS, which circumvent the convergence of every node to the same feature vector. In the experiments (Figure 2), the Dirichlet Energy decays at a similar rate to the other methods, which is more important than its starting position, though the authors imply that having a higher Dirichlet energy indicates less decay. One ideal result would be convergence to an intermediate value greater than 0 but less than its starting position, yet the decay appears to be constant. It is not clear what is causing the higher Dirichlet Energy, e.g. initialisation. Further, Higher-order methods have been shown to prevent or mitigate such decay, creating doubts in my mind as to whether the higher-order aspect has been used effectively. It might be the case that selecting a new relation at each step does not produce the same effect, and I expect clarifications to this point going forward. As a side note, Figure 2 is very hard to read.

  1. The method does not appear novel/particularly exciting.

Admittedly, this may be due to the lack of related work (see start of last point), making it hard to place the contributions of the work accurately. As stated in this review, metapaths themselves are not novel, and Markov processes are well-established tools. For example, foundational methods such as GraphSage use meta-paths, and there has since been much research on them. Coupling meta-path work with the Markov process foundation makes it appear that MC-HGNN is closely related to a sampling problem, and it might be ideal to have more discourse from this perspective. Other method details, such as reweighting by node degree, are also well established. Nevertheless, the stopping condition and the flexible relation selection make this work potentially interesting.

As a side note, the Theorems do not appear to be sufficiently self-contained. The theorems also seem to end on a statement that interprets their meaning. It is often nuanced and infers such a result from the Theorem conditions, which themselves are dense in definitions with unclear context. Better Theorems should state the claim rigorously without overcomplicating things, and inference of said claim should be outside their declaration and somewhat straightforward, at least with sufficent context.

Questions for authors
  1. The probabilistic transition matrix between nodes of different relations implies that the transition operator is only locally valid, and the global structure therein is not being used. This affects my assessment, given that, in my opinion, the oversmoothing decay is not mitigated. A higher-order mechanism should explore the topology of the graph. Can you further justify the use of the transistion probability matrix in this regard?
Reviewer_cLx2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper tackles the challenges observed in existing heterogeneous graph learning methods, including the over-smoothing issue in relational message-passing models, the expensive attention mechanism for existing transformer-based models, as well as the requirement of predefined path templates for meta-path-based frameworks. The paper then introduces the Markovian Semantic Transport for Heterogeneous Graph Learning (MC-HGNN). MC-HGNN absorbs the observation that row-normalized graph attention can be interpreted as a probabilistic transition over neighbor nodes. It factorizes node transitions into node-dependent and relation-conditioned selections. A hub-aware reweighting strategy and a relation-dependent continuation technique are implemented to enable all-hop operator to aggregate adaptive, variable-length typed trajectories without explicit meta-path enumeration. Experiments were conducted across 7 heterogenous node-classification tasks and reported results were gathered from multiple runs for each task. Ablation studies as well as other critical component effectiveness studies, such as the over-smoothing and hub domination analysis, have been supplied.

Critical strengths
  1. Extensive experiments on the proposed framework conducted to demonstrate the effectiveness of the proposed components (component ablations, robustness analysis, over-smoothing investigations, computational efficiency comparisons, etc.).

  2. The paper organization looks good and the method is easy to follow. Especially the toy example to demonstrate the proposed relation-aware attention as typed transition. It really helps understand the proposed component.

Critical weaknesses
  1. Although training and hyperparameter setting details have been provided, no public code base nor algorithm block to outline the algorithm pipeline. It is desired to have at least one of the two to enhance reproducibility.

  2. The latest work (LMSPS) the authors used to compare with the performance of MC-HGNN was published in 2024. However, there are a few newer work [1, 2] that has demonstrated performance superiority over some of the baselines included. It will be beneficial to also compare the performance with these newer work to verify the effectiveness of the proposed method.

Refs: [1] Heterogeneous Graph Neural Network on Semantic Tree, AAAI'25 [2] Graph Transformer-based Heterogeneous Graph Neural Networks enhanced by multiple meta-path adjacency matrices decomposition, Neurocomputing'25.

Questions for authors

Please address the Weaknesses.

Reviewer_Km6WOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

MC-HGNN models heterogeneous graph propagation as a learned Markov process. It combines relation-aware attention, node-dependent relation selection, hub correction, and relation-specific continuation probabilities. A resolvent operator aggregates variable-length typed paths through sparse iterations. Experiments cover seven node-classification benchmarks, supported by theoretical analysis, ablations, and efficiency measurements.

Critical strengths
  1. MC-HGNN achieves the best reported Macro-F1 on six of seven datasets. Multiple runs, standard deviations, validation-based selection, and component ablations strengthen the evidence.
  2. Reusing learned transitions separates propagation range from attention depth. Sparse implementation avoids explicit matrix inversion, with reported memory and per-epoch runtime improvements on OGBN-MAG.
Critical weaknesses
  1. The core operator is a generalized personalized-PageRank resolvent with learned transitions and node-dependent stopping. Its distinction from established adaptive diffusion methods needs stronger positioning and comparison.
  2. Theorem 2 covers exact linear transport, while the implemented finite sum is generally not row-stochastic and is followed by nonlinear updates. Its depth-dependent lower bound can also approach zero.
  3. “Shared continuation” and “Matched PPR” both use one learned continuation parameter with the same transition mechanism, yet report different scores. Their implementation differences are unspecified.
  4. SeHGNN appears in the accuracy table but is absent from the efficiency evaluation. Per-epoch timings also leave total training cost and full-graph inference efficiency unresolved.
  5. Exact split sizes and input-feature initialization are missing. Yelp’s heterogeneous construction and its mapping to the claimed official PyG masks also need explanation.
Questions for authors

See the weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.