Atomic HINs: Entity-Attribute Duality for Heterogeneous Graph Modeling
Authors: Shao-En Lin
Ming-Yi Hong
Miao-Chen Chiang
Chih-Yu Wang
Che Lin
Venue: ICLR 2026 Poster (2026)
Keywords: Heterogeneous Information Networks
Heterogeneous Graph Neural Networks
Graph Representation Learning
Primary area: learning on graphs and other geometries & topologies

Abstract: Heterogeneous Information Networks (HINs) provide a powerful framework for modeling multi-typed entities and relations, typically defined under a fixed schema. Yet, most research assumes this structure is given, overlooking the fact that alternative designs can emphasize different aspects of the data and substantially influence downstream performance.
As a theoretical foundation for such designs, we introduce the principle of entity-attribute duality: attributes can be atomized as entities with their associated relations, while entities can, in turn, serve as attributes of others. This principle motivates atomic HIN, a canonical representation that makes all modeling choices explicit and achieves maximal expressiveness.
Building on this foundation, we propose a systematic framework for task-specific schema refinement.
Within this framework, we demonstrate that widely used benchmarks correspond to heuristic refinements of the atomic HIN—often far from optimal.
Across eight datasets, refinement alone enables a simplified Relational GCN (sRGCN) to achieve state-of-the-art performance on node- and link-level tasks, with further gains from advanced HGNNs. These results highlight schema design as a key dimension in heterogeneous graph modeling.
By releasing the atomic HINs, searched schemas, and refinement framework, we enable principled benchmarking and open the way for future work on schema-aware learning, automated structure discovery, and next-generation HGNNs.
Our code is available at: https://github.com/ntuidssplab/AtomHIN.

Published as a conference paper at ICLR 2026
ATOMIC HINS: ENTITY-ATTRIBUTE DUALITY FOR HETEROGENEOUS GRAPH MODELING
Shao-En Lin', ,iig- Yi Hong Miao-Chen Chiang!? Chih-Yu Wang", Che Lin 13-
National Taiwan University. 'Academia Sinica, Data Science Degree Program, National Taiwan University and Academia Sinica
ABSTRACT
Heterogeneous Information Networks (HINs) provide a powerful framework for modeling multi-typed entities and relations, typically defined under fixed schema. Yet, most research assumes this structure is given, overlooking the fact that alternative designs can emphasize different aspects of the data and substan- tially influence downstream performance. As a theoretical foundation for such designs, we introduce the principle of entity-atribute duality; attributes can be at- omized as entities with their associated relations, while entities can, in turn, serve as attributes of others. This principle motivates atomic HIN, a canonical represen- tation that makes all modeling choices explicit and achieves maximal expressive- ness. Building on this foundation, we propose systematic framework for task- specific schema refinement. Within this framework, we demonstrate that widely used benchmarks correspond to heuristic refinements of the atomic HIN-ofter far from optimal. Across eight datasets, refinement alone enables a simplified Relational GCN (sRGCN) to achieve state-of-the-ar performance on node- and link-level tasks, with further gains from advanced HGNNs. These results high- light schema design as a key dimension in heterogeneous graph modeling. By releasing the alomic HINs, searched schemas, and refinement framework, we en- able principled benchmarking and open the way for future work on schema-aware learning, automated structure discovery, and next gext-generation HGNNs. Our code is available at: https: /
com nt
INTRODUCTION
Heterogeneous Information Networks (HINs) provide powerful abstraction for modeling sys- tems with multiple types of entities and relations. Such graphs naturally arise in bibliometrics, e-commerce, knowledge graphs, and social networks, where diverse node and edge types yield rich semantics. To leverage these structures, Heterogencous Graph Neural Networks (HGNNs) extend Graph Neural Networks (GNNs) with type-aware message passing across heterogeneous schemas.
Despite this progress, most research relies on a few benchmark HINS with manually specified schemas, often chosen heuristically. In practice, multiple valid schemas can be derived from the same data. For instance, the IMDb benchmark is constructed from single movie table"] columns such actor and director are processed be entities, while others (e.g., keyword, language, coun- try) remain attributes (Figure lb). In some variants, keywords are treated as entities rather than mere attributes (Figure Tcl. while additional unexplored variants are equally possible (Figure Id].
The ambiguity in schema design has received limited attention. Some recent efforts (Fey et al.) 2024] explore schema construction from relational databases, but they still rely on database-speciffe design choices, each of which corresponds to different schema variants. Consequently, the broader problem of designing HIN schemas remains open.
We introduce atomic HIN, grounded in the principle of entity-atributte duality; attributes can be atomized as entities, and entities can in turn serve as attributes of others. This duality maximizes expressiveness by making all schema choices explicit, but also increases modeling complexity.
"Corresponding author: chelin @ ntw.cdu.tw.
https: www.. w com

---

Published as a conference paper at ICLR 2026
Keyword
Actor
Country
Movie
ddreccor Facder
Heyward rosuntry
+keyerd
Heeyword rcountly
Actor
+drrecor
<director
*contenl languagge
#contontrating Hanguage
Director
ncontent rating Hanguuge
Keyworl
Director
Acontent
Heyyorr
taclor
Language
+keyunnd
+dineeter
+keyward
(a) Original data
(b) IMDh Fuu
(c) IMDb
et al. 2021
(d) Alternative schema
Figure 1: Illustration of multiple heterogeneous schemas derived from the same IMDb source table.
To address this, we propose task-specific schema refinement, which selects or discards node types (entities) and edge types (relations) to tailor the schema. Node-type selection determines which entities are assigned unique identities, while edge-type selection removes relations of limited utility, simplifying both the schema and the model. From this perspective, widely used benchmark schemas are merely heuristic node- and edge-type selections, as essentially all schema variants can be viewed as refinements of the atomic form.
Empirically, pairing the atomic form with sRGCN-a simplified RGCN with stronger parameter sharing achieves state-of-the- results on eight datasets spanning node classification and link prediction. On node classification, Macro-F1 improves by up to 6.2% over recent advanced HGNNs, and on link prediction, ROC-AUC increases by an average of 4.9%. Our systematic search further shows that benchmark schemas often diverge from optimal ones, highlighting the effectiveness of atomic HINs with schema refinement. Morcover, schemas refined with sRGCN generalize well to advanced HGNNs, with subsequent refinement under stronger models yielding additional gains.
We summarize our contributions as follows:
We introduce the principle of entity- attriblt duality, which motivates the atomic HIN, canon- ical representation that makes all schema choices explicit and achieves maximal expressiveness.
Building on this foundation, we propose schema refinement, which turns the otherwise open- ended challenge of schema design into a principled structural learning problem, enabling task- aware optimization while controlling complexity.
We show that widely used benchmark schemas are, in fact, particular refinements of the atomic form, and our systematic search reveals that these heuristic choices often differ substantially from optimal ones, underscoring the central role of schema design in HGNN development and evaluation.
Extensive experiments on eight benchmarks demonstrate that atomic HINs with refined schemas consistently improve HGNN performance. Even simplified RGCN (sRGCN) achieves state-of-the-art results, while advanced HGNNs obtain further improvements. Analy- sis of the search results further confirms the importance of atomic IINS and schema refinement.
2 RELATED WORK
2.1 HETEROGENEOUS GRAPH NEURAL NETWORKS
Heterogeneous graph neural networks (HGNNs) extend GNNs to exploit the semantic richness of heterogeneous information networks (HINs). Early models such as HAN (Wang et al. 2019)
and MAGNN (Fu
2020 rely on hand-crafted metapaths define composite relations.
RGCN (Schlichtkrull et al. 2018), HGT (Hu et al.) 2020b). and SimpleHGN (Lv et al. 2021)
instead model heterogeneity through relation-specifh transformations or heterogeneous attention. GTN (Yun et al., 2019), MHGCN (Yu et al., (002), and RE-GNN (Wang et al.) 2023) further learn soft weights over edge types, effectively performing differentiable metapath or subgraph selection. More recently, SeHGNN (Yang al. 2023). PSHGCN (He et al. 2024), and LMSPS (Li et al.
2024 precompute propagation along metapaths to support mini-batch training on large-scale HINs.
Collectively, these methods capture heterogeneous structure the level of relations, metapaths, or soft subgraphs, using either manual design or differentiable selection. However, they all assume a fixed underlying schema which message passing is defined.
2

---

Published as a conference paper at ICLR 2026
2.2 HETEROGENEOUSS GRAPH SCHEMA DESIGN
Compared to architectural innovations, the design of heterogeneous graph schemas has received relatively little systematic study. Common strategies include augmenting schemas with metapath- based edges (Wang et al.] [209 Fu et al.) 2020; Hu et al.) 2024), introducing metapath-derived features (Ly al. 2021, Fey al. 2024), and adding autributedderiee relations, typically limited to binary or categorical attributes encoded as edges.
While flexible, these strategies produce schema-design spaces that are both unbounded and com- plex. Attribute-derived relations expand the relation set, while metapath- based constructions grow exponentially with the number of relations. Benchmark datasets, therefore, implement these ideas inconsistently and often rely on ad-hoc decisions. For instance, HGB (Lv et al., (022) selectively elevates certain attributes (e.g., actors, keywords) to entities while leaving others (e.g., language, country) plain features. OGB (Hu et al. 2020a) averages textual-term embeddings into paper nodes but does not construct term nodes or relations. RelBench (Fey et al. (024) moves toward systematic schema construction while still yielding multiple valid choices.
In contrast, we introduce simple and principled framework for schema design. The atomic HIN unifies and generalizes existing ad-hoe practices into canonical representation in which all schema decisions are explicit. On this foundation, schema refinement becomes a systematic and optimizable process: it reduces the originally open-ended design space tractable selections of nodes and rela- tion types without sacrificing the expressive power available to downstream HGNNs. This positions schema design not merely preprocessing step but core dimension of heterogeneous graph modeling, enabling principled benchmarking and schema-aware model development.
3 PRELIMINARIES
Attributed Heterogeneous Information Networks
An undirected HIN is a graph G (V,E) consisting of node set V and an edge set E. Each node v V and edge
is assigned type through mappings Φ V V T and v + R, where T = { and R- = {r | denote the sets of node types (entities) and edge types (relations). Edges are represented by adjacency matrices { {A, E ER MI*I ) where A, corresponds to edges with relation with {e E & vie) r.
An attributed HIN is further associated with an attribute set F, where each f E F is assigned to an owner node type via ( F - T. Autributes are then represented as feature matrices (X,= E [eeeel p where Vein (v V/ d(v) <(f) } and dy is the dimension f.
Spectral heterogeneous graph convolution (SHGC). Defferrard al. (2016) showed that spec- tral filters on homogeneous graphs can be parameterized as L-order polynomials of the Laplacian eigenvalues. Butler et al. (2023) extended the formulation to heterogeneous graphs, introducing spectral filters based on non con-commutative polynomials over relation-specifie shift operators. For an input signal æ E R the filter is defined as
H HSS S 0) 0,1x
Σ
Σ Ort (Sr, S...). Plsmnt
where S, is the shift operator for relation r. A common choice is the row-normalized adjacency A, D. A,, where D, i] E (i, is the degree matrix of A.. The learnable param-
eters collected in θ 0o } U Or by...... where each coefficient 0o, Or E R. In this paper, we adopt SHGC as general formulation of HGNNs.
METHODOLOGY
4.1 FROM ATTRIBUTE ATOMIZATION TO ATOMIC HINS
Constructing graph structure from attributes a Long-standing but often implicit technique in HIN schema design. In most existing pipelines, this is applied during preprocessing only to binary or
3

---

Published as a conference paper at ICLR 2026
categorical attributes, which can be expanded into one-hot multi-hot representations and then converted into additional node and edge types. A widely used example is the IMDb dataset (Fig- ure I where attributes such as keywords actors clevated to entities.
Formally, this process operates independently on each attribute. In this work, we generalize the idea beyond binary attributes, treating all attributes uniformly under the principle of entity- attribb duality. For a given attribute, we define it as follows:
Definition 4.1 (Attribute Atomization). Given an attribute f F
F.F of a HIN g with feature matrix X, atomizing produces augmented HIN g' = (V JU,EUET), where U (i...... Udy is the set of new nodes with cardinality corresponding to attribute dimensions and
E = {v;)
X5(i,5] + 0 sii 1 5
Here v; denotes the i-th node of Ve()) and uj is the j-th node of the induced set U. Each edge (4,, Uy) 1 is weighted by X3 j.. This introduces new node type I' and new edge type r', yielding T TU {T'} with (v) r' if U and o' ('()) =(v) otherwise; and R R U (r') with (e) = i E and (e) = ve(e) otherwise.
In this way, atomization replaces the nonzero entries of x with explicit edges to the corresponding attribute-induced nodes, thereby converting attributes- categorical, or numerical ex- plicit structure and relations. This allows HGNNs to exploit structural dependencies and relational patterns such metapaths (Sun al., 201T).
The common practice of constructing edges via ID matching across relational tables (Fey et al, 2024 is special case where Xy is sparse and binary, producing small number of attribute nodes. When X encodes numerical attributes, atomization produces the same star-like pattern: each at- tribute dimension becomes weighted edge. Thus, both binary and numerical attributes yield structurally similar, star-shaped adjacency patterns centered at attribute-induced nodes.
induced node, and every original node connects to with single
Applying atomization to all attributes yields the atomic HIN, canonical representation in which all information is expressed structurally, achieving maximal expressiveness and making explicit all modeling choices. This representation serves as the foundation for our next step: task-specific schema refinement.
4.2
SCHEMA REANEMENT VIA NODE- AND EDGE-TYPE SELECTION
XaA
X,
XA
Xa,
X
Author
Author
Author
X
XT
Paper
Paper
Pre-propagation
Type Selection
Term
Term
Term
(a) Atomic
(b) Pre-propagated
(c) Refined HIN
Figure 2: Toy example of schema refinement on atomic HINs: pre- pre-propagatio ensures indepen-
dence between node-type and edge-type selection.
We then propose the schema refinement problem, binary selection problem over node types (enti- ties) and edge types (relations), aiming to harness the expressiveness of atomic HINs while control- ling complexity. To this end, we first define two basic operations:
Node-type selection. For each node type 7 E (,...., [T] }. a binary parameter 3, E { {0, 1) de- termines whether nodes of this type assigned unique identity and thus contribute attributes to the HIN.
Edge-type selection. For each relation r E {1...., specifies whether the relation is retained and modeled in the schema.
......./ R }. a binary parameter a, E {0,1)
4

---

Published as a conference paper at ICLR 2026
Under the SHGC framework (Equation D. which use general form of HGNNs, refinement on an atomic HIN is expressed as:
Z H(a aIR S R2) X BIT))
(2)
where (-) denotes the SHGC filter, and ( BITT) IPI VI is the feature matrix after node-type selection.
The edge-type selectors a, directly control which relations and edges participate message passing. Setting a, = 0 removes relation r and its edges entirely, equivalent in practice to dropping that relation from the constructed HIN. This makes refinement compatible with any HGNN in a plug- and-play manner, without requiring architectural modifications.
Node-type type selection specifies which node types are assigned unique learnable embeddings. A straightforward construction is to assign the identity matrix as node features for the selected node types:
Xo(31...... 16m)) - B2l2 ... B 117:
where i, R is the type-specific identity matrix, with ir if the i-th node v; V has type d(v)) = r. and 0 otherwise. When all types are selected, Xo(1...., 1) = J The motivation is learn embeddings only for informative node types, thereby reducing parameters and mitigating overfitting.
However, this naive construction can induce dependencies.
Definition 4.2 (Dependency relative to a node type). For node type E (1,...,17[}, we say that has dependency on Tj if I., ZuI., = 0 for some Tj with Br, 1, where Zo H())xo() is the output of SHGC on the naive feature initialization.
Dependencies arise because pruning certain edge types can disconnect selected nodes from the rest of the graph. For example, in Figure if all edges incident to term nodes are removed, their embed- dings become isolated and cannot contribute to downstream predictions. Thus, although edge-typs pruning improves efficiency and compatibility, it may inadvertently invalidate node-type selections by cutting off identity propagation.
To mitigate this issue, introduce pre-propagation feature initialization, which ensures that em- beddings of selected node types remain accessible regardless of subsequent edge-type choices.
4.3 PRE-PROPAGATION FEATURE INITIALIZATION
To address the dependency issue in Definition 4.2
introduce pre-prroepeee pre-propagation feature initial- ization. The intuition is straightforward: prior to refinement, each selected node type propagates its identity once other node types, ensuring that its signal remains accessible even if incident edge types are subsequently removed. Formally, we define pre-propagated features as
X(8 [I+ Σ (
(o(S1...., B(T)),
(4)
TIATT
where (r,,..79) denotes the adjacency the shortest path from type Ty to Tú, defined as the shortest product of adjacency matrices satisfying Á (T.xx.)) + 0. We provide details for the imple-
mentation this pre-propagation step in Appendix B.4
This initialization effectively distributes each identity embedding beyond its original source node, ensuring its availability across node types and thereby climinating hidden dependencies.
Lemma 4.1 (Independence of Selections). With pre-propagation, for any node type т, and any i, Zi,, 1,, + O. Hence, node-type selection independent of edge-type
selected type Tú with 3r, selection: even if all edges incident to Tj are removed, no dependency arises.
Lemma 4.2 (Neutrality of Pre- Pre-propagation). Consider an SHGC with row-normalized adjacencies
S. A, as shift operators and convolution order L sufficiently large. If raw identity features Xo(1...., 1) are replaced with pre- preprropagate features X(1...., 1). the effect is merely reparameterization of the filter coefficients (fr {6r ) Fri... Hence, pre-propagation does not alter the expressive power of the model.
5

---

Published as a conference paper at ICLR 2026
Proofs are deferred to Appendix
without reducing expres sive power (Lemma 4.2), ensuring that edge types be pruned without invalidating node type selections. We illustrate this with row-normalized adjacency. while in practice we adopt a general- ized union via dlement-wise maximum (Lv al., (02T) (see Appendix [B.).. Pre-propagation thus provides a principled basis for schema refinement without manual adjustments for each choice.
In summary, pre-propagation resolves node dependencies (Lemmaa 4.1
4.4 SYSTEMATIC SEARCH FOR SCHEMA REFINEMENT
Schema refinement reduces to a binary selection over node and edge types, but the search space of 2 candidates prohibitively large. Moreover, the space is highly skewed: retaining more edge types generally increases expressiveness (Lemma 4.3), while sparse high-cardinality node types often introduce excessive parameters and risk overfitting. Hence, naive grid or random search ineffecttvve.
To address this, we formulate schema refinement as a hyperparameter optimization problem and adopt genetic algorithm (GA)-based search strategy. While GAs have been widely studied for binary optimization, to our knowledge, they have not been applied to HIN schema refinement. Our formulation naturally enables this approach, providing a practical and effective means explore the skewed binary space and achieve near-optimal solutions within reasonable budgets (Deb et al.) 2002 Katoch al., (02T). We initialize the population with the vamilla schema and jointly optimize schema parameters with model depth L, consistent with Lemma 4.2 provided in Appendix A.4
Full algorithmic details are
4.5 HGNNs FOR ATOMIC HINS
Atomizing attributes enhances expressiveness by establishing additional structure and relations, en- abling HGNNs to capture richer semantics. In particular, the new relations introduced through attribute atomization enlarge the filter space, as formalized below:
Lemma 4.3 (Attribute Atomization Enlarges Filter Space). Let R be the original set of edge types, and let R' 3 R denote the set obtained after attribute atomization. Under the SHGC formulation, the space of heterogeneous filters spanned by
{I) (S....... rr.....,
R', R'
strictly larger than the corresponding space defined with R. Hence, attribute atomization strictly enlarges the filter space by converting altributes inlo entities with associated relations.
To connect with existing HGNNs and illustrate the broad utility of atomic HINs, we observe that many architectures can be viewed as instances approximations of SHGC.
Proposition 4.1 (RGCN (Schlichtkrull et al. 2018) as First-Order Approximation of SHGC). RGCN can be expressed as a first-order approximation of SHGC under row-normalized adjacencies
S, = Å,, with filter coefficient matrices {Wo} U (W!!)) (8)) Ir.--
Proposition 4.2 (GTN Yuun et al. 2019) as a First-Order Approximation of SHGC). GTN can be expressed as first-order approximation of SHGC under row-normalized adjacencies, with scalar filter coefficients {0o} U (0 by
These cases show that widely used HGNNs, despite differing interpretation, are first-order SHGC with distinct parameter-sharing schemes (e.g., GTN enforces w o 1). Along with additional
representative models such as SimpleHGN (Lv al. 2021), SeHGNN (Yang et al., (023), and PSHGCN (He et al. 2024), detailed derivations and extensions to higher-order variants provided in Appendix|C
On atomic HINs, SHGC particularly favors architectures with stronger parameter sharing (e.g., GTN-style), since all inputs reduce to unique identity embeddings. In this setting. heavy feature transformations MLP layers become largely consistet with the empirical findings of He et al.] (2020) that shallow parameterization can outperform deeper transformations when natural features absent.

---

Published as a conference paper at ICLR 2026
Table 1: Performance comparison on different datasets. Top panel reports node classification results; bottom panel reports link prediction results. Best results are in bold, second- brotddbbsttee are underlined. Statistical signifi- cance is marked by (p < 0.001) and (p < 0.01). OOM indicates out- out-of-memory
IMDb
Freebase
DELP
OGBN-MAG
HGNN
Macro-F1
Micro-FI
Macro-F1
Micro-F1
Macro-F1
Micro-F7 F1
Macro-F1
Micro-F1
Acc. (Val)
Acc. (Test)
XGBooott
64.27.0.21
67.58_0.20
77.96.
78.65.0..4
86.921001
86.90.010
21.85
22.65.0022
RGUN
62.05-015
46.784077
18.33
91.52=050
02.07=050
91.41=a75
47.37+044
GTN
66.35:2026
68.93=0.4
46.60=225
63.72=1.01
93.97=0.88
94,43+037
93.32+0.7
93.24
OOM
00M
HGT
63.00:1119
67.20_n07
29.28
60.51:.1.6
93.01.025
93.4910as
91.121006
91.00.m16
49.89
49.27/1911
SimpleHGi
63.53-1134
67.362057
47.722148
66.29:0045
46
45.42.044
93.35
OOM
HINormer
61.65=2.53
67,83-034
52.18+00.9
64.92=043
91.57=0233
91.9 91:911221
93.91+044
93.83=045
OOM
00M
SeHGNN
66.63:0034
68.21
50.7
63.41:047
94,86:0114
95 95.24
1:.45
1:046
93,87
55.95-011
53.99
REGUN
65.94-2047
67.89.045
64.16.006
94.80
0OM
0OM
SlaGAT
64.05.000
68.64.033
49.68.187
66:83:0.00
94.95-000
95.31
93.9910.35
94.061.012
00M
PSHOINN
67:10g00m
69.792n.52
40.01 #8.76
62.70
95 15
95.61
94,35
94.27
56. 16:021
$4.572016
RRGCNAuncc
68.97:8005
71.20=0.17
15.4
67.32
95.55=0115
95.85-0.12
94.36+8.23
94.29
57.35-0012
55.21=023
Amazon
LasIFM
PubMed
ROC-AUC
MRR
ROC-AUC
MRR
ROC-AUC
RGUN
86,3429224
93.92an:66
57.21
77.6844.17
84,62=0:3
94,27=0051
88,26::206
74.96:1.46
SimpleHGN
93.40=a02
96.91=n39
67,59:2223
90.81+9.22
85,48=126
93.67=110
SeHGGNN
91.67=204
95. 95.83=n.5
66.5922022
88.6 18.61:1125
85 1.11
95,099:074
SIOGAT
95.17
98 00
10
7259.90
58 n.0
94.71
PSHGCN
91.12
95
sRGEN
97.85=8477
99.26:2006
77.10:4.17
93.70=0.36
90.11=0.99
96.14:2841
Motivated by this perspective, we introduce simplified variant of RGCN, denoted sRGCN. It preserves the RGCN structure but replaces feature transformation matrices with relation -speciff- scalars,
W 8(00 I.
This design yields a minimal yet effective baseline, naturally aligned with the requirements of atomic HINs. Full update rules and implementation details are provided in Appendix D
5 EXPERIMENTS
In this section, we conduct experiments to address the following research questions:
RQI: Do atomic HINs improve performance over benchmark schemas and advanced HGNNs?
RQ2: How does the entily-atribbute duality in the atomic view benefit HGNNs?
RQ3: Is schema refinement truly necessary? How does it affect node-level and link-level tasks?
RQ4: How large the performance gain across schema variants when using the same HGNN? Do schemas refined sRGCN generalize across HGNNs, and can they be further improved through subsequent refinement?
RQ5: How efficient is schema refinement when optimized through a genetic algorithm?
5.1 EXPERIMENT SETUP
Datasets. We evaluate on eight heterogeneous benchmarks drawn from diverse domains, includ- ing bibliometrics, e-commerce, knowledge graphs, social networks, and biomedicine. Dataset statis- ties and corresponding vanilla schemas are listed in Table 4 and Table 2 respectively. Full dataset descriptions are provided in Appendix A.I For all datasets, we perform attribute atomization on every available attribute. When datasets include initial embeddings (e.g., pretrained language model (PLM) embeddings). we treat them as numerical attributes and likewise atomize them into feature nodes. For OGBN-MAG, following Yang et al. (2023), we initialize large-scale node types with 256-dimensional random embeddings to approximate learnable ID embeddings.
Evaluation Setting. We follow the experimental protocols specified for each dataset by its bench- mark or those commonly adopted in the literature. For schema refinement, we employ a GA with 1024 candidates and subsequently fine-tune HGNN hyperparameters the derived optimal schema using 256 trials. Full details experimental setup, baseline implementations, and hyperparameter space provided in Appendix A
7

---

Published as a conference paper at ICLR 2026
Table 2: Schema refinement results on sRGCN. Edge types underline are weighted, and with double underline are weighted and dense. Node type aliases are listed in Appendix A.1.1
Datawet
Variant
Node
Edge
D
O
M-D
M-K
M-W
M-A
M-R
MEN
M-L
M-O
M-C
IMD6
Vanilla Refined
Ba
Mu Sp
Pe
Bk-Bk Bk-Pe
Bl-Or
Bi-Ils
Pe-pp
Bi-Fi Mu-Bs
Pe-Or
Freehase
Vanila Refined
A
T,
P-P
A-A
DRLP
Vanill
Refined
S
ACM
Vanill Retined
OGBN-MAG
Vanilla
Retine
H R
14,
14,
1-
I.P
14
1-8
Amazon
Vanilla
A
A-I
U.u
U.A
LIsEEM
Vanilla
c Dr D
C8
C.C
G-S
G46
C-D
D-D,
C-G
PuhMied
Vanilla
5.2 PERFORMANCE ON ATOMIC HINS (RQ1)
We first evaluate the effectiveness of atomic HINs using sRGCN across eight benchmarks for node classification and link prediction. We compare against recent state-of-the-ar HGNNs under their vanilla schemas. As shown in Table sRGCN on refined atomic schemas consistently outperforms advanced HGNNs. Gains are more significant on datasets with rich attributes or complex schemas (e.g., IMDb, Amazon, Freebase), where attribute atomization increases expressiveness while refine- ment tailors complexity. ACM is already in atomic form with a simple schema, leaving little room for improvement. Yet, LastFM benefits substantially from refinement despite also being in atomic form with an even simpler schema. On the large-scale OGBN-MAG, improvements are mainly driven by relations induced from PLM embeddings atomized relation modes-togetie with schema refinement, showing that even numerical attributes can yield useful relational patterns.
Overall, Macro-Fl improves by up 6.2% for node classification and ROC-AUC by average of 4.9% for link prediction over the strongest baselines.
5.3 How THE ATOMIC VIEW BENEFITS HGNNs? (RQ2)
Table summarizes the refined schemas from atomic HINs using sRGCN across datasets derived from the proposed GA algorithm, comparing with the vanilla schemas. Details on how each vanilla schema corresponds to specific selections are provided in Appendix A.I We make the following observations:
Obs 1: Attribute atomization introduces meaningful relations. Refined schemas frequently preserve relations created when attributes are converted into entities-relation absent vanilla schemas but induced through atomization. This pattern consistently appears in IMDb, DBLP, OGBN-MAG, and Amazon, where refined schemas select edges from atomized attributes, indi- cating that such induced relations provide valuable semantic signals for HGNNs.
Obs 2: Entities can act as strong attributes. In Amazon, for example, item originally de- scribed by attributes such as price or sales-rank. Refined schemas, however, benefit from directly learning ID embeddings for item nodes, while still retaining attributes like price and sales-rank. Similar effects are also observed in IMDb and PubMed.
Obs 3: Relations from numerical attributes can be surprisingly useful. We atomize all attributes, including numerical ones, which induce relations corresponding to dense adjacen- cies. Although such dense edges may appear unintuitive, many are consistently selected re- fined schemas (highlighted with double underlines in Table 2). A plausible explanation is that these edges encode similarity relations through metapaths (Sun et al., (01T)). For example, the paper-author- paperr metapath in the citation network captures co-authorship. while the paper-
8

---

Published as a conference paper at ICLR 2026
Table 3: Performance of HGNNs under different schema variants. Vanilla: the original benchmark schema. Refined(HGNN): schema refined using the corresponding HGNN. The best results within each HGNN are in bold, the second-best are underlined, and global best across all HGNNs are highlighted with blue bold.
Scheman
Freehase
Amazon
OGBN-MAG
Macro-F1
Micro-F1
Macro-FI
Micro-FI
ROC-AUC
Acc. (Vel(Val)
Acc. (Test)
3RGCN
Vanilla
67.6442041
20.05
52.13=1778
67,09:044
95
98.43=0.15
56.734021
54.63:20.33
Retined (sRGCN)
68.97
71.20:0.17
55,40=1255
67.32:0.66
97,85
99.26:1015
57.35
55,21=0.33
Vanilla
63.55+1.36
67.3620.57
47.72=145
66.29:044
93,40+002
96.962029
00M
OOM
SimpleHGN
Refined (sRGCN)
65.89
68 18.60
53.45=185
67,834033
96,50+am7
48.6
00M
OOM
Refined (SimpleHGiN)
67.38
70.02:942
13.51
67.94
97,40.1.11
99.05
00M
OOM
Vanilla
67. 17:10:00000
69.79
40.01
62.70
94, 12:.05
97 97.93au
56.611m11
54,53-0201
PSHGCN
Refined (sRGCN)
67.89
40.53=300
65.66:0055
96.73+05)
98. 29
57.65+0.8
65.28+6.19
Refined (PSHGGCN)
67.89
69.87=184
48,19:1145
66.36-10.55
97.13+a.11
98.91=00
$7.65
65.34
paper embedding paper metapath in OGBN-MAG approximates paper similarity, akin to dot-product signals between embeddings.
5.4 Is SCHEMA REFINEMENT NECESSARY? (RQ3)
Having examined the role of atomic HINs and attribute atomization, we now turn to the necessity of schema refinement. Using the refined schemas reported in Table 2 retaining or discarding node and edge types affects performance.
we analyze how selectively
Obs 4: Schema refinement remains important even for fully atomic schemas. Some datasets, such as Freebase and LastFM, are already in atomic form and therefore cannot benefit from fur- ther atomization. Nevertheless, simple refinement dtrategiss-selcctivel dropping node or edge types-still yield significant improvements, highlighting the value of schema selection beyond atomization alone.
Obs 5: Schema refinement for link prediction favors pruning relations, even target ones. For link prediction tasks, refinement often requires more aggressive relation removal. In LastFM, dropping the user-artist relation (the prediction target) improves results, while in PubMed, dis- carding all edges yields the best performance. This behavior aligns with the over-smoothing ef- fect observed by |Bttler et al.) (2023): link prediction is more sensitive to excessive connectivity, whereas node classification typically benefits from homophily. Pruning relations that reduce con- nectivity can therefore lead directly to performance gains.
5.5 GENERALIZATION OF REFINED SCHEMAS (RQ4)
We now examine the quantitative benefits of schema refinement and its transfcrability across differ- ent HGNNs (Table Beyond sRGCN, we evaluate two additional models: SimpleHGN, a repre- sentative attention- based HGNN, and PSHGCN, a recent precomputation baaeed HGNN that models SHGC without first-order approximation. Further discussion of these models and their connections to SHGC is provided in Appendix C
Obs 6: Schema variants yield substantial performance differences. Across all three HGNNs, refined schemas consistently outperform vanilla ones (first row of each HGNN), showing that schema choice can be as influential as model architecture.
Obs 7: Refined schemas transfer effectively across HGNNs. Schemas discovered with sRGCN generalize well to other HGNNs (second row of each HGNN), often delivering strong results without re-optimization. schema achieves even better performance.
notable case is PSHGCN OGBN-MAG, where the transferred
Obs 8: Subsequent refinement provides small but consistent gains. Re-optimizing schemas for each HGNN (third row of each HGNN) yields additional improvements, though the margin is modest compared to the leap from vanilla to refined (sRGCN). This suggests that schemas found with sRGCN are already opar-ol for other HGNNs.
5.6 How EFFICIENT IS SCHEMA REFINEMENT AS A SEARCH PROBLEM? (RQ5)
We assess the efficiency of schema refinement by tracking performance over search trials (Figure 3) Starting from the vanilla schema, refinement converges rapidly even on relation-rich datasets. For

---

Published as a conference paper at ICLR 2026
MD06
Froebase
Asrazon
PubMicd
Figure 3: Performance improvement across schema search trials on four datasets.
instance, IMDb and PubMed achieve near-optimal performance within 512 trials, despite exhaustive search spaces containing up 2 and 2 candidates, respectively.
5.7 COMPLEXITY ANALYSIS
We analyze the computational cost of the somnework-iicludding astribute atomization, pre- propagation, type selection, and the search procedure-as well as the parameter complexity induced on downstream HGNNs after schema refinement.
Attribute atomization. The atomization step converts node features into edges in the atomic HIN. This operation simply restructures how the data stored, thereby incurring minimal cost. is executed once per dataset as an offline preprocessing step.
Pre-propagation. Pre-propagation, used obtain X (I,..., 1) in Equation can likewise be computed offline. As detailed in Appendix [.4] its cost can be upper-bounded by iteratively ap- plying message passing on the atomic HIN most N times, where N is the maximum number of relations connecting any pair of node types. In practice, N is small constant (the largest among our datasets 4 for atomic DBLP) and further bounded by the number of node types. As a result, the complexity of pre-propagation is ((T))E)), incurred once per dataset.
Type selection. Type selection removes all unselected relations and retains only the feature columns of the precomputed pre- rrepropaggate matrix corresponding the selected node types. This step involves only indexing and filtering operations, and thus adds negligible computational cost.
Effeet on HGNN parameter complexity. Schema refinement directly influences the number of relations and the feature dimensionality exposed to the HGNN. On refined HIN, the number of selected relations is M rr Orr: and the input feature dimension is D = E B-1V+ where [R|
V, {u
((v)==]
For HGNNs that instantiate SHGC or its first-order approximations, the parameter complexity be- comes O D) or O(MLD), where L denotes the SHGC order (or equivalently, the number of layers in first-order formulations).
Search procedure. Finally, the cost of schema refinement is dominated by the HGNN's training time under each candidate schema. With search budget of B trials, the overall time complexity of the search process scales linearly as O(B).
6 CONCLUSION
We introduced the atomic HIN, grounded in the principle of entity-attribute duality, in which tributes can be atomized into entities, and entities can, in turn, serve as attributes of others. This duality maximizes expressiveness by making schema choices explicit. On this foundation, we pro- posed schema refinement, a systematic procedure for selecting or discarding node and edge types to yield task-specific schemas. Across eight datasets, even a simplified RGCN (sRGCN) trained on refined atomic IINs achieves state-of-the-art performance, with further gains from advanced HGNNs. These results establish atomic HINs as a powerful representation for heterogeneous graph learning and highlight schema central dimension of HGNN design and evaluation. Looking ahead, we hope this work provides a foundation for principled schema-awan aware learning, automated schema discovery, and next-generation HGNN architectures.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY
To ensure reproducibility and facilitate future research, we provide detailed descriptions of the ex- perimental setup in Appendix A.3] and the hyperparameter search space in Appendix [A.4 The complete source code, together with processed datasets and search configurations, is available at https://qithe wwwptuulooooomaaaaee http.//iddooddd.../aa.aaoooo.o.. N
ACKNOWLEDGMENTS
This work was supported in part by the National Science and Technology Council and AviviD.ai un- der Grant 22622F--002-01 and National Taiwan University and Academia Sinica under Grant Chih- Yu Wang was supported by the National Science and Technology Council under Grant 1-2222--E-01--002----
NTU-AS-1 144A-41240
1--221-E-001-017-MY22 and the Academia Sinica under Research Grant AS-KPQ-I12-NETT-II-AA
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In The 25th ACM SIGKDD Interna- tional Conference on Knowledge Discovery & Data Mining, pp. 2623-2631, 2019.
Landon Butler, Alejandro Parada-Mayorga, and Alejandro Ribeiro. Convolutional learning on multi- graphs. Trans. Sig. Proc.,, 71:933-99446 Jamuary 2023. ISSN 1053-587X. doi: 10.1 10.1109/TSP:223. 3259144, 144. BRLhttpp::10
11tp://1...1099SSS 2023 3259144
Ivan Cantador, Peter Brusilovsky, and Tsvi Kufiik. Second workshop on information heterogeneity and fusion in recommender systems (hetrec2011). In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys L. pp. 387-388, New York, NY, USA, 201 1. Association for Computing Machinery. ISBN 978 140030683. doi: 10.1 00.11444200439922244416 URL https:
7/doi. 1t1p://0..145/2243392222 2044001
Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. Representa- tion learning for attributed multiplex heterogeneous network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1358-1368. ACM, 2019.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3438 3445, Apr. 2020. doi: 10. (tt.0/9/a/a..4.00.000
5747. URLpttps:: ptatps://on //o:s aaai .or.ii.rrg//o inwixindxxx. http://iidxx..pp/..aaaaaa wwwpp/p///////..pp
5747
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, KDD '16, pp. 785-794, New York, NY, USA, 2016. Association for Computing Machin- ery. ISBN 9781 45034423. doi: 00.1145/233962222999778 URt.itttss://ol/ //tp://////o..r/.....
2TT.2/9999722777777.7 2939785
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002. doi: 10.1 109/ 4235.996017.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances Neural Information Processing Systems, 2016. URL httpt:h///aaaatt
org/ abs/ / 606. 09375
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational deep learning graph representation learning relational databases. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver. Jonathan Scarlett, and Felix Berkenkamp (eds.). Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 13592-13607, PMLR, 21-27 Jul 2024. URL hctps: http::////ceeengegeee mmr..
feess/v23//fey222 html
11

---

Published as a conference paper at ICLR 2026
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neu- ral network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, WWW '20, pp. 2331-2341 New York. NY. USA, 2020. Association for Computing Machin- ery. ISBN 9781 450370233. doi: 10.1145/33642233388880 1145/33664 3380297
URL wttpttt::////e. htt.:p:://ooo.or/1/// org/10.
Jan L. Harrington. Chapter normalization. Jan L. Harrington (ed.), Relational Database Design and Implementation (Fourth Edition), pp. 141-161. Morgan Kaufmann, Boston, fourth edition edition, 2016. ISBN 978-0-12-804399. doi: htps://doi.org/10..00
B978-0- 120-00-----04499-8800000000
URL
www. http://www.eeeeeeirrrcccccooo/es
Mingguo He, Zhewei Wei, Shikun Feng, Zhengjie Huang, Weibin Li, Yu Sun, and Dianhai Yu. Spec- tral heterogeneous graph convolutions via positive noncommutative polynomials. In Proceedings of the ACM Web Conference 2024, WWW '24, pp. 685-696, New York, NY. USA, 2024. Associ- ation for Computing Machinery. ISBN 9798400701719, doi: 10.1145/358933433455555 URL https:
wtw.ggg..... S1w...1111/13338333333 3645515
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, YongDong Zhang, and Meng Wang. Light- gen: Simplifying and powering graph convolution network for recommendation. In Proceed- ings of the 43rd International ACM SIGIR Conference on Research and Development in Infor- mation Retrieval, SIGIR '20, pp. 639-648, New York, NY, USA, 2020. Association for Com- puting Machinery. ISBN 978 450388064.
doi: 10.1 10.1145/3397271.3400066
URL https:
7/doi org/ 10. 114111119311// 3401063
Jun Hu, Bryan Hooi, and Bingsheng He. Efficient heterogeneous graph learning via random projection. IEEE Transactions on Knowledge and Data Engineering, pp. 1-14, 2024. doi: 10.1109/TKDE.2224444538
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: datasets for machine learning on graphs. In Pro- ceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020a. Curran Associates Inc. ISBN 9781713829546.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, WWW '20, pp. 2704-2710, New York, NY, USA, 2020b. Association for Computing Machinery. ISBN 9781450370233. 3380027. URL
doi: 10.1145/3366423. 0tti///1...11/3336423 3380027
Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar. A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80(5):891-88126 2021. ISSN doi: 10. 10.1077711104200000100
1573-7721.
URL https:://ci.org//// 10077
5 s11042-020- 10139-6
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR), 2017.
Chao Li, Zijie Guo, Qiuting He, Hao Xu, and Kun He. Long-range meta-path search on large-scale heterogeneous graphs, 2024.
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang- Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th
ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, pp. 150011660, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 4450883325. doi:
02.114534445548.4475533 URL htllhhtts:/aae org/10 1145/1115000 344744447884 0184444588887777778848888 3467350
Qiheng Mao, Zemin Liu, Chenghao Liu, and Jianling Sun. Hinormer: Representation learning on heterogeneous information networks with graph transformer. In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 599-610, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450394161. doi: 10.1145/2543507.35533 3583493. URL https: aeooioorg/10... 10. 1ttp:/110.11553553555000
//doi.
12

---

Published as a conference paper at ICLR 2026
Yoshihiko Ozaki, Yuki Tanigaki, Shuhei Watanabe, and Masaki Onishi. Multiobjective tree- structured parzen estimator for computationally expensive optimization problems. In Proceed- ings of the 2020 Genetic and Evolutionary Computation Conference. GECCO '20, pp. 533-541, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 1450371 doi: org/10. 1115//11.11113333313111 3.8 3389817
10.1145/3377930.338999
Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg. Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli, Marri-Estther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (eds.), The Semantic Web, pp. 593 607, Cham, 2018. Springer International Pub- lishing. ISBN 978-3-319.93417-4
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. Pathsim: meta path-based top-k similarity search in heterogeneous information networks. Proc. VLDB Endow. 4(11):92--1003, August 2011. ISSN 2150-8097. doi: 10. 10.44788/540277734407777 10. 14477834407000 01tp///33447777342233333
URL
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, accepted as poster.
2018. / www.eeewwwww.ett/ooouuuloooo...e
Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. Enabling homogeneous gnns to handle heterogeneous graphs via relation embedding. IEEE Transactions on Big Data, 9: 9:1697- 1710, 2023.
Minjie Wang, Quan Gan, David Wipf, Zhenkun Cai, Ning Li, Jianheng Tang, Yanlin Zhang, Zizhao Zhang, Zunyao Mao, Yakun Song, Yanbo Wang, Jiahang Li, Han Zhang, Guang Yang, Xiao Qin. Chuan Lei, Muhan Zhang, Weinan Zhang, Christos Faloutsos, and Zheng Zhang. 4dbinfer: A 4d benchmarking toolbox for graph-centric predictive model- ing on rdbs. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 27236-27273. Curran Associates, Inc., 2024. doi: 10.52202/079017-08556
URL
2f 22667477002201533331302222222222 -atasses-..aaatss...aaaaasssa.se and Benchmarks Track.pdf
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The World Wide Web Conference, WWW '19, pp. 1022-2032 New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781 4781466366748. doi: 10. 1145/3308558.331355 URL htllhhtps::/do.o org/ /11111////338... 3313562
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pp. 6861-6871. PMLR, 2019.
Bishan Yang, Wen tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference knowledge bases. International Conference on Learn- ing Representations, 2014. URL httpt:: http:p//ww....eeaa......ooooooor 27760038
Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network represen- tation learning: unified framework with survey and benchmark. TKDE, 2020.
Xiaocheng Yang, Mingyu Yan, Shirui Pan, Xiaochun Ye, and Dongrui Fan. Simple and effi- cient heterogeneous graph neural network. Proceedings of the AAAI Conference on Artificial Intelligence, 1001)-108161111122000 //ojs. www.saaai..ccmm wwwpaaii..gggnndeeeeeeeeeeee
Jun. 2023. doi: wtt.://a..........6... TwA.A//articeeeiee///5556.
URL hetps:
Pengyang Yu, Chaofan Fu, Yanwei Yu, Chao Huang, Zhongying Zhao, and Junyu Dong. Multiplex heterogeneous graph convolutional network. In Proceedings of the 28th ACM SIGKDD Confer- on Knowledge Discovery and Data Mining, pp. 2377-2387, 2022.
13

---

Published as a conference paper at ICLR 2026
Seongjun Yun, Minbyul Jeong, Rachyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph trans- former networks. In Advances in Neural Information Processing Systems, pp. 1 11960-11970, 2019.
Ziang Zhou, Jieming Shi, Renchi Yang, Yuanhang Zou, and Qing Li. Slotgat: slot-based mes- sage passing for heterogeneous graphs. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.or... 2023.
A EXPERIMENTAL SETUP
A.1 DATASETS
We provide detailed descriptions of the eight heterogeneous datasets used in our experiments. For each dataset, we highlight the vanilla schema, the preprocessing conventions used in prior bench- marks, and how our atomization modifies the schema.
IMDb (V et al. 2021): The vanilla IMDb contains four entities: movie, actor, director, and key- word. Each movie node has five attributes-
color, country, content rating, and language. Actor and director nodes use features propagated from word attributes of connected movie nodes, while keyword nodes are represented by a one-hot identity matrix. Relations include movie-actor, movie-director and movie-keyword. In the atomic IMDb, the attributes word, color, country, con- tent rating, and language are atomized into distinct entities connected to movie. Under the schema refinement framework, the vanilla configuration selects the entities keyword, word, color, coun- try, content rating, and language, while movie, actor, and director are unselected. The selected relations are movie-actor, movie-director, and neyorrk Note that keyword and word rep- resent distinct textual levels: a keyword such as "coming of age" corresponds to multiple word tokens ("coming." " "of," "age"" with frequency statisties.
Freebase (Lv et al. 2021): A knowledge graph comprising eight node types types- sopes-book, organiza- tion, business, music, sports, location, film, and people-aud and thirty-six edge types connecting all possible pairs of node types. The dataset contains no attributes; all information is represented by entity identities and relations. As a result, the atomic and vanilla schemas coincide: all eight en- tity types are retained nodes with unique identity embeddings, and all thirty-six relation types are preserved. Within the schema refinement framework, this corresponds to the configuration where all entities and all relations are selected.
DBLP (LV et al. 202T): A bibliographic network containing four entities: author, paper, venue, and term. Term nodes 50-dimensional PLM features, paper and author nodes use sparse multi- hot features, and venue nodes are represented by a one-hot identity matrix. Relations include author-paper, paper-term, and paper-venue. In the atomic DBLP, the features of paper and author are atomized into entities paper-feat and author-feat, connected via paper-paper-fea and suthor--uthor-ffee The PLM feature of term is atomized into term-feat and linked through term- term-feat. Under the schema refinement framework, the vanilla configuration selects the entities author-feut, venue, term-feut, and paper-feat, and retains the relations author-paper, paper-term, and paper-venue.
ACM (L et al. 2021: A citation network containing four node types: paper, subject, author, and term. Term nodes are represented by one-hot identity matrix, and paper, subject, and au- thor nodes are represented by propagated ferm features through term-paper, term--appe-suhjectt and term- author. No explicit attributes available for atomization. Under the schema refinement framework, the vanilla configuration selects only the entity term and all relations.
OGBN-MAG (Hu et al. 2020a): A large-scale academic graph for venue classification. In its vanilla form, it contains four node types: paper, author, institution, and oield-of-ttudy. Paper nodes are represented by 128-dimensional PLM embeddings (mean of connected term embed- dings) and include year attribute used only for data splitting: pre-2018 (train). 2018 (validation), and post-2018 (lest). Other node types have no attributes and are initialized with 256-dimensional random vectors in (Yang et al. 2023). In the atomic OGBN-MAG, the PLM embeddings are atomized into embedding nodes linked via emper-en and the year attribute atomized into nodes connected by pearr-year, constructed only for training papers to avoid data leakage. Under the schema refinement framework, the vanilla configuration selects the node types em- bedding, author, institution, and field-of-study, while paper and year are unselected. The selected
14

---

Published as a conference paper at ICLR 2026
Table 4: Dataset statistics for benchmark and atomic HIN.
Dotaset
Torget (tpe/ etype)
*Classes
Benchmark (vanilia)
Atomic HIN
ANodes
MNod: Types
#Eide
iNodes
MNod: Types
MEdges
#ldge Types
Dense Adi
Clusstication (NC)
IMD6
24,9099
94,3844
4,982x16
180/988
1,057,685
Author
7,723:50
Paper
Paper
21,111,007
21,740,578
736,289:128
Lank Prodiction (1.))
hem--tm
10,099
11,256
1S1.220
1009922
attialsaces
111.796
111,796
PubMed
discase discase
63.109
233,047
63,909
233.047
200-13,561
relations include paper- paper-author, muthor-institutionn paper-fieldoof-stute and paper-paper, with paper-embelding and paper-year unselected. Note that for large-scale node types (author, stitution, field-of-study, paper), random embeddings are applied following prior practice, while smaller node types (embedding, year) use full identity matrices.
Amazon (Cen al. 2019): e-commercc graph whose vanilla form contains single node type, item, and two relation types: co-view and co-purchase. In the atomic Amazon, new node types are atomized from item attributes, including price, sales-rank, category. and brand, along with their connecting relations. Under the schema refinement framework, the vanilla configuration selects the node types price, sales-rank, category, and brand, with item unselected. All relations introduced by atomization are unselected. Note that the price attribute is one one-dimensional; direct normalization collapses values to =1. A dummy column equal to the mean absolute price is appended before normalization to ensure non-trivial edge weights for item-price.
LastFM Cantador et al. 2011 A music network containing the node types user, artist, and tag, targeting user-artist link prediction. All nodes lack attributes and are represented by identity matrices. Since no attributes are available in the benchmark, the graph is already atomic. Under the schema refinement framework, the vanilla configuration selects all node types and relations.
PubMed (Yang et al. 2020): A biomedical knowledge graph whose vanilla form contains four node types: disease, gene, chemical, and species, connected by ten relations. All nodes have 256-dimensional PLM embeddings, which often replaced by learnable identity embeddings in practice. In the atomic PubMed, these embeddings are atomized into feature nodes disease-feat, gene-feat, chemical-fert and species-feat, with corresponding relations their base nodes. Under the schema refinement framework, the vanilla configuration selects the node types disease, gene, chemical, and species, baselines typically use identity embeddings, All original relations induced through atomization are selected.
A.1.1
ALIASES FOR NODE TYPES
Aliases for node types used in Table
IMDb: N numerical, R content rating, D director, word, country, language, A actor, O color, K keyword.
Freebase: Bk = book, Or = organization, Bs business, Mu = music, Sp = sports, Lo location,
film, Pe = people.
DBLP: A author, P = paper, V venue, T term, A author-feature, P paper-feature, T,
term-feature.
ACM: P paper, author, S subject, T term.
Amazon: = item, P = price, B brand, R sales-rank, C= category.
LastFM: U = user, A = artist, T tag-
PubMed: = disease, G gene, chemical, species, D, = disease-feature, G gene-
feature, C chemical-feature, S; = featies-
OGBN-MAG: P paper, A = author, institution, field-of-study. E term ferm--emeedding, year.
15

---

Published as a conference paper at ICLR 2026
A.2 BASELINES HGNNS
We briefly describe the HGNN baselines used in our experiments:
XGBoost (Chen Guestrin 2016): A strong non-neural bascline for tabular learning. We apply
it to node classification datasets with target-node features, providing feature-based comparison independent of graph structure.
GTN Yun et al. 2 Learns soft selections over edge types to construct composite relations, generating metapath-basee adjacency structures which a GCN is applied. This enables dynamic metapath learning rather than relying on manually defined schemas.
RGCN (Schlichtkrul] et al. 2018); One of the earliest HGNNs, extending GCNs to relational graphs by introducing relation-specific feature transformations. Each edge type is assigned distinct projection matrix, enabling type-aware message passing.
HGT (Hu et al., 2020b): An early attention- HGNN. It models heterogeneity through relation-specific attention with node-type-awars keylquery projections, combined with learnable relation-specifie priors to capture the varying importance of different relations.
SimpleHGN (Lv et al. 2021): A simple extension of GAT without beavily modeling heterogene- ity. It incorporates relation-aware information through relation embeddings, achieving competitive performance.
2023): Adapts Graph Transformers to HINs by combining them with GCN-style propagation. It first encodes local structure through neighborhood aggregation, then applies heterogeneous relation encoder to model relation-specific information.
HINormer (Mao et al.
SeHGNN Yang et al. 2023): Extends SGC-style precomputation to HINs, enabling efficient precomputation- training. This design allows mini-batch learning without information loss from subgraph sampling GPU memory overhead, making it well-suited for large- scale settings.
RE-GCN (Wang et al. 2023): Learns relation embeddings for heterogeneous graphs with gradient scaling, enabling GCN-style aggregation ability handle heterogeneity.
a over soft composite relation subgraphs and improving its
SlotGAT (Zhou et al. 2023): A GAT-based model for heterogeneous graphs. It conducts message passing separately across node-type-specific "slots," preserving distinct semantics in different fea- ture spaces.
A spectral HGNN that models heterogeneous graphs under positive semi-definite constraints on spectral filters. Its framework also extends to precomputation-base settings, enabling scalable and efficient training on large-scale HINs.
PSHGCN (He et al. 2024
A.3 EVALUATION SETTING
For node classification datasets (IMDb, Freebase, DBLP, ACM, OGBN-MAG), we follow the offi- cial splits and evaluation metrics provided by each benchmark. On OGBN-MAG, we report classifi- cation accuracy on both validation and sets, following the official protocol, and present the mean and standard deviation over 10 runs. On the other datasets, we report both Macro-F1 and Micro-F1, averaged over 5 runs.
For link prediction datasets (Amazon, LastEM, PubMed), the task is cast as binary classification on node pairs. We evaluate with ROC-AUC and MRR, using negative samples drawn from 2-hop neighbors of each positive pair, following the protocol Lv et al. (202I). All datasets use official splits except PubMed, which was originally introduced by Yang al. (2020). We found that its official split suffers from severe distribution shift, so re-split the dataset (with the same ratio). All experiments are conducted on a single RTX A6000 GPU with 48GB memory or smaller GPUs.
A.4 HYPERPARAMETER SETTING
As discussed in Section 4.2 we treat schema parameters and model depth as hyperparameters. Hy- perparameter optimization carried out using optuna (Akiba et al. 2019). We adopt two-stage tuning process: (1) schema tuning with a budget of 1024 trials, followed by (2) HGNN hyperparam- eter tuning with 256 trials.
16

---

Published as a conference paper at ICLR 2026
Schema tuning. We use GA (Deb al. 2002 with default parameters, except that muta- tion probability is set to 1/8 for datasets with more than eight schema parameters. The search is initialized from the vanilla schema configuration and explores 1024 candidate points.
HGNN hyperparameter tuning. We apply the Tree-structured Parzen Estimator (TPE) Ozaki
2020) implemented in optuna, using default parameters. For each model, define the al.
following search spaces:
sRGCN: number of layers, hidden dimension, number of heads, dropout rate, edge dropout (or input dropout for precomputation-base -based setting on OGBN-MAG), learning rate, weight decay, decoder ML.P layers.
SimpleHGN (Lv et al. 2021]: number of layers, hidden dimension, number of heads, dropout rate, edge dropout, learning rate, weight decay.
PSHGCN (He et al., 2024): number of layers/hops, hidden dimension, embedding dimension, dropout rate, input dropout, learning rate, weight decay.
B DETAILS OF PRE-PROPAGATION FEATURE INITIALIZATION
This section provides further motivation and proofs for the lemmas stated in Section along with additional technical details.
B. PROOF OF LEMMA 4.1
Lemma (Independence of Selections). With pre-propagation, for any node type T; and any selected type Tj with 3,, 1. i, Zi,, # O. Hence, node-type selection is independent of edge-type selec- tion: even if all edges incident to Tj are removed, no dependency arises.
Proof. Expanding the SHGC polynomial yields
2 = H(, SI........... ............ R S
=
3m
Σ
O Or ... (().))
(5)
1=1 Platoss
The first term guarantees that i, ( (B........ B # 0 for all node types Ti whenever 3r, 1, independent of the edge-type selectors }a,} Jr. Hence, even if all incident relations of тj are pruned, its pre-propagated identity remains accessible to all other node types, confirming independence. C
B.2 PROOF OF LEMMA
Lemma (Neutrality of rreppropagation). Consider SHGC with row-normalized adjacencies
S. A, shift operators and convolution order L sufficiently large. If raw identity features Xo(I...., I are replaced with pre-propagated features X (I,...,,), the effect is merely reparameterization of the filter coefficients (fr,....rr))....... Hence, pre-propagation does not al- ter the expressive power of the model.
Proof. The SHGC representation with identity features be written
0 + Σ Σ 0 O re (Ar, Ar, I.
F=1 Pl....te
After applying pr-propagattin, the identity features are replaced by
X(1, 11..,1)) 1)= Σ À (
T
17

---

Published as a conference paper at ICLR 2026
yielding
Z' 0ol + Σ Σ
O ( ... ...Ar)))
X (1)
f=1 t-lr
00 E (Ar, in ....A)))..
(6)
where the updated coefficients { result from expanding the product with X (1,.... ... 1).
Since the operator span (A,, ... Ar, In.....r remains unchanged given sufficiently large L, pre-
propagation only reparameterizes the convolution coefficients without altering expressive power of the model.
B.3 GENERALIZED UNION AGGREGATION.
We first demonstrate pre-propagation using row-normalized adjacencies Á,, which corresponds to mean weighted-sum pooling:
C;
Σ
A,,
JEA
where A!!r) denotes the neighbors of node under relation r.
In practice, however, union-based aggregation is often used to initialize features, as in L.v et al. 202I). In the unweighted case, this equivalent to an element-wise maximum across neighbors:
i [k] max xy[k] JENT
We extend this to generalized union operator that performs element-wise maximization while ignoring sign. This variant naturally handles weighted adjacencies and empirically yields more stable performance when used for pre-propagation:
T. [k] Ar [b),
L= arg [i,
jEA
Here the chosen neighbor the one with the maximum (magnitude) contribution on dimension k. Overall, we find that union-based pre-propagation tends yield more consistent performance across datasets compared to mean weighted-sum pooling with A,.
B.4 IMPLEMENTATION.
Tre-propagation is performed before type selection. This procedure is independent of edge-type selection and thus needs to be precomputed only once per dataset.
The computation proceeds independently for each node type. For given node type Ty, initialize its feature matrix as Xx; I,y. i.e., identity features for nodes of type Ty and zeros elsewhere. Prop- agation is then applied along any relation whose source node type already has non-empty features and whose destination node type still empty. This process is repeated iteratively until all node types have received non-empty features, yielding the pre- prepaaapaet initialization X X(I....,1) for node type Tÿ.
The full procedure is summarized in Algorithm 1
C SHGC PERSPECTIVE ON HGNNS
This appendix provides detailed case analyses how representative HGNNs relate to the Spectral Heterogeneous Graph Convolution (SHGC) formulation introduced in Equation I We show that several widely used models can be interpreted as first-order approximations of SHGC under different parameter-sharing schemes.
18

---

Published as a conference paper at ICLR 2026
Algorithm Pre-propagation of features
Input: {Ar)r: row-normalized adjacency matrices of relations in the heterogeneous graph [T]
Input: {X, T= feature matrices for each node type
Output: (X+ 1==1 pre-propagated feature matrices
(
procedure PREPROPAGATE( Jr. )
2: Initialize {X; - {0)==1
3: for Ty + to do
4: Construct (X T Jn=1 where X (5) + X,, and X (7)
17)
72 + 0 for Tj # To
5: [Z r, f PROPAGATEFEATURESS( Ar (x(5) (5))7
1=
6:
for f- 1 to
T do
7:
+ ZT: X <- X 72
8: end for
9:
end for
return (X)1 177
10:
11:
function PROPAGATEFEATURESS( (Ar),. (X+ )
12:
while 3r, such that X,, = 0 do
13:
for all A, E {r do (Tas Te) < source and target node types of relation
15:
if X r. * 0 and X,, = 0 then
16:
X < A,X,,
end if end for end while
18:
19:
20:
return (X-)=-)
21:
end function
22:
end procedure
Table 5: Representative HGNNs interpreted under SHGC. Approximation indicates whether the model corresponds to a first-order approximation of SHGC models SHGC directly. Shift opera- tors: A, denotes relation-specific row-normalization, and A, denotes cross-type row-normalization.
Model
Approximation
Shift Operator
Parameter Sharing
RGCN Schlichttrull et al.
2018
First-order
A.
w Eg (x(
sRGCN (ours)
First-order
A,
W(()) = =
GTN (Yun et
2019
First-order
A,
W =
SimpleHGN (Lv
2021
First-order
Å.
W(O ((()))
ScHGNN Yang ct al.
2023
A,
W
PSHGCN (He et al.
2024
Á.
W W Ort...ry W
Formally, extending SHGC (Equation)
! to multi-chamn features X E R yields
z - IXW, +
Σ
Σ S ... ... Sr, X W Wri...
(10)
Em Plonnee
where W. Fi.... E Rdddd are generalized filter coefficients for multi-channel features and S, de- notes the shift operator associated with relation
C.1 FIRST-ORDER APPROXIMATIONS
Relational GCN (RGCN). RGCN (Schlichtkrul et al. 2018) extends GCN Kipf & Welling
2017) to heterogencous graphs. Following GCN, which adopts a first-order approximation of spec- tral convolution (i.e., I. 1) and realizes higher-order convolution by stacking multiple layers,
19

---

Published as a conference paper at ICLR 2026
RGCN can likewise be viewed as first-order approximation of SHGC:
H IH W Σ (
where A, denotes the normalized adjacency matrix for relation
Even with this first-order approximation, the number of parameters { ( be prohibitive for relation-rich graphs. To address this, RGCN introduces a basis-decomposition scheme for parameter sharing:
R fr, still
Σ 0,D Wo.
where B E N is the number of basis transformations, W, E Rdxd' are shared across all relations, and 6r are relation-specific coefficients.
Graph Transformer Network (GTN). GTN (Yun et al. 2019) learns weighted combinations of adjacency matrices construct meta-relations, producing a meta-patt veta-path adjacency Ap on which GCN can be applied.
Formally, Ap learned for an arbitrary meta-path of length at most
R
Ap
II E=1
0
I
0
Ar
where self-loops are included to allow paths shorter than L hops. A GCN is then applied using the row-normalized adjacency Ap as the propagation operator:
= (I + Ap) XW.
Expanding Åp shows that Z can be written as
Z = 0 IXW + Σ Σ O' Cn
An Å.. XW,
(=1 Ply
where each coefficient .',,...,r is a product of up to L scalars (0(t)) Dr.e. For example, 6% = 1 +
I g( corresponds to the identity term.
This expansion demonstrates that GTN another example of first-order approximation of SHGC, but with stronger parameter sharing:
w = I
In practice, GTN further introduces multiple sets of scalars off.b) for b 1...., B to capture diverse meta-relational structures. We omit this extension here for clarity.
HGNNs, such SimpleHGN (Lv al.) 2021 extend GAT /Velicković et al.) 2018) by introducing relation-aware attention through relation-specific bias in the attention mechanism.
SimpleHGN. Attention-baan
Empirically, attention models behave similarly to spectral graph convolution with row- normalization (Chen et al. (2020). Assuming further that the relation-specifie bias acts effectively multiplicative scalar, SimpleHGN can be interpreted as first-order SHGC approximation with parameter-sharing as:
w g(0 (t)
(11)
where ( dd is shared projection and o.0) R is relation-specifé scalar.
RRGCN considers different normalization choices depending on relation-specife normalization node-level tasks, and cross-relation normalization for link-level tasks. Here, A, corresponds to the relation- specific normalization.
20

---

Published as a conference paper at ICLR 2026
Concretely, SimpleHGN incorporates edge-type information by introducing learnable relation em- bedding W2 E Id (with de a hyperparameter) and projection Wie. For an edge (i.j) type (((,,))) the modified attention score is
رااه a W h4 W hj W W
- Ub.j + 02 W wr,,
where ei 1 V + R the edge-type indicator, ai, = aj [WTh; WT is the vanilla GAT attention score, and a a1 || ag. (For readability, we omit the layer index (E) in this part; it is reintroduced in the update equations below.)
Although this formulation is intuitive extension of GAT, the relation-specifi term ag W w, can be reparametrized by single scalar 0r. yielding
a/i Oi.j O,.
Just as GTN introduces multiple scalar coefficients per relation, SimpleHGN extends to use multi- head attention, each head learning its own 0r,b-
Following the empirical observation that attention resembles row-normalized spectral convolu- tion (Chen et al. (220)), we may approximate the relational bias as multiplicative scalar edge weights g(0) This yields the SimpleHGN update rule
R
(E+1)
Σ
000
(9T W
n + (O h
JEND
where N/T1) denote the neighbors of i-th node via edge type Or equivalently in matrix form,
R
((+1)
= 8
IH
where A, is the cross-type row-normalized adjacency matrix for relation r, approximating the soft- max normalization of GAT. This shows the parameter-sharing introduced earlier Equation []
C.2 BEYOND FIRST-ORDER APPROXIMATIONS
While many HGNNs adopt first-order approximations, several recent works learn SHGC more directly without truncation. These models are often precomputation-based. computing Sr, S.,)) offline. Such precomputation advantageous when the number of relations is moderate, as it enables efficient mini-batch training: precomputed features (S,, S, ... Sr,) X can be sliced directly without subgraph sampling. thereby avoiding the trade-off between information loss (few hops or few sampled neighbors) and GPU memory overhead.
SeHGNN. ScHGNN (Yang al. 2023) is one of the carliest and most representative reeomputation-aaseee HGNNs, extending SGC (Wu et al. 2019) to heterogeneous graphs. It di- rectly parameterizes spectral filters of the form S,,, Sr, ... Sr,, with S, A, the now-normalized adjacency of relation and learns a projection W Wr,..rre ddxd' for each such sequence.
Thus, SeHGNN follows Equation I0 exactly, while further applying a Transformer-based semantic fusion followed by MLP prediction head. The semantic fusion can equivalently be viewed part of a general decoder Y = MLP(Z). since the metapath sequences (i.e., polynomial terms) form a lixed-length, orderless set.
PSHGCN. PSHGCN (He et al. 2024) is another HGNN that directly learning the coefficients 8o Or,...., of SHGC (as in Equation 1] without first-order approximation, while additionally con- straining the polynomial coefficients to be positive semi-definite, ensuring the optimization objective convex.
PSHGCN also adopts stronger parameter sharing:
Wo 0 W.
W W 0 O B.....WWW W
21

---

Published as a conference paper at ICLR 2026
where W Raxd is node-type-specieee projection. Since heterogeneous graphs often have features in different spaces and dimensions, W decomposes as XW Σ X,W, where X = + X, is the direct sum of features across node types and W- is the corresponding block of W applied to T.
C.3 SUMMARY
The above analyses show that representative HGNNs can all be interpreted within the SHGC for- mulation, differing mainly in (i) the order of approximation and (ii) the extent of parameter shar- ing. This perspective highlights two key insights: (1) representative models such as RGCN, GTN, and SimpleHGN correspond to first-order SHGC approximations with different parameter-sharing schemes, while SeHGNN and PSHGCN directly instantiate higher-order SHGC; (2) these results provide theoretical justification that atomic HINs are broadly compatible with diverse HGNN de- signs.
Table provides a concise taxonomy of representative HGNNs under the SHGC lens.
D SRGCN: SIMPLIFIED RELATIONAL GCN
As discussed in Section 4.5| propose simplified variant of RGCN under the strongest parameter sharing, where relation-specific weights collapse to scalars:
( 0(
Propagation rule.
The update rule of sRGCN is
[ 0
((++1)
((0) H +
A, + H
(12)
} are relation coefficients normalized through softmax, following Yun et al. 2019), for numerical stability.
with initial features (0) XW. Here ((0) (0(2)
Multi-head extension. Following Yun et al. (2019); Lv al. (202I), we employ a multi-head
scheme, where multiple sets of coefficients {0, ((,)) (r,.) Fr,ébb are learned in parallel, thereby increasing
model capacity.
Training enhancements. We incorporate model-agnostic techniques commonly adopted in ad- vanced HGNNs, including: (i) 1.2-normalization of output logits (Lv et al. (02T), (ii) edge dropout (or input dropout in the precomputation setting). and (iii) residual connections across layers.
Decoders.
Following existing practices, we apply an MLP decoder to the learned embeddings for node classification tasks. For link prediction tasks, we use either dot-product decoder or Dist- Mult (Yang et al. 2014).
Precomputation setting. Following the idea of precomputation-basee HGNNs Yang et al. 2023 He et al.) 2024). sRGCN can be further simplified by removing intermediate non- non-linear activations and expanding the layerwise updates into polynomial terms:
L (10 + 11I
|
Z =
(
000) A.)
XW,
where (Āg + corresponds to the residual connection.
This enables efficient training large-scale HINs such OGBN-MAG, and also permits the of labels as attributes, as proposed by Yang et al. (2023).
E MUTATION PROBABILITY ANALYSIS FOR GA-BASED SCHEMA SEARCH
We conduct parameter study the genetic algorithm used in the systematic search for schema refinement. Figure presents the performance curves over search trials under different mutation probabilities.
22

---

Published as a conference paper at ICLR 2026
146
Figure 4: Performance improvement under different mutation probabilities across schema-search trials on Freebase.
Table Performance comparison of sRGCN on schemas searched with different mutation proba- bilities.
Mutation-prob.
Macro-F1
Micro-F1
1/2
55.32=1441
66.72:+0.25
1/8
55.40=0.66
67.32++0.66
1/32
55.29=087
67.49:10.37
1/45
52.54=1.67
66.3441046
When the mutation probability is too small (e.g., 1/45, effectively flipping only one parameter per trial), convergence becomes slower and may lead to suboptimal results. For other reasonable settings (e.g., 1/2, 1/8, 1/32), the GA yields similar convergence behavior and comparable final performance. The quantitative results summarized in Table
F CONNECTION TO DATABASE NORMALIZATION
Attribute atomization for categorical attributes is closely related to database normalization. Database normalization decomposes tables into smaller, separate tables that satisfy specific normal forms, often to reduce redundancy and limit undesirable dependencies.
particular, the sixth normal form (6NF) decomposes a table so that contains a primary key and at most one additional attribute (Harrington 2016). If a relational database is already in 6NF and all categorical attributes are represented by foreign keys pointing to reference tables that enumerate their possible values, fien-under the transformation described by WWan et al. (2024) the resulting structure corresponds directly to an atomic HIN. From this viewpoint, atomic HINs can be viewed the graph-structured analogue of fully decomposed schema.
When numerical attributes are present, our atomization extends this correspondence by representing numeric dimensions attribute nodes connected via weighted edges, ensuring that all attribute cafommatoon-categoriiaal or numeric-is encoded structurally. This enables HGNNs to operate over fully structural representation while retaining the expressive benefits of full decomposition.
G LIMITATIONS AND FUTURE DIRECTIONS
While our study highlights the benefits of atomic HINs, several limitations remain. Our treatment of attributes primarily relies on metadata, whereas, in principle, they could be divided into finer- grained entities. For example, numerical columns though each column may carry a distinct semantic meaning. Such granularity introduces additional complexity, which remains challenging even for mainstream HGNNs.
currently grouped into single node type.
Looking ahead, we outline several directions where atomic HINs may enable further advances:
Soft relaxation of selection. Schema refinement in Section 4.2 is framed as binary selections ar, 3, E { 0, }.. These can be relaxed beyond binary: node-type selectors 3, could interpolate between no identity embedding (3, 0) and full-rank embeddings (B, 1), with low-rank em-
23

---

Published as a conference paper at ICLR 2026
beddings corresponding intermediate values. Similarly, edge-type selectors a, could be relaxed into continuous meta-weights over relations, particularly suitable for models that parameterize het- erogeneity through relation scalars.
Inductive bias of human-defined schemas. Heuristically constructed schemas in common benchmarks often follow practical principles: sparser node types (with larger cardinality) mod- eled as structural entities without identity embeddings, while denser node types (with smaller car- dinality) left attributes. These design choices implicitly define the inductive bias of current HGNNs and may hinder fair evaluation of new models. At the same time, counterexamples high- light the limitations of these heuristics. For instance, the venue relation in DBLP and the subject relation in ACM provide consistent gains despite their low cardinality, while high-cardinality nodes such as keyword director in IMDb also contribute positively when modeled with embeddings. These cases underscore the importance of minimizing heuristic assumptions in schema design. More broadly, less conventional structures- such as bottleneck nodes or numerical attributes atomized into dense relation nodes-call for tailored architectural mechanisms in future HGNNs, rather than relying solely on adaptations of existing designs.
LARGE LANGUAGE MODELS
Large Language Models (LLMs) were used for linguistic polishing and editing of the manuscript. All technical content, theoretical results, and experiments were designed and implemented indepen- dently by the authors.
24


Reviews:
[{"review_id": "D53QeZQCPJ", "reviewer": "Reviewer_c825", "summary": "This paper works on heterogeneous information networks for which many different machine learning techniques are known. These models start with the data and their structure as given. The authors argue that there is in fact a lot of different ways the data can be structured into HINs and this can have a high impact on the results. They define a formal framework to show the entity - attribute duality which leads to the possibility to do this. In two propositions the show that two existing methods (from 2018 and 2019) can be expressed within this framework. The results indicate that indeed the results vary with the choice of entities vs attributes and that the revised schemas proposed by the authors have good performance.", "questions": "- How about more recent methods compared to the 2018 and 2019 ones. Why only consider those two?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- Good theoretical foundation for the entity - attribute duality and the following atomization step.\n- Unification of existing methods based on the framework. \n- Good experimental evaluation", "weaknesses": "- This paper is more a database / KDD type of paper, for me that would be the more appropriate venues. The authors are correct by writing that ICLR typically start from the given structure. This is also reflected in the references where the only refs to ICLR and related venues are for the tools used not as comparisons to the proposed methods.\n- The reformulation of two methods into the new setting is interesting but the methods are from 2018 and 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k14YmT8pQ9", "reviewer": "Reviewer_8dUP", "summary": "The work explores the new structure of HIN, which transforms certain feature values into new node types.\n\nTo this end, the authors propose an atomic HIN, which selectively transforms certain features into nodes via an evolutionary algorithm.\n\nThe authors demonstrate the effectiveness of the atomic HIN in various heterogeneous graph benchmark datasets.", "questions": "See Weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The motivation and presentation are clear and intriguing.\n\nS2. Key arguments are supported by theoretical analysis.\n\nS3. Various datasets have been used for evaluations.", "weaknesses": "I have several questions regarding this work:\n\n**W1. [Complexity]** While the authors use an evolutionary algorithm to avoid the exhaustive exponential search regarding which features to be transformed into nodes, I still think the search process requires heavy computations. Can the authors analyze the time consumption for this search process?\n\n**W2. [Backbone HIN]** It seems the proposed method is coupled with SHGC. Can the method be coupled with other types of HINs?\n\n**W3. [Feature constraint]** I think for binary features, the transformation is natural. However, for numeric features, how is the transform being performed? Are the values assigned by edge types (or weights)? If so, then wouldn't the graph be very dense?\n\nMy initial score is below the acceptance threshold, but I’m willing to raise it pending the authors’ clarifications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kpyQRlKDav", "reviewer": "Reviewer_eaMx", "summary": "The paper proposes an atomic view of heterogeneous information networks (HINs) by atomizing attributes into explicit nodes and relations, so that all information becomes structural. On top of this representation, the authors introduce schema refinement via a genetic algorithm that searches over which attribute-derived node/edge types to include for a downstream task.", "questions": "- What is the connection between atomic representation and normalization form in database theory? \n- Does this method extend to relational databases? Could you apply the same idea to solve the relational deep learning problem like in RelBench?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Elevating attributes to first-class graph elements clarifies a long-standing, often ad-hoc HIN design step. The discussion is genuinely interesting and important for the community.\n- Using GA to navigate the combinatorial schema space is a neat and pragmatic idea.\n- Framing schema choice as an optimization target (rather than a one-off manual decision) is valuable and underexplored.\n- Proofs and experiments are commendable", "weaknesses": "- Baseline: How does the proposed method compare with the tabular learning baseline?\n- Additional ablation study and details over the GA could be added, i.e., different variants of the fitness function\n- Scalability analysis is missing: what is the atomization cost, searching cost, and runtime/memory of the model added up, and how do it compare with standard GNN methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yITzfd7HPG", "reviewer": "Reviewer_uBa4", "summary": "This paper introduces the principle of entity-attribute duality, motivating an 'atomic HIN' where all attributes become entities to maximize the graph's expressiveness. On this foundation, the authors propose a framework for task-specific schema refinement, which systematically selects the most informative nodes and relations for a given task. This allows a simple model to achieve state-of-the-art performance and stronger models to improve further, demonstrating that schema design is a critical and overlooked component in heterogeneous graph modelling.", "questions": "1. What specific components constitute the core novelty beyond formalizing attribute atomization (e.g., canonical atomic HIN, schema refinement/search, pre-propagation), and how does each component independently contribute to performance?\n2. What are the per-dataset costs of atomization in terms of graph expansion (nodes/edges/types), density, training time, and peak memory?\n3. What are the time and memory complexities of pre-propagation as a function of relation/type counts, and how do those complexities manifest on OGBN-MAG-scale graphs?\n4. How does the proposed discrete search compare empirically to differentiable schema/subgraph selection methods (e.g., GTN/MHGCN/RE-GNN) on small/medium benchmarks?\n5. How transferable are refined schemas across heterogeneous GNN architectures and tasks, and what failure cases or negative transfers were observed?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The papers validates its framework across eight heterogeneous benchmark datasets from diverse domains (bibliometrics, e-commerce, knowledge graphs, biomedicine).\n2. By canonicalizing schema design and turning it into a first-class, searchable object, the work shifts attention from only designing graph neural layers to co-designing data schemas + models.\n3. The finding that benchmark schemas are often far from optimal (under equal model capacity) is important for the community’s evaluation practices; the release of atomic graphs, refined schemas, and a refinement framework directly supports more principled future benchmarking.", "weaknesses": "1. The paper formalizes attribute atomization and 'atomic HINs,' but it also acknowledges that constructing structure from attributes is a long-standing preprocessing technique (e.g., one-hot/multi-hot attributes turned into nodes/edges, as in IMDB). This makes the core idea feel more like a principled unification than a new representational primitive. It is recommended to add a small related-work ablation to show where each piece of the proposed appproach adds value beyond prior metapath/feature-node practices.\n2. Schema refinement is cast as binary search with a genetic algorithm and a sizeable budget (1024 schema trials), followed by 256 model-HP trials. This raises fairness and overfitting concerns if competitor baselines do not receive commensurate tuning. \n3. Several methods effectively learn metapaths/subgraphs via soft weights (e.g., GTN, MHGCN, RE-GNN). Since these are differentiable schema search to a degree, they’re natural baselines/foils for the discrete approach. If excluded due to scale or incompatibility, justify; otherwise is would be better to add them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)