Relation-Aware Diffusion for Heterogeneous Graphs with Partially Observed Features

Authors: Daeho Um, Yoonji Lee, Jiwoong Park, Seulki Park, Yuneil Yeo, Seong Jin Ahn
Primary area: learning on graphs and other geometries & topologies
Keywords: missing features, imputation, heterogeneous graph

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.

Decision: accept (poster)
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729776820105

thread_type:
official_review

<thread_object>
creator: reviewer_p2yo

<content>
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.

The 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. 

The 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. 

In 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.

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. 

The 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. 

The 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.

The 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. 

Regarding the time complexity, the method is impossible to apply to a large network. As expected, the time complexity is proportional to |V|^2. 

Based 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). 

In 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.

questions:
Could you give more details about the time complexity analysis?
Is the size of the network from Table 4 the main connected component?
What is the behavior when you include \alpha and \beta equal to 1?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730537401791

thread_type:
official_review

<thread_object>
creator: reviewer_qsit

<content>
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.

strengths:
- The paper is in general well-written and easy to follow;
- The proposed approach, while being relatively simple, shows good results in the experiments;
- 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.
- 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.
- 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.
- 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).
- Code for reproducing the results is not provided (if I am not mistaken).

Minor: 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.

Typos:
- L143: \citet should be \cite
- L220: one of V_k^d should be V_u^d
- L376: "we apply missing to a feature matrix"
- L1102: "highest.Since"

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?

Q2. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730618189766

thread_type:
official_review

<thread_object>
creator: reviewer_56ce

<content>
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.

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.

S2. 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.

S3. 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.

W2. Calculating edge-type weights requires complete pairwise feature distance calculations among all attributed nodes, leading to high computational costs that could limit scalability.

W3. Using incomplete features for similarity calculations makes the results less reliable.

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.

Q2. 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.

Q3. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730793303417

thread_type:
official_review

<thread_object>
creator: reviewer_wm4n

<content>
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.

Authors 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.

strengths:
- The idea of virtual features to allow the diffusion over heterogeneous graphs is novel and worth studying.
- 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.
- 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.
- 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.
- 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.

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?

- 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.

- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732482206432

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
This paper proposes Heterogeneous Graph Feature Diffusion (HetGFD), a novel imputation scheme that enables diffusion-based imputation in heterogeneous graphs. HetGFD tackles the significant challenges of applying diffusion-based imputation to heterogeneous graphs, achieving outstanding performance in semi-supervised node classification and link prediction across various feature-missing settings.

**We express our profound gratitude to all reviewers for dedicating their time and effort to thoroughly evaluate our manuscript. The constructive feedback provided by the reviewers has greatly enhanced the quality of our paper**. To address the reviewers’ concerns, **we provide point-by-point responses to all the questions and concerns raised by the reviewers**. Below is a summary of the key updates made to our paper:
* Reorganization of the Proposed Method Section (in Sec. 4)
* The Inclusion of kNN Imputation as a Baseline (in Sec. 5)
* Statistical Analysis (in Appendix D.5)
* Discussion on Feature Homophily (in Appendix. E)
* Complexity Analysis (in Sec. 6)
* Additional Complexity Analysis (in Appendix D.3)
* Limitations (in Sec. 7)
* Experimental Details for Link Prediction (in Appendix B.4)
* Hyperparameter Search Range (in lines 943-945 of Appendix. B.6)
* Comparison with Feature Distance-Based Weights (in Appendix. C.11)
* Code: https://anonymous.4open.science/r/ICLR_6591_code-AA8A/

**For the revised and updated parts in the manuscript, we have marked the changes in blue**. We hope that the responses provided below address all the reviewers’ concerns, and **please let us know if the raised concerns are addressed**. We are happy to answer further questions and would be delighted to provide additional clarifications.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733268428070

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final Summary

comment:
Dear Senior Area Chairs, Area Chairs, and Reviewers,

We would like to express our gratitude to both the chairs and the reviewers for their hard work. During the discussion period, the reviewers provided thorough and professional feedback, enabling us to significantly enhance the quality of the paper by addressing all their concerns and incorporating their suggestions. **Except for Reviewer wM4n, all reviewers have expressed opinions supportive of acceptance**.

**Despite our repeated attempts to seek confirmation from Reviewer wM4n, we have not yet received any response over the past two weeks**. To facilitate the discussions among the chairs and reviewers, we would like to summarize (1) the contributions of our work and (2) our rebuttal addressing all of Reviewer wM4n's concerns as a final note. We hope these points will be taken into consideration when the final decision is made.
***
## **Contributions**
1. To the best of our knowledge, this work is **the first attempt to utilize diffusion-based imputation on heterogeneous graphs**.
2. We address significant challenges in heterogeneous graphs to enable feature diffusion: \
2-1) Non-attributed nodes $\rightarrow$ **Virtual feature generation**\
2-2) Various edge types $\rightarrow$ A new measure termed **edge-type homophily, enabling relation-aware distance encoding**
3. Across various missing rates, including **99.5\%**, our HetGFD demonstrates **superiority on various datasets in both semi-supervised node classification and link prediction tasks**.
***
## **Reviewer wM4n's Concerns**
**The absence of a hyperparameter sensitivity analysis**
* We clarified that the original manuscript **already included** an analysis of hyperparameter sensitivity in Appendix C.

**The absence of an ablation study**
* We clarified that the original manuscript **already included** a comprehensive ablation study in Appendix D.1.

**How can we define the similarity using incomplete features?**

  * We clarified that **we do not define similarity using incomplete features**.

**Non-learning-based approach**
  * We clarified that the reason we chose a non-learning-based approach was **to design an imputation method that can be applied to various GNNs for both semi-supervised node classification and link prediction**.

**Link prediction setting**
* We clarified that **we strictly adhered to standard experimental settings for link prediction**.

**Feature homophily**
  * We conducted an **in-depth discussion on feature homophily in heterogeneous graphs** in Appendix E of the revised manuscript.

***
**We have thoroughly addressed Reviewer wM4n's concerns, but we have not received any response**. We strongly believe that the ICLR Senior Area Chairs, Area Chairs, and other reviewers will agree with our perspective upon reviewing our rebuttal to Reviewer wM4n. **We hope that Reviewer wM4n will take the time to review our rebuttal even after the discussion period has concluded**. While we respect Reviewer wM4n's evaluation, we trust that our rebuttal to Reviewer wM4n and the lack of confirmation from Reviewer wM4n will be carefully considered in the final decision-making process.
 
Once again, we extend our sincerest thanks to all the chairs and reviewers for their efforts.

Sincerely,\
The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a novel method to handle missing data in heterogeneous graphs, where nodes and edges can have different types. By introducing virtual features for undefined nodes and prioritizing edge types during diffusion, the method achieves significant performance improvements in tasks like node classification and link prediction.

All reviewer's concerns have been addressed except of reviewer wM4n who was unresponsive throughout the rebuttal period. 
I suggested for acceptance of the paper.