Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
Authors: Eli Chien
Wei-Cheng Chang
Cho-Jui Hsieh
Hsiang-Fu Yu
Jiong Zhang
Olgica Milenkovic
Inderjit S Dhillon
Venue: ICLR 2022 Poster (2022)
Keywords: Self-supervised learning
Graph Neural Networks
Extreme multi-label classification

Abstract: Learning on graphs has attracted significant attention in the learning community due to numerous real-world applications. In particular, graph neural networks (GNNs), which take \emph{numerical} node features and graph structure as inputs, have been shown to achieve state-of-the-art performance on various graph-related learning tasks. Recent works exploring the correlation between numerical node features and graph structure via self-supervised learning have paved the way for further performance improvements of GNNs. However, methods used for extracting numerical node features from \emph{raw data} are still \emph{graph-agnostic} within standard GNN pipelines. This practice is sub-optimal as it prevents one from fully utilizing potential correlations between graph topology and node attributes. To mitigate this issue, we propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT). GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information, and scales to large datasets. We also provide a theoretical analysis that justifies the use of XMC over link prediction and motivates integrating XR-Transformers, a powerful method for solving XMC problems, into the GIANT framework. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets: For example, we improve the accuracy of the top-ranked method GAMLP from $68.25\%$ to $69.67\%$, SGC from $63.29\%$ to $66.10\%$ and MLP from $47.24\%$ to $61.10\%$ on the ogbn-papers100M dataset by leveraging GIANT.

Published as a conference paper at ICLR 2022
NODE FEATURE EXTRACTION BY SELF-SUPERVISED MULTI-SCALE NEIGHBORHOOD PREDICTION
Eli Chien"
Wei-Cheng Chang
University of Illinois Urbana-Champaign, USA ichien3es 11 wllinniis....i.oi..iii..ii mois.edu edu
Amazon, USA chanweic@@aazzoooo
Cho-Jui Hsieh
Hsiang-Fu Yu, Jiong Zhang
University of California, Los Angeles, USA chohsiehEcs, ucla. edu
Amazon, USA [hsiangfu, jionggj
Olgica Milenkovic
Inderjit S. Dhillon
University of Illinois Urbana-Champaige USA mi Lllenkov@ilinoiss
Amazon, USA isdlamazon. com
ABSTRACT
Learning on graphs has attracted significant attention in the learning commu- nity due numerous real-world applications. In particular, graph neural net- works (GNNs), which take numerical node features and graph structure as inputs, have been shown to achieve offieoof-thearr performance on various graph-related learning tasks. Recent works exploring the correlation between numerical node features and graph structure via supersupe learning have paved the way for further performance improvements of GNNs. However, methods used for extract- ing numerical node features from raw data still graph-agnostic within standard GNN pipelines. This practice is sub-optimal as it prevents one from fully utilizing potential correlations between graph topology and node attributes. To mitigate this issue, we propose new self-supervised learning framework, Graph Informa- tion Aided Node feature exTraction (GIANT), GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information, and scales to large datasets. We also provide a theoretical analysis that justifies the use of XMC over link pre- diction and motivates integrating TR-Transformers, a powerful method for solv- ing XMC problems, into the GIANT framework. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Bench- mark datasets: For example, we improve the accuracy of the top-ranked method GAMLP from 68.25% to 69.67%, SGC from 63.29% to 66.10% and MLP from 47.24% 61.10% on the ogbn-papers 100M 100M dataset by leveraging GIANT. Our implementation is public available
INTRODUCTION
The ubiquity of graph-structured data and its importance in solving various real-world problems such as node and graph classification have made graph-centered machine learning an important research area (Lü & Zhou, [011] Shervashidze et al.) [001]] Zhu (005). Graph neural networks (GNNs) offer state-of-the-art performance on many graph learning tasks and have by now become standard methodology in the field (Kipf & Welling 2017 Hamilton et al.) 2017 Velickovic al., 2018 Chien et al. 2020). most such studics, GNNs take graphs with numerical node attributes inputs and train them with task-specific labels.
Recent research has shown that self-supervised learning (SSL) leads to performance improvements in many applications, including graph learning, natural language processing and computer vision.
TThis work was done during Eli Chien's intersship at Amazon, USA.
httpp:: / thub. com/ www.aaaaanccaaee hampe//pcccs/ttreeeeeeee http./////////ccc//e//////aaaaaa http://///mmiinnneeeeeeeeaaa ine/exmmp les ea/giant-xrt

---

Published as a conference paper at ICLR 2022
Neightorhood prediction XMC problem:
Downstream tasks
Standard GNN
A
A, Y trn
T2
pipeline:
No fine-tuning
Optional
GMINs
Node Title Abstract
BoW
X plain
GNNs
*X SLLGNNN
ather ML methods)
Output
Graph information included
Graph information included
1
0
0
D
0
Multi-label
GIANT:
A
A, Y
A
y2 E (0.1)"
Node i: Abstract
SSL line-tuned language
X GIANT
GNN:s other ML methods)
Output
((+())
enzoder
-
Graph Information included
T
f: (:Predictor
Figure 1: Left: Illustration of the standard GNN pipeline and our GIANT framework. Note that only the language model (i.e., the Transformers) in GIANT can use the correlation between graph topology and raw text. Nevertheless, GIANT can work with other types of input data formats, such as images and audio; the study of these models is deferred to future work. Right: Illustration of the connection between our neighborhood prediction and the XMC problem. We use graph informa- tion to self-supervise fine-tuning of the text encoder T (i.e., the Transformer) in our neighborhood prediction problem. The resulting fine-tur tee-tuned text encoder then used to generate numerical node features XGIANT for use in downstream tasks (see also Figure and the description in Section 3
Several SSL approaches have also been successfully used with GNNs (Hu et al. 2020b You et al. 2018 2020. Hu al., 2020c] Velickovie et al.] 2019; Kipf & Welling 2016 Deng al. 2020). The common idea behind these works is to explore the correlated information provided by the numerical node features and graph topology, which can lead to improved node representations and GNN ini- tialization. However,
critical yet neglected issue in the current graph learning literature is how to actually obtain the numerical node features from raw data such as text, images and audio signals. As an example, when dealing with raw text features, the standard approach is apply graph-agnostic methods such as bag-of-words, word2vec (Mikolov et al. 2013) or pre-trained BERT (Devlin et al.) 2019) (As further example, raw texts of product descriptions are used to construct node features via the bag-of -orrdd model for benchmarking GNNs on the ogbn-products dataset (Hu et al. 2020aa Chiang et al., 2019)). The pre-trained BERT language model, as well as convolutional neural net- works (CNNs) (Goyal et al.) 2019; Kolesnikov et al. 2019), produce numerical features that can significantly improve the performance of various downstream learners (Devlin et al. 2019). Still, none of these works leverage graph information for actual self- self-supervision. Clearly, using graph- agnostic methods to extract numerical features is sub-optimal, as correlations between the graph topology and raw features are ignored.
Motivated by the recent success of SSL approaches for GNNs, we propose GIANT, an SSL frame- work that resolves the aforementioned issue of graph-agnostic feature extraction in the standard GNN learning pipeline. Our framework takes raw node attributes and generates numerical node features with graph-structured self-supervision. To integrate the graph topology information into language models such as BERT, we also propose novel SSL task termed neighborhood prediction, which works for both homophilous and heterophilous graphs, and establish connections between neighborhood prediction and the eXtreme Multi-label Classification (XMC) problem (Shen et al.) 2020 YYu et al., 2022; Chang al., 2020b). Roughly speaking, the neighborhood of each node can be encoded using binary lulti-labels (indicating whether a node is a neighbor or not) and the BERT model fine-tuned by successively improving the predicted neighborhoods, This approach allows us to not only leverage the advanced solvers for the XMC problem and address the issue of graph-agnostic feature extraction, but also to perform theoretical study of the XMC problem and determine its importance in the context of graph-guided SSL.
Throughout the work, we focus on raw texts as these are the most common data used for large- scale graph benchmarking, Examples include titles/abstracts in citation networks and product de- scriptions in co- co-purchase networks. To solve our proposed sulf-supe XMC task, we adopt the state-of-the-arr Transssffrr method (Zhang et al.) 202 By using the encoder from the XR- Transformer pre-trained with GLANT, we obtain informative numerical node features which consistently boost the performance of GNNs downstream tasks.
2

---

Published as a conference paper at ICLR 2022
Notably, GIANT significantly improves -fte-offthe-art methods for node classification tasks de- scribed on the Open Graph Benchmark (OGB) (Hu et al. (200aa) leaderboard on three large-seale graph datasets, with absolute improvements in accuracy roughly 1.5% for the first-ranked meth- ods, 3% for standard GNNs and 14% for multilayer perceptron (MIP). GIANT coupled with XR- Transformer is also highly scalable and can be combined with other downstream learning methods.
Our contributions may be summarized as follows.
1. We identify the issue of graph-agnostic feature extraction in standard GNN pipelines and propose a new GIANT self-supervised framework as a solution to the problem.
2. We introduce new approach to extract numerical features by graph information based on the idea of neighborhood prediction. The gist of the approach is to use neighborhood prediction within language model such as BERT to guide the process of fine-tuning the features. Unlike link- prediction, neighborhood prediction resolves problems associated with heterophilic graphs
3. We establish pertinent connections between neighborhood prediction and the XMC problem by noting that neighborhoods of individual nodes can be encoded by binary vectors which may be inter- preted as multi-labels. This allows for performing neighborhood prediction via Rr-Transformers especially designed to solve XMC problems at scale.
4. We demonstrate through extensive experiments that GIANT consistently improves the perfor- mance of tested GNNs on downstream tasks by large margins. We also report new state-of-the-ar results on the OGB leaderboard, including absolute improvements in accuracy roughly 1.5% com- pared to the top-ranked method, 3% for standard GNNs and 14% for multilayer perceptron (MLP). More precisely, we improve the accuracy of the top-ranked method GAMLP (Zhang et al. 202 from 65% to 69.67%. SGC (Wu et al. 2019) from 63. 69% to 66.10% and MLP from 47 7.24% to 61.10% on the
100M dataset.
5. We present new thcoretical analysis that verifies the benefits of key components in XR- Transformers on our neighborhood prediction task. This analysis also further improves our un- derstanding of XR-Transformers and the XMC problem.
Due to the space limitation, all proofs are deferred to the Appendix.
BACKGROUND AND RELATED WORK
General notation. Throughout the paper, we use bold capital letters such as A to denote matrices. We use A, for the i-th row of the matrix and A.y for its entry in row i and column j. We reserve bold lowercase letters such as a for vectors. The symbol I denotes the identity matrix while 1 denotes the all-ones vector. We use o(),, O+),, w.), (()) in the standard manner.
SSL in GNNs. SSL is a topic of substantial interest due to its potential for improving the perfor- mance of GNNs on various tasks. Exploiting the correlation between node features and the graph structure is known to lead to better node representations or GNN initialization (Hu et al., 2020b You al. 2018 2020 Hu et al. 2020c). Several methods have been proposed for improving node representations, including (variationa)) graph autoencoders (Kipf & Welling, 2016). Deep Graph Infomax (Velickovic et al., 2019) and GraphZoom (Deng et al. 2020). For more information, the interested reader is referred to a survey of SSL. GNNs (Xie et al. (021]. While these methods can be used as SSL modules in GNNs (Figure [ it clear that they do not solve the described graph agnostics issue in the standard GNN pipeline. Furthermore, the above described SSL GNNs mod- ules and other pre-processing and post-processing methods for GNNs such as C&S (Huang et al.) 2021) and FLAG (Kong al. 2020 in general improve graph learners, it is worth pointing out that they can be naturally be integrated into the GIANT framework. This topic is left as a future work.
The XMC problem, PECOS and TR-Transformer. The XMC problem can be succinetly formu- lated as follows: We are given a training set {T, y where T; D is the ith input text instance and y; E {0, _ is the target multi-label from an extremely large collection of labels. The goal is to leam function f D x [4] + R, where f(T, captures the relevance between the input text T' and the label I. The XMC problem is of importance in many real-world applications (Jiang et al. 2021 Ye et al. 2020): For example, in E-commerce dynamic search advertising, XMC arises when trying to find a "good" mapping from items to bid queries on the market (Prabhu et al. 2018 Prabhu &
Varma 2014]. In open-domain question answering, XMC problems arise when trying to map ques-
3

---

Published as a conference paper at ICLR 2022
tions to "evidence" passages containing the answers (Chang et al. 2020a Lee et al. 2019). Many methods for the XMC problem leverage hierarchical clustering approaches for labels (Prabhu et al, 2018 You et al. 2019). This organizational structure allows one to handle potentially enormous numbers of labels, such as used by PECOS (Yu et al. 2022). The key is to take advantage of the correlations among labels within the hierarchical clustering. In our approach, we observe that the multi-labels correspond to neighborhoods of nodes in the given graph. Neighborhoods have to be predicted using the textual information in order best match the priori given graph topology. We use the oftte-of-thearr XR- TR-Transformer Zhang et al.) 2021a) method for solving the XMC prob- lem achieve this goal. The high-level idea is to first cluster the output labels, and then learn the instance-to-cluster "matchers" (please refer to Figure 2 Note that many other methods have used PECOS (including ) for solving large-scale real-world learning problems (Etter et al. 2022; Liu et al. 2021,Chang et al. 2020b; Baharav et al., [202]] Chang et al. 2021]] Yadav
ct al. 2021: Sen et al. 2021). but not in the context of self-supervised numerical feature extraction as done in work.
GNNs with raw text data. It is conceptually possible to jointly train BERT and GNNs in an end-to-end fashion, which could potentially resolve the issue of being graph agnostic in the standard pipeline. However, the excessive model complexity of BERT makes such a combination practically prohibitive due to GPU memory limitations. Furthermore, it is nontrivial to train this combination of
methods with arbitrary mini-batch sizes (Chiang et al.) 2019 Zeng et al.) 2020). In contrast, the XR- Transformer architecture naturally supports mini-batch training and scales well (Jiang et al.) 2021). Hence, our GIANT method uses XR- ArR-Trnsforrmrs instead of combinations of BERT and GNNs. To the best of our knowledge, we are aware of only one prior work that uses raw text inputs for node classification problem (Zhang et al., 2020), but it still follows the standard pipeline described in Figure [ Some other works apply GNNs on texts and for document classification, where the actual graphs are constructed based on the raw text. This is clearly not the focus of this work (Yao et al.,
2019 Huang et al.] 2019;
Zhang & Zhang 2020 Liu et al. 2020).
METHODS
Our goal is to resolve the issue of graph-agnostic numerical feature extraction for standard GNN learning pipelines. Although our interest lies in raw text data, as already pointed out, the proposed methodology can be easily extended to account for other types of raw data and corresponding feature extraction methods.
To this end, consider a large-scale graph G with node set V (1.2.....n) n) and adjacency matrix A E {0, 10,1_x Each node i is associated with some raw text, which we denote by T, The language model is treated as an encoder & that maps the raw text Ti to numerical node feature X, Rdd Key to our SSL approach is the task of neighborhood prediction, which aims determine the neighborhood A; from T, The neighborhood vector A; can be viewed as a target multi-label y; for node i, where have L labels. Hence, neighborhood prediction represents an instance of the XMC problem, which we solve by leveraging XR- TRR-Trassformers The trained encoder in an XR-Transformer generates informative numerical node features, which can then be used further in downstream tasks, the SSL GNNs module and for GNN praiting
Detailed description regarding the use of XR- Tr-nranstsseers for Neighborhood Prediction. The most straightforward instance of the XMC problem is the one-versus-all (OVA) model, which can be formalized as (T, w/" (T); E [L], where W (wi..... WL] E R are weight vectors and D + Rd is the encoder that maps T d-dimensional feature vector. OVA can be a deterministic model such as bag-of-word (TFIDF) model or some other model with learnable parameters, such as XLNet (Yang et 2019) and RoBERTa (Liu et al., (019b). We choose to work with tre-trained BERT (Devlin et al.) 2019).
the Term Frequency-Inverss Document Frequency
Also, one can change & according to the type of input data format (i.e., CNNs for images). Despite their simple formulation, it is known Chang et al. (2020b) that fine-tuning transformer models di- rectly on large output spaces can be prohibitively complex. For neighborhood prediction, L = n, and the graphs encountered may have millions of nodes. Hence, we need more scalable approach to training Transformers. As part of an XR- Transformer, one builds a hierarchical label clustering tree based the label features Z E R4xd, Z is based on Positive Instance Feature Aggregation
4

---

Published as a conference paper at ICLR 2022
Fin text of node
Ti-raw text of node
Cluster
ML-based
Guide
ML-based
Cluster
Cluster
matching
matching
Cluster
Cluster
Cluster
Cluster
Cluster
Recursive Machine- learned Matching.
Semantic hierarchical node clustering.
most relevant clusters recursively (fram coansetto fine).
Temporary multilabels obtain from the clustering.
Results from higher level will used in lower level.
Figure 2: Illustration of the of KR-Transformers. Step 1: Perform semantic hierarchical cluster- ing of target labels (neighborhoods) to build a tree. Step 2: At each intermediate (internal node) level of the tree, fine-tune the Transformers for the XMC sub-problem that maps raw text of nodes to label clusters. Note that the results of higher levels are used to guide the Transformers at lower levels and hence improve their performance. The resulting Transformers numerical node features from raw texts. Note that we can change the encoder (e.g., Transformer) to address other raw data formats such as images or audio signals.
used encoders that generate
(PIFA):
Z
Vi [v
where Vi =
Σ V(T),, e [L]. #yLi=
(I)
Note that for neighborhood prediction, the above expression represents exactly one step of graph convolution with node features (T.),, followed by a norm normalization; here, vi()) denotes some text vectorizer such as bag-of-words or TFIDF. In the next step, IR-Transformer uses balanced k- means recursively partition label sets and generate the hierarchical label cluster tree in a top-down fashion. This step corresponds to Step in Figure 2 Note that at each intermediate level, it learns matcher to find the most relevant clusters, illustrated in Step hierarchy defined by the cluster tree, the XR- ER-Transformer can train the model on multi-resolution objectives. Multi-resolution learning has been used in many different contexts, including com- puter vision (Lai et al.) 2017 Karras et al. 2018 2019: Pedersoli et al. 2015), meta-learning (Liu ct al. 2019a), but has only recently been applicd to the XMC problem as part of PECOS and XR- Transformers. For neighborhood prediction, multi-resolution amounts generating a hierarchy of coarse-to- views neighborhoods. The only line of work in self-supervised graph learning that somewhat resembles this approach is GraphZoom (Deng al.. 2020), in so far that it applies SSL on coarsened graphs. Nevertheless, the way in which we perform coarsening is substantially different; furthermore, GraphZoom still falls into the standard GNN pipeline category depicted in Figure
Figure By leveraging the label
THEORETICAL ANALYSIS
We also provide theoretical evidence in support of using each component of our proposed learning framework. First, we show that sulf-supe neighborhood prediction is better suited to the task hand than standard link prediction. More specifically, we show that the standard design criteria in self- culervupe link prediction tasks are biased towards graph homophily assumptions (McPher-) son et al. 2001 Klicpera al. (018). contrast, our self-supervised neighborhood prediction model works for both homophilic and heterophilic graphs. This universality property is crucial for the robustness of graph learning methods, especially in relationship to GNNs (Chien et al., 2020). Second, we for demonstrate the benefits of using PIFA embeddings and clustering in XR- IRR-ransformers numerical feature extraction. Our analysis is based on the contextual stochastic block model (cSBM) (Deshpande et al. 2018). which also used in Chien et al.) (2020) for test- ing the GPR-GNN framework and in Baranwal et al. (2021) for establishing the utility of graph convolutions for node classification.
Link versus neighborhood prediction. One standard SSL task on graphs is link prediction, which aims find an entry in the adjacency matrix according
P (Aij = 1) x Similarity (T,) (T,)))
Here, the function Similarity(x. y) is measure of similarity of two vectors, and y. The most frequently used choice for the function is the inner product of two input vectors followed by a sigmoid function. However, this type of design implicitly relies the homophily assumption:
5

---

Published as a conference paper at ICLR 2022
Nodes with similar node representations are more likely to have links. It has been shown in Pei
et al. (2020): [Chien et al.] (200); Zhu et al. (2020); Lim et al. (2021) that there are real-world
graph datasets that violate the homophily assumption and which many GNN architectures fail.
A simple example that shows how SSI. link prediction may fail is
presented in Figure D] Nodes of the same color share the same features (these are for simplicity represented as numerical values). Clearly, no matter what encoder & we have, the similarity of node features for nodes of the same color is the highest. However, there no edge between nodes of the same color, hence the standard methodology of link prediction based on homophily assumption fails to work for this simple heterophilous graph. In order to fix this issue, we use different modeling assumption, stated below.
G
4
Figure 3: A counter-example for standard link prediction methodology.
Assumption 4.1. Nodes with similar node features have similar "structural roles" in the graph. In our study, we equate "structure" with the 1-hop neighborhood of node (i.e., the row of the adjacency matrix indexed by the underlying node).
The above assumption is in alignment with our XMC problem assumptions, where nodes with a small perturbation in their raw text should be mapped to similar multi-label. Our assumption is more general then the standard homophily assumption; it is also clear that there exists a perfect map- ping from node features to their neighborhoods for the example in Figure Hence, neighborhood prediction appears to be a more suitable SSL approach than SSL link prediction for graph-guided feature extraction.
Analysis of key components in XR- RR-Transformers. In the original XR- RR-Transformer work (Zhang al. 2021a), the authors argued that one needs to perform clustering of the multi-label space in order to resolve scarce training instances in XMC. They also empirically showed that directly fine- tuning language models on extremely large output spaces is prohibitive. Furthermore, they empiri- cally established that constructing clusters based on PIFA embedding with TFIDF features gives the best performance. However, no theoretical evidence was given in support of this approach to solving the XMC problem. We next leverage recent advances in graph learning to analytically characterize the benefits of using XR- Transformers.
Description of the cSBM. Using our Assumption the case where the graph and node features are generated accord- ing cSBM (Deshpande
analyze
d²
x² Vd
N 1 d
d
N(
al. 2018) (see Figure 4 For sim- plicity, we use the most straightforward two-cluster cSBM. Let {u.)__ E {0, 1) be the labels of nodes in graph. We denote the size of class j E {0, }} by C₁ = (i: yı = Vi E [n] H. We also assume that the classes are balanced, i.e., Co C1
P P
m
The node features { E Rd are independent d-dimensional Gaussian random vectors, such that X, ~ 1. if
V: and X, N(- 2 if y1 1. The adjacency matrix of the cSBM denoted by A, and is clearly symmetric. All edges are drawn according to independent Bernoulli random variables, so that A.j ~ Ber(p) if y = y, and A.j ~ Ber(g) if y/: * Vj- Our analysis is inspired by Baranwal et al. (2021) and Li et al. (2019), albeit their definitions of graph convolutions
Figure 4: Illustration of a cSBM: Node features are independent Gaussian random vectors while edges are modeled as indepen- dent Bernoulli random variables.
and random walks differ from those in PIFA. For our subsequent analysis, we also make use of the following standard assumption and define the notion of effect size.
Assumption 4.2. p.q = w(y loga
lp-9l D-44
O(1). d o(n). 0 0< =000=0(11) O().
1p-2l and d. In contrast, we do Note that Baranwal et al. (2021) also poses constraints on p, q, p+g not require p - 0 > 0 to hold (Baranwal et al., 2021 Li et al. 2019) so that we can address graph structures that either homophilic heterophilic. Due to the difference between PIFA and standard graph convolution, we require p, to be larger compared to the corresponding values used in Baranwal et al. (202))

---

Published as a conference paper at ICLR 2022
Table 1: Basic statisties of the OGB benchmark datasets (Hu al. 2020a).
#Nodes
#Edges
Avg. Node Degree
Split ratio (%)
Metric
ogbn-arxiv ogbn- prod-rroducss
169,343 2,449.029 111,059,956
1,66,,243
13.7
54/18/28
Accuracy
61,859,144 140
50.5
8/2/90
Accuracy
ogbn-papers 100M
1,615,685,872
29.1
78/8/14
Accuracy
Definition 4.3. For cSBM, the effect size of the two centroids of the node features X of the two different classes is defined as
IEX; EX, E X; EX 12
E X, EX where ya F Yj-
In the standard definition of effect size, the mean difference is divided by the standard deviation of a class, as the latter is assumed to be the same for both classes. We use the sum of both standard deviations to prevent any ambiguity our definition. Note that for the case of isotropic Gaussian distributions, the larger the effect size the larger the separation of the two classes.
Theoretical results. We are now ready to state our main theoretical result, which asserts that effect size of centroids for PIFA embeddings Z is asymptotically larger than that obtained from the original node features. Our Theorem 4.4 provides strong evidence that using PIFA in XR- Transformers offers improved clustering results and consequently, better feature quality.
Theorem 4.4. For the cSBM and under Assumption 4.2 the effect size of the two centroids of @(1). Moreover. the effect size of the
the node features X of the two different classes is two centroids of the PIFA embedding of the two different classes, conditioned on an event of probubility least ( for some constant e 0, is w(1).
We see that although two nodes i, from the same class have the same neighborhood vectors in expectation, EA,-- = EA,, their Hamming distance can be large in practice. This finding formally characterized in Proposition 4.5
Proposition 4.5. For the cSBM and under Assumption 4.2 the Hamminng distance between A, and Aj with y; yj is w( /n log n) with probability at least - O (,,)), for some >>> 0.
Hence, directly using neighborhood vectors for self-supervision agrees with findings from the XMC literature (Chang et al.) (020b). It is also intuitively clear that averaging neighhorhood vectors from the same class can reduce the variance, which is approxi- mately performed by clustering based node representations (in case, via PIFA embedding). This result establishes the importance of clustering within the KR-Transformer approach and for the SSL neighborhood prediction task.
not advisable. Our result also
EXPERIMENTS
Evaluation Datasets. We consider node classification
downstream task and evaluate GI- ANT on three large-scale OGB datasets (Hu et al., 2020a) with available raw text: ogbn-arxiv, ogbn-products, and feghn-paperss 10pers100M.. 10M. The parameters of these datasets are given in Tableeaan de- tailed descriptions are available the Appendix E. Following the OGB benchmarking protocol, report the average test accuracy and the corresponding standard deviation by repeating runs of each downstream GNN model.
Evaluation Protocol. We refer our actual implementation as GIANT-XRT since the multi-scale neighborhood prediction task in the proposed GIANT framework is solved by an XR-Transe Transformer. In the pre-training stage, GIANT-XRT learns a raw text encoder by optimizing the self-supervised neighborhood prediction objective, and generates fine-tuned node embedding for later stages. For the node classification downstream tasks, we input the node embeddings from GIANT-XRT into several different GNN models. One is the multi-layer perceptron (MLP). which does not use graph information. Two other methods are GraphSAGE (Hamilton et al. 2017). which we applied to ogbn-arxiv, and GraphSAINT (Zeng al. 2020). which we used for egbn-produs mini-bate muni-batch training. Due to scalability issues, we used Simple Graph Convolution (SGC) (Wu et al. 2019) for ogpn-papers 00M. We also tested the state-of-the-art GNN for each dataset.
it allows for
7

---

Published as a conference paper at ICLR 2022
Table 2: Results for the obgn-arxiv and oghn- ggbn-products datasets. Mean accuracy (%) + one stan- dard deviation. Boldfaced numbers indicate the best performances of downstream models, while underlined numbers indicate the best performance of models with a standard GNN pipeline for downstream models using Xplain and XSSLGNN- Methods under XGIANT (GIANT framework) part of the ablation study.
Datasct
ogbn-arxiv
ogba-products
ML.
GripSAGGE
ReuGAT
RevGAT+SalrKD
MI.P
GraphSINT
SLG
OGB-feat BERT"
58.50 0.23
71.49 + 0.27
74.02 0.18
0.12
61.06
79.08 + 0.24
84.28 0.11
X Xlais
62.91 = 0.60
70.97 = 0.33
73.59 0.10
73.55 0,44
60.90 1.09
79.55 0.85
8311
OGB-feat+GZ
70.95 0.38
71.41 0.09
72.42 0,
72.50 0.08
0.555
0.21 78.38
79.78 0.11
BERT +GZ
70.46 0.21
0.19
0.006
7..30
00M
00M
0OM
DGB-teat+DGI
56.02 0.16
73.48 0.27
0.144
0.29
70,54 0.13
0.16
81.59 0.14
BERT +DGI
59.42 0.38
73.24 0.01
73.60 0.21
73.62 0.23
81.29
0.41
82.90 0.21
SSLON
OGB-feat GAB
56.47
73.70 7.200
74.06 0.10
7
78.23
82.85
0.11
BERT* +GAE
62.11 0.32
0.17
74.26
0.20
74.48 a 0.15
78.42
62.74
84.42 = 0.04
OGB-feat+
56.70 0.20
73.59 0.29
0.17
73.95 0.09
74.66
78.65 + 0.20
83.06 0.06
BERT* -VGE
62.48 0.14
0.02
74.21 0.00
74.44 0.09
82.80 0.225
0.11
84.40 0.09
BERT+IP
67.33 0.54
2.86
75.50 0.11
0.04
73.83 + 0.06
81 0.08
XGIANTT
NO TRIDF+ NO PIFA
69.33 = 0.19
0,34
74.95
0.07
75.16 0.06
80.70 74.16
0.51
81.63 0.28
NO TRIDF-PIAA
72.74 0.17
74.43 0.20
75.88
0.05
76.06 0.02
78.91 0.228
81.54 + 0.14
82.22 + 0.15
TFI PIFA
71.74 0.15
74.09
# 0.33
75.56
+ 0.09
75.85 + 0.05
79.37
83.83 # 0.14
85.01 = 0.10
GIANT-XRT
73.08 0.06
75.96 = 0.09
76.12 0.16
79.82 0.07
85.47 8.14
At the time we conducted the main experiments (07/01/2021), the top-ranked model for ogbn-arxiv was RevGAT (Li et al. 2021) and the top-ranked model for ogbn-products was SAGN (Sun & Wu 2021). When we conducted the experiment on ogbn-papers 1anss10000 100M (09/10/2021), the top- ranked model for ogbn-papers 100M 100M was GAMLI (Zhang et al. 2021b) (Since then, the highest reported accuracy was improved by 0.05% for ogbn-arxiv and 0.31% for ogbn-products; both of these improvements fall short compared publicly available implementations of the GNNs. For RevGAT, we report the performance of the model with and without self knowledge distillation; the former setting is henceforth referred as +SelfKD. For SAGN, we report results with the self-lebelennhanced (SLE) feature, and denote them by SAGN+SLE. For GAMLP, we report results with and without Reliable Label Utilization (RLU); the former is denoted as GAMLP+RLU.
those offered by GIANT). For all evaluations, we use
SSL GNN Competing Methods. We compare GIANT-XRT to methods that rely on graph- agnostic feature inputs and use node embeddings generated by various SSL GNNs modules. The graph-agnostic features are either default features available from the OGB datasets (denoted by OGB-feat) or obtained from plain BERT embeddings (without fine-tuning) generated from raw text (denoted by BERT*). For OGB-feat combined with downstream GNN methods, we report the re- sults from the OGB leaderboard (and denote them by f). For the SSL GNNs modules, we test three frequently-used methods: (Variantional) Graph A AutoEncoders (Kipf & Welling, 2016) (denoted by (V)GAE); Deep Graph Infomax (Velickovic et al. 2019) (denoted by DGI); and GraphZoom (Deng) ct al. 2020 (denoted by GZ). The hyper-parameters of SSL GNNs modules are given in the Ap- pendix For all reported results, we use Xplann XSSLONN and XGIANT (c.f. Figure T to denote which framework the method belongs to. Note that XCIANT refers to our approach. The implemen- tation details and hyper- paremmerrsssesss of GIANT-XRT can be founded in the Appendix E.3
5.1
MAIN RESULTS
The results for the ogbn-arxiv and ogbn-products datasets are listed in Table Our GIANT-XRT ap- proach gives the best results for both datasets and all downstream models. It improves the accuracy of the tap-ranked OGB leaderboard models by a large margin: 1.86% on ogbn-arxiv and 1.19% on ogbn-producte Using graph-agnostic BERT embeddings does not necessarily lead to good results (see the first two rows in Table 2. This shows that the improvement of our method is not merely
eff/ /fE/ogon/oo arxiv dgl
Sittssswwwtt____t SL.
https://giithbb..co////k-i-
8

---

Published as a conference paper at ICLR 2022
Table 3: Results for the obgn-papert 100 dataset. Mean accuracy (%) + one standard deviation. Boldfaced values indicate the best performance amongst the tested downstream models.
Sgbn-papers100M.
MLP
SGC
GAMLP
GAMLP+RLU
OGB-feat'
47.24 = 0.31 63.29 0.19 67.71 + 0.20
68.25 : 0.19
plain
BERT*
47.24 = 0.39 61.69 + 0.29 66.25 + 0.05
67.15 2 0.07
XGIANT
GIR
61.10 = 0.19 66.10 + 0.13 69.16 + 0.08 69.67 = 0.04
due to the use of a more powerful language model, and establishes the need for self-supervision governed by graph information. Another observation is that among possible combinations involving a standard GNN pipeline with a SSL module, BERT+(V)GAE offers the best performance. This can be attributed to exploiting the correlation between numerical node features and the graph structure, albeit in a two-stage approach within the standard GNN pipeline. The most important finding is that using node features generated by GIANT-XRT leads to consistent and sigmificant improvement in the accuracy of all tested methods, when compared to the standard GNN pipeline: In particular, on ogbn-arxiv, the improvement equals 17.58% for MLP and 1% for GraphSAGE, on oghn- products, the improvement equals 18. 76% for MLP and 5.32% for GraphSAINTI Figure 5 in the Appendix further illustrate the gain obtained by our GIANT-XRT over SOTA methods on OGB leaderboard.
Another important observation is that GIANT-XRT is highly scalable, which can be clearly ob- served on the example of the ogbn-papers Carapeers00M0 100M dataset, for which the results are shown in Table In particular, GIANT-XRT improves the accuracy of the top-ranked model, GAMLP-RLU, by margin of 1.42%. Furthermore. GIANT-XRT again consistently improves all tested downstream methods on the ogbn-papers 100M dataset. As final remark, we surprisingly find that combining MLP with GIANT-XRT greatly improves the performance of the former learner on all datasets. becomes just slightly worse then GIANT-XRT-GNNs and can even outperform the GraphSAGE and GraphS methods with default OGB features on ogbn-arxiv and ogbn-products datasets. This is yet another positive property of GIANT, since MLPs are low-complexity and more easily implementable than other GNNs.
5.2
ABLATION STUDY
We also conduct an ablation study of the GIANT framework to determine the relevance of each module involved. The first step is to consider alternatives to the proposed multi-scale neighborhood prediction task: In this case, we fine-tune BERT with a SSL link prediction approach, which we for simplicity refer to as BERT+LP. In addition, we examine how the PIFA embedding affects the performance of GIANT-XRT and how more informative node features (TFIDF) can improve the clustering steps. First, recall that in GIANT-XRT, we use TFIDF features from raw text to con- struct PIFA embeddings. We subsequently use the term "NO TFIDF" to indicate that we replaced the TFIDF feature matrix by identity matrix, which contain no raw text information. The term "TFIDF+NO PIFA" is used to refer to the setting where only raw text information (node attributes) used to perform hierarchical clustering. Similarly, "NO THIDF+PIFA" indicates that we only use normalized neighborhood vectors (graph structure) to construct the hierarchical clustering. If both node attributes and graph structure are ignore, the result is a random clustering. Nevertheless, we keep the same sizes of clusters at each level in the hicrarchical clustering.
The results of the ablation study are listed under rows indexed by XGIANT in Table 2 for ogbn-arxiv and ogondprosucts datasets. They once again confirm that GIANT-XRT consistently outperforms other tested methods. For BERT+LP, we find that it has better performance on ogbn-arixv compared to that of the standard GNN pipeline but a worse performance on ogbn- products. This shows that us- ing link prediction to fine-tune BERT in sulf-supe manner is not robust general, and further strengthens the case for using neighborhood instead of link prediction. With respect to the ablation study of GIANT-XRT, we see that NO TNIDF+NO PIFA indeed gives the worst results. Using node attributes (TFIDF features) or graph information (PIFA) to construct the hierarchical clustering in GIANT-XRT leads to performance improvements that can be seen from Table 2 Nevertheless, com- bining both as done in GIANT-XRT gives the best results. Moreover, PIFA always gives better results compared to the case when PIFA is not used. It aligns with our theoretical analysis, which shows that PIFA embeddings lead to better hierarchical clusterings.
can observe that using

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
The authors thank the support from Amazon and the Amazon Post Internship Fellowship. Cho-Jui Hsieh is partially supported by NSF under IIS-200817, 173 and I1S-2048280. This work was funded in part by the NSF grant 1956384.
ETHICS STATEMENT
We are not aware of any potential ethical issues regarding our work.
7 REPRODUCIBILITY STATEMENT
We provide our code in the supplementary material along with an easy-to-follow description and package dependency for reproducibility. Our experimental setting is stated Section and de- tails pertaining to hyperparameters and computational environment are described in the Appendix. tested methods are integrated our code: httpp::/ /gtps////ithbb... com/ amzn/pecos/tred ma in line//e////e examp Seseppllllseee iiggg-xatitt
REFERENCES
Tavor Z Baharav, Daniel Jiang, Kedarnath Kolluri, Sujay Sanghavi, and Inderjit Dhillon. En- abling efficiecyy-prcciiin trade-offss for label trees in extreme classification. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3717 2021.
Vassilcios Balntas, Edgar Riba, Daniel Ponsa, and Krystian Mikolajezyk. Learning local feature descriptors with triplets and shallow convolutional neural networks. In The British Machine Vision Conference (BMVC), volume pp. 3, 2016.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In International conference on machine learning, 2021.
Wei-Cheng Chang, Felix X. Yu, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar. Pre-training tasks for emhedding- based large-scale retrieval. In International Conference on Learning Repre- sentations, 2020a.
Wei-Cheng Chang, Hsiang-Fu Yu, Kai Zhong, Yiming Yang, and Inderjit $ Dhillon. Taming pre- trained transformers for extreme multi-label text classification. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3163-3171, 2020b.
Wei-Cheng Chang, Daniel Jiang, Hsiang-Fu Yu, Choon-Hui Teo, Jiong Zhang, Kai Zhong, Kedar- nath Kolluri, Qie Hu, Nikhil Shandilya, Vyacheslav levgrafov, Japinder Singh, and Inderjit Dhillon. Extreme multi-label learning for semantic matching in product search. In Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2021.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2020.
C Deng. Z Zhao, Y Wang, Z Zhang, and Z Feng. Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding. International Conference on Learning Representa- fions, 2020.
10

---

Published as a conference paper at ICLR 2022
Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. In Advances in Neural Information Processing Systems, 2018.
Jacob Devlin, Ming-War Beng-Wei&o Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. (0.18653/v1/N19111 14-13199-442.... URL https:
7/aclant
Philip A Etter, Kai Zhong, Hsiang-Fu Yu, Lexing Ying, and Inderjit Dhillon. Accelerating inference for sparse extreme multi-label ranking trees. In Proceedings of the Web Conference 2022, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self- supervised visual representation learning. In Proceedings of the IEEE/CVF International Confer- ence on Computer Vision, pp. 6391-6400, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024- 1034, 2017.
Xiangnan He. Ming Gao. Min- Yen Kan, and Dingxian Wang. BiRank: Towards ranking on bipartite graphs. IEEE Transactions on Knowledge and Data Engineering. (91))777-7,, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pp. 409-426. Springer, 1994.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 22118-22133, Curran Asso- ciates, Inc., 2020a. URL Eb60d41 225000002S8670222227002202202220
pdf
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020b. URL htttp::/ net/ htt.r/ummmme//oo forum?id-
HJ HJIWKJSFDH
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun. GPT-GNN: Generative pre-training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1857-1867, 2020c.
Lianzhe Huang, Dehong Ma, Sujian Li, Xiaodong Zhang, and Houfeng Wang. Text level graph neural network for text classification. In Conference on Empirical Methods in Natural Language Processing (EMNLP). 2019.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Confer- ence on Learning Representations, 2021. URL httpt: fttte::://opereviiie net net/forummid
8E1 f3VhX1o
Ting Jiang, Deqing Wang. Leilei Sun, Huayi Yang, Zhengyang Zhao, and Fuzhen Zhuang. Lig Transformer with dynamic negative sampling for high-performance extreme multi- label text classification. Thirty-Fifih AAAI Conference on Artificial Intelligence (AAAI), 2021.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for im- proved quality, stability, and variation. In International Conference on Learning Representations, 2018.
11

---

Published as a conference paper at ICLR 2022
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4401-4410, 2019.
Thomas N Kipf and Max Welling. 1oXiv:161.00700 2016.
Variational
graph auto-encoders.
arXiv preprint
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual repre- sentation learning. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 1920-1929 1929, 2019.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. FLAG: Adversarial data augmentation for graph neural networks. arXiv preprint arXiv:2010.0989/ 2020.
Wei-Sheng Lai, Jia-Bin Huang, Narendra Ahuja, and Ming-Hsuan Yang. Deep Laplacian pyra- mid networks for fast and accurate super-resolutio. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Kenton Lee, Ming-Wei Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisties. pp. 1186-6096, 2019.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference machine learning. 2021.
Pan Li, Chien, and Olgica Milenkovic. Optimizing generalized pagerank methods for seed- expansion community detection. In Advances in Neural Information Processing Systems, vol- ume 32, pp. 11710-11721 2019.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. arXiv preprint 104.01444 2021.
Shikun Liu, Andrew Davison, and Edward Johns. Self-Supervised generalisation with meta aux- iliary learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett (.ds),, Advances in Neural Information Processing Systems, volume 32, Curran Asso- ciates, Inc., 2019a. URL httppsss/pppccce..gs....t new.eeipsdinn...nns............ httplpps..cppppppepee wc/ppaper/211///ieeee.
pdf
Xien Liu, Xinxin You, Xiao Zhang, Ji Wu, and Ping Lv. Tensor graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1409-84166 2020.
Xuanqing Liu, Wei-Cheng Chang, Hsiang-Fu Yu, Cho-Jui Hsieh, and Inderjit S Dhillon. Label disentanglement in partition-base extreme multilabel classification. arXiv preprint arXiv:2106. 12751, 2021.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1692, 2019b.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey, Physica A: statistical mechanics and its applications, 390(6): 150-1170, 2011.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-44 2001.
12

---

Published as a conference paper at ICLR 2022
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp- 3111-3119, 2013.
Marco Pedersoli, Andrea Vedaldi, Jordi Gonzalez, and Xavier Roca. A coarse-to- tossee-to-fine approach for fast deformable object detection. Pattern Recognition, 48(5):1844-188 2015.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Lei, and Bo Yang. Geom-GCN: Geo- metric graph convolutional networks. In International Conference Learning Representattonss 2020.
Yashoteja Prabhu and Manik Varma. FastXML: A fast, accurate and stable tree-classifier for treme multi-label learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 263-2722222 2014.
Yashoteja Prabhu, Anil Kag, Shrutendra Harsola, Rahul Agrawal, and Manik Varma. Parabel: Par- titioned label trees for extreme classification with application to dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference, pp. 993-1002, 2018.
Rajat Sen, Alexander Rakhlin, Lexing Ying, Rahul Kidambi, Dean Foster, Daniel Hill, and Inder- jit Dhillon. Top-k extreme contextual bandits with arm bierarchy. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9433.9433. PMLR, 18-24 Jul 2021. URL URL
htt.sigss.......eess//////s/ss/ htmml
Yanyao Shen, Hsiang-fu Yu, Sujay Sanghavi, and Inderjit Dhillon. Extreme multi-label classifica- tion from aggregated labels. In International Conference on Machine Learning, pp. 9752-8762. PMLR, 2020.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):2539- 2561, 2011.
Chuxiong Sun and Guoshi Wu. Scalable and adaptive graph neural networks with self-label- enhanced training. arXiv preprint arXiv:2104.09376, 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lia, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018. URL
net/ rett:forrmmnd==rr0p)))0
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, volume 2, pp. 4, 2019.
Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396- 413, 2020.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- PMLR, 2019.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. arXiv preprint arXiv:2102.1077. 10757, 2021.
Nishant Yaday, Rajat Sen, Daniel N Hill, Arya Mazumdar, and Inderjit Dhillon. Session-aware query auto-completion using extreme multi-label ranking. In Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2021.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2022
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI conference on artificial intelligence, pp. 7370-7377, 2019.
Hui Ye, Zhiyu Chen, Da-Han Wang, and Brian Davison. Pretrained generalized autoregressive model with adaptive probabilistic label clusters for extreme multi-label text classification. In International Conference on Machine Learning, pp. 10809-10819, PMLR, 2020.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovee. GraphRNN: Generat- ing realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708-5717. PMLR, 2018.
Ronghui You, Zihan Zhang, Ziye Wang. Suyang Dai, Hiroshi Mamitsuka, and Shanfeng Zhu. At- tentionXML: Label tree-based attention-aware deep model for high-performance extreme multi- label text classification. In Advances in Neural Information Processing Systems, volume 32, pp- 5820-5830, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances Neural Information Processing Systems, volume 33, pp. 2812-5823, 2020.
Hsiang-Fu Yu, Kai Zhong. Jiong Zhang, Wei-Cheng Chang, and Inderjit S Dhillon. PECOS: Pre- diction for enormous and correlated output spaces. Journal of Machine Learning Research, 2022.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference Learn- ing Representations, 2020. URL https: //pp///iiee/eiiiee///m/emee net weeperummid-BBeeeeee
Haopeng Zhang and Jiawei Zhang. Text graph transformer for document classification. In Confer-
ence on Empirical Methods in Natural Language Processing (EMNLP). 2020.
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Sun. Graph-Bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.051400 2020.
Jiong Zhang, Wei-Cheng Chang, Hsiang-Fu Yu, and Inderjit Dhillon. Fast multi-resolution trans- former fine-tuning for extreme multi-label text classification. In Advances in Neural Information Processing Systems, 2021a.
Wentao Zhang, Ziqi Yin, Zeang Sheng, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. arXiv preprint arXiv:2 10097, 2021b.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, volume 33, 2020.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of Misconsin-Madison Department of Computer Sciences, 2005.
14

---

Published as a conference paper at ICLR 2022
APPENDIX
A CONCLUSIONS
We introduced novel self-supervised learning framework for graph-guided numerical node feature extraction from raw data, and evaluated it within multiple GNN pipelines. Our method, termed GIANT, for the first time successfully resolved the issue of graph-agnostic numerical feature extrac- tion. We also described a new SSL task, neighborhood prediction, established connection between the task and the XMC problem, and solved it using XR- Transfssforers. We also examined the the- oretical properties of GIANT in order to evaluate the advantages of neighborhood prediction over standard link prediction, and to assess the benefits of using XR- Transformers. Our extensive numer- ical experiments, which showed that GIANT consistently improves state-of-the-arr GNN models, were supplemented with an ablation study that aligns with our theoretical analysis.
B PROOF OF THEOREM 4.4
Throughout the proof, we use μ = ș to denote the mean of node feature from class and v = #1 for class 1. We choose keep this notation to demonstrate that our setting on mean be easily generalized. The choice of the high probability events will be clear in the proof.
The proof for the effect size of centroid for node feature X is quite straightforward from the Defini- tion 4.3 By directly plugging in the mean and standard deviation, we have
2r
(
20
The last equality is due to our assumption that both r, a > O are both constants.
To prove the effect size of centroid for PIFA embedding Z. we need first introduce some standard concentration results for sum of Bernoulli and Gaussian random variables.
Lemma B.1 (Hoeffiding's s inequality (Hoffdding 1994)). Let Sn = =Ei= Xn, where X are i...d Bernoulli random variable with parameter p. Then for any >> have
-212
IP (IS,. - mpl
2exp(
Lemma B.2 (Concentration of sum of Gaussian). Let Sn random variable with zero mean and standard deviation a. Then for some constant e <>> 0, we have
Ei= Xuo where X; are i.i.d. Gaussian
2²
P (1sa) 2 ca v n logm) S 22exp(
log n).
(6)
Now we are ready to prove our claim. Recall that the definition of PIFA embedding Z as follows:
Z
Vi where V; =
Σ X, = [AX] j:A.=1
v
We first focus analyzing the vector v.. We denote N. Kj yı リy A.j j [n]) and
N = No + N₁. Without loss of generality, we assume = 0. The conditional expectation of is
as follows:
E [v
Naj + NAv.
(8)
Next, by leveraging Lemma
B.I
we have
nq
4t2
P(NNa
2 t) < exp(
(9)
2
n
By choosing & = C1 / log n. for some constant
> 1, we know that with probability at least ng + ci / m)) Finally, by our Assumption 4.2 we know
n... that nq = w(1 ((/nnl logn). Thus, we arrive to the conclusion that with probability at least 1 0 mp Na ng + o1).
1- 1-0( (
), No1 E 2
ng
Ci ciyn logn, 2
15

---

Published as a conference paper at ICLR 2022
Following the same analysis, we can prove that with probability at least 1-0
x² Noo 2 = ). random variables in this case as there's 's no self-loop. Nevertheless, (3 - 1) $ (11 o(1) so the result is the same. Note that need to apply union bound over 2n error events (vi E [n]] and 2 cases for No and Nú respectively). Together we know that the emor probability is upper bounded by O( (2=²²) ) for some new constant C2 = c1 1 0. Hence, we characterize the mean of v, on a high probability event B1
The only difference is that we are dealing with
Next we need to analyze its norm. By direct analysis and condition on A, we have
Σ (o + D + Gj))
(10)
Amm
where Gyæ are i..d. Gaussian random variables with zero mean, standard deviation and _ stands for equal in distribution. Then by Lemma B.2 we know that with probability at least 1 0( x
for some constant C3 > 2 + 02
Σ Gr - 0 0
N N.).
(1I)
Vd
This is because condition on A, we are summing over N; Gaussian random variables. Recall that condition on our high probability event B1. N₁. = [p + (1 + o(1) = w(Vn S n. Thus,
we know that for some 02 > 0, with probability at least 1 - 0 n ) = O パل we have
|Σ= Gykl O va log Again, recall that both No, Nu w(yn log n)), thus together
we have
n²
| 1
(pap- 2wg)
(12)
d
+
*||ug||
= n
Σ [meo+ +x))+
(13)
2
n
2 1p g]r(1 + +
(14)
Again, we need to apply union bound over nd error events, which result in the error probability
O since C3 + 02 and d o(n) in our Assumption 4.2 We denote the corresponding high
probability event to be Bz. Note that the same analysis can be applied to the case the result for the norm is the same and the result for e would be just swapping p and q. Combine
1, where
all the current result, we know that with probability at least 1 - 0( (1) for some 02 >> 0, the PIFA embedding Z, equals to the following
z: = (up + vz) + o(1)) (11p + v1) + o(1)
if y/ = 0.
(15)
-l=-g)r(++o(1)
p q/r
up) + glr((++((()))
(nq up) + o(1)
Z, -
y 1.
(16)
p qr
Hence, the centroid distance would be
(1(p - q) + -(g (())
(17)
r/p rlp-q
(n - v)(p - () +0(1)
(18)
r|p - [1
vil (1+ (1+ o(1) = 2(1+)(1))
(19)
Now we turn to the standard deviation part. Specifically, we will characterize the following quantity (again, recall that we assume y; = 0 w.l.o.g..)
(up + vg)
2
(20)
rpp ql
16

---

Published as a conference paper at ICLR 2022
Recall that the latter part is the centroid for nodes with label 0. Hence, by characterize this quantity we can understand the deviation of PIFA embedding around its centroid. From the analysis above, know that given A, we have
(up mg)
Noo + NEw
(up + kg) rlp gl
Σラ A Pelll
24
+
(21)
p ql
For the terms ||ull No Nu and Σー= MzZZ above. Plug in those results, the first term becomes
we already derive their concentration results
Nap + NA
(oeP + vg)
(22)
||//1
rip q
2 (1p(1 + o(1) + vg(1 o())
(up + vq)
||
(23)
Frlp 91(1 o
rlp - gl
(ppo(11 +1q(1)))
r|p 9 + ((]) 1|= - r/p -1p-9/8 gl
r1p- 9|(1 + o(1)) d(1)
(24)
The second term becomes
EJ= A.G G
O n2 log n
(25)
|uu|l
Frlp g + (1))
/nlgoo ((),
(26)
where the last equality is from our Assumption 4.2 that r. are constants. Together we show that
the deviation of nodes from their centroid is of scale o(1). The similar result holds for the case y: 1. Together we have shown that the standard deviation of Z; is o(1) on the high probability
event B, n Bg. Hence, the effect size for the PIFA embedding is w(1) with probability at least
1- 0 (+/))) for some constant C2 > O, which implics that PIFA embedding gives a better clustered node representation. Thus, it is preferable to use PIFA embedding and we complete the proof.
C PROOF OF PROPOSITION 4.5
the Hamming distance of A,, A, for y/ = yj is a boisson-Binomiaa random variable. More precisely, note that
Note that under the setting of cSBM and the Assumption 4.2
Vk [n]] {i.j} s.t.y. = Mis A Ajal ~ Ber(2p(1 (1))) Vk E [n] {i.}} s.t.yk # ye where they are all independent. Hence, we have
(27)
A Ayal ~ Ber(2q(1 - -)))
(28)
Hamming A, A,) ~ Binl n
2 2, 2p(1 p)) + Binl n 2q -)),
(29)
2
where Hamming (A, Aj) denotes the Hamming distance of A,, A, and Bin(a, b) stands for the Bi- nomial random variable with a trials and the success probability is b. By leveraging the Lemma know that for random variable X Bin ( 21(1 4)), have
4t )
P (IX ng(1 - 4) 2 t) < 2 exp(
(30)
Note that the function q(1 - g) is monotonic increasing for 9 E [0, 11 and has maximum at y 2-
Combine with Assumption 4.2 we know that rgg(1 v) = w6 /n log n). Hence, by choosing / = have
Ven log for some constant c 0, with probability at least 0(
logn w( / n log n)
X ng(1 -q) 9)
(31)
Finally, by noting the fact that with probability 1 we have Bin( 2, 21 - p)) 2 0. Hence, by showing X ~ Bin( 2g(1-g) is of order w(Vn log n) with probability at least 1 (-- implies that the Hamming distance of A,, A, is of order w( log with at least the same probability. Together complete the proof.
17

---

Published as a conference paper at ICLR 2022
D PROOF OF LEMMA B.2
By Chernoff bound, we have
P (S, 2 a) S min taineee(tta)eexppppp
(32)
1>0
By the i.d assumption, we have
min exp(-ta))eex((ss.) = min exp(-ta) (epptt) t20
(33)
E>0
Note that the moment generating function (MGF) of zero-mean, standard deviation Gaussian random variable is exp( o²t Hence we have
min exp( (B (Eexp(tX;))) min exp( ( ta). 1>0
(34)
t>0
By minimizing the upper bound with respect I, choose 1 nor. Plug in this choice of t we have
P (S, 2 a) S exp(
(35)
2no
Finally, by choosing c/ / log for some and the union bound, we complete the proof.
0, applying the same bound for the other side
E EXPERIMENTAL DETAIL
E. DATASETS
In this work, we choose node classification our downstream task focus. We conduct experi- ments on three large-scale datasets, ogbn-arxiv, ogbn-products and ogbn-papers 100M as these are the only three datasets with raw text available in OGB. Ogbn-arxiv and ogbn-papers 100M (Wang et al. 2020 Hu et al. 2020a) are citation networks where each node represents paper. The corre- sponding input raw text consists titles and abstracts and the node labels are the primary categories of the papers. Ogbn-product (Chiang et al. 2019; Hu et al.) 2020a) is an Amazon co-purchase network where each node represents a product. The corresponding input raw text consists of titles and descriptions of products. The node labels are categories of products.
E.2 PARAMEERS SSL GNN MODULES
The implementation of (V)GAE and DGI are taken from Pytorch Geometric Library (Fey & Lenssen 2019). Note that due the GPU memory constraint, adopt GraphSAINT (Zeng al., 2020) to (V)GAE and DGI for ogbn-products GraphZoom directly taken from the official repos- itory For all downstream GNNs in the experiment, we average the results over three independent runs. The only exception is OGB-feat downstream GNNs, where we directly take the results from OGB leaderboard. Note that we also try to repeat the experiment of OGB-feat downstream GNNs, where the accuracy is similar to the one reported on the leaderboard. To prevent confusion we decide to take the results from OGB leaderboard for comparison. For the BERT model used throughout the paper, we use thert-base-uncasede downloaded from FinggiggFace 6 For the methods used in the SSI. GNNs module, we try our best to follow the default setting. We slightly optimize some hy- perparameters (such learning rate, epochs...etc) to ensure the training process converge. To ensure the fair comparison, we fix the output dimension for all SSL GNNs as 768 which is the same bert-base-uncased and IR-Transformer.
E.3 SYPER-PARAMETERS GIANT-XRT AND BERT+LP
Pre-training of GIANT-XRT. In Table we outline the pre-training hyper-parameter of GIANT-XRT for all three OGB benchmark datasets. We mostly follow the convention of XR- Transformer (Zhang et al. 202 to set the hyper-parameters. For ogbn-arxiv and ogbn-products
https://qithub.cr how.ttttwbooooooceooooommmoo corne http://///.omm1111aaaaaa/aaaapa/
https://hugginggfae wwt.eo//ttte.e....
18

---

Published as a conference paper at ICLR 2022
datasets, use the full graph adjacency matrix the XMC instance-to-label matrix Y {0, (0,1)=xm, where n is number of nodes in the graph. For agbn-papers100M, we sub-sample 50M (out of 111M) most important nodes based on page rank scores of the bipartite graph (He et al. 2016). The resulting XMC instance-to-label matrix has 50.0M of rows, 49.9M of columns, and 2.5B of edges. The PIFA node embedding for hierarchical clustering is constructed by aggregating its neighborhood nodes' TF-IDF features. Specifically, the PIFA node embedding is a 4.2M high- dimensional sparse vector, consisting of IM of word unigram, 3M of word bigram, and 200K of character triagram. Finally, for ogbn-arxiv and ogbn-proe products, we use TF N AN negative sam- pling to pre-train XR-Transfommer where the model-awar negatives (MAN) are selected from top 20 model's predictions. Because of the extreme scale of ogbn-papent 100M, we consider 7 TFN only to avoid excessive CPU memory consumption on GPU machine.
ogbn-products,
Table 4: Hyper-parametern GIANT-XRT. HLT defines the structures the hierarchical label trees. Irmoz is the maximum learning rate in pre-training. Rstep is the number of optimization steps for each layer of HLT, respectively. B is total number of batch size when using Nvidia V V100 GPUs. NS is the negative sampling strategy in XR- AR-Transformer. D is the Dth layer of H LT where take the Transformer encoder to generate node embeddings as input for downstream GNN models.
Dataset
HLT
Ir muz
Rsteep
B
NS D
ogbn-arxiv
32-128-512-2044 004-512-2048-8192--227
6 10
2,000
256
TFN+MAN
4
oghn-products
6
10,000
256
TFN+MAN
2
ogbn-papers 100M
128-2048-32768
6 x 10
100,000
512
TFN
3
Pre-training on BERT+LP. To verify the effectiveness multi-scale neighborhood prediction loss, consider learning a Siamese BERT encoder with the alternative Link Prediction loss for pre- training, hence the name BERT+LP. We implement BERT+LP baseline with the triplet loss (Baintas) al., 2016)
empirically observed has better performance than other loss functions for the link prediction task. We sample one positive pair and one negative pair for each node as training samples for each epoch, and train the model until the loss is converged.
E.4 HYPEERPPRRMMTTES OF DOWNSTREAM METHODS
For the downstream models, optimize the learning rate within {0.01, 0.001 for all models. For MLP, GraphSAGE and GIaphSAINT, we optimize the number of layers within 31. For RevGAT, keep the hyperparameter choice the same default. For SAGN, also optimize the number of layers within {1, 3). For GAMLP, we directly adopt the setting from the official implementation. Note that all hyperparameter tuning applies for all pre-trained node features (Xplain- XSSLGNN and XGIANT).
E.5 COMPUTATIONAL ENVIRONMENT
All experiments are conducted on the AWS p3dn.24xlarge instance, consisting of 96 Intel Xeon CPUs with 768 GB of RAM and 8 Nvidia V100 GPUs with 32 GB of memory each.
E.6 ILLUSTRATION ON THE IMPROVEMENT OF GIANT-XRT
See Figure
19

---

Published as a conference paper at ICLR 2022
TOP8 GNNs on ogbn-arxiv (Nov 11, 2021)
GIANT-XRT-ReVGAT-KKO
GIANT-XRT+ReWGAT
AGDN--BTT+ali-K44005
ACDN+BoT+seff-O
RevGAT Rev.CATTH.AALLLaaRRBBeee---SK
GAT-node2vec self-KD
GAT-label seu
AGDN+BoT
0.73
0.77
Average Test Accuracy
TOP8 GNNs on ogbn-products (Nov 11, 2021)
SIANTAART-SACN-SLE-OOSSS
GIANT-XRT-SAGN-SE
SAGN+SLE (4 Stages)+C&S
SAGN-SLE (4 stages)
GAMLP+RLU
Spec-MLP-Wer + CaS
SAG
0.80
0.81
0.82
0.83
0.84
0.85
0.86
0.87
0.88
Average Test Accuracy
TOP8 GNNs on ogbn-papers100M
(Nov 11, 2021)
GIANT-XRTTGAMMPPRUU
GIANT-XRT+GAMLP
SAGN+SLE (4 stages)
GAMLP+RLU
FSGNN
SAGN+SLE
GAMLP
TraneformerConv
0.85
0.86
0.67
0.68
0.69
0.70
Average Test Accuracy
Figure 5: To further demonstrate that our GIANT-XRT indeed achieves a significant improvement over -tate-of-the-art methods, we plot the performance of top 8 models on OGB leaderboard (As of Nov. 11th, 2021). Note that our results on ogbn-product, is better than those reported in Table 2 since we adopt the latest choice of hyperparameters provided in SAGN GitHub repository.
20


Reviews:
[{"review_id": "sfdKeeX8hE-", "reviewer": "Reviewer_ZAh6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The proposed method is simple and reasonable. The experimental studies are extensive.\n\nWeaknesses:\n\n(1) The novelty is limited. In my view, masked language modeling aims to predict the masked tokens given the context, and in this paper, neighborhood prediction aims to predict the relation given the context. Relation-prediction-based objectives have been widely applied in knowledge/entity oriented pre-training, such as K-ADAPTER (Wang et al.),  ERICA (Qin et al.). In addition, the impact of the proposed method could be rather minor given their experimental results. For example, in Table 1, on the ogbn-arxiv dataset, based on GIANT-XRT, GraphSAGE, RevGAT, and RevGAT+SelfKD gain accuracies of 74.59%, 75.96%, and 76.12%, respectively, and based on TFIDF+NO PIFA, gain accuracies of 74.09%, 75.56%, and 75.85%. With such small gaps, it would be important to know whether the difference is actually statistically significant.\n\n(2) Some details in Figure 1 are not clear, e.g., denotations of A and Y, full terms of XMC. To make Figure 1 self-contained, the caption of the figure should provide more necessary information.\n\n(3) The idea are verified on three node classification datasets, while some details are missing. “Split ratio”in Table 1 is confusing, I cannot figure out what the ratios for train/test/development are. How many classes for each dataset? It would be better to show some real instances.\n\n(4) What is the dataset used for pre-training GIANT?\n", "summary_of_the_paper": "This paper presents a new self-supervised learning framework to enhance language model based on graph information. ", "summary_of_the_review": "The novelty is limited, and the impact of the proposed method could be rather minor. Some necessary details should be provided.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hGnTnRmS878", "reviewer": "Reviewer_3rZe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The problem is well motivated.\n2. The proposed framework could be useful in general.\n3. Both theoretical analysis and experiments are convincing.\n\nWeaknesses:\n1. the efficiency is not supported with experiments.\n2. There are some typos.\n", "summary_of_the_paper": "This paper develops a self-supervised learning framework to extract node features with the aid of graph. Connections between neighborhood prediction and the XMC problem are also established. Experiments on large-scale data show the superiority of the proposed method.", "summary_of_the_review": "This paper develops a self-supervised learning framework to extract node features supervised graph. It is an interesting problem. Theoretical analysis is also provided. Extensive experiments on large-scale data validated the effectiveness of the proposed method.\nThere are some typos, e.g., \"These have to be predicted using the textual information in order to best match the a priori given graph topology. This is achieved this by using the state-of-the-art XR-Transformer (Zhang et al., 2021a) method for\nsolving the XMC problem.\"", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fYnqFVIFM24", "reviewer": "Reviewer_grtb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths:\n+ Introducing the idea of neighborhood prediction to guide self-supervised node feature learning is interesting and somewhat novel.\n+ Connecting neighborhood prediction with the XMC problem is novel.\n+ Extensive experiments are conducted on OGB and show new state-of-the-art results.\n\n\nWeaknesses: \n- The reviewer has some concerns on the provided theoretical analysis based on cSBM (Deshpande et al., 2018). It seems misleading and incomplete. \n\nThe theoretical analysis could be deduced from the analysis in Baranwal et al. (2021) with a few changes. In Baranwal et al. (2021), the cSBM is used to analysis the effect of graph convolution operation on the linear separability. The established theoretical results show that: if the means of the two mixture of Gaussians is not large than a threshold, the results after graph convolution are not guaranteed with high probability to improve the linear separability. \n\nHowever, the statements in Theorem 4.4 is relatively vague. Note that PIFA is just one step of a graph convolution with the node features, plus a normalization step. What can we say about the performance of using the PIFA embedding?  Without the characteristic of the node features and the affinity of the graph convolution, it is hardly to have a convinsing conclusion. \n\nFurthermore, the requirement on $p > q$, i.e., the probability $p$ of having a link between two nodes having the same label $y_i=y_j$ should be larger than the probability of having a wrong link between two nodes having different labels $y_i \\neq y_j$. Is it necessary or not? Why? \n\n", "summary_of_the_paper": "The paper proposed a self-supervised learning framework for learning node feature by exploring the correlation between the node feature and the graph structure, which leverages the graph information based on neighborhood prediction. To be specific, the proposed GIANT approach is combined with the pre-trained language model BERT, and incorporated the XMC formalism based on XR-Transformer. Partial theoretical analysis is also presented. Experiments conducted on three large benchmark datasets show promissing improvements.", "summary_of_the_review": "The idea is clear and the empirical evaluation is strong. Since that the reviewer has some concerns on the provided theoretical analysis, it would be safe to decide after reading the feedback from the authors. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this submission, the authors presented a framework (GIANT) for self-supervised learning to improve LM by leveraging graph information. Reviewers agree that the method is somewhat novel, the (partial) theoretical analysis is interesting, and the evaluations are strong. We thank the authors for doing an excellent job in rebuttal which cleared essentially all the questions reviewers initially raised.
Decision: Accept (Poster)