acceptodds
Under review as a conference paper at ICLR 2027

Relational Alignment Profiles: The Geometry of Graph-Learning Problems

Abstract

Graph learning is usually architecture-first: for a new attributed graph, the appropriate computational bias (local smoothing, multihop propagation, heterophily-aware filtering, role-based reasoning, or global attention) is typically discovered only after training several competing models. We ask whether the graph-learning problem itself can be diagnosed first, so that the needed computation can be inferred before model search. We introduce the Relational Alignment Profile (RAP), which characterizes how structural, feature, and task geometries align, conflict, and vary across relational scale. RAP provides a compact coordinate for architecture selection and dictionary-free curves that reveal whether relational organization is local, delayed, oppositional, feature-explained, or role-driven. We train RAP-based selectors only on controlled synthetic problems and evaluate them under generator shift and frozen synthetic-to-real transfer. Across 22 real node-classification benchmarks, the label-free native coordinate is the strongest zero-shot selector among the tested representations, achieving only percentage points of regret and outperforming conventional graph statistics. At matched dimension, also outperforms PCA/NMF compressions of the same native alignment fields. These results support a problem-first view of graph learning: diagnose relational organization before deciding what computation an unseen problem requires.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph learning, graph neural networks, relational alignment, multiscale graph representation, architecture selection, graph heterophily, homophily, graph diagnostics

Reviews

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

This paper proposes Relational Alignment Profiles (RAP) to characterize graph-learning problems through multiscale alignment between graph structure, node features, and task labels. RAP provides compact coordinates for architecture selection and alignment curves for relational diagnosis.

Critical strengths

The paper explores a problem-first perspective on graph learning, aiming to characterize relational properties before selecting suitable GNN architectures.

Critical weaknesses
  1. The manuscript contains obvious errors that suggest insufficient proofreading of AI generation content. For example, Figure 1 contains the duplicated text "Attributed Attributed Graph", along with inconsistent spacing, crowded labels, and poor visual organization. Such basic errors in a central framework figure raise serious concerns about the care taken in preparing and verifying the submission. The overall presentation falls below the expected standard for a conference paper.
  2. The task-conditioned component consistently fails to improve architecture selection, despite being part of the central formulation. The real-world Top-1 selection accuracy is only 36.36%, and the evaluation mainly relies on a small, fixed architecture bank.
Questions for authors

See weakness.

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

This paper proposes Relational Alignment Profiles (RAP), a framework that characterizes relationships among graph structure, node features, and task labels across scales for model selection and problem diagnosis. Experiments on synthetic graphs and 22 real node-classification datasets report promising transfer performance, particularly for the label-free representation.

Critical strengths
  1. The paper presents a useful perspective on characterizing graph-learning problems before choosing an architecture.
  2. The evaluation covers 22 real datasets with diverse graph properties and uses selectors trained solely on synthetic data.
  3. The label-free representation achieves lower selection regret than conventional graph statistics and matched-dimensional PCA/NMF baselines.
Critical weaknesses
  1. The role of the task coordinate β could be clarified further. The authors acknowledge its lack of consistent gains: adding β does not improve selection over α in Tables 2 and 14, while the full representation performs below chance on mechanism identification in Table 7. Since the task-alignment curves do not depend on the β projection, their diagnostic value does not directly establish the usefulness of β itself. It would help to clarify β’s contribution or provide experiments that isolate its value.

  2. The benefit over a fixed selection strategy needs further validation. The means in Table 9 imply approximately 1.46 percentage points of regret for always selecting SAGE-role, versus 2.22 for α in Table 2, with identical Top-1 accuracy. Since this comparison is post hoc, a fixed-model baseline chosen solely on synthetic training data would enable a fairer assessment.

Questions for authors
  1. Could the authors clarify why α is omitted from the mixture evaluation in Table 1? Section 4.2 states that it requires a single reference generator, but this requirement is not apparent from its definition in Section 3.3 as a projection of structure-feature alignment fields onto a fixed dictionary.

  2. Section 4.1 refers to a “paired regret test” without specifying the procedure. Please state the test used, the unit of analysis, and whether it is one- or two-sided, along with resampling details if applicable.

  3. I wonder whether some Top-1 misses select models that perform almost as well as the best one. How often is the selected model within one percentage point of the best?

  4. A brief breakdown of selection regret by dataset family would help show where the method works well and where it struggles.

  5. Could the authors report the time needed to compute α on one or two datasets, compared with training a candidate model? This would help readers understand the practical cost.

Reviewer_wzJROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Relational Alignment Profiles (RAP), which uses rank-based alignment domains to characterize the dependencies between structural relationships, feature relationships, and task relationships. This article uses a synthetic mechanism dictionary to compress these alignment domains into native coordinates and task condition coordinates"to achieve prediction of architecture and performance. Experiments cover synthetic distribution shifts and transfer to 22 real node-classification datasets.

Critical strengths

S1. The motivation is clear.

S2. Compared to a single homophily metric, the proposed method provides a richer description of graph learning problems, and the unified description of multiple relationships is valuable.

S3. The paper is well-organised.

Critical weaknesses

W1. The residual term in Section 3.2 measures label consistency solely based on the ranking of feature distances in scalar form, which may fail to capture all the predictive information contained within node attributes. Consequently, interpreting such residual associations as task-relevant information distinct from the attributes themselves requires additional sufficiency assumptions.

W2. The matched-task counterfactual experiment provides limited support for the proposed mechanism diagnosis. Table 7 reports 26.7% mechanism-identification accuracy for γ\gamma, below chance (33.3%) and conventional statistics (41.1%), while Table 8 illustrates unchanged architecture selection despite changes in the optimal architecture.

W3. This inconsistency leaves the actual information requirements and mixture protocol unclear. Table 1 and Appendix C.1 exclude Raw and α\alpha from mixture evaluation since they require a single reference generator. Although their definitions use observed graph quantities and a frozen dictionary; γ\gamma, which contains α\alpha, is nevertheless evaluated.

Questions for authors

Q1. Does the held-out-generator experiment change the graph generator while retaining all mechanisms, as described in Appendix A.5, or withhold an entire mechanism, as stated in Table 1 and Appendix C.1?

Q2. How are individual dictionary atoms constructed from multiple synthetic templates, and what regression model and hyperparameters are used to estimate the feature-conditioned expectation?

Reviewer_VFpuOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the Relational Alignment Profile (RAP) to describe the relationships between graph structure, node features, and task labels. RAP is used for model recommendation and for understanding graph-learning problems. The authors train a model selector on synthetic problems and transfer it to 22 real node-classification datasets without further fitting. The results show that the label-free representation α is useful for model selection, while the alignment curves illustrate different relational patterns in graph tasks.

Critical strengths
  1. The problem has practical value. Training and comparing several models on a target graph can be costly. The paper explores whether the graph properties of the problem can help recommend a good model in advance. This is a useful direction for reducing model-selection effort.

  2. The selector is trained only on synthetic problems but achieves low average selection regret across 22 real datasets. Comparisons with PCA and NMF at the same dimension also support the value of α beyond simply reducing the representation size.

  3. The unified analysis is useful for interpretation. RAP considers graph structure, node features, and task labels in one framework. It separates cases where structure aligns with features from cases where structure contains additional task-related signal. The real-data examples make these differences easier to understand and provide clues about model performance.

Critical weaknesses
  1. Most models in the candidate pool are quite old. The coverage of recent graph-learning methods is limited. The results support RAP within the current model pool, but it is unclear whether the advantage would remain with a broader set of modern architectures.

  2. The authors suggest that RAP could initialize or narrow down architecture search. However, the experiments focus on predicting performance and recommending models from a fixed pool. Without an evaluation in an actual NAS pipeline, it is unclear whether RAP can reduce search cost while maintaining the final model performance.

Questions for authors
  1. Would RAP keep its advantage if more recent graph-learning models are added? Does the current model pool cover the main architecture choices in the intended applications?

  2. Can RAP reduce the number of candidate evaluations or the search time in an actual NAS pipeline while maintaining the final performance?

  3. Do the datasets where RAP makes poorer recommendations share any common properties? An analysis of these cases could help explain when a selector trained on synthetic problems is reliable on real graphs.

Comments on the paper

6 comments
AuthorsOpenReview ↗

Response to followup by Reviewer rr3u

We thank the reviewer for the follow-up and for recognizing the value of a problem-first perspective. We respectfully clarify three points.

1. The fixed baseline. We added this baseline at another reviewer's request and reported every result openly. We gently note a tension: the original review criticized our reliance on a small bank and a limited suite, yet the follow-up treats a fixed choice's success on that same suite as decisive. A fixed default works only when the test suite resembles its corpus. When it does not, SAGE-role's regret reaches 15.64 pp (worse than random), the re-chosen default flips to GT with tripled real-data regret (1.46 → 4.89 pp), and on a regime absent from training α has 6.65 pp regret vs. 13.11 pp for the fixed choice (Appendix C.7). On the current suite the difference is not significant (p=0.29p = 0.29), and the two datasets where α loses are flagged in advance by RAP's own task curve (Appendix C.5). A fixed default offers neither adaptation nor such a warning.

2. Selection is one part of the contribution. The paper's second half, the diagnostic curves and β (§4.3, Appendix C.10), explains why Squirrel-filtered defeats propagation despite the strongest structure–feature alignment in the suite, why featureless airport graphs reward role-aware models, and when the selector should not be trusted. No fixed default provides this.

3. On "trivial methodology behind obscure framing." We respectfully disagree. An attributed graph defines two geometries on the same node population, one from the attributes and one from the graph, and RAP asks how they align, where, and at what scale. Comparing two notions of proximity on one population is a well-studied problem, and RAP uses established tools for it, motivated and formally defined in §3 and Appendix B:

  • Copula theory for dependence between rankings of incommensurable geometries (Nelsen, 2006; Genest & Favre, 2007).
  • Diffusion geometry for a multiscale graph metric (Coifman & Lafon, 2006).
  • Structural equivalence for role-based geometry (Ribeiro et al., 2017).
  • Double/debiased machine learning, adapted into an endpoint-disjoint cross-fitting scheme for dyadic data, where pairs share nodes and standard cross-fitting leaks labels (Appendix B.4).

These tools come from statistics and geometry rather than mainstream GNN design, but clearly motivated, formally defined constructions are not obscure. The other reviewers found the paper clear: "the motivation is clear", "the paper is well-organised" (wzJR), "the unified analysis is useful for interpretation" (VFpu).

Nor is the method a rank correlation. Its central object is the full alignment field ASX(d)(r,s)A^{(d)}_{SX}(r,s), which records where structure and features agree or conflict. The correlation is only its lossy integral (Appendix B.5), which §3.2 explicitly argues is insufficient. The simple final stage is deliberate: NNLS gives interpretable mechanism coordinates that outperform matched-dimension PCA and NMF (p=0.013p = 0.013), and the low-capacity predictor (§3.5) ensures that the representation carries the signal. A method cannot be both "trivial" and "over-complicated."

Finally, the presentation was first judged insufficiently careful and is now judged too heavy; the additions were made at reviewers' request. We sincerely hope the reviewer will reconsider the paper in light of its stated contribution: a general, principled diagnosis of graph-learning problems.

I thank the authors for the follow-up, but I maintain my position and score.

  1. Selective reporting on the FIXED baseline (Table 17, Appendix C.7): The authors argue that under distribution shift, ALWAYS SAGE-ROLE reaches 15.64 pp regret (worse than random) and that the refit default FIXED+ (GT) triples its real-data regret from 1.46 pp to 4.89 pp. However, this omits the corresponding numbers for α\alpha in the very same Table 17: on the hostile test, the original α\alpha suffers the exact same 15.64 pp regret (also worse than random's 12.96 pp) because it makes the identical picks. More importantly, when refit on the extended corpus, α+\alpha^+'s regret on the 22 real datasets degrades even further to 6.59 pp (and γ+\gamma^+ to 7.43 pp)—performing worse than FIXED+ (4.89 pp) on real data, as well as on G_test (1.70 vs. 1.59 pp) and the hostile test (3.56 vs. 3.51 pp). Thus, whether before or after corpus expansion, the learned selector consistently fails to outperform the corresponding fixed choice on real benchmarks.
  2. Clarification on presentation and methodology: There is no contradiction in my critique. My initial comment regarding insufficient care referred to submitting the central framework diagram (Figure 1) and manuscript without basic proofreading of obvious AI-generated artifacts. Meanwhile, describing the method as "trivial behind an over-complicated framing" points out that basic statistical building blocks are wrapped in heavy terminology and a multi-stage computational pipeline that ultimately fails to deliver meaningful gains in practice. Recognizing the value of the research question does not imply that the proposed implementation is effective.

We thank the reviewer for the continued engagement.

On the fixed baseline. The reviewer is correct, and we appreciate the careful reading of Table 17. Under matched training corpora, α does not outperform a well-chosen fixed default: it ties on the hostile test and trails on the current real benchmarks. All of these numbers appear in the paper, which states explicitly that we do not claim α beats a strong in-distribution default (Appendix C.7, Conclusion); our earlier summary should have shown both rows side by side. The one setting in Table 17 that tests generalization to a regime absent from training is where α leads (6.65 vs. 13.11 pp). We include it here for completeness, as it was not mentioned.

On the contribution. In practice, the best architecture for a new graph is found only by training and comparing candidates on that graph, which is often infeasible for large graphs, scarce labels, or limited compute. The alternative, a fixed default, is a bet on the training corpus with no indication of when it will fail. RAP offers a third option: a cheap, problem-side diagnosis computed before any model is trained, complementary to search and to defaults rather than a replacement for either. We would gently note that, across three rounds, the discussion has focused entirely on selection regret against a default, while the paper's diagnostic results have not yet been engaged with:

  • The alignment curves explain why Squirrel-filtered defeats propagation despite the strongest structure–feature alignment in the suite.
  • β identifies role-driven label structure on graphs with no features at all.
  • RAP's task curve flags in advance every dataset where selection fails (Appendix C.5).

None of this is available from a fixed default. On the methodology, we respect the reviewer's view, and we leave it to the AC to weigh it against the formal construction in §3 and Appendix B and against the other reviewers' assessments of the paper's clarity.

We thank the reviewer again for the time spent on our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.