DREAM: Dual Structured Exploration with Mixup for Open-set Graph Domain Adaption

We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.

Q1: While the DREAM model shows promise in the explored environments, the paper could benefit from a deeper discussion on its generality across diverse environments. Actionable Insight: Test the DREAM model in a broader set of RL environments, particularly those that have different dynamics or complexities than the ones currently evaluated. This would provide a more comprehensive understanding of where the model excels and where it might face challenges.

A1: Thanks for your question. Firstly, we add a more complicated scenario with diverse environments. In particular, we have four different target domains and one source domain for each dataset. The performance comparison of different methods is shown as follows. From the results, we can conclude that our method has better generalization capacity compared with baselines. Secondly, thank you for bringing RL into our attention. In future works, we would extend the DREAM model to a broader set of RL environments with dynamic graphs.

We have also added your suggestion about future works into our revised version.

Q2: How does the DREAM model scale with increasing complexity of the RL environment, especially in terms of computational resources and time? Does the "dream" mechanism become more resource-intensive in more complex scenarios?

A2: Thanks for your question. We have analyzed the computational complexity of our method. The computational complexity primarily relies on two different branches for graph representations. Given a graph $G$, $||A||_0$ denotes the number of nonzeros in the adjacency matrix, $d$ denotes the feature dimension, $L$ denotes the number of layers, $T$ denotes the number of views, $R$ denotes the number of clusters. The graph-level representation learning branch takes $O(L||A||_0d+L|V|d^2+Td|V|+Td^2)$. The subgraph-view representation learning branch takes $O(L||A||_0d+L|V|d^2+R^2d)$. In our case, $R^2\ll||A||_0$, $T\ll d$ and $T\ll|V|$. Therefore, the complexity of the proposed DREAM and GraphCL are both $O(L||A||_0d+L|V|d^2)$ for each graph sample, which is linearly related to $||A||_0$ and $|V|$. We would further explore the complexity of our method in more complicated scenarios such as graph-based reinforcement learning in our future works.

We have also added your suggestion about future works into our revised version. Thanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.

We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.

Q1: The contribution of the article is not clear. While the author elaborates on their method in detail, it is not evident how this work contributes in comparison to others.

A1: Thanks for your comment. The contribution of this paper is summarized as follows:

• New Problem We introduce a novel problem of open-set graph domain adaptation, which accommodates unlabeled in-the-wild target graphs from unseen classes.

• Two branches to learn graph semantics in a complementary way. Our graph-level representation branch employs the message passing and attention mechanism to explore topological knowledge while our subgraph-view branch focuses on key local functional parts using graph clustering and constructs a hierarchical GNN architecture.

• EM-style interaction between two branches. We combine the advantages of two branches by posterior regularization to enhance the consistency between the predictions from the two branches.

• Well-designed Mixup for domain alignment and open-set classification. We not only utilize linear interpolation to generate virtual novel samples in the hidden space, but also combine multiple cross-domain neighboring samples to generate virtual samples for domain alignment.

• Extensive Experiments. Extensive performance comparisons to competing methods and ablation studies validate the superiority of our proposed DREAM over state-of-the-art methods.

Q2: Should 'v' in Equation (1) be adjusted or corrected to 'h'? In Equation (4), 'g' and 'h' represent different entities but appear in the same position as 'p_\theta(y| )'. Equation (11) seems unrelated to the subsequent formulas, and it maybe appear unnecessary.

A2: Thanks for your comment. We have corrected typos as below.

• As for Equation (1): We have modified it to $h_i^{(l)}=COMBINE^{(l)}(h_i^{(l-1)},n_i^{(l)})$;
• As for Equation (4): We have modified it into $L_s=-E_{(G,y) \in D^s}[log p_\theta (y|G)]-E_{(\bar{h},y) \in D^v} [log \phi_\theta^g (\bar{h})[C+1]]$.
• As for Equation (11): $A_{ij}$ appears in Equation (12) to guide the generation of virtual samples.

Q3: The paper does not compare with methods of graph domain adaptation or methods for open-set graph classification. It is insufficient to only compare with graph classification and open-set classification algorithms.

A3: Thanks for your comment. We have added two graph domain adaptation methods: DEAL [1] and CoCo [2], and three open-set methods: RIGNN [3], OpenWGL [4], and OpenWRF [5] for comparison. The results are shown as below. From the results, we can validate the superiority of the proposed DREAM.

In light of these responses, we hope we have addressed your concerns, and hope you will consider raising your score. If there are any additional notable points of concern that we have not yet addressed, please do not hesitate to share them, and we will promptly attend to those points.

Reference

[1] Hoffmann M, Galke L, Scherp A. Open-World Lifelong Graph Learning. IJCNN 2023.

[2] Yin N, Shen L, Li B, Wang M, Luo X, Chen C, Luo Z, Hua XS.. DEAL: An Unsupervised Domain Adaptive Framework for Graph-level Classification. ACM MM 2022.

[3] Yin N, Shen L, Wang M, Lan L, Ma Z, Chen C, Hua XS, Luo X. CoCo: Let Weisfeiler-Lehman Kernel Improve Unsupervised Domain Adaptive Graph Classification. ICML 2023.

[4] Luo X, Zhao Y, Mao Z, Qin Y, Ju W, Zhang M, Sun Y. RIGNN: A Rationale Perspective for Semi-supervised Open-world Graph Classification. TMLR 2023.

[5] Wu M, Pan S, Zhu X. Openwgl: Open-world graph learning. ICDM 2020.

Dear reviewers,

We sincerely appreciate your valuable feedback.

As the deadline for the author-reviewer discussion phase is approaching, we would like to check if you have any other remaining concerns about our paper. If our responses have adequately addressed your concerns, we kindly hope that you can consider increasing the score.

We sincerely thank you for your dedication and effort in evaluating our submission. Please do not hesitate to let us know if you need any clarification or have additional suggestions.

Best Regards,

Authors.

Dear Reviewer,

Thank you for your invaluable feedback. As the deadline for the author-reviewer discussion phase is approaching, we hope to make sure that our response sufficiently addressed your concerns regarding the contribution, as well as the revised version of our paper. We hope this could align with your expectations and positively influence the score. Please do not hesitate to let us know if you need any clarification or have additional suggestions.

Best Regards,

Authors

We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.

Q1: Novelty overclaimed and related works not well addressed. The authors claim that "we are the first to study open-set graph domain adaptation". However, the problem studied is no difference with the existing open-world graph classification, such as [1], where the task is to classify each unlabeled graph example into either one of the known classes or a corresponding novel class. Moreover, it also closely resembles the open-world graph learning works like [2,3], where the learning goal is to classify nodes belonging to seen classes into correct groups, but also classify nodes not belonging to existing classes to an unseen class. The paper lacks a thorough review of related literature. In addition to open-world graph works, fields such as (graph) OOD detection is also closely related and should be discussed in the related works.

A1: Thanks for your comment. Compared with open-world graph classification [1], our problem also considers potential distribution shifts across labeled and unlabeled data. Out-of-distribution unlabeled data [4] is always ubiquitous in practical graph learning and our problem aims to align the representations of source and target data besides OOD detection. Compared with node-level open-world graph learning [3,4] which studies a single graph with extensive nodes, our problem involves a large number of graphs and graph-level labels. We have included the discussion of open-set graph domain adaptation, node-level open-world graph learning and graph OOD detection into our related works as follows:

"Recently, graph neural networks have also been studied in different OOD settings. Semi-supervised open-world graph classification involves partial unlabeled graphs belonging to unknown classes [1]. Graph OOD detection aims to detect OOD graph samples without using ground-truth labels [2]. Node-level open-world graph learning aims to find OOD nodes on a single graph [3,5]. Compared with these problem settings, we not only detect OOD graph samples, but also overcome distribution shifts across source and target domains."

Q2: Following the above point, the experiments should include open-world graph learning related baselines. Currently only general graph classification methods are compared.

A2: Thanks for your question. We adapt more open-world graph learning methods, i.e., RIGNN [1], OpenWGL [3] and OpenWRF [5] in our setting for comparison. The results are shown as below. We can observe that our proposed DREAM surpasses the performance of baseline models, highlighting the superiority of the proposed method.

Q3: The method design includes a lot of modules but lack support and motivations. Why is the attention mechanism necessary for aggregation? Why can the graph-of-graph design generate plausible cross-domain virtual features? For the objective why are L_s, L_T, L_DA added without weights? The overall method seems complex and ferruginous and unclear why it works.

A3: Thanks for your question. We will explain the motivations of the modules in detail:

• The Attention Mechanism: We have added a model variant (DREAM w/o A), which replaces the attention mechanism with the global pooling. The compared results are shown below. From the results, we can observe that our full model outperforms DREAM w/o A. The reason is that a global pooling operator cannot capture the task relevance of nodes and structural dependencies while our attention mechanism can generate super-nodes for semantic exploration.

• Graph-of-Graph: Our graph-of-graph connects graph samples to identify similar cross-domain graphs for each graph. Then mixing these similar graphs in the embedding space would also generate virtual representations with similar semantics and encourage the consistency between original samples and their cross-domain virtual representations would thus enhance the domain alignment. In addition, we have included a model variant (DREAM w/o MM), which removes the graph-of-graphs for domain alignment and the following Mixup. The compared results are shown below. From the results, we can observe that DREAM w/o MM performs much worse, which validates our graph-of-graph is important for domain alignment.

• The Weights of Objective Loss: We have included the weights by modifying the overall loss to $L=L_S+\alpha L_T+\beta L_DA$. To determine the hyper-parameters of $\alpha$ and $\beta$, we study the sensitivity analysis with $\alpha$ and $\beta$ in the range of {0.6, 0.8, 1, 1.2, 1.4}, which is shown in the Table. We can find that our performance is robust to both $\alpha$ and $\beta$. Therefore, we directly set the default parameter to $1$.

In light of these responses, we hope we have addressed your concerns, and hope you will consider raising your score. If there are any additional notable points of concern that we have not yet addressed, please do not hesitate to share them, and we will promptly attend to those points.

Reference

[1] Luo X, Zhao Y, Mao Z, Qin Y, Ju W, Zhang M, Sun Y. RIGNN: A Rationale Perspective for Semi-supervised Open-world Graph Classification. TMLR 2023.

[2] Liu Y, Ding K, Liu H, Pan S. GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection. WSDM 2023

[3] Wu M, Pan S, Zhu X. Openwgl: Open-world graph learning. ICDM 2020.

[4] Gui S, Li X, Wang L, Ji S. GOOD: A Graph Out-of-Distribution Benchmark. NeurIPS 22

[5] Hoffmann M, Galke L, Scherp A. Open-World Lifelong Graph Learning. IJCNN 2023.

Dear reviewers,

We sincerely appreciate your valuable feedback.

As the deadline for the author-reviewer discussion phase is approaching, we would like to check if you have any other remaining concerns about our paper. If our responses have adequately addressed your concerns, we kindly hope that you can consider increasing the score.

We sincerely thank you for your dedication and effort in evaluating our submission. Please do not hesitate to let us know if you need any clarification or have additional suggestions.

Best Regards,

Authors.

Thanks for your feedback and we are happy to resolve your further concerns as follows:

Q1. Given this work's similarity with open-world graph works, it's hard to claim open-set graph domain adaptation as a new problem.

A1. The difference between our problem and traditional open-world graph problems is the introduction of distribution shifts between training data and test data. Given that extensive works [1,2] focus on distribution shifts, we believe that our problem is more challenging than the classic open-world graph problems. We have also revised our manuscript accordingly.

Q2. The graph-of-graph technique has been explored in previous open-world works.

A2. Thanks for your problem. You may refer to RIGNN [3]. Actually, graph-of-graph is not our contribution while one of our related contributions is Well-designed Mixup for domain alignment and open-set classification. We not only utilize linear interpolation to generate virtual novel samples in the hidden space, but also combine multiple cross-domain neighboring samples based on graph-of-graph to generate virtual samples for domain alignment.

Moreover, we summarize the differences between RIGNN and our method as follows:

• Different methodology. RIGNN constructs a graph-of-graph to connect unlabeled graphs with labeled graphs while our DREAM focuses on the exploration of cross-domain relationships between graphs.
• Different motivations RIGNN builds a graph-of-graph to enhance the representation learning while our DREAM aims to align graph representation from different sources.
• Different objectives. RIGNN constructs a graph-of-graph for contrastive learning while our DREAM utilizes the graph-of-graph to guide our multi-sample Mixup for domain alignment.

Q3. regarding the question on plausible cross-domain virtual representations, there's no guarantee that mixing similar graphs would generate virtual representations with similar semantics. This assumption is rather strong without additional supervision.

A3. Thanks for your comment. We have three reasons to support this:

• A recognized fact is that the features of samples with the same semantic information should lay on a high-dimensional manifold as in [4,5]. Therefore, the mixed representations should be still in the high-dimensional manifold, which indicates the similar semantics in most cases.

• Mixing representations from different samples have been introduced in manifold Mixup [6]. This paper [6] shows that mixing in the latent space can produce virtual samples with similar semantics in meaningful regions. Therefore, the assumption is not strong. Moreover, our method extends manifold Mixup into our new setting for domain alignment and open-set classification.

• Our ablation studies (comparison between DREAM w/o Multi-sample Mixup and DREAM) have been shown in Table 3. From the results, we can observe that introducing our Mixup performs much better, which validates our component is reasonable and crucial for domain alignment.

We have also revised our manuscript accordingly.

Q4. To me, the contribution and novelty of this paper is not prominent.

A4. Thanks for your comment. We want to emphasize our contribution as follows:

• New Problem We introduce a novel problem of open-set graph domain adaptation, which accommodates unlabeled in-the-wild target graphs from unseen classes.

• Two branches to learn graph semantics in a complementary way. Our graph-level representation branch employs the message passing and attention mechanism to explore topological knowledge while our subgraph-view branch focuses on key local functional parts using graph clustering and constructs a hierarchical GNN architecture.

• EM-style interaction between two branches. We combine the advantages of two branches by posterior regularization to enhance the consistency between the predictions from the two branches.

• Well-designed Mixup for domain alignment and open-set classification. We not only utilize linear interpolation to generate virtual novel samples in the hidden space, but also combine multiple cross-domain neighboring samples to generate virtual samples for domain alignment.

• Extensive Experiments. Extensive performance comparisons to competing methods and ablation studies validate the superiority of our proposed DREAM over state-of-the-art methods.

Thanks again for your constructive suggestions. Please let us know if you have further questions.

Reference

[1] GOOD: A Graph Out-of-Distribution Benchmark, NeurIPS 2022

[2] SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks, NeurIPS 2022

[3] RIGNN: A Rationale Perspective for Semi-supervised Open- world Graph Classification, TMLR 2023

[4] Conditional Adversarial Domain Adaptation, NeurIPS 2018

[5] CIMON: Towards High-quality Hash Codes, IJCAI 2021

[6] Manifold Mixup: Better Representations by Interpolating Hidden States, ICML 2018

Dear Reviewer,

Thank you for your invaluable feedback. As the deadline for the author-reviewer discussion phase is approaching, we hope to make sure that our response sufficiently addressed your concerns regarding the contribution, as well as the revised version of our paper. We hope this could align with your expectations and positively influence the score. Please do not hesitate to let us know if you need any clarification or have additional suggestions.

Best Regards,

Authors

We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.

Q1: There seem a lot of modules in the DREAM, it’s better to analysis the complexity of the proposed method.

A1: Thanks for your comment. We have analyzed the computational complexity of our method. The computational complexity primarily relies on two different branches for graph representations. Given a graph $G$, $||A||_0$ denotes the number of nonzeros in the adjacency matrix, $d$ denotes the feature dimension, $L$ denotes the number of layers, $T$ denotes the number of views, $R$ denotes the number of clusters. The graph-level representation learning branch takes $O(L||A||_0d+L|V|d^2+Td|V|+Td^2)$. The subgraph-view representation learning branch takes $O(L||A||_0d+L|V|d^2+R^2d)$. In our case, $R^2\ll||A||_0$, $T\ll d$ and $T\ll|V|$. Therefore, the complexity of the proposed DREAM and GraphCL are both $O(L||A||_0d+L|V|d^2)$ for each graph sample, which is linearly related to $||A||_0$ and $|V|$. We have added this into the revised version.

Q2: What I am concern is the scalability of this model, i.e., whether this method can be applied into the dynamic graph scenario for learning.

A2: Thanks for your comment. We have included the complexity analysis, showing that our method has a comparable scalability as popular GraphCL. In future works, we would try to extend the work to more complicated scenarios such as dynamic graphs.

We have also added your suggestion about future works to our revised version. Thanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.

Dear Reviewer,

Thank you for your invaluable feedback. As the deadline for the author-reviewer discussion phase is approaching, we hope to make sure that our response sufficiently addressed your concerns regarding the real-world applications, as well as the revised version of our paper. We hope this could align with your expectations. Please do not hesitate to let us know if you need any clarification or have additional suggestions.

Best Regards,

Authors

We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.

Q1: The format of references is not uniform, such as [4] and [5].

A1: Thanks for your comment. We have unified the reference format.

Q2: What’s the difference between the open-set graph domain adaptation and universal domain adaptation? Can the proposed model be extended to UDA?

A2: Thanks for your comment. Universal domain adaptation allows two domains to own their private categories, which is a more generalized problem including open-set domain adaptation, partial domain adaptation and open-partial domain adaptation. In contrast, we only focus on open-set domain adaptation on graphs. We would extend our DREAM to more generalization problems such as universal graph domain adaptation in our future work.

We have also added your suggestion about future works to our revised version. Thanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.