PATTERN MATCHING-BASED OUT-OF-DISTRIBUTION DETECTION FOR MULTI-LABEL NODE CLASSIFICATION

Q1: code not available.

A1: We will open-source the code after the publication of the paper.

Q2: I want to know the difference in MLNC OOD detection between graph and CV/NLP data. My main concern is that there seems no difficulty in applying the existing techniques on the graph. I wonder about the unique challenges of graph domains and how the authors solve them with their creative contributions.

A2: In the MLNC OOD detection problem, the primary challenge lies in the fact that each node can be assigned multiple labels. As shown in Figure 3, methods like MSP, which rely solely on the maximum confidence score, can be adapted but fail to achieve satisfactory performance. To address this, our label pattern matching method incorporates information from multiple labels. Furthermore, we leverage the crucial label dependency relationships inherent in multi-label scenarios, a factor not considered in other OOD detection methods. Inspired by the VIM method, we also integrate the feature distribution information from the training set to enhance the robustness of our method. Finally, while CV/NLP datasets typically assume independent and identically distributed data, graph data contains exploitable topological structures. Therefore, similar to GNNASAFE, we employ a label propagation algorithm to further refine the scores.

Q3: It seems that this paper is not the first work to solve multi-label graph OOD detection. See this work: Evidence-Based Out-of-Distribution Detection on Multi-Label Graphs.

A3: Thank you for pointing this out. Based on our understanding, the problem definition in that work differs significantly from ours. Specifically, in [1], a node is defined as an OOD sample if it contains any unknown category. In contrast, under our definition, a node is classified as OOD only if it does not belong to any known category. Our definition is a natural extension of the one proposed in JointEnergy.

[1] Evidence-Based Out-of-Distribution Detection on Multi-Label Graphs

Q4: I think the paper could be further polished. The language writing could be significantly improved.

A4: Thank you for your suggestion regarding our writing. Our intention was to illustrate that, compared to directly using logit information, utilizing probabilities mapped through the sigmoid function yields less effective results for the OOD detection problem. We sincerely apologize for the confusion caused by the unclear logic in this section. Based on your suggestion, we have revised and condensed this part in the original manuscript.

Q5: It would be more solid if the proposed solutions could have some theoretical guarantee.

A5: Similar to works like MSP and Max Logit, our method is heuristic-based and validated through experimental results. Specifically, our method is designed for the graph multi-label OOD scenario, leveraging the unique characteristics of this problem to develop a tailored solution. Therefore, as demonstrated by the experimental results, I believe our method is better suited for the MLNC OOD problem compared to other approaches.

Q6: between ID and OOD nodes, there seem to be some middle cases, for example, ID nodes have labels $A, B, C$ with distribution $P_1(A, B, C)$, some other nodes have labels $A, B, C, D, E$ with a totally different distribution $P_2(A, B, C, D, E)$, and then the rest node have labels $D, E$ with the distribution $P_3(D, E)$. I wonder how to deal with $P_1$ and $P_2$.

A6: In fact, such nodes do exist. We define both $P_1$ and $P_2$ as ID nodes since they have known labels $A$, $B$ and $C$, while $P_3$ is a typical OOD node because it does not belong to any known category. Since we cannot determine during the training phase which nodes belong to $P_2$ , no additional processing is performed. However, if there are a large number of $P_2$ nodes in the training set, it can significantly increase the difficulty of detecting $P_3$ nodes during the OOD detection process (as discussed in response to Reviewer 1's Q3 regarding why DBLP performs poorly in certain domains). We will provide a more comprehensive discussion of this issue in future revisions.

Q1: The connection between pattern matching and multi-label classification needs clearer illustration. Specifically, it would be helpful to explain how pattern matching contributes to or enhances the multi-label classification process and to outline the role it plays within the proposed framework.

A1: We argue that the goal of OOD detection is not to enhance classifier accuracy but to increase their trustworthiness. Our method is a post-processing method that computes feature pattern matching scores and label pattern matching scores based on the model's output features and logits, respectively, to quantify the differences between test samples and training samples (i.e., ID samples). Compared to other methods, our method achieves better performance because it is more tailored to the graph-based multi-label OOD detection scenario. Specifically, it leverages label dependencies and graph topology information, and the incorporation of multi-source information further enhances its robustness.

Q2: The scalability of the proposed method is not thoroughly explored, particularly for large-scale graphs where such an method might be impractical.

A2: As discussed in Q5 with Reviewer 2, the time complexity of our method is $O(({K_l}^2+K_f) \cdot N)$, which ensures good scalability and allows it to handle large-scale graphs effectively.

Q1: The method proposed in this paper lacks necessary theoretical analysis.

A1: Similar to works like MSP and Max Logit, our method is heuristic-based and validated through experimental results. Our method is specifically designed for the multi-label graph OOD detection scenario, leveraging multi-source information to address this challenge. More specifically, our method incorporates feature distribution information, label dependencies, and graph topology information based on the characteristics of the problem. As demonstrated by the experimental results, we believe our method is better suited for this task.

Q2: The idea of confidence score is not novel, as it has been widely used in works related to OOD and class imbalance.

A2: We use the term confidence score to align with its usage in other works, making it easier for peers to understand and reproduce our work. However, the technical details for obtaining the confidence score in our method differ from those in other studies. For example, the MSP method computes confidence scores by applying softmax to the model’s logit outputs and selecting the maximum value. In contrast, our method leverages multi-source information and accounts for label dependencies and graph topology relationships in the context of multi-label graph OOD detection. Therefore, although both our method and others ultimately rely on confidence scores to detect OOD samples, our method is better suited for multi-label graph OOD detection, as supported by the experimental results.

Q3: I noticed that the authors cited the work of Zhao et al.[1], but they did not use the relevant new datasets in the experimental section.

A3: According to your request, we have supplemented the experimental results related to the PCG, HumLoc, and EukLoc datasets. Experimental results indicate that, overall, our method still demonstrates a performance advantage.

Q4: The ablation experiments show it is very sensitive to hyperparameters, especially regarding label propagation.

A4: From the results of the ablation experiments, our method does show sensitivity to the propagation parameter T. For multiple datasets, the ablation experiments reveal a consistent pattern: excessively large T values lead to a sharp decline in OOD detection performance. The underlying reason is that excessive propagation results in over-smoothing, where the information from each node spreads across the entire graph, causing the loss of node-specific information and making nodes harder to distinguish. As a result, we limit the propagation to a single round when selecting the propagation hyperparameter. Thank you for pointing this out, we will provide a more detailed explanation of this phenomenon in the revised version.

Q5: No time complexity or runtime comparison. No pseudo-code and no data statistics.

A5: In our method, the time complexity primarily comes from the computation of feature pattern matching and label pattern matching. During the computation of feature pattern matching, each sample needs to query the pre-modeled density function for each of its $K_f$-dimensional features. Thus, the time complexity for feature pattern matching is $O(K_f)$ per sample. For label pattern matching, each sample's logit vector with $1 \times K_l$ dimension needs to perform a dot product with an $M_{K_l \times K_l}$ matrix. The result is in a time complexity of $O({K_l}^2)$ per sample. Therefore, for $N$ test samples, the overall time complexity of our method is: $O(({K_l}^2+K_f) \cdot N)$.

Due to the limits of page, we included the pseudocode in the appendix when submitting the paper, and the data statistics you mentioned are presented in Table 2 of the main text.

Q3: Though the experimental results show the proposed method achieves a better score on average, it is suggested to provide further analysis to explain why it performs worse in certain domains within the DBLP dataset. In addition, the paper lacks a theoretical foundation to support the effectiveness of the proposed method.

A3: Similar to works like MSP and Max Logit, our method is heuristic-based and validated through experimental results, and here is the analysis of why our method performs poorly in certain domains of the DBLP dataset: In the DBLP dataset, among all nodes with the DM label, 39% also have additional labels, which is the highest proportion compared to other categories (DB, AI, and IR have proportions of 26%, 17%, and 36%, respectively). Consequently, when the DM category is treated as the OOD category, the training set still contains many nodes that actually have the DM label (i.e., nodes labeled with DM along with other labels), allowing the model to learn from these nodes. During the testing phase, the model predicts OOD nodes to have similar label patterns and feature patterns to these nodes, leading to a decline in the performance of our method.

Q4: The major concern is the limited novelty of the proposed method. Feature pattern matching and label pattern matching have been widely adopted in previous works like NAC and (Hendrycks et al., 2022). And label propagation is also common in handling graph data to refine pseudo labels or predicted scores. The proposed method appears to be a direct combination of existing methods in multi-label classification OOD and graph mining, with limited novel contributions.

A4: We argue that there exist significant difference between our work and existing works utilizing feature and logit information for addressing the OOD problem. First, our problem definition is different. These methods are designed for single-label OOD detection or multi-label OOD detection in non-image data, whereas we are focused on solving the graph multi-label OOD problem.

Second, our technical details also differ significantly. For example, NAC processes the network’s multi-layer outputs from the perspective of activation values, whereas we simply use the output from the penultimate layer to represent the feature distribution. Moreover, leveraging the multi-label characteristics of the problem, we propose using label correlations to calculate the label pattern matching score, which has not been addressed in existing OOD detection methods. Experimental results further demonstrate that our method achieves superior performance in graph multi-label OOD scenarios.

Q1: The paper lacks details on the normalization of two scores in Equation 11. Additionally, the equal weighting of these scores seems arbitrary and might need further investigation into alternative weighting schemes or a data-driven method to determine optimal weights.

A1: Regarding the details of the normalization function: given the significant difference in scales between the two score values and the need to preserve the distribution characteristics of the scores, we chose the commonly used Z-Score normalization for the regularization process.

Additionally, we have included ablation experiments on the weights. Spcifically, we assign weights $\beta$ and $1-\beta$ to $S_f$ and $S_l$, respectively. The experimental results indicate that no single weighting achieves optimal performance across all datasets. We believe the reason lies in the fact that different datasets require different types of information, leading to variations in suitable weights. For instance, assigning a higher weight to the label pattern matching score yields better results on the DBLP dataset. However, when the weights are skewed toward extreme values, the average performance of OOD detection declines. This suggests that over-reliance on a single source of information negatively impacts multi-label graph OOD detection, which is precisely why we propose incorporating multi-source information.

In the absence of sufficient prior knowledge to determine which type of information is better suited for a given dataset, we default to assigning equal weights to both scores. Your suggestion is highly valuable, and we will include a discussion on this aspect in the revised version.

Q2: Figure 3 in the paper lacks explicit details about its origin. It is unclear whether the figure is based on specific data analysis or merely serves as a random illustration. This lack of clarity is particularly crucial because the figure is used to explain the design choice of "sum logits" in the absence of theoretical analysis.

A2: Regarding the choice of sum logit, we conducted validation experiments on multiple graph datasets and consistently observed the same conclusion: sum logit outperforms other methodes. However, due to space constraints, we only present the results from the DBLP dataset in the paper to illustrate this phenomenon.