acceptodds
Under review as a conference paper at ICLR 2027

Learning Time-Varying Relational Constraints on Dynamic Heterogeneous Graphs

Abstract

I study when changing rules that link related nodes on a typed, time-varying graph can be recovered from the observations, and which kind of model is needed in each case. I call this change *relational-semantics drift*: two nodes should still satisfy , but the map can move even when the graph shape and node features look similar. What can be recovered depends on what the data still contains. If each node is reduced to a mixed average over all neighbor types, that average no longer depends on the typed maps, so the maps cannot be recovered. The raw typed pairs do keep the map: orthogonal Procrustes recovers it when the map stays in , and least squares recovers it when the map is in . A Cayley sheaf with a slow path and a fast path improves anomaly scores when the planted rule changes smoothly, beating TGN, DualPath, and aggregated Procrustes and matching EvolveGCN; it tracks coboundary energy, not a typed . Averaging nodes first does *not* recover unlabeled jumps ( vs. DualPath ). When the pairs themselves are observed, unlabeled trimmed least squares in recovers the post-jump residual (five-seed AUC ); orthogonal Procrustes fails if the jump leaves .

Primary area:
learning on graphs and other geometries & topologies
Keywords:
dynamic graphs, heterogeneous graphs, graph neural networks, anomaly detection, sheaf neural networks

Reviews

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

The aim of the paper appears to be finding time-dependent maps between attributes for adjacent nodes in a dynamic network. I am not entirely certain I have interpreted the aim correct as the problem was only defined on page 4 and it was not possible to follow on an initial reading. Prior to that point, there was undefined notation and concepts which made the paper near impossible to read. As a result, I am unable to comment on the contribution and validation of the results presented in this work.

Critical strengths

The author is clearly knowledgable in the mathematical theory used in the paper. However, this is not explained in anywhere near a suitable manner for a wider audience. Potentially, with a vast and thorough editing of the paper, the theory could be worthy of publication but that is currently not possible to confirm.

Critical weaknesses

Notation and concepts were introduced without definition from the beginning making it impossible for anyone without expertise in this area to understand what is trying to be accomplished. In it's current state, it is unsuitable for a wide-ranging audience like ICLR.

Questions for authors

Based on the writing style, I believe this was written by a single author. Was the manuscript shared with anyone else at any stage to check for readability and clarity?

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

This paper studies when a time-varying typed rule on a dynamic heterogeneous graph can be recovered, using a Cayley sheaf that tracks coboundary energy and Procrustes or least squares on raw endpoint pairs.

The results show that what can be recovered depends on what the observation still contains (Table 2). In addition, the author shows that mixed node averages do not determine the typed rule, while raw endpoint pairs do, from a theoretical and empirical perspective by conducting experiments with node-aggregated Procrustes, pair Procrustes, and trimmed least squares on synthetic heterogeneous graphs with fresh endpoint features.

Critical strengths
  • The findings from the paper are backed up by theoretical proof and empirical results.

  • The paper calls out an existing gap of the literature: TGNN models let node memory change while the relation stays fixed, or they give each edge type its own weights that do not change meaning over time. In fact, the rule linking the two endpoints can itself change

Critical weaknesses
  • I found the abstract and the introduction of the paper very hard to follow. From the perspective of readers whose expertise is not in sheaf learning and continuous dynamics and jumps, the author tries to use too much terminology and references many methodologies without first explaining them (e.g Rr,tR_{r,t}, SNP, SO$(d)$, coboundary energy)

  • The conclusions drawn from this paper are mostly based off synthetics data, leaving their applicability

  • Limited baseline. While the main focus of the paper is on temporal graphs, heterogeneous temporal graphs, to be specific, empirical results are reported on two main TGNN baselines: TGN and EvolveGCN, which are not originally designed for a heterogeneous setting.

Questions for authors
  • The only real-world dataset used in the paper is Elliptic++, which is a Bitcoin transaction graph. Could the author extend the coverage of the experiment to other transaction token networks [1,2,3] or datasets on other domains [4]?

  • Can the author include additional TGNN baselines, such STHN[5] for heterogeneous graph settings?


[1] Shamsi K, Ngo TG, Shirzadkhani R, Huang S, Poursafaei F, Azad P, Rabbany R, Coskunuzer B, Rabusseau G, Akcora C. Mint: Multi-network transfer benchmark for temporal graph learning. Advances in Neural Information Processing Systems. 2026 Apr 23;38.

[2] Zhu X, Feng G, Serafini M, Ma X, Yu J, Xie L, Aboulnaga A, Chen W. LiveGraph: A transactional graph storage system with purely sequential adjacency list scans. arXiv preprint arXiv:1910.05773. 2019 Oct 13.

[3] Shamsi K, Victor F, Kantarcioglu M, Gel Y, Akcora CG. Chartalist: Labeled graph datasets for utxo and account-based blockchains. Advances in Neural Information Processing Systems. 2022 Dec 6;35:34926-39.

[4] Gastinger J, Huang S, Galkin M, Loghmani E, Parviz A, Poursafaei F, Danovitch J, Rossi E, Koutis I, Stuckenschmidt H, Rabbany R. Tgb 2.0: A benchmark for learning on temporal knowledge graphs and heterogeneous graphs. Advances in neural information processing systems. 2024 Dec 16;37:140199-229.

[5] Li C, Hong R, Xu X, Trajcevski G, Zhou F. Simplifying temporal heterogeneous network for continuous-time link prediction. InProceedings of the 32nd ACM International Conference on Information and Knowledge Management 2023 Oct 21 (pp. 1288-1297).

Reviewer_1MwkOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates relational-semantics drift in dynamic heterogeneous graphs, focusing on how time-varying relationships between connected nodes can be identified and modeled. The authors propose a theoretical framework that examines the limitations of mixed-node aggregation and the identifiability of relational operators using typed endpoint pairs. They also introduce a temporal sheaf-based model combining Cayley transformations, recurrent updates, and snapshot-based adaptation. For detecting abrupt changes, the paper explores an unlabeled least-squares approach using raw endpoint observations. Experiments on synthetic datasets and Elliptic++ demonstrate promising results for smooth relational drift and operator recovery under controlled settings. However, the proposed neural model struggles with abrupt changes, and its performance on real-world data remains less competitive than established temporal graph models.

Overall, the paper explores an interesting problem and provides useful theoretical insights, although the connection between the proposed framework and practical improvements requires further validation.

Critical strengths
  1. I appreciate the paper's focus on relational-semantics drift, which is an important but relatively underexplored aspect of dynamic graph learning. The analysis of information loss under mixed-node aggregation is particularly interesting. Theorem 2 and the operator-identifiability propositions help clarify why retaining typed endpoint information matters for recovering changing relational constraints. This provides a useful perspective for designing future dynamic graph models.

  2. The paper evaluates several drift scenarios and compares its approach against established temporal graph baselines. The synthetic experiments show encouraging results, particularly for smooth drift, where the Cayley sheaf achieves an AUROC of 0.930, close to EvolveGCN's 0.932. The unlabeled IT-GLLS estimator also performs very well on the planted jump experiments.

Critical weaknesses
  1. My main concern is that the paper motivates learning time-varying, relation-specific operators, but the proposed neural sheaf model uses a single shared connection across edge types. As written in Section 3 and the limitations discussion, this model does not directly recover the typed operators studied in the theoretical analysis. Instead, typed-operator recovery is demonstrated separately using Procrustes and IT-GLLS on raw endpoint pairs. While both components are useful, their combination does not yet establish a unified method for learning time-varying relational constraints. Furthermore, Theorem 2 relies on isotropic, independently generated endpoint features, whereas real graph datasets often contain persistent node identities and correlated observations. This limits how broadly the identifiability result can be applied.

  2. Although the proposed approach performs reasonably well under smooth synthetic drift, the improvements over strong baselines are limited. EvolveGCN performs slightly better under slow drift and more clearly under fast smooth drift. The performance on abrupt changes is also relatively weak. For example, the aggregated Cayley sheaf achieves an AUROC of 0.594 on the single-jump setting, which is nearly identical to DualPath's 0.590. The perfect performance of IT-GLLS is encouraging, but it is obtained using raw endpoint pairs under a controlled synthetic generation process. More importantly, Table 3 shows that the temporal sheaf achieves an overall AUC of only 0.646 on Elliptic++, compared with 0.872 for TGN and 0.867 for DualPath. Although the proposed method shows a smaller pre/post performance drop, its absolute detection accuracy remains substantially lower.

These results raise questions about the practical value of the more complex architecture. Stronger real-world evidence and a clearer demonstration of when the proposed model is preferable would improve the contribution.

Questions for authors
  1. Could the authors clarify how the proposed shared-operator Cayley sheaf could be extended to recover time-varying, relation-specific operators? Would such an extension preserve the current theoretical properties?

  2. How would the conclusions of Theorem 2 change when node features persist across edges and observations are correlated, as commonly occurs in real heterogeneous graphs?

  3. Given the lower overall AUC on Elliptic++, what is the main practical advantage of the proposed method over TGN and EvolveGCN? Could the authors clarify which deployment scenarios would benefit most from the improved robustness?

  4. To what extent does the perfect IT-GLLS performance depend on the planted linear relationships and independently generated anomalous targets? How might the method behave when these assumptions are violated?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Clarification, Revised abstract and introduction section

Dear reviewer,

Thanks for your time to provide the feedback.

Q1. The formal setting is a discrete-time dynamic graph: the graph is a sequence of snapshots, not a continuous-time event stream. The revised introduction states this explicitly. I have revised both abstract and introduction in the PDF. Please have a look.

As TGN is a continuous-time link predictor, it keeps a memory per node, updates that memory on timestamped events, and ranks future interactions against negative destinations. In these experiments it is adapted to the snapshot protocol. Each snapshot is one batch, and every edge in that snapshot uses the snapshot index as its timestamp. The decoder scores those existing edges with binary cross-entropy, and the per-node memory is updated after the score. Training uses the same leak-free split as the other snapshot models: the loss is computed only on snapshots before the midpoint, and test labels are not used. This is supervised scoring of observed edges, not TGN’s original future-link task. Your point that this adaptation changes TGN’s task is fair.

I did not report STHN for that reason. STHN is a continuous-time heterogeneous link predictor. A snapshot anomaly scorer built from it would be a different model, and I did not want to report that reimplementation under the name STHN. To test typed aggregation inside this snapshot protocol, I used a temporal R-GCN control on the same DualPath backbone and the same split.

Q2. This control is not the static R-GCN. Relation types are handled inside each snapshot. Time is a graph-level state carried from one snapshot to the next.

Within a snapshot, each edge type has its own linear map. Source features are transformed by that map and averaged onto the target. A shared layer mixes each node’s features with that typed average. Those relation weights are shared across snapshots. They do not depend on time, and edges have no timestamps. This is one round of per-type mean aggregation, not the basis-regularized R-GCN stack from the 2018 paper.

Across snapshots, the node embedding are averaged into one graph vector. A GRU reads that vector in snapshot order and keeps one hidden state for the whole graph, not a memory per node. A gate, whose input is the current graph vector and an exponential moving average of earlier graph vectors, mixes the GRU output with the current graph vector. The fused vector is added to every node. The edge score uses the two endpoint embedding and their raw features.

Training matches DualPath. The loss uses only snapshots before the midpoint. At evaluation the recurrent state is reset and the snapshots are replayed in order. The recurrent state at a snapshot comes from earlier snapshots, including earlier test snapshots. The current snapshot’s features and edges are inputs to the encoder when that snapshot’s edges are scored. Test labels are not used.

The temporal signal in this control is the graph-level GRU state and the gate’s moving average. TGN keeps a memory per node. EvolveGCN evolves the weight matrices. The Cayley sheaf updates a shared orthogonal transport. This control does none of those three.

Regrading presentation, I have revised Abstract and Introduction in the PDF, I would appreciate if you have a look again.

I would also like to thank you that you followed review comments from other reviewers and I specifically choose to notify all respected reviewers during adding my comments. I would respectfully like to say that, one more reviewer and not reviewers who provided this feedback.

I hope this will help you reassess and happy to clarify if any questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.