Relation-Aware Diffusion for Heterogeneous Graphs with Partially Observed Features
Authors: Daeho Um
Yoonji Lee
Jiwoong Park
Seulki Park
Yuneil Yeo
Seong Jin Ahn
Venue: ICLR 2025 Poster (2025)
Keywords: missing features
imputation
heterogeneous graph
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a novel feature imputation scheme for heterogeneous graphs.

Abstract: Diffusion-based imputation methods, which impute missing features through the iterative propagation of observed features, have shown impressive performance in homogeneous graphs. However, these methods are not directly applicable to heterogeneous graphs, which have multiple types of nodes and edges, due to two key issues: (1) the presence of nodes with undefined features hinders diffusion-based imputation; (2) treating various edge types equally during diffusion does not fully utilize information contained in heterogeneous graphs. To address these challenges, this paper presents a novel imputation scheme that enables diffusion-based imputation in heterogeneous graphs. Our key idea involves (1) assigning a {\it virtual feature} to an undefined node feature and (2) determining the importance of each edge type during diffusion according to a new criterion. Through experiments, we demonstrate that our virtual feature scheme effectively serves as a bridge between existing diffusion-based methods and heterogeneous graphs, maintaining the advantages of these methods. Furthermore, we confirm that adjusting the importance of each edge type leads to significant performance gains on heterogeneous graphs. Extensive experimental results demonstrate the superiority of our scheme in both semi-supervised node classification and link prediction tasks on heterogeneous graphs with missing rates ranging from low to exceedingly high. The source code is available at https://github.com/daehoum1/hetgfd.

Published as a conference paper at ICLR 2025
RELATION-AWARS DIFFUSION FOR HETEROGENEOUS GRAPHS WITH PARTIALLY OBSERVED FEATURES
Daeho Um'
Yoonji Lee Samsung Electronics
AT Center, Samsung Electronics daeho. um8 samsung... com
11811.1ee@sa weee@ssamunggccmmm com
Jiwoong Park
Seulki Park
Department of Electrical and Computer Engineering Texas A&M University
University of Michigan seulki @umi ch edu
ptywoonge gma com
Yuneil Yeo
Scong Jin Ahn KAIST sjal015ekaist.ac.
Department of Civil and Environmental Engineering UC Berkeley yuneily@beerkeeyy.ed
ABSTRACT
Diffusion-basse -based imputation methods, which impute missing features through the iterative propagation of observed features, have shown impressive performance in homogeneous graphs. However, these methods are not directly applicable to het- erogeneous graphs, which have multiple types of nodes and edges, due to two key issues: (1) the presence of nodes with undefined features hinders diffusion-bart imputation; (2) treating various edge types equally during diffusion does not fully utilize information contained in heterogeneous graphs. To address these chal- lenges, this paper presents novel imputation scheme that enables diffusion-bast based imputation in heterogeneous graphs. Our key idea involves (1) assigning a virtual feature to an undefined node feature and (2) determining the importance of each edge type during diffusion according to a new criterion. Through experiments, we demonstrate that our virtual feature scheme effectively serves as bridge between existing liffusion-based methods and heterogeneous graphs, maintaining the ad- vantages of these methods. Furthermore, we confirm that adjusting the importance of each edge type leads to significant performance gains on heterogeneous graphs, Extensive experimental results demonstrate the superiority of our scheme in both semi-supervised node classification and link prediction tasks heterogeneous graphs with missing rates ranging from low to exceedingly high. The source code is available https: / thub. c daehoum! /hetgfd.
INTRODUCTION
Missing data is prevalent problem the real world, caused by various factors including measure- ment failures and cost constraints during data collection (Allison, 2009). This poses a challenge for various machine learning techniques, as they typically assume complete (fully observed) input data. To address this problem, traditional imputation methods such utilized to fill in missing values (Armitage et al., 2015). However, in situations with high missing rates, traditional imputation methods show limitations in maintaining the performance of machine learning techniques in downstream tasks (Rossi et al., 2022). Morcover, missing data problem be- comes more challenging when handling graph-structured data, which contain internal relations.
mean imputation are widely
To address this problem in graph-structure data, recently, imputation methods based on graph dif- fusion (Rossi et al., 2022; Um et al., 2023; 2025b) have been proposed, which iteratively propagate observed features to missing features without training neural networks. These diffusion-bant ods have attracted great attention due to their various advantages: exceptional performance in down- stream tasks, fast imputation time, and being agnostic to downstream network design. Diffusion-
meth-
"Corresponding author

---

Published as a conference paper at ICLR 2025
based methods assume that given data are homogeneous graphs, where all nodes are of the same type and all edges represent the same types of relations. However, there are various objects and rela- tions in real-world scenarios. Heterogeneous graphs, containing multiple types of nodes and edges, have been widely studied due to their ability to model the diverse and complex nature of real-world scenarios, such as wireless networks with various devices and link types (Zhang et al., 2019).
Although both heterogeneous graphs and the problem of missing data hold important positions in real-world applica- tions, imputation for heterogeneous graphs very challeng- ing due to the complex relations between various objects. In most real-world heterogeneous graph datasets, only nodes of a certain type possess features. Figure demonstrates an example of a real-world heterogeneous graph. As shown in the figure, only 'Movie' nodes have features (i.e., are attributed) while 'Actor' and 'Director' nodes do not have features (i.e., are non-attributed). However, in real-world heterogeneous graphs, missing data can occur even within features of attributed nodes 'Movie' nodes in Figure 1. While several studies have been proposed to address unde- fined features for non-attributed nodes (Jin et al., 2021; Wang et al., 2022), they are based on the strong assumption that all features in attributed nodes are fully observed. To the best of our knowl- edge, missing feature imputation within attributed nodes is underexplored. We tackle this problem in heterogeneous graphs, where both undefined features for non-attributed nodes and missing features within attributed nodes coexist, presenting challenging but practical scenario.
Actor
Movie
Director
Known feature Missing feature
Figure 1: An example real-world heterogeneous graph.
When attempting to apply diffusion- -based methods (Rossi al., 2022; Um al., 2023; 2025b) to missing feature imputation within attributed nodes on heterogeneous graphs, there are two challeng- ing issues. (1) Attributed nodes often lack direct connections to each other, hindering imputation via diffusion. Since diffusion- -baed impute methods fill in missing values by aggregating features in neighboring nodes, missing features cannot be filled in without direct connections among attributed nodes. (2) In a heterogeneous graph, each edge type represents distinct relation. For instance, in Figure I, an 'Actor' and 'Movie' node are connected via an 'is starred in' relation, while 'Movie' node and 'Director' node connected via an 'is directed by' relation. Thus, simply treating all edge types equally cannot fully utilize the relational information contained in heterogeneous graphs
To tackle these challenges in heterogeneous graphs, we present HetGFD (Heterogeneous Graph Feature Diffusion), a novel diffusion-based imputation method for heterogeneous graphs. Our key idea involves (1) generating virtual features for non-attributed nodes and (2) ranking edge types according to new criterion called edge-type-wise homophily. For issuc (I), virtual features on non- attributed nodes are initialized to zero values, and enable diffusion- imputation by acting as real features. To address issue (2), during the diffusion process, leverage our proposed edge-type- wise homophily to enable relation-aware distance encoding, leading to relation- diffusion. Through experiments, we verify that these methods successfully maintain their effectiveness in heterogeneous graphs. Furthermore, extensive experimental results demonstrate the superiority of our HetGFD over tfate-of-the-ar methods in both cemi-supervised node classification and link prediction tasks on benchmark datasets. We also show the applicability of HetGFD to the biomedical domain. We confirm that HetGFD performs well even with an extreme missing rate of 99.5%.
Our key contributions summarized as follows: 1) To the best of our knowledge, this work is the first attempt to leverage diffusion-based feature imputation for heterogeneous graphs and to design relation-aware distance encoding. Our virtual feature scheme enables the use of inffusion-based imputation methods and successfully transfers their effectiveness to the heterogeneous graph do- main. 3) We define a new measure, edge-type-wor homophily, to adjust the influence of each edge type during diffusion. By utilizing edge-type-wis. homophily, HetGFD, tailored to heterogeneous graphs, outperforms state-of-the-a methods across various domains, including the biomedical do- main, by treating multiple edge types differently.
2 RELATED WORK
Handling Missing Features in Graphs. The problem of missing data has been extensively studied in the literature (Allison, 2009; Loh & Wainwright, 2011). However, in cases where the rate of missing features is substantial, accurate reconstruction becomes challenging. Besides, achieving
2

---

Published as a conference paper at ICLR 2025
type attributed
Node types noo-sttributed nodes
A missing feature
Virtual features assigned to non-attributed nodes
Generate virtual features
Rank edge types
soos
Final
SOD POD
output
3rd
X
X
1st
2nd
soot
Initial Missing
Preliminary Diffusion
Relation-Aware Diffusion
Figure 2: A brief overview of Heterogeneous Graph Feature Diffusion (HetGFD). Virtual features generated for non non-attributed nodes enable diffusion- -bsedd imputation. Since the calculation of edge- type-wise homophily requires a complete feature matrix without missing features, we first impute missing features via the preliminary diffusion stage. Subsequently, using these pre-imputed fea- tures, edge types are ranked according to edge-type-wisg homophily. A final output obtained via relation-aware diffusion where the edge-type ranking plays important role.
accurate reconstruction does not necessarily guarantee high performance in downstream tasks (Um al., 2023). Thus, recent research directions of feature imputation in graphs focus on enhancing performance on downstream tasks rather than achieving perfect restoration. While GCN (Kipf & Welling, vaaarant methods (Jiang & Zhang, 2020; Taguchi et al., 2021) utilize new GNN architectures to enhance the performance in downstream tasks with missing features, diffusion-based methods (Rossi et al., 2022; Um et al., 2023) (different from generative diffusion models (Ho et al., 2020; Dhariwal & Nichol, 2021; Yeo & Um, 2025)) have significantly improved the performance by imputing missing features through the diffusion of known features. However, as most methods for addressing missing features in graphs focus on homogeneous graphs, they cannot handle complex graphs with multiple node and edge types. Recently, several approaches have been proposed to learn representations for non-attributed nodes heterogeneous graphs (He et al., 2022; Jin et al., 2021; Wang et al., 2022). However, these studies commonly assume that all nodes in an attributed node type have all their features intact, which can cover only limited missing scenarios. In contrast, we aim to handle the presence of missing features within attributed nodes, which makes the problem more challenging. While Zhang et al. (2023) is related our work, targets Similarly, Gupta et al. (2023) is relevant; however, it does not consider multi-type nodes or edges.
graphs.
Heterogeneous GNNs. While GNNs (Kipf & Welling, 2016a; Veličković et al., 2017; Lim et al., 2021; Um al., 2025a) have proven to be a powerful approach for learning graph representations, most GNNs have primarily focused on homogeneous graphs. Hence there have been considerable efforts to extend the advantages GNNs to heterogeneous graphs (Zhang et al., 2019; Wang al., 2019; Fu et al., 2020; Hu et al., 2020b). For example, Heterogeneous Graph Transformer (HGT) (Hu al., 2020b) adopts the architecture design of Transformer (Vaswani et al., 2017) to learn node rep- resentations before message passing. Additionally, Guo et al. (2023) proposes meta- reeta-path-induced metric to quantify the degree of homophily. However, it can only deal with meta-paths between nodes of the same type. Unlike the homophily we define, this metric is measured based pre- defined meta-paths rather than actual edges.
Distance Encoding. Based on feature homophily, we assign the importance of each feature during diffusion by measuring the shortest path distance between the feature and known features. Distance encoding for graphs generates auxiliary node features calculated by the distance from designated nodes to another node. These generated features are then utilized to perform a given task. For in- stance, nodes are assigned new features based on the distances to target nodes (Zhang & Chen, 2018; Zhang et al., 2021). ). Position-awan graph neural network (P-GNN) (You et al., 2019) leverages the distance between a given target node and sampled anchor node sets. To enhance the expressive power of graph neural networks, an additional node feature called distance encoding is proposed (Li et al., 2020). While distance encoding- based heterogeneous graph neural network (DHN) (Ji et al., 2021) extends distance encoding heterogeneous graphs, DHN does not consider different edge types during the distance measurement. In contrast to previous approaches in distance encoding, we propose relation-aware distance encoding, considering multiple edge types.
3

---

Published as a conference paper at ICLR 2025
3 PROBLEM SETTING
heterogeneous graph denoted by 9 = (V, T, where V= {ui) the set of N nodes, E is the set of edges, T is the set of node types, R is the set of edge types, and IT| + |R] > 2. To express nodes linked by an r-type edge, we let (v, r; f2y) denote an r-type edge connecting 1, and Uy, i.e., (Vi, T, m2) E E. We let R (1IR)...1 to indicate each edge type in R. E, denotes the set of edges of type where E R so that UrERÊ, E. We introduce A {0, 1] J to denote an adjacency matrix. A representative dataset for a heterogeneous graph g is the DBLP dataset which consists of four node types (paper, author, term, and conference) and three edge types (paper-author, paper-term, and paper-conference).
The tt-type nodes with partially known features are called attributed nodes and the other nodes where features are undefined are called non-attributed nodes. V denotes the set of attributed nodes. V denotes the set of non-attributed nodes. N+ and N denote | and |V respectively, where [V] indicates the cardinality of node set V. Letting F be the number of feature channels of each node in V*' X IR N denotes the node-feature matrix for V+
Attributed nodes with partially known features mean that the node-feature matrix X E R x has missing elements. (:d)) denotes a set of nodes with unknown features in d-th channel, where the nodes correspond to the rows with missing elements in the d-th column of X. The set of remaining
nodes with known features in the d-th channel is denoted by ((d)) Thus Vid and V((d)) become a partition of V+.
Under the above setting, we tackle the problem of learning on heterogeneous graph with missing node features. The problem learn a function that produces desired output Y of a given task (e.g.. semi- semi-supervised node classification or link prediction) on G with partially known node features. To this end, we aim design an imputation scheme for missing features in X of V+, which maximizes the performance of downstream GNN for given task.
PROPOSED METHOD
4.1 OVERVIEW OF HETGFD
Figure provides a brief overview of the proposed scheme called heterogencous graph feature diffu- sion (HetGFD). HetGFD consists of two diffusion stages: preliminary diffusion and relation-aware diffusion. For relation-aware diffusion, distinct importance for each edge type is required. Thus, the preliminary diffusion stage first assumes equal importance for all edge types and generates pre-imputed matrix. This pre-imputed matrix is then used to determine the importance each edge type. The importance of each edge type enables relation-aware diffusion, which produces the final imputed matrix.
4.2 PRELIMINARY DIFFUSION
Diffusion-based methods (Rossi al., 2022; Um al., 2023) developed for homogeneous graphs update unknown features and utilize the unknown features as pathways to spread known features si- multancously. However, in a heterogeneous graph with non-attributed nodes, the diffusion blocked by the absence of features. To tackle this challenge, we define virtual features filled with zeros for every non-attributed node in V", where the dimension of the virtual features is set to the same dimension of features in the attributed node (i.e., F). These virtual features are then iteratively up- dated through the preliminary diffusion propagating known features, enabling the missing features at attributed nodes in V to be updated via diffusion across all nodes in both -/ and y+, While we assume a single attributed node type, HetGFD can handle not only G with a single attributed node type but also G with multiple node types with different attribute distributions (e.g.. different feature dimensions). In such cases, we can impute missing features in each node type by applying HetGFD independently.
In our design, we adopt a channel-wise formulation with d-th channel. For notational convenience, reorder all nodes in V in the order of v(d)) v(d)) and V According to the order of the reordered nodes, the feature vector and the r-type adjacency matrix can be written as:
(d)7
(d.r)
(d.r)
A (d.r)
x
Ew
(d)
x
(d)
(d.r)
A (dir)
uk
(d.r)
A (d.r)
(1)
(d)
(dir)
(d.r)
A (d.r)
4

---

Published as a conference paper at ICLR 2025
where X (d)
(d)
and (d)
are column vectors that denote d-th channel feature vectors concatenated for all nodes in Dia ydd) and yاا respectively. Here, V((a) is referred to source nodes. x (d) consists of virtual feature values. Similarly, A (dr) E R is composed of nine sub-matrices related to () v(dd) and V= g(d) denotes the edge set of the reordered nodes for d-th channel.
The preliminary diffusion is performed by iterative propagation using transition matrix for each channel. Since the preliminary diffusion does not account for the importance of each edge type, assigning equal weights to all nodes when constructing the transition matrix may seem reasonable approach. However, this approach can result in biased diffusion, where propagation predominantly occurs along the majority edge type. To address this issue, we introduce a penalty for the majority edge type when defining A (d.r) E RNNN
|E.1T if A #0 otherwise
(d.r)
(2)
We then sum A (d.r) over all edge types to construct A (40) ..e., A(4) =00=>a E (d.r)
Next, to ensure that each updated feature is generated as a weighted average of neighboring features, we nor-
-- malize A (d) to compute a a row-stochastic matrix M(4) E RNXN, Formally, M = (D( -1 A (d) where
D Σ, A. To preserve the known features x during the preliminary diffussio, we replace the first
| rows of ( with ( E RNNN;
I
Oku M
Og- M (d)
(
M uk
(3)
M
M
M
where I E "
(xin) is an identity matrix, and Okn and O2- are zero matrices. Using (d) a transition matrix, the preliminary diffusion defined by
x (1)
((00((00)
1), 1= 1....... K;
X
(4)
4 (0)
O.
where x (1) denotes an imputed feature vector after propagation steps. Here, O,, and O_. are zero column vectors with length of [V! and N- respectivel. As K + oo, the recursion converges, and (K) reaches a steady state. We prove the convergence in Appendix A. It is noteworthy that we initialize the values with zeros based on this proof. The proof shows that initial values for x(!!) and x (d) do not affect the steady state. With sufficiently large K, we approximate the steady state (K). Since the imputed feature x( has different ordering from the original one, we rearrange (K) to x(d(() in the original order. We then obtain a pre-imputed feature matrix X RN by concatenating (K))) along the channels.
lim (() to (K))
4.3 EDGE-TYPE-WE WISE HOMOPHILY
With the introduction of virtual features, pre-imputed features can be obtained for all nodes, en- abling the comparison of features between attributed and non-attributed nodes. Feature homophily the working principle of diffusion- imputation methods developed for homogeneous graphs. However, in heterogeneous graphs, different edge types contribute to feature homophily in varying degrees. For example, two papers written by an author may have more similar features compared to two randomly chosen papers submitted to the same conference. Therefore, we aim to enhance message passing along edge types that significantly contribute to feature homophily in the relation- aware diffusion process. To quantify the contribution of each edge type, we define new criterion named edge-type homophily, denoted by H.
Definition 1. Edge-type-wir homophily of edge type for a given feature matrix X is defined by
H(r) | Eieerapye sim (X, X
(5)
E www.imm n.:3 X xm.)
where sim((..) denotes cosine similarity between two row vectors, and X.:: denotes the z-th row vector of X. Evn.,.eelsii((.... ev(sim(Xn.. Xm.)] is calculated from randomly sampled node pairs in V.
5

---

Published as a conference paper at ICLR 2025
S = 2
= = a 120
(0 (0<a) a. 11)
node
W
1-th channel
Figure 3: An illustrative example of relation aware distance encoding. The shortest path distance from source nodes (SPD-S) is utilized to calculate pseudo-confidence (PC), which indicates the influence of each feature during diffusion. According to edge-type ranking based on H, edge weights in (d)) are assigned using 3. The key idea is to rapidly decrease PC of features that are connected with observed features via low-ranking edges.
We calculate Then, we rank the edge types in descending order of H(r), i.e., H(ri) > > M(((Rj), which means that r is the edge type with the k-th highest homophily, As a result, edge-type ranking is prepared prior to the relation-awe aware diffusion.
homophily H(r) by using the pre-imputed feature matrix X RXF.
4.4 RELATION-AWARE DIFFUSION
To build a transition matrix for relation aware diffusion, we utilize the concept of pseudo-confidenec (PC) (Um et al., 2023). Pseudo-confidence (PC) represents the importance of each feature in the diffusion process. As PC of a feature increases, the feature can propagate its value more strongly. PC assumes that missing feature located far from source nodes is more likely to be imputed with an inaccurate value. Consequently, Um et al. (2023) decreases PC as the distance between a feature and the nearest source nodes increases. PC defined as:
Definition 2. Pseudo-confidence of Xi,a is defined by Ei, a (0 < a < 1) where Sta denotes the shortest path distance between the i-th node and its nearest source node (SPD-S), a is hyperparameter.
Since PC is developed for homogeneous graphs, here Si, E (x E Z/x 2 0}.
However, given the nature of heterogeneous graphs with multiple edge types, treating all edges equally can result in information loss. We enhance PC by incorporating edge-type-wise distinctions. We extend PC weighted graphs, implying that St.d {æ E R| 2 0} unlike existing PC. To obtain the weighted graphs where our new PC is calculated, we leverage the edge-type ranking.
Since PC and edge-type ranking are commonly based on feature homophily, the two concepts can be naturally combined. The key idea is to rapidly decrease the PC of feature when it is connected source nodes primarily through low-ranking edges (i.e., edges belonging to a low-H edge type). Accordingly, we assign greater weights low-ranking edges in the weighted graph W(d) (d) used for PC calculation.
Formally, weighted adjacency matrix (d.r) obtain St, is defined
(k-1) if ((,,,, = rí
w(dd)) fJ
(6)
0
otherwise
for (o,, r, Ui) E g(d), where 3 is a hyperparameter between and 1 and vf()) is numbering function from edge type to r with ranking We attain W(d) by summing ((dr) for all edge type r E R.
Aligned with our key idea, as the ranking of edge type drops (i.e., H(r) decreases or k increases), the weights for r-type edges in (dd) increase by dividing by 3, as defined in Eq. (6). To calculate PC, defined as Eidd Si. the shortest path distance from source nodes Si, on (id) is given by:
S SPD--S( w(d)),

---

Published as a conference paper at ICLR 2025
where SPD-S is function that outputs the shortest path distance from the i-th node to the source nodes (i.e., the nodes in D(()) on W(d), By Definition we can calculate PC of each feature value with Si,d measured on W(d), In Figure 3, the calculation process of PC is illustrated. It is important to note that W(d) is not a transition matrix for relation-aware diffusion but is exclusively utilized for the calculation PC.
In addition to PC for adjusting the importance of each feature during relation-aware diffusion, we assign greater weights to high-ranking edges (i.e. edges belonging to high-H edge type). To construct a transition matrix for relation-awarr diffusion, we define an asymmetric weight matrix W(dr) where element Wild.)) represents the weight of a directed edge from j-th node to i-th node, defined by:
118h1 Ej,a/Eid if (( = 0
w
(8)
otherwise
for (v,, (e,r, Uz) E E(d), The term 3h-1 in Eq. (8) accomplishes objective that the higher the ranking of an edge becomes (k decreases), the higher the edge's 's weight becomes. The term & strengthens the message passing from high-PC features to low-PC features, indicating that high-PC features propagate their values more strongly than low-PC features. If Çi,a is lower than Ej.d. the term Ej.a/C Ei is larger than which strengthens the weight of directed edge from the j-th node to the i-th node.
We compute W(l) as W(d) = EPER W(d.), Next, we normalize ((d) to obtain a row-stochastic
transition matrix T(d), defined as T(d) = (Drid) > Wil,, where De = =, W.G To preserve
i the known features, we replace the first ( rows of ((d) with ((d) as follows:
0 kuu
Og
T(d
T
(2)
T
(d)
((d)
(9)
uk
The relation-aware diffusion for final imputation is defined by
x x10 (l)
(()) 1), t= 1.... K;
(d) x On
(0)
&
(10)
0_
where (())(t) is an imputed feature vector in relation-aware diffusion through propagation steps. We use x(() (K) with large enough K to approximate a steady state of x(() (t). After obtain- ing (x(a)) (K)] via the channel-wise diffusion, we rearrange (x((((
in the original or- der. Then, we attain an imputed feature matrix & by stacking the originally ordered vectors in (K)) along the channels. Finally, we obtain X' E g xF by removing all rows corre- sponding to V from & X is an output of HetGFD and is fed to GNNs for downstream tasks.
In summary, our HetGFD framework addresses two critical challenges in heterogeneous graphs: handling non-attributed nodes through virtual features and accounting for distinct relations via edge- type-wise homophily H. Leveraging H. which aligns with the principles of diffusion-baat tation, HetGFD controls the overall diffusion process at both the feature level and the edge level in heterogeneous graphs. This dual control, with consideration of edge types, creates a significant gap compared to PCFI, which simply utilizes PC computed on unweighted graphs. This enables the use of information inherent in the edge types of heterogeneous graphs, resulting in imputed features that are beneficial for downstream tasks in such graphs.
impu-
5
EXPERIMENTS
5.1 EXPERIMENTAL. SETUP
Data Setting. We conduct experiments three widely used heterogeneous graph datasets (ACM, DBLP, and IMDB) (Jin et al., 2021) from different domains. Detailed descriptions of these datasets and their sources can be found in Appendix B.2. To conduct experiments graphs with missing
7

---

Published as a conference paper at ICLR 2025
Structural missing
Uniform missing
80
+0.13%
80
+0.18%
+1.51%
+0.58%
75
77
+1800
+4066
70
74
71
0
0.5
0.9
0.995
0.5
0.9
0.995
Zaro 4P Mean
KNN 0
SVD d
GAIN
GRAFENNE
FP+VF PCF
HetGFD (ours)
Figure 4: Performance averaged across the three datasets in semi-supervised node classification, measured in terms of Macro-F1 (%) under structural-missing settings with varying missing rates I'm E {0, 0.5, 0.9, 0.995). HGNN-AC is consistently used as downstream GNN. VF denotes our virtual feature scheme. Figures highlighted in red indicate performance improvements over the most competitive baseline across each setting.
features, we remove fixed rate of features in the datasets. Note that in the original data, raw features exist only for paper-type nodes in ACM and DBLP, and for movie-type nodes in IMDB. That is, only nodes of a single specific type (attributed-nool information. To compare the performance of imputation methods, we introduce missing values into a feature matrix from an attributed node type. Specifically, we remove features according to a missing rate, denoted Tm, ranging from 0 to 1. In the positions where features are removed, fill them with the value 'NaN'. We remove features in two ways as suggested in Um et al. (2023): (1) strucfural missing: After randomly selecting nodes with a ratio of I' among +t-type nodes, remove whole features from the selected nodes. That is, features in a node are either entirely known (observed) entirely unknown (missing). (2) uniform missing: After randomly selecting feature values with a ratio of I'm from the feature matrix X, we remove the selected features. That is, we remove features uniformly across all -type nodes.
type) are given raw features that represent semantic
Given missing rate Ti, we randomly create 10 different binary masks of feature matrix for each dataset. These masks indicate the location where feature values are missing, with a rate of Tm- We evaluate imputation methods across 10 runs, using the generated masks. To non-attributed nodes, we assign one-hot node features for each node type (e.g., author and subject in ACM) so that a fair comparison of imputation methods for attributed nodes is enabled.
Baselines. We compare the performance of HetGFD with the following seven baselines: zero im- putation, mean imputation, k-Nearest Neighbors (kNN) imputation (Troyanskaya et al., 2001), Iter- ative SVD (Troyanskaya et al., 2001), GAIN (Yoon et al., 2018), GRAFENNE (Gupta et al., 2023), FP+virtual features (FP+ VF), PCFI (Um et al., 2023)+virtual features (PCFI+VF) It is noteworthy that our virtual feature scheme enables the use of existing diffusion-based methods, including FP and PCFI, on heterogeneous graphs
Existing methods for attribute completion on heterogeneous graphs (He et al., 2022; Jin al., 2021; Wang et al., 2022) cannot be compared since all these methods focus on learning representations for non-attributed nodes (i.e., V-) under the assumption of no missing features in -T-type nodes. In real-world situations, there is guarantee that missing data occurs only in specific types, our setting can be widely applied to various real-world applications. We demonstrate that HctGFD is in collaborative relationship with attribute completion methods by utilizing HGNN-AC (Jin et al., 2021) as a downstream GNN.
Implementation Details. Except GRAFFENE which is a GNN framework, we feed a complete feature matrix obtained by the imputation methods into downstream GNNs. For a fair compari- son of imputation methods, we adopt HGT (Hu et al., 2020b) for downstream GNNs, which is a state-of-the-al heterogeneous graph neural network. For link prediction, we utilize embeddings ob- tained from GNN with HGT layers. To predict a link between a pair of nodes, we adopt the dot product of embeddings of the two nodes, as in Kipf & Welling (2016b); Lv et al. (2021). We fur- semi-supervised node classification using HGNN-AC
ther conduct experiments GNN for the following two reasons: 1) to demonstrate the superiority of HetGFD across various GNNs; 2) demonstrate that HetGFD can be combined with existing methods for attribute com-
downstream
8

---

Published as a conference paper at ICLR 2025
Table 1: Semi Supe-viee node classification results (%) with I'm 0.995.
GNN
Missing
Method
Maen-FFi
ACM
Macro-FI
DBLP
MicrosFi
IMDB
Micro-Fi
Tull features
92.52 1 0.41
92.48
1 0.41
B1 1:11
91.08
1.11
54.51 1 4.74
56.38 - 4.74
Zero
82.75 1: 1.40
83.44 1: 1.21
90:11 1.06
90.90
1.33
36.29
1.50
47.91
0.89
Mesn
83.20 + 1.20
83.90 + 1:20
89.58 + 2.02
90.74
2.002
45.35
+ 2:21
48.21
= -2221
Structural
KNN
SVD
60.71 + 1.57
82.67 = 1.54
85.20
88.56 +: 1.82
1:15
90.37 +: 1.07
00:11 1:46
91.04
90.90
1.70
1.46
16.28
68.88
+ 3.25
48:22
47.91
= 1.58
1.82
micsing
GAIN
82,84 1.50
83.58
1.27
90.08 1.25
90.85
1.11
GRAFENNE
52.77 7.26
65.49
5.17
18.65 3.15
27.73
0.94
27.20
8 2.7.3
1.76
HGT
FP-VF
PCFT-VP
1.22
10:30
00-41 1.25
91.17
(ours)
0.51
90.88
91.
46.88
Zero
SL.6
82.67 1.051
10011 1:37
50.300
Mean
52.76 1. 1.51
85.48
1.51
00:54 1.62
91.32
36.53
68.30
1.49
Uniferm
INN
81.01 0.85
82.43
0.30
00:50:
91:20
15.81
2:30
65.70
1.15
SVD
S0.45 2. 2.22
81.52 4: 2:17
90-331 4: 1.86
91.07
1.82
46.53
6.
48.08
1.26
missing
GAIN
82.98 + 0.76
83.84 + 0.78
00002 + 1.41
91.01
1.41
06.54
1.50
48.48
1.59
GRAFENNE
73.04 1 1.54
74.29 1 1.06
17 2.24
28.0
0.91
36.51
1.88
39.82
1.60
TT-VT
20.50 1 175
BUA49 1108
BK115 1:30
50.001
1.49
15:35
2311
US.11
2701
VC
96.26 2: 0.50
86.51
4: 0.60
90.
2: 1.43
91.14
1.35
47.25
2 1.88
49.14
1.38
HalDFD (ouns)
88.14 + 0.89
88.14 + 0.60
90.05 + 1.53
91.40
1.24
48.57
1.41
50.57
1.06
Table 2: Link prediction results (%) with I'm
0.995. AUC denotes the ROC AUC score.
Missing type
Method
AUC
ACM
AP
AUC
DBLP
AP
AUC
IMDB
AP
Full feutures
76.25 1: 1.20
77.64 2: 1.07
71.52 a 0.51
08.92
1: 0.66
92.17 1: 1.06
56.91
1: 1.61
Zero
71.65 4. 2.16
71.74 2: 3.55
72.49 1 0.63
14.21 1: 0.60
92.48
2: 1.06
86,95 4: 1.00
Mean
71.64 1,30
71.66
1.33
72.49
16.00.0.0 0.63
T1.20 1: 0.60
91.78
1.13
85,80 1 2.12
Structural
SVD
71.49 1: 1.77
72.04
1.06
72.29
72.55
2.13
72.49 1: 0.63
71.96
74:21 1: 0.60
91.10
92.18
1.06
56.95
1.00
1.97
missing
GAIN
72.22 + 1.19
73.21
1.10
72.49
+ 0.63
14:20
+ 0.61
92.48
1.06
86.95 1.00
GRAFENNE
74.87 4 6.71
67.00
:: 5.87
90.14
+ 7.26
76.53 + 7.12
82.08
4: 5.75
09.72
4.00
74100
0.34
71.28 0.85
70.01 + 1.45
1.04
56.30
PC
73.41 1.16
73.22
1.18
71.37
0.55
66.78
+ 0.74
91.71
1.33
85.37 + 2.08
HeGGD cours)
78 + 1.34
78.62
2.12
91 11.9442 0.67
91.88-2
0.91
9/2 50
1.04
86. 91
1.58
Zero
1.48
3.07
72.48
0.61
T4:20 0.60
50
Mean
71.98 1: 1.00
72.02
0.96
72:48
0.62
74.20 0.60
91. 1.14
65.33 1:93
missing
Uniform
KNN
SVD
GAIN
70.49 010-::24 2.11
71.9210..0 0.92
71.02 1.19
72.19
73.17
70.70
:: 2.06
4.08
72-48 0.62
72.48
72:72 1 1.85
70.29 1: 3,73
T4:20 0.60
0.060
9/.550 02..500
91.15 1: 1.09
1.04
86 91
81.50 1 2.01
1.58
GRAFENNE
74.76 9.82
72.96
9.71
63.78
31.28
86 28.14
30,69 + 15.81
22 1 14.33
FP-VF
78.18 4: 0.96
79.77
0.82
71.86
1.66
70.03
+: 1.97
91.52
1.15
85.67 1: 2.14
PCFI-VF
71.94 1.37
73,80
1.03
70.76 11 3.14
08.97
1: 3.85
91.51 2:
65.70 2.08
HeGGFD (ours)
76.96 1.74
77.19
1.98
92.17
0.56
92.
12.12 0.53
91.95
86.72
3.40
pletion in heterogeneous graphs, which assume full features in t +t-type nodes. We include further details on experiments (e.g.. hyperparameter tuning, baseline implementation, train/ fainn/vaiiaaion/tess splits, and training details) in Appendix B. Further experimental results, including ablation study, time complexity, and qualitative results, can be found in Appendix D. Due to space limitations, the experimental setup for the PPI dataset (Zitnik & Leskovee, 2017) in the biomedical domain is described in Appendix B.5.
5.2 SEMI-SUPERVISED NODE CLASSIFICATION RESULTS
Figure 4 shows the trend of Macro-F1 F1 scores for the compared methods when HGNN-AC models are used for downstream GNNs across all the methods. Macro-F1 tends to decrease across all methods as the missing rate I' increases. Notably, the compared methods, except for the diffusion-based methods, exhibit significant performance degradation. This result suggests that diffusion-based methods are also effective in heterogencous graphs. Among the diffusion--aase methods, Het- GFD outperforms both FP+VF and PCFI+VE. Moreover, the performance gain of HetGFD tends to increase as I'm increases. This is because when I'm is low, the other methods can also maintain a certain level of performance using remaining known features. However, when Tmm increases, the importance of imputation becomes greater as the proportion of imputed values in output ma- trix increases. HetGFD demonstrates remarkable resistance to high Tm as evidenced by the results obtained from different settings. Table shows the overall results of semi-supervised node clas- sification with Tm = 0.995 when HGT is used as the downstream GNN (results for HGNN-AC are provided in Appendix F). HetGFD shows superior performance compared to all other methods regardless of downstream GNN in all settings with r'm = 0.995.
5.3 LINK PREDICTION RESULTS
The link prediction results under the missing settings with rm 0.995 are shown in Table 2. During the experiments, we observe that Zero Mean, SVD, and GAIN impute values very close to 0 for the missing features at r.. 0.995. We found that this observation leads to similar performance

---

Published as a conference paper at ICLR 2025
Table 3: Performance the protein-protein interaction networks (PPI) dataset for different Ym- measured by accuracy (%). VF denotes our virtual feature scheme. 'Impr'' indicates performance improvements over the most competitive baseline at each T'm
0.5
0,9
0.995
Mean
98.49 1: 0.13
64.40
1.97
64.40
1.57
62.14
0.15
KNN
98.49 + 0.13
78.74 + 1.01
64.15 - 1.18
62.20 + 0.24
GAIN
98.49 0.11
78.85
1.09
64.13
1.09
62:20
0.24
GRAFENNE
83.76 + 9.15
63.97
1.87
63.15 = 1.31
02.26
0.00
PCFI-VE
98.49
0.13
80.75
1.68
63.22
2.19
62.14 0,32
HerGFD (OUIS)
98.49
+ 0.13
81.57
1.04
66.84 : 1.92
63.20
0.37
Impr.
-1.02%
+1.51%
among these four methods. On the IMDB dataset, the results show that the overall methods perform similarly to when full features are used. This indicates that the information contained the features not useful for link prediction on IMDB. HetGFD achieves Mlateof-thhear performance across all settings except for IMDB with uniform missing. Features obtained by HetGFD contain rich struc- tural information, taking edge types into consideration, which leads to performance improvement in heterogeneous graphs.
5.4 APPLICABILITY TO THE BIOMEDICAL DOMAIN
To demonstrate the applicabiliity of HetGFD biomedical domain, conduct experiment the protein-proted interaction networks (PPI) dataset, which is used for analyzing biological relevance and disease understanding. Table 3 shows the semi-supervised node classification performance of different imputation methods on the PPI dataset, where structural missing is applied using different Tm- As shown in the table, the accuracy of all methods commonly decreases as I'm increases. However, our HetGFD consistently shows the best performance across various Tm- Among type and type B edge types, we observe that type exhibits higher edge-type-wiss homophily, and HetGFD) assigns more importance to type A edges. We attribute the performance gains of HetGFD to the correlation between the edge types and the class label. Unlike existing methods, HetGFD differentiates between edge types, enabling more effectively utilize the information contained within them.
COMPLEXITY ANALYSIS
The time complexity of HetGFD involves three main processes: two diffusion stages (O(LE))) edge- type-wise homophily calculation (O(F'. |E()), and PC calculation (O(N²)). In structural -iissug settings, a single PC calculation is needed (O(F. [3] + N2)), while in uniform- mooosin settings, F PC calculations required (O(F. |8] F N2)). Notably, PCFI, the most competitive baseline, also involves PC calculation with O(N2). Compared to PCFI, HetGFD consistently demonstrates superior performance across all experimental settings. more detailed time complexity analysis is provided in Appendix D.3.
CONCLUSION
In this paper, introduce virtual features that enable the use of liffusion-based imputation heterogeneous graphs. Building on these virtual features, we propose a novel imputation method called Heterogeneous Graph Feature Diffusion (HetGFD) tailored heterogeneous graphs. Het- GFD ranks each edge type according to edge-type-wise homophily, and this edge-type ranking facilitates relation-aware distance encoding. By treating each edge type differently, HetGFD, us- ing relation- diffusion, shows its superiority over state-of-the methods on semi-supervised node classification and link prediction tasks across various domains. We further confirm that our virtual feature scheme effectively transfers the advantages of existing diffusion-basee methods to the heterogeneous graph domain. We believe that our work will significantly contribute to solv- ing missing data problems in various real-world scenarios that contain heterogeneity, due to the effectiveness and rapid imputation time of HetGFD. However, its effectiveness may be limited on hettrpp-htteoophilic heterogeneous graphs, where most paths connecting attributed nodes are het- erophilic connections. Additionally, HetGFD will be effective when all nodes belonging to node type with features have features of the same nature and scale.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Paul D Allison. Missing data. The SAGE handbook of quantitative methods in psychology, pp- 72-89, 2009. 1.2
Emily Grace Armitage, Joanna Godzien, Vanesa Alonso-Herren Angeles López- Lónzz-Gonzälvez, and Coral Barbas. Missing value imputation strategies for metabolomics data. Electrophoresis, 36 (24):3050-3060, 2015.
Abraham Berman and Robert J Plemmons. Nonnegative matrices in the mathematical sciences. SIAM, 1994. 14
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. Advances in neural information processing systems, 34:8780-8794 2021.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02444 2019. 15, 23
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. Proceedings of The Web Conference 2020, pp- 2331-2341, 2020. 3
Jiayan Guo, Lun Du, Wendong Bi, Qiang Fu, Xiaojun Ma, Xu Chen, Shi Han, Dongmei Zhang, and Yan Zhang. Homephily-orrentted heterogeneous graph rewiring. arXiv preprint arXiv:2302.06699, 2023.
Shubham Gupta, Sahil Manchanda, Sayan Ranu, and Srikanta J Bedathur. Grafenne: Learning on graphs with heterogeneous and dynamic feature sets. International Conference on Machine Learning, pp. 12165-12181. PMLR, 2023. 3, 8, 15, 16
Dongxiao He, Chundong Liang, Cuiying Huo, Zhiyong Feng, Di Jin, Liang Yang, and Weixiong Zhang. Analyzing heterogencous networks with missing attributes by unsupervised contrastive learning. IEEE Transactions on Neural Networks and Learning Systems, 2022. 3,
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
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. Advances in neural information processing systems, 33:22 177221882200 18-22133, 2020a. 23
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogencous graph transformer. In Proceedings of the web conference 2020, pp. 2704-2710, 2020b. 3, 8, 17
Houye Ji, Cheng Yang, Chuan Shi, and Pan Li. Heterogeneous graph neural network with distance encoding. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1138-1143. IEEE, 2021. 3
Jiang and Ziyan Zhang. Incomplete graph representation and learning via partial graph neural networks. arXiv preprint 2:Xi::2003.10130 2020. 3
Di Jin, Cuiying Huo. Chundong Liang, and Liang Yang. Heterogeneous graph neural network via attribute completion. In Proceedings of the Web Conference 202/, pp. 391-400, 2021. 2, 3, 7, 8, 16, 17
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14XX::1412.6988 2014. 17
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: weteii.09..2200 02907, 2016a. 3,
Thomas N Kipf and Max Welling. 16X1:1611.003000 2016b. 8,
Variational graph auto-encoders.
arXiv preprint
11

---

Published as a conference paper at ICLR 2025
Pan Li, Yanbang Wang. Hongwei Wang. and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465-4477 2020. 3
Jongin Lim, Daeho Um, Hyung Jin Chang, Dae Ung Jo, and Jin Young Choi. Class-attentive dif- fusion network for semi-supervised classification. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 8601-8609, 2021.
Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity. Advances in neural information processing systems, 24, 2011. 2
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, pp. 1150-1160, 2021. 8
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. 15
Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. On the unreasonable effectiveness of feature propagation in learning graphs with missing node features. In Learning on Graphs Conference, pp. 11-1. PMLR, 2022. 1, 2, 3, 4, 14, 15, 16
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021. 3
Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B Altman. Missing value estimation methods for dna microarrays.
Bioinformaticx, 17(6):520-525, 2001. 8, 15, 16
Daeho Um, Jiwoong Park, Seulki Park, and Jin young Choi. Confidence-basedd feature imputation for graphs with partially known features. In The Eleventh International Conference on Learning Representations, 2023. URL
http:p/rrrrreeeeeeee/ororrmmmmmm wtw.orrrmmnddppepIe.... Kt. 1,
2,3.4, 6, 8, 14, 15, 16
Daeho Um, Jongin Lim, Sunoh Kim, Yuneil Yeo, and Yoonho Jung. Spreading cut-of-distribution detection on graphs. In The Thirteenth International Conference on Learning Representations, 2025a. URL https://///..c.. /pppnevveeeeeeeeeeeeeeeeeeeeeeee net/ http://wwneee//ouureeeeooolopo Forum?1d-p11Txyyyppp
Daeho Um, Ji Won Yoon, Seong Jin Ahn, and Yunha Yeo. Gene-gene relationship modeling based on genetic evidence for single-cell ma-seq data imputation. Advances in Neural Information Processing Systems, 37:18882-18909 2025b. 1.2
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne, Journal of machine learning research, 9(11), 2008. 22
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention you need. Advances in neural informa- tion processing systems, 30, 2017. 3
Petar Veličkovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Kai Wang, Yanwei Yu, Chao Huang, Zhongying Zhao, and Junyu Dong. Heterogeneous graph neural network for attribute completion. Knowledge-Bie -Based Systems, 251:109171, 2022. 2,
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang. Yanfang Ye, Peng Cui, and Philip S Yu. Hcterogeneous graph attention network. In The world wide web conference, pp. 2022-2032, 2019. 3
Yunha Yeo and Dacho Um. The butterfly effect: Color soood-g image generation from unconditional diffusion models. IEFE Access, 2025.
12

---

Published as a conference paper at ICLR 2025
Jinsung Yoon, James Jordon, and Mihaela Schaar. Gain: Missing data imputation using generative adversarial nets. In International conference on machine learning, pp. 5689-5698. PMLR, 2018. 8, 15, 16
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International conference on machine learning, pp. 7134-7143. PMLR, 2019. 3
Chuxu Zhang. Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 793-803, 2019. 2,
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061 19073, 2021. 3
Zhiwen Zhang, Hongjun Wang, Zipei Fan, Xuan Song, and Ryosuke Shibasaki. Missing road con- dition imputation using a multi-view heterogeneous graph network from gps trajectory. IEFE Transactions Intelligent Transportation Systems, 2023. 3
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1100-i198, 2017. 9, 17
13

---

Published as a conference paper at ICLR 2025
A CONVERGENCE PROOF FOR DIFFUSION IN HETGFD
HetGFD comprised two diffusion stages: preliminary diffusion and relation-aware diffusion.
We prove the convergence of the two diffusion stages follows.
Proposition A row-stochastic transition matrix M (d) for the preliminary diffusion is expressed as
Oku
Og
M
(4)
M (d)
M
M (d)
M
M
(4)
M (d)
The recursive formula of preliminary diffusion is defined by
(t)
z 7
(t)
11)
= M x (11) (t 1), t= , K;
5 (0)
O2
Then, lim ( (K) converges.
K000
The proof of Proposition 1 follows proof' in Rossi et al. (2022): Um et al. (2023), Um et al. (2023) proves convergence of feature diffusion with row-stochastic transition matrix. Here, we prove the case when non-attributed nodes participate in feature diffusion with virtual features. We begin with two lemmas.
(D ((d))-MMe MMd) where ( Lemma 1. ( is row-stochastic matrix obtained by M (D a weighted-adjaaene, matrix of a connected graph 9 and D E, M Let M E R(N R(N-IV (N-- be the bottom-right rightt submatrix of M(d) and p(.) be spectral radius. Then, (d) 1.
p(M mn
Proof. Let M(d)
ano E N be a matrix defined by
M (c)
Obe
Ogn M
nnO
Onk
where O&k (x)1") Okn E ( IN(-- and O. E NN Since M (d) is the weighted adjacency matrix of the connected graph G, M uno I (d) clement-wisely and M (4) * M. Furthermore, M((d) + (d) an adjacency matrix of connected graph. By Theorem 2.2.7 of Berman & Plemmons (1994), ano + (4) is irreducible. By Corollary 2.5.5 of Berman & Plemmons (1994), p (M) < p (d) and by Theorem 2.5.3, ((M(d)) 1. Then, p(M((d) (d)
ano) p( (M since M(d) ano and ((d)) have the same non-zero eigenvalues. Therefore, p(M(d) (d) = p(M M(dd) 1.
Lemma 2. I ( is invertible where is the (N - ( () (N - ( identity matrix.
Proof. By Lemma. 1 1 is not eigenvalue of (d) Therefore, 0 is not eigenvalue of I - -MM/d)
Hence ( is invertible.
We now prove Proposition 1 as follows.
(d) Proof. Let (d) E Dx and M( E 1N
(N be the bottom-left and
[c] (t)
bottom-right submatrices of (d), respectively. Let -!40 (1)
Then, we can unfold the
- (d) (t)
14

---

Published as a conference paper at ICLR 2025
recursive formula of preliminary diffusion as
2((00 (t)
2 (1) =
M (1)0 (1 1)
Ih (t)
(1)
I
Okn
(d) (t 1)
M nk
M
In (1 1)
(
x& (1 - 1)
(t - 1) + M ()) ((d)
(t
In x rows from the top, x ing rows. We unroll the recursion the remaining N D rows as follows.
(1) does not change from a
Hence we only consider the remain-
i x (K)
M (d) nk T + (
(M
(d) (d)
(M K x (0)
nk 2bz
(0) 0 regardless of initial values for 10 (0) (We set the initial values to zeros implementation for simplicity).
By Lemma that lim (M )k
0, lim
(M (d) K In
K-+00
K
Since lim EFS (M (I M and p(M < 1 by Lemma. I M (d) invertible. Then,
is
K0000
K
lim (K) lim K+00
ax ((dd)) M (d)
K +00
((d)) M M (d) Tt
Here, lim 2((((K) is the first (1( rows K-o
lim K
( (K) that converges.
In the same way, the convergence of relation-aware diffusion can be proved by simply replacing M (d) with ((d).
B FURTHER DETAILS ON IMPLEMENTATION
All the models used in this paper are implemented with Pytorch (Paszke et al., 2017) and Pytorch Geometric (Fey & Lenssen, 2019). All experiments conducted with an Intel Core 15-6600 CPU @ 3.30 GHz and a single GPU (NVIDIA GeForce RTX 2080 Ti).
B. BASELINES
We compare the performance of HetGFD with the following seven baselines. (1) Zero imputation (Zero) imputes all missing features with zero values. (2) Mean imputation (Mean) imputes a miss- ing feature value at X,, with the mean of all known feature values in the j-th channel. (3) Iterative SVD (SVD) (Troyanskaya et al., 2001) 1) is structure-agnosicc method that imputes missing features by performing iterative low-rank SVD decomposition for matrix completion. (4) GAIN (Yoon et al., 2018) is structure-agnostic deep imputation method that employs generative adversarial training. (5) GRAFENNE (Gupta et al., 2023) is a GNN architecture that addresses heterogeneous features. (6) FP (Rossi et al., 2vr2utl features (FP+VF). FP is cerfuusion-bssed imputation method designed for homogeneous graphs, where known features diffuse shannel-wisely To enable diffu- sion, introduce virtual feature scheme to FP. (7) PCFI (Um al., 2virull features
15

---

Published as a conference paper at ICLR 2025
Table 4: Dataset statistics.
Datasels
Nodes
Edges
classes
Feature dimension
Target node type
Target edge type
Paper: 4014
Paper-Paper: 9612
ACM
Author: 7157
Papce-Author: 26791
3
4000
Paper
Papor-Auther
Subject:
Paper-Subject: 8028
Author: 4057
Paper-Authort 39290
DBLP
e Term: 7723
Paper:
# Paper-Temm: 171620
4
4231
Author
Paper-Auther
Paper Conference: 28656
Conference:
Movic; 4025
Movie-Dinecter: 8050
IMDB
Director: 1836
e Motie-Actor: 24144
3066 5
Movie
Movie-Director
# Actor: 4523
(PCFI+VF). PCFI is a state-of-the-art diffusion-based method for homogeneous graphs, which uti- lizes pseudo-confidence of each feature value during the diffusion. Similarly, our virtual feature scheme is employed in PCFI well.
For all baselines, we use their original hyperparameters and tuning methods specified in the re- spective papers and official codes. For two simple baselines, Zero imputation (Zero) and Mean imputation (Mean), we implement them with Pytorch built-in function. For the other baselines, we implement them follows.
k-nearest neighbor (kNN) imputation (Troyanskaya et al., 2001). We use a custom our implementation that performs imputation by creating & edges for each node based on cosine similarity and leveraging the neighborhood mean. For each setting, k is search within {1,3, 10).
Iterative SVD (SVD) (Troyanskaya al., 2001). We use the implementation from the fan- cyimpute package.' We tune hyperparameter rank in {F/5, F 1} as in the implemented code from the package.
Generative adversarial imputation nets (GAIN) (Yoon al., 2018). We the source code" released by the authors. We set all the hyperparameters of GAIN to those in the released source code.
GRAFENNE (Gupta et al., 2023). We use the source code released by the authors. We set all the hyperparameters GRAFENNE to those in the released source code.
Feature propagation (FP) (Rossi et al., 2022). We use the source code* released by the authors.
Beeudo-Confidence-baan feature imputation (PCFT) (Um et al., 2023). We use the source code released by the authors. For PCFI models, tune hyperparameter a, the search range specified in Um et al. (2023).
While the codes for SVD, FP, PCFI are Apache-2.0 licensed, the codes for GAIN and GRAFENNE have no public declaration of license.
B.2 DATASETS
ACM is citation network consisting of three node types and three edge types. DBLP is bibliog- raphy network consisting of four node types and three edge types. IMDB, extracted from an online movie database, includes three node types and two edge types. We downloaded all the datasets used in this paper from the GitHub repository for Jin et al. (2021). This publicly available repository does contain any statements ragarding licenses for the datasets. We conducted all the experiments on the largest connected components of each dataset. For disconnected graph, HetGFD can deal with by working on each connected component independently. The statisties of the three datasets are summarized in Table 4.
hhtps://githuu.com//// http://ggihbbb.cmm///s//////nnnp
16

---

Published as a conference paper at ICLR 2025
B.3
NODE CLASSIFICATION
We utilize the node split suggested in Jin al. (2021), which uses 10% nodes for training, 10% nodes for validation, and 80% nodes for testing. When training HGT (Hu et al., 2020b) models, we use Adam optimizer (Kingma & Ba, 2014). The maximum number of epochs is set 1000 and we apply an early stopping strategy with the patience of 200 epochs. We tune hyperparame- ters for training downstream GNN models and conduct grid search based on the validation sets. Specifically, we search for the optimal number of layers from {1, 2, 3) and the learning rate from 10.1,0.01, 0.001, 0.0 We set the the hidden dimension to 64 for all the models. In the ex- periments with HGNN-AC (Jin et al., 2021), we set a learning strategy and all the parameters of HGNN-AC models according to the official code for Jin et al. (2021).
B.4 LINK PREDICTION
For the link prediction splits, as described in Kipf & Welling (2016b), we divide target edges into training, validation, and testing sets, comprising 10%, 5%, and 85% of the edges, respectively. In our approach, negative sampling is performed to generate non-existent edges for training, validation, and testing in link prediction tasks. First, we create a mask that identifies all potential edges in the graph, excluding existing edges form pool of non-edges. From this pool, randomly sample negative edges, ensuring the number of negative samples matches the desired ratio for validation and testing. The remaining non-edges are used create a training mask for negative samples. For each dataset, we generate 10 edge splits. We utilize the Adam optimizer (Kingma & Ba, 2014) to train the HGT models with the hidden dimension of 64. Similar to HGT training in semi-supervised node classification, we tune the hyperparameters for training the downstream GNN models and perform a grid search based on the validation sets. Specifically, we search for the optimal number of layers from (1, 33 and the learning rate from (0.1. 0.01, 0.001, 0.0001), }. It is important to note that both imputation and the training of downstream GNNs are performed exclusively on training edges in each split, with validation and testing edges excluded.
For evaluation, we utilize AUC and AP, two metries widely used for link prediction tasks. The ROC AUC metric (denoted as AUC) evaluates the model's ability to distinguish between positive (true) links and negative (non-existent) links. It is computed by assessing the True Positive Rate (TPR) and False Positive Rate (FPR) at various thresholds of the predicted edge scores. These values are used to construct a Receiver Operating Characteristic (ROC) curve, which plots FPR on the x-axis and TPR on the y-axis. The Area Under the Curve (AUC) is then calculated, providing a single value that represents the overall performance of the model. The AP (Average Precision) metric emphasizes the precision-recall tradeoff, making it particularly valuable for imbalanced datasets. is calculated by measuring Precision and Recall values across different thresholds of the predicted edge scores. These values are used to create a Precision- Recall curve, and the AP score is derived as the weighted average of precision values at each level of recall. A higher AP score reflects better performance, especially in identifying true links among large number of negatives.
B.5 EXPERIMENTAL SETTING FOR THE PPI DATASET
In the protein-protee interaction networks (PPI) dataset (Zitnik & Leskovee, 2017), a node repre- sents a protein, and an edge represents an interaction between two proteins. Each node has 121 binary gene ontology (GO) terms, which describe biological information, such as biological path- ways, cellular components, and molecular functions. For consistency with our experimental setup, use the first GO term as the node label for prediction. The second GO term is used to determine the edge type. Edges connecting two nodes with the same second GO term are classified as type A, while edges connecting two nodes with different second GO terms are classified type B. We then utilize the remaining 119 GO terms as node features for proteins, and apply structural missing with different rates. We use 80% nodes for training. 10% nodes for validation, and 10% nodes for testing. We randomly create 10 different binary masks of a feature matrix for each r' and evaluate imputation methods across 10 runs using the generated masks. We consistently utilize GCN (Kipf & Welling, 2016a) models for downstream networks across imputation methods.
17

---

Published as a conference paper at ICLR 2025
B.6 HYPERPARAMETER DETAILS
Table 5:
(a and 3) of HetGFD used in experiments with I' = 0.995.
Missing type
Structural missing
Uniform missing
Task
GNN
Dataset
ACM
DBLP
IMDB
ACM
DBLP
IMDB
0.7
0.1
0.7
0.1
0.1
0.3
HGT
Semi-supervised
0.2
0.4
0.1
0.4
0.4
0.5
node classification
0.7
0.1
0.7
0.5
0.1
0.5
HGNN-AC
0.8
0.5
0.9
0.9
0.99
Link prediction
HGT
Q
0.
0.5
0.9
0.1
0.9
0.9
B
0.4
0.8
0.8
0.5
0.9
0.99
Table 6: Hyper-paran sypper-prrmmeters (a and () of HetGFD under structural-missing settings with HGNN-AC and I' E {0.9, 0.5}.
mm
Dataset
ACM
DBLP
IMDB
a 0.7
0.9
3
0.8
0.99
0.2
0.9
0.1
0.9
0.5
0.99
0.99
0.8
Table Hyper-parameters (a and 3) HetGFD on the PPI dataset.
I'
0.5
0.9
0.995
0.5
0.5
0.7
B
0.8
0.8
0.4
To find the optimal hyperparameters and 3 for HetGFD, we perform grid search validation sets. The search range is set to B)a, E (0,,0..,,0,,,3330..,) 0.3.0... E (0.99, 0.9, 0.8, 0.5, 0.4, 0.2, 0.1, 0.05) We set the value of K 100. We list the hyperparame- ters of HetGFD used for HetGFD in our paper in Table 5, Table 6, and Table 7.
C HYPERPARAMETER SENSITIVITY
0.9
82.64
0.7
83.91
84.37
85.16
83.59
83.01
82.76
82.53
82.49
a
0.5
83.36
83.98
84.04
83.94
83.82
82.94
83.27
0.3
83.61
84.03
84. 12
84.78
84.13
83.49
83.65
83.23
0.1
83.72
83.88
84.44
84.48
83.58
83.88
83.39
83.23
0.05
0.1
0.2
0.4
0.5
0.8
0.9
0.99
B
Figure 5: Average Macro-F1 (%) in semi-supervised node classification for different (a, 9) on ACM under a structural- setting with r. 0.995. HGT is commonly used as a downstream GNN. This heatmap shows the results the validation where we search a and
18

---

Published as a conference paper at ICLR 2025
0,9
84.09
84.15
84.38
84.51
84.00
84.05
83.98
83.89
0.7
84.87
85.28
85.87
85.14
84.67
84.40
84.58
84.19
a
0.5
84.36
84.86
85.45
84.85
84.71
84.26
84.70
84.67
0.3
84.13
84.35
85.07
85.07
84.94
84.56
84.32
84.24
0.1
84.02
84.39
84.54
84.49
84.49
84.56
84.71
84.62
0.05
0.1
0.2
0.4
0.5
0.8
0.9
0.99
B
Figure 6: Average Macro-F1 score (%) in semi-supervised node classification for different (a, B) ACM under a structural- setting with rm 0.995. HGT is commonly used as a downstream GNN. This heatmap shows the results the test set.
0.9
75.06
74.77
74.10
73.16
72.52
72.44
72.32
73.66
0.7
76.05
76.17
73.73
72.90
73.34
72.85
72.91
72.57
0.5
75.41
73.21
72.50
73.17
72.56
73.11
0.3
77.69
78.03
76.28
73.98
73.15
72.33
72.67
73.04
0.1
78.26
77.39
76.48
78.25
76.22
72.75
72.55
72.49
0.05
0.1
0.4
0.5
0.8
0.9
0.99
B
Figure 7: Average AUR ROC (%) in link prediction for different (a,, 3) on ACM under a structural- missing setting with I' 0.995. HGT is commonly used as downstream GNN. This heatmap shows the results on the test set.
We conduct experiments to investigate the effects of hyperparameters of HetGFD, a and / are hy- perparameters of HetGFD, where controls PC and determines the importance difference among edge types. Figure 5 shows the effects of the hyperparameters a and 8 of HctGFD when HGT is used downstream GNN. We determine optimal hyperparameters based on the validation sets.
We conduct additional experiments on test sets in both semi-supervin prediction. Figure 6 and Figure show the results on ACM under structural-missing settings with missing rate of I'm 99.5%. As shown in Figure 6, when the runner-up's Macro-Fi F1 score is 84.47%, most combinations Figure 7, when the runner-up's 's ROC AUC is 74.87%, many combinations achieve state-of-the-art performance, demonstrating the robustness of our HetGFD against a and B.
node classification and link
and 3 achieve state-of-the-art performance. Similarly, as shown in
We conduct further experiments analyzing the impact of the diffusion step K on performance. Ta- ble shows the performance HetGFD for different values of K, the number of diffusion steps. As shown in the table, while the performance of HetGFD with K E {10, 20) is slightly lower than others, the performance becomes stable after reaches 40. This is because imputed features ap- proach the same steady state with large enough K. In summary, K 40 shows the robustness in both semi-supervised node classification and link prediction.
D FURTHER EXPERIMENTS
D. ABLATION STUDY
We conduct extensive ablation study analyze the effectiveness of the components in HetGFD. The experiments for semi-supervised node classification are performed under uniform-mine misssig set- tings with F.. 0.995 and HGT is commonly used.
19

---

Published as a conference paper at ICLR 2025
Table 8: Performance of HetGFD for the different value of K, the number of diffusion steps. Semi-supervised node classification (Macro-F])
K
10
20
40
100 (used)
200
ACM
85.05 1.36
85.92 + 0.81
85.90 + 0.79
85.87
0.81
85.89 + 1.07
DBLP
90.68 = 0.93
90.84 + 0.81
90.88 + 0.80
90.88 + 0.79
90.88 + 0.79
IMDB
45.27 4.00
46.33 + 2.96
47.10 + 3.14
47.15 1.66
47.15 + 1.65
Link prediction (ROC AUC)
10
20
40
100 (used)
200
ACM
77.90 + 1.12
77.98
0.79
78.10 = 0.88
78.25 + 1.34
78.25 1.34
DBLP
11.800.55
91.88
0.44
91.98
0.50
91.94 + 0.67
91.97 + 0.52
IMDB 1.15
91.66 1.27
92.50 = 1.04
92.50 + 1.04
92.50 1.04
Table 9: Ablation study of HctGFD under uniform misiiomimmiiiigggggg settings with Tm 0.995. A denotes using random edge-type ranking.
Edge-type ranking
ACM
DBLP
IMDB
PC
Macro-F1
Micro-Fi
Macro-F1
Micro-FI
Macro-F1
Micro-Fi
84.07 + 1.38
84.66 1.38
89.47 + 1.76
90.26
1.76
45.57
4.00
48.26 1 2.03
85.19 + 1.04
85.45
+ 1.04
89.89 + 1.62
90.46 + 1.62
46.25 1:25::2:
48.66 + 1.57
X
86.26 0.69
86.61
+ 0.63
90.49 + 1.43
91.14
1.35
47.25 + 1.88
49.94 + 1.38
86.87 2.15
87.12
1.50
90.89
47.13 2.94
50.08
1.81
88. 0.69
88.14
0.66
90.65
1.53
91.40
1.24
48.57
1.41
50.57
1.66
Table 10: Performance comparison of HetGFD and its variant using direct edge-type-wis ho- mophily (H) instead the edge ranking based on H. terms of Macro-F1 score on semi-supervised node classification.
ACM
DBLP
IMDB
direct H HetGFD
83.55 t 1.40
89.25 t 1.65
42.93 : 5.95
85.87 + 0.81
90.88 = 0.79
47.15 + 1.66
PC and edge-type ranking. PC and edge-type ranking can be removed from HetGFD by substi- tuting 1 for a and 8. respectively. This substitution reduces HetGFD to FP, as it eliminates the mechanisms for controlling PC and distinguishing edge types. Additionally, HetGFD with random edge-type ranking is compared. The results of the ablation study are presented in Table 9. The re- sults show that the performance gain achieved by edge-type ranking is significantly greater when PC is used than when it is not. This suggests that both PC and edge-type ranking mechanisms, which are grounded the principle of feature homophily, work synergistically boost performance. The notable performance improvement over the variant of HetGFD with random edge-type ranking fur- ther validates the concept of edge-type-wiss homophily in determining edge-type ranking within our HetGFD framework.
Direct H ranking-based. We evaluate the performance HetGFD using direct values instead of the edge-type ranking approach. 3 (k-1) in Eq. (6) and gh-1 in Eq. (8) is where the edge- type ranking is utilized. B-(k-1) in Eq. (6) is designed reduce the importance (PC) of features connected through low-ranking edges for the relation-aware diffusion stage, and 3 in Eq. (8) is designed to make diffusion occur more through high-ranking edges for the relation-aware diffusion stage. We the direct edge-type-wiaz homophily H of each edge type instead of 3 (k-1) in Eq. (6) and @k-1 in Eq. (8). We replace 3- (k-1 in Eq. (6) with H-1 of each edge type and replace 36-1 in Eq. (8) with H to align with the design concept HetGFD. Table 10 shows the results. The results indicate that using direct 76 values results in lower performance across all datasets compared to when edge-type ranking is used. This suggests that transforming H into the ranking provides a more stable and effective way to leverage edge-type-wise homophily.
Random initialization vs zero initialization. We conduct additional experiments comparing the performance of HetGFD when zero initialization and random initialization used for virtual fea-
20

---

Published as a conference paper at ICLR 2025
Table 11:
Performance of HetGFD for different initialization strategies for missing features. K
denotes the number of diffusion steps.
Semi-supervised node classification (Macro-FI)
Initialization
ACM
DBLP
IMDB
random init (K = 100)
85.81 + 0.78
90.65 + 1.18
46.47 + 2.06
random init (K 1000)
85.85 = 0.80
90.90 = 0.80
47.11 + 1.58
zero init (used)
85.87 + 0.81
90.88 + 0.79
47.15 + 1.66
Link prediction (ROC AUC)
Initialization
ACM
DBLP
IMDB
random init (K 100)
77.57 + 1.91
91.64 + 0.77
92.50 + 1.04
random init (K 1000)
78.27 + 1.29
91.96 = 0.74
92.50 = 1.04
zero init (used)
78.25 + 1.34
91.94 + 0.67
92.50 + 1.04
ture generation. Table 11 shows the results. As shown in the table, zero initialization with K = 100 used this paper shows slightly better performance compared that of random initialization with K == 100, where K is the number of diffusion steps. However, when we increase K of HetGFD us- ing random initialization to 1000, the performance both becomes almost identical. This because random initialization requires larger value of K to reach steady state. Although updated features approach the same steady state with a large K regardless of the initialization based on the proof in Appendix A, careful consideration is needed when determining K, depending the initialization.
Table 12: Performance comparison of pre-imputed features obtained by preliminary diffusion and HetGFD's imputed matrix when fed to HGT.
Semi-supervised node classification (Macro-FI)
ACM
DBLP
IMDB
pre-imputed
83.40 1.16
88.92 + 1.82
45.02 + 4.65
HelGFD
85.87 + 0.81
90.88 + 0.79
47.15 + 1.66
Link prediction (ROC AUC)
ACM
DBLP
IMDB
pre-imputed
72.53 + 2.10
63.21 + 0.71
63.47 + 13.05
HetGFD
78.25 + 1.34
91.94 + 0.67
92.50 + 1.04
vs X'. To quantitatively assess the impact of our preliminary diffusion approach, we conduct additional experiments comparing the performance of semi-supervised node classification and link prediction tasks with pre-imputed features obtained via preliminary diffusion and HetGFD's imputed matrix. The results, presented in Table 12, show significant improvements when using HetGFD over pre-imputed features. Specifically, the Macro-Fl scores and ROC AUC metrics demonstrate that HetGFD consistently outperforms the preliminary diffusion approach across various datasets (ACM, DBLP, and IMDB). These results highlight the importance of edge-type-wise homophily and the resulting edge-type rankings.
Table 13: Performance comparison of HetGFD and its variant using uniform weights instead of |-,1-1 in Eq. (2), in terms of Macro-F1 score semi-supervised node classification. E, denotes set of r-type edges.
ACM
DBLP
IMDB
uniform weights
85.87
0.81
90.29
1.68
43.19 5.38
HetGFD
85.87
0.81
90.88 + 0.79
47.15 1.66
Uniform weights vs | in Eq. (2). We compare the performance HetGED using uniform weights against the proposed |&,| -1 weights in Eq. (2), where E, denotes the set of r-type edges.
21

---

Published as a conference paper at ICLR 2025
The results are shown in Table 13. While both variants perform equally well on ACM, HetGFD with the proposed weights achieved superior performance on DBLP and IMDB. This performance dif- ference stems from that uniform weights cause biased diffusion toward the majority edge type. For example, in DBLP, there are edge types of Paper-Author, Paper-Term, and Paper-Conference, with each edge type having 39,290, 171,620, and 28,656 edges, respectively. In this case, using uniform weights causes excessive diffusion through Tere edges, subsequently making the Paper-Term edge-type-wise homophily the highest. Since authors connected through Paper-Author edges may have more similar features than those connected through Paper- Term and Seper-Conference edges, using uniform weights leads performance degradation. In contrast, we confirm that the original HetGFD consistently ranks Paper-Author as the highest edge-type-wise homophily.
Table 14: Performance comparison of HetGFD by assigning different weights to W(dd) in Eq. (8), in terms of Macro-F1 score semi-supervised node classification.
Widdr Eq. (8)
ACM
DBLP
IMDB
83.06 +: 1.14
88.57 +: 2.83
43.84 i 3.98
SealEa go- Eya/End (HeIGED)
85.09 + 1.54
90.29 = 1.12
42.97 + 5.46
85.87 0.81
90.88 0.79
47.15 + 1.66
Ablation study in Eq. (8). We experiment with different weight assignments for W(dr)) in Eq. (8). In this equation, the term Lj,// strengthens the message passing from high-PC features to low-PC features. The results in Table 3 show that the combination of f and &, used in HetGFD consistently outperforms other weighting schemes. This highlights the effectiveness of our proposed weighting strategy.
Imputed features
Deep features
PCFI+VF
Class
Class
Class
HetGFD
(ours)
Figure 8: A t-SNE plot of imputed features and deep features learned with HGT.
D.2 QUALITATIVE RESULTS
We provide qualitative results by employing t-SNE (Van der Maaten & Hinton, 2008) to visualize imputed features and deep features HGT, obtained by HeiGFD. For comparison, also present visualizations of features obtained by PCFI+VF which is the most competitive method. Figure shows the qualitative results on ACM under structural-missing setting with rm 0.995. HetGFD provides much clearer cluster structures for both imputed features and deep features than PCFI+VF, indicating a more effective feature imputation.
D.3 ADDITIONAL COMPLEXITY ANALYSIS
The two main processes consider in the time complexity of HetGFD the two diffusion stages, the calculation tiiee homophily H. the calculation PC, The two diffusion stage have time complexity of O((El) since they implemented using the message passing operation in
22

---

Published as a conference paper at ICLR 2025
500
452.26
386.08
375
250
125
0.00107
0.00403
0.872
4.21
5.67
9.46
Zero
Mean
kNN
SVD
GAIN
FP+VF PCEI+ HetGFD
Figure 9: Imputation time (s) of methods ACM under a structural-missingg missing setting with T'm 0.995.
PyTorch Geometric (Fey & Lenssen, 2019). This operation involves aggregating information from neighboring nodes, which scales linearly with the number of edges in the graph. The calculation of H has time complexity of O(F (8]) since measures feature similarity across all edges. The calculation of PC has time complexity of O(N2). This is because the calculation of PC uses Dijkstra's algorithm, an algorithm for finding the shortest paths between nodes in a graph, for distance encoding. In structural-missing settings, the missing status of nodes is identical across all channels. Therefore, only a single transition matrix needs to be computed, requiring just one PC calculation. However, in uniform-missing settings, the missing status of nodes varies for each channel, necessitating different transition matrices for each of the F channels. Consequently, F PC calculations are required. Thus, HetGFD operates in structural-missing settings with time complexity of O(F |8| + N2) and in uniform-missing settings with a complexity of O(F .F... |E| + F-N²). However, it is important note that PCFI, the most competitive baseline, also involves the calculation of PC using Dijkstra's i algorithm, which has time complexity of ON?²). Compared to PCFI, our HetGFD consistently demonstrates superiority across all experimental settings.
For each imputation method, we measure the time for imputation. Figure 9 shows imputation time on a single split of ACM under structural-missing setting with I'm 0.995. While Zero and Mean show much shorter imputation time than the other methods, Zero and Mean suffer from significant performance degradation at high r'- Meanwhile, diffusion- HetGFD) show far less imputation time than SVD and GAIN. Although our method, HetGFD, necessitates more imputation time compared to other diffusion- based methods, results in notable performance improvements in two major graph learning tasks.
methods (FP+VF PCFI+VF, and
To validate the scalability of HetGFD, we conduct additional experiments on OGBN-Arxiv (Hu et al., 2020a), which consists of 169343 nodes, 1166243 edges, and 128-dim node features. The nodes represent papers published in 2017, 2018, and 2019. We divide edges into three types: 2017- 2018, 2018-2015 and 2017-2019. Under structural-misiie
setting with T'. observed that HetGFD require only 0.39 hours for imputation. This demonstrates the efficiency of HetGFD in terms of imputation time, even for graphs with large number of nodes.
D.4 COMPARISON WITH FEATURE DISTANCE-BAN BASEDD WEIGHTS
We conduct additional experiments to compare the weighted matrix (d) used in relation-aware diffuuion against feature distance-based weights. The purpose of Wil) is to assign greater weights edge types that significantly contribute to feature homophily, i.e., edge types that result in highly similar features between connected nodes. In contrast, the feature distance-based approach can be simpler method for calculating weights. To construct the feature distance- basedd propagation matrix, we follow these steps: First, pre-imputed feature matrix is generated using preliminary diffusion, as HetGFD. Then, a single feature mean vector computed for each node type based on the pre-imputed matrix. For each edge type, the feature distance is calculated by measuring the distance between the mean feature vectors the two node types connected by that edge type. For each edge type, the calculated distance is inverted and assigned to the edges belonging to that edge type. Finally, the resulting weighted matrix row-stochastically normalized to perform diffusion-baat based imputation.
Table 15 presents a performance comparison between the feature distance-based approach and our HetGFD. For this comparison, perform semi-supervised classification and link prediction tasks,
23

---

Published as a conference paper at ICLR 2025
Table 15: Performance comparison with HetGFD using feature distance-based weights.
Semi-supervised node classification (Structural missing)
ACM
DBLP
IMDB
Missing Type
Macro-F1
Micro-FI
Macro-F1
Micro-FI FL
Macro-FI
Micro-Fl
Distance-base based
83.30 = 1.45
83.94 # 1.52
88.48 2.30
89.37 = 2.07
43.23 3.83
47.27 - 1.96
HetGFD
85.87 0.81
86.10 = 0.81
90.88 0.79
91.53 0.79
47.15 1.06
49.46 = 1.66
Semi-supervised node classification (Uniform missing)
ACM
DBLP
IMDB
Missing Type
Macro-F1
Micro-FI
Macro-F1
Micro-FI
Macro-F1
Micro-F1
Distance-bused
83.97 1.63
84.70 = 1.35
85.28 7.31
87.25 = 3.95
43.50 2.90
47.39 1.22
HetGFD
88.14
88.14 + 0.66
90.65 1.53
91.40 1:24
48.57 1.41
50.57 1.66
Link prediction (Structural missing)
ACM
Missing Type
AUC
AP
AUC
AP
ALC
AP
Distance- based HetGFD
72.52 = 1.03
73.21 + 1.37
60.52 + 10.23
59.43 = 9.59
72.00 E 16.41
67.66 = 12.23
78.25 1.34
78.62 = 2.12
91.94 0.67
91.88 1 0.91
92.50
86.99 1.58
Link prediction (Uniform missing)
Missing Type
ACM
DBLP
IMDB
ALC
AUC
Distance-based
72.37 + 1.27
73.03 +
00.40 9.00
59.48 8.92
70.57 1 18.07
67.48 15.37
HetGFD
76.96 + 1.74
77.19 = 1.98
92.17 + 0.56
92.12 0.53
91.95 1.72
86.72
consistently utilizing HGT models as downstream GNNs. As shown in the table, HetGFD signif- icantly outperforms the feature distance-based approach across all settings. These results validate the effectiveness of designing the propagation matrix based on sagge-typ-wwae homophily H.
24

---

Published as a conference paper at ICLR 2025
D.5 STATISTICAL ANALYSIS
Table 16: p-values comparing our HetGFD the runner-up in each setting. art, not a runner-up.
denotes state-of-the-
For Table
GNN
Missing Type
Datasct
Metric
Runncr-up
Runner-up's
Ours
p-value
Macro-FI
PCFI+VE
84.47
1.22
85.87
0.81
5.98 x 10
ACM
Micro-F1
PCFI+VE
85.06 0.98
86.10
0.81
7.29 x 10
Structural
DBLP
Macro-Fi
PCFI+VE
90.41 1 1.23
90.88
0.79
2.23 x 10
Micro-F1
PCFI+VE
91.14 1.08
91.53
0.79
2.37 x 10
Macro-F1
PCFI+VI-
46.64 1 1.51
47.15
1.66
5.30 x 10
IMDB
HGT
Micro-F1
PCFL+VI
49.69 + 1.83"
49.46 + 1.66
7.58 x 10-1
Macro-F1
PCFI+VF
86.26 = 0.69
88.14 0.69
1.11 x 10
ACM
Micro-F1
PCFI+VF
86.61 + 0.63
88.14 = 0.66
1.84 x 10-3
Uniform
DBLP
Macro-F1
Mean
90.54 = 1.62
90.65 1.53
8.63 x 10
Micro-F1
Mean
91.32 + 1.62
91.40 1.24
9.27 x 10
Macro-F1
PCFI+VE
47.25 + 1.88
48.57 1.41
4.42 x 10
IMDB
Micro-FI
PCFI+VF
49.94 + 1.38
50.57 1.66
2.63 x 10-)
For Table 18
GNN
Missing Type
Dataset
Metric
Runner-up
Runner-up's
Ours
p-value
Macro-F1
PCFI+VF
69.25
4.32
76.23 2.84
10
ACM
Micro-F1
VC
75.07 = 4.32
76.91 2.84
1.21 10
Structural
DBLP
Macro-Fi
VI
93.02 - 0.49
93.26 0.40
2.49 10
Micro-F1
VC
93.49 + 0.49
93.76 + 0.440
1.59 x 10
Macro-FI
VF
31.29 = 3.46
35.05 1.84
5,98 x 10
IMDB
HGNN-AC
Micro-FI
VF
42.99 = 3.46
43.64 1.84
5.62 x 10-1
Macro-F1
VC
84.04 1: 2,08
85.27 1 1.61
7.72 x 10
ACM
Micro-FI
VC
84.92 + 3.26
85.64 + 1.61
4.79 x 10
Uniform
DBLP
Macro-Fl
VF
93.77 = 0.44
94.03 = 0.29
1.63 x 10
Micro-FI
PC
94.21 1: 0.44
94.45 1 0.29
1.26 x 10
Macro-FI
VC
41.06
= 3.87
43.52
2.66
8.30 x 10
IMDB
Micro-FI
VE
47.20 = 3.87
47.87 2.66
4.30 x 10-1
For Table
Missing Type
Dataset
Metric
Runner-up
Runner-up's
Ours
p-value
AUC
GRAFENNE
74.87 + 6.71
78.25 1.34
1.58 x 10-1
ACM
AP
FP+VF
74.03 + 0.84
78.62 + 2.12
2,65 x 10-4
Structural
DBLP
AUC
GRAFENNE
90.14 1: 7.26
91.94
0.67
4.50 10-1
AP
GRAFENNE
76.53 7.12
0.91 91.88
1.08 10-4
AUC
FP4VF
92.50 + 1.04
92.50
1.04
IMDB
AP
FP+VF
86.99 + 1.58
86.99
1.58
1
AUC
PCFI+VF
74.94 1.37
76.96
1.74
1.60 x 10-2
ACM
AP
PCFI+VF
73.80
77.19
1.98
7,98 10-3
Uniform
DBLP
AUC
GAIN
T2.48
92.17
0.56
4.57 x 10-15
AP
GAIN
74.20 1 0.60
92,12 0.53
5.39 x 10 13
AUC
GAIN
92.50
1.04
91.95 + 1.72
4.98 x 10-1
IMDB
AP
GAIN
86.99
1.58
86.72 + +.400
8.47 10
For Table 3
I'
Runner-up
Runner-up's
Ours
p-value
0.5
PCFI+VF
80.75 + 1.68
81.57 + 1.04
2.53 x 10 10-1
0.9
PCFI+VF
65.22 + 2.19
66.84 + 1.92
7.68
10-2
0.995
GRAFENNE
62.26 + 0.00
63.20 + 0.37
3.25 x 10-5
We conduct additional experiments to evaluate the statistical significance our HetGFD's superior performance. Table 16 shows p-values comparing EDBD to the runner-up in each setting for all the results in Table 1, Table 18, Table 2, and Table 3. As shown in the table, the p-values for Table 1, Ta- ble 18, Table 2, and Table 3 exhibit wide range of distributions. Nevertheless. while the runner-ups vary depending on the setting, HetGFD consistently achieves ofate-of-the-art performance, except for link prediction DBLP under the ciiformmmiisiine setting.
25

---

Published as a conference paper at ICLR 2025
Table 17: Normalized Dirichlet energy for each metapath.
Dataset
Edge Type
Normalized Dirichlet energy
Puper-Author-Pedt Papeer
0.105
ACM
Paper-Subjects Subject-Paper
0.149
Paper-Author- Paper
0,159
DBLP
Paper-Term-Paape
0.183
Paper-Confereecc-PPae Paper
0.203
Movie-Director-Movii
0.125
IMDB
Movie-Actor-Movie
0.203
E DISCUSSION ON FEATURE HOMOPHILY
In the context of homophily, two types are commonly discussed: class homophily and feature homophily. Diffusion-based imputation methods rely on feature homophily. However, in hetero- geneous graphs, some node types often lack features, making it very challenging to assess the overall level of feature homophily such graphs (i.e., whether the graph feature-homophilic hetttooiieeetrohiici)))... Nevertheless, if one wishes to measure feature
or non-feature feature- homophily, it can be done using metapaths (e.g., Movie-Director-Mon that connect node types with features. Each metapath exhibits distinct level of feature homophily within heterogeneous graph. For example, some metapaths, such as Movie-Director-Monn Movie, display low feature homophily.
or Alvie-AAtor-Movv
ex-
hibit high feature homophily, while others, like
Table 17 presents the normalized Dirichlet energy (lower values indicate higher feature homophily), representing the feature homophily levels for each metapath in the datasets used in this paper. As shown in the table, all datasets contain metapaths with varying levels of feature homophily. We emphasize that, while it is very challenging determine whether heterogeneous graph is feature- homophilic or feature- naaturehhetrrphhliee diverse levels of feature homophily exist within the graph de- pending the metapaths. Through the extensive experiments, confirm that our HetGFD effec- tively prevents performance degradation on downstream tasks under various missing data scenarios across these datasets as well as the PPI dataset. However, the effectiveness of HetGFD may be lim- ited on feature-ha ceatture-heeroohhile heterogencous graphs, where most paths connecting attributed nodes are heterophilic connections.
26

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTAL RESULTS
Table 18: Semi-supervised node classification results (%) with Im 0.995.
GNN
Missing
Method
Macro F1
ACM
Micro Ell
Macro E1l
DBLP
Macro Fi
Macro-F
IMDB
Micro ETl
Full festunes
80.00 + 2.38
1.05
48 + 0:55
63.05 +:
55.05 +: 5.07
56.67
1,70
Zero
42.14 1:122
58.01
6.12
4.07
28.81 4.97
19.34 1: 0.44
36.26 0.94
Stuctural
missing
ANN
41.50
(ours)
Zeno
21.00::0000
27:76
19.63
Mean
21.86:00.00
48.70 11.04
11:28 1.78
27.02
20.00 1.55
26:42 1.58
missing
Unionm
SVD
KNN
GAIN
55.28 1. 10.33
61.63
21,85 0.00
65 40 10.33
68-11 6.822
48.74 01000
11.72
11.40 0.63
11.38 0.57
+ 0.75
27.54
28.18
27.51
1.73
20.55
19.86 + 0.77
19.65 1: 0.71
36.45
96.84
96.86
1: 0.7.1
1.775
1.224
GRAFENNE
73.04 1:34
74:20
1.05
17.8 2.24
28.61 + 0.01
36.51 + 1.58
39.80
1.00
1P:VE
51.27 2:21
S1114 2.01
11:30 1:200
28.21 1: 2:40
20.01 1: 1:57
04.24
1.07
PCEL+VE
54.04 + 2.08
S4 022 = 5.25
MS.77 + 0.44
94.21 + 0.44
41.00 5.67
47.30
3.87
HetGFD (ours)
80.27
1.61
8G 1.61
94.00 0.29
94.45 = 0.29
48.52
2 00
47.87 2.06
27


Reviews:
[{"review_id": "7BwZy6LIDG", "reviewer": "Reviewer_wM4n", "summary": "Authors provide the framework that can diffuse missing feature values in the heterogeneous graphs. Authors divide nodes into 3 groups for each feature channel -- nodes with known features, nodes with unknown features, and non-attributed nodes (virtual features) -- and then define the diffusion across those groups along with graph links. In this diffusion process, authors introduce 3 kinds of weights: (1) normalization by the frequency of links, (2) edge-type aware weights based on edge-type homophily, and (3) pseudo-confidence aware weights. After multiple steps of diffusion, the diffused features for attributable nodes are obtained by removing the virtual features of the non-attributed nodes.\n\nAuthors conduct experiments for semi-supervised node classification as well as link prediction tasks by applying the diffused features into a common GNN algorithm. From the empirical experimental results, authors provide the superior performance from the proposed method as opposed to the baselines.", "questions": "- In Eq (5), how can the homophily be defined when the edge type r connects two different types of nodes? For instance, if r connects actor and movie type, then actor node is the non-attributable node for the move type feature. How can we define the similarity here?\n\n- For the link prediction task, applying the diffusion process should be careful since using the links in the test split for the diffusion path is information leakage. Despite this demand for carefulness, it is not addressed in the paper. If authors have not done this way, experiments should be performed in this way. If authors already performed this way, the procedure should be clearly addressed.\n\n- It would be great to see the ablation study such as the impact of convergence (i.e. k steps in diffusion), the importance of edge type ranking , and so on.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea of virtual features to allow the diffusion over heterogeneous graphs is novel and worth studying.\n- Authors show the superior performance of the proposed algorithm for structural as well as random missing features. And its gain increases as the missing rate increases.\n- The proposed algorithm is straightforward.", "weaknesses": "- There is almost no learning process and the proposed method is closer to the well-designed preprocessing process. Some model learning from data would fit better to the venue.\n- There are crucial hyperparameters, but setting them up is decoupled from the task learning. Sensitivity analysis and the proposal for tuning them would be great to have.\n- Homophily is assumed for the proposed diffusion process, while the underlying GNN could capture more general interactions. It would be great to have experiments on the non-homophily dataset.", "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": "Az23vH77pS", "reviewer": "Reviewer_56Ce", "summary": "The paper proposes a novel imputation method named HetGFD. It is designed for heterogeneous graphs with partially observed features. By utilizing a virtual feature mechanism and introducing edge-type-wise homophily, HetGFD enables feature diffusion across different node types and edge connections. The method shows improvements in semi-supervised node classification and link prediction tasks, even under high missing feature rates.", "questions": "Q1. Can the authors provide additional experimental results to show that the proposed method outperforms k-NN? The ablation study suggests similar performance, which raises concerns about its novelty.\n\nQ2. The fine-grained similarity calculation method raises questions. Additional discussions and experimental validations regarding the algorithm's efficiency and scalability would be beneficial. Could the authors also demonstrate the effectiveness of a coarser propagation weight calculation method? For instance, using the difference between the feature means of the specific set of attribute nodes and the overall feature means of all attribute nodes could provide a simpler and more efficient approach. Additionally, Section D3 does not fully outline the model's complexity, particularly regarding similarity and shortest path computations.\n\nQ3. Could the authors provide further motivation or theoretical guarantees, such as lower-bound proofs, to validate the similarity calculation strategy for incomplete features? Additionally, using attention mechanisms or learnable weight matrices for dynamic adjustment of propagation weights for the specific downstream task may be a more effective approach. The authors can further discuss the motivation behind their strategy.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. HetGFD introduces virtual features for nodes with missing attributes. This approach effectively bridges gaps in the feature set, enhancing the model's robustness.\n\nS2. The integration of edge-type-wise homophily allows for a flexible adjustment of edge weights during feature propagation. It improves the quality of the imputed features.\n\nS3. The paper demonstrates the effectiveness of HetGFD through experiments on multiple benchmark datasets. The results show that HetGFD outperforms traditional imputation methods, highlighting its practical applicability in real-world scenarios.", "weaknesses": "W1. The novelty of this paper is limited. The main innovation lies in assigning different propagation weights based on node similarity, which is similar to the k-NN imputation method.\n\nW2. Calculating edge-type weights requires complete pairwise feature distance calculations among all attributed nodes, leading to high computational costs that could limit scalability.\n\nW3. Using incomplete features for similarity calculations makes the results less reliable.", "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": "KQKWooe6WA", "reviewer": "Reviewer_QsiT", "summary": "This paper proposes a method for feature imputation in heterogeneous graphs. It is assumed that only some types of nodes may have a certain feature and for some of them the feature value is not given and has to be imputed. The idea is the following. First, virtual features are assigned to nodes for which a particular feature is undefined. Then, preliminary propagation is used to get initial assignments for all the nodes. Using these assignments, homophily of different edge types is defined. Then, these homophily values are used to re-weight the edges for the final propagation of features. In the experiments, it is shown that the proposed approach outperforms the baselines for different missing feature rates.", "questions": "Q1. I could not find in the text the details on how the models are evaluated for link prediction (dataset splits, negative sampling, details for metric computation, etc.) Could you please provide the details or point to a particular part of the text?\n\nQ2. Regarding the theoretical analysis in Appendix A, it is written in line 725 \"Here, we prove the case when non-attributed nodes participate in feature diffusion with virtual features.\" Do virtual features bring additional challenges to the proof? It seems that you treat nodes with missing features and with no features exactly the same (in line 735), so it reduces to the standard scenario.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The paper is in general well-written and easy to follow;\n- The proposed approach, while being relatively simple, shows good results in the experiments;\n- The authors conduct extensive ablation studies to demonstrate that different components of their solution are important.", "weaknesses": "- It seems that there are two assumptions needed for the approach to work: 1) the graph should be homophilic (nodes with small graph distances between them have similar features) so that feature propagation works, and 2) features are of the same nature/scale so that equation (5) is meaningful. These limitations should be discussed.\n- Some of the components of the proposed solution are designed based on some intuition, but particular formulas are not well motivated (e.g., by models or theoretical analysis). Examples include a particular weighting of the edge types in eq. (2), ranking edge types according to homophily and eq. (6), and equation (8). I acknowledge the ablation studies in Appendix, but still many potential solutions could be used and it would be insightful to understand why a particular form is chosen.\n- One of the baselines (PCFI+VF) shows comparable performance in most cases, I think it would be useful to discuss this method and compare its advantages and disadvantages to the proposed solution in more detail.\n- While the theoretical result in Appendix A seems relatively straightforward and following from existing results (see the question below), its importance is repeatedly mentioned many times in the text (e.g., lines 78, 125, 206, 247).\n- Code for reproducing the results is not provided (if I am not mistaken).\n\nMinor: the first parts of the paper assume that only nodes of a certain type have features. The fact that it is possible to apply the method in a general setup is discussed in L360-362. I advise moving this explanation to earlier in the text.\n\nTypos:\n- L143: \\citet should be \\cite\n- L220: one of V_k^d should be V_u^d\n- L376: \"we apply missing to a feature matrix\"\n- L1102: \"highest.Since\"", "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": "LWMiF7fkNe", "reviewer": "Reviewer_P2Yo", "summary": "The paper proposes a new diffusion-based imputation method for heterogeneous graphs to improve classification. The method is applied to each dimension. Given a dimension d, it starts by creating a transition Matrix \\tilde{M}^(d), where the rows corresponding to the known attributes are set to 1 in the main diagonal (no transition) and the other rows correspond to the probability of going from one node to another. This probability is proportional to the number of edges existing per type of edge. Once the method converges it generates the pre-imputed matrix which is used to compute the Edge-type-wise homophily ranking.\n\nThe Edge-type-wise homophily ranking corresponds to ranking from 1 to r where a value of 1 corresponds to the edge type with the highest homophily. The highest homophily corresponds to the average cosine similarity among nodes of each type of edge standardized by the expected similarity (\"calculated from randomly sampled node pairs\"). This ranking is used to generate a weight adjacency matrix given by equation 6 (high homophily implies lower weights), which is later used to estimate the pseudo-confidence of a node. \n\nThe pseudo-confidence of a node is given by $\\alpha \\times$ the shortest path of the node with respect to a node with a known attribute. So, a high pseudo-confidence implies that the node is closer and its value can be trusted. The pseudo-confidence is again used to estimate a new transition matrix to generate the final values in a new iterative process. \n\nIn summary, the first transition matrix determines \"the importance of nodes based on their similarity/homophily\" and the second transition matrix generates the final attributes based on the imputed importance of the nodes. Then, the imputed features are used for prediction.", "questions": "Could you give more details about the time complexity analysis?\nIs the size of the network from Table 4 the main connected component?\nWhat is the behavior when you include \\alpha and \\beta equal to 1?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The abstract and the introduction define the problem correctly. Even though it seems that the problem will be feature imputation, the problem is clearly defined as the generation of imputed features to improve classification rather than generating unobserved features. \n\nThe method converges thanks to the absorbing state defined by the known nodes. The convergence is also demonstrated in the appendix, but it should be easier to connect it to Markov random models. \n\nThe main contribution of the paper seems to be the inclusion of heterogeneous matrices, which are considered through the summation of the different dimensions.", "weaknesses": "The clarity of the paper is very low. The main idea of the paper can be explained with simple words and the process simplified. For some reason, the authors prefer to use a mathematical explanation instead of a simple algorithm or explanation. Most equations are left for the readers to understand, instead of explaining their meaning and their use in the next steps of the paper. These reduce the readability of the paper. Moreover, the idea of the transition matrix is quite similar to Um et al 2023. So, the paper could be rewritten based on the Um idea, and explaining that the main contribution is the \"summation\" of the matrices, leaving some technical details to the appendix or the Um paper.\n\nThe quality of the paper can also be improved. Besides the complex readability, the authors should try to explain why this method actually works. The paper should state the main difference in comparison to the PCFI method (UM paper). Moreover, the main paper lacks several components, including time complexity, experiment details, and hyperparameter analysis. Even though these parts are included in the Appendix, we are not required to read it for the evaluation of the paper. \n\nRegarding the time complexity, the method is impossible to apply to a large network. As expected, the time complexity is proportional to |V|^2. \n\nBased on the final results, it seems that the differences are not statistically significant. This reduces the significance of this method in comparison to PCFI. Even though the hyperparameters analysis is given in the appendix, the main paper does not discuss their values or their influence on the model. Moreover, no training process is given for these values (\\alpha and \\beta). \n\nIn summary, the paper is complex to read, the most important discussion and experiment details are left in the appendix, and it has a large time complexity.", "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)