Rethinking Independent Cross-Entropy Loss For Graph-Structured Data

We really appreciate the reviewer for the agreements on our technical contributions and presentation. We would like to address the concerns one by one in the following.

W1 and W2: Thanks for your constructional suggestions. We will revise the paper according to the questions and clarify the connection between (5) and (4d) to facilitate readers' understanding of the relationship between maximum likelihood estimation and cross-entropy loss.

Q1: We will introduce the transition from (4c) to (4d). We aim to learn the parameters $\theta$ to maximize the likelihood of the observed conditional distribution $p\left(y_{1}, \ldots, y_{L} \mid z_{1}, \ldots, z_{L} ; \theta\right)$, known as maximum likelihood estimation. To simplify the computation of the likelihood function, it is common practice to use the logarithm of the likelihood function, which transforms the product of probabilities into a sum (taking the logarithm does not alter the optimal solution of the likelihood).

Q2: Thanks for your pointing out. We will fix this mistask and use $i$ as the indice uniformly.

Q3: We flatten the matrix $y_i y_m^{\top} \in \mathbb{R}^{C\times C}$ into shape ${1\times C^2}$, and the shape of output of $g_\phi$ is ${n\times C^2}$, where $n$ represents the number of nodes and $c$ represents the number of classes.

Q4: In Table 1, for citation networks(Cora, CiteSeer and PubMed), following the widely used standard split proposed by [1], we use 20 labeled nodes per class for training, 500 nodes for validation and 1000 nodes for testing. For DBLP and Facebook, we use 20 labeled nodes per class as the training set, 30 nodes per class for validation, and the rest for testing. To verify the the influence of labeling rate, we compare with vanilla cross-entropy (CE) loss on three citation networks. We randomly select five and ten labeled nodes per class as the training set, leaving the validation and test sets unchanged. Considering each backbone model (i.e., GCN, SGC and MLP), our joint-cluster (JC) loss consistently diliver a much higher node classification accuracy.

Q5: Following the experimental settings of original papers, for GAT, we choose the model parameters by utilizing an early stopping strategy with a patience of 100 epochs on classification cross-entropy loss. For other models(GCN, SGC, MLP and GrapgSAGE), we utilize the model parameters which perform best on the validation set for testing. The remaining hyper-parameters including learning rate, dropout and weight decay are tuned for different models.

Q6: In Table 2 of manuscript, we have already demonstrated the advantages on two extremely imbalanced datasets, LastFMAsia and ogbn-arxiv. We attribute this result to the referential ability of joint-cluster distribution modeling, which refers to a cluster of nodes when making decision on target node label during training and inference. The joint distribution weakens the over-confident prediction on the majority classes by assigning prediction confidence on other related minority classes at the cluster, and thus ameliorates the generalization performance. However, in the extremely imbalanced datasets, there are a large number of majority class nodes in the reference cluster of minority class nodes, making the reference information of nodes in the imbalanced datasets not as rich as in the balanced datasets. We think this leads to the improvement on balanced data is higher than imbalanced data.

---

Reference:

[1] Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.

We really appreciate the reviewer for the agreements on our technical contributions and presentation. We would like to address the concerns one by one in the following.

W1: Appreciate for the pointing out of these related work. It should be clarified that we are not overemphasizing the contribution of our method, and we will revise the paper to make our contribution clearly understood. We agree that our method only has the same motivation with the above-mentioned models, but this does not overshadow the multifold contributions of this work. The motivation of node labels are dependent is a common sense in graph community (e.g. GNNs utilize message passing mechanism, label propagation[2] distributes labels along edge, CRF-based methods[1] focus on modeling the local label correlation of every linked node pair and contrastive methods[3] treat neighbors as positive samples), but it is more important in how we can incorporate this knowledge. Comparing with each mentioned work, we list the detailed differences below:

• SPN[1] for inductive setting models the local label correlation of each linked node pair via nodeGNN and edgeGNN and takes all edges in whole graph as input to propagate all the pairwise label correlations along edges. In contrast, we train and infer the joint distribution of the target node only with one reference signal (i.e., cluster), which allows the batch training on large graphs (e.g., Amazon with millions of nodes).
• PTA[2] analyzes the relationship between label propagation and decoupling GNN based on feature propagation. We will supplement this excellent work in the label propagation section of related work. We believe that this method still belongs to the label propagation paradigm, which utilizes label propagation to assign pseudo labels to unlabeled nodes and then performs training.
• Local_GCL[3] proposes a graph contrastive learning method, which creates positive pairs from first-order neighbors. Different from self-supervised contrastive learning, which measures the feature similarity of a pair of data, instead, we extend to measure the joint label distribution of the target node and its cluster.

We introduce a new paradigm of joint-cluster supervised learning for graph data, which breaks the i.i.d assumption in independent cross-entropy loss computation and model the joint distribution between the target node and its located cluster. This perspective on viewing and handling label dependencies between nodes has never appeared before, and we believe it is novel enough.

W2: Thank you for your suggestion. We compare with each mentioned work and list the node classification accuracy on citation networks below. We follow the standard data split. Our method is orthogonal to label propagation and contrastive learning, and they can be effectively combined with our joint-cluster loss, such as using the pseudo-labels assigned by label propagation to make the cluster information richer or introducing node-cluster level contrastive objectives in the representation learning process. We intentionally keep our method simple to illustrate the effectiveness of joint-cluster loss and do not utilize unlabeled nodes during the training process, unlike PTA[2] which assigns pseudo labels to unlabeled nodes and Local_GCL[3] which constrains the representation learning process of unlabeled nodes. It can be found that our method achieves results second only to Local_GCL on small graph data, and delivers the best performance on larger graph arxiv. The SPN[1] requires the edges between labeled nodes for training due to its edge_GNN component. Under the transductive setting, the extremely small number of edges makes it difficult for SPN to model the information of node pairs. For arxiv, SPN cannot be trained on titan RTX24G GPU due to high memory requirements for training each node-pair, which reflects the advantage of utilizing cluster as the reference signal. In addition, our method demonstrates good scalability on millions of large-scale multi-class graphs (Yelp and Amazon), where multi-class tasks are a scenario not covered by the above mentioned works.

---

Reference:

[1] Meng Qu, et al., Neural Structured Prediction for Inductive Node Classification, ICLR 2022

[2] Hande Dong, et al., On the Equivalence of Decoupled Graph Convolution Network and Label Propagation, WWW 2021

[3] Hengrui Zhang, et al., Localized Contrastive Learning on Graphs