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

Authors: Wenlong Chen, Ao Ke, Chuanwen Feng, Xike Xie, S Kevin Zhou
Primary area: learning on graphs and other geometries & topologies
Keywords: Out-of-distribution

Abstract:
Graph neural networks (GNNs) have achieved dominant performance in various prediction tasks on graphs. When deploying GNNs in the real world, estimating the possibility of out-of-distribution (OOD) testing samples becomes a crucial safety concern. Although some research has investigated the graph OOD detection problem, most have concentrated on single-label classification scenarios, aspecific case of the more general multi-label classification, which has broader applications, such as in social networks where nodes can represent users with multiple interests or attributes. In this paper, we first introduce and define the multi-label graph OOD detection problem and propose a simple yet effective pattern matching-based OOD detection method to address it. In particular, our method utilizes feature pattern matching and label pattern matching to obtain two matching scores. By incorporating topological structure adjustment, we ultimately derive confidence scores, serving as indicators of the likelihood that a test sample is an OOD instances. We conduct extensive comparisons with existing OOD detection methods in the context of multi-label graphs. The results show that our method achieves an impressive 7.61% reduction in FPR95 compared to the leading baselines, setting a new state-of-the-art. Furthermore, our approach can servas a benchmark for OOD detection on multi-label graphs.

Decision: reject
Reviewer scores: 5, 5, 6, 3

Reviews and discussion:
<thread>
creation date:
1729050716908

thread_type:
official_review

<thread_object>
creator: reviewer_5z1x

<content>
summary:
This manuscript studies the OOD problem on multi-label graphs. The authors introduce feature pattern matching, label pattern matching, and label propagation via GNN and then conduct the multi-label OOD classification on nodes. Experimental results, as they reported, demonstrate the effectiveness of their solution.

strengths:
S1: the technical solution seems to make sense. 

S2: Figure 1 is beautiful

weaknesses:
W1: code not available

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

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

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

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


Overall, this manuscript may propose a self-contained solution to multi-label OOD problems on graph domains. Although I hate to say this, I am afraid I have to say (with full respect) that the novelty and contributions of this submission might be not strong enough for this conference. I think it might be further enhanced with some theoretical support, more convincing public code, and more clear paper writing 

Plus: Kindly note that when I say "more clear writing", I do not only hope the language issues could be improved (e.g. line 075-077) but I also think there are some logical points in the paper should be polished. For example, the authors use a large part of the content to say they use sigmoid instead of softmax for multi-label problems. Do the authors wish to treat this as their contribution? because I think it is such a simple and obvious thing. If the authors wish to claim this tiny change matters and is a significant technique contribution, maybe they can provide with in-depth theory analysis further. Many other places are looked like just for filling the page length but I don't know why they are necessary to be mentioned. The authors present some technique choices and different results (like Figure 3) but we need to know why.

questions:
Q1: 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$.

Q2: refer to W2

Q3: refer to W5
</content>
</thread_object>

</thread>
<thread>
creation date:
1730718529692

thread_type:
official_review

<thread_object>
creator: reviewer_2ctu

<content>
summary:
This paper addresses the challenge of out-of-distribution (OOD) detection for graph neural networks (GNNs) in multi-label classification tasks. The authors propose a novel, pattern matching-based method that combines feature and label pattern matching to produce two matching scores. These scores are further refined with topological structure adjustments to derive confidence scores, indicating the likelihood of a test sample being an OOD instance.

strengths:
1. The multi-label classification on graph OOD detection is important and interesting.
2. The research problem is challenging.
3. The method is supported by theoretical analysis, which strengthens the validity of the approach.
4. The proposed method demonstrates promising results across multiple datasets, including a real-world application, highlighting its practical effectiveness and versatility.

weaknesses:
1. 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.

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

questions:
same as in the Weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730731356168

thread_type:
official_review

<thread_object>
creator: reviewer_bjgr

<content>
summary:
Multi-label classification on graphs is an important task. This paper studies the multi-label graph OOD detection problem and proposes a simple yet effective pattern matching-based OOD detection method. Experimental results show that the method proposed in this paper is good.

strengths:
1. This paper is easy to follow.
2. Multi-label classification on graphs is an important issue. 
3. Improvement in experiments seems good.

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

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

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

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

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

   [1]Multi-label node classification on graph-structured data. TMLR 2023.

questions:
Can you provide the experimental results related to the PCG, HumLoc, and EukLoc datasets [1] ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730829591153

thread_type:
official_review

<thread_object>
creator: reviewer_ucql

<content>
summary:
This paper focuses on detecting OOD in graph multi-label classification problems. It defines the problem, and proposes a method to quantify feature pattern matching and label pattern matching, utilizing label propagation to derive the final confidence score for OOD. Empirical evaluations on five real-world datasets demonstrate that the proposed method achieves better average accuracy compared to selected baselines.

strengths:
Strengths:
1. The paper studies OOD in a practical setting, which could lead to potential real-world application and inspire further research and development in the field.

2. The proposed method is straightforward and easily understandable.

3. Ablation studies are included to analyze the contribution of different components of the proposed method.

weaknesses:
Weaknesses:
1. 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 approach to determine optimal weights.

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

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

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

questions:
See Weaknesses
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies the graph OOD problem which is encountered when employing graph neural networks (GNNs) in real-world scenarios.  The authors propose an approach which adapts the graph OOD problem which is typically on a single-label classification setting to a multi-label one.  Moreover, the authors propose an approach to combine feature pattern matching and label pattern matching to estimate confidence of samples being OOD.  

Reviewers pointed out several weaknesses in this work which led to a reject recmomendation at this time.  There were a few themes of concerns raised:

- Perceived limited novelty, given the previous approaches of feature pattern matching and label pattern matching have been adopted in prior works (ucQL, 5Z1x)

- Lack of theoretical foundation to support effectiveness of the method; the method is largely heuristic (uCQL, 5Z1x, bjgR)

- Missing experiments around runtime and scalability (2CTU, bjgR)

I encourage the authors to fold these into their revision.