Characterizing Long-Tail Categories on Graphs via A Theory-Driven Framework

Q1: It may require clarification about what sets the TAIL2LEARN framework apart from the existing Graph U-Net.

A1: We are the first to consider the long-tail problem in the task space instead of the instance space. The proposed theoretical analysis and framework consider the complexity of the task. In particular, our model is different from Graph U-Net in the following aspects:

• one of our key ideas is to group similar tasks as a hypertask, while Graph U-Net samples a subset of important nodes ;

• Graph U-Net keeps the indexes of selected nodes for unpooling operation, while our method preserves the tasks hierarchically information to capture the complex relationships among tasks.

 

Q2: It might be worth considering whether the authors have explored the possibility of subdividing the samples into more finely-grained subclasses.

A2: Thank you for your insightful comment!

• Yes, the samples can be finely-grained grouped by increasing the number of tasks. There have been some work delved into overclustering, i.e., the number of clusters is larger than the number of categories. The work [1,2] posits that overclustering can be beneficial for the model to learn expressive features.

• We showed the impact of varying the number of tasks on model performance in Appendix F (last subplot of Figure 6). We have also conducted additional experiments to explore the impact. The experimental results show that our model can achieve great model performance when the hyperparameters are in a certain reasonable range. But there is a slight performance degradation when the number of hypertasks is small.

[1] Ji, Xu, Andrea Vedaldi, and João F. Henriques. "Invariant information clustering for unsupervised image classification and segmentation. ICCV, 2019.

[2] Kim, Yunji, and Jung-Woo Ha. "Contrastive fine-grained class clustering via generative adversarial networks." ICLR, 2022.

 

Q3: The authors claimed that $\mathcal{L}_{BCL} potentially controls the range of losses for different tasks. However, the paper lacks experimental results to support this claim.

A3: The loss range is defined as $\max_{t}\frac{1}{n_t}\sum_{i=1}^{n_t}l(f_t(h(\mathbf{x}^t_{i})), y^t_{i}) - \min_{t}\frac{1}{n_t}\sum_{i=1}^{n_t}l(f_t(h(\mathbf{x}^t_{i})), y^t_{i})$. Intuitively, we assume that the model with $\mathcal{L}\_{BCL}$ can maintain good performance on head tasks, so the second term of the range almost remains constant; however, the balanced contrastive learning improves performance on the tail task, so the first term of the range decreases and therefore can help reduce the loss range. Moreover, in the Table below we empirically show that using $\mathcal{L}\_{BCL}$ improves the model performance from 54.6 to 55.8 (bAcc) on the Cora_Full dataset, which also demonstrates the efficacy of our balanced contrastive learning.

Q4: Can Tail2Learn generalize well on graph datasets having a relatively small number of classes such as Cora, CiteSeer, and PubMed?

A4:

• The datasets Cora, Citeseer, and PubMed are widely used graph datasets. However, they exhibit a relatively limited number of categories, a relatively low degree of imbalance, and do not follow a long-tail distribution. Hence these datasets were initially excluded from our paper.

• We have conducted our model on the datasets compared with baselines. The experimental results suggest the great performance of our model on these datasets. We will provide the complete results in the appendix of the later version.

 

Q5: Have you considered the reciprocal version of the current long-tailedness ratio?

A5: Thanks for your suggestion! We will provide detailed discussions and data statistics by using the reciprocal of long-tailedness ratio in our later version.

 

Q6: The notation (e.g., subscripts) in Equation 6 and Equation 7 appears to be exactly the same, while the underlying meaning is different.

A6: Thanks for your suggestion! We try to use $\prime$ to distinguish classes and hypertasks. For example, use $j \in\mathcal{V} _t\backslash i$ to represent all nodes belonging to category $t$ except $i$, and use $j \in\mathcal{V} _{t^\prime}\backslash i \cup \{z _{t^\prime}\}$ to define all nodes belonging to hypertask $t^\prime$ except $i$ include the prototype $z _{t^\prime}$ of hypertask $t^\prime$. We seek your perspective on the proposed change. We intend to apply this change in the later version if you find it is better for understanding.

 

Q7: The performance of ImGAGN [2] in Table 1 seems unusually low compared to classical GNN.

A7: In the default setting of ImGAGN, it considers only one class as the tail category and generates synthetic minority nodes. Therefore, the performance of the method is relatively weak. We adjusted the number of categories considered as tail categories in ImGAGN, and the experimental results did show an improvement in performance.

Q1: There could be a trade-off between achieving reduced complexity and maintaining distinctiveness among classes.

A1: Thank you for your insightful comment!

• Yes, there has been some work delved into overclustering, i.e., the number of clusters is larger than the number of categories. The work [1,2] posits that overclustering can be beneficial for the model to learn expressive features.

• We showed the impact of varying the number of hypertasks on model performance in Appendix F (last subplot of Figure 6). We have also conducted additional experiments to explore the cases when the number of overtasks >, =, < the number of categories. The experimental results show our model (also using cross-entropy loss and contrastive loss) can ensure sufficient distinctiveness and achieve great model performance. But there is a slight performance degradation when the number of hypertasks is small (i.e., # of hypertasks is way smaller than the # of classes), potentially attributed to issues of indistinctiveness.

[1] Ji, Xu, Andrea Vedaldi, and João F. Henriques. "Invariant information clustering for unsupervised image classification and segmentation. ICCV, 2019.

[2] Kim, Yunji, and Jung-Woo Ha. "Contrastive fine-grained class clustering via generative adversarial networks." ICLR, 2022.

 

Q2: Given the long-tail situation, there would be very few training samples with labels for tail classes. Can you elucidate how Tail2Learn can work effectively in this scenario?

A2: Yes, we use balanced contrast loss to mitigate this problem, which is shown as follows (Section 3.2 M2).

$\mathcal{L} _{SCL}(\mathbf{z} _i) = -\frac{1}{n _{t}-1} \times \sum _{j \ \in\mathcal{V} _t \backslash i} \log \frac{\exp \left(\mathbf{z} _{i} \cdot \mathbf{z} _{j}/\tau\right)}{\sum _{1\leq q\leq T} \frac{1}{n _{q}} \sum _{k\in\mathcal{V} _q} \exp \left(\mathbf{z} _{i} \cdot \mathbf{z} _{k}/\tau\right)}$

$\mathcal{L}(\mathbf{z} _i)=-\frac{1}{n _{t}-1} \times \sum _{j \ \in\mathcal{V} _t\backslash i} \log \frac{\exp \left(\mathbf{z} _{i} \cdot \mathbf{z} _{j}/\tau\right)}{\sum _{k\in\mathcal{V}} \exp \left(\mathbf{z} _{i} \cdot \mathbf{z} _{k}/\tau\right)}$

To be noted that,

• Since there are significant differences in the number of samples between the head and tail categories, the head categories have a great contribution to the denominator in classic contrastive loss. To address this issue, our loss function incorporates a category-based normalization in the denominator, thereby mitigating the dominance of the head categories.

• In addition, we normalize by the number of positive pairs ($n_t-1$) to compute an average instead of a sum to alleviate the label imbalance issue.

• When applying to hypertasks, the node set $\mathcal{V}_t$ includes both task nodes belonging to hypertask $t$ and prototypes of hypertask $t$, which increases the number of positive pairs, especially helping tail categories.

 

Q3: Can you provide more details about the improvements made in tail classes as shown in Figure 4 in LTE4G [1]?

A3: Thanks for your valuable suggestion! In Figure 1, we plot the model performance on each category, showing that our model outperforms the original GCN method. In addition, we have added the following figure to provide more details (https://anonymous.4open.science/r/Tail2Learn-CE08/figs/resultPerClass.pdf).

Q: Related works not well addressed. The long-tail categories studied in the paper is the same as the node-level imbalanced-class problem in graph.

A: Thank you for your suggestion!

• We would like to respectfully emphasize, as we identified in the introduction, that there are three fundamental challenges of long-tail classification problems (C1. Highly-skewed data distribution, C2.Label scarcity, and C3. Task complexity). While there exists some similarity between long-tail and imbalance classification, long-tail learning on the challenges arising from a significantly larger number of tail classes. Consequently, these two problem domains are not the same.

• We have cited work [1-6] for imbalance in the section of related work. Furthermore, we have introduced the TAM method as a baseline for our experiments. We will provide the complete experimental results in a later version.

Thank you for your careful review; it is very helpful for enhancing the quality of our paper. Yes, Theorem 1 should retain the normalization term 1/T. We are still revising our paper to accommodate this change.

In addition, we think that 'improving task diversity can be helpful for multi-task learning' does not contradict our paper. While our paper incorporates the paradigm of multi-task learning, it is crucial to highlight the fundamental differences between long-tail learning and multi-task learning: long-tail learning not only involves a large number of classes but also exhibits substantial class-membership imbalance.

• In the context of multi-task learning discussed in previous work [1], each task corresponds to $n$ observed input samples, where enhancing task diversity proves beneficial for performance. Increasing the number of tasks $T$ decreases the cost associated with estimating the representation $h$, while increasing the number of samples $n$ decreases the cost of estimating task-specific predictors.

• On the other hand, in long-tail learning, where we define task complexity in situations where a vast majority of samples belong to a few head classes, and a minority of samples are allocated to tail classes, increasing the number of classes (particularly tail classes) may increase the difficulty of learning a salient representation and depicting the support regions of each classes. In long-tail learning, task complexity is relevant to $n_1,\ldots , n_T, T$, thus task complexity does not reduce the generalization error.

• Our experimental results show great performance in utilizing hierarchical grouping (Table 1), especially in the harsh long-tail setting (Table 2).

Further, we argue that 'in the long-tail setting, the increase in task complexity, especially considering tail categories have very few samples, raises the difficulty in correct classification'. This is because the shared representation $h$ can be considered as a consensus of different views. The cost of maximizing consistency and learning a uniform representation from multiple subspaces will increase when categories (especially tail categories) increase. And when the number of categories increases, the loss range remains constant or increases.

[1] Maurer et al., The Benefit of Multitask Representation Learning, 2016.