acceptodds
Withdrawn from ICLR 2027

Predicted Links as Messages: Separating Formation from Propagation in Temporal Graphs

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Temporal graph models propagate information along recorded interactions. This convention leaves a plausible future relation unavailable as context until it appears, even when the observed history already supports it. Admitting the relation early can connect useful representations, but it can also transmit an irrelevant state. The missing decision is therefore not only which relation may form, but whether and how it should carry a message. We formalize future-relation message admission under a disjoint temporal protocol. Mechanism-Guided Graph Evolution (MGGE) uses historical formation evidence to freeze a sparse graph of schema-valid non-edges. A uniform residual channel then exposes this graph without writing predicted relations into temporal memory. At the common budget, paired 95% bootstrap confidence intervals for MRR lie above zero on Wiki, Enron, UCI, and GoogleLocal, with gains ranging from to MRR. Equal-budget controls show that utility depends on graph membership rather than edge count alone. Candidate-level analysis shows that formation rank is not a monotone ordering of message utility. On Wiki and GoogleLocal, two-sided exposure consistently exceeds source-only exposure across the tested budgets. A directional decomposition identifies an additional path through the destination representation. Predicted links are therefore candidate communication channels: formation constrains admission, while intervention and exposure determine utility.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
temporal graph learning, temporal link prediction, future link prediction, graph structure learning, graph augmentation, message passing, network formation, disjoint evaluation

Reviews

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

This paper examines the effect of including likely edges (but not necessarily actual edges) in the graph given to a dynamic graph encoder to measure if this improves its predictions of other links in the graph. The proposed method first uses a simple link predictor to find the top-k candidate edges that each node might connect to. Next, it combines the likely neighbors’ embeddings to each candidate node’s embedding. Finally the new embeddings are used for link prediction. This approach moderately improves MRR when applied to a TGN model across four datasets

Critical strengths
  • The approach to this problem is novel and interesting
  • The research questions that stem from the authors novel approach are reasonable and tested well
  • Section 4.5 honestly presents a negative result which contextualizes the positives and negatives of this approach
  • The approach is fairly lightweight, requiring only ~70 additional CPU seconds on the largest dataset and would be applicable broadly to many link prediction models, beyond those tested.
Critical weaknesses
  • The manuscript is very difficult to read. The core concepts of the work are not difficult to grasp, but the writing uses unnecessarily complex, jargon heavy, and vague language to convey them. Some simpler terminology (e.g. calling the “auditable mechanism vector for legal pairs” simply “edge features”) would make the work easier to follow
  • The components of the edge features (closure, popularity, compatibility, activity, and recency) are named, but not formally defined in the body of the work or the appendix. More clarity e.g. which community detection mechanism, how the time windows affect these calculations, etc. would be helpful.
  • The value β\beta in equation 7 is never explicitly defined. Is it a learned value, an explicitly calculated parameter?
  • The first phase assigns exactly K edges to every support-active source with no threshold on their score, and Section 3.3. says that their scores are not used to weight these edges contributions to the final embeddings. This likely affects sparse datasets negatively, e.g. the average node degree in each dataset is 4, 24, 14, and 8 for Wiki, Enron, UCI, and GoogleLocal. This may explain why in Figure 4.a the benefit of ChoiceGaph decreases after K=2 as it sees double the expected number of edges, and some of those edges are likely less plausible
  • The “Mixer-style” encoder referenced in Table 3 is not specified in the body of the work or the appendix. It is also only run on two of the four datasets. Why was this approach not run on Enron or GoogleLocal, and why was the evaluation protocol different?
Questions for authors
  • How are support-active sources selected?
  • How is β\beta in Equation 7 derived?
  • Please provide more details about the mixer-style model in Table 3 and clarify why it was only tested on a subset of the data
Reviewer_qSQTOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper formalizes future-relation message admission and proposes Mechanism-Guided Graph Evolution (MGGE), which uses historical formation evidence to freeze a sparse graph of schema-valid non-edges. A uniform residual channel enables message passing over this graph without writing predicted relations into temporal memory. Experiments on four real graphs examine how graph membership and endpoint exposure affect first-relation ranking, highlighting the distinction between formation plausibility and propagation utility.

Critical strengths

The paper formulates future-relation message admission, separating the plausibility that a relation forms from its utility as an early message.

Critical weaknesses

The main evaluation excludes queries whose positive pairs appear in the auxiliary graphs. Although useful for analyzing indirect effects, these protocols do not establish performance under standard temporal link prediction evaluation.

The experimental evidence relies primarily on TGN, with only limited transfer results for a Mixer-style encoder on two datasets under a different evaluation protocol. The main results lack evaluations on recent temporal link prediction methods, leaving the framework’s effectiveness and the generality of its gains unclear.

Questions for authors

Could the authors evaluate the framework on the full, unfiltered test set under a standard temporal link prediction protocol and report its incremental gains on recent compatible backbones?

What is the precise definition of ChoiceGraph?

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

This paper proposes Mechanism-Guided Graph Evolution (MGGE), a framework that uses predicted future links as auxiliary message channels for temporal link prediction. MGGE employs a Conditional Multinomial Logit model to select candidate links based on historical structural and temporal features, then incorporates the selected links into a frozen auxiliary graph for message propagation without updating the temporal memory. Experiments on four real-world temporal graphs show improvements in mean reciprocal rank (MRR) over the base TGN model.

Critical strengths
  1. The paper evaluates MGGE on four real-world temporal graphs.
Critical weaknesses
  1. The motivation for introducing predicted future links as auxiliary message channels and the necessity of the proposed two-stage design remain unclear. For example, when predicting whether a link between nodes u and v will form at time t, MGGE first relies on a separate Conditional Multinomial Logit model to select candidate links and construct an auxiliary graph, which subsequently influences the node representations used to predict the target link. This raises the question of why predicting the target link should depend on an additional model that itself predicts future link formation. If the target link u,v is admitted into the auxiliary graph, the prediction may become self-referential; even when this direct case is excluded, the prediction still depends on the auxiliary model's selection of other links that affect the representations of u and v. The effectiveness of formation based admission is questionable given the weak alignment between formation scores and downstream message utility. In Section 4.5, the reported Spearman correlation between formation scores and message utility on Wiki is only -0.0409 (95% CI: [-0.0518, -0.0275]). These results raise concerns about using formation scores to select edges for message propagation, as better formation prediction does not translate into improved downstream utility.

  2. The choice of the conditional multinomial logit model for link formation is insufficiently justified. In particular, the model relies on the independence of irrelevant alternatives assumption, which may be violated in temporal graphs where candidate destinations exhibit strong dependencies due to shared communities, semantic similarity, or correlated interaction patterns. Moreover, using a shared coefficient vector across all source nodes may fail to capture heterogeneous link formation preferences.

  3. Although the paper includes several heuristic and learned admission baselines, it lacks direct comparisons with existing temporal graph augmentation and graph rewiring methods.

Questions for authors

See the weaknesses

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

Related papers

Discussion (0)

Sign in to comment.